Author: Thomas Mayer
Date: 23:55:20 09/23/01
Go up one level in this thread
Hi Heiner, >>I don't know how much slower it is, but I maintain another number also for the >>index, the bigger the hashtable the bigger it is. I'm a bit surprised by your >>question because it is even more natural doing this way, and the other way is >>the one that looks like a trick. > >Huh, now *I* am a bit surprised. > >The natural/normal way to proceed is: >(1) Map the complete board into a single hash value (HV). > The HV usually is 64 bit wide. > With the Zobrist hash algorithm this value can be maintained incrementally, > and need not be recomputed from scratch. >(2) From the HV compute an index into the hash table (HI = hash index). > Basically a hash table is an array of some fixed size, say N. > HI is a value between 0 and HI-1. Mostly we do: HI = HV % N; > If N is a power of two, the mod operation can be replaced by masking > log2(N) low bits from HV: HI = HV & mask; >(3) Try to find the searched for info in hash_table[HI], first. >(4) If that hash table slot is filled with other data, we may decide to > search some more slots. Many different ways to do this. > >Mostly, the HV is stored into the hash table entries. >Since part of the HV has already been used to select the entry, one may >try to reduce the stored value to the not yet used part of HV. well, I am doing it quite similar to Antonio I think, I have two 32 bit variables... One is the HashKey and the next one is the HashIndex with which I compute the index in the table with &... Stored is only the HashKey in the table. In the book I've read first about how to do hashtables it was explained that way... I have tried once to change this to a single 64 bit variable, but it was slightly a bit slower - the comparison of 64 bit variables seems to be to slow on current x86-compatibel processors... Since I store also EP-information and castling rights in the HashKey and HashIndex I have never seen a colission anymore... You can say, that is something like a 48 bit - hashkey... When I have only 65536 positions in hash... usually more then a million, the used hashkey size grows with the size of the table... Greets, Thomas
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.