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.rs1100
1 files changed, 0 insertions, 1100 deletions
diff --git a/src/board/engine.rs b/src/board/engine.rs
deleted file mode 100644
index 2dc93eb..0000000
--- a/src/board/engine.rs
+++ /dev/null
@@ -1,1100 +0,0 @@
-use std::{time::{Instant, Duration}, f32::INFINITY, cmp::Ordering};
-use crate::board::*;
-
-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,
- captures: u64,
- en_passants: u64,
- castles: u64,
- checks: u64,
-}
-
-const PAWN_BONUS: [f32; 64] = [
- // A B C D E F G H
- 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00,
- 0.50, 0.50, 0.50, 0.50, 0.50, 0.50, 0.50, 0.50,
- 0.10, 0.10, 0.20, 0.30, 0.30, 0.20, 0.10, 0.10,
- 0.05, 0.05, 0.10, 0.25, 0.25, 0.10, 0.05, 0.05,
- 0.00, 0.00, 0.00, 0.20, 0.20, 0.00, 0.00, 0.00,
- 0.05, -0.05, -0.10, 0.00, 0.00, -0.10, -0.05, 0.05,
- 0.05, 0.10, 0.10, -0.20, -0.20, 0.10, 0.10, 0.05,
- 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00
-];
-
-const KNIGHT_BONUS: [f32; 64] = [
- // A B C D E F G H
- -0.50, -0.40, -0.30, -0.30, -0.30, -0.30, -0.40, -0.50,
- -0.40, -0.20, 0.00, 0.00, 0.00, 0.00, -0.20, -0.40,
- -0.30, 0.00, 0.10, 0.15, 0.15, 0.10, 0.00, -0.30,
- -0.30, 0.05, 0.15, 0.20, 0.20, 0.15, 0.05, -0.30,
- -0.30, 0.00, 0.15, 0.20, 0.20, 0.15, 0.00, -0.30,
- -0.30, 0.05, 0.10, 0.15, 0.15, 0.10, 0.05, -0.30,
- -0.40, -0.20, 0.00, 0.05, 0.05, 0.00, -0.20, -0.40,
- -0.50, -0.40, -0.30, -0.30, -0.30, -0.30, -0.40, -0.50,
-];
-
-const BISHOP_BONUS: [f32; 64] = [
- // A B C D E F G H
- -0.20, -0.10, -0.10, -0.10, -0.10, -0.10, -0.10, -0.20,
- -0.10, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.10,
- -0.10, 0.00, 0.05, 0.10, 0.10, 0.05, 0.00, -0.10,
- -0.10, 0.05, 0.05, 0.10, 0.10, 0.05, 0.05, -0.10,
- -0.10, 0.00, 0.10, 0.10, 0.10, 0.10, 0.00, -0.10,
- -0.10, 0.10, 0.10, 0.10, 0.10, 0.10, 0.10, -0.10,
- -0.10, 0.25, 0.00, 0.00, 0.00, 0.00, 0.25, -0.10,
- -0.20, -0.10, -0.10, -0.10, -0.10, -0.10, -0.10, -0.20,
-];
-
-const ROOK_BONUS: [f32; 64] = [
- // A B C D E F G H
- 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00,
- 0.05, 0.30, 0.30, 0.30, 0.30, 0.30, 0.30, 0.05,
- -0.05, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.05,
- -0.05, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.05,
- -0.05, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.05,
- -0.05, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.05,
- -0.05, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.05,
- 0.00, 0.00, 0.00, 0.05, 0.05, 0.00, 0.00, 0.00
-];
-
-const QUEEN_BONUS: [f32; 64] = [
- // A B C D E F G H
- -0.20, -0.10, -0.10, -0.05, -0.05, -0.10, -0.10, -0.20,
- -0.10, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, -0.10,
- -0.10, 0.00, 0.05, 0.05, 0.05, 0.05, 0.00, -0.10,
- -0.05, 0.00, 0.05, 0.05, 0.05, 0.05, 0.00, -0.05,
- 0.00, 0.00, 0.05, 0.05, 0.05, 0.05, 0.00, -0.05,
- -0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.00, -0.10,
- -0.10, 0.00, 0.05, 0.00, 0.00, 0.00, 0.00, -0.10,
- -0.20, -0.10, -0.10, -0.05, -0.05, -0.10, -0.10, -0.20
-];
-
-const KING_BONUS: [f32; 64] = [
- // A B C D E F G H
- -0.30, -0.40, -0.40, -0.50, -0.50, -0.40, -0.40, -0.30,
- -0.30, -0.40, -0.40, -0.50, -0.50, -0.40, -0.40, -0.30,
- -0.30, -0.40, -0.40, -0.50, -0.50, -0.40, -0.40, -0.30,
- -0.30, -0.40, -0.40, -0.50, -0.50, -0.40, -0.40, -0.30,
- -0.20, -0.30, -0.30, -0.40, -0.40, -0.30, -0.30, -0.20,
- -0.10, -0.20, -0.20, -0.20, -0.20, -0.20, -0.20, -0.10,
- 0.20, 0.20, 0.00, -0.10, -0.10, 0.00, 0.20, 0.20,
- 0.20, 0.10, 0.30, -0.20, 0.00, 0.10, 0.30, 0.20
-];
-
-
-impl Board {
- 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.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.ep_target.clone();
- let castling_rights_before = self.castling_rights.clone();
- let hash_before = self.hash.clone();
- let captured_piece = self.make_move(mov);
- // King can not be in check after our own move
- if !self.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.is_king_in_check(color.flip()) {
- result.checks += 1;
- }
- }
-
- if print {
- println!("{:?}", mov);
- self.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.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
- }
-
- fn ep_bitboard(&self) -> Bitboard {
- let color = self.color();
- match self.ep_target {
- Some(square) => {
- let rank = square.rank();
- if (rank == 2 && color == Color::Black) || (rank == 5 && color == Color::White) {
- square.to_bitboard()
- } else {
- 0
- }
- }
- None => 0,
- }
- }
-
- pub fn generate_pseudolegal_moves(&self) -> Vec<Move> {
- let mut result = Vec::new();
- result.append(&mut self.generate_moves_core(true));
- result.append(&mut self.generate_moves_core(false));
- result
- }
-
- pub fn generate_moves_core(&self, tactical_only: bool) -> Vec<Move> {
- let color = self.color();
- let player_pieces = self.pieces_by_color(color);
- let mut moves = Vec::with_capacity(256);
- let empty = self.empty();
-
- let targets = if tactical_only {
- self.color_occupancy(color.flip()) ^ match color {
- // Exclude opponent king because we can't capture it
- Color::White => self.piece_sets[Piece::KingBlack as usize],
- Color::Black => self.piece_sets[Piece::King as usize],
- }
- } else {
- empty
- };
-
- let kind = if tactical_only {
- MoveKind::Capture
- } else {
- MoveKind::Quiet
- };
-
- for (piece_id, piece) in player_pieces.iter().enumerate() {
- for source in piece.serialize() {
- let piece_type = Piece::from(piece_id);
- let move_targets = match piece_type {
- Piece::Bishop => self.attacks.bishop(self.occupancy, source),
- Piece::Rook => self.attacks.rook(self.occupancy, source),
- Piece::Queen => self.attacks.queen(self.occupancy, source),
- Piece::Knight => self.attacks.knight[source as usize],
- Piece::King => self.attacks.king[source as usize],
- Piece::Pawn => if tactical_only {
- self.attacks.pawn[color as usize][source as usize]
- } else {
- self.attacks.pawn_pushes[color as usize][source as usize]
- },
- _ => panic!("Incorrect piece type"),
- };
-
- // Generalized attack/move pattern for all pieces
- for target in (move_targets & targets).serialize() {
- moves.push(Move { source, target, kind });
-
- // Promotions
- if piece_type == Piece::Pawn {
- if target.rank() == 7 {
- for promo_type in [Piece::Bishop, Piece::Knight, Piece::Rook, Piece::Queen] {
- moves.push(Move { source, target, kind: MoveKind::Promotion(promo_type)})
- }
- } else if target.rank() == 0 {
- for promo_type in [Piece::BishopBlack, Piece::KnightBlack, Piece::RookBlack, Piece::QueenBlack] {
- moves.push(Move { source, target, kind: MoveKind::Promotion(promo_type)})
- }
- }
- }
- }
-
- // En Passant
- if piece_type == Piece::Pawn && tactical_only {
- for target in (move_targets & self.ep_bitboard()).serialize() {
- moves.push(Move { source, target, kind: MoveKind::EnPassant });
- }
- }
- }
- }
-
- if !tactical_only {
- // Double Pushes
- // Make sure no blocking piece is standing in front of the pawns
- // that are potential double-push sources
- let able_to_double_push_mask = match color {
- Color::White => empty >> 8,
- Color::Black => empty << 8,
- };
- for source in (player_pieces[Piece::Pawn as usize] & able_to_double_push_mask).serialize() {
- for target in (self.attacks.pawn_double_pushes[color as usize][source as usize] & empty).serialize() {
- moves.push(Move { source, target, kind: MoveKind::DoublePush });
- };
- }
-
- // Castling
- let king_home_position = match color {
- Color::White => Square::E1,
- Color::Black => Square::E8,
- };
- if player_pieces[Piece::King as usize].bitscan() == king_home_position {
- for rook_square in player_pieces[Piece::Rook as usize]
- .serialize()
- .iter()
- .filter(|rook_square| rook_square.rank() == king_home_position.rank())
- {
- match rook_square.file() {
- 0 => {
- let all_empty = [
- king_home_position.west_one(),
- king_home_position.west_one().west_one(),
- king_home_position.west_one().west_one().west_one(),
-
- ].iter().all(|square| empty & square.to_bitboard() > 0);
-
- let any_checks = [
- king_home_position,
- king_home_position.west_one(),
- king_home_position.west_one().west_one(),
- ].iter().any(|square| self.is_square_attacked(*square, color.flip()));
-
- if all_empty && !any_checks && self.castling_rights[color as usize][CastlingSide::Queen as usize] {
- moves.push(Move {
- source: king_home_position,
- target: king_home_position.west_one().west_one(),
- kind: MoveKind::Castle,
- })
- }
- },
- 7 => {
- let all_empty = [
- king_home_position.east_one(),
- king_home_position.east_one().east_one(),
-
- ].iter().all(|square| empty & square.to_bitboard() > 0);
-
- let any_checks = [
- king_home_position,
- king_home_position.east_one(),
- king_home_position.east_one().east_one(),
- ].iter().any(|square| self.is_square_attacked(*square, color.flip()));
-
- if all_empty && !any_checks && self.castling_rights[color as usize][CastlingSide::King as usize] {
- moves.push(Move {
- source: king_home_position,
- target: king_home_position.east_one().east_one(),
- kind: MoveKind::Castle,
- })
- }
- },
- _ => {},
- }
- }
- }
- }
- return moves
- }
-
- /// Count pseudo-legal moves without actually generating them
- /// Also exclude all moves that put a piece under attack of a pawn - so called safe mobility
- pub fn mobility(&self, color: Color) -> f32 {
- let mut mobility = 0.;
- let opponent_occupancy = self.color_occupancy(color.flip());
- let player_pieces = self.pieces_by_color(color);
-
- let opponent_pawns = match color {
- Color::Black => self.piece_sets[Piece::Pawn as usize],
- Color::White => self.piece_sets[Piece::PawnBlack as usize],
- };
-
- let pawn_attacked_squares = opponent_pawns.serialize().iter().fold(0u64, |acc, square| {
- acc | self.attacks.pawn[color.flip() as usize][*square as usize]
- });
-
- // Exclude squares controlled by enemy pawns from mobility
- let empty = self.empty() & !pawn_attacked_squares;
-
- for (piece_type, piece) in player_pieces.iter().enumerate() {
- match Piece::from(piece_type) {
- Piece::Pawn => {
- for source in piece.serialize() {
- let ep_bitboard = match self.ep_target {
- Some(square) => {
- let rank = square.rank();
- if (rank == 2 && color == Color::Black) || (rank == 5 && color == Color::White) {
- square.to_bitboard()
- } else {
- 0
- }
- }
- None => 0,
- };
- mobility += (self.attacks.pawn[color as usize][source as usize] & (opponent_occupancy | ep_bitboard)).pop_count() as f32;
- mobility += (self.attacks.pawn_pushes[color as usize][source as usize] & empty).pop_count() as f32;
- }
- let able_to_double_push_mask = match color {
- Color::White => empty >> 8,
- Color::Black => empty << 8,
- };
- for source in (*piece & able_to_double_push_mask).serialize() {
- mobility += (self.attacks.pawn_double_pushes[color as usize][source as usize] & empty).pop_count() as f32;
- }
- }
- Piece::King => {
- for source in piece.serialize() {
- mobility += (self.attacks.king[source as usize] & (empty | opponent_occupancy)).pop_count() as f32;
-
- // Castling
- let king_home_position = match color {
- Color::White => Square::E1,
- Color::Black => Square::E8,
- };
- if *piece == king_home_position.to_bitboard() {
- for rook_square in player_pieces[Piece::Rook as usize]
- .serialize()
- .iter()
- .filter(|rook_square| rook_square.rank() == king_home_position.rank())
- {
- match rook_square.file() {
- 0 => {
- let castle_line = [
- king_home_position.west_one(),
- king_home_position.west_one().west_one(),
- ];
-
- let all_empty = castle_line.iter().all(|square| empty & square.to_bitboard() > 0);
- let any_checks = castle_line.iter().any(|square| self.is_square_attacked(*square, color.flip()));
-
- if all_empty && !any_checks && self.castling_rights[color as usize][CastlingSide::Queen as usize] {
- mobility += 1.;
- }
- },
- 7 => {
- let castle_line = [
- king_home_position.east_one(),
- king_home_position.east_one().east_one(),
- ];
-
- let all_empty = castle_line.iter().all(|square| empty & square.to_bitboard() > 0);
- let any_checks = castle_line.iter().any(|square| self.is_square_attacked(*square, color.flip()));
-
- if all_empty && !any_checks && self.castling_rights[color as usize][CastlingSide::King as usize] {
- mobility += 1.;
- }
- },
- _ => {},
- }
- }
- }
- }
- }
- Piece::Knight => {
- for source in piece.serialize() {
- mobility += (self.attacks.knight[source as usize] & (empty | opponent_occupancy)).pop_count() as f32;
- }
- }
- Piece::Bishop => {
- for source in piece.serialize() {
- mobility += (self.attacks.bishop(self.occupancy, source) & (empty | opponent_occupancy)).pop_count() as f32;
- }
- }
- Piece::Rook => {
- for source in piece.serialize() {
- mobility += (self.attacks.rook(self.occupancy, source) & (empty | opponent_occupancy)).pop_count() as f32;
- }
- }
- Piece::Queen => {
- // Do not account queen in mobility
- }
- incorrect_type => panic!("Incorrect piece type: {:?}", incorrect_type),
- }
- }
-
- mobility
- }
-
-
- /// Count player pieces' material, giving bonus for pieces standing well
- 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 = Piece::from(piece_index);
-
- let bonus_table = match piece_type {
- Piece::Pawn => PAWN_BONUS,
- Piece::Knight => KNIGHT_BONUS,
- Piece::Bishop => BISHOP_BONUS,
- Piece::Rook => ROOK_BONUS,
- Piece::King => KING_BONUS,
- Piece::Queen => QUEEN_BONUS,
- _ => panic!("Unreachable")
- };
-
- material += bitboard.serialize().iter().fold(0., |acc, square| {
- acc + piece_type.static_eval() + bonus_table[
- match color {
- Color::White => square.mirror() as usize,
- Color::Black => *square as usize,
- }
- ]
- });
- }
- material
- }
-
- /// Returns sum of the doubled, blocked and isolated pawns
- /// The greater result is, the worse is the pawn structure
- pub fn pawn_structure_penalty(&self, color: Color) -> f32 {
- let mut result = 0.0;
-
- let pawns = match color {
- Color::White => self.piece_sets[Piece::Pawn as usize],
- Color::Black => self.piece_sets[Piece::PawnBlack as usize],
- };
-
- for file in 0..8 {
- let file_mask = A_FILE << file;
- let pawns_on_file = (pawns & file_mask).pop_count() as f32;
-
- // Doubled pawns (-1 because one pawn on a file is ok)
- result += (pawns_on_file - 1.).max(0.0);
-
- // Isolated pawns (no pawns on neighbor files)
- if [
- A_FILE << (file - 1).max(0), // File to the left (if any)
- A_FILE << (file + 1).min(7), // File to the right (if any)
- ].iter().all(|file| file & pawns == 0) {
- result += pawns_on_file;
- }
- }
-
- // Blocked pawns
- let blocked_mask = match color {
- Color::White => self.occupancy >> 8,
- Color::Black => self.occupancy << 8,
- };
- result += (pawns & blocked_mask).pop_count() as f32;
-
- 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 = match color {
- Color::White => self.piece_sets[Piece::King as usize],
- Color::Black => self.piece_sets[Piece::KingBlack as usize],
- }.bitscan();
-
- for (piece_type, bitboard) in self.pieces_by_color(color.flip()).iter().enumerate() {
- if piece_type != Piece::King as usize && piece_type != Piece::Pawn as usize {
- for square in bitboard.serialize() {
- let distance =
- (king_square.rank() as f32 - square.rank() as f32).abs() +
- (king_square.file() as f32 - square.file() as f32).abs();
-
- result += distance / Piece::from(piece_type).static_eval();
- }
- }
- }
- result
- }
-
- /// Evaluate a position relative to the current player
- pub fn evaluate(&self) -> f32 {
- let color = self.color();
- let opponent_color = color.flip();
-
- let mobility_advantage = self.mobility(color) - self.mobility(opponent_color);
-
- let opponent_material = self.material(opponent_color);
- let material_advantage = self.material(color) - opponent_material;
-
- let pawn_structure_penalty = self.pawn_structure_penalty(color) - self.pawn_structure_penalty(opponent_color);
-
- let king_tropism_penalty = self.king_tropism(color) - self.king_tropism(opponent_color);
-
- material_advantage
- + 0.15 * mobility_advantage
- - 0.3 * pawn_structure_penalty
- + king_tropism_penalty * (opponent_material / 40.0) * 0.07
- }
-
- /// Evaluate move for move ordering, prioritizing efficient captures
- /// where low-value pieces capture high-value pieces
- fn eval_move(&self, m: Move) -> f32 {
- if m.is_tactical() {
- let [source_eval, target_eval] = [m.source, m.target]
- .map(|sq| self.piece_by_square(sq))
- .map(|p| {
- match p {
- Some(p) => p.static_eval(),
- None => 0.,
- }
- });
- return 2. * target_eval - source_eval
- }
- 0.0
- }
-
- /// Find current transposition in Transposition Table
- pub fn transposition(&self) -> Option<TranspositionTableItem> {
- match self.transposition_table[(self.hash % TTABLE_SIZE) as usize] {
- Some(item) => {
- if item.hash == self.hash {
- return Some(item)
- }
- None
- }
- None => None
- }
- }
-
- pub fn order_moves(&self, moves: Vec<Move>, killer_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
- }
- if b.is_tactical() && !a.is_tactical() {
- return Ordering::Greater
- }
- }
- a_eval.total_cmp(b_eval).reverse()
- });
-
- let mut ordered_moves: Vec<Move> = moves_with_eval.iter().map(|(m, _)| *m).collect();
-
- // Insert killer moves after winning captures
- let equal_capture_index = match moves_with_eval.iter().position(|(m, eval)| m.is_tactical() && *eval == 0.0) {
- Some(x) => x,
- None => 0,
- };
-
- for killer in killer_moves {
- match ordered_moves.iter().position(|m| *m == killer) {
- Some(index) => {
- let mov = ordered_moves.remove(index);
- ordered_moves.insert(equal_capture_index, mov);
- }
- None => {}
- };
-
- }
-
- match self.transposition() {
- Some(transposition) => ordered_moves.insert(0, transposition.mov),
- None => {},
- }
-
- ordered_moves
- }
-
- 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.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.ep_target.clone();
- let castling_rights_before = self.castling_rights.clone();
- let hash_before = self.hash.clone();
- let captured_piece = self.make_move(mov);
-
- if !self.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.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
-
- if score >= beta {
- self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
- hash: self.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.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
- hash: self.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.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
- hash: self.hash,
- mov,
- depth: depth_left, // TODO: should be actual depth searched
- node_type: NodeType::All,
- score,
- });
- }
- } else {
- self.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.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();
- moves = self.order_moves(moves, Vec::new());
-
- if !self.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.ep_target.clone();
- let castling_rights_before = self.castling_rights.clone();
- let hash_before = self.hash.clone();
- let captured_piece = self.make_move(mov);
-
- if !self.is_king_in_check(color) {
- legal_move_found = true;
- let evaluation = -self.quiscence(-beta, -alpha);
- self.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.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
- }
- }
-
- if !legal_move_found {
- if self.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"),
- }
- }
-}
-
-
-#[cfg(test)]
-mod tests {
- use std::time::Duration;
- use crate::{board::{Board, engine::{PerftResult, KING_BONUS}, Color, io::IO}, square::Square, moves::{Move, MoveKind}};
- use super::VALUE_WIN;
-
- #[test]
- fn perft() {
- let mut board = Board::new();
-
- assert_eq!(board.perft(0, false), PerftResult { leaf_nodes: 1, captures: 0, en_passants: 0, castles: 0 , checks: 0 });
- assert_eq!(board.perft(1, false), PerftResult { leaf_nodes: 20, captures: 0, en_passants: 0, castles: 0 , checks: 0 });
- assert_eq!(board.perft(2, false), PerftResult { leaf_nodes: 400, captures: 0, en_passants: 0, castles: 0 , checks: 0 });
- assert_eq!(board.perft(3, false), PerftResult { leaf_nodes: 8902, captures: 34, en_passants: 0, castles: 0 , checks: 12 });
- assert_eq!(board.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 mut board = Board::from_FEN(fen);
- assert_eq!(board.perft(0, false), PerftResult { leaf_nodes: 1, captures: 0, en_passants: 0, castles: 0 , checks: 0 });
- assert_eq!(board.perft(1, false), PerftResult { leaf_nodes: 48, captures: 8, en_passants: 0, castles: 2 , checks: 0 });
- assert_eq!(board.perft(2, false), PerftResult { leaf_nodes: 2039, captures: 351, en_passants: 1, castles: 91 , checks: 3 });
- assert_eq!(board.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 mut board = Board::from_FEN(fen);
-
- assert_eq!(board.perft(1, false), PerftResult { leaf_nodes: 14, captures: 1, en_passants: 0, castles: 0 , checks: 2 });
- assert_eq!(board.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 material() {
- let board = Board::new();
- 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), 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 (_, pv) = board.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 mut board = Board::from_FEN(fen);
-
- let (_, pv) = board.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!"
- );
- }
-
- #[test]
- fn castle_bonus() {
- assert_eq!(KING_BONUS[Square::E1.mirror() as usize], 0.0);
- assert!(KING_BONUS[Square::G1.mirror() as usize] > 0.0);
- assert!(KING_BONUS[Square::C1.mirror() as usize] > 0.0);
- assert!(KING_BONUS[Square::D1.mirror() as usize] < 0.0);
- assert!(KING_BONUS[Square::E2.mirror() as usize] < 0.0);
-
- assert_eq!(KING_BONUS[Square::E8 as usize], 0.0);
- assert!(KING_BONUS[Square::G8 as usize] > 0.0);
- assert!(KING_BONUS[Square::C8 as usize] > 0.0);
- assert!(KING_BONUS[Square::D8 as usize] < 0.0);
- assert!(KING_BONUS[Square::E2 as usize] < 0.0);
- }
-
- mod evaluation {
- use crate::{moves::{Move, MoveKind}, square::Square, board::io::IO};
-
- use super::*;
-
- #[test]
- fn initial_eval() {
- let board = Board::new();
- assert_eq!(board.evaluate(), 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();
- 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();
- 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();
- 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();
- 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();
- 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();
- 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();
- 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();
- 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();
- 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 06:51:05 +0000