Lesson plan
transposition table
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.