Difference between revisions of "Transposition Table"

From Chessprogramming wiki
Jump to: navigation, search
(24 intermediate revisions by the same user not shown)
Line 5: Line 5:
  
 
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]] 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> .  
+
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=  
Line 102: Line 102:
 
<span id="Entry"></span>
 
<span id="Entry"></span>
 
=What Information is Stored=  
 
=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> :
+
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 look whether the position is the right one while probing
 
* [[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]]
 
* [[Best Move|Best-]] or [[Refutation Move|Refutation move]]
Line 117: Line 117:
 
<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]] 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:
+
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 135: Line 135:
 
<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]] 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> .
+
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 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> .
+
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]], [[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==  
Line 181: Line 181:
 
=Publications=  
 
=Publications=  
 
==1967 ...==  
 
==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]]
+
* [[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 192:
 
==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]] and [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]
+
* [[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 236: Line 236:
 
* [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 263: Line 264:
 
'''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 295: Line 297:
 
* [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/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/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 Bala Jr.]], [[CCC]], June 25, 2011
+
* [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 335: Line 337:
 
* [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 396: Line 399:
 
* [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/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]]
Line 406: Line 410:
 
* [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'''
 
'''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=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=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=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=71994 Looking for TT policy advice] by [[Vivien Clauzon]], [[CCC]], October 04, 2019 » [[#ReplacementStrategies|Replacement Strategy]]
Line 416: Line 422:
 
* [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=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=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
  
 
=External Links=  
 
=External Links=  

Revision as of 07:46, 29 June 2021

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

How it works

When the search encounters a 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 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. Therefor to calculate the address or index requires signature modulo number of entries, for power of two sized tables, the lower part of the hash key, masked by an 'and'-instruction accordantly.

Collisions

The 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:

Cardinalities of positions and signatures #
Upper bound for the number of reachable chess positions [6] 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 number of entries 1e8

Index Collisions

Index collisions or type-2 errors [7] [8] , 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.

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 [9] [10] . 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 [11], 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 [12] [13] .

Bits Required

During the WCCC 1989 Workshop New Directions in Game-Tree Search, James Gillogly, author of Tech, discussed transposition table collisions [14] . 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 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 [15]. The dangers of transposition table collisions were further studied by Robert Hyatt and Anthony Cozzie as published in their 2005 paper Hash Collisions Effect [16]. 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.

What Information is Stored

Typically, the following information is stored as determined by the search [17] :

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.

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

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.

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 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 [23] .

Aging

Aging considers searches of different chess positions during game play. 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, 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 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

Publications

1967 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1990 ...

1995 ...

1996

1997

Re: Hash functions for use with a transition table by Ronald de Man, rgcc, March 7, 1997 » BCH Hashing

1998

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

1999

2000 ...

2001

2002

2003

2004

2005 ...

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

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2019

2020 ...

2021

External Links

References

  1. 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
  2. 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
  3. Re: Berliner vs. Botvinnik Some interesting points, post 8 by Bradley C. Kuszmaul, rgcc, November 06, 1996 » Transposition Table in Mac Hack
  4. Algorithms that use dynamic programming from Wikipedia
  5. Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (2006). Algorithms. McGraw-Hill, ISBN: 978-0073523408, amazon, Chapter 6, Dynamic programming
  6. Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
  7. 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
  8. Collision probability by Dennis Breuker, rgcc, April 15, 1996
  9. TT Key Collisions, Workarounds? by Clemens Pruell, CCC, August 16, 2011
  10. how to measure frequency of hash collisions by Daniel Shawul, CCC, June 16, 2012
  11. Computer Chess - Hash Collisions in Chess Engines, and What They May Mean... by Kenneth W. Regan
  12. Pablo Lafuente vs Shredder (Computer) (2005) from chessgames.com
  13. Current tournaments – Sanjin, Biel, Argentina, Israel, ChessBase News, July 21, 2005
  14. James Gillogly (1989). Transposition Table Collisions. Workshop on New Directions in Game-Tree Search
  15. James Gillogly (1989). New Directions in Game-Tree Search - First Workshop Session. ICCA Journal, Vol. 12, No. 2
  16. Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 3
  17. Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1997). Information in Transposition Tables. Advances in Computer Chess 8
  18. MTD(f)- and some PVS-implementations store distinct upper and lower bound scores, rather than one score with flags
  19. Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1994). Replacement Schemes for Transposition Tables. ICCA Journal, Vol. 17, No. 4
  20. Re: Transposition table usage in quiescent search? by Robert Hyatt, CCC, March 06, 2013
  21. Joe Condon, Ken Thompson (1983). BELLE Chess Hardware. Advances in Computer Chess 3
  22. Dennis Breuker, Jos Uiterwijk, Jaap van den Herik (1996). Replacement Schemes and Two-Level Tables. ICCA Journal, Vol. 19, No. 3
  23. Don Beal, Martin C. Smith (1996). Multiple Probes of Transposition Tables. ICCA Journal, Vol. 19, No. 4
  24. Transposition Age Tutorial by Dennis Sceviour, CCC, January 25, 2016
  25. Hashtable aging by Martin Fierz, CCC, April 25, 2016
  26. Robert Hyatt and Tim Mann (2002). A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1
  27. Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
  28. Transposition-driven scheduling - Wikipedia
  29. Transposition driven scheduling by Daniel Shawul, CCC, April 04, 2013
  30. Re. Fail low after fail high by Marcel van Kervinck, CCC, April 05, 2015 » Fail-Low , Fail-High
  31. 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
  32. David E. Welsh, Boris Baczynskyj (1985). Computer Chess II. William C Brown Publications, ISBN-13: 978-0697099112

Up one Level