simple ttable tests

7 files changed, 232 insertions, 67 deletions

diff --git a/include/bitboard.h b/include/bitboard.h
index b1ddcf0..25ff27d 100644
--- a/include/bitboard.h
+++ b/include/bitboard.h
@@ -84,6 +84,7 @@ bool check_valid_position(position_t position);
     position.bitboards[BLACK_PAWN]
 
 
+int find_piece_on_square(position_t* p, int square);
 void print_position(position_t position);
 void print_bitboard(bitboard_t bitboard);
 
diff --git a/include/engine/ttable.h b/include/engine/ttable.h
index 2ee1a5c..8b1938a 100644
--- a/include/engine/ttable.h
+++ b/include/engine/ttable.h
@@ -1,11 +1,13 @@
 #ifndef TTABLE_H
 #define TTABLE_H
 
+#include "engine/moves.h"
 #include "bitboard.h"
+#include <stdatomic.h>
 
 #define TABLE_BITS 24
 #define TABLE_SIZE (1ULL << TABLE_BITS)
-#define MASK (TABLE_SIZE - 1)
+#define TT_MASK (TABLE_SIZE - 1)
 #define TT_BUCKET_SIZE 4
 
 static struct zobrist_keys {
@@ -15,6 +17,9 @@ static struct zobrist_keys {
   u64 en_passant[64];
 } zobrist_keys;
 
+void zobrist_init();
+u64 zobrist_hash(position_t position);
+
 enum { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
 typedef struct {
   atomic_uint_fast64_t key;
@@ -28,16 +33,29 @@ typedef struct {
 
 typedef struct {
   tentry_t entries[TT_BUCKET_SIZE];
+  int items_filled;
 } 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);
+struct ttable_insert_args {
+  u64 key;
+  move_t move;
+  i16 score;
+  i16 eval;
+  u16 depth;
+  u16 generation;
+  u8 flag;
+};
+
+void ttable_init(ttable_t *table);
+void ttable_deinit(ttable_t table);
+void __ttable_insert(ttable_t table, struct ttable_insert_args args);
+tentry_t *ttable_find(ttable_t table, u64 key);
+
+#define ttable_insert(ttable, ...) __ttable_insert( \
+  ttable, \
+  (struct ttable_insert_args) { __VA_ARGS__ } \
+)
 
 #endif // TTABLE_H
diff --git a/src/bitboard.c b/src/bitboard.c
index 1c3ed28..71e66a5 100644
--- a/src/bitboard.c
+++ b/src/bitboard.c
@@ -73,6 +73,22 @@ char get_piece_char_from_sqr(position_t position, size_t square) {
   return ' ';
 }
 
+int find_piece_on_square(position_t* p, int square) {
+  if ((p->bitboards[WHITE_KING]   >> square) & 1) return WHITE_KING;
+  if ((p->bitboards[WHITE_QUEEN]  >> square) & 1) return WHITE_QUEEN;
+  if ((p->bitboards[WHITE_ROOK]   >> square) & 1) return WHITE_ROOK;
+  if ((p->bitboards[WHITE_BISHOP] >> square) & 1) return WHITE_BISHOP;
+  if ((p->bitboards[WHITE_KNIGHT] >> square) & 1) return WHITE_KNIGHT;
+  if ((p->bitboards[WHITE_PAWN]   >> square) & 1) return WHITE_PAWN;
+  if ((p->bitboards[BLACK_KING]   >> square) & 1) return BLACK_KING;
+  if ((p->bitboards[BLACK_QUEEN]  >> square) & 1) return BLACK_QUEEN;
+  if ((p->bitboards[BLACK_ROOK]   >> square) & 1) return BLACK_ROOK;
+  if ((p->bitboards[BLACK_BISHOP] >> square) & 1) return BLACK_BISHOP;
+  if ((p->bitboards[BLACK_KNIGHT] >> square) & 1) return BLACK_KNIGHT;
+  if ((p->bitboards[BLACK_PAWN]   >> square) & 1) return BLACK_PAWN;
+  assert(0 && "Failed to find the piece on the square");
+}
+
 void print_position(position_t position) {
   for (int i = 8; i > 0; i--) {
     printf("+---+---+---+---+---+---+---+---+\n");
diff --git a/src/engine/moves.c b/src/engine/moves.c
index 6f96109..8df9364 100644
--- a/src/engine/moves.c
+++ b/src/engine/moves.c
@@ -63,22 +63,6 @@ void get_legal_moves(moves_t* moves, position_t position) {
   moves->length = write;
 }
 
-int find_piece_on_square(position_t* p, int square) {
-  if ((p->bitboards[WHITE_KING]   >> square) & 1) return WHITE_KING;
-  if ((p->bitboards[WHITE_QUEEN]  >> square) & 1) return WHITE_QUEEN;
-  if ((p->bitboards[WHITE_ROOK]   >> square) & 1) return WHITE_ROOK;
-  if ((p->bitboards[WHITE_BISHOP] >> square) & 1) return WHITE_BISHOP;
-  if ((p->bitboards[WHITE_KNIGHT] >> square) & 1) return WHITE_KNIGHT;
-  if ((p->bitboards[WHITE_PAWN]   >> square) & 1) return WHITE_PAWN;
-  if ((p->bitboards[BLACK_KING]   >> square) & 1) return BLACK_KING;
-  if ((p->bitboards[BLACK_QUEEN]  >> square) & 1) return BLACK_QUEEN;
-  if ((p->bitboards[BLACK_ROOK]   >> square) & 1) return BLACK_ROOK;
-  if ((p->bitboards[BLACK_BISHOP] >> square) & 1) return BLACK_BISHOP;
-  if ((p->bitboards[BLACK_KNIGHT] >> square) & 1) return BLACK_KNIGHT;
-  if ((p->bitboards[BLACK_PAWN]   >> square) & 1) return BLACK_PAWN;
-  assert(0 && "Failed to find the piece on the square");
-}
-
 void position_make_move(position_t* position, move_t move) {
   position->passantable_file = 0;
 
diff --git a/src/engine/ttable.c b/src/engine/ttable.c
index 31bdd72..851e389 100644
--- a/src/engine/ttable.c
+++ b/src/engine/ttable.c
@@ -1,8 +1,10 @@
-#include "engine/ttable.h"
+#include <stdlib.h>
+#include <string.h>
 
-void ttable_init() {
-  tbucket_t *table = calloc(TABLE_SIZE * sizeof(*table));
+#include "engine/ttable.h"
+#include "random.h"
 
+void zobrist_init() {
   for (int i = 0; i < PIECE_TYPE_COUNT; i++) {
     for (int j = 0; j < 64; j++) {
       zobrist_keys.piece[i][j] = random_u64();
@@ -45,46 +47,181 @@ u64 zobrist_hash(position_t position) {
   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;
-    }
+void ttable_init(ttable_t *table) {
+  ttable_t output = calloc(TABLE_SIZE, sizeof(tbucket_t));
+  memcpy(table, &output, sizeof(output));
+}
+
+void ttable_deinit(ttable_t table) {
+  free(table);
+}
+
+void __ttable_insert(ttable_t table, struct ttable_insert_args args) {
+  tbucket_t *bucket = table + (args.key & TT_MASK);
+  tentry_t *best = bucket->entries;
 
-    tentry_t object;
-    object.move = move;
-    object.score = score;
-    object.eval = eval;
-    object.depth = depth;
-    object.flag = flag;
-    object.generation = generation;
+  int count = bucket->items_filled;
+  for (int i = 1; i < count; i++) {
+    if (bucket->entries[i].depth >= best->depth) continue;
+    best = bucket->entries + i;
+  }
 
-    memcpy(best, &object, sizeof(object));
-    atomic_store_explicit(&best->key, key, memory_order_release);
+  tentry_t object;
+  object.best_move = args.move;
+  object.score = args.score;
+  object.eval = args.eval;
+  object.depth = args.depth;
+  object.flag = args.flag;
+  object.generation = args.generation;
+
+  memcpy(best, &object, sizeof(object));
+  atomic_store(&best->key, args.key);
 }
 
-tentry_t *ttable_probe(ttable_t *table, u64 key) {
-    tbucket_t *bucket = ttable + key & MASK;
+tentry_t *ttable_find(ttable_t table, u64 key) {
+  tbucket_t *bucket = table + (key & TT_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;
-    }
+  for (int i = 0; i < TT_BUCKET_SIZE; i++) {
+    if (atomic_load(&(bucket->entries + i)->key) != key) continue;
+    return bucket->entries + i;
+  }
 
-    return NULL;
+  return NULL;
 }
+
+#ifdef TEST_MOD
+
+bool test_empty_ttable() {
+  ttable_t table;
+  ttable_init(&table);
+
+  if (ttable_find(table, 123456789ULL) != NULL) return false;
+
+  ttable_deinit(table);
+
+  return true;
+}
+
+bool test_ttable_insert_and_find() {
+  ttable_t table;
+  ttable_init(&table);
+
+  u64 key = 0x123456789ABCDEF0ULL;
+  ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT);
+
+  tentry_t *e = ttable_find(table, key);
+
+  assert(e != NULL);
+  assert(e->key == key);
+  assert(e->depth == 8);
+  assert(e->flag == TT_EXACT);
+
+  ttable_deinit(table);
+
+  return true;
+}
+
+bool test_ttable_wrong_key() {
+  ttable_t table;
+  ttable_init(&table);
+
+  u64 key = 0x123456789ABCDEF0ULL;
+  ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT);
+  assert(ttable_find(table, --key) == NULL);
+
+  ttable_deinit(table);
+  return true;
+}
+
+bool test_ttable_update_existing() {
+  ttable_t table;
+  ttable_init(&table);
+
+  u64 key = 987654321ULL;
+  ttable_insert(table, .key = key, .depth = 10, .flag = TT_LOWERBOUND);
+  ttable_insert(table, .key = key, .depth = 11, .flag = TT_EXACT);
+
+  tentry_t *e = ttable_find(table, key);
+  assert(e != NULL);
+  assert(e->key == key);
+  assert(e->depth == 11);
+  assert(e->flag == TT_EXACT);
+
+  ttable_deinit(table);
+  return true;
+}
+
+// bool FAH_test_bucket_collision() {
+//   ttable_t table;
+//   ttable_init(&table);
+//
+//
+//
+//     TranspositionTable tt;
+//     tt_init(&tt, 1); // one bucket
+//
+//     tt_store(&tt, 1, 10, 10, 5, TT_EXACT);
+//     tt_store(&tt, 2, 20, 20, 5, TT_EXACT);
+//     tt_store(&tt, 3, 30, 30, 5, TT_EXACT);
+//     tt_store(&tt, 4, 40, 40, 5, TT_EXACT);
+//
+//     assert(tt_probe(&tt, 1) != NULL);
+//     assert(tt_probe(&tt, 2) != NULL);
+//     assert(tt_probe(&tt, 3) != NULL);
+//     assert(tt_probe(&tt, 4) != NULL);
+//
+//     tt_destroy(&tt);
+// }
+
+// void test_replace_shallowest(void) {
+//     TranspositionTable tt;
+//     tt_init(&tt, 1);
+//
+//     tt_store(&tt, 1, 0, 0, 10, TT_EXACT);
+//     tt_store(&tt, 2, 0, 0, 20, TT_EXACT);
+//     tt_store(&tt, 3, 0, 0, 30, TT_EXACT);
+//     tt_store(&tt, 4, 0, 0, 40, TT_EXACT);
+//
+//     // Bucket is full.
+//
+//     tt_store(&tt, 5, 0, 0, 25, TT_EXACT);
+//
+//     assert(tt_probe(&tt, 1) == NULL);
+//
+//     assert(tt_probe(&tt, 2) != NULL);
+//     assert(tt_probe(&tt, 3) != NULL);
+//     assert(tt_probe(&tt, 4) != NULL);
+//     assert(tt_probe(&tt, 5) != NULL);
+//
+//     tt_destroy(&tt);
+// }
+
+// void test_many_entries(void)
+// {
+//     TranspositionTable tt;
+//     tt_init(&tt, 1 << 16);
+//
+//     for (uint64_t i = 0; i < 50000; i++)
+//     {
+//         tt_store(&tt,
+//                  i * 7919,
+//                  i,
+//                  i,
+//                  i % 64,
+//                  TT_EXACT);
+//     }
+//
+//     for (uint64_t i = 0; i < 50000; i++)
+//     {
+//         TTEntry *e = tt_probe(&tt, i * 7919);
+//
+//         if (e)
+//         {
+//             assert(e->key == i * 7919);
+//         }
+//     }
+//
+//     tt_destroy(&tt);
+// }
+
+#endif
diff --git a/tests/generated.c b/tests/generated.c
index f2ee156..7de9c24 100644
--- a/tests/generated.c
+++ b/tests/generated.c
@@ -1,13 +1,18 @@
 #include "../src/fen.c"
+#include "../src/engine/ttable.c"
 #include "../src/engine/moves.c"
 #include "../src/engine/moves/king.c"
 #include "../src/uci/command.c"
 
-int total_test_count = 10;
-bool (*tests[10])(void) = {
+int total_test_count = 14;
+bool (*tests[14])(void) = {
   test_fen_no_passant,
   test_fen_passant,
   test_starting_position,
+  test_empty_ttable,
+  test_ttable_insert_and_find,
+  test_ttable_wrong_key,
+  test_ttable_update_existing,
   test_perft_starting_position,
   test_perft_kiwipete_position,
   test_perft_position3,
@@ -18,10 +23,14 @@ bool (*tests[10])(void) = {
 };
 
 int max_test_name_size = 23;
-char test_names[10][100] = {
+char test_names[14][100] = {
   "fen_no_passant",
   "fen_passant",
   "starting_position",
+  "empty_ttable",
+  "ttable_insert_and_find",
+  "ttable_wrong_key",
+  "ttable_update_existing",
   "perft_starting_position",
   "perft_kiwipete_position",
   "perft_position3",
diff --git a/tests/main.c b/tests/main.c
index 800e80d..4ab84c6 100644
--- a/tests/main.c
+++ b/tests/main.c
@@ -50,4 +50,4 @@ int main() {
   return return_type;
 }
 
-#include "random.c"
+#include "../src/random.c"