From 8e47b8f9f8a017f25a1c9a9baba05b0bf9b12d2d Mon Sep 17 00:00:00 2001
From: Adam <adammegarules1@gmail.com>
Date: Sun, 16 Aug 2026 11:22:34 +0200
Subject: perf(draw) instead of having a hash map for three fold repetion check
 now we have

---
 src/board/board.cpp | 44 ++++++++++++++++++++++++++++++++------------
 src/board/board.hpp |  5 ++++-
 2 files changed, 36 insertions(+), 13 deletions(-)

(limited to 'src/board')

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;
-- 
cgit v1.2.3