[Computer-go] Has Anyone Heard of Multi-Hashing?
pasky at ucw.cz
Fri Jul 19 12:45:21 PDT 2013
On Wed, Jul 17, 2013 at 08:54:21AM -0700, Brandon Cieslak wrote:
> We are using multiple hash tables to store win rates for large patterns.
> Each table uses a different Zobrist hash function. The tables are “sloppy”
> in that, when two patterns inevitably hash to the same location, we simply
> combine the information.
The idea seems interesting, but if you are really worried about
collisions, I wonder if this approach really pays off compared to some
more standard approach like linked lists in the buckets or using
adjecent buckets. The issue is that each hash lookup results in pretty
much guaranteed cache miss (and can easily trash your cache if you do
too many of these) and serving a cache miss takes *long* time...
Perhaps a good compromise would be to use one hash function to
generate positions, then use another function (or multiple functions)
to match the desired value locally.
The bottom-line then really is just whether collisions are bad enough
that handling this compensates for the (CPU time, cache space) overhead
of calculating multiple zobrist hashes in parallel. I'd be very curious
to hear about your findings. :-)
Petr "Pasky" Baudis
More information about the Computer-go