Author: Robert Hyatt
Date: 12:52:05 09/22/98
Go up one level in this thread
On September 22, 1998 at 08:50:53, Pat King wrote: > >On September 21, 1998 at 19:32:37, James Robertson wrote: > > >>I sent a message to Robert Hyatt with the same question, and he said that the >>odds of turning up two positions with the same number is almost nil. > This was with respect to using a *64 bit* hash signature. Several of us ran some exhaustive tests a few years ago and discussed this in r.g.c.c, John Stanback, myself, perhaps Bruce, and I'm not sure who else. The bottom line is that using 32 bit hash keys has a probability of nearly *one* for producing collisions in a search of any length. We typically had hundreds of "collisions" during 3 minute searches (we measured this by storing the signature *and* the real board position, and when the signatures matched, we compared the real positions.) For 64 bit entries I got *zero* collisions for any reasonable searches, up to 2 billion nodes total. For 32 bit signatures, I got *plenty* of them... >Almost. I use a 16 bit index and 16 bit signature, so the chance of two >positions having >the same index and signature is 2^-32 (assuming my hashing algorithms are doing >a >good job of uniformly distributing the keys). 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. And is the error in a place likely to affect the 1 billion nodes isn't 20 plies. I've done plenty of testing where a 13 ply search wrapped an unsigned int back around to zero again (over 4 billion nodes)... outcome >of the search? >Probably not. So we can sleep well at night knowing that at least mistakes in >recalling >hash nodes are not a serious problem! depends on your definition of "not a serious problem". Many hash collisions can be absorbed by the search with no change at the root. Many, but *not all*. There are those that will change the score, and there are those that will make you choose a losing move, thinking it is a winner. 32 bits is not enough, by actual experiment. you can compute a 64 bit signature, and only store 32 bits of it in the table, by using the other part for the probe index... > >Pat > >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!
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.