Editing Transposition table (section)

{{short description|Cache of previously seen positions, and associated evaluations in a game tree}}
{{no footnotes|date=November 2017}}

A '''transposition table''' is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program.  If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position. Transposition tables are primarily useful in [[perfect-information game]]s (where the entire state of the game is known to all players at all times). The usage of transposition tables is essentially [[memoization]] applied to the tree search and is a form of [[dynamic programming]].  

Transposition tables are typically implemented as [[hash table]]s encoding the current board position as the hash index.  The number of possible positions that may occur in a game tree is an exponential function of depth of search, and can be thousands to millions or even much greater.  Transposition tables may therefore consume most of available system memory and are usually most of the [[memory footprint]] of game playing programs.