BCH Hashing,
a fast incrementalHash function to transform a board position into a number of a set length, quite similar to Zobrist Hashing. It was proposed by Tony Warnock and Burton Wendroff in 1988 ^{[1]}, relying on BCH codes invented by Alexis Hocquenghem in 1959 ^{[2]}, and independently by Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri in 1960 ^{[3]}. 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 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 ^{[4]}, and refers Elwyn Berlekamp'sAlgebraic Coding Theory^{[5]} .

The following paper describes a method of generating the numbers for a hash table. By using 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 random set of numbers.

MacWilliams and Sloane's book on error correcting codes^{[9]}has the glory details about the theory and programming.

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 University of New Mexico. Those people had 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.

Home * Search * Transposition Table * BCH HashingBCH Hashing,a fast incremental Hash function to transform a board position into a number of a set length, quite similar to Zobrist Hashing. It was proposed by Tony Warnock and Burton Wendroff in 1988

^{[1]}, relying on BCH codes invented by Alexis Hocquenghem in 1959^{[2]}, and independently by Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri in 1960^{[3]}. 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 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^{[4]}, and refers Elwyn Berlekamp'sAlgebraic Coding Theory^{[5]}.^{[6]}## Table of Contents

## Quotes

## Tony Warnock

onSearch Tables in Computer Chess^{[7]}^{[8]}:The following paper describes a method of generating the numbers for a hash table. By using 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 random set of numbers.MacWilliams and Sloane's book on error correcting codes^{[9]}has the glory details about the theory and programming.## Kathe and Dan Spracklen

excerpt from theirOral History^{[10]}: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 University of New Mexico. Those people had 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

## Publications

1959).Codes correcteurs d'erreurs. Chiffres, Paris 2, pp. 147–156 (French)1960).On A Class of Error Correcting Binary Group Codes. Information and Control Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, pdf1968).Algebraic Coding Theory. New York: McGraw-Hill. Revised ed., Aegean Park Press, (1984), ISBN 0894120638. amazon^{[11]}1981).The Theory of Error-Correcting Codes. North-Holland Mathematical Library, amazon1988).Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 11993).Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf1995).Programmes d'Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d'Évaluations, Parallélisme de Recherche. Ph.D. Thesis. Université Paris 8, Saint-Denis, zipped ps (French)^{[12]}2004).Using the BCH construction to generate robust linear hash functions. Information Theory Workshop, 2004. IEEE## Postings

## External Links

GF(2) from Wikipedia

## References

1988).Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 11959).Codes correcteurs d'erreurs. Chiffres, Paris 2, pp. 147–156 (French)1960).On A Class of Error Correcting Binary Group Codes. Information and Control Vol. 3, No. 1, pp. 68–79, ISSN 0890-5401, pdf1993).Game Tree Search on Massively Parallel Systems. Ph.D. Thesis, pdf, BCH Codes at page 22 and page 145 (Appendix A)1968).Algebraic Coding Theory. New York: McGraw-Hill. Revised ed., Aegean Park Press, (1984), ISBN 0894120638. amazon1988).Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 11981).The Theory of Error-Correcting Codes. North-Holland Mathematical Library, amazon2005).Oral History of Kathe and Dan Spracklen. pdf from The Computer History Museum## What links here?

Up one Level