3
$\begingroup$

Consider an iterative deepening search using a 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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, 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).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$
    – ihavenoidea
    Mar 23, 2019 at 20:29
  • 2
    $\begingroup$ @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. $\endgroup$
    – Dennis Soemers ♦
    Mar 23, 2019 at 20:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .