Transposition table
From Wikipedia, the free encyclopedia
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree.
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 has 4 possible transpositions, since either player may swap their move order. In general, after n moves, the maximum number of possible transpositions is n!². Although many of these will be 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 in constant time, without searching through the entire table.) 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.
It must be noted that 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 functions are designed to be very fast anyway. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a lower 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 uses other 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 have 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.
[edit] 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 perform sophisticated pawn evaluations without significantly reducing efficiency.
- 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.
