Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-02T00:23:17.490Z
Answers.Text: 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: http://www.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.
Answers.UserDisplayName: Shannon Deaton
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-02T01:41:33.127Z
Answers.Text: 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.
Answers.UserDisplayName: Stockfischer
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T02:58:34.197Z
Answers.Text: 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): https://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.
Answers.UserDisplayName: Shannon Deaton
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T16:05:21.820Z
Answers.Text: 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.
Answers.UserDisplayName: Stockfischer
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-08T02:05:09.960Z
Answers.Text: 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.
Answers.UserDisplayName: Shannon Deaton
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-01T13:36:41.380Z
Answers.LastActivityDate: 2023-09-01T13:36:41.380Z
Answers.UserDisplayName: Stockfischer
Body: <p>I am programming a chess engine in C#, and it uses a Negamax function with alpha/beta pruning and &quot;killer&quot; 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 <strong>disabled</strong>, the engine selects logical moves.  When the table is <strong>enabled</strong>, 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.</p>
  <p><strong>My Question:</strong> How can I ensure that my transposition table is working correctly?</p>
  <p>Here is my code for the Negamax function:</p>
  <h1>Negamax</h1>
  <pre><code>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&lt;Move&gt; 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 &gt; score) {        
              score = cur;
          }
  
          //:::::::::::::::::::::::::::::::::::::::::::::://
          //        PRINCIPAL VARIATION (PV) FOUND        //
          //:::::::::::::::::::::::::::::::::::::::::::::://
          if (score &gt; _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 &gt;= _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;
  }
  </code></pre>
  <p>Additionally, here is my &quot;GetScore&quot; function for the transposition table:</p>
  <h1>Get Score from Transposition Table</h1>
  <pre><code>public static float GetScore(UInt64 _zobristKey, float _alpha, float _beta, int _depth) {      // should only be called if &quot;IsPositionInTable&quot; is true
  
      TranspositionTable.TT_Entry tt_entry = transpositionTable[_zobristKey];
  
      if (tt_entry.depth &lt;= _depth) {
          if (tt_entry.flag == Flag.PV) {
              return tt_entry.score;
          }
  
          if (tt_entry.flag == Flag.FAIL_LOW &amp;&amp; tt_entry.score &lt;= _alpha) {
              return _alpha;
          }
  
          if (tt_entry.flag == Flag.FAIL_HIGH &amp;&amp; tt_entry.score &gt;= _beta) {
              return _beta;
          }
      }
      return unknownValue;
  }
  </code></pre>
  <p>Finally, here is how my Zobrist Keys are generated, in case that is relevant:</p>
  <h1>Generate Zobrist Key</h1>
  <pre><code>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 &lt; allBoard.Length; board++) {
          List&lt;int&gt; 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;
  }
  </code></pre>
  <p>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.</p>
  <p>Any idea why this approach might be returning bad moves at times?</p>
  
Tags: <engines><programming>
Title: How can I ensure my transposition table is working correctly?
ThreadText: # How can I ensure my transposition table is working correctly?
  
  (Asked by: username_0 on 2023-08-26)
  
  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?
  
  **Tags:** engines, programming
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-09-01. Score: 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.
  
  > **Comments:**
  > **username_0**: 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: http://www.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.  
  > **username_1**: 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.  
  > **username_0**: 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): https://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.  
  > **username_1**: 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.  
  > **username_0**: 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.  
  
  ---
  
  