feat: gather principal variation in negamax

4 files changed, 40 insertions, 11 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 59aa9d6..510ad97 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,3 +11,7 @@ num_enum = "0.5.7"
 [[bench]]
 name = "perft"
 harness = false
+
+[[bench]]
+name = "negamax"
+harness = false
diff --git a/benches/negamax.rs b/benches/negamax.rs
new file mode 100644
index 0000000..b9e38df
--- /dev/null
+++ b/benches/negamax.rs
@@ -0,0 +1,20 @@
+use std::{time::Instant, f32::INFINITY};
+use chessnost::board::Board;
+
+fn main() {
+    let fen = String::from("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1");
+    let mut board = Board::from_FEN(fen);
+    board.ply = 0;
+
+    let depth = 4;
+    let start = Instant::now();
+    let (eval, pv) = board.negamax_search(-INFINITY, INFINITY, depth);
+    println!("Negamax search (depth = {}) finished in {:?}: {:?}", depth, start.elapsed(), eval);
+    board.print();
+    for mov in pv {
+        println!("{:?}", mov);
+        board.make_move(mov);
+        board.print();
+        println!("Eval for {:?}: {}", board.color(), board.material_advantage());
+    }
+}
diff --git a/src/board/engine.rs b/src/board/engine.rs
index 9b0e36c..ff071ea 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -99,11 +99,11 @@ impl Board {
         eval
     }
 
-    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> f32 {
-        let color = Color::from(self.ply as u8 % 2);
-
+    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> (f32, Vec<Move>) {
+        let mut principal_variation = Vec::new();
+        let color = self.color();
         if depth_left == 0 {
-            return self.material_advantage();
+            return (self.material_advantage(), principal_variation);
         }
         let moves = self.generate_pseudolegal_moves(color);
 
@@ -113,20 +113,24 @@ impl Board {
             let captured_piece = self.make_move(mov);
 
             if !self.is_king_in_check(color) {
-                let evaluation = -self.negamax_search(-beta, -alpha, depth_left - 1);
+                let (mut evaluation, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1);
+                evaluation *= -1.;
                 self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before);
 
                 if evaluation >= beta {
-                    return beta; // Fail-hard beta-cutoff
+                    return (beta, principal_variation); // Fail-hard beta-cutoff
                 }
                 if evaluation > alpha {
-                    alpha = evaluation
+                    alpha = evaluation;
+                    principal_variation = Vec::with_capacity(depth_left as usize);
+                    principal_variation.push(mov);
+                    principal_variation.append(&mut subtree_pv);
                 }
             } else {
                 self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before);
             }
         }
-        alpha
+        (alpha, principal_variation)
     }
 
 }
@@ -166,8 +170,9 @@ mod tests {
         let fen = String::from("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - ");
         let mut board = Board::from_FEN(fen);
 
-        let eval = board.negamax_search(-INFINITY, INFINITY, 4);
-        println!("{}", eval);
+        let (eval, pv) = board.negamax_search(-INFINITY, INFINITY, 4);
+        assert_eq!(eval, 0.0);
+        assert_eq!(pv.len(), 4);
     }
 
     #[test]
diff --git a/src/board/mod.rs b/src/board/mod.rs
index 5e2f4e3..d339f1d 100644
--- a/src/board/mod.rs
+++ b/src/board/mod.rs
@@ -123,7 +123,7 @@ impl Board {
     }
 
     /// Color to move at this ply
-    fn color(&self) -> Color {
+    pub fn color(&self) -> Color {
         Color::from(self.ply as u8 % 2)
     }