Answers.Body: <p>There were three main issues - I was foolishly using unsigned long as a variable to store the hash instead of unsigned long long. I wrote a functionto detect hash collisions, and there were plenty. Lastly, there were two bugs with the hash generation that I have now fixed.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-21T07:56:26.207Z
Answers.Text: Note that experiments on SF show that you should be able to go down to 20 bits of hash without notable performance degradation.
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-20T20:09:46.780Z
Answers.LastActivityDate: 2021-03-20T20:09:46.780Z
Answers.UserDisplayName: Paul
Body: <p>I have implemented a simple variant of Zobrist keys to store and look up positional data, but whenever I let my engine play itself with either white or black using hashtables and the opponent doesn't, the player using the hashtable consistently performs worse.</p>
  <p>I can rule out a significant computational load due to the hash key updates and storing/retrieval of data - the kilonodes per second are more or less within the same range. Secondly, I observe that in the endgame, a 9 ply depth of the player not using hashtables is met with about 11 plies for the player using hashtables. In the early game, there is almost no discernible advantage in search depth (<strong>which is a side question - does that seem sensible?</strong>). Still, given the increased endgame depth, one would expect a systematic benefit for the player using hashtables - all else being equal (no quiescence search, same allocated time for iterative deepening), that is.</p>
  <p>Hence, I believe that the error has to do with storage or retrieval of data; or incorrect hash keys. The latter seems implausible based on tests. I would appreciate if anyone can point out a potential problem with the hashtable implementation.</p>
  <p>Here is the code to insert data into the hashtable, which is called at each node when alpha beta returns a value:</p>
  <pre><code>void Hashtable::setHashData(int distanceToLeaf, int value, int alpha, int beta, std::tuple&lt;char, char, char, char&gt; preferredMove) {
      unsigned long index = Hashtable::hash % Hashtable::HASH_SIZE;
      if (((value &gt; alpha) &amp;&amp; (value &lt; beta)) || (alpha == beta)) {
          Hashtable::table[index].type = NodeType::Exact;
          Hashtable::table[index].value = value;
      }
      else if (value &gt;= beta) {
          Hashtable::table[index].type = NodeType::Upper;
          Hashtable::table[index].value = value;
      }
      else if (value &lt;= alpha) {
          Hashtable::table[index].type = NodeType::Lower;
          Hashtable::table[index].value = value;
      }
  
      Hashtable::table[index].distanceToLeaf = distanceToLeaf;
      Hashtable::table[index].zobristKey = Hashtable::hash;
      Hashtable::table[index].preferredMove = preferredMove;
  }
  </code></pre>
  <p>Here is the part of the alpha-beta-search function that invokes the hashtable. This part is executed <em>before</em> the possible moves at this position are determined and alphabeta is called recursively:</p>
  <pre><code>int Engine::alphaBeta(ChessBoard* board, Colour colour, char depth, int alpha, int beta) 
  [...]
  if (useHashtable) {
      HashData data = Engine::transpos_table.getHashData();
      if ((data.zobristKey == Engine::transpos_table.hash) &amp;&amp; (data.distanceToLeaf &gt;= (depthLimit - depth))) {
          Engine::transpos_table.hashHits++;
  
          if ((data.type == NodeType::Exact))
              return data.value;
          else if ((data.type == NodeType::Lower) &amp;&amp; (data.value &lt; beta))
              beta = data.value;
          else if ((data.type == NodeType::Upper) &amp;&amp; (data.value &gt; alpha))
              alpha = data.value;
  
          if (alpha &gt;= beta) return data.value;
  
          if (colour == Colour::White)
              return Engine::alphaBeta_preferredMove(board, Colour::White, depth, alpha, beta, data.preferredMove);
          else
              return Engine::alphaBeta_preferredMove(board, Colour::Black, depth, alpha, beta, data.preferredMove);
      }
  }
  </code></pre>
  <p>The idea being that I either have searched a position fully (exact node- I can just return the value), or I can update alpha or beta if they provide an improvement of an earlier bound. Moreover, I can store the preferred move (may not be the best one due to an early cutoff) and pass that to an alpha beta implementation that executes this preferred move first (Engine::alphaBeta_preferredMove).</p>
  <p>Lastly, here is the code for updating the Zobrist key given a move (this has been tested to be self-inverse, but perhaps there is still a problem somewhere - and apologies for the lack of case statements, and the nasty std::get&lt;&gt; notation). Obviously, this gets called every time a move is made, and every time a move is unmade. &quot;hk_[...]&quot; are (arrays of) random bitstrings per board feature that are initialized at the start.</p>
  <pre><code>    void Hashtable::updateHash(ChessBoard* board, MoveData move) {
      if (move.pieceMoved-&gt;colour == Colour::White) {
          hash ^= hk_blackToMove;
          if (move.pieceMoved-&gt;getPieceType() == PieceType::Pawn)
              hash = hash ^ hk_whitePawn[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whitePawn[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Knight)
              hash = hash ^ hk_whiteKnight[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whiteKnight[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Bishop)
              hash = hash ^ hk_whiteBishop[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whiteBishop[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Rook)
              hash = hash ^ hk_whiteRook[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whiteRook[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Queen)
              hash = hash ^ hk_whiteQueen[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whiteQueen[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::King)
              hash = hash ^ hk_whiteKing[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_whiteKing[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          if (move.pieceTaken != nullptr) {
              if (move.pieceTaken-&gt;getPieceType() == PieceType::Pawn)
                  hash = hash ^ hk_blackPawn[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Knight)
                  hash = hash ^ hk_blackKnight[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Bishop)
                  hash = hash ^ hk_blackBishop[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Rook)
                  hash = hash ^ hk_blackRook[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Queen)
                  hash = hash ^ hk_blackQueen[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::King)
                  hash = hash ^ hk_blackKing[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          }
          if (move.isWhiteLRookCastling)
              hash = hash ^ hk_whiteLRookCastling;
          else if (move.isWhiteRRookCastling)
              hash = hash ^ hk_whiteRRookCastling;
      }
      else {
          hash = hash ^ hk_whiteToMove;
          if (move.pieceMoved-&gt;getPieceType() == PieceType::Pawn)
              hash = hash ^ hk_blackPawn[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackPawn[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Knight)
              hash = hash ^ hk_blackKnight[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackKnight[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Bishop)
              hash = hash ^ hk_blackBishop[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackBishop[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Rook)
              hash = hash ^ hk_blackRook[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackRook[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::Queen)
              hash = hash ^ hk_blackQueen[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackQueen[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          else if (move.pieceMoved-&gt;getPieceType() == PieceType::King)
              hash = hash ^ hk_blackKing[std::get&lt;0&gt;(move.orig)][std::get&lt;1&gt;(move.orig)] ^ hk_blackKing[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          if (move.pieceTaken != nullptr) {
              if (move.pieceTaken-&gt;getPieceType() == PieceType::Pawn)
                  hash = hash ^ hk_whitePawn[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Knight)
                  hash = hash ^ hk_whiteKnight[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Bishop)
                  hash = hash ^ hk_whiteBishop[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Rook)
                  hash = hash ^ hk_whiteRook[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::Queen)
                  hash = hash ^ hk_whiteQueen[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
              else if (move.pieceTaken-&gt;getPieceType() == PieceType::King)
                  hash = hash ^ hk_whiteKing[std::get&lt;0&gt;(move.dest)][std::get&lt;1&gt;(move.dest)];
          }
          if (move.isBlackLRookCastling)
              hash = hash ^ hk_blackLRookCastling;
          else if (move.isBlackRRookCastling)
              hash = hash ^ hk_blackRRookCastling;
      }
      if (move.prevEnPassantPawn != std::tuple&lt;char, char&gt;(127, 127))
          hash = hash ^ hk_enPassantSquare[std::get&lt;0&gt;(move.prevEnPassantPawn)][std::get&lt;1&gt;(move.prevEnPassantPawn)];
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T16:16:09.270Z
Comments.Text: Have you measured or counted how often a hash collision occurs? I don't see any method to deal with hash collisions aside from eviction, and the hash being based on `Hashtable::hash` seems suspicious (it should be a function based on the key, but I'm not sure the definition of `Hashtable::hash`)
Comments.UserDisplayName: nanofarad
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-20T20:08:27.607Z
Comments.Text: Thanks - hash collisions were the main issue. I will post an answer.
Comments.UserDisplayName: Paul
Tags: <engines>
Title: Hashtable decreases playstrength
ThreadText: # Hashtable decreases playstrength
  
  (Asked by: username_0 on 2021-03-15)
  
  I have implemented a simple variant of Zobrist keys to store and look up positional data, but whenever I let my engine play itself with either white or black using hashtables and the opponent doesn't, the player using the hashtable consistently performs worse.
  
  I can rule out a significant computational load due to the hash key updates and storing/retrieval of data - the kilonodes per second are more or less within the same range. Secondly, I observe that in the endgame, a 9 ply depth of the player not using hashtables is met with about 11 plies for the player using hashtables. In the early game, there is almost no discernible advantage in search depth (**which is a side question - does that seem sensible?**). Still, given the increased endgame depth, one would expect a systematic benefit for the player using hashtables - all else being equal (no quiescence search, same allocated time for iterative deepening), that is.
  
  Hence, I believe that the error has to do with storage or retrieval of data; or incorrect hash keys. The latter seems implausible based on tests. I would appreciate if anyone can point out a potential problem with the hashtable implementation.
  
  Here is the code to insert data into the hashtable, which is called at each node when alpha beta returns a value:
  
  ```
  void Hashtable::setHashData(int distanceToLeaf, int value, int alpha, int beta, std::tuple<char, char, char, char> preferredMove) {
      unsigned long index = Hashtable::hash % Hashtable::HASH_SIZE;
      if (((value > alpha) && (value < beta)) || (alpha == beta)) {
          Hashtable::table[index].type = NodeType::Exact;
          Hashtable::table[index].value = value;
      }
      else if (value >= beta) {
          Hashtable::table[index].type = NodeType::Upper;
          Hashtable::table[index].value = value;
      }
      else if (value <= alpha) {
          Hashtable::table[index].type = NodeType::Lower;
          Hashtable::table[index].value = value;
      }
  
      Hashtable::table[index].distanceToLeaf = distanceToLeaf;
      Hashtable::table[index].zobristKey = Hashtable::hash;
      Hashtable::table[index].preferredMove = preferredMove;
  }
  
  ```
  
  Here is the part of the alpha-beta-search function that invokes the hashtable. This part is executed *before* the possible moves at this position are determined and alphabeta is called recursively:
  
  ```
  int Engine::alphaBeta(ChessBoard* board, Colour colour, char depth, int alpha, int beta) 
  [...]
  if (useHashtable) {
      HashData data = Engine::transpos_table.getHashData();
      if ((data.zobristKey == Engine::transpos_table.hash) && (data.distanceToLeaf >= (depthLimit - depth))) {
          Engine::transpos_table.hashHits++;
  
          if ((data.type == NodeType::Exact))
              return data.value;
          else if ((data.type == NodeType::Lower) && (data.value < beta))
              beta = data.value;
          else if ((data.type == NodeType::Upper) && (data.value > alpha))
              alpha = data.value;
  
          if (alpha >= beta) return data.value;
  
          if (colour == Colour::White)
              return Engine::alphaBeta_preferredMove(board, Colour::White, depth, alpha, beta, data.preferredMove);
          else
              return Engine::alphaBeta_preferredMove(board, Colour::Black, depth, alpha, beta, data.preferredMove);
      }
  }
  
  ```
  
  The idea being that I either have searched a position fully (exact node- I can just return the value), or I can update alpha or beta if they provide an improvement of an earlier bound. Moreover, I can store the preferred move (may not be the best one due to an early cutoff) and pass that to an alpha beta implementation that executes this preferred move first (Engine::alphaBeta\_preferredMove).
  
  Lastly, here is the code for updating the Zobrist key given a move (this has been tested to be self-inverse, but perhaps there is still a problem somewhere - and apologies for the lack of case statements, and the nasty std::get<> notation). Obviously, this gets called every time a move is made, and every time a move is unmade. "hk\_[...]" are (arrays of) random bitstrings per board feature that are initialized at the start.
  
  ```
      void Hashtable::updateHash(ChessBoard* board, MoveData move) {
      if (move.pieceMoved->colour == Colour::White) {
          hash ^= hk_blackToMove;
          if (move.pieceMoved->getPieceType() == PieceType::Pawn)
              hash = hash ^ hk_whitePawn[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whitePawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Knight)
              hash = hash ^ hk_whiteKnight[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Bishop)
              hash = hash ^ hk_whiteBishop[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Rook)
              hash = hash ^ hk_whiteRook[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Queen)
              hash = hash ^ hk_whiteQueen[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::King)
              hash = hash ^ hk_whiteKing[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
          if (move.pieceTaken != nullptr) {
              if (move.pieceTaken->getPieceType() == PieceType::Pawn)
                  hash = hash ^ hk_blackPawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Knight)
                  hash = hash ^ hk_blackKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Bishop)
                  hash = hash ^ hk_blackBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Rook)
                  hash = hash ^ hk_blackRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Queen)
                  hash = hash ^ hk_blackQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::King)
                  hash = hash ^ hk_blackKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
          }
          if (move.isWhiteLRookCastling)
              hash = hash ^ hk_whiteLRookCastling;
          else if (move.isWhiteRRookCastling)
              hash = hash ^ hk_whiteRRookCastling;
      }
      else {
          hash = hash ^ hk_whiteToMove;
          if (move.pieceMoved->getPieceType() == PieceType::Pawn)
              hash = hash ^ hk_blackPawn[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackPawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Knight)
              hash = hash ^ hk_blackKnight[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Bishop)
              hash = hash ^ hk_blackBishop[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Rook)
              hash = hash ^ hk_blackRook[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::Queen)
              hash = hash ^ hk_blackQueen[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
          else if (move.pieceMoved->getPieceType() == PieceType::King)
              hash = hash ^ hk_blackKing[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
          if (move.pieceTaken != nullptr) {
              if (move.pieceTaken->getPieceType() == PieceType::Pawn)
                  hash = hash ^ hk_whitePawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Knight)
                  hash = hash ^ hk_whiteKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Bishop)
                  hash = hash ^ hk_whiteBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Rook)
                  hash = hash ^ hk_whiteRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::Queen)
                  hash = hash ^ hk_whiteQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
              else if (move.pieceTaken->getPieceType() == PieceType::King)
                  hash = hash ^ hk_whiteKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
          }
          if (move.isBlackLRookCastling)
              hash = hash ^ hk_blackLRookCastling;
          else if (move.isBlackRRookCastling)
              hash = hash ^ hk_blackRRookCastling;
      }
      if (move.prevEnPassantPawn != std::tuple<char, char>(127, 127))
          hash = hash ^ hk_enPassantSquare[std::get<0>(move.prevEnPassantPawn)][std::get<1>(move.prevEnPassantPawn)];
  }
  
  ```
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: Have you measured or counted how often a hash collision occurs? I don't see any method to deal with hash collisions aside from eviction, and the hash being based on `Hashtable::hash` seems suspicious (it should be a function based on the key, but I'm not sure the definition of `Hashtable::hash`)  
  > **username_0**: Thanks - hash collisions were the main issue. I will post an answer.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-03-20. Score: 3 | Accepted answer
  
  There were three main issues - I was foolishly using unsigned long as a variable to store the hash instead of unsigned long long. I wrote a functionto detect hash collisions, and there were plenty. Lastly, there were two bugs with the hash generation that I have now fixed.
  
  > **Comments:**
  > **username_2**: Note that experiments on SF show that you should be able to go down to 20 bits of hash without notable performance degradation.  
  
  ---
  
  