Re: [gnugo-devel] May I ask a question about the hashing in gnugo 3.6

[Gunnar Farnebäck]

Kai wrote:
>     I found out that the hashing data structures have changed a lot
> in GnuGo 3.6 compared to GnuGo 3.4, such as the removal of
> the "Hashposition" data structure, the removal of
> the "FULL_POSITION_IN_HASH" scheme, and the replacing of the "Read_result"
> field which contained two unsigned ints with  the "data" field which is
> only an unsigned int in "Hashnode" data structure.

Yes, the caching of read results was reimplemented more or less from
scratch between 3.4 and 3.6.

>     What's the collision occurence rate of the hash table?

According to the code comments in engine/hash.h about once per 10^9
games with the default 64 bit hash. I'm unsure about the reliability
of that information but if you're worried about collisions, increasing
the number of bits to 96 would reduce the collision probability by a
factor 2^32.

> Given that the "FULL_POSITION_IN_HASH" has been turned off, what
> would GnuGo 3.6 do if there is a collision?

As Paul said FULL_POSITION_IN_HASH was not turned on by default in 3.4
so there's no principal difference between 3.4 and 3.6 in this
respect. In most cases some part of a reading tree might get incorrect
results but there's no guarantee that it would propagate to the root
node or in the end affect the move generation. However, with
sufficiently bad luck the engine may well crash in an assertion
failure or in some other way.

If you want to try for yourself how serious collisions are, reduce the
number of bits to 32 and play a couple of games.

> And why the "Read_result" field was replaced with the smaller "data"
> field.

In the new caching scheme about half of the information in the
Read_result struct could be Zobrist hashed together with the board
hash, so there was no need to for more than the 32 bits in the data
field.

Paul wrote:
> There were two basic reasons for the new hashing scheme:
> 
> - it is a little faster and a little more efficient;
> 
> - it is much simpler.

You missed that it's also much more flexible.

/Gunnar