Author: Dan Newman
Date: 20:56:06 09/21/98
Go up one level in this thread
On September 21, 1998 at 20:53:55, Dan Newman wrote: >On September 21, 1998 at 18:56:46, John Coffey wrote: > >>On September 21, 1998 at 18:12:36, Tom Kerrigan wrote: >> >>>Mostly correct, although maintaining two numbers to describe the position is >>>overkill. One 64 bit number should be enough. >>> >> >>Is one 64 bit number enough to uniquely identify a position? Does this >>prevent two positions from getting the same hash key? >> >>I assume that you convert your hash key into an index into the history. >>I assume that you take your 64 bit number and divide it by a constant >>(or right shift it) to get the number of entries available in your hash >>table? i.e. 64 megs would be 4 million positions. >> >>John Coffey > >There are many orders of magnitude more positions than 2^64 of course, >so every hash code corresponds to a stupendously large number of >positions. But, with 64 bits you get a hashing error only rarely (or >at least it should be rare, and you hope that that occasional error >doesn't lose a game). > >I mask off a certain number of bits to form the index into the hash >table (20 or so), the rest of the bits I store in the table entry to >test against. > >-Dan. I just looked back at an old file with the results of some hashing error rate measurements that I made. I found that I was getting about 600-900 errors/second with a 29-bit hash code (probably the node rate was on the order of 100 knps--though I didn't write that down). The error rate varied with the position being searched. With 33 bits it was between 0-8 errors/s. With 37 bits < 1 error/s. I couldn't really measure it with any acurracy with 41 bits (3 errors over several minutes). If we assume 750 errors/s for a 29-bit hash code, and if we accept that each bit added halves the error rate (well it seems reasonable to me anyway), then 64 bits should drive the error rate down to 750 * 2^-35 or 2.18x10^-8/s or about 1 error every 1.45 years. (I have effectively 65-bit hash codes in my program because I use the side-to-move as an extra bit of index instead of XORing a side-to-move bit pattern into the hash code.) -Dan.
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.