0
$\begingroup$

Context

Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.

The table has a finite recycled memory (key % p is the index of the key, p is table size and prime).

That is, at table[index(key)] (there) we store key and (game position) evaluation.

So, when fetching cached evaluation of a game position P that was hashed into key:

  • If key matches with key stored at index(key), we return evaluation stored there.
  • Else, we return default value (indicating "empty"), then rewrite key and evaluation there.

(I've basically summarized how a simple transposition table can be implemented.)

Collision problem

The problem is when two different game positions P1 and P2 are hashed into the same key (collision).

Say that we encounter position P1 first. First time reading this key, "empty" value will be returned and evaluation1 for P1 will be stored in table[index(key)]. Second time reading this key (matching key at index), evaluation1 for P1 will be returned. This will either:

  • Be fine, in the case that we encountered P1 again.

  • Be an error in the game evaluation, in the case that we encountered P2.

How can this error be detected and corrected, efficently?

Apparently stockfish uses something like this Zorbist hashing and has verification "Every entry is carefully validated before use,...", meaning that "...this (game engine) would work even if every hash table access would return random numbers."; But, how is this verification implemented?

$\endgroup$
0
$\begingroup$

I don't have any particular experience with transposition tables in particular, but in general, the standard way to use a hash table stores the key (e.g., the value P1 or P2) in the entry, not the hash of the key. This way you can detect collisions.

Terminology: in standard hash table usage, the key is the value (i.e., the position, such as P1 or P2), not its hash.

There are many standard ways to resolve collisions in hash tables, e.g., using open chaining or closed chaining. See https://en.wikipedia.org/wiki/Hash_table. However, I suspect those are not needed for transposition tables, as I suspect it is fine to return "unknown" in the event of a collision. If so, you might not need any of those methods.

$\endgroup$
1
  • $\begingroup$ I'm not concerned with that type of collisions (my hash function that compute the index is simple modulo p, prime size), i.e. I'm not concerned with the transposition table hashing. Instead, note that people combine transposition tables with additional (e.g. Zorbist) hashing of keys to save space (smaller keys). Then they usually try to minimize collisions of hashed keys in various ways, as they will inevitably happen. Instead of minimizing collisions, I'm wondering if there's a way to efficiently detect and correct those collisions, maybe using properties of Zorbist or some other hash. $\endgroup$
    – Vepir
    Jun 18 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.