Transposition Table

From Chessprogramming wiki

Home *Search * Transposition Table

Salvador Dalí,The Persistence of Memory 1931

ATransposition Table,
first used inGreenblatt's programMac Hack VI^[1]^[2]^[3], is a database that stores results of previously performed searches. It is a way to greatly reduce the search space of achess tree with little negative impact. Chess programs, during theirbrute-force search, encounter the samepositions again and again, but from different sequences ofmoves, which is called atransposition. Transposition (andrefutation) tables are techniques derived fromdynamic programming^[4], a term coined byRichard E. Bellman in the 1950s, when programming meant planning and dynamic programming was conceived to optimally plan multistage processes^[5] .

How it works

When the search encounters atransposition, it is beneficial to 'remember' what was determined the last time the position was examined, rather than redoing the entire search again. For this reason, chess programs have a transposition table, which is a largehash table storing information about positions previously searched, how deeply they were searched, and what we concluded about them. Even if thedepth (draft) of the related transposition table entry is not big enough, or does not contain the right bound for a cutoff, abest (or good enough) move from a previous search can improvemove ordering, and save search time. This is especially true inside aniterative deepening framework, where one gains valuable table hits from previous iterations.

Hash functions

Hash functions convert chess positions into an almost unique, scalar signature, allowing fast index calculation as well as space-saving verification of stored positions.

Both, the more common Zobrist hashing as well BCH hashing use fast hash functions, to provide hash keys or signatures as a kind ofGödel number of chess positions, today typically64-bit wide. They areupdated incrementally duringmake andunmake move by either own-inverseexclusive or or by addition versus subtraction.

Address Calculation

The index is not based on the entire hash key because this is usually a 64-bit number, and with current hardware limitations, no hash table can be large enough to accommodate it. Therefore calculating the address or index requires a signaturemodulo a number of entries, for the power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly.

What Information is Stored

Typically, the following information is stored as determined by thesearch^[6] :

Zobrist- orBCH-key, to see whether the position is the right one while probing
Best- orRefutation move
Depth (draft)
Score,either withIntegrated Bound and Valueor otherwise with
Type of Node^[7]

PV-Node, Score isExact

All-Node, Score isUpper Bound

Cut-Node, Score isLower Bound

Age is used to determine when to overwrite entries from searching previous positions during thegame of chess

Table Entry Types

In analpha-beta search, we usually do not find the exact value of a position. But we are happy to know that the value is either too low or too high for us to be concerned with searching any further. If we have the exact value, of course, we store that in the transposition table. But if the value of our position is either high enough to set the lower bound, or low enough to set the upper bound, it is good to store that information also. So each entry in the transposition table is identified with thetype of node, often referred to asexact,lower- orupper bound.

Using the Transposition Table

Transposition Tables are an integral part of an engine's search. It is used in both search heuristics and move ordering.

Transposition Table Cutoffs

Depth, value, and bound information can be used to produce cutoffs and reduce redudant computation. In more advanced engines transposition table cutoffs are not performed on PV-Nodes.

A cutoff can be performed when the depth of entry is greater (or equal) to the depth of the current node and one of the following criteria is satisfied:

The entry type is EXACT
The entry type is LOWERBOUND and greater than or equal to beta
The entry type is UPPERBOUND and less than alpha

Hash Move

Main Article:Hash Move

Best move/Refutation move information from the transposition table is the most important part of move ordering. They are first in order and can be searched before other moves are generated. When the hash move fails high, generating other moves is not necessary. InStockfish, 75% of cutoffs produced in a position with hash moves are caused by the hash move.

Singular Extensions

Restricted SE is only attempted on a position where a TT entry exist, they entry has a valid TT move, the entry has a high enough depth, and the entry has exact or lowerbound bounds.

Collisions

Thesurjective mapping from chess positions to a signature and an, even more, denser index range impliescollisions, different positions share the same entries, for two different reasons, hopefully, rare ambiguous keys (type-1 errors), or regularly ambiguous indices (type-2 errors).

Cardinalities

The typical cardinalities of positions and signatures inside the search reflect the likelihood of collisions:

Cardinalities of positions and signatures	#
Upper bound for the number of reachablechess positions^[8]	1e46
Different64 bit keys	1.84e19
Some number of distinct nodes searched per game, assuming 100 moves times 1e8 nodes per move	1e10
Different32 bit keys	4.29e9
Some arbitrary table size in the number of entries	1e8

Index Collisions

Index collisions or type-2 errors^[9]^[10], where different hash keys index same entries, happen regularly. They require detection, realized by storing the signature as part of the hash entry, to check whether a stored entry matches the position while probing. Especially with the power of two entry tables, many programmers choose to trade-off space for accuracy and only store that part of the hash key not already considered as an index, or even less.

Key Collisions

Key collisions or type-1 errors are inherent in using signatures with far fewer bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature^[11]^[12]. When storing only a partial key, the chance of a collision greatly increases. To accept only hits wherestored moves arepseudo-legal decreases the chance of type-1 errors. On his computer chess page^[13],Ken Regan broached on chess engine bugs, anomalies and hash collisions, and mentions aShredder 9.1 game where a key collision might have caused a strange move^[14]^[15].

Bits Required

During theWCCC 1989 WorkshopNew Directions in Game-Tree Search,James Gillogly, author ofTech, discussed transposition table collisions^[16] . He produced the following table using theBirthday Paradox, where the columns are the number of positions stored and the rows are the probability of collision. The entries are the number of bits of combined address and check hash required to reduce the probability of collision to the desired amount.

Number of Positions:		105	106	107	108	109	1010
Collision probability:	.01	39	46	53	59	66	73
	.001	43	49	56	63	69	76
	.0001	46	53	59	66	73	79
	.00001	49	56	63	69	76	83

During the discussion,David Slate andKen Thompson pointed out that the Birthday Paradox does not apply to most programs, since the hash table will fill up and not all previous positions will be in the table; thus these figures must be regarded as an upper bound on the number of bits required for safety^[17]. The dangers of transposition table collisions were further studied byRobert Hyatt andAnthony Cozzie as published in their 2005 paperHash Collisions Effect^[18]. They gave a surprising answer to the question “Is it really worth all the effort to absolutely minimize signature collisions?”, and concluded that 64-bit signatures are more than sufficient.

Replacement Strategies

Because there are a limited number of entries in a transposition table, and because in modern chess programs, they can fill up very quickly, it is necessary to have a scheme by which the program can decide which entries would be most valuable to keep, i.e. a replacement scheme^[19] . Replacement schemes are used to solve an index collision when a program attempts to store a position in a table slot that already has a different entry in it. There are two opposing considerations to replacement schemes:

Entries that were searched to a high depth save more work per table hit than those searched to a low depth.
Entries that are closer to the leaves of the tree are more likely to be searched multiple times, making the table hits of them higher. Also, entries that were searched recently are more likely to be searched again.
Most well-performing replacement strategies use a mix of these considerations.

Always Replace

This replacement strategy is very simple, placing all emphasis on the second consideration. Any old entries are replaced immediately when a new entry is stored^[20].

Priority by Searched Nodes Count

This replacement strategy uses the number of nodes searched spent to obtain an entry, as replacement priority.

Priority by Move Ordering Position

This replacement strategy uses the position of entry move inmove ordering list as replacement priority. The main idea is that if the best move was not considered as a good cut-off candidate by the move-ordering algorithm, storing it in TT should provide better help for the search.

Depth-Preferred

This replacement strategy puts all emphasis on the first consideration. The only criterion in deciding whether to overwrite an entry is whether the new entry has a higher depth than the old entry.

Two-tier System

This strategy, devised byKen Thompson andJoe Condon^[21] , uses two tables, side by side. For each table slot, there is a depth-preferred and an always-replace entry^[22] .

Bucket Systems

This family of strategies is similar to the two-tier system, but any number of tiers (known as "buckets") can be used (typically the number is based on the size of a cache line). The difference is that the buckets are not specific to one consideration, but rather the new entry overwrites the entry in the bucket with the lowest depth^[23] .

Aging

Aging considers searches for different chess positions during gameplay. While early implementations and programs relying onroot pre-processing to guide search andevaluation were obligated to clear the hash table between root positions, most todays programs do not, profit from entries of previous searches. Nevertheless, to avoid persistence of old entries which may no longer occur from the current root, aging is used to likely replace those entries by new ones, even if their draft and flags would otherwise protect them. To implement aging, one often stores and compares the currenthalfmove clock as age, likely modulo some power two constant, depending on how many bits are used to store it inside an entry^[24]^[25].

TT and Parallel Search

Aglobal transposition table, shared by multiplethreads orprocesses is essential for effectiveparallel search algorithms on modern multi-core CPUs, and might be accessedlock-less, as proposed byRobert Hyatt andTim Mann^[26] .

Further Hash Tables

Besides storing the best move and scores of the search trees, furtherhash tables are often used to cache other features.

Maximizing Transpositions

Publications

1967 ...

Richard Greenblatt,Donald Eastlake,Stephen D. Crocker (1967).The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted (1988) inComputer Chess Compendium,pdf fromThe Computer History Museum or aspdf or ps fromDSpace atMIT

1970 ...

Albert Zobrist (1970).A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison, WI, USA. Reprinted (1990) inICCA Journal, Vol. 13, No. 2.,pdf
David Slate,Larry Atkin (1977).CHESS 4.5 - The Northwestern University Chess Program.Chess Skill in Man and Machine (ed.Peter W. Frey), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted (1988) inComputer Chess Compendium »Chess