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)
So, when fetching cached evaluation of a game position
P that was hashed into
keymatches with key stored at
index(key), we return
- Else, we return default value (indicating "empty"), then rewrite
(I've basically summarized how a simple transposition table can be implemented.)
The problem is when two different game positions
P2 are hashed into the same
Say that we encounter position
P1 first. First time reading this
key, "empty" value will be returned and
P1 will be stored in
table[index(key)]. Second time reading this
key (matching key at index),
P1 will be returned. This will either:
Be fine, in the case that we encountered
Be an error in the game evaluation, in the case that we encountered
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?