ttable lookup & probe

5 files changed, 134 insertions, 61 deletions

diff --git a/include/engine/transposition_table.h b/include/engine/transposition_table.h
deleted file mode 100644
index f06ddbe..0000000
--- a/include/engine/transposition_table.h
+++ /dev/null
@@ -1,16 +0,0 @@
-#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/engine/ttable.h b/include/engine/ttable.h
new file mode 100644
index 0000000..2ee1a5c
--- /dev/null
+++ b/include/engine/ttable.h
@@ -0,0 +1,43 @@
+#ifndef TTABLE_H
+#define TTABLE_H
+
+#include "bitboard.h"
+
+#define TABLE_BITS 24
+#define TABLE_SIZE (1ULL << TABLE_BITS)
+#define MASK (TABLE_SIZE - 1)
+#define TT_BUCKET_SIZE 4
+
+static struct zobrist_keys {
+  u64 piece[PIECE_TYPE_COUNT][64];
+  u64 castle[CASTLE_COUNT];
+  u64 turn[TURN_COUNT];
+  u64 en_passant[64];
+} zobrist_keys;
+
+enum { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
+typedef struct {
+  atomic_uint_fast64_t key;
+  move_t best_move;
+  i16 score; // depth analysed
+  i16 eval; // non-depth analysed
+  u16 depth;
+  u16 generation;
+  u8 flag;
+} tentry_t;
+
+typedef struct {
+  tentry_t entries[TT_BUCKET_SIZE];
+} tbucket_t;
+
+typedef tbucket_t* ttable_t;
+
+void ttable_init();
+u64 zobrist_hash(position_t position);
+void ttable_store(
+  ttable_t *ttable, u64 key, move_t move, i16 score,
+  i16 eval, u16 depth, u16 generation, u8 flag
+);
+tentry_t *ttable_probe(ttable_t *table, u64 key);
+
+#endif // TTABLE_H
diff --git a/src/engine.c b/src/engine.c
index dc6940a..9f0a2d2 100644
--- a/src/engine.c
+++ b/src/engine.c
@@ -1,4 +1,4 @@
 #include "engine/threads.c"
 #include "engine/thread.c"
 #include "engine/moves.c"
-#include "engine/transposition_table.c"
+#include "engine/ttable.c"
diff --git a/src/engine/transposition_table.c b/src/engine/transposition_table.c
deleted file mode 100644
index 1afbc81..0000000
--- a/src/engine/transposition_table.c
+++ /dev/null
@@ -1,44 +0,0 @@
-#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/engine/ttable.c b/src/engine/ttable.c
new file mode 100644
index 0000000..31bdd72
--- /dev/null
+++ b/src/engine/ttable.c
@@ -0,0 +1,90 @@
+#include "engine/ttable.h"
+
+void ttable_init() {
+  tbucket_t *table = calloc(TABLE_SIZE * sizeof(*table));
+
+  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;
+}
+
+void ttable_store(
+  ttable_t *ttable,
+  u64 key,
+  move_t move,
+  i16 score,
+  i16 eval,
+  u16 depth,
+  u16 generation,
+  u8 flag
+) {
+    tbucket_t *bucket = ttable + (key & MASK);
+    tentry_t *best = bucket.entries;
+
+    for (int i = 1; i < TT_BUCKET_SIZE; i++) {
+      if (bucket.entries[i].depth >= best->depth) continue;
+      best = bucket.entries + i;
+    }
+
+    tentry_t object;
+    object.move = move;
+    object.score = score;
+    object.eval = eval;
+    object.depth = depth;
+    object.flag = flag;
+    object.generation = generation;
+
+    memcpy(best, &object, sizeof(object));
+    atomic_store_explicit(&best->key, key, memory_order_release);
+}
+
+tentry_t *ttable_probe(ttable_t *table, u64 key) {
+    tbucket_t *bucket = ttable + key & MASK;
+
+    for (int i = 0; i < TT_BUCKET_SIZE; i++) {
+      if (atomic_load_explicit(
+        &(bucket.entries + i)->key,
+        memory_order_acquire
+      ) != key) continue;
+      return bucket.entries + i;
+    }
+
+    return NULL;
+}