transposition table
≈ 4 min read
Names in other languages
- Françaistable de Transposition
- PortuguêsTabela de transposição
- DeutschTranspositionstabelle
- Englishtransposition table
- 中文换位表
- 中文换位表
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 reoccurs 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 games (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 tables 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.
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 reoccurs 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 games (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 tables 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.
Related techniques
Similar techniques can be used to cache evaluations of certain features of a position. For example, a pawn hash table can be used to store an evaluation of the pawn structures in a position. Since the number of pawn positions examined is generally much smaller than the total number of positions searched, the pawn hash table has a very high hit rate, allowing a program to spend more time on sophisticated pawn evaluations because they are reused many times. A refutation table can be used to store sequences of moves from the root node to leaf nodes. This includes the principal variation and responses to other lines showing that they are inferior. Refutation tables were sometimes used instead of transposition tables in the earlier years of computer chess, when memory was more limited. Some modern chess programs use refutation tables in addition to transposition tables for move ordering, while most do not use them at all. Static bitmaps of the possible moves of each type of piece on each space of the board can be cached at program initialization, so that the legal moves of a piece (or together, all legal moves for move generation) can be retrieved with a single memory load instead of having to be serially enumerated. These are commonly used in bitboard implementations.
See also
Minimax algorithm Alpha-beta pruning Zobrist hashing
Notes and references
External links
Transposition Tables Sigmachess.com Technical The Main Transposition Table (information on the data structure and implementation) The anatomy of chess programs T.A. Marsland, University of Alberta Transposition Table The Chess Programming Wiki
Text derived from https://en.wikipedia.org/w/index.php?oldid=1352587116 under CC BY-SA 4.0; modifications have been made.