aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authoreug-vs <eugene@eug-vs.xyz>2023-09-03 04:15:40 +0300
committereug-vs <eugene@eug-vs.xyz>2023-09-03 04:24:00 +0300
commit395c2066ece606e66a08b7bb69a6ea0a659462c5 (patch)
tree9c64851c3ac1d462670a0d51339340c89ec113c6
parent08060989f1e3b2669e5969b12aaa35e56d0ff214 (diff)
downloadchessnost-395c2066ece606e66a08b7bb69a6ea0a659462c5.tar.gz
feat: apply Mate Distance Pruning
-rw-r--r--benches/search.rs4
-rw-r--r--src/grossmeister/search.rs63
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
}
}