simple ttable tests

3 files changed, 192 insertions, 55 deletions

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