diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/attacks.rs | 2 | ||||
| -rw-r--r-- | src/board/engine.rs | 1100 | ||||
| -rw-r--r-- | src/board/io.rs | 56 | ||||
| -rw-r--r-- | src/board/mod.rs | 83 | ||||
| -rw-r--r-- | src/grossmeister/evaluation.rs | 466 | ||||
| -rw-r--r-- | src/grossmeister/mod.rs | 35 | ||||
| -rw-r--r-- | src/grossmeister/move_generation.rs | 266 | ||||
| -rw-r--r-- | src/grossmeister/perft.rs | 0 | ||||
| -rw-r--r-- | src/grossmeister/search.rs | 426 | ||||
| -rw-r--r-- | src/grossmeister/ttable.rs (renamed from src/board/ttable.rs) | 19 | ||||
| -rw-r--r-- | src/lib.rs | 1 | ||||
| -rw-r--r-- | src/main.rs | 46 |
12 files changed, 1291 insertions, 1209 deletions
diff --git a/src/attacks.rs b/src/attacks.rs index 376e666..d0f2ddd 100644 --- a/src/attacks.rs +++ b/src/attacks.rs @@ -35,7 +35,7 @@ enum Direction { NoWe, } -#[derive(Debug, Clone, PartialEq, Eq)] +#[derive(Debug, Clone, Copy, PartialEq, Eq)] pub struct Attacks { pub knight: AttackTable, pub king: AttackTable, 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()); - } - } - -} diff --git a/src/board/io.rs b/src/board/io.rs index 30d487f..ca75c8c 100644 --- a/src/board/io.rs +++ b/src/board/io.rs @@ -1,8 +1,5 @@ -use std::io::{stdin, stdout, Write}; -use crate::{bitboard::Bitboard, attacks::Attacks, moves::Move, square::Square}; - - -use super::{Board, Piece, ttable::TTABLE_SIZE, zobrist::Zobrist}; +use crate::{bitboard::Bitboard, attacks::Attacks, moves::Move}; +use super::{Board, Piece, zobrist::Zobrist}; const PIECE_CHARS: [&str; 12] = [ "♟︎", "♞", "♝", "♜", "♛", "♚", @@ -45,6 +42,7 @@ impl IO for Board { println!(" a b c d e f g h"); } + #[allow(non_snake_case)] fn from_FEN(fen: String) -> Self { let mut piece_sets = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; @@ -99,7 +97,6 @@ impl IO for Board { castling_rights: [[true; 2]; 2], // TODO: actualy parse from FEN ep_target: None, // TODO: parse from FEN hash: 0, - transposition_table: vec![None; TTABLE_SIZE as usize], zobrist_seed: Board::seed(), }; board.update_occupancy(); @@ -113,29 +110,30 @@ impl IO for Board { } fn read_move(&self) -> Result<Move, String> { - print!("\nEnter a move: "); - stdout().flush().unwrap(); - let mut s = String::new(); - stdin().read_line(&mut s).unwrap(); - let chars = &mut s.chars(); - - let source = match Square::from_notation(chars) { - Ok(s) => s, - Err(e) => return Err(e), - }; - let target = match Square::from_notation(chars) { - Ok(s) => s, - Err(e) => return Err(e), - }; - - let moves = self.generate_pseudolegal_moves(); - - let mov = match moves.iter().find(|m| m.source == source && m.target == target) { - Some(m) => *m, - None => return Err(String::from("Move is not valid")), - }; - - Ok(mov) + todo!(); + // print!("\nEnter a move: "); + // stdout().flush().unwrap(); + // let mut s = String::new(); + // stdin().read_line(&mut s).unwrap(); + // let chars = &mut s.chars(); + // + // let source = match Square::from_notation(chars) { + // Ok(s) => s, + // Err(e) => return Err(e), + // }; + // let target = match Square::from_notation(chars) { + // Ok(s) => s, + // Err(e) => return Err(e), + // }; + // + // let moves = self.generate_pseudolegal_moves(); + + // let mov = match moves.iter().find(|m| m.source == source && m.target == target) { + // Some(m) => *m, + // None => return Err(String::from("Move is not valid")), + // }; + + // Ok(mov) } } diff --git a/src/board/mod.rs b/src/board/mod.rs index e6a6446..579488b 100644 --- a/src/board/mod.rs +++ b/src/board/mod.rs @@ -1,12 +1,10 @@ use crate::{bitboard::{Bitboard, BitboardFns}, moves::{Move, MoveKind}, attacks::Attacks, square::Square, board::io::IO}; -use self::{ttable::{TranspositionTable, TTABLE_SIZE}, zobrist::{ZobristSeed, Zobrist}, piece::Piece, color::Color}; +use self::{zobrist::{ZobristSeed, Zobrist}, piece::Piece, color::Color}; pub mod io; pub mod color; pub mod piece; mod zobrist; -mod engine; -mod ttable; #[derive(Debug, Clone, Copy)] pub enum CastlingSide { @@ -14,7 +12,9 @@ pub enum CastlingSide { Queen, } -#[derive(Debug, Clone, PartialEq)] +/// Chess board is an main interface to the internal game state. +/// Board defines rules of the game and manages players actions. +#[derive(Debug, Clone, Copy, PartialEq)] pub struct Board { pub ply: u16, pub piece_sets: [Bitboard; 12], @@ -27,10 +27,8 @@ pub struct Board { pub occupancy: Bitboard, /// Zobrist hash of the current position pub hash: u64, - - // TODO: remove - transposition_table: TranspositionTable, zobrist_seed: ZobristSeed, + attacks: Attacks, } @@ -49,22 +47,22 @@ impl Board { self.occupancy = self.piece_sets.iter().fold(0, |acc, bitboard| acc | bitboard) } - fn empty(&self) -> Bitboard { + pub fn empty(&self) -> Bitboard { !self.occupancy } - fn pieces_by_color(&self, color: Color) -> &[Bitboard] { + pub fn pieces_by_color(&self, color: Color) -> &[Bitboard] { match color { Color::White => &self.piece_sets[0..6], Color::Black => &self.piece_sets[6..12], } } - fn color_occupancy(&self, color: Color) -> Bitboard { + pub fn color_occupancy(&self, color: Color) -> Bitboard { self.pieces_by_color(color).iter().fold(0, |acc, bitboard| acc | bitboard) } - fn piece_by_square(&self, square: Square) -> Option<Piece> { + pub fn piece_by_square(&self, square: Square) -> Option<Piece> { let square_bb = square.to_bitboard(); self.piece_sets .iter() @@ -73,6 +71,21 @@ impl Board { .and_then(|(pt, _)| Some(Piece::from(pt))) } + pub 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, + } + } + /// *Blindlessly* apply a move without any validation /// Legality test should still be performed pub fn make_move(&mut self, mov: Move) -> Option<Piece> { @@ -302,7 +315,7 @@ impl Board { self.ply -= 1; } - fn is_square_attacked(&self, square: Square, attacker_color: Color) -> bool { + pub fn is_square_attacked(&self, square: Square, attacker_color: Color) -> bool { for (piece_type, piece) in self.pieces_by_color(attacker_color).iter().enumerate() { match Piece::from(piece_type) { Piece::Queen => { @@ -341,7 +354,7 @@ impl Board { false } - fn is_king_in_check(&self, color: Color) -> bool { + pub fn is_king_in_check(&self, color: Color) -> bool { let king_bb = match color { Color::White => self.piece_sets[Piece::King as usize], Color::Black => self.piece_sets[Piece::KingBlack as usize], @@ -365,31 +378,6 @@ mod tests { } #[test] - fn generate_pseudolegal_moves_starting_position() { - let mut board = Board::new(); - let moves = board.generate_pseudolegal_moves(); - board.ply += 1; - let black_moves = board.generate_pseudolegal_moves(); - - assert_eq!(moves.len(), 20); - assert_eq!(black_moves.len(), 20); - - for mov in moves { - mov.print(); - } - } - - #[test] - fn mobility() { - let board = Board::new(); - let white = board.mobility(Color::White); - let black = board.mobility(Color::Black); - - assert_eq!(white, 20.); - assert_eq!(black, 20.); - } - - #[test] fn make_move() { let fen = String::from("q1b2k2/5p1p/4p1pb/pPPp4/3N4/3nPB2/P2QKnR1/1R6 w - - 0 25"); let mut board = Board::from_FEN(fen); @@ -459,23 +447,4 @@ mod tests { assert_eq!(board.is_square_attacked(Square::E4, Color::White), false); assert_eq!(board.is_square_attacked(Square::B6, Color::Black), true); } - - #[test] - fn moved_king_castle() { - let fen = String::from("4k2r/ppp1n3/8/4R1Pp/5P2/q1P5/P1P1BP2/1K1R4 b - - 2 22"); - let mut board = Board::from_FEN(fen); - board.ply += 1; - - // Shuffle kings around, returning to the same position - board.make_move(Move { source: Square::E8, target: Square::F8, kind: MoveKind::Quiet }); - board.make_move(Move { source: Square::B1, target: Square::A1, kind: MoveKind::Quiet }); - board.make_move(Move { source: Square::F8, target: Square::E8, kind: MoveKind::Quiet }); - board.make_move(Move { source: Square::A1, target: Square::B1, kind: MoveKind::Quiet }); - - let moves = board.generate_pseudolegal_moves(); - - let castle = moves.iter().find(|m| **m == Move { source: Square::E8, target: Square::G8, kind: MoveKind::Castle }); - println!("{:?}", board.castling_rights); - assert!(castle.is_none(), "Castle should not be allowed after king has moved"); - } } diff --git a/src/grossmeister/evaluation.rs b/src/grossmeister/evaluation.rs new file mode 100644 index 0000000..201aaed --- /dev/null +++ b/src/grossmeister/evaluation.rs @@ -0,0 +1,466 @@ +use crate::{board::{piece::Piece, color::Color, CastlingSide}, bitboard::{BitboardFns, Bitboard}, square::Square}; + +use super::Grossmeister; + +static A_FILE: Bitboard = 0x0101010101010101; + +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 Grossmeister { + /// Evaluate a position relative to the current player + pub fn evaluate(&self) -> f32 { + let color = self.board.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 + } + + /// 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.board.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.board.piece_sets[Piece::Pawn as usize], + Color::Black => self.board.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.board.occupancy >> 8, + Color::Black => self.board.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.board.piece_sets[Piece::King as usize], + Color::Black => self.board.piece_sets[Piece::KingBlack as usize], + }.bitscan(); + + for (piece_type, bitboard) in self.board.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 + } + + /// 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.board.color_occupancy(color.flip()); + let player_pieces = self.board.pieces_by_color(color); + + let opponent_pawns = match color { + Color::Black => self.board.piece_sets[Piece::Pawn as usize], + Color::White => self.board.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.board.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.board.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.board.is_square_attacked(*square, color.flip())); + + if all_empty && !any_checks && self.board.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.board.is_square_attacked(*square, color.flip())); + + if all_empty && !any_checks && self.board.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.board.occupancy, source) & (empty | opponent_occupancy)).pop_count() as f32; + } + } + Piece::Rook => { + for source in piece.serialize() { + mobility += (self.attacks.rook(self.board.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 + } +} + +#[cfg(test)] +mod tests { + use crate::{board::{Board, io::IO}, moves::{Move, MoveKind}}; + + use super::*; + + #[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); + } + + #[test] + fn mobility() { + let board = Board::new(); + let gm = Grossmeister::new(board); + let white = gm.mobility(Color::White); + let black = gm.mobility(Color::Black); + + assert_eq!(white, 20.); + assert_eq!(black, 20.); + } + + #[test] + fn material() { + let board = Board::new(); + let gm = Grossmeister::new(board); + assert_eq!(gm.material(Color::Black), gm.material(Color::White)); + + } + + #[test] + fn initial_eval() { + let board = Board::new(); + let gm = Grossmeister::new(board); + assert_eq!(gm.evaluate(), 0.0); + } + + #[test] + fn king_tropism() { + let board = Board::new(); + let mut gm = Grossmeister::new(board); + gm.board.make_move(Move { source: Square::D1, target: Square::F5, kind: MoveKind::Quiet }); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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 gm = Grossmeister::new(board); + let score = gm.evaluate(); + gm.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); + let gm = Grossmeister::new(board); + board.ply += 1; // TODO: remove me when FEN parsing includes side to move + let score = gm.evaluate(); + gm.board.print(); + println!("Score {}", score); + score + }; + + assert_eq!(score1.abs(), score2.abs()); + } + +} diff --git a/src/grossmeister/mod.rs b/src/grossmeister/mod.rs new file mode 100644 index 0000000..b7c134d --- /dev/null +++ b/src/grossmeister/mod.rs @@ -0,0 +1,35 @@ +use crate::{board::Board, attacks::Attacks}; +use self::ttable::{TranspositionTable, TTABLE_SIZE}; + +mod ttable; +mod move_generation; +mod evaluation; +mod search; + +/// Grossmeister is a powerful entity that plays the game of Chess. +/// This structure represents a player, it stores his knowledge +/// and experience about the game. +pub struct Grossmeister { + pub board: Board, + + /// Array of pre-computed attack tables. + /// This structure allows Grossmeister to calculate attacks of the pieces + /// as fast as possible using his big brain. + attacks: Attacks, + + /// Transposition table is a cache of all positions that Grossmeister + /// has seen and evaluated. + /// It's indexex by Zobrist hash of a position mod size + transposition_table: TranspositionTable, +} + + +impl Grossmeister { + pub fn new(board: Board) -> Self { + return Self { + board, + attacks: Attacks::new(), + transposition_table: vec![None; TTABLE_SIZE as usize], + } + } +} diff --git a/src/grossmeister/move_generation.rs b/src/grossmeister/move_generation.rs new file mode 100644 index 0000000..25d92c7 --- /dev/null +++ b/src/grossmeister/move_generation.rs @@ -0,0 +1,266 @@ +use std::cmp::Ordering; + +use crate::{moves::{Move, MoveKind}, board::{color::Color, piece::Piece, CastlingSide}, bitboard::BitboardFns, square::Square}; + +use super::Grossmeister; + + +impl Grossmeister { + 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 + } + + fn generate_moves_core(&self, tactical_only: bool) -> Vec<Move> { + let color = self.board.color(); + let player_pieces = self.board.pieces_by_color(color); + let mut moves = Vec::with_capacity(256); + let empty = self.board.empty(); + + let targets = if tactical_only { + self.board.color_occupancy(color.flip()) ^ match color { + // Exclude opponent king because we can't capture it + Color::White => self.board.piece_sets[Piece::KingBlack as usize], + Color::Black => self.board.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.board.occupancy, source), + Piece::Rook => self.attacks.rook(self.board.occupancy, source), + Piece::Queen => self.attacks.queen(self.board.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.board.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.board.is_square_attacked(*square, color.flip())); + + if all_empty && !any_checks && self.board.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.board.is_square_attacked(*square, color.flip())); + + if all_empty && !any_checks && self.board.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 + } + + /// 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.board.piece_by_square(sq)) + .map(|p| { + match p { + Some(p) => p.static_eval(), + None => 0., + } + }); + return 2. * target_eval - source_eval + } + 0.0 + } + + 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 + } + +} + +#[cfg(test)] +mod tests { + use crate::board::{Board, io::IO}; + + use super::*; + + #[test] + fn generate_pseudolegal_moves_starting_position() { + let board = Board::new(); + let mut gm = Grossmeister::new(board); + let moves = gm.generate_pseudolegal_moves(); + gm.board.ply += 1; + let black_moves = gm.generate_pseudolegal_moves(); + + assert_eq!(moves.len(), 20); + assert_eq!(black_moves.len(), 20); + + for mov in moves { + mov.print(); + } + } + + + #[test] + fn moved_king_castle() { + let fen = String::from("4k2r/ppp1n3/8/4R1Pp/5P2/q1P5/P1P1BP2/1K1R4 b - - 2 22"); + let mut board = Board::from_FEN(fen); + board.ply += 1; + let gm = Grossmeister::new(board); + + // Shuffle kings around, returning to the same position + board.make_move(Move { source: Square::E8, target: Square::F8, kind: MoveKind::Quiet }); + board.make_move(Move { source: Square::B1, target: Square::A1, kind: MoveKind::Quiet }); + board.make_move(Move { source: Square::F8, target: Square::E8, kind: MoveKind::Quiet }); + board.make_move(Move { source: Square::A1, target: Square::B1, kind: MoveKind::Quiet }); + + let moves = gm.generate_pseudolegal_moves(); + + let castle = moves.iter().find(|m| **m == Move { source: Square::E8, target: Square::G8, kind: MoveKind::Castle }); + println!("{:?}", board.castling_rights); + assert!(castle.is_none(), "Castle should not be allowed after king has moved"); + } +} diff --git a/src/grossmeister/perft.rs b/src/grossmeister/perft.rs new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/grossmeister/perft.rs diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs new file mode 100644 index 0000000..57ce672 --- /dev/null +++ b/src/grossmeister/search.rs @@ -0,0 +1,426 @@ +use std::{time::{Instant, Duration}, f32::INFINITY}; + +use crate::{moves::{Move, MoveKind}, board::io::IO}; + +use super::{Grossmeister, ttable::{NodeType, TTABLE_SIZE, TranspositionTableItem}}; + +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, +} + +impl Grossmeister { + 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.board.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.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + + if !self.board.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.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + + if score >= beta { + self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.board.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.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.board.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.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.board.hash, + mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::All, + score, + }); + } + } else { + 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 + if Instant::now() > deadline { + break; + } + } + + if !legal_move_found { + if self.board.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.board.color(); + let mut moves = self.generate_pseudolegal_moves(); + moves = self.order_moves(moves, Vec::new()); + + if !self.board.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.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + + if !self.board.is_king_in_check(color) { + legal_move_found = true; + let evaluation = -self.quiscence(-beta, -alpha); + self.board.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.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); + } + } + + if !legal_move_found { + if self.board.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"), + } + } + + 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.board.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.board.ep_target.clone(); + let castling_rights_before = self.board.castling_rights.clone(); + let hash_before = self.board.hash.clone(); + let captured_piece = self.board.make_move(mov); + // King can not be in check after our own move + if !self.board.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.board.is_king_in_check(color.flip()) { + result.checks += 1; + } + } + + if print { + println!("{:?}", mov); + self.board.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.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); + } + + result + } +} + + +#[cfg(test)] +mod tests { + use std::time::Duration; + use crate::{board::{Board, io::IO}, square::Square, moves::{Move, MoveKind}, grossmeister::{Grossmeister, search::PerftResult}}; + use super::VALUE_WIN; + + #[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!(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 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!(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 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!(board.perft(3, false), PerftResult { leaf_nodes: 2812, captures: 209, en_passants: 2, castles: 0 , checks: 267 }); + } + + #[test] + fn checkmate() { + 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, 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 mut gm = Grossmeister::new(board); + let (_, pv) = gm.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 board = Board::from_FEN(fen); + + let mut gm = Grossmeister::new(board); + let (_, pv) = gm.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!" + ); + } +} diff --git a/src/board/ttable.rs b/src/grossmeister/ttable.rs index 9f9e0b0..4bf2398 100644 --- a/src/board/ttable.rs +++ b/src/grossmeister/ttable.rs @@ -1,5 +1,7 @@ use crate::moves::Move; +use super::Grossmeister; + /// https://www.chessprogramming.org/Node_Types #[derive(Debug, PartialEq, Clone, Copy)] pub enum NodeType { @@ -23,3 +25,20 @@ pub struct TranspositionTableItem { pub const TTABLE_SIZE: u64 = 2u64.pow(24); pub type TranspositionTable = Vec<Option<TranspositionTableItem>>; + + +impl Grossmeister { + /// Find current transposition in Transposition Table + pub fn transposition(&self) -> Option<TranspositionTableItem> { + match self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] { + Some(item) => { + if item.hash == self.board.hash { + return Some(item) + } + None + } + None => None + } + } + +} @@ -3,3 +3,4 @@ pub mod bitboard; pub mod board; pub mod attacks; pub mod moves; +pub mod grossmeister; diff --git a/src/main.rs b/src/main.rs index 7788b73..bb244ca 100644 --- a/src/main.rs +++ b/src/main.rs @@ -4,27 +4,28 @@ use std::env; use chessnost::board::color::Color; use chessnost::board::io::IO; use chessnost::board::Board; +use chessnost::grossmeister::Grossmeister; -fn opponent_move(board: &mut Board) { - let mov = match board.read_move() { +fn opponent_move(gm: &mut Grossmeister) { + let mov = match gm.board.read_move() { Ok(m) => m, Err(e) => { println!("Error: {}", e); - return opponent_move(board); + return opponent_move(gm); } }; print!("{:?}", mov); - board.make_move(mov); - board.print(); + gm.board.make_move(mov); + gm.board.print(); } -fn computer_move(board: &mut Board, time_left: &mut Duration) { +fn computer_move(gm: &mut Grossmeister, time_left: &mut Duration) { let allowed_move_duration = *time_left / 20; - let max_depth = 7 + (board.ply as i32 / 15) as u8; + let max_depth = 7 + (gm.board.ply as i32 / 15) as u8; println!("~{:?} left, allocating {:?} for a move", time_left, allowed_move_duration); let move_start = Instant::now(); - let (score, pv) = board.iterative_deepening(max_depth, allowed_move_duration, true); + let (score, pv) = gm.iterative_deepening(max_depth, allowed_move_duration, true); let elapsed = move_start.elapsed(); if *time_left >= elapsed { @@ -37,17 +38,17 @@ fn computer_move(board: &mut Board, time_left: &mut Duration) { let mov = pv[0]; println!("{:?}", mov); - board.make_move(mov); - board.print(); + gm.board.make_move(mov); + gm.board.print(); // Ponder for some time println!("Pondering, assume opponent move from PV: {:?}", pv[1]); - let ep_target_before = board.ep_target.clone(); - let castling_rights_before = board.castling_rights.clone(); - let hash_before = board.hash.clone(); - let captured_piece = board.make_move(pv[1]); - board.iterative_deepening(max_depth, Duration::from_secs(3), false); - board.unmake_move(pv[1], captured_piece, ep_target_before, castling_rights_before, hash_before); + let ep_target_before = gm.board.ep_target.clone(); + let castling_rights_before = gm.board.castling_rights.clone(); + let hash_before = gm.board.hash.clone(); + let captured_piece = gm.board.make_move(pv[1]); + gm.iterative_deepening(max_depth, Duration::from_secs(3), false); + gm.board.unmake_move(pv[1], captured_piece, ep_target_before, castling_rights_before, hash_before); } fn main() { @@ -71,25 +72,26 @@ fn main() { }); let manual_decrement = Duration::from_secs(7); // Time to sync moves with the game - let mut board = if args.len() == 5 { + let board = if args.len() == 5 { Board::from_FEN(args[4].to_string()) } else { Board::new() }; - board.print(); + let mut gm = Grossmeister::new(board); + gm.board.print(); loop { time_left += increment; time_left -= manual_decrement; match color { Color::White => { - computer_move(&mut board, &mut time_left); - opponent_move(&mut board); + computer_move(&mut gm, &mut time_left); + opponent_move(&mut gm); } Color::Black => { - opponent_move(&mut board); - computer_move(&mut board, &mut time_left); + opponent_move(&mut gm); + computer_move(&mut gm, &mut time_left); } } } |