Re: [gnugo-devel] hash collisions

[Gunnar Farnebäck]

Doug wrote:
> For MIN_HASHBITS = 32, there are several nullspace basis vectors of size
> 10. Here's one:
> [...]
> Informal testing of other random matrices of the same size showed that
> this is pretty good:  8 is typical, and 6 was the lowest I saw. I didn't
> work out positions for MIN_HASHBITS = 64, but similar tests of random
> matrices showed 20 as a typical low collision size, and 30 some for 96.

Interesting.

> HASHVALUE_PRINT_FORMAT in hash.h should probably define a field length.

Please elaborate.

> Random numbers are good, but may not be absolutely ideal for Zobrist
> hashing. For example, consider 0: it's as likely to appear for the hash
> value of a point as any other number, but it's a disaster for Zobrist
> hashing, as that point would then not ever contribute to the hash, i.e. a
> collision of length one. One could imagine using the freedom in picking
> nonrandom values to avoid this and other short collisions, or to ensure
> that collisions are distributed in some implausible way.

There are somewhat similar problems in coding theory, but I'm doubtful
they are similar enough to be relevant. Still it could be an area to
look into.

> Random is simple, though.

Indeed. I would guess that it's hard to find big enough improvements
to motivate a more complex algorithm.

> In a web search I found that some chess programmers use fairly short
> hashes, and accept a certain level of collisions. Even though this does
> cause misevaluations due to false cache hits, it's a fairly small fraction
> of nodes which will effect the evaluation of the root node, and can be a
> win overall.

Sounds reasonable, at least if there are effective methods to
determine whether a bad move was caused by hash collisions. (It would
be a nightmare to debug otherwise.) I suppose the main reason for this
is to allow bigger hashtables in the same amount of memory, which
maybe is more useful in chess than in go. At least GNU Go doesn't seem
to benefit much from a huge cache.

/Gunnar