Transposition table replacement strategies

[zd3nik]

Here is how I handle TT probes/stores in my main search routine. If anyone can spot potential problem(s) I would appreciate feedback.

Code: Select all

    pv = EMPTY
    bestScore = MATED_AT(ply);

    ttGets++;
    ttMove = NONE;
    ttEntry = TT.GetEntryAt(positionKey);
    if (ttEntry.Matches(positionKey)) {
      ttHits++;
      ttMove = ttEntry.BestMove();
      if (ttEntry.Depth() >= depth) {
        switch (ttEntry.Type()) {
        case UpperBound:
          if &#40;ttEntry.Score&#40;) <= alpha&#41; &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        case LowerBound&#58;
          if &#40;ttEntry.Score&#40;) >= beta&#41; &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        case ExactScore&#58;
          if (&#40;ttEntry.Score&#40;) <= alpha&#41; OR &#40;ttEntry.Score&#40;) >= beta&#41; OR &#40;not pvNode&#41;) &#123;
            pv = ttMove;
            return ttEntry.Score&#40;);
          &#125;
          break;
        &#125;
      &#125;
      Exec&#40;ttMove&#41;;
      bestScore = -child.Search&#40;-beta, -alpha&#41;
      Undo&#40;ttMove&#41;;
      pv = ttMove + child.pv;
      if &#40;bestScore >= beta&#41; &#123;
        ttEntry.Set&#40;bestScore, LowerBound, ttMove&#41;;
        return bestScore;
      &#125;
    &#125;

    GenerateMoves&#40;);
    if &#40;no legal moves&#41; &#123;
      if &#40;in check&#41; return MATED_AT&#40;ply&#41; else return DRAW;
    &#125;

    foreach&#40;move&#41; &#123;
      if &#40;move != ttMove&#41; &#123;
        Exec&#40;move&#41;;
        score = -child.Search&#40;-beta, -alpha&#41;;
        Undo&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
          pv = move + child.pv;
          bestScore = score
        &#125;
        if &#40;score >= beta&#41; &#123;
          ttEntry.Set&#40;score, LowerBound, move&#41;;
          return score;
        &#125;
        alpha = max&#40;score, alpha&#41;;
      &#125;
    &#125;

    if &#40;bestScore > original_alpha&#41; &#123;
      ttEntry.Set&#40;bestScore, ExactScore, pv.FirstMove&#40;));
    &#125;
    else &#123;
      ttEntry.Set&#40;bestScore, UpperBound, pv.FirstMove&#40;));
    &#125;

    return bestScore;

Of course I've simplified things a lot in this psuedo-code. For example the real code implements null move pruning, PVS, LMR, etc...

QSearch does the TT lookup and returns ttEntry.Score() where appropriate. But QSearch does not store results (never calls ttEntry.Set)