Changes

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

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