Author: Vincent Diepeveen
Date: 15:58:18 09/24/01
Go up one level in this thread
On September 24, 2001 at 02:55:20, Thomas Mayer wrote: >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. If i understand well you only store 32 bits. So with a table of size 2^22 you store 32 bits and have another 22 bits for index. Total 22 + 32 = 54 bits. Now if you use 2 probes, then it's in fact 53 bits at most. If you hash the color instead of use another bit for that (and also not both hash it AND use another bit) then it's only 52 bits. That's asking for trouble! You should take care that you use effectively 62 or 63 at least! The problem is that 10 bits less doesn't mean that there is a 2^10 = 1024 times bigger chance to get a collission. Practical spoken the chance gets *way* bigger than 1024 times. I have seen many models on the chance that you get a collission, but most seem not exactly true. When i used 32 bits to store and 2^22 or something to lookup for hashtable in draughts i already simply saw it play WORSE moves actually! In fact a major bug happened because of that in the endgame (though there were still many pieces left on the board). A collission caused my program to draw a 3 versus 1 instead of exchange to a won 3 vs 1 (at that time there were no EGTBs yet in draughts). >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.