feat: put killers directly after winning captures

1 files changed, 43 insertions, 19 deletions

diff --git a/src/board/engine.rs b/src/board/engine.rs
index 821c4a4..c43a722 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -229,7 +229,7 @@ impl Board {
         }
     }
 
-    pub fn order_moves(&self, moves: Vec<Move>) -> Vec<Move> {
+    pub fn order_moves(&self, moves: Vec<Move>, killer_moves: Vec<Move>) -> Vec<Move> {
         let mut moves_with_eval: Vec<(Move, f32)> = moves
             .iter()
             .map(|m| (*m, self.eval_move(*m)))
@@ -248,21 +248,41 @@ impl Board {
             a_eval.total_cmp(b_eval).reverse()
         });
 
-        moves_with_eval.iter_mut().map(|(m, _)| *m).collect()
-    }
+        let mut ordered_moves: Vec<Move> = moves_with_eval.iter().map(|(m, _)| *m).collect();
 
-    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();
+        // Insert killer moves after winning captures
+        let equal_capture_index = match moves_with_eval.iter().position(|(m, eval)| m.is_tactical() && *eval == 0.0) {
+            Some(x) => x,
+            None => 0,
+        };
 
-        let mut moves = self.generate_pseudolegal_moves(color);
-        moves = self.order_moves(moves);
+        for killer in killer_moves {
+            match ordered_moves.iter().position(|m| *m == killer) {
+                Some(index) => {
+                    let mov = ordered_moves.remove(index);
+                    ordered_moves.insert(equal_capture_index, mov);
+                }
+                None => {}
+            };
+
+        }
 
         match self.hash_move() {
-            Some(mov) => moves.insert(0, mov),
+            Some(mov) => ordered_moves.insert(0, mov),
             None => {},
         }
 
+        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>) {
+        let mut principal_variation = Vec::new();
+        let mut killer_moves = Vec::new();
+        let color = self.color();
+
+        let mut moves = self.generate_pseudolegal_moves(color);
+        moves = self.order_moves(moves, parent_killers.to_vec());
+
         if depth_left == 0 {
             return (self.quiscence(alpha, beta), principal_variation);
         }
@@ -280,15 +300,15 @@ impl Board {
 
                 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, deadline)
+                    self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, deadline)
                 } else {
                     // After we have PV-node (that raised alpha) all other nodes will be searched
                     // with zero-window first to confirm this assumption
-                    let result = self.negamax_search(-(alpha + 0.0001), -alpha, depth_left - 1, deadline);
+                    let result = self.negamax_search(-(alpha + 0.0001), -alpha, depth_left - 1, &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, deadline)
+                        self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, deadline)
                     } else {
                         result
                     }
@@ -305,6 +325,13 @@ impl Board {
                         score,
                     });
 
+                    if mov.kind == MoveKind::Quiet {
+                        match parent_killers.iter().find(|m| **m == mov) {
+                            None => parent_killers.push(mov),
+                            Some(..) => {},
+                        }
+                    }
+
                     return (beta, principal_variation);
                 }
                 if score > alpha {
@@ -352,12 +379,7 @@ impl Board {
     pub fn quiscence(&mut self, mut alpha: f32, beta: f32) -> f32 {
         let color = self.color();
         let mut moves = self.generate_pseudolegal_moves(color);
-        moves = self.order_moves(moves);
-
-        match self.hash_move() {
-            Some(mov) => moves.insert(0, mov),
-            None => {},
-        }
+        moves = self.order_moves(moves, Vec::new());
 
         let stand_pat = self.evaluate(Some(moves.len() as f32));
 
@@ -403,10 +425,12 @@ impl Board {
         let mut beta = INFINITY;
         let window_size = 0.5;
         let mut gradual_widening_counter = 0;
+        let mut root_killers: Vec<Move> = Vec::new();
+
 
         while depth <= max_depth {
             println!("\nSearching depth({}) in the window {:?}", depth, (alpha, beta));
-            let search_result = self.negamax_search(alpha, beta, depth, deadline);
+            let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, deadline);
 
             if search_result.0.abs() >= VALUE_WIN {
                 return search_result