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...

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.

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 :-(

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?

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.

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.

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).

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...

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.

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. :)