25,161
edits
Changes
Created page with "'''Home * Search * Transposition Table * BCH Hashing''' FILE:Metamorphosis_of_Narcissus.jpg|border|right|thumb|link=http://en.wikipedia.org/wiki/Metam..."
'''[[Main Page|Home]] * [[Search]] * [[Transposition Table]] * BCH Hashing'''
[[FILE:Metamorphosis_of_Narcissus.jpg|border|right|thumb|link=http://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus| [[Arts#Dali|Salvador Dalí]] - [https://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus Metamorphosis of Narcissus], 1937 <ref>[https://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus Metamorphosis of Narcissus from Wikipedia]</ref> ]]
'''BCH Hashing''',<br/>
a fast [[Incremental Updates|incremental]] [https://en.wikipedia.org/wiki/Hash_function Hash function] to transform a board [[Chess Position|position]] into a number of a set length, quite similar to [[Zobrist Hashing]]. It was proposed by [[Tony Warnock]] and [[Burton Wendroff]] in 1988 <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref>, relying on [https://en.wikipedia.org/wiki/BCH_code BCH codes] invented by [[Mathematician#Hocquenghem|Alexis Hocquenghem]] in 1959 <ref>[[Mathematician#Hocquenghem|Alexis Hocquenghem]] ('''1959'''). ''Codes correcteurs d'erreurs''. Chiffres, Paris 2, pp. 147–156 (French)</ref>, and independently by [[Mathematician#RCBose|Raj Chandra Bose]] and [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] in 1960 <ref>[[Mathematician#RCBose|Raj Chandra Bose]], [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] ('''1960'''). ''On A Class of Error Correcting Binary Group Codes''. [https://en.wikipedia.org/wiki/Information_and_Computation Information and Control] Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, [http://kom.aau.dk/~heb/kurser/NOTER/KOFA03.PDF pdf]</ref>. They used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (64*12 - 2*2*8 + 4 + 8 + 1) bits, which is sufficient to avoid [[Transposition Table#KeyCollisions|collisions]] within an 8 ply search. They stored 63 bits of the BCH signature as "lock" inside the table, and used 18 (or more) lower bits as index. [[Rainer Feldmann]] elaborates on BCH codes inside his thesis as well <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/BCH_Code BCH Codes] at page 22 and page 145 (Appendix A)</ref>, and refers [[Elwyn Berlekamp|Elwyn Berlekamp's]] ''Algebraic Coding Theory'' <ref>[[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory''. New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon]</ref> .
=Quotes=
==[[Tony Warnock]]==
on ''Search Tables in Computer Chess'' <ref>[https://groups.google.com/group/rec.games.chess/msg/2a4183cb654443dc?hl=en Re: Hash tables----Clash!!!-What happens next?] by [[Tony Warnock]], [[Computer Chess Forums|rgcc]], March 17, 1994</ref> <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref>:
The following paper describes a method of generating the numbers for a hash table. By using [https://en.wikipedia.org/wiki/Error_detection_and_correction error correcting codes], we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a [[Pseudorandom number generator|random set of numbers]].
[[Mathematician#JMacWilliam|MacWilliams]] and [[Mathematician#NSloane|Sloane's]] book on error correcting codes <ref>[[Mathematician#JMacWilliam|Jessie MacWilliams]], [[Mathematician#NSloane|Neil Sloane]] ('''1981'''). ''[http://www.sciencedirect.com/science/bookseries/09246509/16 The Theory of Error-Correcting Codes]''. North-Holland Mathematical Library, [http://www.amazon.com/Theory-Error-Correcting-North-Holland-Mathematical-Library/dp/0444851933 amazon]</ref> has the glory details about the theory and programming.
==[[Kathe Spracklen|Kathe]] and [[Dan Spracklen]]==
excerpt from their ''Oral History'' <ref>[http://www.computerhistory.org/trustee/gardner-hendrie Gardner Hendrie] ('''2005'''). ''Oral History of Kathe and Dan Spracklen''. [http://archive.computerhistory.org/projects/chess/related_materials/oral-history/spacklen.oral_history.2005.102630821/spracklen.oral_history_transcript.2005.102630821.pdf pdf] from [[The Computer History Museum]]</ref> :
Well, first explain what a hash table is... You want to spread your positions out over a large data area so you need random numbers that will distribute a Chess position over, you know, a lot of different, you know, memory maps or memory locations.
So BCH random numbers were something that some people had developed at the [https://en.wikipedia.org/wiki/University_of_New_Mexico University of New Mexico]. Those people had [[Lachex|a Chess program]]. They wrote an article on it and ... I think it's three different people that developed it. Anyway, it's a coding scheme that gives the maximal distance between... Bit adjacent numbers so that you spread your positions over - more uniformly over the hash table area. They don't tend to bunch up as much that way.
So, anyway, they wrote an article on how to do that and I had - in fact, I even got the book that they recommended and read it and figured it out how to do it because they didn't really tell you how to do it. They just said that they were using them and they were... So I tried it and, sure enough, they worked a lot better than the old method of getting random numbers.
=See also=
* [[Hash Table]]
* [[Zobrist Hashing]]
=Publications=
* [[Mathematician#Hocquenghem|Alexis Hocquenghem]] ('''1959'''). ''Codes correcteurs d'erreurs''. Chiffres, Paris 2, pp. 147–156 (French)
* [[Mathematician#RCBose|Raj Chandra Bose]], [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] ('''1960'''). ''On A Class of Error Correcting Binary Group Codes''. [https://en.wikipedia.org/wiki/Information_and_Computation Information and Control] Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, [http://kom.aau.dk/~heb/kurser/NOTER/KOFA03.PDF pdf]
* [[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory''. New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon] <ref>[http://www.cse.buffalo.edu/~atri/courses/coding-theory/ CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications] by [http://www.cse.buffalo.edu/~atri/ Atri Rudra]</ref>
* [[Mathematician#JMacWilliam|Jessie MacWilliams]], [[Mathematician#NSloane|Neil Sloane]] ('''1981'''). ''[http://www.sciencedirect.com/science/bookseries/09246509/16 The Theory of Error-Correcting Codes]''. North-Holland Mathematical Library, [http://www.amazon.com/Theory-Error-Correcting-North-Holland-Mathematical-Library/dp/0444851933 amazon]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis
* [[Jean-Christophe Weill]] ('''1995'''). ''Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche''. Ph.D. Thesis. [[University of Paris#8|Université Paris 8]], Saint-Denis, [http://www.recherche.enac.fr/%7Eweill/publications/phdJCW.ps.gz zipped ps] (French) <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30008&start=11 Re: Overlapped Zobrist keys array] by [[Rémi Coulom]], [[CCC]], October 06, 2009</ref>
* [[J. P. Grossman]], [http://www.linkedin.com/in/ljakab Levente Jakab] ('''2004'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1405309 Using the BCH construction to generate robust linear hash functions]''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=9641 Information Theory Workshop, 2004. IEEE]
=Postings=
* [https://groups.google.com/group/rec.games.chess/msg/2a4183cb654443dc?hl=en Re: Hash tables----Clash!!!-What happens next?] by [[Tony Warnock]], [[Computer Chess Forums|rgcc]], March 17, 1994
* [https://groups.google.com/d/msg/rec.games.chess.computer/0sIKY_dfLUs/aMlLOXkDJJsJ Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997
* [http://www.science-bbs.com/121-math/3da76fc0fd4785b9.htm#.UdMt06wXl8E How gracefully do BCH codes degrade] by Eb Oesch, [http://www.science-bbs.com/viewforum/121-math/1796.htm Science Forum, math], May 20, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=30008&start=11 Re: Overlapped Zobrist keys array] by [[Rémi Coulom]], [[CCC]], October 06, 2009
=External Links=
* [https://en.wikipedia.org/wiki/BCH_code BCH codes from Wikipedia]
* [https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm Berlekamp–Massey algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm Berlekamp–Welch algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Coding_theory Coding theory from Wikipedia]
* [http://www.youtube.com/course?list=EC5002EB7306694E7D Coding Theory] by [http://www.ee.iitm.ac.in/~andrew/ Andrew Thangaraj], Department of Electronics & Communication Engineering, [https://en.wikipedia.org/wiki/Indian_Institute_of_Technology_Madras Indian Institute of Technology Madras], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
* [https://en.wikipedia.org/wiki/Cyclic_code Cyclic code from Wikipedia]
* [https://en.wikipedia.org/wiki/Error_detection_and_correction Error detection and correction from Wikipedia]
* [https://en.wikipedia.org/wiki/Finite_field Finite field from Wikipedia]
: [https://en.wikipedia.org/wiki/GF%282%29 GF(2) from Wikipedia]
* [https://en.wikipedia.org/wiki/Forward_error_correction Forward error correction from Wikipedia]
* [http://mint.sbg.ac.at/desc_CCyclic-BCHBound.html MinT - Cyclic Codes (BCH-Bound)]
* [https://en.wikipedia.org/wiki/Root_of_unity_modulo_n Root of unity modulo n from Wikipedia]
* [[Videos#HuxFlux|Hux Flux]] - Calculus, [https://en.wikipedia.org/wiki/Hux_Flux#Albums Cryptic Crunch], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=zqxOJptzkcQ|alignment=left|valignment=top}}
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
[[FILE:Metamorphosis_of_Narcissus.jpg|border|right|thumb|link=http://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus| [[Arts#Dali|Salvador Dalí]] - [https://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus Metamorphosis of Narcissus], 1937 <ref>[https://en.wikipedia.org/wiki/Metamorphosis_of_Narcissus Metamorphosis of Narcissus from Wikipedia]</ref> ]]
'''BCH Hashing''',<br/>
a fast [[Incremental Updates|incremental]] [https://en.wikipedia.org/wiki/Hash_function Hash function] to transform a board [[Chess Position|position]] into a number of a set length, quite similar to [[Zobrist Hashing]]. It was proposed by [[Tony Warnock]] and [[Burton Wendroff]] in 1988 <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref>, relying on [https://en.wikipedia.org/wiki/BCH_code BCH codes] invented by [[Mathematician#Hocquenghem|Alexis Hocquenghem]] in 1959 <ref>[[Mathematician#Hocquenghem|Alexis Hocquenghem]] ('''1959'''). ''Codes correcteurs d'erreurs''. Chiffres, Paris 2, pp. 147–156 (French)</ref>, and independently by [[Mathematician#RCBose|Raj Chandra Bose]] and [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] in 1960 <ref>[[Mathematician#RCBose|Raj Chandra Bose]], [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] ('''1960'''). ''On A Class of Error Correcting Binary Group Codes''. [https://en.wikipedia.org/wiki/Information_and_Computation Information and Control] Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, [http://kom.aau.dk/~heb/kurser/NOTER/KOFA03.PDF pdf]</ref>. They used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (64*12 - 2*2*8 + 4 + 8 + 1) bits, which is sufficient to avoid [[Transposition Table#KeyCollisions|collisions]] within an 8 ply search. They stored 63 bits of the BCH signature as "lock" inside the table, and used 18 (or more) lower bits as index. [[Rainer Feldmann]] elaborates on BCH codes inside his thesis as well <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis, [https://en.wikipedia.org/wiki/BCH_Code BCH Codes] at page 22 and page 145 (Appendix A)</ref>, and refers [[Elwyn Berlekamp|Elwyn Berlekamp's]] ''Algebraic Coding Theory'' <ref>[[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory''. New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon]</ref> .
=Quotes=
==[[Tony Warnock]]==
on ''Search Tables in Computer Chess'' <ref>[https://groups.google.com/group/rec.games.chess/msg/2a4183cb654443dc?hl=en Re: Hash tables----Clash!!!-What happens next?] by [[Tony Warnock]], [[Computer Chess Forums|rgcc]], March 17, 1994</ref> <ref>[[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]</ref>:
The following paper describes a method of generating the numbers for a hash table. By using [https://en.wikipedia.org/wiki/Error_detection_and_correction error correcting codes], we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a [[Pseudorandom number generator|random set of numbers]].
[[Mathematician#JMacWilliam|MacWilliams]] and [[Mathematician#NSloane|Sloane's]] book on error correcting codes <ref>[[Mathematician#JMacWilliam|Jessie MacWilliams]], [[Mathematician#NSloane|Neil Sloane]] ('''1981'''). ''[http://www.sciencedirect.com/science/bookseries/09246509/16 The Theory of Error-Correcting Codes]''. North-Holland Mathematical Library, [http://www.amazon.com/Theory-Error-Correcting-North-Holland-Mathematical-Library/dp/0444851933 amazon]</ref> has the glory details about the theory and programming.
==[[Kathe Spracklen|Kathe]] and [[Dan Spracklen]]==
excerpt from their ''Oral History'' <ref>[http://www.computerhistory.org/trustee/gardner-hendrie Gardner Hendrie] ('''2005'''). ''Oral History of Kathe and Dan Spracklen''. [http://archive.computerhistory.org/projects/chess/related_materials/oral-history/spacklen.oral_history.2005.102630821/spracklen.oral_history_transcript.2005.102630821.pdf pdf] from [[The Computer History Museum]]</ref> :
Well, first explain what a hash table is... You want to spread your positions out over a large data area so you need random numbers that will distribute a Chess position over, you know, a lot of different, you know, memory maps or memory locations.
So BCH random numbers were something that some people had developed at the [https://en.wikipedia.org/wiki/University_of_New_Mexico University of New Mexico]. Those people had [[Lachex|a Chess program]]. They wrote an article on it and ... I think it's three different people that developed it. Anyway, it's a coding scheme that gives the maximal distance between... Bit adjacent numbers so that you spread your positions over - more uniformly over the hash table area. They don't tend to bunch up as much that way.
So, anyway, they wrote an article on how to do that and I had - in fact, I even got the book that they recommended and read it and figured it out how to do it because they didn't really tell you how to do it. They just said that they were using them and they were... So I tried it and, sure enough, they worked a lot better than the old method of getting random numbers.
=See also=
* [[Hash Table]]
* [[Zobrist Hashing]]
=Publications=
* [[Mathematician#Hocquenghem|Alexis Hocquenghem]] ('''1959'''). ''Codes correcteurs d'erreurs''. Chiffres, Paris 2, pp. 147–156 (French)
* [[Mathematician#RCBose|Raj Chandra Bose]], [[Mathematician#RayChaudhuri|Dwijendra Kumar Ray-Chaudhuri]] ('''1960'''). ''On A Class of Error Correcting Binary Group Codes''. [https://en.wikipedia.org/wiki/Information_and_Computation Information and Control] Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, [http://kom.aau.dk/~heb/kurser/NOTER/KOFA03.PDF pdf]
* [[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory''. New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon] <ref>[http://www.cse.buffalo.edu/~atri/courses/coding-theory/ CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications] by [http://www.cse.buffalo.edu/~atri/ Atri Rudra]</ref>
* [[Mathematician#JMacWilliam|Jessie MacWilliams]], [[Mathematician#NSloane|Neil Sloane]] ('''1981'''). ''[http://www.sciencedirect.com/science/bookseries/09246509/16 The Theory of Error-Correcting Codes]''. North-Holland Mathematical Library, [http://www.amazon.com/Theory-Error-Correcting-North-Holland-Mathematical-Library/dp/0444851933 amazon]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems''. Ph.D. Thesis
* [[Jean-Christophe Weill]] ('''1995'''). ''Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche''. Ph.D. Thesis. [[University of Paris#8|Université Paris 8]], Saint-Denis, [http://www.recherche.enac.fr/%7Eweill/publications/phdJCW.ps.gz zipped ps] (French) <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30008&start=11 Re: Overlapped Zobrist keys array] by [[Rémi Coulom]], [[CCC]], October 06, 2009</ref>
* [[J. P. Grossman]], [http://www.linkedin.com/in/ljakab Levente Jakab] ('''2004'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1405309 Using the BCH construction to generate robust linear hash functions]''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=9641 Information Theory Workshop, 2004. IEEE]
=Postings=
* [https://groups.google.com/group/rec.games.chess/msg/2a4183cb654443dc?hl=en Re: Hash tables----Clash!!!-What happens next?] by [[Tony Warnock]], [[Computer Chess Forums|rgcc]], March 17, 1994
* [https://groups.google.com/d/msg/rec.games.chess.computer/0sIKY_dfLUs/aMlLOXkDJJsJ Re: Hash functions for use with a transition table] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], March 7, 1997
* [http://www.science-bbs.com/121-math/3da76fc0fd4785b9.htm#.UdMt06wXl8E How gracefully do BCH codes degrade] by Eb Oesch, [http://www.science-bbs.com/viewforum/121-math/1796.htm Science Forum, math], May 20, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=30008&start=11 Re: Overlapped Zobrist keys array] by [[Rémi Coulom]], [[CCC]], October 06, 2009
=External Links=
* [https://en.wikipedia.org/wiki/BCH_code BCH codes from Wikipedia]
* [https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm Berlekamp–Massey algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm Berlekamp–Welch algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Coding_theory Coding theory from Wikipedia]
* [http://www.youtube.com/course?list=EC5002EB7306694E7D Coding Theory] by [http://www.ee.iitm.ac.in/~andrew/ Andrew Thangaraj], Department of Electronics & Communication Engineering, [https://en.wikipedia.org/wiki/Indian_Institute_of_Technology_Madras Indian Institute of Technology Madras], [https://en.wikipedia.org/wiki/YouTube YouTube] Videos
* [https://en.wikipedia.org/wiki/Cyclic_code Cyclic code from Wikipedia]
* [https://en.wikipedia.org/wiki/Error_detection_and_correction Error detection and correction from Wikipedia]
* [https://en.wikipedia.org/wiki/Finite_field Finite field from Wikipedia]
: [https://en.wikipedia.org/wiki/GF%282%29 GF(2) from Wikipedia]
* [https://en.wikipedia.org/wiki/Forward_error_correction Forward error correction from Wikipedia]
* [http://mint.sbg.ac.at/desc_CCyclic-BCHBound.html MinT - Cyclic Codes (BCH-Bound)]
* [https://en.wikipedia.org/wiki/Root_of_unity_modulo_n Root of unity modulo n from Wikipedia]
* [[Videos#HuxFlux|Hux Flux]] - Calculus, [https://en.wikipedia.org/wiki/Hux_Flux#Albums Cryptic Crunch], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=zqxOJptzkcQ|alignment=left|valignment=top}}
=References=
<references />
'''[[Transposition Table|Up one Level]]'''
