Chess - Programming - Transposition Table

A database that stores results of previously performed searches.

• It is a way to greatly reduce the search space of a chess tree with little negative impact.
• Chess programs, during their brute-force search, encounter the same positions again and again, but from different sequences of moves, which is called a transposition.

When the search encounters a transposition, it is beneficial to 'remember' what was determined last time the position was examined, rather than redoing the entire search again.

• For this reason, chess programs have a transposition table, which is a large hash table storing information about positions previously searched, how deeply they were searched, and what we concluded about them.

A transposition table makes uses of Hash functions to convert chess positions into an almost unique, scalar signature, allowing fast index calculation as well as space saving verification of stored positions.

The major disadvantage of transposition tables is their size.

Refutation tables attempt to retain one of the advantages of transposition tables, when used with iterative deepening, but with smaller memory requirements.

• For each iteration, the search yields a path for each move from the root to a leaf node that results in either the correct minimax score or an upper bound on its value.
• This path from the d-1 ply search can be used as the basis for the search to d ply.
• Often, searching the previous iteration’s path or refutation for a move as the initial path examined for the current iteration will prove sufficient to refute the move one ply deeper.