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

----

===== Hash functions =====

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.

----

===== Disadvantage of Transposition Tables =====

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.