How can I ensure my transposition table is working correctly?

Question

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:

Negamax

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

    //:::::::::::::::::::::::::::::::::::::::::::::://
    //    CHECK TRANSPOSITION TABLE FOR POSITION    //
    //:::::::::::::::::::::::::::::::::::::::::::::://
    TranspositionTable.GeneratePositionZobristKey();
    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) {
        nodesSearched++;

        Move.MakeMove(_move);
        ChangeTurn();

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

        Move.UnMakeMove();
        ChangeTurn(true);

        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?

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.