Contents  Introduction  Basic Board  Representations  Bit Boards  Transposition  Tables  Generating Hash  Keys for Chess  Boards  History Tables  Pre-processing  move generation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Transposition Tables

In chess, there are often many ways to reach the same position.  For example, it doesn't matter whether you play 1. P-K4 ... 2. P-Q4 or 1. P-Q4... 2. P-K4; the game ends up in the same state.  Achieving identical positions in different ways is called transposing.

Now, of course, if your program has just spent considerable effort searching and evaluating the position resulting from 1. P-K4 ... 2. P-Q4, it would be nice if it were able to remember the results and avoid repeating this tedious work for 1. P-Q4... 2. P-K4.  This is why all chess programs, since at least Richard Greenblatt's Mac Hack VI in the late 1960's, have incorporated a transposition table.

A transposition table is a repository of past search results, usually implemented as a hash dictionary or similar structure to achieve maximum speed.  When a position has been searched, the results (i.e., evaluation, depth of the search performed from this position, best move, etc.) are stored in the table.  Then, when new positions have to be searched, we query the table first: if suitable results already exist for a specific position, we use them and bypass the search entirely.

There are numerous advantages to this process, including:

• Speed.  In situations where there are lots of possible transpositions (i.e., in the endgame, when there are few pieces on the board), the table quickly fills up with useful results and 90% or more of all positions generated will be found in it.
• Free depth.  Suppose you need to search a given position to a certain depth; say, four-ply (i.e., two moves for each player) ahead.  If the transposition table already contains a six-ply result for this position, not only do you avoid the search, but you get more accurate results than you would have if you had been forced to do the work!
• Versatility.  Every chess program has an "opening book" of some sort, i.e., a list of well-known positions and best moves selected from the chess literature and fed to the program to prevent it from making a fool out of itself (and its programmer) at the very beginning of the game.  Since the opening book's modus operandi is identical to the transposition table (i.e., look up the position, and spit out the results if there are any), why not initialize the table with the opening book's content at the beginning of the game?  This way, if the flow of the game ever leaves the opening book and later translates back into a position that was in it, there is a chance that the transposition table will still contain the appropriate information and be able to use it.

The only real drawback of the transposition table mechanism is its voracity in terms of memory.  To be of any use whatsoever, the table must contain several thousand entries; a million or more is even better.  At 16 bytes or so per entry, this can become a problem in memory-starved environments.

Other uses of transposition tables
CHESS 4.5 also employed hash tables to store the results of then-expensive computations which rarely changed in value or alternated between a small number of possible choices:

• Pawn structure.  Indexed only on the positions of pawns, this table requires little storage, and since there are comparatively few possible pawn moves, it changes so rarely that 99% of positions result in hash table hits.
• Material balance, i.e., the relative strength of the forces on the board, which only changes after a capture or a pawn promotion.

This may not be as useful in these days of plentiful CPU cycles, but the lesson is a valuable one: some measure of pre-processing can save a lot of computation at the cost of a little memory.  Study your game carefully; there may be room for improvement here.

Next : Generating Hash Keys for Chess Boards