Body: <p>This is a question I am asking for a chess engine I am attempting to create.</p>
  <p>I have read that engines like Stockfish can look at around 100 million positions per second on a good computer. The <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/types.h" rel="noreferrer">code on GitHub</a> (line 104) shows that Stockfish uses &quot;uint64_t&quot;, a 64-bit int for hash keys. This <a href="https://en.wikipedia.org/wiki/Birthday_problem#Probability_table" rel="noreferrer">Wikipedia page</a> 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%.</p>
  <p>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).</p>
  <p>Am I missing something?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-31T01:10:36.047Z
Comments.Text: 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.
Comments.UserDisplayName: Oscar Smith
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-14T03:06:22.657Z
Comments.Text: 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
Comments.UserDisplayName: Laska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-03T23:57:20.773Z
Comments.Text: 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.
Comments.UserDisplayName: pulsar512b
Tags: <engines><computer-chess>
Title: How often do hash collisions occur in modern chess engines?
ThreadText: # How often do hash collisions occur in modern chess engines?
  
  (Asked by: username_0 on 2021-01-31)
  
  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](https://github.com/official-stockfish/Stockfish/blob/master/src/types.h) (line 104) shows that Stockfish uses "uint64\_t", a 64-bit int for hash keys. This [Wikipedia page](https://en.wikipedia.org/wiki/Birthday_problem#Probability_table) 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?
  
  **Tags:** engines, computer-chess
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: 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  
  > **username_3**: 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.  
  
  ---
  
  ## 0 answers
  
  