feat: only recalculate higher-depth transpositions

2 files changed, 22 insertions, 8 deletions

diff --git a/src/main.c b/src/main.c
index aa520b1..a920cfd 100644
--- a/src/main.c
+++ b/src/main.c
@@ -528,14 +528,14 @@ int compare_moves(const void* a, const void* b) {
   return ((Move*)b)->value - ((Move*)a)->value;
 }
 
-int order_moves(Move* moves, int moves_count, int* board, long hash, int* transposition_table, long* zobrist_seed) {
+int order_moves(Move* moves, int moves_count, int* board, long hash, Transposition* transposition_table, long* zobrist_seed) {
   int cache_hits = 0;
   for (int i = 0; i < moves_count; i++) {
     int color = board[moves[i].origin] % 2;
     // Lookup move in transpoition table
     long move_hash = hash_after_move(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);
+    if (transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].depth > -1) {
+      moves[i].value = transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].value * (color == WHITE ? 1 : -1);
       cache_hits++;
     } else {
       int origin_value = get_piece_raw_value(board[moves[i].origin]);
@@ -555,7 +555,7 @@ int order_moves(Move* moves, int moves_count, int* board, long hash, int* transp
  * Alpha is the best value for maximizer (white)
  * Beta is the best value for minimizer (black)
  */
-Move minimax_search(int* board, int color, int depth, int alpha, int beta, int* metrics, long hash, int* transposition_table, long* zobrist_seed) {
+Move minimax_search(int* board, int color, int depth, int alpha, int beta, int* metrics, long hash, Transposition* transposition_table, long* zobrist_seed) {
   int is_maximizer = (color == 0);
 
   Move best_move = { -100, -100, 0 };
@@ -574,12 +574,17 @@ Move minimax_search(int* board, int color, int depth, int alpha, int beta, int*
       long move_hash = hash_after_move(move, board, zobrist_seed, hash);
       int captured_piece = make_move(move, board);
 
-      move.value = depth < MAX_DEPTH
+      int local_depth = MAX_DEPTH - depth;
+
+      move.value = local_depth > 0
         ? minimax_search(board, 1 - color, depth + 1, alpha, beta, metrics, hash, transposition_table, zobrist_seed).value
         : evaluate_position(board, available_moves_count, color);
 
-      if (!transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE]) TRANSPOSITION_TABLE_CARDINALITY++;
-      transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE] = move.value;
+      if (transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].depth < local_depth) {
+        if (transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].depth == -1) TRANSPOSITION_TABLE_CARDINALITY++;
+        transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].value = move.value;
+        transposition_table[move_hash % TRANSPOSITION_TABLE_SIZE].depth = local_depth;
+      }
 
       unmake_move(move, captured_piece, board);
 
@@ -606,7 +611,11 @@ int main() {
   generate_zobrist_seed(zobrist_seed);
   long hash = zobrist_hash(zobrist_seed, board, WHITE);
 
-  int transposition_table[TRANSPOSITION_TABLE_SIZE];
+  Transposition transposition_table[TRANSPOSITION_TABLE_SIZE];
+  for (int i = 0; i < TRANSPOSITION_TABLE_SIZE; i++) {
+    transposition_table[i].value = 0;
+    transposition_table[i].depth = -1;
+  }
 
   Move move;
 
diff --git a/src/structs.h b/src/structs.h
index 643e7f2..5a60ba9 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -4,3 +4,8 @@ typedef struct {
   int value; // Estimated move value
 } Move;
 
+typedef struct {
+  int value; // Estimated position value
+  int depth; // Depth -1 indicates it has not been evaluated yet
+} Transposition;
+