Hash tables and transposition tables

[Kabir Shah]

I wanted to know whether hash tables in java are similar to transposition tables used in games.
Can any one give me link to some sources which deals with pseudo code for implementing transposition tables in artificial intelligence games. It will be better if all the pseudo codes are in java.

[Mich Robinson]

Transposition tables are implemented using hash tables and sometimes the terms are interchanged. These tables store the positions you've already examined and what score each position was were given. The idea of using them is quite simple though:

compress the board position down into a small hash code (an int ideally but a small string is fine)
search the transposition table to see if this code is already stored 

if it is then 
        no need to search further
        return the score held against the code
else
        continue recursive search of moves
        put score for this position into transposition table against small code

A few notes:

Transposition tables are stored as hash tables to make the search faster.

It still takes time to search a transposition table so there are trade-offs here.

Using transposition tables won't make your program play any better - it will just come up with the same evaluation a bit quicker.

Maximum search depth and the depth associated with the score for a position are also important.

Opening books can be stored in transposition tables and handled by the same code but these tables can get large quite quickly so they less useful in java applets etc.

Because of the size of these tables you would need to limit the growth. You could also prune away positions which are no longer possible to reach ie in chess if you've exchanged queens then there's no need to keep any positions which have queens on the board.

Some folks have put all positions possible into similar tables and abandoned all evaluation. These programs rely on a huge table and will play flawlessly if they move first but they play badly if moving 2nd as they know the game is lost so what does it matter what move is made. In either case the programs aren't much fun to play against.

I don't remember much about how your program played but I suspect you want to improve the way it plays before trying to make it play quicker.

Is your program playable on the web yet?

Mike

[Kabir Shah]

@Mich

Thanks for replying.

Talking about the evaluations of my program. I have made some modifications, I made provision to search for three in a row as well so the computer sees if there is no 4 but three then play that move instead of any other, however I am not getting a perfect AI as player1, No doubt it plays strong,but there is still a difference between strong and perfect player.

In connect4, there are many confusing concepts. There are times when there is only one move which can win but after many moves (beyond the current dept of search.). take for the example of the following move order(4-1 4-4, these numbers are the column numbers). Now here only way to win is by playing in column 4. (Its obvious to dominate middle column, but its not obvious every time).

My program plays stronger,it beats online applets, also had 2-2 with yours.

Further if you can help me with evaluations, let me know what should I do in order to make it better.

I am yet to make it as an applet,that wont take much time though, this improvement is going on in AI part, which has got nothing to do with the GUI, so I thought rather to focus on strength than display.

So talking about the hash tables, what should be the preferable size of it?

[Mich Robinson]

Gurudas Bhandarkar wrote:So talking about the hash tables, what should be the preferable size of it?

I don't use hash tables in my program so I can't give you a set figure. It will always be a compromise because of the points I raised earlier. I'd try out different sizes and see how often the hash table is used in normal play (show hash matches and maximum depth reached at the end of each search). If it isn't used much then you could ignore this feature. If it is used a lot then try getting the program to play itself but to use a separate and differently sized hash table for each side - you could then see how much difference it makes.

Gurudas Bhandarkar wrote:I am yet to make it as an applet,that wont take much time though

I'd of thought showing off your work should be the first priority! It would also make it easier to suggest improvements if we can see the program actually playing.

Gurudas Bhandarkar wrote:My program plays stronger,it beats online applets, also had 2-2 with yours.

That's a better result than I get when playing it! Can I ask what level my program was playing at and what level (or depth or thinking time) was yours running at. I'm just curious whether I need to improve the strength on my program. 2-2 against my program is actually quite a good result - it sounds like your program has come on quite well.

[Kabir Shah]

ok I have made an applet version which is too slow according to me.
Here it is: MY Connect-4 Applet
Just be careful that Human inputs should be legal,computer wont check them.
I have not added this feature yet to applet as of now. late on I will add it when I get a speedy applet.
The current depth is of 8plys.Also the applet is not auto playing, Press Play Button whenever you wish the computer to play.

[Mich Robinson]

It's good to see it actually playing!

I was intending on matching your program against mine for a few games and seeing how they faired but your current interface needs a fair bit of work and I'd suggest the following at the very least:

Only allow legal moves to play

Allow the user to take moves back

Indicate graphically where the computers move was

Allow the user to change the level or depth of search

There is a text box at the bottom which seems to do nothing

I'd include a random element which to make it a bit less predictable - your's opens in the centre every time

It should definitely auto play

I'd also start the program on a lower level because most people who will play it on the web will be playing for fun - I start mine off on a 4 ply search with a lot of the clever evaluations switched off. At this level it seemed to compete on par with yours (set at 8 ply). I then tried my program on the next level up (level=not bad which is still under 8 ply but more evaluation functions are turned on) and mine seemed to have a big advantage even though I gave yours first move each time. I assume this must be because more analysis is done of each board position when scoring.

I'd recommend getting the human interface cleaned up first and then you can more easily test it going forward and it will also make it more accessible to other users. It was very interesting playing them together.

Mike

[Kabir Shah]

I was intending on matching your program against mine for a few games and seeing how they faired but your current interface needs a fair bit of work and I'd suggest the following at the very least:
# Only allow legal moves to play
# Allow the user to take moves back
# Indicate graphically where the computers move was
# Allow the user to change the level or depth of search
# There is a text box at the bottom which seems to do nothing
# I'd include a random element which to make it a bit less predictable - your's opens in the centre every time
# It should definitely auto play

This will take some time tough to implement as currently I am thinking to improve the evaluation methods. You made a point that

I'd include a random element which to make it a bit less predictable - your's opens in the centre every time

but we all know that player 1 always wins iff he plays in center,not anywhere else.

# It should definitely auto play

Why auto play mode, I really did not get this point of yours?

# There is a text box at the bottom which seems to do nothing

The text box has the purpose of displaying moves and other things, for debugging purposes, I put an equivalent statement for System.out.println(), to display it on the text area, so that its easier for me to see what is going on.

I assume this must be because more analysis is done of each board position when scoring.

This is exactly what I am talking about.The evaluation and scoring.
I made provisions to check three in rows and odd row threats, what else should I do?
The question is how did you go about the evaluations?
Do you mind to share its outline,or may be pseudo code with me

[Mich Robinson]

The interface: Altering this should be easy by using the mouseDown method to see which column the user has clicked. Look for the lowest free square in that column and, if it's free, put the human's piece there. Then start the computer thinking on it's move. You could use the same mouseDown method to detect buttons ie new game, level or take back. Doing the above would make future testing of your software much easier and allow others to play your program without difficulty.

The random element: the aim is to make the program fun to play and if it always plays the same move each time then where's the fun? The random element would only nudge the score slightly in one direction or another. Alternatively at lower levels it could make the first move completely random. Playing in the centre guarantees a win under perfect play but neither your program or mine plays perfectly. The only program I did play that played "perfectly" had a huge database of positions to work with - it played perfectly if it moved first but it also played appallingly if it played 2nd as it figured it already had a lost game - this meant I ended up with a draw over a few games when playing it myself while I loose most of the time when playing my (non perfect) program at the slightly harder levels. I'm sure there's a moral in there somewhere.

Evaluation: I gave you a few links before detailing various techniques that can be employed. Part of the fun of writing these type of programs is thinking up new ways of looking at positions and trying to give the program a cleverer AI. The good thing about doing this yourself is that you get better at the game in question and your programming skills will increase dramatically.

PS if it makes you feel any better I'm working on a simple Othello program at the moment and I'm having big problems trying to make it play well. The good thing about having it play poorly is my kids quite enjoy playing it while they can still win.

[Kabir Shah]

well I am not a othello player, so I cannot judge your game, but it beats me straight out.