From 9749c21b06f20bcaf983140970d881a0f43c6297 Mon Sep 17 00:00:00 2001 From: eug-vs Date: Fri, 27 Jan 2023 21:47:48 +0300 Subject: tmp: killer moves --- src/board/engine.rs | 33 ++++++++++++++++++++++++++++++--- 1 file changed, 30 insertions(+), 3 deletions(-) diff --git a/src/board/engine.rs b/src/board/engine.rs index 05cb1e7..8852c1f 100644 --- a/src/board/engine.rs +++ b/src/board/engine.rs @@ -204,13 +204,29 @@ impl Board { }); } - pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, deadline: Instant) -> (f32, Vec) { + pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec, deadline: Instant) -> (f32, Vec) { let mut principal_variation = Vec::new(); + let mut killer_moves = Vec::new(); let color = self.color(); let mut moves = self.generate_pseudolegal_moves(color); self.order_moves(&mut moves); + 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 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); + } + } + match self.transposition_table[(self.hash % TTABLE_SIZE) as usize] { Some(item) => { if item.hash == self.hash { @@ -231,7 +247,7 @@ impl Board { let captured_piece = self.make_move(mov); if !self.is_king_in_check(color) { - 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); @@ -244,6 +260,15 @@ impl Board { score, }); + if mov.kind == MoveKind::Quiet { + // println!("Killer {:?} found at depth {}", mov, depth_left); + // self.print(); + match parent_killers.iter().find(|m| **m == mov) { + None => parent_killers.push(mov), + Some(..) => {}, + } + } + return (beta, principal_variation); } if score > alpha { @@ -338,10 +363,12 @@ impl Board { let mut depth = 1; let mut alpha = -INFINITY; let mut beta = INFINITY; + let mut root_killers: Vec = Vec::new(); let window_size = 0.25; + while depth <= max_depth { - let search_result = self.negamax_search(alpha, beta, depth, deadline); + let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, deadline); println!("Finished depth({}) {:?} [{:?} left]", depth, search_result, deadline - Instant::now()); if Instant::now() > deadline { -- cgit v1.2.3 From 2eb7603f298fbe719320d0b6433bd8566d4cce8f Mon Sep 17 00:00:00 2001 From: eug-vs Date: Sun, 29 Jan 2023 10:19:13 +0300 Subject: fix: do not use killers outside of movelist --- src/board/engine.rs | 57 ++++++++++++++++++++++++++--------------------------- 1 file changed, 28 insertions(+), 29 deletions(-) diff --git a/src/board/engine.rs b/src/board/engine.rs index 6a0db61..a5f6894 100644 --- a/src/board/engine.rs +++ b/src/board/engine.rs @@ -229,7 +229,7 @@ impl Board { } } - pub fn order_moves(&self, moves: Vec) -> Vec { + pub fn order_moves(&self, moves: Vec, killer_moves: Vec) -> Vec { let mut moves_with_eval: Vec<(Move, f32)> = moves .iter() .map(|m| (*m, self.eval_move(*m))) @@ -248,36 +248,40 @@ impl Board { a_eval.total_cmp(b_eval).reverse() }); - moves_with_eval.iter_mut().map(|(m, _)| *m).collect() - } + let mut ordered_moves: Vec = moves_with_eval.iter().map(|(m, _)| *m).collect(); - pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec, deadline: Instant) -> (f32, Vec) { - let mut principal_variation = Vec::new(); - let mut killer_moves = Vec::new(); - let color = self.color(); + // Insert killer moves after non-losing captures + let losing_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(losing_capture_index, mov); + } + None => {} + }; + + } match self.hash_move() { - Some(mov) => moves.insert(0, mov), + Some(mov) => ordered_moves.insert(0, mov), None => {}, } - let loosing_capture_index = match moves.iter().position(|m| { - m.is_tactical() && self.eval_move(*m) < 0.0 - }) { - Some(x) => x, - None => 0, - }; + ordered_moves + } - // 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); - } - } + pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec, deadline: Instant) -> (f32, Vec) { + 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); @@ -358,12 +362,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)); -- cgit v1.2.3