aboutsummaryrefslogtreecommitdiff
path: root/src/grossmeister/search.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/grossmeister/search.rs')
-rw-r--r--src/grossmeister/search.rs309
1 files changed, 250 insertions, 59 deletions
diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs
index 372fecc..e8cb696 100644
--- a/src/grossmeister/search.rs
+++ b/src/grossmeister/search.rs
@@ -1,8 +1,15 @@
use std::f32::INFINITY;
-use crate::{moves::{Move, MoveKind}, board::io::IO};
+use crate::{
+ board::io::IO,
+ moves::{Move, MoveKind},
+};
-use super::{Grossmeister, ttable::{NodeType, TranspositionTableItem}, evaluation::Score};
+use super::{
+ evaluation::Score,
+ ttable::{NodeType, TranspositionTableItem},
+ Grossmeister,
+};
const SCORE_MATE: Score = 20_000.0;
@@ -19,38 +26,46 @@ impl Grossmeister {
// Mate distance pruning
// If a non-zero value (mating score) is returned, branch could be safely pruned
pub fn MDP(alpha: &mut Score, beta: &mut Score, root_distance: u8) -> Score {
- { // Update bound in case we are winning
+ {
+ // Update bound in case we are winning
let mating_score = SCORE_MATE - root_distance as Score;
if mating_score < *beta {
*beta = mating_score;
if *alpha >= mating_score {
- return mating_score
+ return mating_score;
}
}
}
- { // Update bound in case we are losing
+ {
+ // Update bound in case we are losing
let mating_score = -SCORE_MATE + root_distance as Score;
if mating_score > *alpha {
*alpha = mating_score;
if *beta <= mating_score {
- return mating_score
+ return mating_score;
}
}
}
0.0
}
- pub fn negamax_search(&mut self, mut alpha: Score, mut beta: Score, depth_left: u8, root_distance: u8) -> Score {
+ 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
+ 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
+ return mating_score;
}
if let Some(transposition) = self.transposition() {
@@ -84,7 +99,7 @@ impl Grossmeister {
};
if depth_left == 0 {
- return self.quiscence(alpha, beta, root_distance)
+ return self.quiscence(alpha, beta, root_distance);
}
let mut full_window_search = true;
@@ -106,7 +121,12 @@ impl Grossmeister {
} else {
// After we have PV-node (that raised alpha) all other nodes will be searched
// with zero-window first to confirm this assumption
- let score = -self.negamax_search(-(alpha + 0.01), -alpha, depth_left - 1, root_distance + 1);
+ let score = -self.negamax_search(
+ -(alpha + 0.01),
+ -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 score > alpha {
@@ -115,7 +135,13 @@ impl Grossmeister {
score
}
};
- self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
+ self.board.unmake_move(
+ mov,
+ captured_piece,
+ ep_target_before,
+ castling_rights_before,
+ hash_before,
+ );
if score >= beta {
transposition.mov = Some(mov);
@@ -127,7 +153,7 @@ impl Grossmeister {
self.register_killer(mov);
}
- return beta
+ return beta;
}
if score > alpha {
alpha = score;
@@ -137,7 +163,13 @@ impl Grossmeister {
transposition.node_type = NodeType::PV;
}
} else {
- self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
+ 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
@@ -148,11 +180,11 @@ impl Grossmeister {
if !legal_move_found {
if self.board.is_king_in_check(color) {
- return -SCORE_MATE + root_distance as Score
+ return -SCORE_MATE + root_distance as Score;
} else {
transposition.score = 0.0;
self.store_transposition(transposition);
- return 0.0
+ return 0.0;
}
}
@@ -164,13 +196,13 @@ impl Grossmeister {
let color = self.board.color();
if self.board.threefold_repetition() {
- return 0.0
+ 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
+ return mating_score;
}
if let Some(transposition) = self.transposition() {
@@ -219,7 +251,11 @@ impl Grossmeister {
let mut legal_move_found = false;
self.cleanup_selector();
- while let Some(mov) = if tactical_only { self.next_tactical() } else { self.next_move() } {
+ while let Some(mov) = if tactical_only {
+ self.next_tactical()
+ } 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;
@@ -228,7 +264,13 @@ impl Grossmeister {
if !self.board.is_king_in_check(color) {
legal_move_found = true;
let evaluation = -self.quiscence(-beta, -alpha, root_distance + 1);
- self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
+ self.board.unmake_move(
+ mov,
+ captured_piece,
+ ep_target_before,
+ castling_rights_before,
+ hash_before,
+ );
if evaluation >= beta {
transposition.mov = Some(mov);
@@ -249,12 +291,18 @@ impl Grossmeister {
transposition.node_type = NodeType::All;
}
} else {
- self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
+ self.board.unmake_move(
+ mov,
+ captured_piece,
+ ep_target_before,
+ castling_rights_before,
+ hash_before,
+ );
}
}
if !legal_move_found && self.board.is_king_in_check(color) {
- return -SCORE_MATE + root_distance as Score
+ return -SCORE_MATE + root_distance as Score;
}
self.store_transposition(transposition);
@@ -282,8 +330,13 @@ impl Grossmeister {
let mut subtree_pv = self.collect_pv(depth - 1);
pv.append(&mut subtree_pv);
- self.board.unmake_move(mov, captured, ep_target_before, castling_rights_before, hash_before);
-
+ self.board.unmake_move(
+ mov,
+ captured,
+ ep_target_before,
+ castling_rights_before,
+ hash_before,
+ );
}
} else {
println!("No PV node found for hash {}", self.board.hash);
@@ -304,11 +357,12 @@ impl Grossmeister {
let mut upperbound = INFINITY;
while lowerbound < upperbound {
- let beta = score + if score == lowerbound {
- window_size
- } else {
- 0.0
- };
+ let beta = score
+ + if score == lowerbound {
+ window_size
+ } else {
+ 0.0
+ };
score = self.negamax_search(beta - window_size, beta, depth, 0);
@@ -340,12 +394,14 @@ impl Grossmeister {
// Print UCI info
print!("info depth {} score ", depth);
- 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
- };
+ 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} ", score * 100.0)
@@ -430,35 +486,92 @@ impl Grossmeister {
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);
+ 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);
+ println!(
+ "Found {} leaf nodes in this subtree (depth {})",
+ result.leaf_nodes, depth
+ );
}
result
}
}
-
#[cfg(test)]
mod tests {
- use crate::{board::{Board, io::IO}, square::Square, moves::{Move, MoveKind}, grossmeister::{Grossmeister, search::PerftResult}};
use super::SCORE_MATE;
+ use crate::{
+ board::{io::IO, Board},
+ grossmeister::{search::PerftResult, Grossmeister},
+ moves::{Move, MoveKind},
+ square::Square,
+ };
#[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!(
+ 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 });
}
@@ -468,10 +581,46 @@ mod tests {
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!(
+ 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 });
}
@@ -481,8 +630,26 @@ mod tests {
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!(
+ 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 });
}
@@ -494,11 +661,26 @@ mod tests {
let (score, pv) = gm.iterative_deepening(8);
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 },
- Move { source: Square::D3, target: Square::A6, kind: MoveKind::Quiet },
- ]);
+ 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]
@@ -510,21 +692,30 @@ mod tests {
let (_, pv) = gm.iterative_deepening(6);
assert_eq!(
pv[0],
- Move { source: Square::F5, target: Square::H4, kind: MoveKind::Quiet },
+ 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 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);
assert_eq!(
pv[0],
- Move { source: Square::C2, target: Square::C3, kind: MoveKind::Quiet },
+ Move {
+ source: Square::C2,
+ target: Square::C3,
+ kind: MoveKind::Quiet
+ },
"You should fork this bastard!"
);
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-23 04:15:41 +0000