Has Anyone Heard of Multi-Hashing?

[Brandon Cieslak]

*

Hello Computer Go mailing list,

We were wondering if anyone has ever seen or heard of a method of storing
patterns similar to the one we are currently trying to implement and test.

Here is our method:

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.

When we store a win or a loss for a pattern (encountered in a recorded game
or a playout), we store it in each table. When looking for the win rate of
a pattern, we look in each of the tables and get the average of those
results.

The advantage of this approach (over one big table) is that, if there are n
tables, each lookup averages n copies of the “signal” but only 1 copy of
each collision. Preliminary experiments suggest that this is a better use
of memory than one large table.

(We also plan to store patterns at several different scales this way, but
that’s another story.)

The only reference we found to this approach has been a single section of
Narayanasamy et al., “Catching Accurate Profiles in Hardware” (
http://cseweb.ucsd.edu/~calder/papers/HPCA-03-Multihash.pdf, Section 6 is
most relevant). They call this approach Multi-Hashing.

Thank you in advance,

The Orego Team*

[steve uurtamo]

You can likely think about this in the context of bloom filters.

s.

Post by Brandon Cieslak
*
Hello Computer Go mailing list,
We were wondering if anyone has ever seen or heard of a method of storing
patterns similar to the one we are currently trying to implement and test.
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.
When we store a win or a loss for a pattern (encountered in a recorded
game or a playout), we store it in each table. When looking for the win
rate of a pattern, we look in each of the tables and get the average of
those results.
The advantage of this approach (over one big table) is that, if there are
n tables, each lookup averages n copies of the “signal” but only 1 copy of
each collision. Preliminary experiments suggest that this is a better use
of memory than one large table.
(We also plan to store patterns at several different scales this way, but
that’s another story.)
The only reference we found to this approach has been a single section of
Narayanasamy et al., “Catching Accurate Profiles in Hardware” (
http://cseweb.ucsd.edu/~calder/papers/HPCA-03-Multihash.pdf, Section 6 is
most relevant). They call this approach Multi-Hashing.
Thank you in advance,
The Orego Team*
_______________________________________________
Computer-go mailing list
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

[Petr Baudis]

Hi!

Post by Brandon Cieslak
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