feat: add transposition table lookup

2 files changed, 47 insertions, 13 deletions

diff --git a/src/config.h b/src/config.h
index 4031d91..951b9b3 100644
--- a/src/config.h
+++ b/src/config.h
@@ -5,3 +5,4 @@
 #define INFINITY 1000000
 #define PLAYER WHITE
 #define MAX_ZOBRIST_SEEDS 1500
+#define TRANSPOSITION_TABLE_SIZE 1000000
diff --git a/src/main.c b/src/main.c
index f1eb6a3..74d83ce 100644
--- a/src/main.c
+++ b/src/main.c
@@ -34,6 +34,19 @@ int zobrist_hash(int* seed, int* board, int color_to_move) {
   return result;
 }
 
+int apply_move_zobrist(Move move, int* board, int* zobrist_seed, int hash) {
+  int piece = board[move.origin];
+  int target_piece = board[move.destination];
+
+  hash ^= zobrist_seed[piece * 128 + move.origin]; // Remove piece from origin
+  hash ^= zobrist_seed[piece * 128 + move.destination]; // Add piece to destination
+  hash ^= zobrist_seed[target_piece * 128 + move.destination]; // Remove target piece from destination
+  hash ^= zobrist_seed[1 - piece % 2]; // It's now opponent's turn
+  hash ^= zobrist_seed[piece % 2]; // Not a current color's turn
+
+  return hash;
+}
+
 
 void print_board(int board[128]) {
   for (int rank = 7; rank >= 0; rank--) {
@@ -458,14 +471,25 @@ int compare_moves(const void* a, const void* b) {
   return ((Move*)b)->value - ((Move*)a)->value;
 }
 
-void sort_moves(Move* moves, int moves_count, int* board) {
+int sort_moves(Move* moves, int moves_count, int* board, int hash, int* transposition_table, int* zobrist_seed) {
+  int cache_hits = 0;
   for (int i = 0; i < moves_count; i++) {
-    int origin_value = get_piece_raw_value(board[moves[i].origin]);
-    int destination_value = get_piece_raw_value(board[moves[i].destination]);
-    moves[i].value = 10 * destination_value - origin_value;
+    int color = board[moves[i].origin] % 2;
+    // Lookup move in transpoition table
+    int move_hash = apply_move_zobrist(moves[i], board, zobrist_seed, hash);
+    if (transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE]) {
+      moves[i].value = transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE] * (color == WHITE ? 1 : -1);
+      cache_hits++;
+    } else {
+      int origin_value = get_piece_raw_value(board[moves[i].origin]);
+      int destination_value = get_piece_raw_value(board[moves[i].destination]);
+      moves[i].value = 10 * destination_value - origin_value;
+    }
   }
 
   qsort(moves, moves_count, sizeof(Move), compare_moves);
+
+  return cache_hits; // Only needed for display
 }
 
 /*
@@ -474,7 +498,7 @@ void sort_moves(Move* moves, int moves_count, int* board) {
  * Alpha is the best value for maximizer (white)
  * Beta is the best value for minimizer (black)
  */
-Move find_best_move(int* board, int color, int depth, int alpha, int beta, int* metrics) {
+Move find_best_move(int* board, int color, int depth, int alpha, int beta, int* metrics, int hash, int* transposition_table, int* zobrist_seed) {
   int is_maximizer = (color == 0);
 
   Move best_move = { -100, -100, 0 };
@@ -484,7 +508,8 @@ Move find_best_move(int* board, int color, int depth, int alpha, int beta, int*
   if (compute_material_advantage(board, color) > -INFINITY / 2) {
     Move available_moves[MAX_AVAILABLE_MOVES];
     int available_moves_count = list_available_moves(available_moves, board, color);
-    sort_moves(available_moves, available_moves_count, board);
+    int cache_hits = sort_moves(available_moves, available_moves_count, board, hash, transposition_table, zobrist_seed);
+    if (cache_hits && (double)cache_hits / (double)available_moves_count > 0.05) printf("More than 5 percent cache hits (%i)\n", cache_hits);
 
     for (int i = 0; i < available_moves_count; i++) {
       *metrics += 1;
@@ -493,9 +518,14 @@ Move find_best_move(int* board, int color, int depth, int alpha, int beta, int*
       int captured_piece = apply_move(move, board);
 
       move.value = depth < MAX_DEPTH
-        ? find_best_move(board, 1 - color, depth + 1, alpha, beta, metrics).value
+        ? find_best_move(board, 1 - color, depth + 1, alpha, beta, metrics, hash, transposition_table, zobrist_seed).value
         : compute_score(board, available_moves_count, color);
 
+      if (depth < MAX_DEPTH) {
+        int move_hash = apply_move_zobrist(move, board, zobrist_seed, hash);
+        transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE] = move.value;
+      }
+
       reverse_move(move, captured_piece, board);
 
       if (is_maximizer) {
@@ -514,19 +544,21 @@ Move find_best_move(int* board, int color, int depth, int alpha, int beta, int*
 }
 
 int main() {
+  int color = WHITE;
   int board[128];
   parse_FEN(DEFAULT_FEN, board);
-  print_board(board);
 
+  int zobrist_seed[MAX_ZOBRIST_SEEDS];
+  generate_zobrist_seed(zobrist_seed);
+  int hash = zobrist_hash(zobrist_seed, board, color);
+
+  int transposition_table[TRANSPOSITION_TABLE_SIZE];
 
   Move move;
-  int color = WHITE;
 
-  int zobrist_seed[MAX_ZOBRIST_SEEDS];
-  generate_zobrist_seed(zobrist_seed);
+  print_board(board);
 
   while (1) {
-    int hash = zobrist_hash(zobrist_seed, board, color);
     printf("Zobrist hash: %i\n", hash);
 
     if (color == PLAYER) {
@@ -537,7 +569,7 @@ int main() {
       clock_t start, end;
       int metrics = 0;
       start = clock();
-      move = find_best_move(board, color, 0, -INFINITY, +INFINITY, &metrics);
+      move = find_best_move(board, color, 0, -INFINITY, +INFINITY, &metrics, hash, transposition_table, zobrist_seed);
       end = clock();
       printf("[%i positions analyzed in %f seconds]\n", metrics, (double)(end - start) / CLOCKS_PER_SEC);
 
@@ -555,6 +587,7 @@ int main() {
       break;
     } else {
       apply_move(move, board);
+      hash = apply_move_zobrist(move, board, zobrist_seed, hash);
 
       print_board(board);