Difference between revisions of "Transposition Table"
GerdIsenberg (talk | contribs) |
(→Using the Transposition Table: add a note) |
||
(52 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
[[FILE:The_Persistence_of_Memory.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/The_Persistence_of_Memory| | [[FILE:The_Persistence_of_Memory.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/The_Persistence_of_Memory| | ||
− | [[ | + | [[:Category:Salvador Dalí|Salvador Dalí]], [https://en.wikipedia.org/wiki/The_Persistence_of_Memory The Persistence of Memory] 1931 ]] |
A '''Transposition Table''',<br/> | A '''Transposition Table''',<br/> | ||
− | first used in [[Richard Greenblatt|Greenblatt's]] program [[Mac Hack#HashTable|Mac Hack VI]] <ref>[[Richard Greenblatt]], [[Donald Eastlake]] | + | first used in [[Richard Greenblatt|Greenblatt's]] program [[Mac Hack#HashTable|Mac Hack VI]] <ref>[[Richard Greenblatt]], [[Donald Eastlake]], [[Stephen D. Crocker]] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') 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= | =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. | + | When the search encounters a [[Transposition|transposition]], it is beneficial to 'remember' what was determined the last time the position was examined, rather than redoing the entire search again. For this reason, chess programs have a transposition table, which is a 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== | ==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. | + | [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]] | * [[Zobrist Hashing]] | ||
* [[BCH Hashing]] | * [[BCH Hashing]] | ||
Line 18: | Line 18: | ||
==Address Calculation== | ==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. | + | The index is not based on the entire hash key because this is usually a 64-bit number, and with current hardware limitations, no hash table can be large enough to accommodate it. Therefore calculating the address or index requires a signature [https://en.wikipedia.org/wiki/Modulo_operator modulo] a number of entries, for the power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly. |
+ | |||
+ | <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]], [[Jaap van den Herik]] ('''1997'''). ''Information in Transposition Tables''. [[Advances in Computer Chess 8]]</ref> : | ||
+ | * [[Zobrist Hashing|Zobrist-]] or [[BCH Hashing|BCH-key]], to see 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="Usage"> | ||
+ | =Using the Transposition Table= | ||
+ | |||
+ | Transposition Tables are an integral part of an engine's search. It is used in both search heuristics and move ordering. | ||
+ | |||
+ | ==Transposition Table Cutoffs== | ||
+ | Depth, value, and bound information can be used to produce cutoffs and reduce redudant computation. In more advanced engines transposition table cutoffs are not performed on [[Node Types#PV-Nodes | PV-Nodes]]. | ||
+ | |||
+ | A cutoff can be performed when the depth of entry is greater (or equal) to the depth of the current node and one of the following criteria is satisfied: | ||
+ | |||
+ | * The entry type is [[Exact Score | EXACT]] | ||
+ | * The entry type is [[Lower Bound | LOWERBOUND]] and greater than or equal to beta | ||
+ | * The entry type is [[Upper Bound | UPPERBOUND]] and less than alpha | ||
+ | |||
+ | ==Hash Move== | ||
+ | |||
+ | ''Main Article: [[Hash Move]]'' | ||
+ | |||
+ | Best move/Refutation move information from the transposition table is the most important part of move ordering. They are first in order and can be searched before other moves are generated. When the hash move fails high, generating other moves is not necessary. In [[Stockfish]], 75% of cutoffs produced in a position with hash moves are caused by the hash move. | ||
+ | |||
+ | ==Singular Extensions== | ||
+ | |||
+ | [[Singular_Extensions#Restricted_SE|Restricted SE]] is only attempted on a position where a TT entry exist, they entry has a valid TT move, the entry has a high enough depth, and the entry has exact or lowerbound bounds. | ||
+ | |||
<span id="Collisions"></span> | <span id="Collisions"></span> | ||
+ | |||
=Collisions= | =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). | + | 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 the same entries, for two different reasons, hopefully, rare ambiguous keys (type-1 errors), or regularly ambiguous indices (type-2 errors). |
==Cardinalities== | ==Cardinalities== | ||
− | The typical cardinalities of positions and signatures inside the search | + | The typical cardinalities of positions and signatures inside the search reflect the likelihood of collisions: |
{| class="wikitable" | {| class="wikitable" | ||
Line 43: | Line 85: | ||
| style="text-align:right;" | 4.29e9 | | style="text-align:right;" | 4.29e9 | ||
|- | |- | ||
− | | Some arbitrary table size in number of entries | + | | Some arbitrary table size in the number of entries |
| style="text-align:right;" | 1e8 | | style="text-align:right;" | 1e8 | ||
|} | |} | ||
<span id="IndexCollisions"></span> | <span id="IndexCollisions"></span> | ||
==Index Collisions== | ==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. | + | 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. Especially with the power of two entry tables, many programmers choose to trade-off space for accuracy and only store that part of the hash key not already considered as an index, or even less. |
<span id="KeyCollisions"></span> | <span id="KeyCollisions"></span> | ||
==Key Collisions== | ==Key Collisions== | ||
− | Key collisions or type-1 errors are inherent in using signatures with far | + | Key collisions or type-1 errors are inherent in using signatures with far fewer bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature <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 W. Regan]]</ref>, [[Kenneth W. 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> | <span id="bits"></span> | ||
==Bits Required== | ==Bits Required== | ||
Line 99: | Line 141: | ||
|} | |} | ||
− | During the discussion, [[David Slate]] and [[Ken Thompson]] pointed out that the Birthday Paradox | + | During the discussion, [[David Slate]] and [[Ken Thompson]] pointed out that the Birthday Paradox does not apply to most programs, since the hash table will fill up and not all previous positions will be in the table; thus these figures must be regarded as an upper bound on the number of bits required for safety <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 a surprising answer to the question “Is it really worth all the effort to absolutely minimize signature collisions?”, and concluded that 64-bit signatures are more than sufficient. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<span id="ReplacementStrategies"></span> | <span id="ReplacementStrategies"></span> | ||
=Replacement Strategies= | =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]] | + | 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]], [[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 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. | * 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. | ||
Line 123: | Line 151: | ||
<span id="AlwaysReplace"></span> | <span id="AlwaysReplace"></span> | ||
==Always Replace== | ==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> . | + | 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== | ==Priority by Searched Nodes Count== | ||
− | This replacement strategy uses number of nodes searched spent to obtain an entry, as replacement priority. | + | This replacement strategy uses the number of nodes searched spent to obtain an entry, as replacement priority. |
==Priority by Move Ordering Position== | ==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. | + | This replacement strategy uses the 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 a good cut-off candidate by the move-ordering algorithm, storing it in TT should provide better help for the search. |
<span id="DepthPreferred"></span> | <span id="DepthPreferred"></span> | ||
==Depth-Preferred== | ==Depth-Preferred== | ||
− | This replacement strategy puts all emphasis on the first consideration. The only | + | This replacement strategy puts all emphasis on the first consideration. The only criterion in deciding whether to overwrite an entry is whether the new entry has a higher depth than the old entry. |
<span id="TwoTier"></span> | <span id="TwoTier"></span> | ||
==Two-tier System== | ==Two-tier System== | ||
− | This strategy, devised by [[Ken Thompson]] and [[Joe Condon]] <ref>[[Joe Condon]] | + | This strategy, devised by [[Ken Thompson]] and [[Joe Condon]] <ref>[[Joe Condon]], [[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]], [[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> | <span id="Bucket"></span> | ||
==Bucket Systems== | ==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 | + | This family of strategies is similar to the two-tier system, but any number of tiers (known as "buckets") can be used (typically the number is based on the size of a cache line). The difference is that the buckets are not specific to one consideration, but rather the new entry overwrites the entry in the bucket with the lowest depth <ref>[[Don Beal]], [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]</ref> . |
<span id="Aging"></span> | <span id="Aging"></span> | ||
==Aging== | ==Aging== | ||
− | Aging considers searches | + | Aging considers searches for different chess positions during gameplay. 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, 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= | =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 | + | 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= | =Further Hash Tables= | ||
Line 181: | Line 209: | ||
=Publications= | =Publications= | ||
==1967 ...== | ==1967 ...== | ||
− | * [[Richard Greenblatt]], [[Donald Eastlake]], [ | + | * [[Richard Greenblatt]], [[Donald Eastlake]], [[Stephen D. Crocker]] ('''1967'''). ''The Greenblatt Chess Program''. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted ('''1988''') 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 ...== | ==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] | * [[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] | ||
Line 192: | Line 220: | ||
==1990 ...== | ==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]]. | * [[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]] | + | * [[Don Beal]], [[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]], [[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. | * [[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. | ||
Line 219: | Line 247: | ||
* [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 | * [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''' | '''1997''' | ||
− | * [ | + | * [https://groups.google.com/d/msg/rec.games.chess.computer/0sIKY_dfLUs/Qw9J1ECWeBoJ Hash functions for use with a transition table] by [[Tim Foden]], [[Computer Chess Forums|rgcc]], March 5, 1997 » [[Transposition Table]] |
− | : [ | + | : [https://groups.google.com/d/msg/rec.games.chess.computer/0sIKY_dfLUs/aMlLOXkDJJsJ 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]] | * [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 | * [https://www.stmintz.com/ccc/index.php?id=10317 double hash tables] by [[Chris Whittington]], [[CCC]], October 01, 1997 | ||
+ | * [https://www.stmintz.com/ccc/index.php?id=10471 Hash collisions (was Re: Let's analyze move 36)] by [[Daniel Homan]], [[CCC]], October 08, 1997 » [[#Collisions|Collisions]] | ||
+ | * [https://groups.google.com/d/msg/rec.games.chess.computer/S70uojQGHNU/vU-xEHCfFl0J Using values from transition tables] by [[Tim Foden]], [[Computer Chess Forums|rgcc]], October 13, 1997 | ||
'''1998''' | '''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=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998 | ||
Line 234: | Line 264: | ||
* [https://www.stmintz.com/ccc/index.php?id=22816 draw by repetition and hash tables] by [[Werner Inmann]], [[CCC]], July 24, 1998 | * [https://www.stmintz.com/ccc/index.php?id=22816 draw by repetition and hash tables] by [[Werner Inmann]], [[CCC]], July 24, 1998 | ||
'''1999''' | '''1999''' | ||
+ | * [https://www.stmintz.com/ccc/index.php?id=41612 Hash Tables - Should one store EP, Castling rights etc?] by [[Steve Maughan]], [[CCC]], January 30, 1999 » [[Castling Rights]], [[En passant]] | ||
* [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=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=43990 Hash Collisions] by [[KarinsDad]], [[CCC]], February 21, 1999 | ||
Line 256: | Line 287: | ||
'''2003''' | '''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=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 | + | * [https://www.stmintz.com/ccc/index.php?id=306858 Another memory latency test] by [[Dieter Bürßner]], [[CCC]], July 17, 2003 |
* [https://www.stmintz.com/ccc/index.php?id=308392 Replacement shemes] by [[Sune Fischer]], [[CCC]], July 27, 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 | * [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''' | '''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=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=344036 Question about details of hashing (olithink)] by [[Michel Langeveld]], [[CCC]], January 22, 2004 » [[OliThink]] | ||
* [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=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=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004 » [[Transposition Table#Collisions|Transposition Table - Collisions]] | ||
Line 292: | Line 324: | ||
* [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=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=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/forum3/viewtopic.php?f=7&t=34606 Crafty Transpostion Table Question] by [[Eric Stock]], [[CCC]], May 30, 2010 » [[Crafty]], [[Shared Hash Table#Lockless|Lockless Hashing]] |
+ | * [http://www.talkchess.com/forum/viewtopic.php?t=39481 TT behavior] by [[Karlo Balla|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=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=36516 Is a querying the hash tables such a huge bottleneck?] by [[Oliver Uwira]], [[CCC]], October 28, 2010 | ||
Line 307: | Line 340: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=41640 Mate score in TT] by [[Marco Costalba]], [[CCC]], December 28, 2011 » [[Score#MateScores|Mate Scores]] | * [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''' | '''2012''' | ||
+ | * [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52138 Question on TT] by [[Giuseppe Cannella]], [[Computer Chess Forums|Winboard Forum]], January 06, 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=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=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.talkchess.com/forum/viewtopic.php?t=43172 Hash table division] by [[Ed Schroder|Ed Schröder]], [[CCC]], April 05, 2012 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=43769 TT question?] by [[Fermin Serrano]], [[CCC]], May 19, 2012 » [[Quiescence Search]] | ||
* [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.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=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012 | ||
Line 330: | Line 365: | ||
* [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.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=53462 Transposition table chaining and replacement strategy] by [[Alex Ferguson]], [[CCC]], August 28, 2014 | ||
+ | * [https://groups.google.com/d/msg/fishcooking/6nNXAQQAXOE/FXs2chqDargJ Using the Transposition Table for long searches] by Theodr Elwurtz, [[Computer Chess Forums|FishCooking]], September 22, 2014 » [[Stockfish]] | ||
* [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=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=53859 Transposition Table Oddity] by [[Thomas Kolarik]], [[CCC]], September 28, 2014 | ||
Line 346: | Line 382: | ||
* [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=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=57348 The cost of transposition table instrumentation] by [[Steven Edwards]], [[CCC]], August 23, 2015 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=57634 atomic TT] by lucasart, [[CCC]], September 13, 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=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.talkchess.com/forum/viewtopic.php?t=57924 Hash cache] by [[Harm Geert Muller]], [[CCC]], October 12, 2015 | ||
Line 384: | Line 421: | ||
* [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=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=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 » [[ | + | * [http://www.talkchess.com/forum/viewtopic.php?t=64522 Improving hash replacing schema for analysis mode] by [[Daniel José Queraltó]], [[CCC]], July 05, 2017 » [[#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=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=64604 Equidistributed draft] by [[Alvaro Cardoso]], [[CCC]], July 14, 2017 | ||
Line 390: | Line 427: | ||
* [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=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=65327 Size of Transposition Table Entry] by [[Jason Fernandez]], [[CCC]], September 29, 2017 | ||
+ | * [http://www.talkchess.com/forum/viewtopic.php?t=65526 Transposition table and Fine#70] by [[Vincent Tang]], [[CCC]], October 23, 2017 » [[Lasker-Reichhelm Position]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=65903 TT in Qsearch] by [[Laurie Tunnicliffe]], [[CCC]], December 05, 2017 » [[Quiescence Search]] | ||
* [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=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]] | * [http://www.talkchess.com/forum/viewtopic.php?t=66183 hashing in chess4j] by [[James Swafford]], [[CCC]], December 30, 2017 » [[chess4j]] | ||
'''2018''' | '''2018''' | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=66640 Marcel Duchamp endgame "splits" engines / hash phenomenon] by [[Kenneth | + | * [http://www.talkchess.com/forum/viewtopic.php?t=66640 Marcel Duchamp endgame "splits" engines / hash phenomenon] by [[Kenneth W. Regan|Kenneth Regan]], [[CCC]], February 19, 2018 » [[:Category:Marcel Duchamp|Marcel Duchamp]] |
+ | * [http://www.open-chess.org/viewtopic.php?f=5&t=3170 Do You Track Hash Table Efficiency?] by OneMoreTime, [[Computer Chess Forums|OpenChess Forum]], April 07, 2018 | ||
* [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=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=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=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]] | * [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]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67387 Not detected collisions in tt probing] by [[Andreas Matthies]], [[CCC]], May 09, 2018 » [[#Collisions|Collisions]] | ||
+ | '''2019''' | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69629 Playing transposition table moves in the Quiescence search] by [[Andrew Grant]], [[CCC]], January 17, 2019 » [[Quiescence Search]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70586 Prefetch and Threading] by [[Dennis Sceviour]], [[CCC]], April 25, 2019 » [[Memory]], [[Thread]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67599 Debugging a transposition table] by [[Vincent Tang]], [[CCC]], May 29, 2018 » [[Debugging]], [[Lasker-Reichhelm Position]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70931 Hash collision?] by [[Tom King]], [[CCC]], June 05, 2019 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71994 Looking for TT policy advice] by [[Vivien Clauzon]], [[CCC]], October 04, 2019 » [[#ReplacementStrategies|Replacement Strategy]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72462 Probing the transposition table at depth 0] by [[Gonzalo Arro]], [[CCC]], November 29, 2019 | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72932 hash collisions] by [[Jon Dart]], [[CCC]], January 28, 2020 » [[#KeyCollisions|Key Collisions]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72964 Dense board representation as hash code] by koedem, [[CCC]], February 01, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73110 Zobrist key independence] by [[Harm Geert Muller]], [[CCC]], February 17, 2020 » [[Zobrist Hashing]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73126 SIMD methods in TT probing and replacement] by [[Harm Geert Muller]], [[CCC]], February 20, 2020 » [[SIMD and SWAR Techniques]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73202 Measuring Hash Collisions (once again)] by [[Ed Schroder|Ed Schröder]], [[CCC]], February 27, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73232 Hash size, hash fullness, strength] by [[Vivien Clauzon]], [[CCC]], February 29, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73493 Where to enter/read position into hash table in perft?] by [[Marcel Vanthoor]], [[CCC]], March 28, 2020 » [[Perft]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73516 Hash entry/bucket memory usage optimization] by [[Marcel Vanthoor]], [[CCC]], March 30, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74081 asymmetric evaluation and TT] by [[Vivien Clauzon]], [[CCC]], June 02, 2020 » [[Asymmetric Evaluation]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74411 Correct way to store and extract mate scores] by Ian Mitchell, [[CCC]], July 08, 2020 » [[Checkmate]], [[Score]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75549 Principal Variation Search vs. Transposition Table] by [[Marcel Vanthoor]], [[CCC]], October 26, 2020 » [[Principal Variation]], [[Principal Variation Search]] | ||
+ | '''2021''' | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76499 Transposition table replacement scheme] by [[Niels Abildskov]], [[CCC]], February 05, 2021 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76508 Best practices for transposition tables] by Brian Adkins, [[CCC]], February 06, 2021 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76575 TT: key collisions] by Brian Adkins, [[CCC]], February 13, 2021 » [[#KeyCollisions|Key Collisions]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76887 Hash move ordering vs. Hash cuts: savings in number of nodes visited] by [[Marcel Vanthoor]], [[CCC]], March 16, 2021 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77054 PERFT transposition table funny?!] by [[Martin Bryant]], [[CCC]], April 10, 2021 » [[Perft]], [[Memory]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77286 For or against the transposition table probe in quiet search?] by [[Eugene Kotlov]], [[CCC]], May 11, 2021 » [[Quiescence Search]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77470 Saving moves into the TT] by [[Marcel Vanthoor]], [[CCC]], June 11, 2021 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77504 Hash value composition] by [[Yves De Billoëz]], [[CCC]], June 17, 2021 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77569 When to clear the Transposition table?] by [[Thomas Jahn]], [[CCC]], June 28, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78474 About move ordering and TT hitrate] by Giovanni Maria Manduca, [[CCC]], October 22, 2021 » [[Move Ordering]] | ||
+ | '''2022''' | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79647 Transposition table based cutoffs] by Michal Witanowski, [[CCC]], April 05, 2022 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79720 Consensus for TT: Buckets with Entries, or Entries with Buckets?] by [[Marcel Vanthoor]], [[CCC]], April 19, 2022 | ||
+ | |||
+ | '''2023''' | ||
+ | * [https://talkchess.com/viewtopic.php?t=82494 Checking TT move for legality] by Aaron Li, [[CCC]], August 20, 2023 | ||
+ | |||
+ | '''2024''' | ||
+ | * [https://talkchess.com/viewtopic.php?t=83222 Help with transposition table] by E Boatwright, [[CCC]], January 21, 2024 | ||
+ | * [https://talkchess.com/viewtopic.php?t=83549 adding TT reduces NPS by allot] by Ravael Jansen, [[CCC]], March 29, 2024 | ||
+ | * [https://talkchess.com/viewtopic.php?t=83695 Hybride replacemment strategy worse than always-replace] by mathmoi, [[CCC]], April 25, 2024 | ||
=External Links= | =External Links= | ||
Line 404: | Line 486: | ||
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing 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] | * [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 | + | * [http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth W. Regan]] |
* [http://www.jamesswafford.com/2017/12/30/hashing-in-chess4j/ Hashing in chess4j] by [[James Swafford]], December 30, 2017» [[chess4j]] | * [http://www.jamesswafford.com/2017/12/30/hashing-in-chess4j/ Hashing in chess4j] by [[James Swafford]], December 30, 2017» [[chess4j]] | ||
− | * [[ | + | * [[:Category:Tal Wilkenfeld|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}} | : {{#evu:https://www.youtube.com/watch?v=yu6zUwDv-o4|alignment=left|valignment=top}} | ||
Line 412: | Line 494: | ||
<references /> | <references /> | ||
'''[[Search|Up one Level]]''' | '''[[Search|Up one Level]]''' | ||
+ | [[Category:Salvador Dalí]] | ||
+ | [[Category:Marcel Duchamp]] | ||
+ | [[Category:Tal Wilkenfeld]] |
Latest revision as of 07:49, 27 July 2024
Home * Search * Transposition Table
A Transposition Table,
first used in Greenblatt's program Mac Hack VI [1] [2] [3], is a database that stores results of previously performed searches. It is a way to greatly reduce the search space of a chess tree with little negative impact. Chess programs, during their brute-force search, encounter the same positions again and again, but from different sequences of moves, which is called a transposition. Transposition (and refutation) tables are techniques derived from dynamic programming [4], a term coined by Richard E. Bellman in the 1950s, when programming meant planning and dynamic programming was conceived to optimally plan multistage processes [5] .
Contents
How it works
When the search encounters a transposition, it is beneficial to 'remember' what was determined the last time the position was examined, rather than redoing the entire search again. For this reason, chess programs have a transposition table, which is a large hash table storing information about positions previously searched, how deeply they were searched, and what we concluded about them. Even if the depth (draft) of the related transposition table entry is not big enough, or does not contain the right bound for a cutoff, a best (or good enough) move from a previous search can improve move ordering, and save search time. This is especially true inside an iterative deepening framework, where one gains valuable table hits from previous iterations.
Hash functions
Hash functions convert chess positions into an almost unique, scalar signature, allowing fast index calculation as well as space-saving verification of stored positions.
Both, the more common Zobrist hashing as well BCH hashing use fast hash functions, to provide hash keys or signatures as a kind of Gödel number of chess positions, today typically 64-bit wide. They are updated incrementally during make and unmake move by either own-inverse 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. Therefore calculating the address or index requires a signature modulo a number of entries, for the power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly.
What Information is Stored
Typically, the following information is stored as determined by the search [6] :
- Zobrist- or BCH-key, to see whether the position is the right one while probing
- Best- or Refutation move
- Depth (draft)
- Score, either with Integrated Bound and Value or otherwise with
- Type of Node [7]
- PV-Node, Score is Exact
- All-Node, Score is Upper Bound
- Cut-Node, Score is Lower Bound
- Age is used to determine when to overwrite entries from searching previous positions during the game of chess
Table Entry Types
In an 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 type of node, often referred to as exact, lower- or upper bound.
Using the Transposition Table
Transposition Tables are an integral part of an engine's search. It is used in both search heuristics and move ordering.
Transposition Table Cutoffs
Depth, value, and bound information can be used to produce cutoffs and reduce redudant computation. In more advanced engines transposition table cutoffs are not performed on PV-Nodes.
A cutoff can be performed when the depth of entry is greater (or equal) to the depth of the current node and one of the following criteria is satisfied:
- The entry type is EXACT
- The entry type is LOWERBOUND and greater than or equal to beta
- The entry type is UPPERBOUND and less than alpha
Hash Move
Main Article: Hash Move
Best move/Refutation move information from the transposition table is the most important part of move ordering. They are first in order and can be searched before other moves are generated. When the hash move fails high, generating other moves is not necessary. In Stockfish, 75% of cutoffs produced in a position with hash moves are caused by the hash move.
Singular Extensions
Restricted SE is only attempted on a position where a TT entry exist, they entry has a valid TT move, the entry has a high enough depth, and the entry has exact or lowerbound bounds.
Collisions
The surjective mapping from chess positions to a signature and an, even more, denser index range implies collisions, different positions share the same entries, for two different reasons, hopefully, rare ambiguous keys (type-1 errors), or regularly ambiguous indices (type-2 errors).
Cardinalities
The typical cardinalities of positions and signatures inside the search reflect the likelihood of collisions:
Cardinalities of positions and signatures | # |
---|---|
Upper bound for the number of reachable chess positions [8] | 1e46 |
Different 64 bit keys | 1.84e19 |
Some number of distinct nodes searched per game, assuming 100 moves times 1e8 nodes per move |
1e10 |
Different 32 bit keys | 4.29e9 |
Some arbitrary table size in the number of entries | 1e8 |
Index Collisions
Index collisions or type-2 errors [9] [10], where different hash keys index same entries, happen regularly. They require detection, realized by storing the signature as part of the hash entry, to check whether a stored entry matches the position while probing. Especially with the power of two entry tables, many programmers choose to trade-off space for accuracy and only store that part of the hash key not already considered as an index, or even less.
Key Collisions
Key collisions or type-1 errors are inherent in using signatures with far fewer bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature [11] [12]. When storing only a partial key, the chance of a collision greatly increases. To accept only hits where stored moves are pseudo-legal decreases the chance of type-1 errors. On his computer chess page [13], Ken Regan broached on chess engine bugs, anomalies and hash collisions, and mentions a Shredder 9.1 game where a key collision might have caused a strange move [14] [15].
Bits Required
During the WCCC 1989 Workshop New Directions in Game-Tree Search, James Gillogly, author of Tech, discussed transposition table collisions [16] . He produced the following table using the 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.
Number of Positions: | 105 | 106 | 107 | 108 | 109 | 1010 | |
---|---|---|---|---|---|---|---|
Collision probability: |
.01 | 39 | 46 | 53 | 59 | 66 | 73 |
.001 | 43 | 49 | 56 | 63 | 69 | 76 | |
.0001 | 46 | 53 | 59 | 66 | 73 | 79 | |
.00001 | 49 | 56 | 63 | 69 | 76 | 83 |
During the discussion, David Slate and Ken Thompson pointed out that the Birthday Paradox does not apply to most programs, since the hash table will fill up and not all previous positions will be in the table; thus these figures must be regarded as an upper bound on the number of bits required for safety [17]. The dangers of transposition table collisions were further studied by Robert Hyatt and Anthony Cozzie as published in their 2005 paper Hash Collisions Effect [18]. They gave a surprising answer to the question “Is it really worth all the effort to absolutely minimize signature collisions?”, and concluded that 64-bit signatures are more than sufficient.
Replacement Strategies
Because there are a limited number of entries in a transposition table, and because in modern chess programs, they can fill up very quickly, it is necessary to have a scheme by which the program can decide which entries would be most valuable to keep, i.e. a replacement scheme [19] . Replacement schemes are used to solve an index collision when a program attempts to store a position in a table slot that already has a different entry in it. There are two opposing considerations to replacement schemes:
- Entries that were searched to a high depth save more work per table hit than those searched to a low depth.
- Entries that are closer to the leaves of the tree are more likely to be searched multiple times, making the table hits of them higher. Also, entries that were searched recently are more likely to be searched again.
- Most well-performing replacement strategies use a mix of these considerations.
Always Replace
This replacement strategy is very simple, placing all emphasis on the second consideration. Any old entries are replaced immediately when a new entry is stored [20].
Priority by Searched Nodes Count
This replacement strategy uses the number of nodes searched spent to obtain an entry, as replacement priority.
Priority by Move Ordering Position
This replacement strategy uses the position of entry move in move ordering list as replacement priority. The main idea is that if the best move was not considered as a good cut-off candidate by the move-ordering algorithm, storing it in TT should provide better help for the search.
Depth-Preferred
This replacement strategy puts all emphasis on the first consideration. The only criterion in deciding whether to overwrite an entry is whether the new entry has a higher depth than the old entry.
Two-tier System
This strategy, devised by Ken Thompson and Joe Condon [21] , uses two tables, side by side. For each table slot, there is a depth-preferred and an always-replace entry [22] .
Bucket Systems
This family of strategies is similar to the two-tier system, but any number of tiers (known as "buckets") can be used (typically the number is based on the size of a cache line). The difference is that the buckets are not specific to one consideration, but rather the new entry overwrites the entry in the bucket with the lowest depth [23] .
Aging
Aging considers searches for different chess positions during gameplay. While early implementations and programs relying on root pre-processing to guide search and evaluation were obligated to clear the hash table between root positions, most todays programs do not, profit from entries of previous searches. Nevertheless, to avoid persistence of old entries which may no longer occur from the current root, aging is used to likely replace those entries by new ones, even if their draft and flags would otherwise protect them. To implement aging, one often stores and compares the current halfmove clock as age, likely modulo some power two constant, depending on how many bits are used to store it inside an entry [24] [25].
TT and Parallel Search
A global transposition table, shared by multiple threads or processes is essential for effective parallel search algorithms on modern multi-core CPUs, and might be accessed lock-less, as proposed by Robert Hyatt and Tim Mann [26] .
Further Hash Tables
Besides storing the best move and scores of the search trees, further hash tables are often used to cache other features.
Maximizing Transpositions
See also
- CPW-Engine_transposition
- Fifty-move Rule
- Graph History Interaction
- Hamming Distance [27]
- Hash Move
- Hash Table
- 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
- TT Statistics
Publications
1967 ...
- Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted (1988) in Computer Chess Compendium, pdf from The Computer History Museum or as pdf or ps from DSpace at 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 ICCA Journal, Vol. 13, No. 2., pdf
- David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine (ed. Peter W. Frey), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted (1988) in Computer Chess Compendium » Chess
1980 ...
- Harry Nelson (1985). Hash Tables in Cray Blitz. ICCA Journal, Vol. 8, No. 1
- Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1
- James Gillogly (1989). Transposition Table Collisions. Workshop on New Directions in Game-Tree Search
- Harry Nelson (1989). Some Observations about Hash Tables in Cray Blitz. Workshop on New Directions in Game-Tree Search
1990 ...
- Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1996). Replacement Schemes and Two-Level Tables. ICCA Journal, Vol. 19, No. 3.
- Don Beal, Martin C. Smith (1996). Multiple Probes of Transposition Tables. 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). Memory versus Search in Games. Ph.D. Thesis, 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. pdf » Parallel Search [28] [29]
- Robert Hyatt, Tim Mann (2002). A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1
- Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 3
- Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). 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, pdf
- Rune Rasmussen, Frédéric Maire, Ross Hayward (2007). 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. IJCAI 2011, pdf » Skat
- Robert Hyatt (2014). A Solution to Short PVs Caused by Exact Hash Matches. ICGA Journal, Vol. 37, No. 3 » Separate TT for the PV
Forum Posts
1990 ...
- Hash tables - Clash!!! What happens next? by Valavan Manohararajah, rec.games.chess, March 14, 1994
- Hash table question by John Stanback, rec.games.chess, March 23, 1994
1995 ...
- hash mem in win-chess progs by Pc Sol, rgcc, September 28, 1995 » Windows
1996
- Transposition table by Matthew Bengtson, rgcc, January 25, 1996
- Collision probability by Dennis Breuker, rgcc, April 15, 1996
- Alpha-Beta window in transposition tables? by Marty Bochane, rgcc, October 25, 1996 [30]
- Re: Berliner vs. Botvinnik Some interesting points, post 8 by Bradley C. Kuszmaul, rgcc, November 06, 1996 » Transposition Table in Mac Hack
- hash table fail high/fail low problem by Robert Hyatt, rgcc, November 26, 1996
1997
- Hash functions for use with a transition table by Tim Foden, rgcc, March 5, 1997 » Transposition Table
- Re: Hash functions for use with a transition table by Ronald de Man, rgcc, March 7, 1997 » BCH Hashing
- Handling of repetition (draw) in transposition table by Bjarke Dahl Ebert, rgcc, June 9, 1997 » Repetitions
- double hash tables by Chris Whittington, CCC, October 01, 1997
- Hash collisions (was Re: Let's analyze move 36) by Daniel Homan, CCC, October 08, 1997 » Collisions
- Using values from transition tables by Tim Foden, rgcc, October 13, 1997
1998
- Fast hash algorithm by John Scalo, CCC, January 08, 1998
- Fast hash key method - Revisited! by John Scalo, CCC, January 14, 1998
- Hash tables and data-cache, some programmer stuff... by Ed Schröder, CCC, January 17, 1998
- Hash Table Size Versus Performance by Steven Juchnowski, CCC, May 30, 1998
- Selective deepening and Hashtables by Werner Inmann, CCC, June 30, 1998
- Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 05, 1998 » Mate Scores
- Re: Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 06, 1998
- Re: Using too-shallow mate scores from the hash table by Don Dailey, CCC, July 07, 1998
- draw by repetition and hash tables by Werner Inmann, CCC, July 24, 1998
1999
- Hash Tables - Should one store EP, Castling rights etc? by Steve Maughan, CCC, January 30, 1999 » Castling Rights, En passant
- Hash collisions and a little maths by Rémi Coulom, CCC, February 18, 1999
- Hash Collisions by KarinsDad, CCC, February 21, 1999
- Problem with draws by rep and hash table by James Robertson, CCC, October 07, 1999
2000 ...
- Can we use hash table at root? by Tim, CCC, January 31, 2000 » Root
- Re: Atomic write of 64 bits by Frans Morsch, comp.lang.asm.x86, September 25, 2000 » MMX, Parallel Search
- hashing function by Vladimir R. Medvedev, rgcc, October 17, 2000
- Hash table efficiency by Miguel A. Ballicora, CCC, December 05, 2000 » Gaviota, Search Statistics
- Why not store both a lower and an upper bound in a hashtable? by Leen Ammeraal, CCC, December 06, 2000
2001
- A fast hash -- assuming you are not planning to do incremental updates by Dann Corbit, CCC, June 15, 2001
- "Don't trust draw score" <=Is it true? by Teerapong Tovirat, CCC, August 08, 2001 » Repetitions, Path-Dependency
- About random numbers and hashing by Severi Salminen, CCC, December 04, 2001
- Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
- When to RecordHash()? by Sune Fischer, CCC, December 25, 2001
2002
- Non power of two hash table sizes by Alvaro Jose Povoa Cardoso, CCC, February 18, 2002
- Detecting Draws using a Small Hash Table? by Steve Maughan, CCC, February 20, 2002
- hash entry replacement schemes by Scott Farrell, CCC, September 14, 2002
- hash numbers requested: authors please read by James Swafford, CCC, September 17, 2002
2003
- How important is a big hash table? Measurements... by Tom Kerrigan, CCC, March 29, 2003
- Another memory latency test by Dieter Bürßner, CCC, July 17, 2003
- Replacement shemes by Sune Fischer, CCC, July 27, 2003
- Is it necessary to include empty fields in the hash key of a position? by Frank Hablizel, rgcc, December 25, 2003
2004
- I need your opinion about this hash entry structure by Federico Corigliano, CCC, January 02, 2004
- Question about details of hashing (olithink) by Michel Langeveld, CCC, January 22, 2004 » OliThink
- Fruit - Question for Fabien by Dan Honeycutt, CCC, March 11, 2004 » Fruit, Node Types, Principal Variation, Principal Variation Search
- Hashkey collisions (typical numbers) by Renze Steenhuisen, CCC, April 07, 2004 » Transposition Table - Collisions
- A move to search 2nd... Keep in the trans table? by Eric Oldre, CCC, July 21, 2004
- Transposition table replacement by Eric Oldre, CCC, July 29, 2004
2005 ...
- Side effects of transposition tables by Alessandro Scotti, Winboard Forum, March 04, 2005
- Hashing double bounds by Rasjid Chan, CCC, June 20, 2005
- Mate scores in the hash table by Eduardo Waghabi, Winboard Forum, September 02, 2005 » Mate Scores
- Re: Mate scores in the hash table by Bruce Moreland, Winboard Forum, September 04, 2005
- Re: Mate scores in the hash table by Josué Forte, Winboard Forum, September 04, 2005
- Hash table hit rate by Stef Luijten, Winboard Forum, November 16, 2005
2007
- Transposition Tables by Colin, CCC, July 15, 2007
- fail high handling with tranposition tables by Uri Blass, CCC, August 01, 2007
2008
- Problem with Transposition Table and Repitition-Draw by Oliver Brausch, CCC, January 11, 2008 » Repetitions
- Transposition Table and nps drop by Mathieu Pagé, CCC, February 27, 2008 » Nodes per Second
- Semi-Path Dependent Hashing: a semi-useless idea by Zach Wegner, CCC, May 24, 2008 » Path-Dependency
- Is 64 bits enough as a hash length by Mathieu Pagé, CCC, July 10, 2008
- 31 bit hash values. How often will it fail? by Carey, CCC, September 07, 2008 » Transposition Table - Collisions
- Adaptative LMR and TT by Fermin Serrano, CCC, December 23, 2008 » Late Move Reductions
2009
- transposition table details by Don Dailey, CCC, May 26, 2009
- Transposition Table by Pablo Vazquez, CCC, June 26, 2009
- Cache pollution when reading/writing hash table by Marco Costalba, CCC, August 09, 2009
- Transposition table pruning by Luca Hemmerich, CCC, November 25, 2009
2010 ...
- Correcting Evaluation with the hash table by Mark Lefler, CCC, February 05, 2010 » Evaluation
- TT hit/miss rates by Vlad Stamate, CCC, February 25, 2010
- Zero window TT entry by Vlad Stamate, CCC, March 05, 2010 » Null Window
- Null-move pruning and the hash table by Robert Purves, CCC, March 28, 2010 » Null Move Pruning
- Crafty Transpostion Table Question by Eric Stock, CCC, May 30, 2010 » Crafty, Lockless Hashing
- TT behavior by Karlo Bala Jr., CCC, June 25, 2011
- working! by Robert Hyatt, CCC, September 17, 2010 » Separate TT for the PV
- Is a querying the hash tables such a huge bottleneck? by Oliver Uwira, CCC, October 28, 2010
- Puzzle with mate scores in TT by Robert Purves, CCC, December 10, 2010 » Mate Scores
2011
- Transposition Table: addressing slots by Michael Hoffmann, CCC, March 18, 2011
- Transposition Table updates in Stockfish by Onno Garms, CCC, April 12, 2011 » Stockfish
- Hashing the PV by Stef Luijten, CCC, June 06, 2011
- Dual Bound TT by João Guerra, CCC, July 28, 2011
- TT Key Collisions, Workarounds? by Clemens Pruell, CCC, August 16, 2011
- Repetitions/50 moves and TT by Sergei Markoff, CCC, September 13, 2011 » Fifty-move Rule
- Determining the age of TT buckets by Julien Marcel, CCC, Sepember 18, 2011
- Key collision handling by Jonatan Pettersson, CCC, October 21, 2011
- Mate score in TT by Marco Costalba, CCC, December 28, 2011 » Mate Scores
2012
- Question on TT by Giuseppe Cannella, Winboard Forum, January 06, 2012
- Stockfish hash implementation by Jon Dart, CCC, January 10, 2012 » Stockfish
- cache alignment of tt by Daniel Shawul, CCC, March 11, 2012
- Hash table division by Ed Schröder, CCC, April 05, 2012
- TT question? by Fermin Serrano, CCC, May 19, 2012 » Quiescence Search
- hashtables by Daniel Anulliero, Winboard Forum, May 22, 2012
- how to measure frequency of hash collisions by Daniel Shawul, CCC, June 16, 2012
- TT avoid nullmove flag by Matthew R. Brades, CCC, August 02, 2012 » Null Move Pruning
- Transposition Table - Replacement and PV by Cheney Nattress, CCC, December 04, 2012
- Speaking of the hash table by Ed Schröder, CCC, December 09, 2012
2013
- Transposition table usage in quiescent search? by Jerry Donald, CCC, March 01, 2013 » Quiescence Search
- Transposition driven scheduling by Daniel Shawul, CCC, April 04, 2013 [31]
- The effect of larger hash size by Jacob Børs Lind, CCC, April 13, 2013
- Effect of the Hash Table size by Kai Laskos, CCC, April 28, 2013
- Hash cutoffs and analysis by Harm Geert Muller, CCC, June 17, 2013
- Hashing based on move lists by Matthew R. Brades, CCC, June 30, 2013
- transposition tables by Folkert van Heusden, CCC, July 23, 2013
- ep and castle rights hashing by Natale Galioto, CCC, September 15, 2013 » Castling Rights, En passant, Repetitions
- Hash tables: one bound or two bounds? by Alberto Sanjuan, CCC, December 11, 2013
2014
- LMR & TT interaction by Natale Galioto, CCC, April 29, 2014 » Late Move Reductions
- transposition and multithreading question by Marco Belli, CCC, May 04, 2014 » Parallel Search
- transposition table implementation help by lazyguy123, OpenChess Forum, August 09, 2014
- Transposition table chaining and replacement strategy by Alex Ferguson, CCC, August 28, 2014
- Using the Transposition Table for long searches by Theodr Elwurtz, FishCooking, September 22, 2014 » Stockfish
- Speculative prefetch by Peter Österlund, CCC, September 27, 2014 » Memory
- Transposition Table Oddity by Thomas Kolarik, CCC, September 28, 2014
- Can someone explain what advantage there is to... by Forrest Hoch, CCC, October 06, 2014
- Cache over-writing and PV's by Forrest Hoch, CCC, October 16, 2014 » Principal Variation
- Mate score from the transposition table by Evert Glebbeek, CCC, October 25, 2014 » Mate Scores
- Two hash functions for distributed transposition table by Daniel Shawul, CCC, December 16, 2014
- Transposition table in Q-search by Alex Ferguson, CCC, December 26, 2014 » Quiescence Search
2015 ...
- Legality Check on TT move by Jordan Bray, CCC, January 11, 2015
- (iteration+depth) TT replacement policy by Aleks Peshkov, CCC, February 27, 2015
- Idea #9228: Clearing stale transtable entries by Steven Edwards, CCC, April 06, 2015
- TTable questions by Henk van den Belt, CCC, April 11, 2015
- Fractional plies and transposition tables by Alexandru Mosoi, CCC, April 18, 2015 » Depth - Fractional Plies
- Re: Worst advice by Alexandru Mosoi, CCC, August 10, 2015
- most similar hashes of two positions by Alexandru Mosoi, CCC, August 12, 2015
- The cost of transposition table instrumentation by Steven Edwards, CCC, August 23, 2015
- atomic TT by lucasart, CCC, September 13, 2015
- Transposition table test positons by Robert Pope, CCC, September 11, 2015 » Test-Positions
- Hash cache by Harm Geert Muller, CCC, October 12, 2015
- Perft and hash with legal move generator by Peterpan, OpenChess Forum, November 12, 2015 » Perft
- Transposition table utilizattion by Shawn Chidester, CCC, December 29, 2015
2016
- On-the fly hash key generation? by Evert Glebbeek, CCC, January 12, 2016
- Transposition Age Tutorial by Dennis Sceviour, CCC, January 25, 2016
- TT Mate scores by rgoomes, OpenChess Forum, February 10, 2016 » Mate Scores
- Hashing question by Kenneth Jones, CCC, February 23, 2016
- TT and Iterative Deepening by kuket15, OpenChess Forum, February 26, 2016 » Iterative Deepening
- Transposition table replacement strategies by Shawn Chidester, CCC, March 01, 2016
- about hashtable by Daniel Anulliero, CCC, March 04, 2016
- Hashing in Qsearch? by Martin Fierz, CCC, April 03, 2016 » Quiescence Search
- Shifting alpha/beta on hash hit by Martin Fierz, CCC, April 14, 2016 » Search Instability
- What happens during a hash collision in say Stockfish ... by Isaac Haïk Dunn, CCC, April 24, 2016
- Hashtable aging by Martin Fierz, CCC, April 25, 2016
- Transposition Table replacement schemes by Andrew Grant, CCC, May 05, 2016
- lockless hashing by Lucas Braesch, CCC, May 10, 2016 » Shared Hash Table
- Suggestion for hash tables and analysis by J. Wesley Cleveland, May 22, 2016
- Hashtable and 50 move rule draws by Stan Arts, CCC, May 24, 2016 » Fifty-move Rule
- Transposition Table - Updating entries by Andrew Grant, CCC, June 24, 2016
- Transposition Table Usage by theturk1234, OpenChess Forum, July 12, 2016
- Aspiration window with TT question by sandermvdb, OpenChess Forum, August 01, 2016 » Aspiration Windows
- Storing both alpha and beta scores in TT by Thomas Dybdahl Ahle, CCC, August 02, 2016
- Using side to move as a separate bit in hash key by J. Wesley Cleveland, CCC, August 06, 2016 » Side to move
- Question about TT by stefano.c, FishCooking, August 21, 2016
- transposition table pseudocode by Erin Dame, CCC, August 22, 2016
- transposition tables and three-fold repetition by Erin Dame, CCC, September 10, 2016 » Repetitions
- Transposition tables in Cray Blitz by Erin Dame, CCC, September 26, 2016 [32] » Cray Blitz
- Hash table transformation by Dann Corbit, CCC, October 05, 2016
- Modify hash probing code to pvs by Fernando Tenorio, CCC, December 05, 2016
2017
- What is wrong with doing Nulls & ttcuts in a pv node ? by Mahmoud Uthman, CCC, January 21, 2017 » Null Move Pruning, PV-Nodes
- Interesting hash-replacement scheme by Harm Geert Muller, CCC, April 08, 2017
- Problems with TT, sometimes makes blunder moves by Tony Soares, CCC, April 12, 2017
- TT Table replacement strategy by kickstone, OpenChess Forum, April 29, 2017
- Hash Tables Deep Blue by Gustavo Mallada, CCC, May 18, 2017 » Deep Blue
- Hash table by Daniel José Queraltó, CCC, June 12, 2017
- Improving hash replacing schema for analysis mode by Daniel José Queraltó, CCC, July 05, 2017 » Replacement Strategy, Persistent Hash Table
- TT aging by Marco Pampaloni, CCC, July 09, 2017
- Equidistributed draft by Alvaro Cardoso, CCC, July 14, 2017
- 2-level TT by Rein Halbersma, CCC, July 14, 2017
- cutechess-cli: not restarting an engine because of tt by Folkert van Heusden, CCC, July 22, 2017 » Cutechess-cli
- Size of Transposition Table Entry by Jason Fernandez, CCC, September 29, 2017
- Transposition table and Fine#70 by Vincent Tang, CCC, October 23, 2017 » Lasker-Reichhelm Position
- TT in Qsearch by Laurie Tunnicliffe, CCC, December 05, 2017 » Quiescence Search
- Transposition table based pruning idea by Jerry Donald, CCC, December 25, 2017 » Pruning
- hashing in chess4j by James Swafford, CCC, December 30, 2017 » chess4j
2018
- Marcel Duchamp endgame "splits" engines / hash phenomenon by Kenneth Regan, CCC, February 19, 2018 » Marcel Duchamp
- Do You Track Hash Table Efficiency? by OneMoreTime, OpenChess Forum, April 07, 2018
- Mate scores in TT (a new?... approach) by Vince Sempronio, CCC, April 09, 2018
- Yet another Mate scores in TT thread by Andrew Grant, CCC, April 12, 2018 » Checkmate, Score
- Draw scores in TT by Srdja Matovic, CCC, April 14, 2018 » Draw, Draw Score
- Depth extensions and effect on transposition queries by Kenneth Jones, CCC, April 16, 2018 » Extensions, Check Extensions
- Not detected collisions in tt probing by Andreas Matthies, CCC, May 09, 2018 » Collisions
2019
- Playing transposition table moves in the Quiescence search by Andrew Grant, CCC, January 17, 2019 » Quiescence Search
- Prefetch and Threading by Dennis Sceviour, CCC, April 25, 2019 » Memory, Thread
- Debugging a transposition table by Vincent Tang, CCC, May 29, 2018 » Debugging, Lasker-Reichhelm Position
- Hash collision? by Tom King, CCC, June 05, 2019
- Looking for TT policy advice by Vivien Clauzon, CCC, October 04, 2019 » Replacement Strategy
- Probing the transposition table at depth 0 by Gonzalo Arro, CCC, November 29, 2019
2020 ...
- hash collisions by Jon Dart, CCC, January 28, 2020 » Key Collisions
- Dense board representation as hash code by koedem, CCC, February 01, 2020
- Zobrist key independence by Harm Geert Muller, CCC, February 17, 2020 » Zobrist Hashing
- SIMD methods in TT probing and replacement by Harm Geert Muller, CCC, February 20, 2020 » SIMD and SWAR Techniques
- Measuring Hash Collisions (once again) by Ed Schröder, CCC, February 27, 2020
- Hash size, hash fullness, strength by Vivien Clauzon, CCC, February 29, 2020
- Where to enter/read position into hash table in perft? by Marcel Vanthoor, CCC, March 28, 2020 » Perft
- Hash entry/bucket memory usage optimization by Marcel Vanthoor, CCC, March 30, 2020
- asymmetric evaluation and TT by Vivien Clauzon, CCC, June 02, 2020 » Asymmetric Evaluation
- Correct way to store and extract mate scores by Ian Mitchell, CCC, July 08, 2020 » Checkmate, Score
- Principal Variation Search vs. Transposition Table by Marcel Vanthoor, CCC, October 26, 2020 » Principal Variation, Principal Variation Search
2021
- Transposition table replacement scheme by Niels Abildskov, CCC, February 05, 2021
- Best practices for transposition tables by Brian Adkins, CCC, February 06, 2021
- TT: key collisions by Brian Adkins, CCC, February 13, 2021 » Key Collisions
- Hash move ordering vs. Hash cuts: savings in number of nodes visited by Marcel Vanthoor, CCC, March 16, 2021
- PERFT transposition table funny?! by Martin Bryant, CCC, April 10, 2021 » Perft, Memory
- For or against the transposition table probe in quiet search? by Eugene Kotlov, CCC, May 11, 2021 » Quiescence Search
- Saving moves into the TT by Marcel Vanthoor, CCC, June 11, 2021
- Hash value composition by Yves De Billoëz, CCC, June 17, 2021
- When to clear the Transposition table? by Thomas Jahn, CCC, June 28, 2021
- About move ordering and TT hitrate by Giovanni Maria Manduca, CCC, October 22, 2021 » Move Ordering
2022
- Transposition table based cutoffs by Michal Witanowski, CCC, April 05, 2022
- Consensus for TT: Buckets with Entries, or Entries with Buckets? by Marcel Vanthoor, CCC, April 19, 2022
2023
- Checking TT move for legality by Aaron Li, CCC, August 20, 2023
2024
- Help with transposition table by E Boatwright, CCC, January 21, 2024
- adding TT reduces NPS by allot by Ravael Jansen, CCC, March 29, 2024
- Hybride replacemment strategy worse than always-replace by mathmoi, CCC, April 25, 2024
External Links
- The Main Transposition Table from Bruce Moreland's Programming Topics
- Transposition table from Wikipedia
- Zobrist hashing from Wikipedia
- Gödel numbering from Wikipedia
- Computer Chess - Hash Collisions in Chess Engines, and What They May Mean... by Kenneth W. Regan
- Hashing in chess4j by James Swafford, December 30, 2017» chess4j
- Tal Wilkenfeld - Table For One, YouTube Video
References
- ↑ Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted (1988) in Computer Chess Compendium, pdf from The Computer History Museum or as pdf or ps from DSpace at MIT
- ↑ 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 ICCA Journal, Vol. 13, No. 2, pdf
- ↑ Re: Berliner vs. Botvinnik Some interesting points, post 8 by Bradley C. Kuszmaul, rgcc, November 06, 1996 » Transposition Table in Mac Hack
- ↑ Algorithms that use dynamic programming from Wikipedia
- ↑ Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (2006). Algorithms. McGraw-Hill, ISBN: 978-0073523408, amazon, Chapter 6, Dynamic programming
- ↑ Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1997). Information in Transposition Tables. Advances in Computer Chess 8
- ↑ MTD(f)- and some PVS-implementations store distinct upper and lower bound scores, rather than one score with flags
- ↑ Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
- ↑ 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 ICCA Journal, Vol. 13, No. 2, pdf
- ↑ Collision probability by Dennis Breuker, rgcc, April 15, 1996
- ↑ TT Key Collisions, Workarounds? by Clemens Pruell, CCC, August 16, 2011
- ↑ how to measure frequency of hash collisions by Daniel Shawul, CCC, June 16, 2012
- ↑ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean... by Kenneth W. Regan
- ↑ Pablo Lafuente vs Shredder (Computer) (2005) from chessgames.com
- ↑ Current tournaments – Sanjin, Biel, Argentina, Israel, ChessBase News, July 21, 2005
- ↑ James Gillogly (1989). Transposition Table Collisions. Workshop on New Directions in Game-Tree Search
- ↑ James Gillogly (1989). New Directions in Game-Tree Search - First Workshop Session. ICCA Journal, Vol. 12, No. 2
- ↑ Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 3
- ↑ Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1994). Replacement Schemes for Transposition Tables. ICCA Journal, Vol. 17, No. 4
- ↑ Re: Transposition table usage in quiescent search? by Robert Hyatt, CCC, March 06, 2013
- ↑ Joe Condon, Ken Thompson (1983). BELLE Chess Hardware. Advances in Computer Chess 3
- ↑ Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1996). Replacement Schemes and Two-Level Tables. ICCA Journal, Vol. 19, No. 3
- ↑ Don Beal, Martin C. Smith (1996). Multiple Probes of Transposition Tables. ICCA Journal, Vol. 19, No. 4
- ↑ Transposition Age Tutorial by Dennis Sceviour, CCC, January 25, 2016
- ↑ Hashtable aging by Martin Fierz, CCC, April 25, 2016
- ↑ Robert Hyatt and Tim Mann (2002). A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1
- ↑ Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
- ↑ Transposition-driven scheduling - Wikipedia
- ↑ Transposition driven scheduling by Daniel Shawul, CCC, April 04, 2013
- ↑ Re. Fail low after fail high by Marcel van Kervinck, CCC, April 05, 2015 » Fail-Low , Fail-High
- ↑ 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. pdf
- ↑ David E. Welsh, Boris Baczynskyj (1985). Computer Chess II. William C Brown Publications, ISBN-13: 978-0697099112