feat: implement verified null move pruningshannon-type-b

1 files changed, 117 insertions, 97 deletions

diff --git a/src/board/engine.rs b/src/board/engine.rs
index 2e22b35..2a5f4b8 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -339,11 +339,12 @@ impl Board {
         ordered_moves
     }
 
-    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec<Move>, deadline: Instant) -> (f32, Vec<Move>) {
+    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, mut depth_left: u8, parent_killers: &mut Vec<Move>, mut should_verify: bool, deadline: Instant) -> (f32, Vec<Move>) {
         let mut principal_variation = Vec::new();
         let mut killer_moves = Vec::new();
         let color = self.color();
         let is_in_check = self.is_king_in_check(color);
+        let mut zugzwang_candidate = false;
 
         match self.transposition() {
             Some(transposition) => {
@@ -375,14 +376,16 @@ impl Board {
             return (self.quiscence(alpha, beta), principal_variation);
         }
 
-        // Try a Null Move heuristic
-        if !is_in_check && depth_left >= 3 {
+        // Verified Null Move Pruning
+        // https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1c46f15861dbfa80bb667d9d86193fc7d51a4418
+        if !is_in_check && !(should_verify && depth_left == 1) {
             let reduction = 3;
              // Apply Null Move
             self.ply += 1;
             self.hash ^= self.zobrist_seed[780];
 
-            let (mut score, ..) = self.negamax_search(-beta, -alpha, (depth_left as i8 - 1 - reduction).max(0) as u8, &mut Vec::new(), deadline);
+            // Use minimal window around beta since we only care if there's beta cutoff
+            let (mut score, ..) = self.negamax_search(-beta, -beta + 0.001, (depth_left as i8 - 1 - reduction).max(0) as u8, &mut Vec::new(), should_verify, deadline);
             score *= -1.;
 
             // Undo Null Move
@@ -390,113 +393,130 @@ impl Board {
             self.hash ^= self.zobrist_seed[780];
 
             if score >= beta {
-                return (beta, principal_variation);
+                if should_verify {
+                    depth_left -= 1;
+                    should_verify = false;
+                    zugzwang_candidate = true;
+                } else {
+                    return (beta, principal_variation);
+                }
             }
         }
 
         let mut moves = self.generate_pseudolegal_moves(color);
         moves = self.order_moves(moves, parent_killers.to_vec());
 
-        let mut should_pv_search = true; // = !should_apply_LMR
-        let mut legal_move_found = false;
-        for mov in moves {
-            let ep_target_before = self.ep_target.clone();
-            let castling_rights_before = self.castling_rights.clone();
-            let hash_before = self.hash.clone();
-            let captured_piece = self.make_move(mov);
-
-            if !self.is_king_in_check(color) {
-                legal_move_found = true;
-
-                let (mut score, mut subtree_pv) = 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, &mut killer_moves, deadline)
-                } else {
-                    // Apply late move reductions
-                    let reduction = if
-                        depth_left > 2 &&
-                        !is_in_check &&
-                        !mov.is_tactical()
-                        {
-                            1
-                        } else {
-                            0
-                        };
-
-                    // After we have PV-node (that raised alpha) all other nodes will be searched
-                    // with zero-window first to confirm this assumption.
-                    // Also (optionally) apply Late Move Reductions
-                    // TODO: changing 0.001 -> 0.0001 leads to a weird bug
-                    let result = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1 - reduction, &mut killer_moves, deadline);
-                    // 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 {
-                        self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, deadline)
+        loop { // This loop is needed to be able to return here
+            let mut should_pv_search = true; // = !should_apply_LMR
+            let mut legal_move_found = false;
+            for &mov in &moves {
+                let ep_target_before = self.ep_target.clone();
+                let castling_rights_before = self.castling_rights.clone();
+                let hash_before = self.hash.clone();
+                let captured_piece = self.make_move(mov);
+
+                if !self.is_king_in_check(color) {
+                    legal_move_found = true;
+
+                    let (mut score, mut subtree_pv) = 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, &mut killer_moves, should_verify, deadline)
                     } else {
-                        result
-                    }
-                };
-                score *= -1.;
-                self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
-
-                if score >= beta {
-                    self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
-                        hash: self.hash,
-                        mov,
-                        depth: depth_left, // TODO: should be actual depth searched
-                        node_type: NodeType::Cut,
-                        score,
-                    });
-
-                    if mov.kind == MoveKind::Quiet {
-                        match parent_killers.iter().find(|m| **m == mov) {
-                            None => parent_killers.push(mov),
-                            Some(..) => {},
+                        // Apply late move reductions
+                        let reduction = if
+                            depth_left > 2 &&
+                            !is_in_check &&
+                            !mov.is_tactical()
+                            {
+                                1
+                            } else {
+                                0
+                            };
+
+                        // After we have PV-node (that raised alpha) all other nodes will be searched
+                        // with zero-window first to confirm this assumption.
+                        // Also (optionally) apply Late Move Reductions
+                        // TODO: changing 0.001 -> 0.0001 leads to a weird bug
+                        let result = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1 - reduction, &mut killer_moves, should_verify, deadline);
+                        // 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 {
+                            self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, should_verify, deadline)
+                        } else {
+                            result
+                        }
+                    };
+                    score *= -1.;
+                    self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
+
+                    if score >= beta {
+                        self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                            hash: self.hash,
+                            mov,
+                            depth: depth_left, // TODO: should be actual depth searched
+                            node_type: NodeType::Cut,
+                            score,
+                        });
+
+                        if mov.kind == MoveKind::Quiet {
+                            match parent_killers.iter().find(|&&m| m == mov) {
+                                None => parent_killers.push(mov),
+                                Some(..) => {},
+                            }
                         }
-                    }
 
-                    return (beta, principal_variation);
+                        return (beta, principal_variation);
+                    }
+                    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.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                            hash: self.hash,
+                            mov,
+                            depth: depth_left, // TODO: should be actual depth searched
+                            node_type: NodeType::PV,
+                            score,
+                        });
+                    } else if self.transposition().is_none() {
+                        self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                            hash: self.hash,
+                            mov,
+                            depth: depth_left, // TODO: should be actual depth searched
+                            node_type: NodeType::All,
+                            score,
+                        });
+                    }
+                } else {
+                    self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
                 }
-                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.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
-                        hash: self.hash,
-                        mov,
-                        depth: depth_left, // TODO: should be actual depth searched
-                        node_type: NodeType::PV,
-                        score,
-                    });
-                } else if self.transposition().is_none() {
-                    self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
-                        hash: self.hash,
-                        mov,
-                        depth: depth_left, // TODO: should be actual depth searched
-                        node_type: NodeType::All,
-                        score,
-                    });
+
+                // Could not finish in time, return what we have so far
+                if Instant::now() > deadline {
+                    break;
                 }
-            } 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 {
-                break;
+            if !legal_move_found {
+                if is_in_check {
+                    return (-VALUE_WIN, principal_variation);
+                }
             }
-        }
 
-        if !legal_move_found {
-            if is_in_check {
-                return (-VALUE_WIN, principal_variation);
+            if zugzwang_candidate {
+                // Null move predicted beta-cutoff, but in reality no move increased beta
+                // - we are in zugzwang! Re-search with original depth
+                depth_left += 1;
+                zugzwang_candidate = false;
+                should_verify = true;
+                continue;
             }
-        }
 
-        (alpha, principal_variation)
+            return (alpha, principal_variation)
+        }
     }
 
     pub fn quiscence(&mut self, mut alpha: f32, beta: f32) -> f32 {
@@ -579,7 +599,7 @@ impl Board {
             if print {
                 println!("\nSearching depth({}) in the window {:?}", depth, (alpha, beta));
             }
-            let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, deadline);
+            let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, true, deadline);
 
             if search_result.0.abs() >= VALUE_WIN {
                 return search_result
@@ -604,7 +624,7 @@ impl Board {
                 beta = alpha + window_size * 0.1;
                 alpha = search_result.0 - window_size * 2.0f32.powi(gradual_widening_counter);
                 if latest_cutoff == Some(Cutoff::Beta) {
-                    println!("Detected search instability! You are probably in Zugzwang. Aborting...");
+                    println!("Detected search instability! Skipping current depth.");
                     depth += 1;
                     latest_cutoff = None;
                     gradual_widening_counter = 0;
@@ -623,7 +643,7 @@ impl Board {
                 alpha = beta - window_size * 0.1;
                 beta = search_result.0 + window_size * 2.0f32.powi(gradual_widening_counter);
                 if latest_cutoff == Some(Cutoff::Alpha) {
-                    println!("Detected search instability! You are probably in Zugzwang. Aborting...");
+                    println!("Detected search instability! Skipping current depth.");
                     depth += 1;
                     latest_cutoff = None;
                     gradual_widening_counter = 0;