Answers.Body: <p>If a small change in the input consistently makes a small change in the hash, then it becomes somewhat probable that <em>two</em> small changes in the input will combine to produce <em>no</em> change to the hash. In other words, hash collisions with such a function are likely to come from inputs that have a small Hamming distance. This seems like an undesirable property if you're using them to accelerate tree search, where you're making incremental changes from a starting position.</p>
  <p>On the other hand, if even a single-bit change in the input changes on average 50% of the hash bits (the standard for cryptographic hashes), then nearby inputs will be no more likely to generate a collision than <em>any</em> pair of inputs, and so the &quot;distance between collisions&quot; will be large on average, decreasing the number of collisions you're likely to encounter in an orderly scenario like evaluating a chess game.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-31T03:36:13.193Z
Answers.LastActivityDate: 2024-12-31T03:36:13.193Z
Answers.UserDisplayName: hobbs
Answers.Body: <p>The emphasis on why it needs to be &quot;entirely different indices&quot; may be because of how engines <a href="https://www.chessprogramming.org/Transposition_Table#Address_Calculation" rel="nofollow noreferrer">calculate table indices based on the Zobrist Key</a> - many of them use a subset of bits of the actual Zobrist Key to index a Transposition Table entry very quickly.</p>
  <p>If similar positions (e.g. one-ply different) produce similar results, transposition tables may <a href="https://www.chessprogramming.org/Transposition_Table#Replacement_Strategies" rel="nofollow noreferrer">replace them very frequently</a> during the search because it would collide with a similar position searched recently - thereby negating any performance improvements the Transposition Table was able to provide.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-20T05:39:55.540Z
Answers.LastActivityDate: 2024-12-20T05:59:55.757Z
Answers.LastEditDate: 2024-12-20T05:59:55.757Z
Answers.UserDisplayName: vishnu.bh
Body: <p>When reading the <a href="https://www.chessprogramming.org/Zobrist_Hashing" rel="noreferrer">chess programming wiki article</a>, it mentions the following:</p>
  <blockquote>
  <p>The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient Hash tables or databases, e.g. transposition tables and opening books.</p>
  </blockquote>
  <p>It is not immediately obvious to me why it would be beneficial for similar positions to generate entirely different hash values. The article implies that this would make the hash table more efficient somehow? But I don't see why that would be the case.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-12T07:49:41.087Z
Comments.Text: Hash tables are most efficient when they avoid collisions - i.e. multiple given inputs map to the same output. [You then have an extra level of searching](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution) to resolve the collision. I am not a chess programmer but my guess is that as similar positions are likely to occur in the analysis of a given position for efficiency you really want to avoid collisions. But this is a guess, I'll leave it to somebody who has actually programmed this to answer.
Comments.UserDisplayName: Ian Bush
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-13T04:11:53.300Z
Comments.Text: It's a bit unclear what "entirely different" actually means. It's a property of many hashing algorithms that very similar inputs yield radically different outputs. But it's not clear if that's what's meant here, or "entirely different" just means "definitely not the same".
Comments.UserDisplayName: Steve Bennett
Tags: <programming>
Title: Why is it important for similar positions to generate vastly different hash values?
ThreadText: # Why is it important for similar positions to generate vastly different hash values?
  
  (Asked by: username_0 on 2024-12-12)
  
  When reading the [chess programming wiki article](https://www.chessprogramming.org/Zobrist_Hashing), it mentions the following:
  
  > The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient Hash tables or databases, e.g. transposition tables and opening books.
  
  It is not immediately obvious to me why it would be beneficial for similar positions to generate entirely different hash values. The article implies that this would make the hash table more efficient somehow? But I don't see why that would be the case.
  
  **Tags:** programming
  
  > **Comments:**
  > **username_1**: Hash tables are most efficient when they avoid collisions - i.e. multiple given inputs map to the same output. [You then have an extra level of searching](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution) to resolve the collision. I am not a chess programmer but my guess is that as similar positions are likely to occur in the analysis of a given position for efficiency you really want to avoid collisions. But this is a guess, I'll leave it to somebody who has actually programmed this to answer.  
  > **username_2**: It's a bit unclear what "entirely different" actually means. It's a property of many hashing algorithms that very similar inputs yield radically different outputs. But it's not clear if that's what's meant here, or "entirely different" just means "definitely not the same".  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2024-12-31. Score: 1
  
  If a small change in the input consistently makes a small change in the hash, then it becomes somewhat probable that *two* small changes in the input will combine to produce *no* change to the hash. In other words, hash collisions with such a function are likely to come from inputs that have a small Hamming distance. This seems like an undesirable property if you're using them to accelerate tree search, where you're making incremental changes from a starting position.
  
  On the other hand, if even a single-bit change in the input changes on average 50% of the hash bits (the standard for cryptographic hashes), then nearby inputs will be no more likely to generate a collision than *any* pair of inputs, and so the "distance between collisions" will be large on average, decreasing the number of collisions you're likely to encounter in an orderly scenario like evaluating a chess game.
  
  
  ---
  
  ### Answer by username_4 on 2024-12-20. Score: 1
  
  The emphasis on why it needs to be "entirely different indices" may be because of how engines [calculate table indices based on the Zobrist Key](https://www.chessprogramming.org/Transposition_Table#Address_Calculation) - many of them use a subset of bits of the actual Zobrist Key to index a Transposition Table entry very quickly.
  
  If similar positions (e.g. one-ply different) produce similar results, transposition tables may [replace them very frequently](https://www.chessprogramming.org/Transposition_Table#Replacement_Strategies) during the search because it would collide with a similar position searched recently - thereby negating any performance improvements the Transposition Table was able to provide.
  
  
  ---
  
  