I am programming a chess engine in C#, and it uses a Negamax function with alpha/beta pruning and "killer" moves for sorting. Additionally, I have implemented a crude transposition table using Zobrist Keys, but it doesn't seem to work as expected. When the table is disabled, the engine selects logical moves. When the table is enabled, the engine will select logical moves for the first 4-5 turns and then begin making random pawn moves (e.g. h7, h5). For some reason, these random moves seem more prominent when it is black's turn to play.

My Question: How can I ensure that my transposition table is working correctly?

Here is my code for the Negamax function:


static private float NegaMaxAlphaBeta(int _depth, float _alpha, float _beta) {

    UInt64 zKey = TranspositionTable.GetCurrentZobristKey();

    if (TranspositionTable.IsEnabled()) {

        if (TranspositionTable.IsPositionInTable(zKey)) {
            float tt_score = TranspositionTable.GetScore(zKey, _alpha, _beta, _depth);

            if (tt_score != TranspositionTable.unknownValue) {
                return tt_score;

    //          RETURN IF MAX DEPTH REACHED         //
    if (_depth == 0) {          // TO DO: Add checkmate check here
        return GetEval(turn);

    //                 GENERATE MOVES               //
    float score = float.NegativeInfinity;
    List<Move> movesList = Move.SortMovesList(Move.ConvertToLegalMoves(Move.GetAllMoves(turn)), _depth);

    foreach (Move _move in movesList) {


        float cur = -NegaMaxAlphaBeta(_depth - 1, -_beta, -_alpha);


        if (cur > score) {        
            score = cur;

        //        PRINCIPAL VARIATION (PV) FOUND        //
        if (score > _alpha) {     
            _alpha = score;

            if (_depth == maxDepth) {
                bestMove = _move;                                                                            // save best move
            TranspositionTable.AddEntry(zKey, _depth, _alpha, TranspositionTable.Flag.PV, bestMove);         // save principal variation (PV) w/ bestMove

        //            BETA CUT-OFF (FAIL HIGH)          //
        if (_alpha >= _beta) {    
            Move.SaveKillerMove(_depth, _move);                                                    // save killer move
            TranspositionTable.AddEntry(zKey, _depth, _alpha, TranspositionTable.Flag.FAIL_HIGH);  // save fail_high score
            return _alpha;

    //                    FAIL LOW                  //
    TranspositionTable.AddEntry(zKey, _depth, score, TranspositionTable.Flag.FAIL_LOW);            // save fail_low score

    return score;

Additionally, here is my "GetScore" function for the transposition table:

Get Score from Transposition Table

public static float GetScore(UInt64 _zobristKey, float _alpha, float _beta, int _depth) {      // should only be called if "IsPositionInTable" is true

    TranspositionTable.TT_Entry tt_entry = transpositionTable[_zobristKey];

    if (tt_entry.depth <= _depth) {
        if (tt_entry.flag == Flag.PV) {
            return tt_entry.score;

        if (tt_entry.flag == Flag.FAIL_LOW && tt_entry.score <= _alpha) {
            return _alpha;

        if (tt_entry.flag == Flag.FAIL_HIGH && tt_entry.score >= _beta) {
            return _beta;
    return unknownValue;

Finally, here is how my Zobrist Keys are generated, in case that is relevant:

Generate Zobrist Key

public static void GeneratePositionZobristKey() {
    UInt64 zobristKey = 0;
    BB[] allBoard = BoardManager.Instance.GetAllPieceBitBoards();

    // Add the score of each square and each piece to the ZobristKey
    for (int board = 0; board < allBoard.Length; board++) {
        List<int> squareIndices = BitboardUtility.GetAllBits(allBoard[board]);

        foreach (int squareIndex in squareIndices) {
            zobristKey ^= randomSquareValues[squareIndex, board];

    // Add the score of the color to move to the ZobristKey
    // Note: Only black is added because 'White' would only add '0'
    if (Engine.GetTurn() == Move.PieceColor.BLACK) {
        zobristKey ^= (UInt64)Move.PieceColor.BLACK;

    // Add castling and enpassant boards to ZobristKey
    zobristKey ^= BoardManager.Instance.GetBitBoard(BB.Board.CASTLING).GetPos();
    zobristKey ^= BoardManager.Instance.GetBitBoard(BB.Board.ENPASSANT).GetPos();

    currentZobristKey = zobristKey;

For debugging purposes, the engine is currently generating the Zobrist Keys on the fly during each iteration of Negamax. I understand that this is not optimal, and I have a plan for implementing 'iterative' changes to the Zobrist Key in the future. However, to ensure I at least have a working model, the Zobrist Key is generated fresh at the beginning of each Negamax iteration for now.

Any idea why this approach might be returning bad moves at times?

1 Answer 1


I don't see any obvious bugs in the code, but I didn't look that closely. I recommend testing the TT with perft positions, but instead of storing the eval you can store the number of resulting leaf nodes after a certain depth. You will only be able to use TT results from the same depth, but you should still be able to catch the bug with perft divide and enough depth.

  • Thanks for helping! I have done some research on Perft Divide, and I understand its usefulness in determining bugs in move generation (Here is a source for anyone who needs more information: rocechess.ch/perft.html). However, I am uncertain how this will help with TT bugs. Do many engines use a Perft Divide feature that I could compare against the total leaf nodes I find for a position using my TT? It seems that the number of leaf nodes would depend on the individual evaluation function of each engine, and would therefore be different between two engines. Commented Sep 2, 2023 at 0:23
  • Many engines, including Stockfish have a built in perft divide feature. You said that the individual evaluation function would affect the number of leaf nodes, which is true in a normal negamax search. However, I was suggesting that you do a pure and complete search of all possible lines and nodes, so this should not vary between engines. The idea is that if there is a bug with storing values in the TT or in your hashing function you will get an incorrect leaf node count result and can easily track down the bug with the perft divide. Commented Sep 2, 2023 at 1:41
  • I am still not understanding the link between the transposition table (TT) and the Divide function. Since the function of the TT is to cause pruning of the search tree, I do not understand how the Perft Divide results would be compatible with another engine. Here is a screenshot of Perft 4 (w/ Divide) between my engine (left) and Stockfish (right): imgur.com/a/QPmMzwf Note that the TT is disabled in the screenshot. The moves are ordered differently, but the node totals look the same. If I enable the TT, it seems like my node count would be smaller than Stockfish. Commented Sep 4, 2023 at 2:58
  • If you have modified everything as I recommended earlier (use TT to store moves after a certain depth, only access TT entry if depth is the same as in the entry), then a difference in results when using the TT signifies a problem with how the TT is storing the number of leaf nodes or hashing the positions. To debug, you can get the TT at the failed depth and disable adding new TT entries, then make one of the moves with an incorrect result. Simply repeat and reduce depth by one each time. You should eventually find a position where the TT entry doesn't match the real results properly. Commented Sep 4, 2023 at 16:05
  • Using your method, I think I found the issue. The correct evaluation score is not being returned from the TT in the "GetScore" function I shared above. My theory is that there is an error in the return value (positive/negative). My evaluation function returns a score relative to the player whose turn it is to move (if white to move and white is losing, the score will be negative; if black to move and black is winning, the score will be positive). Any thoughts on how to make this scoring pattern align with the "GetScore" function in the TT? I feel like a negative sign is missing somewhere. Commented Sep 8, 2023 at 2:05

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.