25,161
edits
Changes
no edit summary
'''[[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#:Category:John 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/>
[[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#:Category:M. C. 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=
* 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 rightsRights|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
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> :
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:
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=
* [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 rightsRights]], [[En passant]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66372 Zobrist hashing for text] by [[Alvaro Cardoso]], [[CCC]], January 20, 2018
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73110 Zobrist key independence] by [[Harm Geert Muller]], [[CCC]], February 17, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76508 Best practices for transposition tables] by Brian Adkins, [[CCC]], February 06, 2021
=External Links=
* [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#:Category:John 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}}
'''[[Transposition Table|Up one Level]]'''
[[Category:Schaeffer Quotes]][[Category:M. C. Escher]][[Category:John Cage]]
