aboutsummaryrefslogtreecommitdiff
path: root/src/board/engine.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/board/engine.rs')
-rw-r--r--src/board/engine.rs346
1 files changed, 281 insertions, 65 deletions
diff --git a/src/board/engine.rs b/src/board/engine.rs
index 8852c1f..6a0db61 100644
--- a/src/board/engine.rs
+++ b/src/board/engine.rs
@@ -5,6 +5,8 @@ use super::ttable::{NodeType, TranspositionTableItem};
static A_FILE: Bitboard = 0x0101010101010101;
+const VALUE_WIN: f32 = 20_000.0;
+
#[derive(Debug, Default, PartialEq)]
pub struct PerftResult {
leaf_nodes: u64,
@@ -81,41 +83,39 @@ impl Board {
}
/// Compute material advantage relative to the current player
- pub fn material_advantage(&self) -> f32 {
- let mut eval = 0f32;
- for (piece_index, bitboard) in self.pieces.iter().enumerate() {
+ pub fn material(&self, color: Color) -> f32 {
+ let mut material = 0f32;
+ for (piece_index, bitboard) in self.pieces_by_color(color).iter().enumerate() {
let piece_type = PieceType::from(piece_index);
- let sign = if Color::from_piece(piece_type) == self.color() {
- 1.
- } else {
- -1.
- };
-
- eval += sign * match piece_type {
+ material += match piece_type {
PieceType::Pawn => {
- serialize_bitboard(*bitboard).iter().fold(0., |acc, square| {
- acc + match (*square).rank() {
- 6 => 3.,
- 5 => 2.,
- _ => 1.,
+ match color {
+ Color::White => {
+ serialize_bitboard(*bitboard).iter().fold(0., |acc, square| {
+ acc + match (*square).rank() {
+ 6 => 3.,
+ 5 => 2.,
+ _ => 1.,
+ }
+ })
+ },
+ Color::Black => {
+ serialize_bitboard(*bitboard).iter().fold(0., |acc, square| {
+ acc + match (*square).rank() {
+ 1 => 3.,
+ 2 => 2.,
+ _ => 1.,
+ }
+ })
}
- })
- }
- PieceType::PawnBlack => {
- serialize_bitboard(*bitboard).iter().fold(0., |acc, square| {
- acc + match (*square).rank() {
- 1 => 3.,
- 2 => 2.,
- _ => 1.,
- }
- })
+ }
}
_ => {
piece_type.static_eval() * pop_count(*bitboard) as f32
}
};
}
- eval
+ material
}
/// Returns sum of the doubled, blocked and isolated pawns
@@ -154,20 +154,50 @@ impl Board {
result
}
+ /// Returns the weighted sum of distances from attacking pieces to a king
+ /// The higher this value, the safer is the king
+ pub fn king_tropism(&self, color: Color) -> f32 {
+ let mut result = 0.0;
+
+ let king_square = bitscan(match color {
+ Color::White => self.pieces[PieceType::King as usize],
+ Color::Black => self.pieces[PieceType::KingBlack as usize],
+ });
+
+ for (piece_type, bitboard) in self.pieces_by_color(color.flip()).iter().enumerate() {
+ if piece_type != PieceType::King as usize && piece_type != PieceType::Pawn as usize {
+ for square in serialize_bitboard(*bitboard) {
+ let distance =
+ (king_square.rank() as f32 - square.rank() as f32).abs() +
+ (king_square.file() as f32 - square.file() as f32).abs();
+
+ result += distance / PieceType::from(piece_type).static_eval();
+ }
+ }
+ }
+ result
+ }
+
/// Evaluate a position relative to the current player
pub fn evaluate(&self, precomputed_mobility: Option<f32>) -> f32 {
- let opponent_mobility = self.mobility(self.color().flip());
+ let color = self.color();
+ let opponent_color = color.flip();
+
+ let opponent_mobility = self.mobility(opponent_color);
let player_mobility = match precomputed_mobility {
Some(m) => m,
- None => self.mobility(self.color()),
+ None => self.mobility(color),
};
let mobility_advantage = player_mobility - opponent_mobility as f32;
- let material_advantage = self.material_advantage();
+ let opponent_material = self.material(opponent_color);
+ let material_advantage = self.material(color) - opponent_material;
- let pawn_structure_penalty = self.pawn_structure_penalty(self.color()) - self.pawn_structure_penalty(self.color().flip());
+ let pawn_structure_penalty = self.pawn_structure_penalty(color) - self.pawn_structure_penalty(opponent_color);
- material_advantage + 0.1 * mobility_advantage - 0.5 * pawn_structure_penalty
+ let king_tropism_penalty = self.king_tropism(color) - self.king_tropism(opponent_color);
+
+ material_advantage + 0.1 * mobility_advantage - 0.4 * pawn_structure_penalty + king_tropism_penalty * opponent_material / 150.0
}
/// Evaluate move for move ordering, prioritizing efficient captures
@@ -187,11 +217,26 @@ impl Board {
0.0
}
- pub fn order_moves(&self, moves: &mut Vec<Move>) {
- moves.sort_unstable_by(|a, b| {
- let a_eval = self.eval_move(*a);
- let b_eval = self.eval_move(*b);
- if a_eval == 0.0 && b_eval == 0.0 {
+ pub fn hash_move(&self) -> Option<Move> {
+ match self.transposition_table[(self.hash % TTABLE_SIZE) as usize] {
+ Some(item) => {
+ if item.hash == self.hash {
+ return Some(item.best_move)
+ }
+ None
+ }
+ None => None
+ }
+ }
+
+ pub fn order_moves(&self, moves: Vec<Move>) -> Vec<Move> {
+ let mut moves_with_eval: Vec<(Move, f32)> = moves
+ .iter()
+ .map(|m| (*m, self.eval_move(*m)))
+ .collect();
+
+ moves_with_eval.sort_unstable_by(|(a, a_eval), (b, b_eval)| {
+ if *a_eval == 0.0 && *b_eval == 0.0 {
// Prioritize equal captures over non-captures
if a.is_tactical() && !b.is_tactical() {
return Ordering::Less
@@ -200,8 +245,10 @@ impl Board {
return Ordering::Greater
}
}
- a_eval.total_cmp(&b_eval).reverse()
+ a_eval.total_cmp(b_eval).reverse()
});
+
+ moves_with_eval.iter_mut().map(|(m, _)| *m).collect()
}
pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8, parent_killers: &mut Vec<Move>, deadline: Instant) -> (f32, Vec<Move>) {
@@ -210,7 +257,12 @@ impl Board {
let color = self.color();
let mut moves = self.generate_pseudolegal_moves(color);
- self.order_moves(&mut moves);
+ moves = self.order_moves(moves);
+
+ match self.hash_move() {
+ Some(mov) => moves.insert(0, mov),
+ None => {},
+ }
let loosing_capture_index = match moves.iter().position(|m| {
m.is_tactical() && self.eval_move(*m) < 0.0
@@ -219,7 +271,7 @@ impl Board {
None => 0,
};
- // Insert killer moves after winning and equal captures
+ // Insert killer moves (from previous siblings) after winning and equal captures
for mov in &mut *parent_killers {
// Validate that killer piece still exists
if mov.source.to_bitboard() & self.color_occupancy(color) > 0 {
@@ -227,19 +279,11 @@ impl Board {
}
}
- match self.transposition_table[(self.hash % TTABLE_SIZE) as usize] {
- Some(item) => {
- if item.hash == self.hash {
- moves.insert(0, item.best_move);
- }
- }
- None => {},
- }
-
if depth_left == 0 {
return (self.quiscence(alpha, beta), principal_variation);
}
+ let mut legal_move_found = false;
for mov in moves {
let ep_target_before = self.ep_target.clone();
let castling_rights_before = self.castling_rights.clone();
@@ -247,6 +291,7 @@ impl Board {
let captured_piece = self.make_move(mov);
if !self.is_king_in_check(color) {
+ legal_move_found = true;
let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1, &mut killer_moves, deadline);
score *= -1.;
self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
@@ -261,8 +306,6 @@ impl Board {
});
if mov.kind == MoveKind::Quiet {
- // println!("Killer {:?} found at depth {}", mov, depth_left);
- // self.print();
match parent_killers.iter().find(|m| **m == mov) {
None => parent_killers.push(mov),
Some(..) => {},
@@ -299,25 +342,26 @@ impl Board {
// Could not finish in time, return what we have so far
if Instant::now() > deadline {
- println!("Returning early!");
return (alpha, principal_variation)
}
}
+ if !legal_move_found {
+ if self.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.color();
let mut moves = self.generate_pseudolegal_moves(color);
- self.order_moves(&mut moves);
+ moves = self.order_moves(moves);
- match self.transposition_table[(self.hash % TTABLE_SIZE) as usize] {
- Some(item) => {
- if item.hash == self.hash {
- moves.insert(0, item.best_move);
- }
- }
+ match self.hash_move() {
+ Some(mov) => moves.insert(0, mov),
None => {},
}
@@ -363,30 +407,42 @@ impl Board {
let mut depth = 1;
let mut alpha = -INFINITY;
let mut beta = INFINITY;
+ let window_size = 0.5;
+ let mut gradual_widening_counter = 0;
let mut root_killers: Vec<Move> = Vec::new();
- let window_size = 0.25;
while depth <= max_depth {
+ println!("\nSearching depth({}) in the window {:?}", depth, (alpha, beta));
let search_result = self.negamax_search(alpha, beta, depth, &mut root_killers, deadline);
- println!("Finished depth({}) {:?} [{:?} left]", depth, search_result, deadline - Instant::now());
+
+ if search_result.0.abs() >= VALUE_WIN {
+ return search_result
+ }
if Instant::now() > deadline {
+ println!("Aborting...");
break;
}
+
+ println!("Finished depth({}) {:?} [{:?} left]", depth, search_result, deadline - Instant::now());
+
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 if search_result.0 <= alpha { // Alpha-cutoff
println!("Alpha cutoff {} <= {:?}", search_result.0, (alpha, beta));
+ gradual_widening_counter += 1;
beta = alpha;
- alpha = search_result.0 - window_size * 4.0;
+ alpha = search_result.0 - window_size * 2.0f32.powi(gradual_widening_counter);
continue;
} else if search_result.0 >= beta { // Beta-cutoff
println!("Beta cutoff {:?} <= {}", (alpha, beta), search_result.0);
+ gradual_widening_counter += 1;
alpha = beta;
- beta = search_result.0 + window_size * 4.0;
+ beta = search_result.0 + window_size * 2.0f32.powi(gradual_widening_counter);
continue;
} else {
panic!("Can this ever be possible? (probably not)");
@@ -405,7 +461,9 @@ impl Board {
#[cfg(test)]
mod tests {
- use crate::board::{Board, engine::PerftResult};
+ use std::time::Duration;
+ use crate::{board::{Board, engine::PerftResult, Color}, square::Square, moves::{Move, MoveKind}};
+ use super::VALUE_WIN;
#[test]
fn perft() {
@@ -441,9 +499,167 @@ mod tests {
}
#[test]
- fn material_advantage() {
+ fn material() {
let board = Board::new();
- assert_eq!(board.material_advantage(), 0.0, "Material advantage should be 0 at starting position");
+ assert_eq!(board.material(Color::Black), board.material(Color::White));
+
+ }
+
+ #[test]
+ fn checkmate() {
+ let fen = String::from("2kr1b1r/pp1npppp/2p1bn2/7q/5B2/2NB1Q1P/PPP1N1P1/2KR3R w - - 0 1");
+ let mut board = Board::from_FEN(fen);
+ let (score, pv) = board.iterative_deepening(8, Duration::from_secs(15));
+
+ 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 (_, pv) = board.iterative_deepening(6, Duration::from_secs(60));
+ 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 mut board = Board::from_FEN(fen);
+
+ let (_, pv) = board.iterative_deepening(5, Duration::from_secs(60));
+ assert_eq!(
+ pv[0],
+ Move { source: Square::C2, target: Square::C3, kind: MoveKind::Quiet },
+ "You should fork this bastard!"
+ );
}
+
+ mod evaluation {
+ use crate::{moves::{Move, MoveKind}, square::Square};
+
+ use super::*;
+
+ #[test]
+ fn initial_eval() {
+ let board = Board::new();
+ assert_eq!(board.evaluate(None), 0.0);
+ }
+
+ #[test]
+ fn king_tropism() {
+ let mut board = Board::new();
+ board.make_move(Move { source: Square::D1, target: Square::F5, kind: MoveKind::Quiet });
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+
+ assert!(score < 0.0);
+ assert!(score > -1.0);
+ }
+
+ #[test]
+ fn white_winning() {
+ let fen = String::from("8/5pk1/6p1/R4b1p/3P4/1P2N3/P1r2PPP/R5K1 b - - 1 27");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+
+ assert!(score > 7.0);
+ }
+
+ #[test]
+ fn black_winning() {
+ let fen = String::from("8/p7/1k4K1/8/4P3/8/PP5r/8 b - - 1 38");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+
+ assert!(score < -3.0);
+ }
+
+ #[test]
+ fn encourage_center_pawns() {
+ let score1 = {
+ let fen = String::from("rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 2");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ let score2 = {
+ let fen = String::from("rnbqkbnr/pppp1ppp/8/4p3/2P5/8/PP1PPPPP/RNBQKBNR w KQkq - 0 2");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ assert!(score1 > score2);
+ }
+
+ #[test]
+ fn discourage_edge_knights() {
+ let score1 = {
+ let fen = String::from("r1bqkbnr/pppp1ppp/2n5/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq - 2 3");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ let score2 = {
+ let fen = String::from("r1bqkbnr/pppp1ppp/2n5/4p3/4P3/7N/PPPP1PPP/RNBQKB1R w KQkq - 2 3");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ assert!(score1 > score2);
+ }
+
+ #[test]
+ fn mirrored_evaluation() {
+ let score1 = {
+ let fen = String::from("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1");
+ let board = Board::from_FEN(fen);
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ let score2 = {
+ let fen = String::from("r2q1rk1/pP1p2pp/Q4n2/bbp1p3/Np6/1B3NBn/pPPP1PPP/R3K2R b KQ - 0 1 ");
+ let mut board = Board::from_FEN(fen);
+ board.ply += 1; // TODO: remove me when FEN parsing includes side to move
+ let score = board.evaluate(None);
+ board.print();
+ println!("Score {}", score);
+ score
+ };
+
+ assert_eq!(score1.abs(), score2.abs());
+ }
+ }
+
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-23 20:47:47 +0000