zobrist hashing

11 files changed, 94 insertions, 40 deletions

diff --git a/include/bitboard.h b/include/bitboard.h
index 3e1118d..b1ddcf0 100644
--- a/include/bitboard.h
+++ b/include/bitboard.h
@@ -27,11 +27,13 @@ enum {
   WHITE_LONG_CASTLE   =  1  <<  1,
   BLACK_SHORT_CASTLE  =  1  <<  2,
   BLACK_LONG_CASTLE   =  1  <<  3,
+  CASTLE_COUNT = 4,
 };
 
 enum {
   WHITE_TURN,
   BLACK_TURN,
+  TURN_COUNT,
 };
 
 #define BITMASK_RANK_1 255ULL
diff --git a/include/engine/magic.h b/include/engine/magic.h
index 7f584a9..1c9f303 100644
--- a/include/engine/magic.h
+++ b/include/engine/magic.h
@@ -3,6 +3,7 @@
 
 #include "ints.h"
 #include "bitboard.h"
+#include "random.h"
 
 typedef struct {
   bitboard_t mask;
diff --git a/include/engine/moves.h b/include/engine/moves.h
index 755a77a..cd71cdc 100644
--- a/include/engine/moves.h
+++ b/include/engine/moves.h
@@ -68,6 +68,7 @@ void get_moves(moves_t *moves, position_t position);
 
 bool square_attacked(position_t position, square_t square, u8 by_color);
 void get_legal_moves(moves_t *moves, position_t position);
+int find_piece_on_square(position_t* p, int square);
 
 #ifdef MOVES_INTERNAL
 void __forloop_rook_moves_gen(
diff --git a/include/engine/transposition_table.h b/include/engine/transposition_table.h
new file mode 100644
index 0000000..f06ddbe
--- /dev/null
+++ b/include/engine/transposition_table.h
@@ -0,0 +1,16 @@
+#ifndef TRANSPOSITION_TABLE_H
+#define TRANSPOSITION_TABLE_H
+
+#include "bitboard.h"
+
+static struct zobrist_keys {
+  u64 piece[PIECE_TYPE_COUNT][64];
+  u64 castle[CASTLE_COUNT];
+  u64 turn[TURN_COUNT];
+  u64 en_passant[64];
+} zobrist_keys;
+
+void transposition_table_init();
+u64 zobrist_hash(position_t position);
+
+#endif // TRANSPOSITION_TABLE_H
diff --git a/include/random.h b/include/random.h
new file mode 100644
index 0000000..633c015
--- /dev/null
+++ b/include/random.h
@@ -0,0 +1,10 @@
+#ifndef RANDOM_H
+#define RANDOM_H
+
+#include "ints.h"
+
+u64 random_u64();
+u64 random_magic();
+
+#endif // RANDOM_H
+
diff --git a/src/engine.c b/src/engine.c
index a656a79..dc6940a 100644
--- a/src/engine.c
+++ b/src/engine.c
@@ -1,3 +1,4 @@
 #include "engine/threads.c"
 #include "engine/thread.c"
 #include "engine/moves.c"
+#include "engine/transposition_table.c"
diff --git a/src/engine/moves/magic.c b/src/engine/moves/magic.c
index 43f4a32..74b2c72 100644
--- a/src/engine/moves/magic.c
+++ b/src/engine/moves/magic.c
@@ -1,4 +1,5 @@
 #include "engine/magic.h"
+#include "random.h"
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
@@ -8,19 +9,6 @@ static magic_t bishop_table[64];
 static bitboard_t *rook_attacks_flat;
 static bitboard_t *bishop_attacks_flat;
 
-static u64 rng_state = 1070399;
-
-static u64 random_u64(void) {
-  rng_state ^= rng_state << 13;
-  rng_state ^= rng_state >> 7;
-  rng_state ^= rng_state << 17;
-  return rng_state;
-}
-
-static u64 random_magic(void) {
-  return random_u64() & random_u64() & random_u64();
-}
-
 static bitboard_t compute_rook_mask(int sq) {
   bitboard_t mask = 0;
   int rank = sq / 8, file = sq % 8;
diff --git a/src/engine/transposition_table.c b/src/engine/transposition_table.c
new file mode 100644
index 0000000..1afbc81
--- /dev/null
+++ b/src/engine/transposition_table.c
@@ -0,0 +1,44 @@
+#include "engine/transposition_table.h"
+
+void transposition_table_init() {
+  for (int i = 0; i < PIECE_TYPE_COUNT; i++) {
+    for (int j = 0; j < 64; j++) {
+      zobrist_keys.piece[i][j] = random_u64();
+    }
+  }
+  for (int i = 0; i < CASTLE_COUNT; i++) {
+    zobrist_keys.castle[i] = random_u64();
+  }
+  for (int i = 0; i < TURN_COUNT; i++) {
+    zobrist_keys.turn[i] = random_u64();
+  }
+  for (int i = 0; i < 64; i++) {
+    zobrist_keys.en_passant[i] = random_u64();
+  }
+}
+
+u64 zobrist_hash(position_t position) {
+  u64 output = 0;
+  for (int i = 0; i < 64; i++) {
+    int piece_type = find_piece_on_square(&position, i);
+    output ^= zobrist_keys.piece[piece_type][i];
+  }
+
+  if (position.castling & WHITE_SHORT_CASTLE) {
+    output ^= zobrist_keys.castle[0];
+  }
+  if (position.castling & WHITE_LONG_CASTLE) {
+    output ^= zobrist_keys.castle[1];
+  }
+  if (position.castling & BLACK_SHORT_CASTLE) {
+    output ^= zobrist_keys.castle[2];
+  }
+  if (position.castling & BLACK_LONG_CASTLE) {
+    output ^= zobrist_keys.castle[3];
+  }
+
+  output ^= zobrist_keys.turn[position.turn];
+  output ^= zobrist_keys.en_passant[position.passantable_file];
+
+  return output;
+}
diff --git a/src/main.c b/src/main.c
index 511943f..6dd5e13 100644
--- a/src/main.c
+++ b/src/main.c
@@ -3,7 +3,7 @@
 #include <stdio.h>
 #include <unistd.h>
 #include <pthread.h>
-#include "fcntl.h"
+#include <fcntl.h>
 
 #include "ipc/state.h"
 #include "ipc/threads.h"
@@ -49,38 +49,12 @@ skip_refresh:
       !(is_stop = ipc_state_is_event(&ipc_state, EVENT_ENGINE_STOP))
     );
     if (is_stop) {
-      printf("ENDED\n");
       threads_cleanup(&engine_threads);
       ipc_state_set_event(&ipc_state, EVENT_UCI_RUNNING);
       goto waiting_for_go;
     }
     threads_go_loop(&engine_threads);
     ipc_state_set_event(&ipc_state, EVENT_UCI_RUNNING);
-    // if (atomic_load(&ipc_state->state.quit)) break;
-    // if (atomic_load(&ipc_state->state.cleanup)) {
-    //   set_threads(&engine_threads, 0);
-    //   for (int i = 0; i < engine_threads.count; i++) {
-    //     engine_threads.args[i].stop = -1;
-    //   }
-    // }
-    // if (atomic_load(&ipc_state->state.go)) {
-    //   printf("going\n");
-    //   engine_threads.sharing_position = ipc_state->state.position;
-    //   engine_threads.go_args = (struct go_args*)ipc_state->state.go_args;
-    //   set_threads(&engine_threads, ipc_state->state.threads);
-    //   atomic_store(&ipc_state->state.go, 0);
-    //   atomic_store(&ipc_state->state.go_ready_receive, 1);
-    // }
-    // if (atomic_load(&ipc_state->state.stop)) {
-    //   printf("stopping\n");
-    //   send_stop_signal(&engine_threads);
-    //   if (!all_stopped(&engine_threads)) continue;
-    //   set_threads(&engine_threads, 0);
-    //   for (int i = 0; i < engine_threads.count; i++) {
-    //     engine_threads.args[i].stop = -1;
-    //   }
-    //   atomic_store(&ipc_state->state.stop, 0);
-    // }
   }
 
   ipc_state_deinit(&ipc_state);
@@ -91,3 +65,4 @@ skip_refresh:
 
 #include "fen.c"
 #include "bitboard.c"
+#include "random.c"
diff --git a/src/random.c b/src/random.c
new file mode 100644
index 0000000..df55d84
--- /dev/null
+++ b/src/random.c
@@ -0,0 +1,14 @@
+#include "random.h"
+
+static u64 rng_state = 1070399;
+
+u64 random_u64() {
+  rng_state ^= rng_state << 13;
+  rng_state ^= rng_state >> 7;
+  rng_state ^= rng_state << 17;
+  return rng_state;
+}
+
+u64 random_magic() {
+  return random_u64() & random_u64() & random_u64();
+}
diff --git a/tests/main.c b/tests/main.c
index 38eb544..800e80d 100644
--- a/tests/main.c
+++ b/tests/main.c
@@ -49,3 +49,5 @@ int main() {
 
   return return_type;
 }
+
+#include "random.c"