Re: [gnugo-devel] Patch: new cache part 2

[Arend Bayer]

>From Inge Wallin I heard that Gunnar wrote:

>
> > > The only thing that I am sure that you will comment on is that I had
> > > to separate some macro definitions in hash.h dependent on wether
> > > NUM_HASHVALUES is equal to 1 or 2. Take a look and say what you
> > > think.
> >
> > Obviously this still limits MIN_HASHBITS to 64 if long is 32 bits. I
> > still don't think it's resolved whether we are satisfied with this.
> > Even if a collision is extremely unlikely with 64 bits, it has a
> > psychological value to be able to increase it and verify that a weird
> > problem indeed is not caused by hash collisions.

I did some estimates about this with Inge on NNGS.

We need to estimate the number of reading nodes per move. The only thing
this is bound by is the number of nodes per second, and the run time
per move. (I.e. it does not make sense to take the current number of
nodes per move at level 10, because anyone with a fast enough CPU should
be allowed to set gnugo at a level where it's still fast enough for
him.)

Apparently Gunnar mentioned at one point that on his CPU, GNU Go
can do 200000 = 2*10^5 tactical reading nodes per second.

The day where CPUs exist that are 5 times as fast as Gunnar's isn't far
away. So lets assume 10^6 nodes/second.
30 seconds per move seems a realistic figure.
So 3*10^7 nodes per move.

Assume the cache is big enough to hold all read results for one move.
There are (3*10^7)^2/2 = 5*10^14 chances for hash collisions.

As 2^64 = 2 * 10^19, this means one hash collision per
4*10^4 moves, or roughly once per 400 games.

Is the assumption about the cache size realistic? We need 12 bytes per
entry, so this would be 360 MB. Not completely unrealistic either.

Once per 400 games is a too much for my taste. So I think we need to
be able to change to 96 bit.

Note that Inge's modifications _did_ affect this numbers. After these
changes, the likelyhood of a hash collision is 2^-64.
Before, it was
2^-64 * p(two routines are equal) * p(targets have same origin).

Arend