4

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;
  }

5
  • Do you see any weird issues with castling rights? It looks like your rank masks define Rank 1 as 0xFF, which should imply that the white Queenside Rook is on square 1 and the Kingside Rook is on Square 7, but the move code uses those for the origin squares (and capture squares) of black rooks when updating castling rights. I don't know if that's the (or even an) issue, but it's just something I've noticed so far.
    – Nelson O
    Aug 1, 2023 at 15:44
  • Another point: the Transposition Table in chess engines do not typically use a built-in map/dictionary data structure. They typically use fixed-size arrays and use the hashkey to figure out the index in the array that the value should be stored at. Collisions in the index is what "always overwrite" refers to as collisions on hashes is very unlikely in a single game. Using the Map would mean that every analyzed position is saved and your hash table will continue to grow. If you don't clear it between moves, does memory usage continue to grow?
    – Nelson O
    Aug 1, 2023 at 18:25
  • @NelsonO I haven't noticed any issues with castling rights. My move generation passes all PerfT tests I gave which includes various edge cases for castling (enemy attacks, king/rook moves, enemy capturing rook, etc) so I would assume it works based on that, but I could've missed an edge case I didn't think about. I think my code is poorly written in that the LSB of my bitboard represents square a1 but the array index of that in the char array representation of the board is 56, so that would make the black queen side rook index 0 or a8. I can see how that would be unnecessarily confusing.
    – Nikhil
    Aug 8, 2023 at 2:49
  • @NelsonO That is something I saw in other people's codes, but I just assumed it didn't matter, but I'm now realizing that may have been a faulty assumption. I'm not sure why using a fixed-size array vs a built-in Java map structure makes a difference though. My thought was that if I use a Map, I can avoid the problem of index collisions to a greater extent since java automatically increases the capacity of the hash map based on the load factor and as long as my Zobrist keys are generated correctly, I should very rarely be generating the same key for different positions.
    – Nikhil
    Aug 8, 2023 at 3:14
  • It's too much to go into detail here, but the gist is that a transposition table cannot reasonably store all evaluated positions, so we do not need a structure that attempts to store everything that we give it. Aside from that, many positions eventually become irrelevant due to irreversible moves, so we are also fine with a data structure that overwrites data. Lastly, growing a table is expensive, so we prefer to specify a fixed size when initializing the engine to both constrain the maximum size, and also avoid reorganizing the table during a search.
    – Nelson O
    Aug 8, 2023 at 21:07

1 Answer 1

4

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.

4
  • That seems to have worked, thank you so much! Kind of annoying such a minor error was creating such a huge problem.
    – Nikhil
    Aug 11, 2023 at 3:36
  • Doesn't the move we reach a position in matter, though, because of the 50-move rule (and maybe also because of the threefold repetition rule)? Jan 7 at 15:39
  • @HelloGoodbye That is true, and that is why it is a good idea to consider those rules prior to looking at the transposition table. In Stockfish, the position is evaluated for a draw prior to querying the transposition table, and the score from the transposition table is also not returned if we are within 10 ply (so 5 turns) of the 50-move rule being relevant. It is important to consider these rules, but it is easy enough to handle them separately so that the bulk of the search can ignore these exceptions.
    – Nelson O
    Jan 8 at 17:16
  • That makes sense. But it feels like that instead of ignoring the transposition table altogether when you are within 10 ply of the 50-move rule being relevant, you could instead just make the hash code dependent on how many moves that have been made since the last capture (even if you only do so in the cases where you would otherwise have ignored the transposition table). Jan 10 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.