refactor: reconstruct PV only after the search

1 files changed, 70 insertions, 66 deletions

diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs
index 455fb6f..378349c 100644
--- a/src/grossmeister/search.rs
+++ b/src/grossmeister/search.rs
@@ -40,31 +40,27 @@ impl Grossmeister {
         0.0
     }
 
-    pub fn negamax_search(&mut self, mut alpha: Score, mut beta: Score, depth_left: u8, root_distance: u8) -> (Score, Vec<Move>) {
-        let mut principal_variation = Vec::new();
+    pub fn negamax_search(&mut self, mut alpha: Score, mut beta: Score, depth_left: u8, root_distance: u8) -> Score {
         let color = self.board.color();
 
         if self.board.threefold_repetition() {
-            return (0.0, principal_variation);
+            return 0.0
         }
 
         if let Some(transposition) = self.transposition() {
             if transposition.depth == depth_left {
                 match transposition.node_type {
                     NodeType::PV => { // PV-nodes have exact score
-                        principal_variation.push(transposition.mov);
-                        return (transposition.score, principal_variation);
+                        return transposition.score
                     }
                     NodeType::Cut => {
                         if transposition.score >= beta {
-                            principal_variation.push(transposition.mov);
-                            return (beta, principal_variation);
+                            return beta
                         }
                     }
                     NodeType::All => {
                         if transposition.score <= alpha {
-                            principal_variation.push(transposition.mov);
-                            return (alpha, principal_variation);
+                            return alpha
                         }
                     }
                 }
@@ -74,11 +70,11 @@ impl Grossmeister {
         // Mate distance pruning
         let mating_score = Grossmeister::MDP(&mut alpha, &mut beta, root_distance);
         if mating_score != 0.0 {
-            return (mating_score, principal_variation)
+            return mating_score
         }
 
         if depth_left == 0 {
-            return (self.quiscence(alpha, beta, root_distance), principal_variation);
+            return self.quiscence(alpha, beta, root_distance)
         }
 
         let mut should_pv_search = true;
@@ -94,20 +90,20 @@ impl Grossmeister {
             if !self.board.is_king_in_check(color) {
                 legal_move_found = true;
 
-                let (mut score, mut subtree_pv) = if should_pv_search {
+                let mut score = if should_pv_search {
                     // Assume PV-node is high in the list (if move ordering is good)
                     self.negamax_search(-beta, -alpha, depth_left - 1, root_distance + 1)
                 } else {
                     // After we have PV-node (that raised alpha) all other nodes will be searched
                     // with zero-window first to confirm this assumption
                     // TODO: changing 0.001 -> 0.0001 leads to a weird bug
-                    let result = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1, root_distance + 1);
+                    let score = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1, root_distance + 1);
                     // In case some of the other nodes raises alpha, then it's true PV node now,
                     // let's research with full window to find its exact value
-                    if -result.0 > alpha {
+                    if -score > alpha {
                         self.negamax_search(-beta, -alpha, depth_left - 1, root_distance + 1)
                     } else {
-                        result
+                        score
                     }
                 };
                 score *= -1.;
@@ -126,14 +122,11 @@ impl Grossmeister {
                         self.register_killer(mov);
                     }
 
-                    return (beta, principal_variation);
+                    return beta
                 }
                 if score > alpha {
                     alpha = score;
                     should_pv_search = false; // Once we have PV-node we can start zero-window searching
-                    principal_variation = Vec::with_capacity(depth_left as usize);
-                    principal_variation.push(mov);
-                    principal_variation.append(&mut subtree_pv);
 
                     self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
                         hash: self.board.hash,
@@ -163,13 +156,13 @@ impl Grossmeister {
 
         if !legal_move_found {
             if self.board.is_king_in_check(color) {
-                return (-SCORE_MATE + root_distance as Score, principal_variation);
+                return -SCORE_MATE + root_distance as Score
             } else {
-                return (0.0, principal_variation);
+                return 0.0
             }
         }
 
-        (alpha, principal_variation)
+        alpha
     }
 
     pub fn quiscence(&mut self, mut alpha: Score, mut beta: Score, root_distance: u8) -> Score {
@@ -233,8 +226,30 @@ impl Grossmeister {
         alpha
     }
 
-    pub fn iterative_deepening(&mut self, max_depth: u8) -> Option<(Score, Vec<Move>)> {
-        let mut result = None;
+    fn reconstruct_pv(&mut self, depth: u8) -> Vec<Move> {
+        let mut pv = Vec::with_capacity(depth as usize);
+
+        if let Some(transposition) = self.transposition() {
+            let mov = transposition.mov;
+            let ep_target_before = self.board.ep_target;
+            let castling_rights_before = self.board.castling_rights;
+            let hash_before = self.board.hash;
+            let captured = self.board.make_move(mov);
+
+            let mut subtree_pv = self.reconstruct_pv(depth - 1);
+            self.board.unmake_move(mov, captured, ep_target_before, castling_rights_before, hash_before);
+
+            pv.push(mov);
+            pv.append(&mut subtree_pv);
+        }
+        debug_assert!(pv.len() == depth as usize);
+        pv
+    }
+
+    pub fn iterative_deepening(&mut self, max_depth: u8) -> (Score, Vec<Move>) {
+        let mut best_score = 0.0;
+        let mut pv = Vec::new();
+
         let mut depth = 1;
         let mut alpha = -INFINITY;
         let mut beta = INFINITY;
@@ -246,81 +261,70 @@ impl Grossmeister {
                 println!("info string window {:?}", (alpha, beta));
             }
 
-            let search_result = self.negamax_search(alpha, beta, depth, 0);
+            let score = self.negamax_search(alpha, beta, depth, 0);
 
             if self.should_halt.load(std::sync::atomic::Ordering::SeqCst) {
                 println!("info string halting search");
                 break;
             }
 
-            if search_result.0 <= alpha { // Alpha-cutoff
+            if score <= alpha { // Alpha-cutoff
                 gradual_widening_counter += 1;
                 beta = alpha + window_size * 0.1;
-                alpha = search_result.0 - window_size * 2.0f32.powi(gradual_widening_counter);
+                alpha = score - window_size * 2.0f32.powi(gradual_widening_counter);
                 println!("info depth {} score upperbound {:.0}", depth, beta * 100.0);
                 continue;
             }
-            if search_result.0 >= beta { // Beta-cutoff
+            if score >= beta { // Beta-cutoff
                 gradual_widening_counter += 1;
                 alpha = beta - window_size * 0.1;
-                beta = search_result.0 + window_size * 2.0f32.powi(gradual_widening_counter);
+                beta = score + window_size * 2.0f32.powi(gradual_widening_counter);
                 println!("info depth {} score lowerbound {:.0}", depth, alpha * 100.0);
                 continue;
             }
 
-            if search_result.1.is_empty() {
-                panic!("Why the fuck no moves?");
-            }
+            best_score = score;
+            pv = self.reconstruct_pv(depth);
 
             // Print UCI info
             print!("info depth {} score ", depth);
-            if search_result.0.abs() >= SCORE_MATE - 128f32 { // TODO: VALUE_WIN - MAX_PLY
-                let mate_distance = (SCORE_MATE - search_result.0.abs()) * if search_result.0 > 0.0 {
+            if score.abs() >= SCORE_MATE - 128f32 { // TODO: VALUE_WIN - MAX_PLY
+                let mate_distance = (SCORE_MATE - score.abs()) * if score > 0.0 {
                     1.
                 } else {
                     -1. // -N means we are mated in N plies
                 };
                 print!("mate {:.0} ", (mate_distance / 2.0).ceil());
             } else {
-                print!("cp {:.0} ", search_result.0 * 100.0)
+                print!("cp {:.0} ", score * 100.0)
             }
             print!("pv ");
-            for mov in &search_result.1 {
+            for mov in &pv {
                 print!("{} ", mov);
             }
             println!();
 
-            // If our score is mate in N, we break at depth N
-            if depth as Score >= SCORE_MATE - search_result.0.abs() {
-                result = Some(search_result);
-                break;
-            }
-
             depth += 1;
             gradual_widening_counter = 0;
-            alpha = search_result.0 - window_size;
-            beta = search_result.0 + window_size;
-            result = Some(search_result);
-        }
+            alpha = score - window_size;
+            beta = score + window_size;
 
-        if result.is_none() {
-            println!("info string could not find move in time, will re-run depth-1 search to avoid panic");
-            result = Some(self.negamax_search(-INFINITY, INFINITY, 1, 0))
+            // If our score is mate in N, we break at depth N
+            if depth as Score >= SCORE_MATE - score.abs() {
+                break;
+            }
         }
 
         println!("info hashfull {}", 1000 * self.transposition_table.iter().filter(|item| item.is_some()).count() / self.transposition_table.len());
-
-        if let Some(r) = result.clone() {
-            if !r.1.is_empty() {
-                print!("bestmove {}", r.1[0]);
-            }
-            if r.1.len() > 1 {
-                print!(" ponder {}", r.1[1])
-            }
-            println!();
+        if !pv.is_empty() {
+            print!("bestmove {}", pv[0]);
+        }
+        if pv.len() > 1 {
+            print!(" ponder {}", pv[1])
         }
+        println!();
 
-        result
+        (best_score, pv)
     }
 
     pub fn perft(&mut self, depth: u8, print: bool) -> PerftResult {
@@ -436,7 +440,7 @@ mod tests {
         let fen = String::from("2kr1b1r/pp1npppp/2p1bn2/7q/5B2/2NB1Q1P/PPP1N1P1/2KR3R w - - 0 1");
         let board = Board::from_FEN(fen);
         let mut gm = Grossmeister::new(board);
-        let (score, pv) = gm.iterative_deepening(8).unwrap();
+        let (score, pv) = gm.iterative_deepening(8);
 
         assert_eq!(score, SCORE_MATE - 3.0);
         assert_eq!(pv, vec![
@@ -452,7 +456,7 @@ mod tests {
         let board = Board::from_FEN(fen);
 
         let mut gm = Grossmeister::new(board);
-        let (_, pv) = gm.iterative_deepening(6).unwrap();
+        let (_, pv) = gm.iterative_deepening(6);
         assert_eq!(
             pv[0],
             Move { source: Square::F5, target: Square::H4, kind: MoveKind::Quiet },
@@ -466,7 +470,7 @@ mod tests {
         let board = Board::from_FEN(fen);
 
         let mut gm = Grossmeister::new(board);
-        let (_, pv) = gm.iterative_deepening(5).unwrap();
+        let (_, pv) = gm.iterative_deepening(5);
         assert_eq!(
             pv[0],
             Move { source: Square::C2, target: Square::C3, kind: MoveKind::Quiet },
@@ -481,7 +485,7 @@ mod tests {
 
         let mut gm = Grossmeister::new(board);
         gm.debug = true;
-        let (score, pv) = gm.iterative_deepening(5).unwrap();
+        let (score, pv) = gm.iterative_deepening(5);
         dbg!(score, pv);
         assert_eq!(SCORE_MATE - score, 3.0); // Mate in 3 plies
     }
@@ -493,7 +497,7 @@ mod tests {
 
         let mut gm = Grossmeister::new(board);
         gm.debug = true;
-        let (score, pv) = gm.iterative_deepening(5).unwrap();
+        let (score, pv) = gm.iterative_deepening(5);
         dbg!(score, pv);
         assert_eq!(score + SCORE_MATE, 4.0); // Mate in 4 plies
     }
@@ -505,7 +509,7 @@ mod tests {
 
         let mut gm = Grossmeister::new(board);
         gm.debug = true;
-        let (score, pv) = gm.iterative_deepening(5).unwrap();
+        let (score, pv) = gm.iterative_deepening(5);
         dbg!(score, pv);
         assert_eq!(SCORE_MATE - score, 3.0); // Mate in 3 plies
     }
@@ -517,7 +521,7 @@ mod tests {
 
         let mut gm = Grossmeister::new(board);
         gm.debug = true;
-        let (score, pv) = gm.iterative_deepening(5).unwrap();
+        let (score, pv) = gm.iterative_deepening(5);
         dbg!(score, pv);
         assert!(score <= 0.0);
     }