How often do hash collisions occur in modern chess engines?

Question

This is a question I am asking for a chess engine I am attempting to create.

I have read that engines like Stockfish can look at around 100 million positions per second on a good computer. The code on GitHub (line 104) shows that Stockfish uses "uint64_t", a 64-bit int for hash keys. This Wikipedia page shows that for a hash table with 64 bit entries (4th line reading down), the probability of a collision after 6.1×10^8=600 million hashes (in the p=0.01 column) is 1%.

So at 100 million positions per second, giving the engine 6 seconds per half-move, 600 million positions would be analyzed for each half-move. A collision would occur 1 in every 100 half-moves. Thus, a collision would happen about once per game (50 moves per game seems roughly typical).

Am I missing something?

Answer 1

Generally the answer is, that there has been a patch from some developer of the community in the past, which happened to be an improvement over the status quo after tight statistically sound testing and this is usually accepted without questions, even if the change appears illogical to some.

It is known that a high collision rate must not be detremial for a chess engine. Bob Hyatt (author of "crafty") had written a paper about it a long time ago (https://craftychess.com/hyatt/collisions.html).

Stockfish uses a variable sized hash table (cluster granularity) with clusters of 32 bytes having 3 entries of size 10 byte each(https://github.com/official-stockfish/Stockfish/blob/master/src/tt.h#L68). Each cluster entry stores only 16 bit of the original zobrist key (https://github.com/official-stockfish/Stockfish/blob/master/src/tt.h#L51).

Another similar point is, that stockfish uses no locks to access the table, technically that means it is racy, that means 100% undefined behaviour. Every entry is carefully validated before use instead and given that a racy access simply returns an potential erroneus value, this would work even if every hash table access would return random numbers, at least this is the idea. As a side note, if there is some pedagocical language lawyer around reading this, please don't tell us stockfish could format our hard drives, we know it and are awaiting it with composure. The first one to show this technique was AFAIK again Hyatt (https://craftychess.com/hyatt/hashing.html).

We see that wrong hash values are absolutely no problem for stockfish, all that matters is what happens most of the time. All entries are reevaluated fully at the next iteration and can only cost search time.