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

[Paul Pogonyshev]

Arend wrote:
> 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.

i made a much more math-like investigation, but got results very
close to Arend's.  i guess that's because 3 * 10^7 is so much
smaller than 2 * 10^19.  if you are interested, read on ;)

i'll take for granted the hidden assumption that hash values are
distributed uniformly since it is very hard to say anything about
the matter.  let's assume we have (m) reading nodes per move and
(n) possible hash values and that we store all reading nodes for
one move in cache.

when we add the first node into cache, there is obviously zero
probability of collision.  for the second node the probability is
(1 / n) since it can collide only with the first node.  similarly,
for other nodes the probabilities will be (2 / n), (3 / n), ...,
((m - 1) / n).

now we need the probability of _not_ having collision on any step.
clearly it is

        P = (n - 0) * (n - 1) * ... * (n - (m - 1)) / (n^m) =
          = n! / ((n - m)! * n^m)

now let's apply Stirling formula:

        n! = sqrt(2 * pi * n) * (n^n) * (e^(-n))

where the equality is not precise of course.

we get

        P = sqrt(2 * pi * n) * n^n * (e^(-n)) /
            / ((sqrt(2 * pi (n - m)) * (n - m)^(n - m) * (e^(m - n)) *
               * (n^m)) =
          = sqrt(n / (n - m)) * n^(n - m) * (n - m)^(n - m) * e^(-m) =
          = sqrt(n / (n - m)) * (n / (n - m))^(n - m) * e^(-m)

hence

        ln P = 0.5 (ln n - ln (n - m)) + (n - m) * (ln n - ln (n - m)) - m =
             = (n - m + 0.5) (ln n - ln (n - m)) - m

0.5 clearly doesn't matter.  now, since (ln n) and ln (n - m) are very
close, we use Taylor's formula:

        ln (n - m) = ln n - (m / n) - (m^2 / (2 * n^2)) - O((m / n)^3)

hence

        ln P = (n - m) * (m /n) + (n - m) * (m ^2 / (2 * n^2)) - m =
             = - (m^2 / 2 * n) - (m^3 / 2 * n^2)

with good precision.

let's take Arend's numbers: m = 3 * 10^7, n = 2 ^ 10^19.  then

        ln P =  - 2.25 * 10^(-5) - 3.375 * 10^(-17)

clearly, (n - m) * O((m / n)^3) was ignored correctly.

now,

        P = exp(ln P) = exp(-0.0000225) = 0.9999775

and the probability of a collision in a given move is

        Q = 1 - P = 0.0000225 = 2.25 * 10^(-5) (not a surpise).

mathematical expectation of random variable

        A = {number of moves without collision}

which is distributed by geometrical law is well known:

        E{A} = P / Q = 0.9999775 / 0.0000225 = 4.44 * 10^4

very close to what Arend got (4 * 10^4).

Paul