diff options
Diffstat (limited to 'src/grossmeister/search.rs')
| -rw-r--r-- | src/grossmeister/search.rs | 426 |
1 files changed, 426 insertions, 0 deletions
diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs new file mode 100644 index 0000000..57ce672 --- /dev/null +++ b/src/grossmeister/search.rs @@ -0,0 +1,426 @@ +use std::{time::{Instant, Duration}, f32::INFINITY}; + +use crate::{moves::{Move, MoveKind}, board::io::IO}; + +use super::{Grossmeister, ttable::{NodeType, TTABLE_SIZE, TranspositionTableItem}}; + +const VALUE_WIN: f32 = 20_000.0; + +#[derive(Debug, Default, PartialEq)] +pub struct PerftResult { + leaf_nodes: u64, + captures: u64, + en_passants: u64, + castles: u64, + checks: u64, +} + +impl Grossmeister { + 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.board.color(); + + match self.transposition() { + Some(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); + } + NodeType::Cut => { + if transposition.score >= beta { + principal_variation.push(transposition.mov); + return (beta, principal_variation); + } + } + NodeType::All => { + if transposition.score <= alpha { + principal_variation.push(transposition.mov); + return (alpha, principal_variation); + } + } + } + } + } + None => {}, + } + + if depth_left == 0 { + return (self.quiscence(alpha, beta), principal_variation); + } + + let mut moves = self.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 { + let ep_target_before = self.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + + if !self.board.is_king_in_check(color) { + legal_move_found = true; + + 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, deadline) + } 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, 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, &mut killer_moves, deadline) + } else { + result + } + }; + score *= -1.; + self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + + if score >= beta { + self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.board.hash, + mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::Cut, + 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 { + 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, + mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::PV, + score, + }); + } else if self.transposition().is_none() { + self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.board.hash, + mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::All, + score, + }); + } + } else { + self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + } + + // Could not finish in time, return what we have so far + if Instant::now() > deadline { + break; + } + } + + if !legal_move_found { + if self.board.is_king_in_check(color) { + return (-VALUE_WIN, principal_variation); + } + } + + (alpha, principal_variation) + } + + pub fn quiscence(&mut self, mut alpha: f32, beta: f32) -> f32 { + let color = self.board.color(); + let mut moves = self.generate_pseudolegal_moves(); + moves = self.order_moves(moves, Vec::new()); + + if !self.board.is_king_in_check(color) { + // If we are not in check, we can evaluate stand pat + let stand_pat = self.evaluate(); + + if stand_pat >= beta { + return beta; + } + if alpha < stand_pat { + alpha = stand_pat; + } + + // If we are not in check, we can only search tactical moves + moves = moves + .iter() + .filter(|m| m.is_tactical()) + .map(|m| *m) + .collect() + } + + let mut legal_move_found = false; + for mov in moves { + let ep_target_before = self.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + + if !self.board.is_king_in_check(color) { + legal_move_found = true; + let evaluation = -self.quiscence(-beta, -alpha); + self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + + if evaluation >= beta { + return beta; // Fail-hard beta-cutoff + } + if evaluation > alpha { + alpha = evaluation; + } + } else { + self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + } + } + + if !legal_move_found { + if self.board.is_king_in_check(color) { + return -VALUE_WIN + } + } + + alpha + } + + pub fn iterative_deepening(&mut self, max_depth: u8, duration: Duration, print: bool) -> (f32, Vec<Move>) { + let start = Instant::now(); + let deadline = start + duration; + let mut result = None; + let mut depth = 1; + let mut alpha = -INFINITY; + 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 { + if print { + println!("\nSearching depth({}) in the window {:?}", depth, (alpha, beta)); + } + let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, deadline); + + if search_result.0.abs() >= VALUE_WIN { + return search_result + } + + if Instant::now() > deadline { + if print { + println!("Aborting..."); + } + break; + } + + if print { + println!("Finished depth({}) {:?} [{:?} left]", depth, search_result, deadline - Instant::now()); + } + + if search_result.0 <= alpha { // Alpha-cutoff + if print { + println!("Alpha cutoff {} <= {:?}", search_result.0, (alpha, beta)); + } + gradual_widening_counter += 1; + beta = alpha + window_size * 0.1; + alpha = search_result.0 - window_size * 2.0f32.powi(gradual_widening_counter); + continue; + } + if search_result.0 >= beta { // Beta-cutoff + if print { + println!("Beta cutoff {:?} <= {}", (alpha, beta), search_result.0); + } + gradual_widening_counter += 1; + alpha = beta - window_size * 0.1; + beta = search_result.0 + window_size * 2.0f32.powi(gradual_widening_counter); + continue; + } + + if search_result.1.len() > 0 { + depth += 1; + gradual_widening_counter = 0; + alpha = search_result.0 - window_size; + beta = search_result.0 + window_size; + } else { + panic!("Why the fuck no moves?"); + } + + result = Some(search_result); + } + + match result { + Some(r) => return r, + None => panic!("Could not find a move in time"), + } + } + + pub fn perft(&mut self, depth: u8, print: bool) -> PerftResult { + let mut result = PerftResult::default(); + + if depth == 0 { + result.leaf_nodes = 1; + return result; + } + let color = self.board.color(); + + let moves = self.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()); + } + + for mov in moves { + let ep_target_before = self.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + // King can not be in check after our own move + if !self.board.is_king_in_check(color) { + if depth == 1 { + match mov.kind { + MoveKind::Capture => { + result.captures += 1; + } + MoveKind::EnPassant => { + result.en_passants += 1; + result.captures += 1; + } + MoveKind::Castle => { + result.castles += 1; + } + _ => {} + } + if self.board.is_king_in_check(color.flip()) { + result.checks += 1; + } + } + + if print { + println!("{:?}", mov); + self.board.print(); + } + let subtree_result = self.perft(depth - 1, print); + + result.leaf_nodes += subtree_result.leaf_nodes; + result.captures += subtree_result.captures; + result.checks += subtree_result.checks; + result.castles += subtree_result.castles; + result.en_passants += subtree_result.en_passants; + + } + self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + } + + if print { + println!("Found {} leaf nodes in this subtree (depth {})", result.leaf_nodes, depth); + } + + result + } +} + + +#[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; + + #[test] + fn perft() { + let board = Board::new(); + let mut gm = Grossmeister::new(board); + + assert_eq!(gm.perft(0, false), PerftResult { leaf_nodes: 1, captures: 0, en_passants: 0, castles: 0 , checks: 0 }); + assert_eq!(gm.perft(1, false), PerftResult { leaf_nodes: 20, captures: 0, en_passants: 0, castles: 0 , checks: 0 }); + assert_eq!(gm.perft(2, false), PerftResult { leaf_nodes: 400, captures: 0, en_passants: 0, castles: 0 , checks: 0 }); + assert_eq!(gm.perft(3, false), PerftResult { leaf_nodes: 8902, captures: 34, en_passants: 0, castles: 0 , checks: 12 }); + assert_eq!(gm.perft(4, false), PerftResult { leaf_nodes: 197281, captures: 1576, en_passants: 0, castles: 0 , checks: 469 }); + // assert_eq!(board.perft(5, false), PerftResult { leaf_nodes: 4865609, captures: 82719, en_passants: 258, castles: 0, checks: 27351 }); + } + + #[test] + fn position_perft() { + let fen = String::from("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - "); + let board = Board::from_FEN(fen); + let mut gm = Grossmeister::new(board); + + assert_eq!(gm.perft(0, false), PerftResult { leaf_nodes: 1, captures: 0, en_passants: 0, castles: 0 , checks: 0 }); + assert_eq!(gm.perft(1, false), PerftResult { leaf_nodes: 48, captures: 8, en_passants: 0, castles: 2 , checks: 0 }); + assert_eq!(gm.perft(2, false), PerftResult { leaf_nodes: 2039, captures: 351, en_passants: 1, castles: 91 , checks: 3 }); + assert_eq!(gm.perft(3, false), PerftResult { leaf_nodes: 97862, captures: 17102, en_passants: 45, castles: 3162, checks: 993 }); + // assert_eq!(board.perft(4, false), PerftResult { leaf_nodes: 4085603, captures: 757163, en_passants: 1929, castles: 128013, checks: 25523 }); + } + + #[test] + fn endgame_perft() { + let fen = String::from("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - "); + let board = Board::from_FEN(fen); + let mut gm = Grossmeister::new(board); + + assert_eq!(gm.perft(1, false), PerftResult { leaf_nodes: 14, captures: 1, en_passants: 0, castles: 0 , checks: 2 }); + assert_eq!(gm.perft(2, false), PerftResult { leaf_nodes: 191, captures: 14, en_passants: 0, castles: 0 , checks: 10 }); + // assert_eq!(board.perft(3, false), PerftResult { leaf_nodes: 2812, captures: 209, en_passants: 2, castles: 0 , checks: 267 }); + } + + #[test] + fn checkmate() { + 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, Duration::from_secs(15), true); + + assert_eq!(score, VALUE_WIN); + assert_eq!(pv, vec![ + Move { source: Square::F3, target: Square::C6, kind: MoveKind::Capture }, + Move { source: Square::B7, target: Square::C6, kind: MoveKind::Capture }, + Move { source: Square::D3, target: Square::A6, kind: MoveKind::Quiet }, + ]); + } + + #[test] + fn stupid_knight_sac() { + let fen = String::from("r3k1r1/pp3ppp/1q6/2ppPn2/6P1/1PPP1P2/P1N3KP/R2QR3 b - - 0 18"); + let mut board = Board::from_FEN(fen); + board.ply += 1; // TODO: remove me when FEN parsing includes side to move + + let mut gm = Grossmeister::new(board); + let (_, pv) = gm.iterative_deepening(6, Duration::from_secs(60), true); + assert_eq!( + pv[0], + Move { source: Square::F5, target: Square::H4, kind: MoveKind::Quiet }, + "You should save this poor knight from danger!" + ); + } + + #[test] + fn weird_bishop_sac() { + let fen = String::from("r1b1k1nr/p4pp1/1pp1p3/4n2p/1b1qP3/1B1P3N/PPPBQPPP/RN2K2R w KQkq - 7 10"); + let board = Board::from_FEN(fen); + + let mut gm = Grossmeister::new(board); + let (_, pv) = gm.iterative_deepening(5, Duration::from_secs(60), true); + assert_eq!( + pv[0], + Move { source: Square::C2, target: Square::C3, kind: MoveKind::Quiet }, + "You should fork this bastard!" + ); + } +} |