Answers.Body: <p>The term you're looking for is "replacement schemes". As far as I'm aware, the primary reference on this is still <a href="https://www.researchgate.net/publication/2737817_Replacement_Schemes_for_Transposition_Tables" rel="nofollow noreferrer">Replacement Schemes for Transposition Tables</a>, although it is a fairly old paper from 1994.</p>
  
  <p>I'll very briefly summarize the seven different schemes listed in this paper, but full text of the paper is also freely available and contains more info:</p>
  
  <ol>
  <li><strong>Deep</strong>: preserve position for which the deepest subtree below it was searched.</li>
  <li><strong>New</strong>: Always replace an old entry with the newest entry.</li>
  <li><strong>Old</strong>: Opposite of New. Paper mentions only including it for the sake of completeness, implies that it's probably not a good scheme.</li>
  <li><strong>Big1</strong>: similar to Deep, but uses the size (in number of nodes) of subtree searched, rather than just its depth. If the same position (i.e. table entry) occurs multiple times in a subtree, it is only counted once.</li>
  <li><strong>BigAll</strong>: same as above, but really counts the number of nodes rather than number of positions (so a position that occurs multiple times is counted multiple times).</li>
  <li><strong>TwoDeep</strong>: In this scheme, the TT is modified to contain two positions per table entry, rather than just one position. You could view it as the table having two "layers". In this scheme, a new position is moved into the first "slot" if it has the deepest subtree (as in the Deep scheme), moving the previous position in the first slot into the second slot. If a new position doesn't have a new deepest subtree, it is instead moved into the second slot.</li>
  <li><strong>TwoBig1</strong>: Similar to the above, but using Big1-style replacement rather than Deep-style replacement.</li>
  </ol>
  
  <p>If I recall correctly, the Two-layered schemes tend to perform best (of course they do require approximately twice as much memory for the same number of bits per key).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-23T20:29:30.060Z
Answers.Text: Thanks for the answer! I wasn't aware of that paper. One side question: How would you know the size of a subtree? (As suggested in Big1)
Answers.UserDisplayName: ihavenoidea
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-23T20:47:43.387Z
Answers.Text: @ihavenoidea I suppose you'd have to add some extra code to your recursive calls to keep track of the number of searched nodes. Note that the paper does specifically mention counting the nodes that have been searched, so nodes in parts of the tree that get pruned due to $\alpha\beta$-pruning do not need to be counted.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-23T09:49:36.470Z
Answers.LastActivityDate: 2019-03-23T09:49:36.470Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Consider an <a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="nofollow noreferrer">iterative deepening search</a> using a <a href="https://en.wikipedia.org/wiki/Transposition_table" rel="nofollow noreferrer">transposition table</a>. Whenever the transposition table is full, what are common strategies applied to replace entries in the table?</p>
  <p>I'm aware of two strategies:</p>
  <ol>
  <li><p>Replace the oldest entry whenever a new one is found.</p>
  </li>
  <li><p>Replace an entry if the new one has a higher depth.</p>
  </li>
  </ol>
  <p>I'm curious about other replacement approaches.</p>
  
Tags: <search><dynamic-programming><iddfs>
Title: What are the common techniques one could use to deal with collisions in a transposition table?
UserDisplayName: ihavenoidea
ThreadText: # What are the common techniques one could use to deal with collisions in a transposition table?
  
  (Asked by: username_0 on 2019-03-22)
  
  Consider an [iterative deepening search](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) using a [transposition table](https://en.wikipedia.org/wiki/Transposition_table). Whenever the transposition table is full, what are common strategies applied to replace entries in the table?
  
  I'm aware of two strategies:
  
  1. Replace the oldest entry whenever a new one is found.
  2. Replace an entry if the new one has a higher depth.
  
  I'm curious about other replacement approaches.
  
  **Tags:** search, dynamic-programming, iddfs
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-23. Score: 2 | Accepted answer
  
  The term you're looking for is "replacement schemes". As far as I'm aware, the primary reference on this is still [Replacement Schemes for Transposition Tables](https://www.researchgate.net/publication/2737817_Replacement_Schemes_for_Transposition_Tables), although it is a fairly old paper from 1994.
  
  I'll very briefly summarize the seven different schemes listed in this paper, but full text of the paper is also freely available and contains more info:
  
  1. **Deep**: preserve position for which the deepest subtree below it was searched.
  2. **New**: Always replace an old entry with the newest entry.
  3. **Old**: Opposite of New. Paper mentions only including it for the sake of completeness, implies that it's probably not a good scheme.
  4. **Big1**: similar to Deep, but uses the size (in number of nodes) of subtree searched, rather than just its depth. If the same position (i.e. table entry) occurs multiple times in a subtree, it is only counted once.
  5. **BigAll**: same as above, but really counts the number of nodes rather than number of positions (so a position that occurs multiple times is counted multiple times).
  6. **TwoDeep**: In this scheme, the TT is modified to contain two positions per table entry, rather than just one position. You could view it as the table having two "layers". In this scheme, a new position is moved into the first "slot" if it has the deepest subtree (as in the Deep scheme), moving the previous position in the first slot into the second slot. If a new position doesn't have a new deepest subtree, it is instead moved into the second slot.
  7. **TwoBig1**: Similar to the above, but using Big1-style replacement rather than Deep-style replacement.
  
  If I recall correctly, the Two-layered schemes tend to perform best (of course they do require approximately twice as much memory for the same number of bits per key).
  
  > **Comments:**
  > **username_0**: Thanks for the answer! I wasn't aware of that paper. One side question: How would you know the size of a subtree? (As suggested in Big1)  
  > **username_1**: @ihavenoidea I suppose you'd have to add some extra code to your recursive calls to keep track of the number of searched nodes. Note that the paper does specifically mention counting the nodes that have been searched, so nodes in parts of the tree that get pruned due to $\alpha\beta$-pruning do not need to be counted.  
  
  ---
  
  