perf(draw) instead of having a hash map for three fold repetion check now we have

6 files changed, 54 insertions, 34 deletions

diff --git a/src/board/board.cpp b/src/board/board.cpp
index 7fe2ff1..c8b29e5 100644
--- a/src/board/board.cpp
+++ b/src/board/board.cpp
@@ -1,4 +1,6 @@
+#include <algorithm>
 #include <cassert>
+#include <cstddef>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
@@ -88,6 +90,30 @@ uint8_t getToValueFromMove(uint16_t move) { return (move >> 8) & 63; };
 Position FindKing(Game *g, bool color) {
   return IndexToPosition(__builtin_ctzll(g->PieceBitboards[color][KING]));
 }
+
+bool isRepetionDraw(uint64_t key, Game *g) {
+  int size = static_cast<int>(g->history.size());
+  if (size < 4) {
+    return false; // draw is imposible if less that 4 moves were played
+  }
+  int start = size - g->halfMoveClock;
+
+  if (start < 0) {
+    return false;
+  }
+  // start can only be smaller than zero in position from fen where
+  // the history is not recorded
+
+  int repetions = 0;
+  for (int i = start; i < size; i++) {
+    uint64_t move = g->history[static_cast<size_t>(i)];
+    if (move == key) {
+      repetions++;
+    }
+  }
+  return repetions >= 3;
+};
+
 Undo MakeMove(uint16_t move, Game *g) {
   uint8_t fromSquare = getFromValueFromMove(move);
   uint8_t toSquare = getToValueFromMove(move);
@@ -132,6 +158,9 @@ Undo MakeMove(uint16_t move, Game *g) {
   } else {
     g->halfMoveClock++;
   }
+  if (g->halfMoveClock >= 100) {
+    g->state = DRAW;
+  }
 
   // Playing enpasstant
   if (piece.type == PAWN && g->canEnpassant &&
@@ -329,15 +358,8 @@ Undo MakeMove(uint16_t move, Game *g) {
 
   undo.ZobristKey = key;
 
-  g->ThreeFoldMap[key]++;
-
-  if (g->ThreeFoldMap[key] >= 3) {
-    g->state = DRAW;
-  }
+  g->history.push_back(key);
 
-  if (g->halfMoveClock >= 100) {
-    g->state = DRAW;
-  }
   return undo;
 };
 void UndoMove(Undo undo, Game *g) {
@@ -395,10 +417,8 @@ void UndoMove(Undo undo, Game *g) {
     }
   }
 
-  g->ThreeFoldMap[undo.ZobristKey] -= 1;
-  if (g->ThreeFoldMap[undo.ZobristKey] <= 0) {
-    g->ThreeFoldMap.erase(undo.ZobristKey);
-  };
+  g->history.pop_back();
+  
   UpdateHelpers(g);
 };
 void UpdateHelpers(Game *g) {
diff --git a/src/board/board.hpp b/src/board/board.hpp
index 133a280..e3692f6 100644
--- a/src/board/board.hpp
+++ b/src/board/board.hpp
@@ -3,6 +3,7 @@
 
 #include <cstdint>
 #include <unordered_map>
+#include <vector>
 
 enum PieceType : std::uint8_t {
   NONEPIECE,
@@ -67,10 +68,12 @@ struct Game {
   Position enPassant;
   bool canEnpassant = false;
   GameState state = TURN;
-  std::unordered_map<uint64_t, int> ThreeFoldMap;
+  std::vector<uint64_t> history;
   std::unordered_map<uint64_t, TranspositionsEntry> *Transpositions = nullptr;
 };
 
+bool isRepetionDraw(uint64_t key, Game *g);
+
 struct Undo {
   Piece movedPiece;
   Piece capturedPiece;
diff --git a/src/bot.cpp b/src/bot.cpp
index 0e959d0..7abe516 100644
--- a/src/bot.cpp
+++ b/src/bot.cpp
@@ -154,10 +154,9 @@ static int search(int depth, Game *b, int alpha, int beta, int ply) {
   }
   const uint64_t gameHash = GenerateZobristKey(b);
 
-  auto repIt = b->ThreeFoldMap.find(gameHash);
-  if (repIt != b->ThreeFoldMap.end() && repIt->second >= 2) {
-    return 0; // repetition -> draw
-  }
+  if (isRepetionDraw(gameHash, b)) {
+    return 0;
+  };
 
   TranspositionsEntry *entry = nullptr;
   if (auto it = b->Transpositions->find(gameHash);
diff --git a/src/moves.cpp b/src/moves.cpp
index 9e45ff5..6299e55 100644
--- a/src/moves.cpp
+++ b/src/moves.cpp
@@ -353,9 +353,6 @@ GameState GetNewGameState(Game *g) {
   if (g->state == DRAW || g->state == WHITE_WON || g->state == BLACK_WON) {
     return g->state;
   }
-  if (g->halfMoveClock >= 100) {
-    g->state = DRAW;
-  }
 
   auto legalMoves = GetLegalMoves(g);
 
diff --git a/src/uci.cpp b/src/uci.cpp
index ff8bc33..b78ffea 100644
--- a/src/uci.cpp
+++ b/src/uci.cpp
@@ -66,20 +66,20 @@ uint16_t UciToMove(const std::string &uci) {
 Game initBoard(
     const std::string &startingFEN,
     std::unordered_map<uint64_t, TranspositionsEntry> *transPositions) {
-  Game b{};
-  b.enPassant = IndexToPosition(0); // default value
-  b.canEnpassant = false;
-  b.state = TURN;
-  b.turn = true;
-  b.halfMoveClock = 0;
-  b.MoveClock = 0;
-  b.Transpositions = transPositions;
-
-  setBoardFen(startingFEN, &b);
-
-  uint64_t key = GenerateZobristKey(&b);
-  b.ThreeFoldMap[key] = 1;
-  return b;
+  Game g{};
+  g.enPassant = IndexToPosition(0); // default value
+  g.canEnpassant = false;
+  g.state = TURN;
+  g.turn = true;
+  g.halfMoveClock = 0;
+  g.MoveClock = 0;
+  g.Transpositions = transPositions;
+
+  setBoardFen(startingFEN, &g);
+
+  uint64_t key = GenerateZobristKey(&g);
+  g.history.push_back(key);
+  return g;
 };
 static void PrintBitboard(uint64_t bb, const std::string &name) {
   std::cout << name << "\n";
diff --git a/src/zobrist.cpp b/src/zobrist.cpp
index 20ac5e9..8c50d3d 100644
--- a/src/zobrist.cpp
+++ b/src/zobrist.cpp
@@ -1,6 +1,7 @@
 #include "zobrist.hpp"
 #include "board/board.hpp"
 
+#include <cstdint>
 #include <random>
 
 uint64_t PieceKeys[2][7][64];