feat: implement killer heuristic

1 files changed, 28 insertions, 3 deletions

diff --git a/src/board/engine.rs b/src/board/engine.rs
index 2c294a3..6a0db61 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -251,8 +251,9 @@ impl Board {
         moves_with_eval.iter_mut().map(|(m, _)| *m).collect()
     }
 
-    pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, deadline: Instant) -> (f32, Vec<Move>) {
+    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);
@@ -263,6 +264,21 @@ impl Board {
             None => {},
         }
 
+        let loosing_capture_index = match moves.iter().position(|m| {
+            m.is_tactical() && self.eval_move(*m) < 0.0
+        }) {
+            Some(x) => x,
+            None => 0,
+        };
+
+        // Insert killer moves (from previous siblings) after winning and equal captures
+        for mov in &mut *parent_killers {
+            // Validate that killer piece still exists
+            if mov.source.to_bitboard() & self.color_occupancy(color) > 0 {
+                moves.insert(loosing_capture_index, *mov);
+            }
+        }
+
         if depth_left == 0 {
             return (self.quiscence(alpha, beta), principal_variation);
         }
@@ -276,7 +292,7 @@ impl Board {
 
             if !self.is_king_in_check(color) {
                 legal_move_found = true;
-                let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1, deadline);
+                let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, deadline);
                 score *= -1.;
                 self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
 
@@ -289,6 +305,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 {
@@ -386,10 +409,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