8

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?

4
  • That sounds about right. It would be interesting to see if using a 128 bit hash produces better results at longer time control. Part of the problem with testing this is that most fishtest runs ar at 10+.1, which would dramatically lower the chance of collision. If there was a similarly fast 128 bit hash, it could make a big difference at TCEC or other big events where there are way more nodes per move. – Oscar Smith Jan 31 at 1:10
  • Interesting question about something I don’t know much about. What is the impact of a collision and how often might it be detectable? E.g. if the opponent plays identically how often would Stockfish play differently? Thanks – Laska Feb 14 at 3:06
  • The impact of a collision would be that Stockfish mistakes a position (B) for a position that it has already evaluated (A). It would consider that posittion (B) has the same evaulation as position A which could be very wrong. – WW. Feb 15 at 0:30
  • Also worth noting that most evaluated positions are maybe not important for the final evaluation, and that it'd require the depth of that evaluation to be more than or equal to the one it requires. So, tldr: it's not really gonna matter. – pulsar512b Mar 3 at 23:57
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.

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.