25,161
edits
Changes
Created page with "'''Home * Search * Transposition Table * Zobrist Hashing''' FILE:King Wen (I Ching).svg|border|right|thumb| [https://en.wikipedia.org/wiki/King_Wen_se..."
'''[[Main Page|Home]] * [[Search]] * [[Transposition Table]] * Zobrist Hashing'''
[[FILE:King Wen (I Ching).svg|border|right|thumb| [https://en.wikipedia.org/wiki/King_Wen_sequence King Wen sequence] <ref>[https://en.wikipedia.org/wiki/King_Wen_sequence King Wen sequence], [https://en.wikipedia.org/wiki/I_Ching I Ching] [https://en.wikipedia.org/wiki/I_Ching_divination divination] involves obtaining a [https://en.wikipedia.org/wiki/Hexagram_%28I_Ching%29 Hexagram] by random generation</ref> <ref>All of [[Arts#Cage|Cage's]] [https://en.wikipedia.org/wiki/Music_of_Changes music] since 1951 was composed using [https://en.wikipedia.org/wiki/John_Cage#Chance chance] procedures, most commonly using the [https://en.wikipedia.org/wiki/I_Ching I Ching]</ref> ]]
'''Zobrist Hashing''',<br/>
a technique to transform a board [[Chess Position|position]] of arbitrary size into a number of a set length, with an equal distribution over all possible numbers, invented by [[Albert Zobrist]] <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>. In an early Usenet post in 1982, [[Tom Truscott]] mentioned [[James Gillogly|Jim Gillogly's]] n-bit hashing technique <ref>[http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982</ref>, who apparently read Zobrist's paper early, and credits Zobrist in a 1997 [[Computer Chess Forums|rgcc]] post <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/oKgv-7WbfO0/TH-p0KUIo2kJ Re: Hashing function for board positions]by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997</ref>. Zobrist Hashing is an instance of [https://en.wikipedia.org/wiki/Tabulation_hashing tabulation hashing] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55449&start=4 Re: Zobrist keys - measure of quality?] by [[Rein Halbersma]], [[CCC]], February 24, 2015</ref>, a method for constructing [https://en.wikipedia.org/wiki/Universal_hashing universal families of hash functions] by combining [https://en.wikipedia.org/wiki/Lookup_table table lookup] with [[General Setwise Operations#ExclusiveOr|exclusive or]] operations. Zobrist Hashing was rediscovered by [[Mathematician#JLCarter|J. Lawrence Carter]] and [[Mathematician#MNWegman|Mark N. Wegman]] in 1977 <ref>[[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]</ref> and studied in more detail by [[Mathematician#MPatrascu|Mihai Pătrașcu]] and [[Mathematician#MThorup|Mikkel Thorup]] in 2011 <ref>[[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]</ref> <ref>[https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]</ref>.
The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient [[Hash Table|Hash tables]] or databases, e.g. [[Transposition Table|transposition tables]] and [[Opening Book|opening books]].
=Metamorphosis=
[[FILE:Metamorphosis_II_1.jpg|none|border|text-bottom|640px|link=http://www.mcescher.com/Gallery/gallery-recogn.htm]]
[[FILE:Metamorphosis_II_2.jpg|none|border|text-bottom|640px|link=http://www.mcescher.com/Gallery/gallery-recogn.htm]]
[[Arts#Escher|M. C. Escher]], [https://en.wikipedia.org/wiki/Metamorphosis Metamorphosis] III, 1967-1968 <ref>[http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref>
=Initialization=
At program initialization, we generate an [[Array|array]] of [[Pseudorandom Number Generator|pseudorandom numbers]] <ref>[http://www.random.org/integers/?mode=advanced RANDOM.ORG - Integer Generator]</ref> <ref>[http://www.stat.fsu.edu/pub/diehard/ The Marsaglia Random Number CDROM including the Diehard Battery of Tests] by [[Mathematician#GMarsaglia|George Marsaglia]]</ref>:
* One number for each [[Pieces|piece]] at each [[Squares|square]]
* One number to indicate the [[Side to move|side to move]] is black
* Four numbers to indicate the [[Castling rights|castling rights]], though usually 16 (2^4) are used for speed
* Eight numbers to indicate the [[Files|file]] of a valid [[En passant]] square, if any
This leaves us with an array with 781 (12*64 + 1 + 4 + 8) random numbers. Since pawns don't happen on first and eighth rank, one might be fine with 12*64 though. There are even proposals and implementations to use overlapping keys from unaligned access up to an array of only 12 numbers for every piece and to rotate that number by square <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=245932&t=26152 Re: Zobrist key random numbers] by [[Zach Wegner]], [[CCC]], January 22, 2009</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30008 Overlapped Zobrist keys array] by [[Stefano Gemma]], [[CCC]], October 06, 2009</ref> .
Programs usually implement their own [[Pseudorandom Number Generator|Pseudorandom number generator]] (PRNG), both for better quality random numbers than standard library functions, and also for reproducibility. This means that whatever platform the program is run on, it will use the exact same set of Zobrist keys. This is also useful for things like opening books, where the positions in the book can be stored by hash key and be used portably across machines, considering [[Endianness|endianness]].
=Runtime=
If we now want to get the Zobrist hash code of a certain position, we initialize the hash key by [[General Setwise Operations#ExclusiveOr|xoring]] all random numbers linked to the given feature, e.g. the [[Initial Position|initial position]]:
<pre>
[Hash for White Rook on a1] xor [Hash for White Knight on b1] xor [Hash for White Bishop on c1] xor ... ( all pieces )
... xor [Hash for White king castling] xor [Hash for White queeb castling] xor ... ( all castling rights )
</pre>
The fact that xor-operation is [https://en.wikipedia.org/wiki/Involution own inverse] and can be undone by using the same xor-operation again, is often used by chess engines. It allows a fast [[Incremental Updates|incremental update]] of the hash key during [[Make Move|make]] or [[Unmake Move|unmake]] [[Moves|moves]]. E.g., for a White Knight that jumps from b1 to c3 capturing a Black Bishop, these operations are performed:
<pre>
[Original Hash of position] xor [Hash for White Knight on b1] ... ( removing the knight from b1 )
... xor [Hash for Black Bishop on c3] ( removing the captured bishop from c3 )
... xor [Hash for White Knight on c3] ( placing the knight on the new square )
... xor [Hash for Black to move] ( change sides)
</pre>
=Collisions=
[[Transposition Table#KeyCollisions|Key collisions]] or type-1 errors are inherent in using Zobrist keys with far less bits than required to encode all reachable chess positions.
==Theory==
An important issue is the question of what size the hash keys should have. Smaller hash keys are faster and more space efficient, while larger ones reduce the risk of a hash collision. A collision occurs if two positions map the same key <ref>[https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004</ref> . The dangers of which were well assessed by [[Robert Hyatt]] and [[Anthony Cozzie]] in their 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>. Usually 64bit are used as a standard size in modern chess programs.
Hash collisions demonstrate the [https://en.wikipedia.org/wiki/Birthday_problem birthday "paradox"], which is to say the chance of collisions approaches certainty at around the '''square root''' of the number of possible keys, contrary to some people's expectations. You can expect to encounter a collision in a 32 bit hash when you have evaluated sqrt(2 ^ 32) == 2 ^ 16 or around 65 thousand positions. With a 64 bit hash, you can expect a collision after about 2 ^ 32 or 4 billion positions.
==Praxis==
Post by [[Jonathan Schaeffer]] <ref>[https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/9zrP0flwuzAJ Re: Hash tables - Clash!!! What happens next?] by [[Jonathan Schaeffer]], March 17, 1994</ref> :
... I can speak from experience here. In the early versions of my chess program [[Phoenix]], I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the random numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were '''lots''' of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error. All randomly generated numbers are not the same!
==Lack a True Integer Type==
<span id="LackInt"></span>Some languages (such as [[JavaScript]] and [https://en.wikipedia.org/wiki/Lua_%28programming_language%29 Lua]) only have a [[Double|64-bit floating point]] "Number" type. In JavaScript, this type breaks down into a 32 bit integer when bitwise operators are used. One way to get a 64 bit hash is to use two 32 bit numbers in parallel, as [[Garbochess-JS]] <ref>[http://forwardcoding.com/projects/ajaxchess/chess.html Garbochess-JS]</ref> does. Another, which [[p4wn]] used at one stage, is to use 47 or 48 bit '''additive''' hashes. 64 bit floating point numbers are true integers up to 53 bits, so it is possible to sum at least 32 (and on average close to 64) random 48 bit numbers, which was enough for p4wn's purposes. For additive Zobrist hashing, you add the number when placing a piece and subtract it when removing it, rather than using xor both ways. There is no difference in accuracy or speed, and 48 bit hashes give you collisions at around the 2 ^ 24 or 16 million point.
==Linear Independence==
The minimum and average [[Population Count#HammingDistance|Hamming Distance]] over all Zobrist keys was often considered as "quality"-measure of the keys. However, maximizing the minimal hamming distance leads to very poor Zobrist keys. As long the minimum hamming distance is greater zero, [https://en.wikipedia.org/wiki/Linear_independence linear independence] (that is a small subset of all keys doesn't xor to zero), is much more important than hamming distance as explained by [[Sven Reichard]] <ref>[https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001</ref> :
{|
|-
| Assume we associate a bitstring to every piece-square combination. That is what's usually done in chess programs; some codes are added for the side to move, castling rights, e.p. squares, etc. We obtain the code of a position by xor-ing the codes of all the pieces contained in it.
What we want to avoid is collisions at nodes close to the root. For nodes close to the leaves the cost of recomputing the score is smaller. Hence we want to avoid that:
<pre>
x1^x2^...^xm = y1^y2^...^yn
for codes xi, yi and small number m and n, and xi not equal to yj
</pre>
To translate that to a language that is more familiar - at least for people of a mathematical background - we consider the [https://en.wikipedia.org/wiki/Field_%28mathematics%29#Finite_fields field F2] of two elements. The elements are 0 and 1, and we can add and multiply them as usual, with the additional rule that 1 + 1 = 0. This is really a field, just like the [https://en.wikipedia.org/wiki/Real_number real] or [https://en.wikipedia.org/wiki/Complex_number complex numbers], and we can do calculations as usual. Note that addition is just the exclusive or.
Now the codes or bitstrings become [https://en.wikipedia.org/wiki/Vector_%28mathematics_and_physics%29 vectors] over the field F2, and the bitwise exclusive or becomes componentwise addition, i.e., usual addition of vectors. All these vectors form the [https://en.wikipedia.org/wiki/Vector_space vector space] F2^k, where k is the length of the vectors. Typically, k = 64.
So, what we want to avoid is an equation
<pre>
x1 + x2 + ... + xm = y1 + y2 + ... + yn
</pre>
or
<pre>
x1 + x2 + ... + xm + y1 + y2 + ... + yn = 0
</pre>
since in F2, subtraction is the same as addition. Remembering some [https://en.wikipedia.org/wiki/Linear_algebra linear algebra], this just means that we want the set x1,...,xm,y1,...,yn to be linearly independent.
This leads to the following criterion for picking a set of hashcodes: A set of vectors in F2^k is a good set of hash codes if each small subset of non-zero vectors is linearly independent. What is not clear here is the meaning of "small", but we want small to be as big as possible. In other words, we consider sets of size up to a certain size as small, and if we can make that size bigger, it is better, since this leads to unique codes deeper in the tree.
However what is clear is that this quality criterion does not depend on the base of the vector space. I.e., if we have a good set and multiply each vector by an invertible matrix (in other words, if we rotate the vectors), the obtained set will be just as good, since the rotation does not change the linear independence. The Hamming distance, on the other hand, is highly dependent on the vector space base. Take for example the vectors (1,0) and (0,1) in F2^2; they have Hamming distance 2. If we multiply both of them by
<pre>
(1 1)
(0 1)
</pre>
we get (1,1) and (0,1), which have Hamming distance 1. Actually we can change any distance to anything else (except for 0) by an appropriate matrix. Thus we try to approximate something that is independent from the base (the quality of our hash codes) by something that depends on it (the Hamming distance). Simple logic tells you that this approximation has to be real bad. An example where it doesn't work: It has been said that the Hamming distance shouldn't be to small or to big. So, vectors at a distance which is half the length should be ok, right? Let the length be 8 (I don't want to type too many 0's and 1's), and consider the vectors
<pre>
11110000
11001100
00111100
</pre>
They all have weight 4, their pairwise distance is 4, and yet they add up to 0. Just by looking at Hamming distances, you have no chance of detecting that.
Summarizing I can say that I see no connection between the quality of hash codes and their Hamming distance. Using a good RNG like the one provided in GNU's stdlib will yield good hash codes ( you can actually prove that), and so I will take the codes as they are supplied by rand() or random() without messing with them and thereby most likely make them worse.
|}
=See also=
* [[CPW-Engine_transposition]]
* [[BCH Hashing]]
=Publications=
* [[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]
* [[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28., No. 3]]
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Viljem Žumer]] ('''2005'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1491153 The Representation of Chess Game]''. Proceedings of the 27th International Conference on Information Technology Interfaces
* [[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]
=Forum Posts=
==1982 ...==
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982
==1990 ...==
* [https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/Jq7rYE0vqtoJ Hash tables - Clash!!! What happens next?] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgc]], March 15, 1994
: [https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/9zrP0flwuzAJ Re: Hash tables - Clash!!! What happens next?] by [[Jonathan Schaeffer]], March 17, 1994
* [https://groups.google.com/d/msg/rec.games.chess.computer/C53jRusegwA/XzgyZLbzcn8J Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/JZ-_0rObjuQ/Mfwy9qBLxoAJ Re: Berliner vs. Botvinnik Some interesting points] by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 6, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/oKgv-7WbfO0/TH-p0KUIo2kJ Re: Hashing function for board positions]by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=29817 How to create a set of random integers for hashing?] by [[Ed Schroder|Ed Schröder]], [[CCC]], October 18, 1998
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/587d039679461fb8 Why Random Number Needed In HashFunction[piece][position]] by Cheok Yan Cheng, [[Computer Chess Forums|rgcc]], June 12, 2001
* [https://www.stmintz.com/ccc/index.php?id=200366 About random numbers and hashing] by [[Severi Salminen]], [[CCC]], December 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=245775 Random keys and hamming distance] by [[James Swafford]], [[CCC]], August 16, 2002
* [https://www.stmintz.com/ccc/index.php?id=313807 Hamming distance and lower hash table indexing] by [[Tom Likens]], [[CCC]], September 02, 2003
* [https://www.stmintz.com/ccc/index.php?id=324223 64-Bit random numbers] by [[Martin Schreiber]], [[CCC]], October 28, 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
* [https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=26152 Zobrist key random numbers] by [[Robert Hyatt]], [[CCC]], January 21, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28523 Incremental Zobrist - slow?] by [[Vlad Stamate]], [[CCC]], June 20, 2009 » [[Incremental Updates]]
* [http://talkchess.com/forum/viewtopic.php?t=28545 On Zobrist keys] by [[Lasse Hansen]], [[CCC]], June 21, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30008 Overlapped Zobrist keys array] by [[Stefano Gemma]], [[CCC]], October 06, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35415 Transposition table random numbers] by Justin Madru, [[CCC]], July 13, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40849 Key collision handling] by [[Jonatan Pettersson]], [[CCC]], October 21, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1872 Using a Transposition Table with Zobrist Keys] by Miyagi403, [[Computer Chess Forums|OpenChess Forum]], February 21, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43910 MT or KISS ?] by [[Dan Honeycutt]], [[CCC]], June 02, 2012 <ref>[https://en.wikipedia.org/wiki/Mersenne_twister Mersenne twister from Wikipedia]</ref> <ref>[http://compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519 64-bit KISS RNGs] by [[Mathematician#GMarsaglia|George Marsaglia]], [http://compgroups.net/comp.lang.fortran/ comp.lang.fortran | Computer Group], February 28, 2009</ref> <ref>[[Bob Jenkins#RKISS|RKISS]] by [[Bob Jenkins]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=44043 Zobrist alternative?] by [[Harm Geert Muller]], [[CCC]], June 12, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45605 Zobrist Number Statistics and WHat to Look For] by Andrew Templeton, [[CCC]], October 16, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2178 Question about Zobrist code] by Hamfer, [[Computer Chess Forums|OpenChess Forum]], December 19, 2012
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55449 Zobrist keys - measure of quality?] by [[Martin Sedlak]], [[CCC]], February 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=58890&start=13 Re: On-the fly hash key generation?] by [[Aleks Peshkov]], [[CCC]], January 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61411 Rotated hash] by [[J. Wesley Cleveland]], [[CCC]], September 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61533 No Zobrist key] by [[Henk van den Belt]], [[CCC]], September 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62733 Enpass + Castling for Zorbist hashes] by [[Andrew Grant]], [[CCC]], January 06, 2017 » [[Castling rights]], [[En passant]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66372 Zobrist hashing for text] by [[Alvaro Cardoso]], [[CCC]], January 20, 2018
=External Links=
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]
* [http://web.archive.org/web/20070810003508/www.seanet.com/%7Ebrucemo/topics/zobrist.htm Zobrist keys] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [http://mediocrechess.blogspot.com/2007/01/guide-zobrist-keys.html Zobrist keys] from [http://mediocrechess.blogspot.com/ Mediocre Chess] by [[Jonatan Pettersson]]
* [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbering from Wikipedia]
* [[Arts#Cage|John Cage]] - [https://en.wikipedia.org/wiki/Music_of_Changes Music of Changes], Book 1 (1951), performed by [https://www.facebook.com/vickychowpianist Vicky Chow], [https://www.facebook.com/DiMennaCenter DiMenna Center], [https://en.wikipedia.org/wiki/New_York_City NYC], June 09, 2012, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=Y7LD1iTl-lM|alignment=left|valignment=top}}
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
[[Category:M. C. Escher]][[Category:John Cage]]
[[FILE:King Wen (I Ching).svg|border|right|thumb| [https://en.wikipedia.org/wiki/King_Wen_sequence King Wen sequence] <ref>[https://en.wikipedia.org/wiki/King_Wen_sequence King Wen sequence], [https://en.wikipedia.org/wiki/I_Ching I Ching] [https://en.wikipedia.org/wiki/I_Ching_divination divination] involves obtaining a [https://en.wikipedia.org/wiki/Hexagram_%28I_Ching%29 Hexagram] by random generation</ref> <ref>All of [[Arts#Cage|Cage's]] [https://en.wikipedia.org/wiki/Music_of_Changes music] since 1951 was composed using [https://en.wikipedia.org/wiki/John_Cage#Chance chance] procedures, most commonly using the [https://en.wikipedia.org/wiki/I_Ching I Ching]</ref> ]]
'''Zobrist Hashing''',<br/>
a technique to transform a board [[Chess Position|position]] of arbitrary size into a number of a set length, with an equal distribution over all possible numbers, invented by [[Albert Zobrist]] <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>. In an early Usenet post in 1982, [[Tom Truscott]] mentioned [[James Gillogly|Jim Gillogly's]] n-bit hashing technique <ref>[http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982</ref>, who apparently read Zobrist's paper early, and credits Zobrist in a 1997 [[Computer Chess Forums|rgcc]] post <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/oKgv-7WbfO0/TH-p0KUIo2kJ Re: Hashing function for board positions]by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997</ref>. Zobrist Hashing is an instance of [https://en.wikipedia.org/wiki/Tabulation_hashing tabulation hashing] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55449&start=4 Re: Zobrist keys - measure of quality?] by [[Rein Halbersma]], [[CCC]], February 24, 2015</ref>, a method for constructing [https://en.wikipedia.org/wiki/Universal_hashing universal families of hash functions] by combining [https://en.wikipedia.org/wiki/Lookup_table table lookup] with [[General Setwise Operations#ExclusiveOr|exclusive or]] operations. Zobrist Hashing was rediscovered by [[Mathematician#JLCarter|J. Lawrence Carter]] and [[Mathematician#MNWegman|Mark N. Wegman]] in 1977 <ref>[[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]</ref> and studied in more detail by [[Mathematician#MPatrascu|Mihai Pătrașcu]] and [[Mathematician#MThorup|Mikkel Thorup]] in 2011 <ref>[[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]</ref> <ref>[https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]</ref>.
The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient [[Hash Table|Hash tables]] or databases, e.g. [[Transposition Table|transposition tables]] and [[Opening Book|opening books]].
=Metamorphosis=
[[FILE:Metamorphosis_II_1.jpg|none|border|text-bottom|640px|link=http://www.mcescher.com/Gallery/gallery-recogn.htm]]
[[FILE:Metamorphosis_II_2.jpg|none|border|text-bottom|640px|link=http://www.mcescher.com/Gallery/gallery-recogn.htm]]
[[Arts#Escher|M. C. Escher]], [https://en.wikipedia.org/wiki/Metamorphosis Metamorphosis] III, 1967-1968 <ref>[http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref>
=Initialization=
At program initialization, we generate an [[Array|array]] of [[Pseudorandom Number Generator|pseudorandom numbers]] <ref>[http://www.random.org/integers/?mode=advanced RANDOM.ORG - Integer Generator]</ref> <ref>[http://www.stat.fsu.edu/pub/diehard/ The Marsaglia Random Number CDROM including the Diehard Battery of Tests] by [[Mathematician#GMarsaglia|George Marsaglia]]</ref>:
* One number for each [[Pieces|piece]] at each [[Squares|square]]
* One number to indicate the [[Side to move|side to move]] is black
* Four numbers to indicate the [[Castling rights|castling rights]], though usually 16 (2^4) are used for speed
* Eight numbers to indicate the [[Files|file]] of a valid [[En passant]] square, if any
This leaves us with an array with 781 (12*64 + 1 + 4 + 8) random numbers. Since pawns don't happen on first and eighth rank, one might be fine with 12*64 though. There are even proposals and implementations to use overlapping keys from unaligned access up to an array of only 12 numbers for every piece and to rotate that number by square <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=245932&t=26152 Re: Zobrist key random numbers] by [[Zach Wegner]], [[CCC]], January 22, 2009</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30008 Overlapped Zobrist keys array] by [[Stefano Gemma]], [[CCC]], October 06, 2009</ref> .
Programs usually implement their own [[Pseudorandom Number Generator|Pseudorandom number generator]] (PRNG), both for better quality random numbers than standard library functions, and also for reproducibility. This means that whatever platform the program is run on, it will use the exact same set of Zobrist keys. This is also useful for things like opening books, where the positions in the book can be stored by hash key and be used portably across machines, considering [[Endianness|endianness]].
=Runtime=
If we now want to get the Zobrist hash code of a certain position, we initialize the hash key by [[General Setwise Operations#ExclusiveOr|xoring]] all random numbers linked to the given feature, e.g. the [[Initial Position|initial position]]:
<pre>
[Hash for White Rook on a1] xor [Hash for White Knight on b1] xor [Hash for White Bishop on c1] xor ... ( all pieces )
... xor [Hash for White king castling] xor [Hash for White queeb castling] xor ... ( all castling rights )
</pre>
The fact that xor-operation is [https://en.wikipedia.org/wiki/Involution own inverse] and can be undone by using the same xor-operation again, is often used by chess engines. It allows a fast [[Incremental Updates|incremental update]] of the hash key during [[Make Move|make]] or [[Unmake Move|unmake]] [[Moves|moves]]. E.g., for a White Knight that jumps from b1 to c3 capturing a Black Bishop, these operations are performed:
<pre>
[Original Hash of position] xor [Hash for White Knight on b1] ... ( removing the knight from b1 )
... xor [Hash for Black Bishop on c3] ( removing the captured bishop from c3 )
... xor [Hash for White Knight on c3] ( placing the knight on the new square )
... xor [Hash for Black to move] ( change sides)
</pre>
=Collisions=
[[Transposition Table#KeyCollisions|Key collisions]] or type-1 errors are inherent in using Zobrist keys with far less bits than required to encode all reachable chess positions.
==Theory==
An important issue is the question of what size the hash keys should have. Smaller hash keys are faster and more space efficient, while larger ones reduce the risk of a hash collision. A collision occurs if two positions map the same key <ref>[https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004</ref> . The dangers of which were well assessed by [[Robert Hyatt]] and [[Anthony Cozzie]] in their 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>. Usually 64bit are used as a standard size in modern chess programs.
Hash collisions demonstrate the [https://en.wikipedia.org/wiki/Birthday_problem birthday "paradox"], which is to say the chance of collisions approaches certainty at around the '''square root''' of the number of possible keys, contrary to some people's expectations. You can expect to encounter a collision in a 32 bit hash when you have evaluated sqrt(2 ^ 32) == 2 ^ 16 or around 65 thousand positions. With a 64 bit hash, you can expect a collision after about 2 ^ 32 or 4 billion positions.
==Praxis==
Post by [[Jonathan Schaeffer]] <ref>[https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/9zrP0flwuzAJ Re: Hash tables - Clash!!! What happens next?] by [[Jonathan Schaeffer]], March 17, 1994</ref> :
... I can speak from experience here. In the early versions of my chess program [[Phoenix]], I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the random numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were '''lots''' of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error. All randomly generated numbers are not the same!
==Lack a True Integer Type==
<span id="LackInt"></span>Some languages (such as [[JavaScript]] and [https://en.wikipedia.org/wiki/Lua_%28programming_language%29 Lua]) only have a [[Double|64-bit floating point]] "Number" type. In JavaScript, this type breaks down into a 32 bit integer when bitwise operators are used. One way to get a 64 bit hash is to use two 32 bit numbers in parallel, as [[Garbochess-JS]] <ref>[http://forwardcoding.com/projects/ajaxchess/chess.html Garbochess-JS]</ref> does. Another, which [[p4wn]] used at one stage, is to use 47 or 48 bit '''additive''' hashes. 64 bit floating point numbers are true integers up to 53 bits, so it is possible to sum at least 32 (and on average close to 64) random 48 bit numbers, which was enough for p4wn's purposes. For additive Zobrist hashing, you add the number when placing a piece and subtract it when removing it, rather than using xor both ways. There is no difference in accuracy or speed, and 48 bit hashes give you collisions at around the 2 ^ 24 or 16 million point.
==Linear Independence==
The minimum and average [[Population Count#HammingDistance|Hamming Distance]] over all Zobrist keys was often considered as "quality"-measure of the keys. However, maximizing the minimal hamming distance leads to very poor Zobrist keys. As long the minimum hamming distance is greater zero, [https://en.wikipedia.org/wiki/Linear_independence linear independence] (that is a small subset of all keys doesn't xor to zero), is much more important than hamming distance as explained by [[Sven Reichard]] <ref>[https://www.stmintz.com/ccc/index.php?id=200622 Re: About random numbers and hashing] by [[Sven Reichard]], [[CCC]], December 05, 2001</ref> :
{|
|-
| Assume we associate a bitstring to every piece-square combination. That is what's usually done in chess programs; some codes are added for the side to move, castling rights, e.p. squares, etc. We obtain the code of a position by xor-ing the codes of all the pieces contained in it.
What we want to avoid is collisions at nodes close to the root. For nodes close to the leaves the cost of recomputing the score is smaller. Hence we want to avoid that:
<pre>
x1^x2^...^xm = y1^y2^...^yn
for codes xi, yi and small number m and n, and xi not equal to yj
</pre>
To translate that to a language that is more familiar - at least for people of a mathematical background - we consider the [https://en.wikipedia.org/wiki/Field_%28mathematics%29#Finite_fields field F2] of two elements. The elements are 0 and 1, and we can add and multiply them as usual, with the additional rule that 1 + 1 = 0. This is really a field, just like the [https://en.wikipedia.org/wiki/Real_number real] or [https://en.wikipedia.org/wiki/Complex_number complex numbers], and we can do calculations as usual. Note that addition is just the exclusive or.
Now the codes or bitstrings become [https://en.wikipedia.org/wiki/Vector_%28mathematics_and_physics%29 vectors] over the field F2, and the bitwise exclusive or becomes componentwise addition, i.e., usual addition of vectors. All these vectors form the [https://en.wikipedia.org/wiki/Vector_space vector space] F2^k, where k is the length of the vectors. Typically, k = 64.
So, what we want to avoid is an equation
<pre>
x1 + x2 + ... + xm = y1 + y2 + ... + yn
</pre>
or
<pre>
x1 + x2 + ... + xm + y1 + y2 + ... + yn = 0
</pre>
since in F2, subtraction is the same as addition. Remembering some [https://en.wikipedia.org/wiki/Linear_algebra linear algebra], this just means that we want the set x1,...,xm,y1,...,yn to be linearly independent.
This leads to the following criterion for picking a set of hashcodes: A set of vectors in F2^k is a good set of hash codes if each small subset of non-zero vectors is linearly independent. What is not clear here is the meaning of "small", but we want small to be as big as possible. In other words, we consider sets of size up to a certain size as small, and if we can make that size bigger, it is better, since this leads to unique codes deeper in the tree.
However what is clear is that this quality criterion does not depend on the base of the vector space. I.e., if we have a good set and multiply each vector by an invertible matrix (in other words, if we rotate the vectors), the obtained set will be just as good, since the rotation does not change the linear independence. The Hamming distance, on the other hand, is highly dependent on the vector space base. Take for example the vectors (1,0) and (0,1) in F2^2; they have Hamming distance 2. If we multiply both of them by
<pre>
(1 1)
(0 1)
</pre>
we get (1,1) and (0,1), which have Hamming distance 1. Actually we can change any distance to anything else (except for 0) by an appropriate matrix. Thus we try to approximate something that is independent from the base (the quality of our hash codes) by something that depends on it (the Hamming distance). Simple logic tells you that this approximation has to be real bad. An example where it doesn't work: It has been said that the Hamming distance shouldn't be to small or to big. So, vectors at a distance which is half the length should be ok, right? Let the length be 8 (I don't want to type too many 0's and 1's), and consider the vectors
<pre>
11110000
11001100
00111100
</pre>
They all have weight 4, their pairwise distance is 4, and yet they add up to 0. Just by looking at Hamming distances, you have no chance of detecting that.
Summarizing I can say that I see no connection between the quality of hash codes and their Hamming distance. Using a good RNG like the one provided in GNU's stdlib will yield good hash codes ( you can actually prove that), and so I will take the codes as they are supplied by rand() or random() without messing with them and thereby most likely make them worse.
|}
=See also=
* [[CPW-Engine_transposition]]
* [[BCH Hashing]]
=Publications=
* [[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]
* [[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28., No. 3]]
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Viljem Žumer]] ('''2005'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1491153 The Representation of Chess Game]''. Proceedings of the 27th International Conference on Information Technology Interfaces
* [[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]
=Forum Posts=
==1982 ...==
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982
==1990 ...==
* [https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/Jq7rYE0vqtoJ Hash tables - Clash!!! What happens next?] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgc]], March 15, 1994
: [https://groups.google.com/d/msg/rec.games.chess/h9Q2wik_kTg/9zrP0flwuzAJ Re: Hash tables - Clash!!! What happens next?] by [[Jonathan Schaeffer]], March 17, 1994
* [https://groups.google.com/d/msg/rec.games.chess.computer/C53jRusegwA/XzgyZLbzcn8J Collision probability] by [[Dennis Breuker]], [[Computer Chess Forums|rgcc]], April 15, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/JZ-_0rObjuQ/Mfwy9qBLxoAJ Re: Berliner vs. Botvinnik Some interesting points] by [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Computer Chess Forums|rgcc]], November 6, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/oKgv-7WbfO0/TH-p0KUIo2kJ Re: Hashing function for board positions]by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=29817 How to create a set of random integers for hashing?] by [[Ed Schroder|Ed Schröder]], [[CCC]], October 18, 1998
==2000 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/587d039679461fb8 Why Random Number Needed In HashFunction[piece][position]] by Cheok Yan Cheng, [[Computer Chess Forums|rgcc]], June 12, 2001
* [https://www.stmintz.com/ccc/index.php?id=200366 About random numbers and hashing] by [[Severi Salminen]], [[CCC]], December 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=245775 Random keys and hamming distance] by [[James Swafford]], [[CCC]], August 16, 2002
* [https://www.stmintz.com/ccc/index.php?id=313807 Hamming distance and lower hash table indexing] by [[Tom Likens]], [[CCC]], September 02, 2003
* [https://www.stmintz.com/ccc/index.php?id=324223 64-Bit random numbers] by [[Martin Schreiber]], [[CCC]], October 28, 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
* [https://www.stmintz.com/ccc/index.php?id=358836 Hashkey collisions (typical numbers)] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 07, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=26152 Zobrist key random numbers] by [[Robert Hyatt]], [[CCC]], January 21, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=28523 Incremental Zobrist - slow?] by [[Vlad Stamate]], [[CCC]], June 20, 2009 » [[Incremental Updates]]
* [http://talkchess.com/forum/viewtopic.php?t=28545 On Zobrist keys] by [[Lasse Hansen]], [[CCC]], June 21, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30008 Overlapped Zobrist keys array] by [[Stefano Gemma]], [[CCC]], October 06, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35415 Transposition table random numbers] by Justin Madru, [[CCC]], July 13, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40062 TT Key Collisions, Workarounds?] by [[Clemens Pruell]], [[CCC]], August 16, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40849 Key collision handling] by [[Jonatan Pettersson]], [[CCC]], October 21, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1872 Using a Transposition Table with Zobrist Keys] by Miyagi403, [[Computer Chess Forums|OpenChess Forum]], February 21, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43910 MT or KISS ?] by [[Dan Honeycutt]], [[CCC]], June 02, 2012 <ref>[https://en.wikipedia.org/wiki/Mersenne_twister Mersenne twister from Wikipedia]</ref> <ref>[http://compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519 64-bit KISS RNGs] by [[Mathematician#GMarsaglia|George Marsaglia]], [http://compgroups.net/comp.lang.fortran/ comp.lang.fortran | Computer Group], February 28, 2009</ref> <ref>[[Bob Jenkins#RKISS|RKISS]] by [[Bob Jenkins]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=44043 Zobrist alternative?] by [[Harm Geert Muller]], [[CCC]], June 12, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45605 Zobrist Number Statistics and WHat to Look For] by Andrew Templeton, [[CCC]], October 16, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2178 Question about Zobrist code] by Hamfer, [[Computer Chess Forums|OpenChess Forum]], December 19, 2012
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55449 Zobrist keys - measure of quality?] by [[Martin Sedlak]], [[CCC]], February 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=58890&start=13 Re: On-the fly hash key generation?] by [[Aleks Peshkov]], [[CCC]], January 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61411 Rotated hash] by [[J. Wesley Cleveland]], [[CCC]], September 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61533 No Zobrist key] by [[Henk van den Belt]], [[CCC]], September 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62733 Enpass + Castling for Zorbist hashes] by [[Andrew Grant]], [[CCC]], January 06, 2017 » [[Castling rights]], [[En passant]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66372 Zobrist hashing for text] by [[Alvaro Cardoso]], [[CCC]], January 20, 2018
=External Links=
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]
* [http://web.archive.org/web/20070810003508/www.seanet.com/%7Ebrucemo/topics/zobrist.htm Zobrist keys] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070811182741/www.seanet.com/%7Ebrucemo/topics/topics.htm Programming Topics]
* [http://mediocrechess.blogspot.com/2007/01/guide-zobrist-keys.html Zobrist keys] from [http://mediocrechess.blogspot.com/ Mediocre Chess] by [[Jonatan Pettersson]]
* [https://en.wikipedia.org/wiki/G%C3%B6del_numbering Gödel numbering from Wikipedia]
* [[Arts#Cage|John Cage]] - [https://en.wikipedia.org/wiki/Music_of_Changes Music of Changes], Book 1 (1951), performed by [https://www.facebook.com/vickychowpianist Vicky Chow], [https://www.facebook.com/DiMennaCenter DiMenna Center], [https://en.wikipedia.org/wiki/New_York_City NYC], June 09, 2012, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=Y7LD1iTl-lM|alignment=left|valignment=top}}
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
[[Category:M. C. Escher]][[Category:John Cage]]
