feat: implement iterative deepening

1 files changed, 30 insertions, 15 deletions

diff --git a/src/board/engine.rs b/src/board/engine.rs
index c6ac512..88ae77a 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -1,4 +1,4 @@
-use std::cmp::Ordering;
+use std::{cmp::Ordering, time::{Instant, Duration}, f32::INFINITY};
 use crate::{bitboard::pop_count, board::*};
 
 use super::ttable::{NodeType, TranspositionTableItem};
@@ -121,7 +121,7 @@ impl Board {
         source_eval - target_eval
     }
 
-    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> (f32, Vec<Move>) {
+    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, deadline: Instant) -> (f32, Vec<Move>) {
         let mut principal_variation = Vec::new();
         let color = self.color();
 
@@ -156,7 +156,7 @@ impl Board {
             };
 
             if !self.is_king_in_check(color) {
-                let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1);
+                let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1, deadline);
                 score *= -1.;
                 self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
 
@@ -179,6 +179,12 @@ impl Board {
             } else {
                 self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
             }
+
+            // Could not finish in time, return what we have so far
+            if Instant::now() > deadline {
+                println!("Returning early!");
+                return (alpha, principal_variation)
+            }
         }
         (alpha, principal_variation)
     }
@@ -236,13 +242,32 @@ impl Board {
 
         alpha
     }
+
+    pub fn iterative_deepening(&mut self, duration: Duration) -> (f32, Vec<Move>) {
+        let start = Instant::now();
+        let deadline = start + duration;
+        let mut result = None;
+        let mut depth = 0;
+
+        loop {
+            let search_result = self.negamax_search(-INFINITY, INFINITY, depth, deadline);
+            println!("Finished depth({}) {:?} [{:?} left]", depth, search_result, deadline - Instant::now());
+
+            if Instant::now() > deadline {
+                match result {
+                    Some(r) => return r,
+                    None => panic!("Could not find a move in time"),
+                }
+            }
+            result = Some(search_result);
+            depth += 1;
+        }
+    }
 }
 
 
 #[cfg(test)]
 mod tests {
-    use std::f32::INFINITY;
-
     use crate::board::{Board, engine::PerftResult};
 
     #[test]
@@ -269,16 +294,6 @@ mod tests {
     }
 
     #[test]
-    fn negamax_search() {
-        let fen = String::from("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - ");
-        let mut board = Board::from_FEN(fen);
-
-        let (eval, pv) = board.negamax_search(-INFINITY, INFINITY, 4);
-        assert_eq!(eval, 0.0);
-        assert_eq!(pv.len(), 4);
-    }
-
-    #[test]
     fn material_advantage() {
         let board = Board::new();
         assert_eq!(board.material_advantage(), 0.0, "Material advantage should be 0 at starting position");