Re: [gnugo-devel] Improvement of the hash table in GNU go

[Inge Wallin]

> If I understood the idea right, the N will be the hashvalue modulus
> cache-size. And the hash will already contain the position, komaster, and
> routine. So we do not have to store the hash value - or if we trust it to be
> good enough, we could skip the (position, komaster, routine).
> 
> I suggest that we add counters to check the frequency of hash collisions,
> both collisions where two totally separate hashes give the same N, and where
> different (p,k,r) give the same hash. With that data in hand we should be
> able to increase N and possibly the number of bits in the hash, until
> collisions are so rare that we can ignore them. Byt that time we can reclaim
> the extra memory by dropping almost everything in the cache nodes. But we
> had better leave the code in, so that we can debug the case where the cache
> does play a trick on us...
> 
> Just my thoughts early morning, before the first coffee. If I am totally
> off, I will welcome a correction.

I am afraid that you are totally off.  :-)

First, this check is impossible to do, unless we store the whole
position and the rest of the information in the hash table.  Granted,
this is possible to do, but it lowers the number of nodes in the table
significally.  We could, of course, do it for checking purposes, but 
 a) the program will be much, much slower and
 b) we will still not know the exact probability of collisions remove
    the extra information from the hash table and therefore can
    increase the number of nodes again.

Second, the calculations already show that given a 64 bit hash value,
and the number of nodes per second that we search, the risk is still
very small.  If you are interested, I can look up the exact
calculations in Breuker and present them to you.  I did it maybe a
year ago, and that mail is probably still in the mailing list archive
somewhere. 

             -Inge