25,161
edits
Changes
Created page with "'''Home * Search * Transposition Table''' FILE:The_Persistence_of_Memory.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/The_Persistence_of_Memo..."
'''[[Main Page|Home]] * [[Search]] * Transposition Table'''
[[FILE:The_Persistence_of_Memory.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/The_Persistence_of_Memory|
[[Arts#Dali|Salvador Dalí]], [https://en.wikipedia.org/wiki/The_Persistence_of_Memory The Persistence of Memory] 1931 ]]
A '''Transposition Table''',<br/>
first used in [[Richard Greenblatt|Greenblatt's]] program [[Mac Hack#HashTable|Mac Hack VI]] <ref>[[Richard Greenblatt]], [[Donald Eastlake]] and [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]</ref> <ref>[[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''') in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/259fbfd2b39b8ee4/80c64ba0f632fc31 Re: Berliner vs. Botvinnik Some interesting points], post 8 by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 06, 1996 » Transposition Table in [[Mac Hack]]</ref> , is a database that stores results of previously performed searches. It is a way to greatly reduce the search space of a [[Search Tree|chess tree]] with little negative impact. Chess programs, during their [[Brute-Force|brute-force]] search, encounter the same [[Chess Position|positions]] again and again, but from different sequences of [[Moves|moves]], which is called a [[Transposition|transposition]]. Transposition (and [[Refutation Table|refutation]]) tables are techniques derived from [[Dynamic Programming|dynamic programming]] <ref>[https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming Algorithms that use dynamic programming from Wikipedia]</ref> , a term coined by [[Richard E. Bellman]] in the 1950s, when programming meant planning, and dynamic programming was conceived to optimally plan multistage processes <ref>[[Mathematician#SDasgupta|Sanjoy Dasgupta]], [[Mathematician#CHPapadimitriou|Christos H. Papadimitriou]], [[Mathematician#UVVazirani|Umesh Vazirani]] ('''2006'''). ''[http://www.cs.berkeley.edu/%7Evazirani/algorithms.html Algorithms]''. [https://en.wikipedia.org/wiki/McGraw-Hill McGraw-Hill], ISBN: 978-0073523408, [http://www.amazon.com/gp/product/0073523402?ie=UTF8&tag=ebookdire-20&link_code=as3&camp=211189&creative=373489&creativeASIN=0073523402 amazon], Chapter 6, Dynamic programming</ref> .
=How it works=
When the search encounters a [[Transposition|transposition]], it is beneficial to 'remember' what was determined 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 large [[Hash Table|hash table]] storing information about positions previously searched, how deeply they were searched, and what we concluded about them. Even if the [[Depth|depth]] (draft) of the related transposition table entry is not big enough, or does not contain the right bound for a cutoff, a [[Best Move|best]] (or good enough) move from a previous search can improve [[Move Ordering|move ordering]], and save search time. This is especially true inside an [[Iterative Deepening|iterative deepening]] framework, where one gains valuable table hits from previous iterations.
==Hash functions==
[https://en.wikipedia.org/wiki/Hash_function Hash functions] convert chess positions into an almost unique, scalar signature, allowing fast index calculation as well as space saving verification of stored positions.
* [[Zobrist Hashing]]
* [[BCH Hashing]]
Both, the more common Zobrist hashing as well BCH hashing use fast hash functions, to provide hash keys or signatures as a kind of [https://en.wikipedia.org/wiki/G%C3%B6del_number Gödel number] of chess positions, today typically [[Quad Word|64-bit]] wide. They are [[Incremental Updates|updated incrementally]] during [[Make Move|make]] and [[Unmake Move|unmake move]] by either own-inverse [[General Setwise Operations#ExclusiveOr|exclusive 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. Therefor to calculate the address or index requires signature [https://en.wikipedia.org/wiki/Modulo_operator modulo] number of entries, for power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly.
<span id="Collisions"></span>
=Collisions=
The [https://en.wikipedia.org/wiki/Surjection surjective] mapping from chess positions to a signature and an even more denser index range implies '''collisions''', different positions share 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, reflects the likelihood of collisions:
{| class="wikitable"
|-
! Cardinalities of positions and signatures
! #
|-
| Upper bound for the number of reachable [[Chess Position|chess positions]] <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>
| style="text-align:right;" | 1e46
|-
| Different [[Quad Word|64 bit]] keys
| style="text-align:right;" | 1.84e19
|-
| Some number of distinct nodes searched per game,<br/>assuming 100 moves times 1e8 nodes per move
| style="text-align:right;" | 1e10
|-
| Different [[Double Word|32 bit]] keys
| style="text-align:right;" | 4.29e9
|-
| Some arbitrary table size in number of entries
| style="text-align:right;" | 1e8
|}
<span id="IndexCollisions"></span>
==Index Collisions==
Index collisions or type-2 errors <ref>[[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) in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b9de346eb1e8300/ Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996</ref> , 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. Specially with 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 index, or even less.
<span id="KeyCollisions"></span>
==Key Collisions==
Key collisions or type-1 errors are inherent in using signatures with far less bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012</ref> . When storing only a partial key, the chance of a collision greatly increases. To accept only hits where [[Hash Move|stored moves]] are [[Pseudo-Legal Move|pseudo-legal]] decreases the chance of type-1 errors. On his computer chess page <ref>[http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate Regan]]</ref>, [[Kenneth Wingate Regan|Ken Regan]] broached on chess engine bugs, anomalies and hash collisions, and mentions a [[Shredder|Shredder 9.1]] game where a key collision might have caused a strange move <ref>[http://www.chessgames.com/perl/chessgame?gid=1352348 Pablo Lafuente vs Shredder (Computer) (2005)] from [http://www.chessgames.com/index.html chessgames.com]</ref> <ref>[http://www.chessbase.com/newsdetail.asp?newsid=2525 Current tournaments – Sanjin, Biel, Argentina, Israel], [[ChessBase|ChessBase News]], July 21, 2005</ref> .
<span id="bits"></span>
==Bits Required==
During the [[WCCC 1989]] Workshop [[WCCC 1989#Workshop|New Directions in Game-Tree Search]], [[James Gillogly]], author of [[Tech]], discussed transposition table collisions <ref>[[James Gillogly]] ('''1989'''). ''Transposition Table Collisions''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]</ref> . He produced the following table using the [https://en.wikipedia.org/wiki/Birthday_problem Birthday 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.
{| class="wikitable"
|-
! colspan="2" | Number of Positions:
! 10<span style="font-size: 80%; vertical-align: super;">5</span>
! 10<span style="font-size: 80%; vertical-align: super;">6</span>
! 10<span style="font-size: 80%; vertical-align: super;">7</span>
! 10<span style="font-size: 80%; vertical-align: super;">8</span>
! 10<span style="font-size: 80%; vertical-align: super;">9</span>
! 10<span style="font-size: 80%; vertical-align: super;">10</span>
|-
! rowspan="4" | Collision<br/>probability:
| style="text-align:left;" | .01
| style="text-align:right;" | 39
| style="text-align:right;" | 46
| style="text-align:right;" | 53
| style="text-align:right;" | 59
| style="text-align:right;" | 66
| style="text-align:right;" | 73
|-
| style="text-align:left;" | .001
| style="text-align:right;" | 43
| style="text-align:right;" | 49
| style="text-align:right;" | 56
| style="text-align:right;" | 63
| style="text-align:right;" | 69
| style="text-align:right;" | 76
|-
| style="text-align:left;" | .0001
| style="text-align:right;" | 46
| style="text-align:right;" | 53
| style="text-align:right;" | 59
| style="text-align:right;" | 66
| style="text-align:right;" | 73
| style="text-align:right;" | 79
|-
| style="text-align:left;" | .00001
| style="text-align:right;" | 49
| style="text-align:right;" | 56
| style="text-align:right;" | 63
| style="text-align:right;" | 69
| style="text-align:right;" | 76
| style="text-align:right;" | 83
|}
During the discussion, [[David Slate]] and [[Ken Thompson]] pointed out that the Birthday Paradox is not applicable 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 <ref>[[James Gillogly]] ('''1989'''). ''New Directions in Game-Tree Search - First Workshop Session''. [[ICGA Journal#12_2|ICCA Journal, Vol. 12, No. 2]]</ref>. The dangers of transposition table collisions were further studied by [[Robert Hyatt]] and [[Anthony Cozzie]] as published in their 2005 paper ''Hash Collisions Effect'' <ref>[[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]</ref>. They gave an 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.
<span id="Entry"></span>
=What Information is Stored=
Typically, the following information is stored as determined by the [[Search|search]] <ref>[[Dennis Breuker]], [[Jos Uiterwijk]], and [[Jaap van den Herik]] ('''1997'''). ''Information in Transposition Tables''. [[Advances in Computer Chess 8]]</ref> :
* [[Zobrist Hashing|Zobrist-]] or [[BCH Hashing|BCH-key]], to look whether the position is the right one while probing
* [[Best Move|Best-]] or [[Refutation Move|Refutation move]]
* [[Depth]] (draft)
* [[Score]], ''either with'' [[Integrated Bounds and Values|Integrated Bound and Value]] ''or otherwise with''
* [[Node Types|Type of Node]] <ref>[[MTD(f)]]- and some [[Principal Variation Search|PVS]]-implementations store distinct [[Upper Bound|upper]] and [[Upper Bound|lower bound]] scores, rather than one score with flags</ref>
: [[Node Types#PV|PV-Node]], Score is [[Exact Score|Exact]]
: [[Node Types#ALL|All-Node]], Score is [[Upper Bound]]
: [[Node Types#CUT|Cut-Node]], Score is [[Lower Bound]]
* [[Transposition Table#Aging|Age]] is used to determine when to overwrite entries from searching previous positions during the [[Chess Game|game of chess]]
=Table Entry Types=
In an [[Alpha-Beta|alpha-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 the [[Node Types|type of node]], often referred to as [[Exact Score|exact]], [[Lower Bound|lower]]- or [[Upper Bound|upper bound]].
<span id="ReplacementStrategies"></span>
=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 <ref>[[Dennis Breuker]], [[Jos Uiterwijk]] and [[Jaap van den Herik]] ('''1994'''). ''Replacement Schemes for Transposition Tables''. [[ICGA Journal#17_4|ICCA Journal, Vol. 17, No. 4]]</ref> . 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.
<span id="AlwaysReplace"></span>
==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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47373&start=28 Re: Transposition table usage in quiescent search?] by [[Robert Hyatt]], [[CCC]], March 06, 2013</ref> .
==Priority by Searched Nodes Count==
This replacement strategy uses number of nodes searched spent to obtain an entry, as replacement priority.
==Priority by Move Ordering Position==
This replacement strategy uses position of entry move in [[Move Ordering|move ordering]] list as replacement priority. The main idea is that if the best move was not considered as good cut-off candidate by move-ordering algorithm, storing it in TT should provide better help for the search.
<span id="DepthPreferred"></span>
==Depth-Preferred==
This replacement strategy puts all emphasis on the first consideration. The only criteria in deciding whether to overwrite an entry is whether the new entry has a higher depth than the old entry.
<span id="TwoTier"></span>
==Two-tier System==
This strategy, devised by [[Ken Thompson]] and [[Joe Condon]] <ref>[[Joe Condon]] and [[Ken Thompson]] ('''1983'''). ''BELLE Chess Hardware''. [[Advances in Computer Chess 3]]</ref> , uses two tables, side by side. For each table slot, there is a depth-preferred and an always-replace entry <ref>[[Dennis Breuker]], [[Jos Uiterwijk]] and [[Jaap van den Herik]] ('''1996'''). ''Replacement Schemes and Two-Level Tables''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref> .
<span id="Bucket"></span>
==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 cacheline). 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 <ref>[[Don Beal]] and [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]</ref> .
<span id="Aging"></span>
==Aging==
Aging considers searches of different chess positions during game play. While early implementations and programs relying on [[Piece-Square Tables#Preprocessing|root pre-processing]] to guide search and [[Evaluation|evaluation]] were obligated to clear the hash table between root positions, most todays programs do not, to 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 current [[Halfmove Clock|halfmove clock]] as age, likely modulo some power two constant, depending on how many bits are used to store it inside an entry <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59047 Transposition Age Tutorial] by [[Dennis Sceviour]], [[CCC]], January 25, 2016</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59960 Hashtable aging] by [[Martin Fierz]], [[CCC]], April 25, 2016</ref>.
=TT and Parallel Search=
A [[Shared Hash Table|global transposition table]], shared by multiple [[Thread|threads]] or [[Process|processes]] is essential for effective [[Parallel Search|parallel search]] algorithms on modern multi core cpus, and might be accessed [[Shared Hash Table#Lockless|lock-less]], as proposed by [[Robert Hyatt]] and [[Tim Mann]] <ref>[[Robert Hyatt]] and [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]</ref> .
=Further Hash Tables=
Besides storing the best move and scores of the search trees, further [[Hash Table|hash tables]] are often used to cache other features.
* [[Evaluation Hash Table]]
* [[Material Hash Table]]
* [[Pawn Hash Table]]
* [[Principal Variation#SeparateTT|Separate TT for the PV]]
=Maximizing Transpositions=
* [[Enhanced Transposition Cutoff]]
* [[Repetitions]]
=See also=
* [[CPW-Engine_transposition]]
* [[Fifty-move Rule]]
* [[Graph History Interaction]]
* [[Population Count#HammingDistance|Hamming Distance]] <ref>[https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001</ref>
* [[Hash Move]]
* [[Hash Table]]
* [[Memory#HugePages|Huge Pages]]
* [[Integrated Bounds and Values]]
* [[Interior Node Recognizer]]
* [[Iterative Deepening]]
* [[Lasker-Reichhelm Position]] (Fine #70)
* [[Move Ordering]]
* [[Path-Dependency]]
* [[Persistent Hash Table]]
* [[Refutation Table]]
* [[Repetitions]]
* [[Search Instability]]
* [[Shared Hash Table]]
* [[Transposition]]
* [[Search Statistics#TTStatistics|TT Statistics]]
=Publications=
==1967 ...==
* [[Richard Greenblatt]], [[Donald Eastlake]], [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]
==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''') in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2.]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf 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''') in [[Computer Chess Compendium]] » [[Chess (Program)|Chess]]
==1980 ...==
* [[Harry Nelson]] ('''1985'''). ''Hash Tables in Cray Blitz''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[James Gillogly]] ('''1989'''). ''Transposition Table Collisions''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Harry Nelson]] ('''1989'''). ''Some Observations about Hash Tables in Cray Blitz''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
==1990 ...==
* [[Dennis Breuker]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1996'''). ''Replacement Schemes and Two-Level Tables''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]].
* [[Don Beal]] and [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
* [[Dennis Breuker]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1997'''). ''Information in Transposition Tables''. [[Advances in Computer Chess 8]]
* [[Dennis Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/ Memory versus Search in Games]''. Ph.D. Thesis, [[Maastricht University|Universiteit Maastricht]], The Netherlands. ISBN 90-9012006-8.
==2000 ...==
* [[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf] » [[Parallel Search]] <ref>[https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013</ref>
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Viljem Žumer]] ('''2005'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1491153 The Representation of Chess Game]''. Proceedings of the 27th International Conference on Information Technology Interfaces
* [[Joel Veness]], [[Alan Blair]] ('''2007'''). ''Effective Use of Transposition Tables in Stochastic Game Tree Search''. IEEE Symposium on Computational Intelligence and Games, [http://jveness.info/publications/cig2007%20-%20effective%20use%20of%20transposition%20tables%20in%20stochastic%20game%20tree%20search.pdf pdf]
* [[Rune Rasmussen]], [[Frédéric Maire]], [[Ross Hayward]] ('''2007'''). ''[http://eprints.qut.edu.au/12527/ A Template Matching Table for Speeding-Up Game-Tree Searches for Hex]''. 20th Australian Joint Conference on Artificial Intelligence » [[Hex]]
==2010 ...==
* [[Timothy Furtak]], [[Michael Buro]] ('''2011'''). ''Using Payoff-Similarity to Speed Up Search''. [[Conferences#IJCAI2011|IJCAI 2011]], [http://ijcai.org/papers11/Papers/IJCAI11-097.pdf pdf] » [https://en.wikipedia.org/wiki/Skat_%28card_game%29 Skat]
* [[Robert Hyatt]] ('''2014'''). ''A Solution to Short PVs Caused by Exact Hash Matches''. [[ICGA Journal#37_3|ICGA Journal, Vol. 37, No. 3]] » [[Principal Variation#SeparateTT|Separate TT for the PV]]
=Forum Posts=
==1990 ...==
* [http://groups.google.de/group/rec.games.chess/browse_thread/thread/87d436c2293f9138 Hash tables - Clash!!! What happens next?] by [[Valavan Manohararajah]], [[Computer Chess Forums|rec.games.chess]], March 14, 1994
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/a9d5fb3e489196ed/68f9f93c938f3349 Hash table question] by [[John Stanback]], [[Computer Chess Forums|rec.games.chess]], March 23, 1994
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Taxgk4l-S90/ggkiWEVavYsJ hash mem in win-chess progs] by [[Adrian Millett|Pc Sol]], [[Computer Chess Forums|rgcc]], September 28, 1995 » [[Windows]]
'''1996'''
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/34826d5ec57f0923 Transposition table] by Matthew Bengtson, [[Computer Chess Forums|rgcc]], January 25, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b9de346eb1e8300/ Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/p8GbiiLjp0o/81vZ3czsthIJ Alpha-Beta window in transposition tables?] by Marty Bochane, [[Computer Chess Forums|rgcc]], October 25, 1996 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55889&start=8 Re. Fail low after fail high] by [[Marcel van Kervinck]], [[CCC]], April 05, 2015 » [[Fail-Low ]], [[Fail-High]]</ref>
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/259fbfd2b39b8ee4/80c64ba0f632fc31 Re: Berliner vs. Botvinnik Some interesting points], post 8 by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 06, 1996 » Transposition Table in [[Mac Hack]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/77ec7b3a94555fb4/d8019f5c3716cd1a hash table fail high/fail low problem] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], November 26, 1996
'''1997'''
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d2c20a63f75f2d4b Hash functions for use with a transition table] by [[Tim Foden]], [[Computer Chess Forums|rgcc]], March 5, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/9b240379394bc968 Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997 » [[BCH Hashing]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/1d601e208c97c395 Handling of repetition (draw) in transposition table] by Bjarke Dahl Ebert, [[Computer Chess Forums|rgcc]], June 9, 1997 » [[Repetitions]]
* [https://www.stmintz.com/ccc/index.php?id=10317 double hash tables] by [[Chris Whittington]], [[CCC]], October 01, 1997
'''1998'''
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=14226 Hash tables and data-cache, some programmer stuff...] by [[Ed Schroder|Ed Schröder]], [[CCC]], January 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=19515 Hash Table Size Versus Performance] by Steven Juchnowski, [[CCC]], May 30, 1998
* [https://www.stmintz.com/ccc/index.php?id=21654 Selective deepening and Hashtables] by [[Werner Inmann]], [[CCC]], June 30, 1998
* [https://www.stmintz.com/ccc/index.php?id=58 Using too-shallow mate scores from the hash table] by [[David Eppstein]], [[CCC]], July 05, 1998 » [[Score#MateScores|Mate Scores]]
: [https://www.stmintz.com/ccc/index.php?id=21814 Re: Using too-shallow mate scores from the hash table] by [[David Eppstein]], [[CCC]], July 06, 1998
: [https://www.stmintz.com/ccc/index.php?id=21838 Re: Using too-shallow mate scores from the hash table] by [[Don Dailey]], [[CCC]], July 07, 1998
* [https://www.stmintz.com/ccc/index.php?id=22816 draw by repetition and hash tables] by [[Werner Inmann]], [[CCC]], July 24, 1998
'''1999'''
* [https://www.stmintz.com/ccc/index.php?id=43613 Hash collisions and a little maths] by [[Rémi Coulom]], [[CCC]], February 18, 1999
* [https://www.stmintz.com/ccc/index.php?id=43990 Hash Collisions] by [[KarinsDad]], [[CCC]], February 21, 1999
* [https://www.stmintz.com/ccc/index.php?id=72221 Problem with draws by rep and hash table] by [[James Robertson]], [[CCC]], October 07, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=93686 Can we use hash table at root?] by Tim, [[CCC]], January 31, 2000 » [[Root]]
* [https://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/ab55c5d57a3a1fd1 Re: Atomic write of 64 bits] by [[Frans Morsch]], [https://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], September 25, 2000 » [[MMX]], [[Parallel Search]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/e70ef78a6a17f225 hashing function] by [[Vladimir Medvedev|Vladimir R. Medvedev]], [[Computer Chess Forums|rgcc]], October 17, 2000
* [https://www.stmintz.com/ccc/index.php?id=143022 Hash table efficiency] by [[Miguel A. Ballicora]], [[CCC]], December 05, 2000 » [[Gaviota]], [[Search Statistics]]
* [https://www.stmintz.com/ccc/index.php?id=143234 Why not store both a lower and an upper bound in a hashtable?] by [[Leen Ammeraal]], [[CCC]], December 06, 2000
'''2001'''
* [https://www.stmintz.com/ccc/index.php?id=175221 A fast hash -- assuming you are not planning to do incremental updates] by [[Dann Corbit]], [[CCC]], June 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=182927 "Don't trust draw score" <=Is it true?] by [[Teerapong Tovirat]], [[CCC]], August 08, 2001 » [[Repetitions]], [[Path-Dependency]]
* [https://www.stmintz.com/ccc/index.php?id=200366 About random numbers and hashing] by [[Severi Salminen]], [[CCC]], December 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001
* [https://www.stmintz.com/ccc/index.php?id=203516 When to RecordHash()?] by [[Sune Fischer]], [[CCC]], December 25, 2001
'''2002'''
* [https://www.stmintz.com/ccc/index.php?id=214125 Non power of two hash table sizes] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], February 18, 2002
* [https://www.stmintz.com/ccc/index.php?id=214562 Detecting Draws using a Small Hash Table?] by [[Steve Maughan]], [[CCC]], February 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=252097 hash entry replacement schemes] by [[Scott Farrell]], [[CCC]], September 14, 2002
* [https://www.stmintz.com/ccc/index.php?id=252598 hash numbers requested: authors please read] by [[James Swafford]], [[CCC]], September 17, 2002
'''2003'''
* [https://www.stmintz.com/ccc/index.php?id=291039 How important is a big hash table? Measurements...] by [[Tom Kerrigan]], [[CCC]], March 29, 2003
* [https://www.stmintz.com/ccc/index.php?id=306858 Another memory latency test] by [[Dieter Bürssner]], [[CCC]], July 17, 2003
* [https://www.stmintz.com/ccc/index.php?id=308392 Replacement shemes] by [[Sune Fischer]], [[CCC]], July 27, 2003
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/42c6f293450dba50/ Is it necessary to include empty fields in the hash key of a position?] by Frank Hablizel, [[Computer Chess Forums|rgcc]], December 25, 2003
'''2004'''
* [https://www.stmintz.com/ccc/index.php?id=339934 I need your opinion about this hash entry structure] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], January 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=354012 Fruit - Question for Fabien] by [[Dan Honeycutt]], [[CCC]], March 11, 2004 » [[Fruit]], [[Node Types]], [[Principal variation]], [[Principal Variation Search]]
* [https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004 » [[Transposition Table#Collisions|Transposition Table - Collisions]]
* [https://www.stmintz.com/ccc/index.php?id=378351 A move to search 2nd... Keep in the trans table?] by [[Eric Oldre]], [[CCC]], July 21, 2004
* [https://www.stmintz.com/ccc/index.php?id=379721 Transposition table replacement] by [[Eric Oldre]], [[CCC]], July 29, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1855 Side effects of transposition tables] by [[Alessandro Scotti]], [[Computer Chess Forums|Winboard Forum]], March 04, 2005
* [https://www.stmintz.com/ccc/index.php?id=432374 Hashing double bounds] by [[Rasjid Chan]], [[CCC]], June 20, 2005
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405 Mate scores in the hash table] by [[Eduardo Waghabi]], [[Computer Chess Forums|Winboard Forum]], September 02, 2005 » [[Score#MateScores|Mate Scores]]
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405#p17151 Re: Mate scores in the hash table] by [[Bruce Moreland]], [[Computer Chess Forums|Winboard Forum]], September 04, 2005
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405#p17152 Re: Mate scores in the hash table] by [[Josué Forte]], [[Computer Chess Forums|Winboard Forum]], September 04, 2005
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=3838 Hash table hit rate] by [[Stef Luijten]], [[Computer Chess Forums|Winboard Forum]], November 16, 2005
'''2007'''
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=131367 Transposition Tables] by Colin, [[CCC]], July 15, 2007
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=15505 fail high handling with tranposition tables] by [[Uri Blass]], [[CCC]], August 01, 2007
'''2008'''
* [http://www.talkchess.com/forum/viewtopic.php?t=18854 Problem with Transposition Table and Repitition-Draw] by [[Oliver Brausch]], [[CCC]], January 11, 2008 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=19867 Transposition Table and nps drop] by [[Mathieu Pagé]], [[CCC]], February 27, 2008 » [[Nodes per second]]
* [http://talkchess.com/forum/viewtopic.php?t=21343 Semi-Path Dependent Hashing: a semi-useless idea] by [[Zach Wegner]], [[CCC]], May 24, 2008 » [[Path-Dependency]]
* [http://www.talkchess.com/forum/viewtopic.php?t=22274 Is 64 bits enough as a hash length] by [[Mathieu Pagé]], [[CCC]], July 10, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=23562 31 bit hash values. How often will it fail?] by [[Carey Bloodworth|Carey]], [[CCC]], September 07, 2008 » [[Transposition Table#Collisions|Transposition Table - Collisions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=25599 Adaptative LMR and TT] by [[Fermin Serrano]], [[CCC]], December 23, 2008 » [[Late Move Reductions]]
'''2009'''
* [http://www.talkchess.com/forum/viewtopic.php?t=28119 transposition table details] by [[Don Dailey]], [[CCC]], May 26, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28652 Transposition Table] by [[Pablo Vazquez]], [[CCC]], June 26, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=285407 Cache pollution when reading/writing hash table] by [[Marco Costalba]], [[CCC]], August 09, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=305218 Transposition table pruning] by [[Luca Hemmerich]], [[CCC]], November 25, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=32396 Correcting Evaluation with the hash table] by [[Mark Lefler]], [[CCC]], February 05, 2010 » [[Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=32897 TT hit/miss rates] by [[Vlad Stamate]], [[CCC]], February 25, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33084 Zero window TT entry] by [[Vlad Stamate]], [[CCC]], March 05, 2010 » [[Null Window]]
* [http://www.talkchess.com/forum/viewtopic.php?t=33514 Null-move pruning and the hash table] by [[Robert Purves]], [[CCC]], March 28, 2010 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39481 TT behavior] by [[Karlo Bala Jr.]], [[CCC]], June 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=36099 working!] by [[Robert Hyatt]], [[CCC]], September 17, 2010 » [[Principal Variation#SeparateTT|Separate TT for the PV]]
* [http://www.talkchess.com/forum/viewtopic.php?t=36516 Is a querying the hash tables such a huge bottleneck?] by [[Oliver Uwira]], [[CCC]], October 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=37016 Puzzle with mate scores in TT] by [[Robert Purves]], [[CCC]], December 10, 2010 » [[Score#MateScores|Mate Scores]]
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38464 Transposition Table: addressing slots] by [[Michael Hoffmann]], [[CCC]], March 18, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38740 Transposition Table updates in Stockfish] by [[Onno Garms]], [[CCC]], April 12, 2011 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39289 Hashing the PV] by [[Stef Luijten]], [[CCC]], June 06, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39889 Dual Bound TT] by [[João Guerra]], [[CCC]], July 28, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40388 Repetitions/50 moves and TT] by [[Sergei Markoff]], [[CCC]], September 13, 2011 » [[Fifty-move Rule]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40450 Determining the age of TT buckets] by [[Julien Marcel]], [[CCC]], Sepember 18, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40849 Key collision handling] by [[Jonatan Pettersson]], [[CCC]], October 21, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41640 Mate score in TT] by [[Marco Costalba]], [[CCC]], December 28, 2011 » [[Score#MateScores|Mate Scores]]
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=41917 Stockfish hash implementation] by [[Jon Dart]], [[CCC]], January 10, 2012 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42833 cache alignment of tt] by [[Daniel Shawul]], [[CCC]], March 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43172 Hash table division] by [[Ed Schroder|Ed Schröder]], [[CCC]], April 05, 2012
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52394 hashtables] by [[Daniel Anulliero]], [[Computer Chess Forums|Winboard Forum]], May 22, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44666 TT avoid nullmove flag] by [[Matthew R. Brades]], [[CCC]], August 02, 2012 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46269 Transposition Table - Replacement and PV] by [[Cheney Nattress]], [[CCC]], December 04, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46346 Speaking of the hash table] by [[Ed Schroder|Ed Schröder]], [[CCC]], December 09, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=47373 Transposition table usage in quiescent search?] by [[Jerry Donald]], [[CCC]], March 01, 2013 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013 <ref>[[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=47773 The effect of larger hash size] by [[Jacob Børs Lind]], [[CCC]], April 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47872 Effect of the Hash Table size] by [[Kai Laskos]], [[CCC]], April 28, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48315 Hash cutoffs and analysis] by [[Harm Geert Muller]], [[CCC]], June 17, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48479 Hashing based on move lists] by [[Matthew R. Brades]], [[CCC]], June 30, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48735 transposition tables] by [[Folkert van Heusden]], [[CCC]], July 23, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49362 ep and castle rights hashing] by [[Natale Galioto]], [[CCC]], September 15, 2013 » [[Castling rights]], [[En passant]], [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50430 Hash tables: one bound or two bounds?] by [[Alberto Sanjuan]], [[CCC]], December 11, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=52169 LMR & TT interaction] by [[Natale Galioto]], [[CCC]], April 29, 2014 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=52226 transposition and multithreading question] by [[Marco Belli]], [[CCC]], May 04, 2014 » [[Parallel Search]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2703 transposition table implementation help] by lazyguy123, [[Computer Chess Forums|OpenChess Forum]], August 09, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53462 Transposition table chaining and replacement strategy] by [[Alex Ferguson]], [[CCC]], August 28, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53849 Speculative prefetch] by [[Peter Österlund]], [[CCC]], September 27, 2014 » [[Memory]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53859 Transposition Table Oddity] by [[Thomas Kolarik]], [[CCC]], September 28, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53965 Can someone explain what advantage there is to...] by Forrest Hoch, [[CCC]], October 06, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54063 Cache over-writing and PV's] by Forrest Hoch, [[CCC]], October 16, 2014 » [[Principal variation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54141 Mate score from the transposition table] by [[Evert Glebbeek]], [[CCC]], October 25, 2014 » [[Score#MateScores|Mate Scores]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54666 Two hash functions for distributed transposition table] by [[Daniel Shawul]], [[CCC]], December 16, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54755 Transposition table in Q-search] by [[Alex Ferguson]], [[CCC]], December 26, 2014 » [[Quiescence Search]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54941 Legality Check on TT move] by Jordan Bray, [[CCC]], January 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55501 (iteration+depth) TT replacement policy] by [[Aleks Peshkov]], [[CCC]], February 27, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55921 Idea #9228: Clearing stale transtable entries] by [[Steven Edwards]], [[CCC]], April 06, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55965 TTable questions] by [[Henk van den Belt]], [[CCC]], April 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56044 Fractional plies and transposition tables] by [[Alexandru Mosoi]], [[CCC]], April 18, 2015 » [[Depth#FractionalPlies|Depth - Fractional Plies]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57235&start=3 Re: Worst advice] by [[Alexandru Mosoi]], [[CCC]], August 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57255 most similar hashes of two positions] by [[Alexandru Mosoi]], [[CCC]], August 12, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57348 The cost of transposition table instrumentation] by [[Steven Edwards]], [[CCC]], August 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57603 Transposition table test positons] by [[Robert Pope]], [[CCC]], September 11, 2015 » [[Test-Positions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57924 Hash cache] by [[Harm Geert Muller]], [[CCC]], October 12, 2015
* [http://www.open-chess.org/viewtopic.php?f=5&t=2913 Perft and hash with legal move generator] by [[Izak Pretorius|Peterpan]], [[Computer Chess Forums|OpenChess Forum]], November 12, 2015 » [[Perft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58727 Transposition table utilizattion] by [[Shawn Chidester]], [[CCC]], December 29, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59047 Transposition Age Tutorial] by [[Dennis Sceviour]], [[CCC]], January 25, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2951 TT Mate scores] by rgoomes, [[Computer Chess Forums|OpenChess Forum]], February 10, 2016 » [[Score#MateScores|Mate Scores]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59334 Hashing question] by Kenneth Jones, [[CCC]], February 23, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2961 TT and Iterative Deepening] by kuket15, [[Computer Chess Forums|OpenChess Forum]], February 26, 2016 » [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59401 Transposition table replacement strategies] by [[Shawn Chidester]], [[CCC]], March 01, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59426 about hashtable] by [[Daniel Anulliero]], [[CCC]], March 04, 2016
* [http://talkchess.com/forum/viewtopic.php?t=59740 Hashing in Qsearch?] by [[Martin Fierz]], [[CCC]], April 03, 2016 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59856 Shifting alpha/beta on hash hit] by [[Martin Fierz]], [[CCC]], April 14, 2016 » [[Search Instability]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59949 What happens during a hash collision in say Stockfish ...] by Isaac Haïk Dunn, [[CCC]], April 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59960 Hashtable aging] by [[Martin Fierz]], [[CCC]], April 25, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60056 Transposition Table replacement schemes] by Andrew Grant, [[CCC]], May 05, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60122 lockless hashing] by Lucas Braesch, [[CCC]], May 10, 2016 » [[Shared Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60243 Suggestion for hash tables and analysis] by [[J. Wesley Cleveland]], May 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60264 Hashtable and 50 move rule draws] by [[Stan Arts]], [[CCC]], May 24, 2016 » [[Fifty-move Rule]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60589 Transposition Table - Updating entries] by [[Andrew Grant]], [[CCC]], June 24, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2991 Transposition Table Usage] by theturk1234, [[Computer Chess Forums|OpenChess Forum]], July 12, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2995 Aspiration window with TT question] by [[Sander Maassen vd Brink|sandermvdb]], [[Computer Chess Forums|OpenChess Forum]], August 01, 2016 » [[Aspiration Windows]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61015 Storing both alpha and beta scores in TT] by [[Thomas Dybdahl Ahle]], [[CCC]], August 02, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61051 Using side to move as a separate bit in hash key] by [[J. Wesley Cleveland]], [[CCC]], August 06, 2016 » [[Side to move]]
* [https://groups.google.com/forum/#!topic/fishcooking/Mh8SzJhxmHQ Question about TT] by stefano.c, [[Computer Chess Forums|FishCooking]], August 21, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61193 transposition table pseudocode] by [[Erin Dame]], [[CCC]], August 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61384 transposition tables and three-fold repetition] by [[Erin Dame]], [[CCC]], September 10, 2016 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61543 Transposition tables in Cray Blitz] by [[Erin Dame]], [[CCC]], September 26, 2016 <ref>[[David E. Welsh]], [[Boris Baczynskyj]] ('''1985'''). ''[http://www.amazon.com/Computer-Chess-II-David-Welsh/dp/0697099113 Computer Chess II]''. William C Brown Publications, ISBN-13: 978-0697099112</ref> » [[Cray Blitz]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61614 Hash table transformation] by [[Dann Corbit]], [[CCC]], October 05, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62391 Modify hash probing code to pvs] by Fernando Tenorio, [[CCC]], December 05, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62890 What is wrong with doing Nulls & ttcuts in a pv node ?] by [[Mahmoud Uthman]], [[CCC]], January 21, 2017 » [[Null Move Pruning]], [[Node Types#PV|PV-Nodes]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63693 Interesting hash-replacement scheme] by [[Harm Geert Muller]], [[CCC]], April 08, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63726 Problems with TT, sometimes makes blunder moves] by [[Tony Soares]], [[CCC]], April 12, 2017
* [http://www.open-chess.org/viewtopic.php?f=5&t=3106 TT Table replacement strategy] by kickstone, [[Computer Chess Forums|OpenChess Forum]], April 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64021 Hash Tables Deep Blue] by Gustavo Mallada, [[CCC]], May 18, 2017 » [[Deep Blue]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64274 Hash table] by [[Daniel José Queraltó]], [[CCC]], June 12, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64522 Improving hash replacing schema for analysis mode] by [[Daniel José Queraltó]], [[CCC]], July 05, 2017 » [[Transposition Table#ReplacementStrategies|Replacement Strategy]], [[Persistent Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64564 TT aging] by [[Marco Pampaloni]], [[CCC]], July 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64604 Equidistributed draft] by [[Alvaro Cardoso]], [[CCC]], July 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64606 2-level TT] by [[Rein Halbersma]], [[CCC]], July 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64688 cutechess-cli: not restarting an engine because of tt] by [[Folkert van Heusden]], [[CCC]], July 22, 2017 » [[Cutechess-cli]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65327 Size of Transposition Table Entry] by [[Jason Fernandez]], [[CCC]], September 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66135 Transposition table based pruning idea] by [[Jerry Donald]], [[CCC]], December 25, 2017 » [[Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66183 hashing in chess4j] by [[James Swafford]], [[CCC]], December 30, 2017 » [[chess4j]]
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66640 Marcel Duchamp endgame "splits" engines / hash phenomenon] by [[Kenneth Wingate Regan|Kenneth Regan]], [[CCC]], February 19, 2018 » [[Arts#Duchamp|Marcel Duchamp]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67049 Mate scores in TT (a new?... approach)] by Vince Sempronio, [[CCC]], April 09, 2018
* [http://www.talkchess.com/forum/viewtopic.php?t=67078 Yet another Mate scores in TT thread] by [[Andrew Grant]], [[CCC]], April 12, 2018 » [[Checkmate]], [[Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67102 Draw scores in TT] by [[Srdja Matovic]], [[CCC]], April 14, 2018 » [[Draw]], [[Score#DrawScore|Draw Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67131 Depth extensions and effect on transposition queries] by [[Kenneth Jones]], [[CCC]], April 16, 2018 » [[Extensions]], [[Check Extensions]]
=External Links=
* [http://web.archive.org/web/20070809015843/www.seanet.com/%7Ebrucemo/topics/hashing.htm The Main Transposition Table] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Transposition_table Transposition table from Wikipedia]
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbering from Wikipedia]
* [http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate Regan]]
* [http://www.jamesswafford.com/2017/12/30/hashing-in-chess4j/ Hashing in chess4j] by [[James Swafford]], December 30, 2017» [[chess4j]]
* [[Videos#TalWilkenfeld|Tal Wilkenfeld]] - [https://en.wikipedia.org/wiki/Transformation_%28Tal_Wilkenfeld_album%29 Table For One], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=yu6zUwDv-o4|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:The_Persistence_of_Memory.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/The_Persistence_of_Memory|
[[Arts#Dali|Salvador Dalí]], [https://en.wikipedia.org/wiki/The_Persistence_of_Memory The Persistence of Memory] 1931 ]]
A '''Transposition Table''',<br/>
first used in [[Richard Greenblatt|Greenblatt's]] program [[Mac Hack#HashTable|Mac Hack VI]] <ref>[[Richard Greenblatt]], [[Donald Eastlake]] and [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]</ref> <ref>[[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''') in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/259fbfd2b39b8ee4/80c64ba0f632fc31 Re: Berliner vs. Botvinnik Some interesting points], post 8 by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 06, 1996 » Transposition Table in [[Mac Hack]]</ref> , is a database that stores results of previously performed searches. It is a way to greatly reduce the search space of a [[Search Tree|chess tree]] with little negative impact. Chess programs, during their [[Brute-Force|brute-force]] search, encounter the same [[Chess Position|positions]] again and again, but from different sequences of [[Moves|moves]], which is called a [[Transposition|transposition]]. Transposition (and [[Refutation Table|refutation]]) tables are techniques derived from [[Dynamic Programming|dynamic programming]] <ref>[https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming Algorithms that use dynamic programming from Wikipedia]</ref> , a term coined by [[Richard E. Bellman]] in the 1950s, when programming meant planning, and dynamic programming was conceived to optimally plan multistage processes <ref>[[Mathematician#SDasgupta|Sanjoy Dasgupta]], [[Mathematician#CHPapadimitriou|Christos H. Papadimitriou]], [[Mathematician#UVVazirani|Umesh Vazirani]] ('''2006'''). ''[http://www.cs.berkeley.edu/%7Evazirani/algorithms.html Algorithms]''. [https://en.wikipedia.org/wiki/McGraw-Hill McGraw-Hill], ISBN: 978-0073523408, [http://www.amazon.com/gp/product/0073523402?ie=UTF8&tag=ebookdire-20&link_code=as3&camp=211189&creative=373489&creativeASIN=0073523402 amazon], Chapter 6, Dynamic programming</ref> .
=How it works=
When the search encounters a [[Transposition|transposition]], it is beneficial to 'remember' what was determined 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 large [[Hash Table|hash table]] storing information about positions previously searched, how deeply they were searched, and what we concluded about them. Even if the [[Depth|depth]] (draft) of the related transposition table entry is not big enough, or does not contain the right bound for a cutoff, a [[Best Move|best]] (or good enough) move from a previous search can improve [[Move Ordering|move ordering]], and save search time. This is especially true inside an [[Iterative Deepening|iterative deepening]] framework, where one gains valuable table hits from previous iterations.
==Hash functions==
[https://en.wikipedia.org/wiki/Hash_function Hash functions] convert chess positions into an almost unique, scalar signature, allowing fast index calculation as well as space saving verification of stored positions.
* [[Zobrist Hashing]]
* [[BCH Hashing]]
Both, the more common Zobrist hashing as well BCH hashing use fast hash functions, to provide hash keys or signatures as a kind of [https://en.wikipedia.org/wiki/G%C3%B6del_number Gödel number] of chess positions, today typically [[Quad Word|64-bit]] wide. They are [[Incremental Updates|updated incrementally]] during [[Make Move|make]] and [[Unmake Move|unmake move]] by either own-inverse [[General Setwise Operations#ExclusiveOr|exclusive 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. Therefor to calculate the address or index requires signature [https://en.wikipedia.org/wiki/Modulo_operator modulo] number of entries, for power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly.
<span id="Collisions"></span>
=Collisions=
The [https://en.wikipedia.org/wiki/Surjection surjective] mapping from chess positions to a signature and an even more denser index range implies '''collisions''', different positions share 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, reflects the likelihood of collisions:
{| class="wikitable"
|-
! Cardinalities of positions and signatures
! #
|-
| Upper bound for the number of reachable [[Chess Position|chess positions]] <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>
| style="text-align:right;" | 1e46
|-
| Different [[Quad Word|64 bit]] keys
| style="text-align:right;" | 1.84e19
|-
| Some number of distinct nodes searched per game,<br/>assuming 100 moves times 1e8 nodes per move
| style="text-align:right;" | 1e10
|-
| Different [[Double Word|32 bit]] keys
| style="text-align:right;" | 4.29e9
|-
| Some arbitrary table size in number of entries
| style="text-align:right;" | 1e8
|}
<span id="IndexCollisions"></span>
==Index Collisions==
Index collisions or type-2 errors <ref>[[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) in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b9de346eb1e8300/ Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996</ref> , 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. Specially with 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 index, or even less.
<span id="KeyCollisions"></span>
==Key Collisions==
Key collisions or type-1 errors are inherent in using signatures with far less bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012</ref> . When storing only a partial key, the chance of a collision greatly increases. To accept only hits where [[Hash Move|stored moves]] are [[Pseudo-Legal Move|pseudo-legal]] decreases the chance of type-1 errors. On his computer chess page <ref>[http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate Regan]]</ref>, [[Kenneth Wingate Regan|Ken Regan]] broached on chess engine bugs, anomalies and hash collisions, and mentions a [[Shredder|Shredder 9.1]] game where a key collision might have caused a strange move <ref>[http://www.chessgames.com/perl/chessgame?gid=1352348 Pablo Lafuente vs Shredder (Computer) (2005)] from [http://www.chessgames.com/index.html chessgames.com]</ref> <ref>[http://www.chessbase.com/newsdetail.asp?newsid=2525 Current tournaments – Sanjin, Biel, Argentina, Israel], [[ChessBase|ChessBase News]], July 21, 2005</ref> .
<span id="bits"></span>
==Bits Required==
During the [[WCCC 1989]] Workshop [[WCCC 1989#Workshop|New Directions in Game-Tree Search]], [[James Gillogly]], author of [[Tech]], discussed transposition table collisions <ref>[[James Gillogly]] ('''1989'''). ''Transposition Table Collisions''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]</ref> . He produced the following table using the [https://en.wikipedia.org/wiki/Birthday_problem Birthday 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.
{| class="wikitable"
|-
! colspan="2" | Number of Positions:
! 10<span style="font-size: 80%; vertical-align: super;">5</span>
! 10<span style="font-size: 80%; vertical-align: super;">6</span>
! 10<span style="font-size: 80%; vertical-align: super;">7</span>
! 10<span style="font-size: 80%; vertical-align: super;">8</span>
! 10<span style="font-size: 80%; vertical-align: super;">9</span>
! 10<span style="font-size: 80%; vertical-align: super;">10</span>
|-
! rowspan="4" | Collision<br/>probability:
| style="text-align:left;" | .01
| style="text-align:right;" | 39
| style="text-align:right;" | 46
| style="text-align:right;" | 53
| style="text-align:right;" | 59
| style="text-align:right;" | 66
| style="text-align:right;" | 73
|-
| style="text-align:left;" | .001
| style="text-align:right;" | 43
| style="text-align:right;" | 49
| style="text-align:right;" | 56
| style="text-align:right;" | 63
| style="text-align:right;" | 69
| style="text-align:right;" | 76
|-
| style="text-align:left;" | .0001
| style="text-align:right;" | 46
| style="text-align:right;" | 53
| style="text-align:right;" | 59
| style="text-align:right;" | 66
| style="text-align:right;" | 73
| style="text-align:right;" | 79
|-
| style="text-align:left;" | .00001
| style="text-align:right;" | 49
| style="text-align:right;" | 56
| style="text-align:right;" | 63
| style="text-align:right;" | 69
| style="text-align:right;" | 76
| style="text-align:right;" | 83
|}
During the discussion, [[David Slate]] and [[Ken Thompson]] pointed out that the Birthday Paradox is not applicable 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 <ref>[[James Gillogly]] ('''1989'''). ''New Directions in Game-Tree Search - First Workshop Session''. [[ICGA Journal#12_2|ICCA Journal, Vol. 12, No. 2]]</ref>. The dangers of transposition table collisions were further studied by [[Robert Hyatt]] and [[Anthony Cozzie]] as published in their 2005 paper ''Hash Collisions Effect'' <ref>[[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]</ref>. They gave an 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.
<span id="Entry"></span>
=What Information is Stored=
Typically, the following information is stored as determined by the [[Search|search]] <ref>[[Dennis Breuker]], [[Jos Uiterwijk]], and [[Jaap van den Herik]] ('''1997'''). ''Information in Transposition Tables''. [[Advances in Computer Chess 8]]</ref> :
* [[Zobrist Hashing|Zobrist-]] or [[BCH Hashing|BCH-key]], to look whether the position is the right one while probing
* [[Best Move|Best-]] or [[Refutation Move|Refutation move]]
* [[Depth]] (draft)
* [[Score]], ''either with'' [[Integrated Bounds and Values|Integrated Bound and Value]] ''or otherwise with''
* [[Node Types|Type of Node]] <ref>[[MTD(f)]]- and some [[Principal Variation Search|PVS]]-implementations store distinct [[Upper Bound|upper]] and [[Upper Bound|lower bound]] scores, rather than one score with flags</ref>
: [[Node Types#PV|PV-Node]], Score is [[Exact Score|Exact]]
: [[Node Types#ALL|All-Node]], Score is [[Upper Bound]]
: [[Node Types#CUT|Cut-Node]], Score is [[Lower Bound]]
* [[Transposition Table#Aging|Age]] is used to determine when to overwrite entries from searching previous positions during the [[Chess Game|game of chess]]
=Table Entry Types=
In an [[Alpha-Beta|alpha-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 the [[Node Types|type of node]], often referred to as [[Exact Score|exact]], [[Lower Bound|lower]]- or [[Upper Bound|upper bound]].
<span id="ReplacementStrategies"></span>
=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 <ref>[[Dennis Breuker]], [[Jos Uiterwijk]] and [[Jaap van den Herik]] ('''1994'''). ''Replacement Schemes for Transposition Tables''. [[ICGA Journal#17_4|ICCA Journal, Vol. 17, No. 4]]</ref> . 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.
<span id="AlwaysReplace"></span>
==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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47373&start=28 Re: Transposition table usage in quiescent search?] by [[Robert Hyatt]], [[CCC]], March 06, 2013</ref> .
==Priority by Searched Nodes Count==
This replacement strategy uses number of nodes searched spent to obtain an entry, as replacement priority.
==Priority by Move Ordering Position==
This replacement strategy uses position of entry move in [[Move Ordering|move ordering]] list as replacement priority. The main idea is that if the best move was not considered as good cut-off candidate by move-ordering algorithm, storing it in TT should provide better help for the search.
<span id="DepthPreferred"></span>
==Depth-Preferred==
This replacement strategy puts all emphasis on the first consideration. The only criteria in deciding whether to overwrite an entry is whether the new entry has a higher depth than the old entry.
<span id="TwoTier"></span>
==Two-tier System==
This strategy, devised by [[Ken Thompson]] and [[Joe Condon]] <ref>[[Joe Condon]] and [[Ken Thompson]] ('''1983'''). ''BELLE Chess Hardware''. [[Advances in Computer Chess 3]]</ref> , uses two tables, side by side. For each table slot, there is a depth-preferred and an always-replace entry <ref>[[Dennis Breuker]], [[Jos Uiterwijk]] and [[Jaap van den Herik]] ('''1996'''). ''Replacement Schemes and Two-Level Tables''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref> .
<span id="Bucket"></span>
==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 cacheline). 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 <ref>[[Don Beal]] and [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]</ref> .
<span id="Aging"></span>
==Aging==
Aging considers searches of different chess positions during game play. While early implementations and programs relying on [[Piece-Square Tables#Preprocessing|root pre-processing]] to guide search and [[Evaluation|evaluation]] were obligated to clear the hash table between root positions, most todays programs do not, to 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 current [[Halfmove Clock|halfmove clock]] as age, likely modulo some power two constant, depending on how many bits are used to store it inside an entry <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59047 Transposition Age Tutorial] by [[Dennis Sceviour]], [[CCC]], January 25, 2016</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59960 Hashtable aging] by [[Martin Fierz]], [[CCC]], April 25, 2016</ref>.
=TT and Parallel Search=
A [[Shared Hash Table|global transposition table]], shared by multiple [[Thread|threads]] or [[Process|processes]] is essential for effective [[Parallel Search|parallel search]] algorithms on modern multi core cpus, and might be accessed [[Shared Hash Table#Lockless|lock-less]], as proposed by [[Robert Hyatt]] and [[Tim Mann]] <ref>[[Robert Hyatt]] and [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]</ref> .
=Further Hash Tables=
Besides storing the best move and scores of the search trees, further [[Hash Table|hash tables]] are often used to cache other features.
* [[Evaluation Hash Table]]
* [[Material Hash Table]]
* [[Pawn Hash Table]]
* [[Principal Variation#SeparateTT|Separate TT for the PV]]
=Maximizing Transpositions=
* [[Enhanced Transposition Cutoff]]
* [[Repetitions]]
=See also=
* [[CPW-Engine_transposition]]
* [[Fifty-move Rule]]
* [[Graph History Interaction]]
* [[Population Count#HammingDistance|Hamming Distance]] <ref>[https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001</ref>
* [[Hash Move]]
* [[Hash Table]]
* [[Memory#HugePages|Huge Pages]]
* [[Integrated Bounds and Values]]
* [[Interior Node Recognizer]]
* [[Iterative Deepening]]
* [[Lasker-Reichhelm Position]] (Fine #70)
* [[Move Ordering]]
* [[Path-Dependency]]
* [[Persistent Hash Table]]
* [[Refutation Table]]
* [[Repetitions]]
* [[Search Instability]]
* [[Shared Hash Table]]
* [[Transposition]]
* [[Search Statistics#TTStatistics|TT Statistics]]
=Publications=
==1967 ...==
* [[Richard Greenblatt]], [[Donald Eastlake]], [https://en.wikipedia.org/wiki/Steve_Crocker Stephen D. Crocker] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') in [[Computer Chess Compendium]], [http://archive.computerhistory.org/projects/chess/related_materials/text/2-4.Greenblatt_Chess_Program/The_Greenblatt_Chess_Program.Greenblatt_Eastlake_Crocker.1967.Fall_Joint_Computer_Conference.062303060.sm.pdf pdf] from [[The Computer History Museum]] or as [http://dspace.mit.edu/handle/1721.1/6176 pdf or ps] from [http://libraries.mit.edu/dspace-mit/ DSpace] at [[Massachusetts Institute of Technology|MIT]]
==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''') in [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2.]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf 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''') in [[Computer Chess Compendium]] » [[Chess (Program)|Chess]]
==1980 ...==
* [[Harry Nelson]] ('''1985'''). ''Hash Tables in Cray Blitz''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[James Gillogly]] ('''1989'''). ''Transposition Table Collisions''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
* [[Harry Nelson]] ('''1989'''). ''Some Observations about Hash Tables in Cray Blitz''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]]
==1990 ...==
* [[Dennis Breuker]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1996'''). ''Replacement Schemes and Two-Level Tables''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]].
* [[Don Beal]] and [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
* [[Dennis Breuker]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''1997'''). ''Information in Transposition Tables''. [[Advances in Computer Chess 8]]
* [[Dennis Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/ Memory versus Search in Games]''. Ph.D. Thesis, [[Maastricht University|Universiteit Maastricht]], The Netherlands. ISBN 90-9012006-8.
==2000 ...==
* [[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf] » [[Parallel Search]] <ref>[https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013</ref>
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Viljem Žumer]] ('''2005'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1491153 The Representation of Chess Game]''. Proceedings of the 27th International Conference on Information Technology Interfaces
* [[Joel Veness]], [[Alan Blair]] ('''2007'''). ''Effective Use of Transposition Tables in Stochastic Game Tree Search''. IEEE Symposium on Computational Intelligence and Games, [http://jveness.info/publications/cig2007%20-%20effective%20use%20of%20transposition%20tables%20in%20stochastic%20game%20tree%20search.pdf pdf]
* [[Rune Rasmussen]], [[Frédéric Maire]], [[Ross Hayward]] ('''2007'''). ''[http://eprints.qut.edu.au/12527/ A Template Matching Table for Speeding-Up Game-Tree Searches for Hex]''. 20th Australian Joint Conference on Artificial Intelligence » [[Hex]]
==2010 ...==
* [[Timothy Furtak]], [[Michael Buro]] ('''2011'''). ''Using Payoff-Similarity to Speed Up Search''. [[Conferences#IJCAI2011|IJCAI 2011]], [http://ijcai.org/papers11/Papers/IJCAI11-097.pdf pdf] » [https://en.wikipedia.org/wiki/Skat_%28card_game%29 Skat]
* [[Robert Hyatt]] ('''2014'''). ''A Solution to Short PVs Caused by Exact Hash Matches''. [[ICGA Journal#37_3|ICGA Journal, Vol. 37, No. 3]] » [[Principal Variation#SeparateTT|Separate TT for the PV]]
=Forum Posts=
==1990 ...==
* [http://groups.google.de/group/rec.games.chess/browse_thread/thread/87d436c2293f9138 Hash tables - Clash!!! What happens next?] by [[Valavan Manohararajah]], [[Computer Chess Forums|rec.games.chess]], March 14, 1994
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/a9d5fb3e489196ed/68f9f93c938f3349 Hash table question] by [[John Stanback]], [[Computer Chess Forums|rec.games.chess]], March 23, 1994
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Taxgk4l-S90/ggkiWEVavYsJ hash mem in win-chess progs] by [[Adrian Millett|Pc Sol]], [[Computer Chess Forums|rgcc]], September 28, 1995 » [[Windows]]
'''1996'''
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/34826d5ec57f0923 Transposition table] by Matthew Bengtson, [[Computer Chess Forums|rgcc]], January 25, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/b9de346eb1e8300/ Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/p8GbiiLjp0o/81vZ3czsthIJ Alpha-Beta window in transposition tables?] by Marty Bochane, [[Computer Chess Forums|rgcc]], October 25, 1996 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55889&start=8 Re. Fail low after fail high] by [[Marcel van Kervinck]], [[CCC]], April 05, 2015 » [[Fail-Low ]], [[Fail-High]]</ref>
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/259fbfd2b39b8ee4/80c64ba0f632fc31 Re: Berliner vs. Botvinnik Some interesting points], post 8 by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 06, 1996 » Transposition Table in [[Mac Hack]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/77ec7b3a94555fb4/d8019f5c3716cd1a hash table fail high/fail low problem] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], November 26, 1996
'''1997'''
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d2c20a63f75f2d4b Hash functions for use with a transition table] by [[Tim Foden]], [[Computer Chess Forums|rgcc]], March 5, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/9b240379394bc968 Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997 » [[BCH Hashing]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/1d601e208c97c395 Handling of repetition (draw) in transposition table] by Bjarke Dahl Ebert, [[Computer Chess Forums|rgcc]], June 9, 1997 » [[Repetitions]]
* [https://www.stmintz.com/ccc/index.php?id=10317 double hash tables] by [[Chris Whittington]], [[CCC]], October 01, 1997
'''1998'''
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=14226 Hash tables and data-cache, some programmer stuff...] by [[Ed Schroder|Ed Schröder]], [[CCC]], January 17, 1998
* [https://www.stmintz.com/ccc/index.php?id=19515 Hash Table Size Versus Performance] by Steven Juchnowski, [[CCC]], May 30, 1998
* [https://www.stmintz.com/ccc/index.php?id=21654 Selective deepening and Hashtables] by [[Werner Inmann]], [[CCC]], June 30, 1998
* [https://www.stmintz.com/ccc/index.php?id=58 Using too-shallow mate scores from the hash table] by [[David Eppstein]], [[CCC]], July 05, 1998 » [[Score#MateScores|Mate Scores]]
: [https://www.stmintz.com/ccc/index.php?id=21814 Re: Using too-shallow mate scores from the hash table] by [[David Eppstein]], [[CCC]], July 06, 1998
: [https://www.stmintz.com/ccc/index.php?id=21838 Re: Using too-shallow mate scores from the hash table] by [[Don Dailey]], [[CCC]], July 07, 1998
* [https://www.stmintz.com/ccc/index.php?id=22816 draw by repetition and hash tables] by [[Werner Inmann]], [[CCC]], July 24, 1998
'''1999'''
* [https://www.stmintz.com/ccc/index.php?id=43613 Hash collisions and a little maths] by [[Rémi Coulom]], [[CCC]], February 18, 1999
* [https://www.stmintz.com/ccc/index.php?id=43990 Hash Collisions] by [[KarinsDad]], [[CCC]], February 21, 1999
* [https://www.stmintz.com/ccc/index.php?id=72221 Problem with draws by rep and hash table] by [[James Robertson]], [[CCC]], October 07, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=93686 Can we use hash table at root?] by Tim, [[CCC]], January 31, 2000 » [[Root]]
* [https://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/ab55c5d57a3a1fd1 Re: Atomic write of 64 bits] by [[Frans Morsch]], [https://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], September 25, 2000 » [[MMX]], [[Parallel Search]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/e70ef78a6a17f225 hashing function] by [[Vladimir Medvedev|Vladimir R. Medvedev]], [[Computer Chess Forums|rgcc]], October 17, 2000
* [https://www.stmintz.com/ccc/index.php?id=143022 Hash table efficiency] by [[Miguel A. Ballicora]], [[CCC]], December 05, 2000 » [[Gaviota]], [[Search Statistics]]
* [https://www.stmintz.com/ccc/index.php?id=143234 Why not store both a lower and an upper bound in a hashtable?] by [[Leen Ammeraal]], [[CCC]], December 06, 2000
'''2001'''
* [https://www.stmintz.com/ccc/index.php?id=175221 A fast hash -- assuming you are not planning to do incremental updates] by [[Dann Corbit]], [[CCC]], June 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=182927 "Don't trust draw score" <=Is it true?] by [[Teerapong Tovirat]], [[CCC]], August 08, 2001 » [[Repetitions]], [[Path-Dependency]]
* [https://www.stmintz.com/ccc/index.php?id=200366 About random numbers and hashing] by [[Severi Salminen]], [[CCC]], December 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001
* [https://www.stmintz.com/ccc/index.php?id=203516 When to RecordHash()?] by [[Sune Fischer]], [[CCC]], December 25, 2001
'''2002'''
* [https://www.stmintz.com/ccc/index.php?id=214125 Non power of two hash table sizes] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], February 18, 2002
* [https://www.stmintz.com/ccc/index.php?id=214562 Detecting Draws using a Small Hash Table?] by [[Steve Maughan]], [[CCC]], February 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=252097 hash entry replacement schemes] by [[Scott Farrell]], [[CCC]], September 14, 2002
* [https://www.stmintz.com/ccc/index.php?id=252598 hash numbers requested: authors please read] by [[James Swafford]], [[CCC]], September 17, 2002
'''2003'''
* [https://www.stmintz.com/ccc/index.php?id=291039 How important is a big hash table? Measurements...] by [[Tom Kerrigan]], [[CCC]], March 29, 2003
* [https://www.stmintz.com/ccc/index.php?id=306858 Another memory latency test] by [[Dieter Bürssner]], [[CCC]], July 17, 2003
* [https://www.stmintz.com/ccc/index.php?id=308392 Replacement shemes] by [[Sune Fischer]], [[CCC]], July 27, 2003
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/42c6f293450dba50/ Is it necessary to include empty fields in the hash key of a position?] by Frank Hablizel, [[Computer Chess Forums|rgcc]], December 25, 2003
'''2004'''
* [https://www.stmintz.com/ccc/index.php?id=339934 I need your opinion about this hash entry structure] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], January 02, 2004
* [https://www.stmintz.com/ccc/index.php?id=354012 Fruit - Question for Fabien] by [[Dan Honeycutt]], [[CCC]], March 11, 2004 » [[Fruit]], [[Node Types]], [[Principal variation]], [[Principal Variation Search]]
* [https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004 » [[Transposition Table#Collisions|Transposition Table - Collisions]]
* [https://www.stmintz.com/ccc/index.php?id=378351 A move to search 2nd... Keep in the trans table?] by [[Eric Oldre]], [[CCC]], July 21, 2004
* [https://www.stmintz.com/ccc/index.php?id=379721 Transposition table replacement] by [[Eric Oldre]], [[CCC]], July 29, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1855 Side effects of transposition tables] by [[Alessandro Scotti]], [[Computer Chess Forums|Winboard Forum]], March 04, 2005
* [https://www.stmintz.com/ccc/index.php?id=432374 Hashing double bounds] by [[Rasjid Chan]], [[CCC]], June 20, 2005
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405 Mate scores in the hash table] by [[Eduardo Waghabi]], [[Computer Chess Forums|Winboard Forum]], September 02, 2005 » [[Score#MateScores|Mate Scores]]
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405#p17151 Re: Mate scores in the hash table] by [[Bruce Moreland]], [[Computer Chess Forums|Winboard Forum]], September 04, 2005
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3405#p17152 Re: Mate scores in the hash table] by [[Josué Forte]], [[Computer Chess Forums|Winboard Forum]], September 04, 2005
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=3838 Hash table hit rate] by [[Stef Luijten]], [[Computer Chess Forums|Winboard Forum]], November 16, 2005
'''2007'''
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=131367 Transposition Tables] by Colin, [[CCC]], July 15, 2007
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=15505 fail high handling with tranposition tables] by [[Uri Blass]], [[CCC]], August 01, 2007
'''2008'''
* [http://www.talkchess.com/forum/viewtopic.php?t=18854 Problem with Transposition Table and Repitition-Draw] by [[Oliver Brausch]], [[CCC]], January 11, 2008 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=19867 Transposition Table and nps drop] by [[Mathieu Pagé]], [[CCC]], February 27, 2008 » [[Nodes per second]]
* [http://talkchess.com/forum/viewtopic.php?t=21343 Semi-Path Dependent Hashing: a semi-useless idea] by [[Zach Wegner]], [[CCC]], May 24, 2008 » [[Path-Dependency]]
* [http://www.talkchess.com/forum/viewtopic.php?t=22274 Is 64 bits enough as a hash length] by [[Mathieu Pagé]], [[CCC]], July 10, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=23562 31 bit hash values. How often will it fail?] by [[Carey Bloodworth|Carey]], [[CCC]], September 07, 2008 » [[Transposition Table#Collisions|Transposition Table - Collisions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=25599 Adaptative LMR and TT] by [[Fermin Serrano]], [[CCC]], December 23, 2008 » [[Late Move Reductions]]
'''2009'''
* [http://www.talkchess.com/forum/viewtopic.php?t=28119 transposition table details] by [[Don Dailey]], [[CCC]], May 26, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28652 Transposition Table] by [[Pablo Vazquez]], [[CCC]], June 26, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=285407 Cache pollution when reading/writing hash table] by [[Marco Costalba]], [[CCC]], August 09, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=305218 Transposition table pruning] by [[Luca Hemmerich]], [[CCC]], November 25, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=32396 Correcting Evaluation with the hash table] by [[Mark Lefler]], [[CCC]], February 05, 2010 » [[Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=32897 TT hit/miss rates] by [[Vlad Stamate]], [[CCC]], February 25, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33084 Zero window TT entry] by [[Vlad Stamate]], [[CCC]], March 05, 2010 » [[Null Window]]
* [http://www.talkchess.com/forum/viewtopic.php?t=33514 Null-move pruning and the hash table] by [[Robert Purves]], [[CCC]], March 28, 2010 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39481 TT behavior] by [[Karlo Bala Jr.]], [[CCC]], June 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=36099 working!] by [[Robert Hyatt]], [[CCC]], September 17, 2010 » [[Principal Variation#SeparateTT|Separate TT for the PV]]
* [http://www.talkchess.com/forum/viewtopic.php?t=36516 Is a querying the hash tables such a huge bottleneck?] by [[Oliver Uwira]], [[CCC]], October 28, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=37016 Puzzle with mate scores in TT] by [[Robert Purves]], [[CCC]], December 10, 2010 » [[Score#MateScores|Mate Scores]]
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38464 Transposition Table: addressing slots] by [[Michael Hoffmann]], [[CCC]], March 18, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38740 Transposition Table updates in Stockfish] by [[Onno Garms]], [[CCC]], April 12, 2011 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39289 Hashing the PV] by [[Stef Luijten]], [[CCC]], June 06, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39889 Dual Bound TT] by [[João Guerra]], [[CCC]], July 28, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40388 Repetitions/50 moves and TT] by [[Sergei Markoff]], [[CCC]], September 13, 2011 » [[Fifty-move Rule]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40450 Determining the age of TT buckets] by [[Julien Marcel]], [[CCC]], Sepember 18, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40849 Key collision handling] by [[Jonatan Pettersson]], [[CCC]], October 21, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41640 Mate score in TT] by [[Marco Costalba]], [[CCC]], December 28, 2011 » [[Score#MateScores|Mate Scores]]
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=41917 Stockfish hash implementation] by [[Jon Dart]], [[CCC]], January 10, 2012 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=42833 cache alignment of tt] by [[Daniel Shawul]], [[CCC]], March 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43172 Hash table division] by [[Ed Schroder|Ed Schröder]], [[CCC]], April 05, 2012
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52394 hashtables] by [[Daniel Anulliero]], [[Computer Chess Forums|Winboard Forum]], May 22, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44666 TT avoid nullmove flag] by [[Matthew R. Brades]], [[CCC]], August 02, 2012 » [[Null Move Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46269 Transposition Table - Replacement and PV] by [[Cheney Nattress]], [[CCC]], December 04, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46346 Speaking of the hash table] by [[Ed Schroder|Ed Schröder]], [[CCC]], December 09, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=47373 Transposition table usage in quiescent search?] by [[Jerry Donald]], [[CCC]], March 01, 2013 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013 <ref>[[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=47773 The effect of larger hash size] by [[Jacob Børs Lind]], [[CCC]], April 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47872 Effect of the Hash Table size] by [[Kai Laskos]], [[CCC]], April 28, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48315 Hash cutoffs and analysis] by [[Harm Geert Muller]], [[CCC]], June 17, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48479 Hashing based on move lists] by [[Matthew R. Brades]], [[CCC]], June 30, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48735 transposition tables] by [[Folkert van Heusden]], [[CCC]], July 23, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49362 ep and castle rights hashing] by [[Natale Galioto]], [[CCC]], September 15, 2013 » [[Castling rights]], [[En passant]], [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50430 Hash tables: one bound or two bounds?] by [[Alberto Sanjuan]], [[CCC]], December 11, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=52169 LMR & TT interaction] by [[Natale Galioto]], [[CCC]], April 29, 2014 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=52226 transposition and multithreading question] by [[Marco Belli]], [[CCC]], May 04, 2014 » [[Parallel Search]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2703 transposition table implementation help] by lazyguy123, [[Computer Chess Forums|OpenChess Forum]], August 09, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53462 Transposition table chaining and replacement strategy] by [[Alex Ferguson]], [[CCC]], August 28, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53849 Speculative prefetch] by [[Peter Österlund]], [[CCC]], September 27, 2014 » [[Memory]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53859 Transposition Table Oddity] by [[Thomas Kolarik]], [[CCC]], September 28, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53965 Can someone explain what advantage there is to...] by Forrest Hoch, [[CCC]], October 06, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54063 Cache over-writing and PV's] by Forrest Hoch, [[CCC]], October 16, 2014 » [[Principal variation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54141 Mate score from the transposition table] by [[Evert Glebbeek]], [[CCC]], October 25, 2014 » [[Score#MateScores|Mate Scores]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54666 Two hash functions for distributed transposition table] by [[Daniel Shawul]], [[CCC]], December 16, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54755 Transposition table in Q-search] by [[Alex Ferguson]], [[CCC]], December 26, 2014 » [[Quiescence Search]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54941 Legality Check on TT move] by Jordan Bray, [[CCC]], January 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55501 (iteration+depth) TT replacement policy] by [[Aleks Peshkov]], [[CCC]], February 27, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55921 Idea #9228: Clearing stale transtable entries] by [[Steven Edwards]], [[CCC]], April 06, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55965 TTable questions] by [[Henk van den Belt]], [[CCC]], April 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56044 Fractional plies and transposition tables] by [[Alexandru Mosoi]], [[CCC]], April 18, 2015 » [[Depth#FractionalPlies|Depth - Fractional Plies]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57235&start=3 Re: Worst advice] by [[Alexandru Mosoi]], [[CCC]], August 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57255 most similar hashes of two positions] by [[Alexandru Mosoi]], [[CCC]], August 12, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57348 The cost of transposition table instrumentation] by [[Steven Edwards]], [[CCC]], August 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57603 Transposition table test positons] by [[Robert Pope]], [[CCC]], September 11, 2015 » [[Test-Positions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57924 Hash cache] by [[Harm Geert Muller]], [[CCC]], October 12, 2015
* [http://www.open-chess.org/viewtopic.php?f=5&t=2913 Perft and hash with legal move generator] by [[Izak Pretorius|Peterpan]], [[Computer Chess Forums|OpenChess Forum]], November 12, 2015 » [[Perft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58727 Transposition table utilizattion] by [[Shawn Chidester]], [[CCC]], December 29, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59047 Transposition Age Tutorial] by [[Dennis Sceviour]], [[CCC]], January 25, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2951 TT Mate scores] by rgoomes, [[Computer Chess Forums|OpenChess Forum]], February 10, 2016 » [[Score#MateScores|Mate Scores]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59334 Hashing question] by Kenneth Jones, [[CCC]], February 23, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2961 TT and Iterative Deepening] by kuket15, [[Computer Chess Forums|OpenChess Forum]], February 26, 2016 » [[Iterative Deepening]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59401 Transposition table replacement strategies] by [[Shawn Chidester]], [[CCC]], March 01, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59426 about hashtable] by [[Daniel Anulliero]], [[CCC]], March 04, 2016
* [http://talkchess.com/forum/viewtopic.php?t=59740 Hashing in Qsearch?] by [[Martin Fierz]], [[CCC]], April 03, 2016 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59856 Shifting alpha/beta on hash hit] by [[Martin Fierz]], [[CCC]], April 14, 2016 » [[Search Instability]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59949 What happens during a hash collision in say Stockfish ...] by Isaac Haïk Dunn, [[CCC]], April 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59960 Hashtable aging] by [[Martin Fierz]], [[CCC]], April 25, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60056 Transposition Table replacement schemes] by Andrew Grant, [[CCC]], May 05, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60122 lockless hashing] by Lucas Braesch, [[CCC]], May 10, 2016 » [[Shared Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60243 Suggestion for hash tables and analysis] by [[J. Wesley Cleveland]], May 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60264 Hashtable and 50 move rule draws] by [[Stan Arts]], [[CCC]], May 24, 2016 » [[Fifty-move Rule]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60589 Transposition Table - Updating entries] by [[Andrew Grant]], [[CCC]], June 24, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2991 Transposition Table Usage] by theturk1234, [[Computer Chess Forums|OpenChess Forum]], July 12, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=2995 Aspiration window with TT question] by [[Sander Maassen vd Brink|sandermvdb]], [[Computer Chess Forums|OpenChess Forum]], August 01, 2016 » [[Aspiration Windows]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61015 Storing both alpha and beta scores in TT] by [[Thomas Dybdahl Ahle]], [[CCC]], August 02, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61051 Using side to move as a separate bit in hash key] by [[J. Wesley Cleveland]], [[CCC]], August 06, 2016 » [[Side to move]]
* [https://groups.google.com/forum/#!topic/fishcooking/Mh8SzJhxmHQ Question about TT] by stefano.c, [[Computer Chess Forums|FishCooking]], August 21, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61193 transposition table pseudocode] by [[Erin Dame]], [[CCC]], August 22, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61384 transposition tables and three-fold repetition] by [[Erin Dame]], [[CCC]], September 10, 2016 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61543 Transposition tables in Cray Blitz] by [[Erin Dame]], [[CCC]], September 26, 2016 <ref>[[David E. Welsh]], [[Boris Baczynskyj]] ('''1985'''). ''[http://www.amazon.com/Computer-Chess-II-David-Welsh/dp/0697099113 Computer Chess II]''. William C Brown Publications, ISBN-13: 978-0697099112</ref> » [[Cray Blitz]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61614 Hash table transformation] by [[Dann Corbit]], [[CCC]], October 05, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62391 Modify hash probing code to pvs] by Fernando Tenorio, [[CCC]], December 05, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62890 What is wrong with doing Nulls & ttcuts in a pv node ?] by [[Mahmoud Uthman]], [[CCC]], January 21, 2017 » [[Null Move Pruning]], [[Node Types#PV|PV-Nodes]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63693 Interesting hash-replacement scheme] by [[Harm Geert Muller]], [[CCC]], April 08, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63726 Problems with TT, sometimes makes blunder moves] by [[Tony Soares]], [[CCC]], April 12, 2017
* [http://www.open-chess.org/viewtopic.php?f=5&t=3106 TT Table replacement strategy] by kickstone, [[Computer Chess Forums|OpenChess Forum]], April 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64021 Hash Tables Deep Blue] by Gustavo Mallada, [[CCC]], May 18, 2017 » [[Deep Blue]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64274 Hash table] by [[Daniel José Queraltó]], [[CCC]], June 12, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64522 Improving hash replacing schema for analysis mode] by [[Daniel José Queraltó]], [[CCC]], July 05, 2017 » [[Transposition Table#ReplacementStrategies|Replacement Strategy]], [[Persistent Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64564 TT aging] by [[Marco Pampaloni]], [[CCC]], July 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64604 Equidistributed draft] by [[Alvaro Cardoso]], [[CCC]], July 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64606 2-level TT] by [[Rein Halbersma]], [[CCC]], July 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64688 cutechess-cli: not restarting an engine because of tt] by [[Folkert van Heusden]], [[CCC]], July 22, 2017 » [[Cutechess-cli]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65327 Size of Transposition Table Entry] by [[Jason Fernandez]], [[CCC]], September 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66135 Transposition table based pruning idea] by [[Jerry Donald]], [[CCC]], December 25, 2017 » [[Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66183 hashing in chess4j] by [[James Swafford]], [[CCC]], December 30, 2017 » [[chess4j]]
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66640 Marcel Duchamp endgame "splits" engines / hash phenomenon] by [[Kenneth Wingate Regan|Kenneth Regan]], [[CCC]], February 19, 2018 » [[Arts#Duchamp|Marcel Duchamp]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67049 Mate scores in TT (a new?... approach)] by Vince Sempronio, [[CCC]], April 09, 2018
* [http://www.talkchess.com/forum/viewtopic.php?t=67078 Yet another Mate scores in TT thread] by [[Andrew Grant]], [[CCC]], April 12, 2018 » [[Checkmate]], [[Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67102 Draw scores in TT] by [[Srdja Matovic]], [[CCC]], April 14, 2018 » [[Draw]], [[Score#DrawScore|Draw Score]]
* [http://www.talkchess.com/forum/viewtopic.php?t=67131 Depth extensions and effect on transposition queries] by [[Kenneth Jones]], [[CCC]], April 16, 2018 » [[Extensions]], [[Check Extensions]]
=External Links=
* [http://web.archive.org/web/20070809015843/www.seanet.com/%7Ebrucemo/topics/hashing.htm The Main Transposition Table] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
* [https://en.wikipedia.org/wiki/Transposition_table Transposition table from Wikipedia]
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbering from Wikipedia]
* [http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate Regan]]
* [http://www.jamesswafford.com/2017/12/30/hashing-in-chess4j/ Hashing in chess4j] by [[James Swafford]], December 30, 2017» [[chess4j]]
* [[Videos#TalWilkenfeld|Tal Wilkenfeld]] - [https://en.wikipedia.org/wiki/Transformation_%28Tal_Wilkenfeld_album%29 Table For One], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=yu6zUwDv-o4|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
