feat: implement iterative deepening

2 files changed, 38 insertions, 11 deletions

diff --git a/src/config.h b/src/config.h
index d436f94..f994cee 100644
--- a/src/config.h
+++ b/src/config.h
@@ -1,9 +1,10 @@
 #define BOARD_SIZE 8
 #define DEFAULT_FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"
-#define MAX_DEPTH 4
+#define MAX_DEPTH 5
 #define MAX_AVAILABLE_MOVES 64 * 64
 #define INFINITY 2000
 #define MAX_ZOBRIST_SEEDS 1500
 #define TRANSPOSITION_TABLE_SIZE 1000000
 #define PLAYER 3
 #define FILENAME "record.txt"
+#define MOVE_TIME 15
diff --git a/src/main.c b/src/main.c
index 78fd66b..c855a6e 100644
--- a/src/main.c
+++ b/src/main.c
@@ -26,7 +26,7 @@ long crop_hash(long hash) {
   return modulo;
 }
 
-int zobrist_hash(long* seed, int* board, int color_to_move) {
+long zobrist_hash(long* seed, int* board, int color_to_move) {
   long hash = 1;
 
   // Last feature means white to move
@@ -583,7 +583,7 @@ int order_moves(Move* moves, int moves_count, int* board, long hash, Transpositi
  * 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, Transposition* 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, clock_t deadline) {
   int is_maximizer = (color == 0);
 
   Move best_move = { -100, -100, 0 };
@@ -603,7 +603,7 @@ Move minimax_search(int* board, int color, int depth, int alpha, int beta, int*
       int captured_piece = make_move(move, board);
 
       move.value = depth > 0
-        ? minimax_search(board, 1 - color, depth - 1, alpha, beta, metrics, move_hash, transposition_table, zobrist_seed).value
+        ? minimax_search(board, 1 - color, depth - 1, alpha, beta, metrics, move_hash, transposition_table, zobrist_seed, deadline).value
         : evaluate_position(board, available_moves_count, color);
 
       if (transposition_table[move_hash].depth < depth) {
@@ -623,12 +623,43 @@ Move minimax_search(int* board, int color, int depth, int alpha, int beta, int*
       }
 
       if (beta <= alpha) break;
+
+      // We ran out of time
+      if (clock() > deadline) break;
     }
   }
 
   return best_move;
 }
 
+
+Move iterative_deepening(int* board, int color, long hash, Transposition* transposition_table, long* zobrist_seed) {
+  Move move, best_move;
+  int depth = 0;
+  clock_t start = clock();
+  clock_t deadline = start + MOVE_TIME * CLOCKS_PER_SEC;
+
+  while (depth <= MAX_DEPTH) {
+    best_move = move;
+    printf("Searching with depth %i... [%.2f seconds left]\n", depth, (double)(deadline - clock()) / CLOCKS_PER_SEC);
+
+    int metrics = 0;
+    move = minimax_search(board, color, depth, -INFINITY, +INFINITY, &metrics, hash, transposition_table, zobrist_seed, deadline);
+
+    if (clock() > deadline) {
+      printf("Out of time! Falling back to result with depth %i\n", depth - 1);
+      return best_move;
+    }
+
+    printf("Done (evaluation %.2f)    [%i positions analyzed]\n", (double)move.value / 10, metrics);
+
+    depth++;
+  }
+
+  printf("Max depth (%i) reached in %.2f seconds\n", MAX_DEPTH, (double)(clock() - start) / CLOCKS_PER_SEC);
+  return best_move;
+}
+
 int main() {
   FILE* record = fopen(FILENAME, "r");
   int is_reading = 1;
@@ -669,13 +700,8 @@ int main() {
       index_to_notation(move.origin, move_in_notation);
       index_to_notation(move.destination, move_in_notation + 2);
     } else {
-      printf("Evaluating move for %s...\n", COLORS[color]);
-      clock_t start, end;
-      int metrics = 0;
-      start = clock();
-      move = minimax_search(board, color, MAX_DEPTH, -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);
+      printf("Evaluating move for %s:\n", COLORS[color]);
+      move = iterative_deepening(board, color, hash, transposition_table, zobrist_seed);
       printf("[Transposition table cardinality: %i]\n", TRANSPOSITION_TABLE_CARDINALITY);
 
       index_to_notation(move.origin, move_in_notation);