Hash position storing (Re: [gnugo-devel] The late phase of the release cycle)

[Arend Bayer]

I have an issue that should be answered well before 3.2.

While I was browsing through chess web pages for minimax optimizations I
also read the following on Zobrist hashing: apparently, chess engines, when
they have found a position with matching hash value in a cache table lookup,
they do the following: instead of exactly comparing the actual position
with the stored position, they just compare a 2nd computed hash value.

The theory behind that is that a "double hash collision" is so unlikely
that it is better to allow for it and instead save cache memory (and a
little time) -- a 2nd hash value needs considerably less memory than a
fullboard position.

I counted  <1000 hash collisions for a GNU Go game. This would mean that
we would on average have one "double hash collision" for four million games
(if the second hash value is another 32 bit integer).  On the other hand,
if we used this method, the struct Hash_data (which currently consists of
a 32bit hash value, a fullboard bit map and the ko position) could get
reduced in size from 448 bits to 64. The memory requirement of a hash node
(which additionally contains two pointers, one to the next hash node,
another to the first read result) would decrease from 512 to 128. According
to a comment in hash.c, there are on average <= 1.4 read results per
hash node, and one read result needs 96 bits.

So we would get as total average memory consumption per entered read result:
        96 bits + 128 bits / 1.4, appr. 198 bits
instead of
        96 bits + 512 bits / 1.4, appr. 462 bits.

So the save would be more than a factor 2. Together with a small performance
increase (computing hash values would get a little faster, the same for
comparing hash positions), I think this would be worth the more theoretical
inaccuracy. Of course, whether we want to use the saved memory to reduce
the default memory usage or to get more read results into the hash table is
open for discussion.

Arend