Author: Dan Newman
Date: 16:10:01 09/16/00
Go up one level in this thread
On September 16, 2000 at 18:30:21, José Carlos wrote: >On September 16, 2000 at 17:04:23, Dan Newman wrote: > >>On September 16, 2000 at 12:25:27, Larry Griffiths wrote: >> >>>I have tried using a 64-bit hash key and storing it in each hash entry to insure >>>that different positions that point to the same hash table entry can be >>>verified. >>> >>>I also have a 32 byte smallboard that I use for debugging. This smallboard has >>>4bits for each piece color and type so I know for sure if the current position >>>matches the hash table entry. >>> >>>The 64-bit hashkey works most of the time, but sometimes different board >>>positions produce the same hash-key. >>> >>>Is there a fail-safe method other than my 32 byte smallboard for insuring that >>>different board positions with the same hash keys can be resolved? >>> >>>Larry. >> >>I once tried to measure the error rate and got no errors at all with 64-bit >>hashcodes over several hours of testing. I was able to measure the error rate >>for 32-bit hashcodes--that was about 1 false match/second (at perhaps 100k >>probes/s). I think someone came up with an estimate of (very approximantely) >>one error/day with a 64-bit hashcode at 100 knps--or was it 1 Mnps? Anyway, >>the error rate is very low and can mostly be ignored. I do try to make sure >>that such an error won't crash my program though... >> >>-Dan. > > If you got 1 false match per second with 32 bits hashcodes, then you shoud >have a false match every 2^32 seconds with 64 bits hashcodes, which is IMHO not >a problem at all. 2^32 seconds is ~136 years. With an error rate that low I wouldn't bother checking the move :). I too have thought that adding a bit should reduce the false match rate by a factor of two. It seems obvious. But there is a problem. If you start out with one bit (two entries), then the error rate will be quite high, almost the probe rate, R. So if we add 31 bits to this we should get R errors in 2^31 seconds. If the probe rate is 100k probes/s, that would give us 4.6 x 10^-5 errors/s (with a 32-bit hashcode), but I get one error/s. So at least at that extreme the factor of two per bit doesn't hold. It may well hold at 32 bits and higher though... -Dan. > I simply ignore that problem in Averno, and the only thing I do is test if the >HT move is legal in the current position before trying it. > > José C.
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.