Author: Bruce Moreland
Date: 17:24:58 01/20/00
Go up one level in this thread
On January 20, 2000 at 17:52:11, Sanjiv Karnataki wrote: >Hi All, > >I would like to learn a little more about the hashing algorithms used esp. for >transposition tables. I have found references to A.L. Zobrist's paper, but no >link to this. > >Any information, as always, is greatly appreciated and thank you in advance. > >Sanjiv. > >P.S. Based on past experience I expect to see several useful in answers in the >next 15-20 minutes... this site is great! Make an array of 64-bit ints. The array is declared as follows, assuming a recent version of Microsoft C++: __int64 hash_values[pcMAX][coMAX][sqMAX]; pcMAX is the number of different kinds of pieces, which is 6 (PNBRQK). coMAX is the number of colors, which is two (white, black). sqMAX is the number of squares on the board, which is 64 (a1..h8). Initialize this array with random gibberish. This is actually fairly hard because you can't just unthinkingly use "rand()", which only returns 15 bits of random gibberish. You have to figure out a way to get crap into all 64 bits, which you can do if you do some shifting. Now you make an __int64 hash key, I'll call it "hash", and set it to zero. Go through the board, and for each piece, XOR the appropriate "hash_values" array element into it. When you are done you have a nice 64-bit hunk of gibberish, which is the hash key. When you make a move, XOR out the "hash_values" value for where the piece that moved moved from, and XOR in the new value for where it moved to. If it captured, XOR out the captured piece. Do the right thing if it promoted, as well. When you "unmake" your move, do the same thing in reverse. Another part of the position is "side to move". You can deal with this by XOR'ing a gibberish constant in if it's black's turn to move, and then XOR'ing the same constant in every time you make or unmake a move. You also need to deal with changes in the castling flags, and the en-passant target square. You may only wish to XOR in en-passant target square info if an en-passant capture appears to be possible, otherwise you end up with a different hash key for 1. e4 e5 2. c4 than you do for 1. c4 e5 2. e4, and that's surprisingly inefficient. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.