Changes

[[Arts#Dali:Category:Salvador Dalí|Salvador Dalí]], [https://en.wikipedia.org/wiki/The_Persistence_of_Memory The Persistence of Memory] 1931 ]]

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

Key collisions or type-1 errors are inherent in using signatures with far less bits than required to encode all reachable chess positions. A key collision occurs when two different positions map the same hash key or signature <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012</ref> . When storing only a partial key, the chance of a collision greatly increases. To accept only hits where [[Hash Move|stored moves]] are [[Pseudo-Legal Move|pseudo-legal]] decreases the chance of type-1 errors. On his computer chess page <ref>[http://www.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate W. Regan]]</ref>, [[Kenneth Wingate 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> .

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

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:

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

* [[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]]

* [[Don Beal]] and , [[Martin C. Smith]] ('''1996'''). ''Multiple Probes of Transposition Tables''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]

* [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/browse_frm0sIKY_dfLUs/thread/d2c20a63f75f2d4b Qw9J1ECWeBoJ Hash functions for use with a transition table] by [[Tim Foden]], [[Computer Chess Forums|rgcc]], March 5, 1997» [[Transposition Table]]: [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/msg0sIKY_dfLUs/9b240379394bc968 aMlLOXkDJJsJ Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997 » [[BCH Hashing]]

* [https://www.stmintz.com/ccc/index.php?id=306858 Another memory latency test] by [[Dieter BürssnerBürßner]], [[CCC]], July 17, 2003

* [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=64522 Improving hash replacing schema for analysis mode] by [[Daniel José Queraltó]], [[CCC]], July 05, 2017 » [[Transposition Table#ReplacementStrategies|Replacement Strategy]], [[Persistent Hash Table]]

* [http://www.talkchess.com/forum/viewtopic.php?t=66640 Marcel Duchamp endgame "splits" engines / hash phenomenon] by [[Kenneth Wingate W. Regan|Kenneth Regan]], [[CCC]], February 19, 2018 » [[Arts#: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.cse.buffalo.edu/~regan/chess/computer/ Computer Chess - Hash Collisions in Chess Engines, and What They May Mean...] by [[Kenneth Wingate W. Regan]]

* [[Videos#TalWilkenfeld: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