perf(board): making hashing use incremental XORs instead of rebuild from scratch

6 files changed, 72 insertions, 17 deletions

diff --git a/src/board/board.cpp b/src/board/board.cpp
index 81a3c4e..faabfac 100644
--- a/src/board/board.cpp
+++ b/src/board/board.cpp
@@ -142,7 +142,10 @@ static void movePiece(const uint8_t &fromSquare, const Piece &fromPiece,
   }
 
   g->PieceBitboard = g->WhitePieceBitboard | g->BlackPieceBitboard;
+  xorSquare(fromSquare, g);
+  xorSquare(toSquare, g);
   g->pieces[toSquare] = fromPiece;
+  xorSquare(toSquare, g);
   g->pieces[fromSquare] = {.color = false, .type = NONEPIECE};
 };
 
@@ -173,6 +176,8 @@ Undo MakeMove(uint16_t move, Game *g) {
   undo.OldBlackCastleKing = g->blackCastleKing;
   undo.OldBlackCastleQueen = g->blackCastleQueen;
 
+  undo.ZobristKey = g->hash;
+
   // play move
   Piece movingPiece = g->pieces[fromSquare];
   Piece captuaredPiece = g->pieces[toSquare];
@@ -196,6 +201,9 @@ Undo MakeMove(uint16_t move, Game *g) {
   }
 
   // Playing enpasstant
+
+  xorEnpassantKey(g); // remove existing key
+
   if (movingPiece.type == PAWN && g->canEnpassant &&
       IndexToPosition(toSquare) == g->enPassant) {
     Position capturedPawn = IndexToPosition(toSquare);
@@ -217,6 +225,7 @@ Undo MakeMove(uint16_t move, Game *g) {
     }
     g->PieceBitboard = g->WhitePieceBitboard | g->BlackPieceBitboard;
 
+    xorSquare(static_cast<uint8_t>(PositionToIndex(capturedPawn)), g);
     g->pieces[PositionToIndex(capturedPawn)] = {.color = false,
                                                 .type = NONEPIECE};
   }
@@ -236,10 +245,6 @@ Undo MakeMove(uint16_t move, Game *g) {
     };
   }
 
-  // promotion is always set and should only be aplied when reached final rank
-  // (default: knight)
-  // because we use only two bits of memory for promotion we cant represent a
-  // none type so we always have knight set and only it last rank and its pawn
   if (movingPiece.type == PAWN &&
       IndexToPosition(toSquare).rank == (movingPiece.color ? 7 : 0)) {
     movingPiece.type = promotion;
@@ -269,7 +274,7 @@ Undo MakeMove(uint16_t move, Game *g) {
       rookFrom.file = 0;
 
       rookTo.file = 3;
-    }
+    };
     uint64_t from = 1ULL << PositionToIndex(rookFrom);
     uint64_t to = 1ULL << PositionToIndex(rookTo);
 
@@ -283,16 +288,22 @@ Undo MakeMove(uint16_t move, Game *g) {
     }
     g->PieceBitboard = g->WhitePieceBitboard | g->BlackPieceBitboard;
 
+    xorSquare(static_cast<uint8_t>(PositionToIndex(rookFrom)), g);
     g->pieces[PositionToIndex(rookTo)] = g->pieces[PositionToIndex(rookFrom)];
+    xorSquare(static_cast<uint8_t>(PositionToIndex(rookTo)), g);
     g->pieces[PositionToIndex(rookFrom)] = {.type = NONEPIECE};
   }
 
   //  remove castling right if king has moved
   if (movingPiece.type == KING) {
     if (movingPiece.color) {
+      xorCastleKey(true, true, g);
+      xorCastleKey(true, false, g);
       g->whiteCastleKing = false;
       g->whiteCastleQueen = false;
     } else {
+      xorCastleKey(false, true, g);
+      xorCastleKey(false, false, g);
       g->blackCastleKing = false;
       g->blackCastleQueen = false;
     }
@@ -302,38 +313,45 @@ Undo MakeMove(uint16_t move, Game *g) {
   if (movingPiece.type == ROOK) {
     if (movingPiece.color) { // White
       if (fromSquare == 0) { // a1
+        xorCastleKey(true, false, g);
         g->whiteCastleQueen = false;
       }
       if (fromSquare == 7) { // h1
+        xorCastleKey(true, true, g);
         g->whiteCastleKing = false;
       }
     } else {                     // Black
       if (fromSquare == 7 * 8) { // a8
+        xorCastleKey(false, false, g);
         g->blackCastleQueen = false;
       }
 
       if (fromSquare == 7 * 9) { // h8
+        xorCastleKey(false, true, g);
         g->blackCastleKing = false;
       }
     }
   }
 
-  // this part is written with ai
   if (captuaredPiece.type == ROOK) {
     if (captuaredPiece.color) { // White rook captured
       if (toSquare == 0) {      // a1
+        xorCastleKey(true, false, g);
         g->whiteCastleQueen = false;
       }
       if (toSquare == 7) { // h1
+        xorCastleKey(true, true, g);
         g->whiteCastleKing = false;
       }
     } else {                   // Black rook captured
       if (toSquare == 7 * 8) { // a8
+        xorCastleKey(false, false, g);
         g->blackCastleQueen = false;
       }
 
       if (toSquare == 7 * 9) {
         // h8
+        xorCastleKey(false, true, g);
         g->blackCastleKing = false;
       }
     }
@@ -344,13 +362,10 @@ Undo MakeMove(uint16_t move, Game *g) {
 
   // changing who turn it is
   g->turn = !g->turn;
+  xorSidekey(g);      // toggle the side key
+  xorEnpassantKey(g); // add new en passant key
 
-  // 3 fold check
-  uint64_t key = GenerateZobristKey(g);
-
-  undo.ZobristKey = key;
-
-  g->history.push_back(key);
+  g->history.push_back(g->hash);
 
   return undo;
 };
@@ -432,4 +447,6 @@ void UndoMove(Undo undo, Game *g) {
   g->history.pop_back();
 
   g->PieceBitboard = g->WhitePieceBitboard | g->BlackPieceBitboard;
+
+  g->hash = undo.ZobristKey;
 };
diff --git a/src/board/board.hpp b/src/board/board.hpp
index a64289e..2b3ac6a 100644
--- a/src/board/board.hpp
+++ b/src/board/board.hpp
@@ -68,6 +68,7 @@ struct Game {
   Position enPassant;
   bool canEnpassant = false;
   GameState state = TURN;
+  uint64_t hash = 0;
   std::vector<uint64_t> history;
   std::unordered_map<uint64_t, TranspositionsEntry> *Transpositions = nullptr;
 };
diff --git a/src/bot.cpp b/src/bot.cpp
index e9b0b4d..969606e 100644
--- a/src/bot.cpp
+++ b/src/bot.cpp
@@ -171,14 +171,12 @@ static int search(int depth, Game *b, int alpha, int beta, int ply) {
       return 0;
     }
   }
-  const uint64_t gameHash = GenerateZobristKey(b);
-
-  if (isRepetionDraw(gameHash, b)) {
+  if (isRepetionDraw(b->hash, b)) {
     return 0;
   };
 
   TranspositionsEntry *entry = nullptr;
-  if (auto it = b->Transpositions->find(gameHash);
+  if (auto it = b->Transpositions->find(b->hash);
       it != b->Transpositions->end()) {
     entry = &it->second;
     if (entry->depth >= depth) {
@@ -241,7 +239,7 @@ static int search(int depth, Game *b, int alpha, int beta, int ply) {
       flag = UPPERBOUND;
     }
 
-    (*b->Transpositions)[gameHash] = {
+    (*b->Transpositions)[b->hash] = {
         .depth = depth, .Eval = bestScore, .flag = flag, .bestMove = bestMove};
   }
   return bestScore;
diff --git a/src/uci.cpp b/src/uci.cpp
index 812a0cd..6e30014 100644
--- a/src/uci.cpp
+++ b/src/uci.cpp
@@ -96,6 +96,8 @@ Game initBoard(
 
   uint64_t key = GenerateZobristKey(&g);
   g.history.push_back(key);
+
+  g.hash = key;
   return g;
 };
 static void PrintBitboard(uint64_t bb, const std::string &name) {
diff --git a/src/zobrist.cpp b/src/zobrist.cpp
index c06f1a2..afef3e6 100644
--- a/src/zobrist.cpp
+++ b/src/zobrist.cpp
@@ -348,6 +348,39 @@ void InitZobrist() {
   SideKey = PolyglotRandom64[idx];
 }
 
+void xorCastleKey(bool color, bool IS_KING_SIDE, Game *g) {
+  const bool WHITE = true;
+
+  if (color == WHITE && IS_KING_SIDE && g->whiteCastleKing) {
+    g->hash ^= CastleKeys[0];
+  };
+  if (color == WHITE && !IS_KING_SIDE && g->whiteCastleQueen) {
+    g->hash ^= CastleKeys[1];
+  };
+  if (color == !WHITE && IS_KING_SIDE && g->blackCastleKing) {
+    g->hash ^= CastleKeys[2];
+  };
+  if (color == !WHITE && !IS_KING_SIDE && g->blackCastleQueen) {
+    g->hash ^= CastleKeys[3];
+  };
+}
+void xorSidekey(Game *g) { g->hash ^= SideKey; }
+void xorEnpassantKey(Game *g) {
+  if (g->canEnpassant && IsEnpassantLegal(g)) {
+    g->hash ^= EnPassantKeys[g->enPassant.file];
+  }
+}
+void xorSquare(uint8_t square, Game *g) {
+  Piece p = g->pieces[square];
+  if (p.type == NONEPIECE) {
+    return;
+  }
+  g->hash ^= PieceKeys[p.color][p.type][square];
+}
+
+/*
+ * should be only called at start of game
+ */
 uint64_t GenerateZobristKey(Game *b) {
   uint64_t key = 0;
 
diff --git a/src/zobrist.hpp b/src/zobrist.hpp
index e23facf..b72b0f2 100644
--- a/src/zobrist.hpp
+++ b/src/zobrist.hpp
@@ -5,3 +5,7 @@ struct Game;
 
 void InitZobrist();
 uint64_t GenerateZobristKey(Game *b);
+void xorCastleKey(bool color, bool IS_KING_SIDE, Game *g);
+void xorSidekey(Game *g);
+void xorEnpassantKey(Game *g);
+void xorSquare(uint8_t square, Game *g);
\ No newline at end of file