🔒 Locked

Chess Transposition Tables

Started by Verminox Apr 21, 2009 at 7:01 AM 23 replies 7.8k views

Original Post

Apr 21, 2009 at 7:01 AM

Hey, I've started working on my own Xboard compatible Java chess engine. I have used pages such as the Beowulf project's Chess Programming Theory and the GameDev.net article on Chess Programming as references. My doubt arises in the implementation of transposition tables. I have managed to implement the hashing scheme to identify a Game State (board position) and to store it's score and the depth to which it is searched in a hashtable. However, this means that everytime I come across a transposition during a full tree search, I have to still generate all legal moves from that position again if I want to search deeper. In my opinion, the move generation could be avoided if we just stored a list of legal moves from the position in the transposition table as well, but this would increase the size of each item in the hashtable from around 20 bytes to 150-200 bytes. Considering that my application requires millions of entries in the hashtable at any given time, I don't know if this is viable solution. Does anybody have any idea of which method is better? Also, when does one start cleaning the hashtable? There is no point storing the transpositions occured at ply 2 when the game is at around ply 40 because that is never going to occur again. One way I can think of solving this is to add a 'lastUsed' variable for each transposition in the table, and before each search, prune the entire hashtable of old states. However, this would mean iterating through millions of hashtable entries at every search... So is this a viable option? What other solutions can be implemented? Please help...

alvaro

Apr 21, 2009 at 8:14 AM

Quote:
Original post by Verminox
My doubt arises in the implementation of transposition tables. I have managed to implement the hashing scheme to identify a Game State (board position) and to store it's score and the depth to which it is searched in a hashtable. However, this means that everytime I come across a transposition during a full tree search, I have to still generate all legal moves from that position again if I want to search deeper.

Assuming you are using alpha-beta pruning (and if you are not using it, drop everything and implement it first), you are missing a two very important pieces of data:
1) An enum indicating if the score stored is an exact score, an upper bound or a lower bound.
2) The move that was found to be best or that generated a beta cut.

This link seems to have a good description of what to put in the table: http://chessprogramming.wikispaces.com/Transposition+Table

Quote:
In my opinion, the move generation could be avoided if we just stored a list of legal moves from the position in the transposition table as well, but this would increase the size of each item in the hashtable from around 20 bytes to 150-200 bytes. Considering that my application requires millions of entries in the hashtable at any given time, I don't know if this is viable solution. Does anybody have any idea of which method is better?

This is not a very good idea. Regenerating moves is quite trivial and having more entries in your transposition table is a better use of your memory.

Quote:
Also, when does one start cleaning the hashtable? There is no point storing the transpositions occured at ply 2 when the game is at around ply 40 because that is never going to occur again. One way I can think of solving this is to add a 'lastUsed' variable for each transposition in the table, and before each search, prune the entire hashtable of old states. However, this would mean iterating through millions of hashtable entries at every search... So is this a viable option? What other solutions can be implemented?

There are several possibilities. What I do is simply erase the transposition tables when a move is played on the board. This might make the program a bit weaker, but it has two key advantages:
1) If you find a bug, you can reproduce it, since you start from a fresh state on every move.
2) Time control combined with iterative deepening is a bit easier to do.

The other popular alternative is having a lastUsed field in each entry, as you said. You don't need to clear old entries before each search. Instead, you can simply have a rule that says that you can always replace an old entry with a new one.

I hope that helps.

Verminox

Apr 21, 2009 at 12:23 PM

Quote:
Original post by alvaro
Assuming you are using alpha-beta pruning (and if you are not using it, drop everything and implement it first), you are missing a two very important pieces of data:
1) An enum indicating if the score stored is an exact score, an upper bound or a lower bound.
2) The move that was found to be best or that generated a beta cut.

This link seems to have a good description of what to put in the table: http://chessprogramming.wikispaces.com/Transposition+Table

Yes, I am indeed using Alpha-Beta pruning. I do check for accuracy of the score but did not implement it correctly in my transposition table, so thanks for remingind me that I have to fix it :-P. And yes, the bestMove is stored in the transposition table but I was just wondering whether the entire ordered list of moves should be stored, and you answered my question. Thanks. The link is also very useful.

Quote:

There are several possibilities. What I do is simply erase the transposition tables when a move is played on the board. This might make the program a bit weaker, but it has two key advantages:
1) If you find a bug, you can reproduce it, since you start from a fresh state on every move.
2) Time control combined with iterative deepening is a bit easier to do.

Hmm, I suppose so. I'll give that a shot then... Thanks for your help...

PS: How deep should an amateur chess program be able to search? Mine can search around 4-5 ply in a few seconds in the opening (not yet implemented books) and middle game but searching to 6 ply kinda kills it :-(

alvaro

Apr 21, 2009 at 1:02 PM

Quote:
Original post by Verminox
PS: How deep should an amateur chess program be able to search? Mine can search around 4-5 ply in a few seconds in the opening (not yet implemented books) and middle game but searching to 6 ply kinda kills it :-(

About twice that. :)

Of course, this depends a lot on what you include in the quiescence search and what moves you extend or penalize. But I wouldn't be comfortable if you cannot get to depth 9 in about 10 seconds.

Have you tried any move-ordering techniques? How many nodes per second are you visiting?

Verminox

Apr 21, 2009 at 1:30 PM

Quote:
Original post by alvaro
About twice that. :)

Of course, this depends a lot on what you include in the quiescence search and what moves you extend or penalize. But I wouldn't be comfortable if you cannot get to depth 9 in about 10 seconds.

Have you tried any move-ordering techniques? How many nodes per second are you visiting?

I have just about started writing the program so I have yet to implement quiescence search and other such extensions. My move ordering is based on values of the score retreived from the transposition table which was stored during a shallower search, no guesswork. However, my evaluation function is very weak at the moment (just scans material and mobility) and I feel that is causing bad move ordering. My hopes of a faster search rely on improving my evaluation function. Also I need to implement an opening book because searching 4-6 ply in the opening is giving me dissatisfactory results.

alvaro

Apr 21, 2009 at 1:43 PM

Quote:
Original post by Verminox
Quote:
Original post by alvaro
About twice that. :)

Of course, this depends a lot on what you include in the quiescence search and what moves you extend or penalize. But I wouldn't be comfortable if you cannot get to depth 9 in about 10 seconds.

Have you tried any move-ordering techniques? How many nodes per second are you visiting?

I have just about started writing the program so I have yet to implement quiescence search and other such extensions.

Ah. Then I recommend you do things in a different order:
* quiescence
* alpha-beta
* move ordering (for instance: killer move first, then captures in largest-victim/smallest-attacker order, then non-captures in history heuristic order)
* iterative deepening
* time control
* transposition tables
* pondering (thinking while it's not your turn)
* null-move pruning

Quote:
My move ordering is based on values of the score retreived from the transposition table which was stored during a shallower search, no guesswork.

That's a good idea, but the rest of the moves should be sorted using something like the order I suggested above. At the very least, consider captures before non-captures.

Quote:
However, my evaluation function is very weak at the moment (just scans material and mobility) and I feel that is causing bad move ordering.

Your lack of quiescence search is probably to blame.

Quote:
My hopes of a faster search rely on improving my evaluation function.

Quiescence, good move ordering and transposition tables are more relevant. Null-move pruning can also be a pretty nice boost to search depth.

Quote:
Also I need to implement an opening book because searching 4-6 ply in the opening is giving me dissatisfactory results.

Yes, implementing an opening book is quite trivial.

Are you using UCI as the interface to talk to your GUI? If you are not, you should definitely consider it. Some UCI GUIs will deal with the opening book for you.

Verminox

Apr 21, 2009 at 2:06 PM

Quote:

Ah. Then I recommend you do things in a different order:
* quiescence
* alpha-beta
* move ordering (for instance: killer move first, then captures in largest-victim/smallest-attacker order, then non-captures in history heuristic order)
* iterative deepening
* time control
* transposition tables
* pondering (thinking while it's not your turn)
* null-move pruning

Ahh, I did not know that quiescence search was so important. I thought it was to extend the search at violent positions, how would it help speed up the search? Maybe I am getting it wrong...

Quote:
Yes, implementing an opening book is quite trivial.

Are you using UCI as the interface to talk to your GUI? If you are not, you should definitely consider it. Some UCI GUIs will deal with the opening book for you.

I am using the XBoard protocol. Regardless, I want to implement my own opening book because I want the program to work fine without a GUI as well as I want the experience (I am doing this as a casual hobbyist project anyway).

alvaro

Apr 21, 2009 at 2:40 PM

Quote:
Original post by Verminox
Ahh, I did not know that quiescence search was so important. I thought it was to extend the search at violent positions, how would it help speed up the search? Maybe I am getting it wrong...

It's not about speed. It's about the results making some sense. Imagine you make a depth-20 search. In one of the leaves of the tree black has just captured a knight with a queen, but the knight was defended by a pawn. The evaluation will tell you that black is a knight ahead, which is totally bogus. A depth-1 program with quiescence search will probably beat a depth-10 program without it (I just made up the numbers).

Quote:
I am using the XBoard protocol.

I found UCI to be much better designed, but whatever floats your boat...

DpakoH

Apr 22, 2009 at 1:18 AM

something out off the topic:

@vermonix: can you share some more information about your project, what programming language are you using for example :) i very curious about chess projects and will be very excited if i can follow your progress, maybe if you are using a blog or smth to share your thoughts and experience developing chess engine.

best of luck,
y.

alvaro

Apr 22, 2009 at 4:46 AM

Quote:
Original post by DpakoH
@vermonix: can you share some more information about your project, what programming language are you using for example :)

Man, you could read the first sentence of the first post, at least. :)

DpakoH

Apr 22, 2009 at 4:50 AM

oopps, my bad. :) thx for pointing out

Verminox

Apr 24, 2009 at 6:31 AM

alvaro: Thanks for your help. My engine has finally started playing sensibly. I am still not able to reach 6 ply in under a minute, so I need to improve the search a bit. I think my move generation is very slow, and using lots of Java exceptions is not helping.

DpakoH: I am using Java to develop the chess engine. I call it Frittle, after the butterfly Frittillus that has chess-board like markings... You can download my first attempt at anything sensible. The current version has beaten amateur human players (like me) but fails against other engines even in easy mode. I still have a lot of things to improve. I just started this around 10 days ago. ..

alvaro

Apr 24, 2009 at 8:03 AM

Congratulations on your progress!

You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else.

The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place?

Also, you haven't told us how many nodes per second your program is visiting.

Verminox

Apr 24, 2009 at 12:00 PM

Quote:
Original post by alvaro
Congratulations on your progress!

You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else.

The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place?

Also, you haven't told us how many nodes per second your program is visiting.

Hmmm.. I guessed as much. I know Java isn't the best language for chess, but I like Java and since I am just doing this as a hobby I thought I could afford the slight performance hit.

I feel my move handling is messed up. In my game, there are two different functions for move validation (given source and destination square, is the move valid? if yes, return the new position of the board) and legal move generation (which generates all the possible moves for all pieces on the board and validates them). Considering that the validation function takes decent time and throws an exception in case the move is not valid, I think I am spending most of my time in the search just generating/validating moves (there must be thousands of exceptions being thrown in every search). I need to be able to generate only legal moves so that I can skip the validation step.

My program is searching around 12,500 nodes per second, which I know is extremely sluggish. My whole move generation is based on the exception model, so refactoring that is going to be a big task. But I think it is really necessary to speed things up.

On the topic of fixed size arrays: How do you mean? The only dynamic data structure I am using is a vector when generating moves, because I don't know how many moves might be possible. Plus, they need to be re-ordered before searching. The transposition table and opening book use fixed size data structures.

alvaro

Apr 24, 2009 at 1:05 PM

Quote:
Original post by Verminox
Hmmm.. I guessed as much. I know Java isn't the best language for chess, but I like Java and since I am just doing this as a hobby I thought I could afford the slight performance hit.

As long as the performance hit is reasonable, that's fine.

Quote:
I feel my move handling is messed up. In my game, there are two different functions for move validation (given source and destination square, is the move valid? if yes, return the new position of the board) and legal move generation (which generates all the possible moves for all pieces on the board and validates them). Considering that the validation function takes decent time and throws an exception in case the move is not valid, I think I am spending most of my time in the search just generating/validating moves (there must be thousands of exceptions being thrown in every search). I need to be able to generate only legal moves so that I can skip the validation step.

You don't really need to validate every move. You can delay the validation to the point when you are about to try the move, instead of validating all the moves when you generate them. In an alpha-beta search there will be many nodes where you hopefully only have to consider a few moves, since you'll get a beta cut.

Quote:
My program is searching around 12,500 nodes per second, which I know is extremely sluggish. My whole move generation is based on the exception model, so refactoring that is going to be a big task. But I think it is really necessary to speed things up.

Right now you are about two orders of magnitude slower than most programs. Most of that probably has nothing to do with Java, though.

Quote:
On the topic of fixed size arrays: How do you mean? The only dynamic data structure I am using is a vector when generating moves, because I don't know how many moves might be possible. Plus, they need to be re-ordered before searching.

You can reorder a fixed-size array; that has nothing to do with it. If that's the only dynamic data structure you have, you are in decent shape. However, you did mention that you had a function that returned the new position of the board, so that sounds like more dynamic memory allocation right there.

Most programs have a single copy of the board (or one per thread, if you go parallel), where you do and undo moves. You basically never need to make a copy of the board, which is expensive.

I hope some of that helps.

Verminox

Apr 24, 2009 at 3:00 PM

Quote:
Original post by alvaro
You don't really need to validate every move. You can delay the validation to the point when you are about to try the move, instead of validating all the moves when you generate them. In an alpha-beta search there will be many nodes where you hopefully only have to consider a few moves, since you'll get a beta cut.

In my program the 'validation' is synonymous to generating the new board position after the move (which in turn, lets me retreive information from the transposition table), so without that, I would not be able to order by moves for the alpha-beta search.

Quote:
Original post by alvaro
Most programs have a single copy of the board (or one per thread, if you go parallel), where you do and undo moves. You basically never need to make a copy of the board, which is expensive.

I hope some of that helps.

Oh, well, in that case, yeah I have a lot of dynamic memory allocation. A lot of GameState (position) objects being copied and each creating their own evaluation results and generating their own move list... You think using only one copy of the board will help improve speed? I had thought of doing this earlier but I wasn't able to implement undo-ing the move. That would require storing a lot of information about the move (like which piece was captured and if there was a promotion involved)... and what about if you had to undo 5-6 places back (coming out of the depth first search)?

Gah! I now feel like my entire code has been approached wrongly...

[Edited by - Verminox on April 25, 2009 12:00:17 AM]

alvaro

Apr 24, 2009 at 4:16 PM

Quote:
Original post by Verminox
You think using only one copy of the board will help improve speed? I had thought of doing this earlier but I wasn't able to implement undo-ing the move. That would require storing a lot of information about the move (like which piece was captured and if there was a promotion involved)... and what about if you had to undo 5-6 places back (coming out of the depth first search)?t, I would not be able to order by moves for the alpha-beta search.

Yes, I expect keeping a single copy of the board will improve speed a lot.

For the `undo' part, you need to remember:
* The move
* The piece captured
* The castlings that were allowed before the move (4 bits)
* How many non-pawn, non-capture moves had been played before the move (for the 50-move rule)

Undoing multiple levels is not a problem if you organize your code right. In the loop that goes through moves in your alpha-beta search, you'll have a call to do the move, a recursive call to search the resulting board and then a call to undo the move. You'll leave things the way they were when you are done, so you don't make any messes.

I don't understand the last part about not being "able to order by moves"...

Verminox

Apr 25, 2009 at 12:55 AM

Quote:
I don't understand the last part about not being "able to order by moves"...

Sorry about that, wrote that in the wrong place. That was for your first suggestion (about move validation). What I was trying to say was that my validation part occurs while I try to create the new board state. It is only after the new state is formed can I lookup the hashtable for a score from a shallower search which will help my move ordering. So my move 'validation' has to occur before I decide to start searching. I can't validate them as I search, because I won't know their tentative score (from shallower searches) and hence won't be able to order them.

Anyway, I'll try to use only one copy of the board. But that would probably take some time. Thanks a lot for your help.

PS: How do you get your engine to be rated (ELO)? I know WinBoard doesn't have a rating system but I think Arena does... How many tests wold I have to go through to get an approximate rating? (I know it won't be very accurate unless thousands of games are played).

PPS: Which chess engine have you worked on? Is it freely available?

Edit: I performed some Perft tests on my move generation and indeed it is the generation of moves itself that is hampering my search speed. In opening positions with lots of pieces I can barely generate 30,000 nodes per second, and in the endgame with few pieces I can generate about 75,000 nodes per second. Either way, I suppose until I improve my move generation there is no scope for search speeding...

[Edited by - Verminox on April 25, 2009 5:55:16 AM]

alvaro

Apr 25, 2009 at 8:15 AM

Quote:
Original post by Verminox
Quote:
I don't understand the last part about not being "able to order by moves"...

Sorry about that, wrote that in the wrong place. That was for your first suggestion (about move validation). What I was trying to say was that my validation part occurs while I try to create the new board state. It is only after the new state is formed can I lookup the hashtable for a score from a shallower search which will help my move ordering. So my move 'validation' has to occur before I decide to start searching. I can't validate them as I search, because I won't know their tentative score (from shallower searches) and hence won't be able to order them.

That sounds too expensive for move ordering. Look up history heuristic' and killer heuristic': Those are some very old tricks to sort the moves without having to actually play them.

Quote:
PS: How do you get your engine to be rated (ELO)? I know WinBoard doesn't have a rating system but I think Arena does... How many tests wold I have to go through to get an approximate rating? (I know it won't be very accurate unless thousands of games are played).

I'm not sure. There used to be people that would run many games among freely available engines and that would publish the results as a rating list, but I haven't been following the scene in years.

Quote:
PPS: Which chess engine have you worked on? Is it freely available?

I worked primarily on Ruy-Lopez, which is not freely available and which is very outdated by now. Four years ago I made an attempt to start a new engine with help from some people that were trying to learn. They ended up not helping much and I got too busy with other things. So the project is abandoned, but you can still find what I did here: https://opensvn.csie.org/traccgi/cpphome_chess/. I tried to keep the code clean, so you might find it useful. Feel free to ask questions about it.

EDIT: If nothing else in that project's site seems useful, at least you might benefit from the links page.

DpakoH

Apr 26, 2009 at 2:05 PM

i just tested your engine, it played better in the begining than in the end :) probably you are using an opening book.. the results is : i won quite easily and i am rated around 2000 elo points. however, i will play some more games with it later and get it out of normal openings and see how it handles the situation. but all i can do is to congratulate you. well done so far and keep going.

please keep us updated with your project status. i am always happy to test chess engines :D

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.