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

[Paul Pogonyshev]

Kai Wang wrote:

>    I'm a student currently working on SlugGo project. I have some
> quesitons about the hashing data structure changes in GnuGo 3.6.

GNU Go, not GnuGo, please.


> Since I couldn't find the answers in GnuGo's documentation website,
> I think here might be the right place to address my questions. If
> it's not, please tell me or simply ignore this email.

This is the right place.


>     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.

`FULL_POSITION_IN_HASH' was not active anyway (i.e. the code to
implement it was #if 0'ed out.)


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

I think it was estimated as approximately one collision per 400
fullboard games, but I may be wrong.


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

`FULL_POSITION_IN_HASH' was not active, as mentioned above.  GNU Go
will never notice a collision to take any specific action upon it.
Tracking them is too slow on its own.  If you feel unsafe with the
current possibility of a collision, better increase hash size, that
will be faster and more fruitful.

If a collision occurs, then most likely, nothing serious will happen.
Maybe some reading result will change and quite unlikely this will
influence move valuation to the point where GNU Go will prefer a
different move.  Finally, an assertion failure may occur or GNU Go
will crash in a less graceful way.


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

Presumably because it is enough for our purposes (I'm too lazy to dig
up old code) and there is no reason to waste space on unused fields.
I think some flags are not used in the new scheme, so we need less
bits for storing essentially the same information.

There were two basic reasons for the new hashing scheme:

- it is a little faster and a little more efficient;

- it is much simpler.

Paul