diff options
Diffstat (limited to 'src/grossmeister/search.rs')
| -rw-r--r-- | src/grossmeister/search.rs | 111 |
1 files changed, 24 insertions, 87 deletions
diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs index 281352e..68756d8 100644 --- a/src/grossmeister/search.rs +++ b/src/grossmeister/search.rs @@ -1,9 +1,11 @@ use std::cmp::Ordering; use std::f32::INFINITY; -use crate::{moves::{Move, MoveKind}, board::io::IO}; +use smallvec::SmallVec; -use super::{Grossmeister, ttable::{NodeType, TTABLE_SIZE, TranspositionTableItem}}; +use crate::{moves::{Move, MoveKind}, board::{io::IO, move_generation::MoveList}}; + +use super::{Grossmeister, ttable::{NodeType, TTABLE_SIZE, TranspositionTableItem}, move_selector::MoveSelector}; const VALUE_WIN: f32 = 20_000.0; @@ -17,9 +19,8 @@ pub struct PerftResult { } impl Grossmeister { - pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec<Move>) -> (f32, Vec<Move>) { + pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> (f32, Vec<Move>) { let mut principal_variation = Vec::new(); - let mut killer_moves = Vec::new(); let color = self.board.color(); if self.board.positions.iter().filter(|p| **p == self.board.hash).count() >= 3 { @@ -54,12 +55,11 @@ impl Grossmeister { return (self.quiscence(alpha, beta), principal_variation); } - let mut moves = self.board.generate_pseudolegal_moves(); - moves = self.order_moves(moves, parent_killers.to_vec()); - let mut should_pv_search = true; let mut legal_move_found = false; - for mov in moves { + + self.cleanup_selector(); + while let Some(mov) = self.next_move() { let ep_target_before = self.board.ep_target; let castling_rights_before = self.board.castling_rights; let hash_before = self.board.hash; @@ -70,16 +70,16 @@ impl Grossmeister { 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) + self.negamax_search(-beta, -alpha, depth_left - 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, &mut killer_moves); + let result = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 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 { - self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves) + self.negamax_search(-beta, -alpha, depth_left - 1) } else { result } @@ -97,10 +97,7 @@ impl Grossmeister { }); if mov.kind == MoveKind::Quiet { - match parent_killers.iter().find(|m| **m == mov) { - None => parent_killers.push(mov), - Some(..) => {}, - } + self.register_killer(mov); } return (beta, principal_variation); @@ -151,14 +148,13 @@ impl Grossmeister { pub fn quiscence(&mut self, mut alpha: f32, beta: f32) -> f32 { let color = self.board.color(); - let mut moves = self.board.generate_pseudolegal_moves(); - moves = self.order_moves(moves, Vec::new()); if self.board.positions.iter().filter(|p| **p == self.board.hash).count() >= 3 { // Draw by repetition return 0.0; } + let mut tactical_only = false; if !self.board.is_king_in_check(color) { // If we are not in check, we can evaluate stand pat let stand_pat = self.evaluate(); @@ -170,12 +166,15 @@ impl Grossmeister { alpha = stand_pat; } + tactical_only = true; + // If we are not in check, we can only search tactical moves - moves.retain(|m| m.is_tactical()) + // moves.retain(|m| m.is_tactical()) } let mut legal_move_found = false; - for mov in moves { + self.cleanup_selector(); + while let Some(mov) = if tactical_only { self.next_capture() } else { self.next_move() } { let ep_target_before = self.board.ep_target; let castling_rights_before = self.board.castling_rights; let hash_before = self.board.hash; @@ -211,7 +210,6 @@ impl Grossmeister { let mut beta = INFINITY; let window_size = 0.25; let mut gradual_widening_counter = 0; - let mut root_killers: Vec<Move> = Vec::new(); while depth <= max_depth { println!("info hashfull {}", 1000 * self.transposition_table.iter().filter(|item| item.is_some()).count() / self.transposition_table.len()); @@ -220,7 +218,7 @@ impl Grossmeister { println!("info string window {:?}", (alpha, beta)); } - let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers); + let search_result = self.negamax_search(alpha, beta, depth); if search_result.0.abs() >= VALUE_WIN { println!("info mate {:.0}", (search_result.1.len() as f32 / 2.0).ceil(), ); @@ -270,7 +268,7 @@ impl Grossmeister { 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, &mut root_killers)) + result = Some(self.negamax_search(-INFINITY, INFINITY, 1)) } match result { @@ -286,65 +284,6 @@ impl Grossmeister { } } - /// Evaluate move for move ordering, prioritizing efficient captures - /// where low-value pieces capture high-value pieces - fn eval_move(&self, m: Move) -> f32 { - if m.is_tactical() { - let [source_eval, target_eval] = [m.source, m.target] - .map(|sq| self.board.piece_by_square(sq)) - .map(|p| { - match p { - Some(p) => p.static_eval(), - None => 0., - } - }); - return 2. * target_eval - source_eval - } - 0.0 - } - - 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))) - .collect(); - - moves_with_eval.sort_unstable_by(|(a, a_eval), (b, b_eval)| { - if *a_eval == 0.0 && *b_eval == 0.0 { - // Prioritize equal captures over non-captures - if a.is_tactical() && !b.is_tactical() { - return Ordering::Less - } - if b.is_tactical() && !a.is_tactical() { - return Ordering::Greater - } - } - a_eval.total_cmp(b_eval).reverse() - }); - - let mut ordered_moves: Vec<Move> = moves_with_eval.iter().map(|(m, _)| *m).collect(); - - // Insert killer moves after winning captures - let equal_capture_index = moves_with_eval - .iter() - .position(|(m, eval)| m.is_tactical() && *eval == 0.0) - .unwrap_or(0); - - for killer in killer_moves { - if let Some(index) = ordered_moves.iter().position(|m| *m == killer) { - let mov = ordered_moves.remove(index); - ordered_moves.insert(equal_capture_index, mov); - } - } - - if let Some(transposition) = self.transposition() { - ordered_moves.insert(0, transposition.mov); - } - - ordered_moves - } - - pub fn perft(&mut self, depth: u8, print: bool) -> PerftResult { let mut result = PerftResult::default(); @@ -354,14 +293,13 @@ impl Grossmeister { } let color = self.board.color(); - let moves = self.board.generate_pseudolegal_moves(); - if print { - println!("Running perft for depth {}. Color to move is {:?}\n{} moves available", depth, color, moves.len()); - println!("{} moves available", moves.len()); + // println!("Running perft for depth {}. Color to move is {:?}\n{} moves available", depth, color, moves.len()); + // println!("{} moves available", moves.len()); } - for mov in moves { + self.cleanup_selector(); + while let Some(mov) = self.next_move() { let ep_target_before = self.board.ep_target; let castling_rights_before = self.board.castling_rights; let hash_before = self.board.hash; @@ -414,7 +352,6 @@ impl Grossmeister { #[cfg(test)] mod tests { - use std::time::Duration; use crate::{board::{Board, io::IO}, square::Square, moves::{Move, MoveKind}, grossmeister::{Grossmeister, search::PerftResult}}; use super::VALUE_WIN; |