diff options
| -rw-r--r-- | benches/search.rs | 2 | ||||
| -rw-r--r-- | src/grossmeister/search.rs | 136 |
2 files changed, 71 insertions, 67 deletions
diff --git a/benches/search.rs b/benches/search.rs index 926f5c3..89c59d5 100644 --- a/benches/search.rs +++ b/benches/search.rs @@ -7,7 +7,7 @@ fn main() { let mut gm = Grossmeister::new(board); let start = Instant::now(); - let (score, pv) = gm.iterative_deepening(8).unwrap(); + let (score, pv) = gm.iterative_deepening(8); println!("Finished in {:?}: score={:?} {:?}", start.elapsed(), score, pv); gm.board.print(); diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs index 455fb6f..378349c 100644 --- a/src/grossmeister/search.rs +++ b/src/grossmeister/search.rs @@ -40,31 +40,27 @@ impl Grossmeister { 0.0 } - pub fn negamax_search(&mut self, mut alpha: Score, mut beta: Score, depth_left: u8, root_distance: u8) -> (Score, Vec<Move>) { - let mut principal_variation = Vec::new(); + pub fn negamax_search(&mut self, mut alpha: Score, mut beta: Score, depth_left: u8, root_distance: u8) -> Score { let color = self.board.color(); if self.board.threefold_repetition() { - return (0.0, principal_variation); + return 0.0 } if let Some(transposition) = self.transposition() { if transposition.depth == depth_left { match transposition.node_type { NodeType::PV => { // PV-nodes have exact score - principal_variation.push(transposition.mov); - return (transposition.score, principal_variation); + return transposition.score } NodeType::Cut => { if transposition.score >= beta { - principal_variation.push(transposition.mov); - return (beta, principal_variation); + return beta } } NodeType::All => { if transposition.score <= alpha { - principal_variation.push(transposition.mov); - return (alpha, principal_variation); + return alpha } } } @@ -74,11 +70,11 @@ impl Grossmeister { // Mate distance pruning let mating_score = Grossmeister::MDP(&mut alpha, &mut beta, root_distance); if mating_score != 0.0 { - return (mating_score, principal_variation) + return mating_score } if depth_left == 0 { - return (self.quiscence(alpha, beta, root_distance), principal_variation); + return self.quiscence(alpha, beta, root_distance) } let mut should_pv_search = true; @@ -94,20 +90,20 @@ impl Grossmeister { if !self.board.is_king_in_check(color) { legal_move_found = true; - let (mut score, mut subtree_pv) = if should_pv_search { + let mut score = 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, root_distance + 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, root_distance + 1); + let score = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1, root_distance + 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 { + if -score > alpha { self.negamax_search(-beta, -alpha, depth_left - 1, root_distance + 1) } else { - result + score } }; score *= -1.; @@ -126,14 +122,11 @@ impl Grossmeister { self.register_killer(mov); } - return (beta, principal_variation); + return beta } 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.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { hash: self.board.hash, @@ -163,13 +156,13 @@ impl Grossmeister { if !legal_move_found { if self.board.is_king_in_check(color) { - return (-SCORE_MATE + root_distance as Score, principal_variation); + return -SCORE_MATE + root_distance as Score } else { - return (0.0, principal_variation); + return 0.0 } } - (alpha, principal_variation) + alpha } pub fn quiscence(&mut self, mut alpha: Score, mut beta: Score, root_distance: u8) -> Score { @@ -233,8 +226,30 @@ impl Grossmeister { alpha } - pub fn iterative_deepening(&mut self, max_depth: u8) -> Option<(Score, Vec<Move>)> { - let mut result = None; + fn reconstruct_pv(&mut self, depth: u8) -> Vec<Move> { + let mut pv = Vec::with_capacity(depth as usize); + + if let Some(transposition) = self.transposition() { + let mov = transposition.mov; + let ep_target_before = self.board.ep_target; + let castling_rights_before = self.board.castling_rights; + let hash_before = self.board.hash; + let captured = self.board.make_move(mov); + + let mut subtree_pv = self.reconstruct_pv(depth - 1); + self.board.unmake_move(mov, captured, ep_target_before, castling_rights_before, hash_before); + + pv.push(mov); + pv.append(&mut subtree_pv); + } + debug_assert!(pv.len() == depth as usize); + pv + } + + pub fn iterative_deepening(&mut self, max_depth: u8) -> (Score, Vec<Move>) { + let mut best_score = 0.0; + let mut pv = Vec::new(); + let mut depth = 1; let mut alpha = -INFINITY; let mut beta = INFINITY; @@ -246,81 +261,70 @@ impl Grossmeister { println!("info string window {:?}", (alpha, beta)); } - let search_result = self.negamax_search(alpha, beta, depth, 0); + let score = self.negamax_search(alpha, beta, depth, 0); if self.should_halt.load(std::sync::atomic::Ordering::SeqCst) { println!("info string halting search"); break; } - if search_result.0 <= alpha { // Alpha-cutoff + if score <= alpha { // Alpha-cutoff gradual_widening_counter += 1; beta = alpha + window_size * 0.1; - alpha = search_result.0 - window_size * 2.0f32.powi(gradual_widening_counter); + alpha = score - window_size * 2.0f32.powi(gradual_widening_counter); println!("info depth {} score upperbound {:.0}", depth, beta * 100.0); continue; } - if search_result.0 >= beta { // Beta-cutoff + if score >= beta { // Beta-cutoff gradual_widening_counter += 1; alpha = beta - window_size * 0.1; - beta = search_result.0 + window_size * 2.0f32.powi(gradual_widening_counter); + beta = score + window_size * 2.0f32.powi(gradual_widening_counter); println!("info depth {} score lowerbound {:.0}", depth, alpha * 100.0); continue; } - if search_result.1.is_empty() { - panic!("Why the fuck no moves?"); - } + best_score = score; + pv = self.reconstruct_pv(depth); // Print UCI info print!("info depth {} score ", depth); - if search_result.0.abs() >= SCORE_MATE - 128f32 { // TODO: VALUE_WIN - MAX_PLY - let mate_distance = (SCORE_MATE - search_result.0.abs()) * if search_result.0 > 0.0 { + if score.abs() >= SCORE_MATE - 128f32 { // TODO: VALUE_WIN - MAX_PLY + let mate_distance = (SCORE_MATE - score.abs()) * if score > 0.0 { 1. } else { -1. // -N means we are mated in N plies }; print!("mate {:.0} ", (mate_distance / 2.0).ceil()); } else { - print!("cp {:.0} ", search_result.0 * 100.0) + print!("cp {:.0} ", score * 100.0) } print!("pv "); - for mov in &search_result.1 { + for mov in &pv { print!("{} ", mov); } println!(); - // If our score is mate in N, we break at depth N - if depth as Score >= SCORE_MATE - search_result.0.abs() { - result = Some(search_result); - break; - } - depth += 1; gradual_widening_counter = 0; - alpha = search_result.0 - window_size; - beta = search_result.0 + window_size; - result = Some(search_result); - } + alpha = score - window_size; + beta = score + window_size; - 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, 0)) + // If our score is mate in N, we break at depth N + if depth as Score >= SCORE_MATE - score.abs() { + break; + } } println!("info hashfull {}", 1000 * self.transposition_table.iter().filter(|item| item.is_some()).count() / self.transposition_table.len()); - - if let Some(r) = result.clone() { - if !r.1.is_empty() { - print!("bestmove {}", r.1[0]); - } - if r.1.len() > 1 { - print!(" ponder {}", r.1[1]) - } - println!(); + if !pv.is_empty() { + print!("bestmove {}", pv[0]); + } + if pv.len() > 1 { + print!(" ponder {}", pv[1]) } + println!(); - result + (best_score, pv) } pub fn perft(&mut self, depth: u8, print: bool) -> PerftResult { @@ -436,7 +440,7 @@ mod tests { let fen = String::from("2kr1b1r/pp1npppp/2p1bn2/7q/5B2/2NB1Q1P/PPP1N1P1/2KR3R w - - 0 1"); let board = Board::from_FEN(fen); let mut gm = Grossmeister::new(board); - let (score, pv) = gm.iterative_deepening(8).unwrap(); + let (score, pv) = gm.iterative_deepening(8); assert_eq!(score, SCORE_MATE - 3.0); assert_eq!(pv, vec![ @@ -452,7 +456,7 @@ mod tests { let board = Board::from_FEN(fen); let mut gm = Grossmeister::new(board); - let (_, pv) = gm.iterative_deepening(6).unwrap(); + let (_, pv) = gm.iterative_deepening(6); assert_eq!( pv[0], Move { source: Square::F5, target: Square::H4, kind: MoveKind::Quiet }, @@ -466,7 +470,7 @@ mod tests { let board = Board::from_FEN(fen); let mut gm = Grossmeister::new(board); - let (_, pv) = gm.iterative_deepening(5).unwrap(); + let (_, pv) = gm.iterative_deepening(5); assert_eq!( pv[0], Move { source: Square::C2, target: Square::C3, kind: MoveKind::Quiet }, @@ -481,7 +485,7 @@ mod tests { let mut gm = Grossmeister::new(board); gm.debug = true; - let (score, pv) = gm.iterative_deepening(5).unwrap(); + let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); assert_eq!(SCORE_MATE - score, 3.0); // Mate in 3 plies } @@ -493,7 +497,7 @@ mod tests { let mut gm = Grossmeister::new(board); gm.debug = true; - let (score, pv) = gm.iterative_deepening(5).unwrap(); + let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); assert_eq!(score + SCORE_MATE, 4.0); // Mate in 4 plies } @@ -505,7 +509,7 @@ mod tests { let mut gm = Grossmeister::new(board); gm.debug = true; - let (score, pv) = gm.iterative_deepening(5).unwrap(); + let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); assert_eq!(SCORE_MATE - score, 3.0); // Mate in 3 plies } @@ -517,7 +521,7 @@ mod tests { let mut gm = Grossmeister::new(board); gm.debug = true; - let (score, pv) = gm.iterative_deepening(5).unwrap(); + let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); assert!(score <= 0.0); } |