Transposition table
Encyclopedia
In computer chess
and other computer games, transposition tables are used to speed up the search of the game tree
. Transposition tables are primarily useful in perfect information
games, meaning the entire state of the game is known to all players at all times.
Game playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling depth-first search
, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called transpositions
. In chess
, for example, the sequence of moves 1. d4 Nf6 2. c4 g6 (see algebraic chess notation
) has 4 possible transpositions, since either player may swap their move order. In general, after n moves, an upper limit on the possible transpositions is (n!)². Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times.
To avoid this problem, transposition tables are used. Such a table is a hash table
of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see if the position has already been analyzed; this can be done quickly, in expected constant time. If so, the table contains the value that was previously assigned to this position; this value is used directly. If not, the value is computed and the new position is entered into the hash table. This is essentially memoization
applied to the search function.
The number of positions searched by a computer often greatly exceeds the memory constraints of the system it runs on; thus not all positions can be stored. When the table fills up, less-used positions are removed to make room for new ones; this makes the transposition table a kind of cache
.
The computation saved by a transposition table lookup is not just the evaluation of a single position - if that were the case, it would hardly be worth the effort, since evaluation function
s are designed to be very fast anyway. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a shallower depth in the game tree are more valuable (since the size of the subtree rooted at such a node is larger) and are therefore given more importance when the table fills up and some entries must be discarded.
The hash table implementing the transposition table can have other uses than finding transpositions. In alpha-beta pruning
, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first. Of course there is no way of knowing the best move, but when iterative deepening
is used, the move which was found to be the best in a shallower search is a good approximation. Therefore this move is tried first. For storing the best child of a node, the entry corresponding to that node in the transposition table is used.
Use of a transposition table can lead to incorrect results if the Graph History Interaction problem is not studiously avoided. This problem arises in certain games because the history of a position may be important. For example, in chess
a player may not castle if the king or the rook to be castled with has moved during the course of the game. A common solution to this problem is to add the castling rights as part of the Zobrist hashing
key. Another example is draw by repetition
: given a position, it may not be possible to determine if it has already occurred. A solution to the general problem is to store history information in each node of the transposition table, but this is inefficient and rarely done in practice.
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
and other computer games, transposition tables are used to speed up the search of the game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
. Transposition tables are primarily useful in perfect information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
games, meaning the entire state of the game is known to all players at all times.
Game playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called transpositions
Transposition (chess)
A transposition in chess is a sequence of moves that results in a position which may also be reached by another, more common sequence of moves. Transpositions are particularly common in opening, where a given position may be reached by different sequences of moves...
. In chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, for example, the sequence of moves 1. d4 Nf6 2. c4 g6 (see algebraic chess notation
Algebraic chess notation
Algebraic notation is a method for recording and describing the moves in a game of chess. It is now standard among all chess organizations and most books, magazines, and newspapers...
) has 4 possible transpositions, since either player may swap their move order. In general, after n moves, an upper limit on the possible transpositions is (n!)². Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times.
To avoid this problem, transposition tables are used. Such a table is a hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see if the position has already been analyzed; this can be done quickly, in expected constant time. If so, the table contains the value that was previously assigned to this position; this value is used directly. If not, the value is computed and the new position is entered into the hash table. This is essentially memoization
Memoization
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
applied to the search function.
The number of positions searched by a computer often greatly exceeds the memory constraints of the system it runs on; thus not all positions can be stored. When the table fills up, less-used positions are removed to make room for new ones; this makes the transposition table a kind of cache
Cache
In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
.
The computation saved by a transposition table lookup is not just the evaluation of a single position - if that were the case, it would hardly be worth the effort, since evaluation function
Evaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
s are designed to be very fast anyway. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a shallower depth in the game tree are more valuable (since the size of the subtree rooted at such a node is larger) and are therefore given more importance when the table fills up and some entries must be discarded.
The hash table implementing the transposition table can have other uses than finding transpositions. In alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first. Of course there is no way of knowing the best move, but when iterative deepening
Iterative deepening depth-first search
Iterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...
is used, the move which was found to be the best in a shallower search is a good approximation. Therefore this move is tried first. For storing the best child of a node, the entry corresponding to that node in the transposition table is used.
Use of a transposition table can lead to incorrect results if the Graph History Interaction problem is not studiously avoided. This problem arises in certain games because the history of a position may be important. For example, in chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
a player may not castle if the king or the rook to be castled with has moved during the course of the game. A common solution to this problem is to add the castling rights as part of the Zobrist hashing
Zobrist hashing
Zobrist hashing is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once...
key. Another example is draw by repetition
Threefold repetition
In chess and some other abstract strategy games, the threefold repetition rule states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions need not occur in succession...
: given a position, it may not be possible to determine if it has already occurred. A solution to the general problem is to store history information in each node of the transposition table, but this is inefficient and rarely done in practice.
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 pawnPawn (chess)The pawn is the most numerous and weakest piece in the game of chess, historically representing infantry, or more particularly armed peasants or pikemen. Each player begins the game with eight pawns, one on each square of the rank immediately in front of the other pieces...
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.
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