Re: [gnugo-devel] hash_1_28.4: revision of hash_1_28.3

[Arend Bayer]

On Sun, 24 Mar 2002, Inge Wallin wrote:

> Arend wrote:
> > I first considered setting the minimum number of hash bits to 96. But I did
> > not get a single mistake/assertion failure when running "make second_batch"
> > with 32 bit hashing. So this suggests that we would get far less than one
> > mistake per game with 32 bit hashing (note that a hash collision does not
> > at all imply a wrong read result lookup yet: the routine, the string in
> > question and stackp have to agree as well). So with 64 bits, we should get
> > less than one mistake per 10^10 games (if we trust the random generator).
> 
> According to a paper that I recently read, the probability of an error
> in a hash table like this can be expressed as:
> 
>                2
>               N
>               --
>               2M
>         1 - e
> 
> (or 1-exp(N^2 / 2M) for those of you with a non-fixed width font)
> 
> where
>   N = the number of positions entered into the hash table during a game
>   M = the number of unique hash keys.
> 
> I will let you do the calculation since I don't know what N might be
> today.  M is, of course, 2^32, 2^64 or 2^96, whatever you choose.
> Does this formula agree with your calculation above?

The number of hash collision is indeed easy to compute. I think for GNU Go
the formula should be 1 - exp( - k * N^2 / M ) \approx k * N^2 / 2M,
where k is the number of moves per game, N is the average number of
positions entered per move, t the average number of hash positions stored,
and M as you say.
I think N is less than 4*10^5, k is 2*10^2. k*N^2/2 is hence  < 10^13

M is 4* 10^9 for 32 bits and 10^19 for 64 bits.

This means we get less than one 64bit hash collision in 10^6 games.

However, it is not possible to guess how likely it is that a wrong read
result lookup is once we have a hash collision, and also you cannot tell
how often this will cause a change in the genmove decision.

Arend