How to improve performance using Transposition Table in Game Playing?

Question

I have implemented iterative deepening with alpha-beta pruning in my game and I also added a Transposition Table to store already evaluated boards.

Right now, I am doing the following:

1. When running iterative deepening, at depth = 0 it evaluates and stores all positions with their scores in TT.
2. Now, when it re-runs with depth = 1. I simply return the value of the board if it exists in the TT. This stops the algorithm at depth = 0 as all values are already in the TT for depth = 0 boards.

If I return values from TT when the depth limit is reached eg. depth = MAX_DEPTH then big sub-trees will never be cut.

So, I am not understanding how should I re-use the values stored in the TT for making my game faster?

Answer 1

I will use chess for explanation rethoric in this answer, of course this reasoning with slight modifications can be applied for other board games as well.

Transposition Tables in board game programs are caches which store already evaluated boards in a cache. It is great to have an easy-to-handle cache value which would uniquely identify a position, like:

WKe5Qd6Pg2h3h4 BKa8Qa7

So if you get to a position, you check for the cache key to be present and if so, then reuse its evaluation. Whenever you visit a position at depth=0, after it's properly evaluated, it can be cached. So, if some moves are made, in the sub-variations you can more-or-less jump over the evaluation. For example, let's consider the example that in the starting position white moved 1. Nf3 and black replied 1... Nf6. After the resulting positions for both plies the position was cached, white's 2. Ng1 needs evaluation, since this was not evaluated nor cached yet, but Black's possible 2... Ng8 doesn't need to be evaluated, because it's resulting in the starting position.

Of course, you can do more aggressive caching and store positions up to depth = 1 or even more.

You will need to make sure that you do not miss some strategic details of the game. In the case of chess you will need to keep in mind:

• the 50-move rule's effect
• 3-time repetition draw
• who's on the move
• were/are some special moves like castling or en-passant possible in the past/in the present and not at the other case

So, you might want to add some further nuances into your algorithm, but to answer the original question: positions already occurred in the game or being very high in the variation table can be cached and more-or-less ignored (the more means in most of the cases, the less means the nuances outlined above)