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

[kwang]

First, thanks for you and Paul's instant reply!

> 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.
Is there any paper or document on the Internet that explains Zobrist
hashing well. I still want to understand why the collision probability is
so low?( once per 10^9 or 400 games?)

>
>> 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
>
Now I understand why it is not necessary for GNU Go to store the board
position in the hash table. Thanks!

The reason that I brought this question up is that we ran into some
problems when we were trying to reuse Gnu Go's hash table in SlugGo. In
SlugGo, a preliminary hashing scheme was implemented reusing GNU Go 3.4's
hashing codes. But a wrong hash table lookup caused by a collision does
make a difference in SlugGo. I will look into GNU Go's new hashing scheme
more closely.

Kai