diff options
author | eug-vs <eugene@eug-vs.xyz> | 2023-09-03 04:15:40 +0300 |
---|---|---|
committer | eug-vs <eugene@eug-vs.xyz> | 2023-09-03 04:24:00 +0300 |
commit | 395c2066ece606e66a08b7bb69a6ea0a659462c5 (patch) | |
tree | 9c64851c3ac1d462670a0d51339340c89ec113c6 | |
parent | 08060989f1e3b2669e5969b12aaa35e56d0ff214 (diff) | |
download | chessnost-395c2066ece606e66a08b7bb69a6ea0a659462c5.tar.gz |
feat: apply Mate Distance Pruning
-rw-r--r-- | benches/search.rs | 4 | ||||
-rw-r--r-- | src/grossmeister/search.rs | 63 |
2 files changed, 52 insertions, 15 deletions
diff --git a/benches/search.rs b/benches/search.rs index 26c4c09..89c59d5 100644 --- a/benches/search.rs +++ b/benches/search.rs @@ -12,10 +12,10 @@ fn main() { println!("Finished in {:?}: score={:?} {:?}", start.elapsed(), score, pv); gm.board.print(); for mov in pv { - println!("Score for {:?} is now: {}", gm.board.color(), gm.quiscence(-INFINITY, INFINITY)); + println!("Score for {:?} is now: {}", gm.board.color(), gm.quiscence(-INFINITY, INFINITY, 0)); println!("{:?}", mov); gm.board.make_move(mov); gm.board.print(); } - println!("Score for {:?} is now: {}", gm.board.color(), gm.quiscence(-INFINITY, INFINITY)); + println!("Score for {:?} is now: {}", gm.board.color(), gm.quiscence(-INFINITY, INFINITY, 0)); } diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs index c77eaff..c899216 100644 --- a/src/grossmeister/search.rs +++ b/src/grossmeister/search.rs @@ -4,7 +4,7 @@ use crate::{moves::{Move, MoveKind}, board::io::IO}; use super::{Grossmeister, ttable::{NodeType, TTABLE_SIZE, TranspositionTableItem}}; -const VALUE_WIN: f32 = 20_000.0; +const SCORE_MATE: f32 = 20_000.0; #[derive(Debug, Default, PartialEq)] pub struct PerftResult { @@ -16,7 +16,31 @@ pub struct PerftResult { } impl Grossmeister { - pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, root_distance: u8) -> (f32, Vec<Move>) { + // Mate distance pruning + // If a non-zero value (mating score) is returned, branch could be safely pruned + pub fn MDP(alpha: &mut f32, beta: &mut f32, root_distance: u8) -> f32 { + { // Update bound in case we are winning + let mating_score = SCORE_MATE - root_distance as f32; + if mating_score < *beta { + *beta = mating_score; + if *alpha >= mating_score { + return mating_score + } + } + } + { // Update bound in case we are losing + let mating_score = -SCORE_MATE + root_distance as f32; + if mating_score > *alpha { + *alpha = mating_score; + if *beta <= mating_score { + return mating_score + } + } + } + 0.0 + } + + pub fn negamax_search(&mut self, mut alpha: f32, mut beta: f32, depth_left: u8, root_distance: u8) -> (f32, Vec<Move>) { let mut principal_variation = Vec::new(); let color = self.board.color(); @@ -52,6 +76,12 @@ impl Grossmeister { return (self.quiscence(alpha, beta, root_distance), principal_variation); } + // Mate distance pruning + let mating_score = Grossmeister::MDP(&mut alpha, &mut beta, root_distance); + if mating_score != 0.0 { + return (mating_score, principal_variation) + } + let mut should_pv_search = true; let mut legal_move_found = false; @@ -134,7 +164,7 @@ impl Grossmeister { if !legal_move_found { if self.board.is_king_in_check(color) { - return (-VALUE_WIN + root_distance as f32, principal_variation); + return (-SCORE_MATE + root_distance as f32, principal_variation); } else { return (0.0, principal_variation); } @@ -143,7 +173,7 @@ impl Grossmeister { (alpha, principal_variation) } - pub fn quiscence(&mut self, mut alpha: f32, beta: f32, root_distance: u8) -> f32 { + pub fn quiscence(&mut self, mut alpha: f32, mut beta: f32, root_distance: u8) -> f32 { let color = self.board.color(); if self.board.positions.iter().filter(|p| **p == self.board.hash).count() >= 3 { @@ -151,6 +181,13 @@ impl Grossmeister { return 0.0; } + // Mate distance pruning + let mating_score = Grossmeister::MDP(&mut alpha, &mut beta, root_distance); + if mating_score != 0.0 { + return mating_score + } + + let mut tactical_only = false; if !self.board.is_king_in_check(color) { // If we are not in check, we can evaluate stand pat @@ -192,7 +229,7 @@ impl Grossmeister { } if !legal_move_found && self.board.is_king_in_check(color) { - return -VALUE_WIN + root_distance as f32 + return -SCORE_MATE + root_distance as f32 } alpha @@ -215,9 +252,9 @@ impl Grossmeister { let search_result = self.negamax_search(alpha, beta, depth, 0); - if search_result.0.abs() >= VALUE_WIN - 128f32 { // TODO: VALUE_WIN - MAX_PLY + if search_result.0.abs() >= SCORE_MATE - 128f32 { // TODO: VALUE_WIN - MAX_PLY let score = search_result.0; - let mate_distance = (VALUE_WIN - score.abs()) * if score > 0.0 { + let mate_distance = (SCORE_MATE - score.abs()) * if score > 0.0 { 1. } else { -1. // -N means we are mated in N plies @@ -226,7 +263,7 @@ impl Grossmeister { result = Some(search_result); - if score.abs() == VALUE_WIN { + if score.abs() == SCORE_MATE { break; } else { depth += 1; @@ -361,7 +398,7 @@ impl Grossmeister { #[cfg(test)] mod tests { use crate::{board::{Board, io::IO}, square::Square, moves::{Move, MoveKind}, grossmeister::{Grossmeister, search::PerftResult}}; - use super::VALUE_WIN; + use super::SCORE_MATE; #[test] fn perft() { @@ -401,13 +438,13 @@ mod tests { } #[test] - fn checkmate() { + fn mate_in_3() { 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); - assert_eq!(score, VALUE_WIN); + assert_eq!(score, SCORE_MATE - 3.0); assert_eq!(pv, vec![ Move { source: Square::F3, target: Square::C6, kind: MoveKind::Capture }, Move { source: Square::B7, target: Square::C6, kind: MoveKind::Capture }, @@ -452,7 +489,7 @@ mod tests { gm.debug = true; let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); - assert_eq!(VALUE_WIN - score, 3.0); // Mate in 3 plies + assert_eq!(SCORE_MATE - score, 3.0); // Mate in 3 plies } #[test] @@ -464,6 +501,6 @@ mod tests { gm.debug = true; let (score, pv) = gm.iterative_deepening(5); dbg!(score, pv); - assert_eq!(score + VALUE_WIN, 4.0); // Mate in 4 plies + assert_eq!(score + SCORE_MATE, 4.0); // Mate in 4 plies } } |