5 files changed, 96 insertions, 0 deletions
diff --git a/src/board.cpp b/src/board.cpp
index 0698571..e058df4 100644
--- a/src/board.cpp
+++ b/src/board.cpp
@@ -1,5 +1,6 @@
 #include "board.hpp"
 #include "bot.hpp"
+#include "zobrist.hpp"
 #include <cassert>
 #include <cstdio>
 #include <iostream>
@@ -143,6 +144,14 @@ void PlayMove(Move move, Game *b) {
   }
   b->pieces[PositionToIndex(move.To)] = piece;
   b->pieces[PositionToIndex(move.From)] = {false, NONE, false};
+
   b->turn = !b->turn;
+
+  uint64_t key = GenerateZobristKey(b);
+
+  b->ThreeFoldMap[key]++;
+  if (b->ThreeFoldMap[key] >= 3) {
+    b->state = DRAW;
+  }
 };
 int PositionToIndex(Position i) { return i.rank * 8 + i.file; }
diff --git a/src/board.hpp b/src/board.hpp
index 1c53827..592b438 100644
--- a/src/board.hpp
+++ b/src/board.hpp
@@ -3,6 +3,7 @@
 
 #include <cstdint>
 #include <string>
+#include <unordered_map>
 enum PieceType {
   NONE,
   PAWN,
@@ -44,6 +45,7 @@ struct Game {
   Position enPassant;
   bool canEnpassant = 0;
   GameState state = TURN;
+  std::unordered_map<uint64_t, int> ThreeFoldMap;
 };
 
 struct Move {
diff --git a/src/main.cpp b/src/main.cpp
index dea578b..ddeb304 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -2,6 +2,7 @@
 #include "fen.hpp"
 #include "moves.hpp"
 #include "uci.hpp"
+#include "zobrist.hpp"
 #include <cstdio>
 #include <cstdlib>
 #include <ctime>
@@ -38,6 +39,7 @@ Game initBoard(string startingFEN) {
 };
 
 int main(int argc, char **argv) {
+  InitZobrist();
   srand(time(0));
   if (argc < 1 || argc > 2) {
     printf("wrong arg count, use: ./chess [--repl for debugging]\n");
diff --git a/src/zobrist.cpp b/src/zobrist.cpp
new file mode 100644
index 0000000..b41b6c6
--- /dev/null
+++ b/src/zobrist.cpp
@@ -0,0 +1,72 @@
+#include "zobrist.hpp"
+#include "board.hpp"
+
+#include <random>
+
+uint64_t PieceKeys[2][7][64];
+uint64_t SideKey;
+uint64_t CastleKeys[16];
+uint64_t EnPassantKeys[8];
+
+void InitZobrist() {
+  std::mt19937_64 rng(1234567); // fixed seed
+
+  for (int color = 0; color < 2; color++) {
+    for (int piece = 0; piece < 7; piece++) {
+      for (int square = 0; square < 64; square++) {
+        PieceKeys[color][piece][square] = rng();
+      }
+    }
+  }
+
+  SideKey = rng();
+
+  for (int i = 0; i < 16; i++) {
+    CastleKeys[i] = rng();
+  }
+
+  for (int i = 0; i < 8; i++) {
+    EnPassantKeys[i] = rng();
+  }
+}
+
+uint64_t GenerateZobristKey(Game *b) {
+  uint64_t key = 0;
+
+  for (int square = 0; square < 64; square++) {
+    Piece p = b->pieces[square];
+
+    if (p.type == NONE)
+      continue;
+
+    key ^= PieceKeys[p.color][p.type][square];
+  }
+
+  // side to move
+  if (b->turn)
+    key ^= SideKey;
+
+  // castling
+  int castle = 0;
+
+  if (b->castle.find('K') != std::string::npos)
+    castle |= 1;
+
+  if (b->castle.find('Q') != std::string::npos)
+    castle |= 2;
+
+  if (b->castle.find('k') != std::string::npos)
+    castle |= 4;
+
+  if (b->castle.find('q') != std::string::npos)
+    castle |= 8;
+
+  key ^= CastleKeys[castle];
+
+  // en passant
+  if (b->canEnpassant) {
+    key ^= EnPassantKeys[b->enPassant.file];
+  }
+
+  return key;
+}
diff --git a/src/zobrist.hpp b/src/zobrist.hpp
new file mode 100644
index 0000000..8de9d42
--- /dev/null
+++ b/src/zobrist.hpp
@@ -0,0 +1,11 @@
+#pragma once
+#include "board.hpp"
+#include <cstdint>
+
+extern uint64_t PieceKeys[2][7][64];
+extern uint64_t SideKey;
+extern uint64_t CastleKeys[16];
+extern uint64_t EnPassantKeys[8];
+
+void InitZobrist();
+uint64_t GenerateZobristKey(Game *b);