Transposition/Refutation Tables

The following sequences of moves from the initial chess position result in the same position.

Sequence 1 - 1. P-K4..P-Q4 2. N-C3..P-KB4

Sequence 2 - 1. P-K4..P-KB4 2. N-C3..P-Q4

If, during the search, a value has been assigned to the position that arises after white's second move in the first sequence, it would be useful if this value could be stored. If then, at a later stage in the search, the same position occurs as a result of the second move sequence, the value of the position is known. In a game tree of depth 8 this would save the negamax procedure from searching an entire sub-tree of depth 5. Such information can be stored in a transposition table.

Due to alpha-beta cutoffs, the exact value of a position is not always known; sometimes only an upper or lower bound is known. This information is stored as it may be used to adjust the alpha-beta bounds if the same position arises again. The highest scoring move at such positions is also stored so that it may be considered early in the sequence of moves (see the section on move ordering). The table therefore becomes a transposition/refutation table.

Implementation of the Transposition/Refutation table

A table is created of a fixed size. A hash key is generated for any position that is to be added to the table and at this location the following information is stored:

A lock, to ensure the position in the table is identical to the position for which we are looking
The best move known at the position
The value of the position
A flag indicating whether the stored value is an upper or lower bound or a true value
A staleness flag (explained below)
The depth searched below the position to determine the stored value

A position is added to the table if there is no position currently held at its hash index. If a position is held at its hash index, the position is added only if it has been searched to a depth that is greater than or equal to the depth field value of the position held in the table, or if its staleness flag is set. The staleness flag on each index is set following each search. This allows positions stored in a previous search to be used in later searches. During a search, if a successful read is done on a hash index, its staleness flag is turned off.

Generation of the hash key is fast and is based on the work of Zorbrist (1970). In a game of chess there are twelve unique pieces that can be placed on any of sixty-four squares. A 12x64 element array of randomly independent integers can be used to represent all possible piece-square combinations. An extra two are used to represent the side on the move. The hash key for a position is generated by performing an exclusive-or on each of the relevant numbers from the array. An example will make this clear.

If the number 1234 represents a white king on square A3 and the number 7621 represents a black king on square E1 and the number 6152 represents a white knight on D7 then a position with a white king on A3, a black king on E1 and a white knight on D7 and no other pieces on the board would have the hash key 1234 XOR 7621 XOR 6152. The hash key can be easily updated as the search progresses.

Given a position with a hash key, h, the movement of a piece from a piece-square combination represented by the integer f, to another represented by the integer t, would give the new hash key: h XOR f XOR t. The Lock field of a table is used to verify that the position retrieved is the same as the position being evaluated in the search. The lock is an additional 31 bit integer that is generated in a similar fashion to the hash key itself. Potentially, some clashes may still occur so the move stored is verified before it is used Hyatt et al (1985). The size of the hash table may be specified in kilobytes either on the command line or via the user interface. Using 8000K as an example, Rival sets up the hash variables as follows.

Firstly, it determines the number of hash entries that will fit into the specified memory. Each hash index is currently uses 13 bytes. (8,000 * 1,024) / 13 = 630,153.
Next it determines the lowest power of two that exceeds this figure. 2^19 = 524,288, 2^20 = 1,048,576.
It then generates random integers between 0 and 1,048,575 for each piece/square combination.
This means that the hash key generated for any given position may be as high as 1,048,575. This exceeds the maximum hash entry (630,152), but is resolved when reading from or writing to the hash table. On a read or write, the index accessed will be (hashindex >= 630,153 ? hashindex-630,153 : hashindex).