Chess Programming, Have to clear my transposition table after every move

Question

I am developing a chess engine and have implemented various basic algorithms such as negamax search, alpha beta pruning with move ordering, and quiescence search. I have a transposition table with an always-replace scheme because it seems to work better, however I've found that if I don't clear my transposition table between every move, the engine sometimes makes terrible blunders like hanging mate in one. I've looked online for solutions and a common error I found was that the table can sometimes become polluted with draw scores, however I've set up my code such that any draw scores simply aren't stored in the table, but that hasn't fixed the problem. I've made sure my zobrist hashing is working correctly, I'm not really sure what else could be causing this issue.

I've based my negamax search off this website.

https://en.wikipedia.org/wiki/Negamax

Any help would be appreciated.

Edit: Here's a link to my code if anyone wants to go further in detail. https://github.com/nikhilsarin1/Chess-Engine

public int search(int depth, int ply, int alpha, int beta) {
    int alphaOriginal = alpha;

    long zobristKey = model.getZobristKey();

    TranspositionEntry entry = model.transpositionTable.getPosition(zobristKey);

    if (entry != null && entry.ply() >= ply) {
      if (entry.flag() == TranspositionEntry.Flag.EXACT) {
        bestMoveForCurrentSearch = entry.bestMove();
        return entry.score();
      } else if (entry.flag() == TranspositionEntry.Flag.LOWER_BOUND) {
        alpha = Math.max(alpha, entry.score());
      } else if (entry.flag() == TranspositionEntry.Flag.UPPER_BOUND) {
        beta = Math.min(beta, entry.score());
      }
      if (alpha >= beta) {
        return entry.score();
      }
    }

    if (model.isCheckmate()) {
      return -mateScore + ply;
    } else if (model.isDraw()) {
      return 0;
    }

    if (depth == 0) {
      return quiescenceSearch(alpha, beta);
    }

    int evaluation = -999999999;
    Move bestMoveAtCurrentDepth = null;

    for (Move move : model.getBitboard().getLegalMoves()) {
      searchCount++;
      model.movePiece(move, false, depth);
      int score = -search(depth - 1, ply + 1, -beta, -alpha);
      model.undoMove();

      if (score > evaluation) {
        evaluation = score;
        bestMoveAtCurrentDepth = move; // Update the best move at this depth
      }

      alpha = Math.max(alpha, evaluation);

      if (alpha >= beta) {
        model.getBitboard().recordKillerMove(move, depth);
        break;
      }
    }

    TranspositionEntry.Flag flag;

    if (evaluation <= alphaOriginal) {
      flag = TranspositionEntry.Flag.UPPER_BOUND;
    } else if (evaluation >= beta) {
      flag = TranspositionEntry.Flag.LOWER_BOUND;
    } else {
      flag = TranspositionEntry.Flag.EXACT;
    }

    if (evaluation != 0) {
      model.transpositionTable.storePosition(
          zobristKey, ply, evaluation, flag, bestMoveAtCurrentDepth);
    }

    bestMoveForCurrentSearch = bestMoveAtCurrentDepth;
    return evaluation;
  }

Answer 1

Ok, I've finally found the root cause of your problem: you are storing the ply rather than the depth in the transposition table. This is wrong, and it ultimately causes your table to save only the results that you have the least information about, and only accept the results which are least informative.

In a transposition table, we save the value of the depth parameter because this tells us how much further we searched beyond that position before we reached the calculated score. The ply tells you how far into the search you were before you reached this position. The evaluation of a position does not depend on history (which is what the ply would hint at), it only depends on what happens after the position. It does not matter if we reached the position on move 1, 5, 10, 50, the best follow-up will always be the same.

When retrieving the results from the table, we compare the depth that the saved result was searched to against the depth that we need to search to. If the saved result was searched at least as deeply as we were planning to search, we can return that result immediately. If not, we can't accept the prior results and need to continue further. As implemented currently, you are essentially doing the opposite. If the saved result was searched more deeply than you plan to search, you ignore it, but if it was searched less deeply, you accept it, leading to blunders due to the low search depth in these evaluations.

---

The fix is not too difficult. In the Search, you should be saving the value of depth in the TranspositionTable, and comparing the depth against the saved depth in the entry. You should also update the names of the relevant variables in TranspositionTable and TranspositionEntry so that it is clear that you are saving depth, not ply.