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.
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 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.