Re: [gnugo-devel] May I ask a question about the hashing in gnugo 3.6

[Arend Bayer]

On Wed, 22 Dec 2004 address@hidden wrote:

> First, thanks for you and Paul's instant reply!
> 
> > According to the code comments in engine/hash.h about once per 10^9
> > games with the default 64 bit hash. I'm unsure about the reliability
> > of that information but if you're worried about collisions, increasing
> > the number of bits to 96 would reduce the collision probability by a
> > factor 2^32.
> Is there any paper or document on the Internet that explains Zobrist
> hashing well. I still want to understand why the collision probability is
> so low?( once per 10^9 or 400 games?)

Since we are using a 64 bit hash, the probability of two random
positions resulting in the same hash is 2^-64 or roughly 0.5*10^-19.
GNU Go analyzes about 10^6 nodes per move, so the the likelyhood that
one of them collides with a position stored in the hash table
(10^6)*number of hash table entries* 0.5*10^-19. 
I am not sure if the above figure of 10^9 is up to date, but it's still
rare enough (>>10^5).

> The reason that I brought this question up is that we ran into some
> problems when we were trying to reuse Gnu Go's hash table in SlugGo. In
> SlugGo, a preliminary hashing scheme was implemented reusing GNU Go 3.4's
> hashing codes. But a wrong hash table lookup caused by a collision does
> make a difference in SlugGo. I will look into GNU Go's new hashing scheme
> more closely.

No need not worry about hash collisions in SlugGo at all. They won't
happen in your lifetime.

Arend