Author: Dan Newman
Date: 11:54:11 09/22/98
Go up one level in this thread
On September 22, 1998 at 12:17:03, Pat King wrote:
>
>On September 22, 1998 at 08:50:53, Pat King wrote:
>
>
>>The odds of a search not containing a mistake are therefore
>>(1-2^-32)^n, where n is the number of nodes searched. To
>>have a 50% chance of an error, you'd need to search about 3e+09
>>nodes. With null-move, that's about 20 plies.
>
>He (I) also said
>
>>PS Since 1-2^32 is so close to 1, there's probably a fair amount
>>of error in that 3e+09 estimate, but you can stand a LOT of error
>>in this case and still have the argument hold up!
>
>Well, upon pondering the problem I made a refined estimate (but
>still only an estimate) of 2^32 or about 4.3 e+09 nodes, which
>works out to 20.2 plies instead of 19.something. Is the 2^32
>figure for P(lookup error)=.5 for a 32 bit key a coincidence? I
>suspect not. If not, then you can easily decide on how much error
>you're willing to tolerate. Based on this analysis, 64 bits
>certainly seems like overkill to me.
>
>Pat
I once measured the hashing error rate for an old program of
mine (I think it was doing on the order of 100 knps). For
a 29 bit hash code I was getting between 600 and 900 errors
per second. At 33 bits I was getting 0-8 errors per second.
(By errors I mean undetected collisions in which two different
positions hash to the same code.) So, 32 bits isn't nearly
enough. I made a guesstimate that 64 bits give me about
1 error in 1.5 years of runtime--that is perhaps overkill,
but if we go down just a few bits, then we get a few errors
per day or hour... (At 41 bits I was getting maybe one
error per minute.)
The trick I used to measure error rate is to mask off
some bits of the hash code and use those that are left
for the index and key. The bits that were masked off were
used to check for an error. Maybe I could put that more
clearly... When comparing the key stored in the hash table
entry with the key for the position, do it twice. Once
ignoring some bits and once again with all the bits:
if( (entry.key & 0x1fffffff) == (key & 0x1fffffff) ) {
if( entry.key != key ) nerrors++;
//etc.
}
With 3 bits masked off we have a 29-bit hash code (assuming
we start with 32 bits). This trick fails to detect about 1/8
of the errors you would get with a 29-bit hash code because we
have only the 3 masked off bits to do the check. If we
mask down a 64 bit hashcode to 32 bits we catch virtually all
the errors this way.
-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.