From 573d674bffd9275ea98abc119e747e74e2abc941 Mon Sep 17 00:00:00 2001 From: eug-vs Date: Thu, 23 Feb 2023 14:49:06 +0300 Subject: refactor: return move generation to board module --- src/board/mod.rs | 1 + src/board/move_generation.rs | 200 +++++++++++++++++++++++++++ src/grossmeister/mod.rs | 1 - src/grossmeister/move_generation.rs | 262 ------------------------------------ src/grossmeister/search.rs | 66 ++++++++- src/lib.rs | 2 + src/player.rs | 7 + 7 files changed, 273 insertions(+), 266 deletions(-) create mode 100644 src/board/move_generation.rs delete mode 100644 src/grossmeister/move_generation.rs create mode 100644 src/player.rs (limited to 'src') diff --git a/src/board/mod.rs b/src/board/mod.rs index aab3136..ff01ddc 100644 --- a/src/board/mod.rs +++ b/src/board/mod.rs @@ -4,6 +4,7 @@ use self::{zobrist::{ZobristSeed, Zobrist}, piece::Piece, color::Color}; pub mod io; pub mod color; pub mod piece; +pub mod move_generation; mod zobrist; #[derive(Debug, Clone, Copy)] diff --git a/src/board/move_generation.rs b/src/board/move_generation.rs new file mode 100644 index 0000000..77714c8 --- /dev/null +++ b/src/board/move_generation.rs @@ -0,0 +1,200 @@ +use crate::{moves::{Move, MoveKind}, board::{color::Color, piece::Piece, CastlingSide}, bitboard::BitboardFns, square::Square}; + +use super::Board; + + +impl Board { + pub fn generate_pseudolegal_moves(&self) -> Vec { + 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 { + 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, + }) + } + }, + _ => {}, + } + } + } + } + moves + } +} + +#[cfg(test)] +mod tests { + use crate::board::{Board, io::IO}; + + use super::*; + + #[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 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 }); + board.print(); + + 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/mod.rs b/src/grossmeister/mod.rs index 6ed5f17..d9e5d1d 100644 --- a/src/grossmeister/mod.rs +++ b/src/grossmeister/mod.rs @@ -2,7 +2,6 @@ use crate::{board::Board, attacks::Attacks}; use self::ttable::{TranspositionTable, TTABLE_SIZE}; mod ttable; -mod move_generation; mod evaluation; mod search; diff --git a/src/grossmeister/move_generation.rs b/src/grossmeister/move_generation.rs deleted file mode 100644 index ea40d18..0000000 --- a/src/grossmeister/move_generation.rs +++ /dev/null @@ -1,262 +0,0 @@ -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 { - 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 { - 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, - }) - } - }, - _ => {}, - } - } - } - } - 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, killer_moves: Vec) -> Vec { - 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 = moves_with_eval.iter().map(|(m, _)| *m).collect(); - - // Insert killer moves after winning captures - let equal_capture_index = moves_with_eval - .iter() - .position(|(m, eval)| m.is_tactical() && *eval == 0.0) - .unwrap_or(0); - - for killer in killer_moves { - if let Some(index) = ordered_moves.iter().position(|m| *m == killer) { - let mov = ordered_moves.remove(index); - ordered_moves.insert(equal_capture_index, mov); - } - } - - if let Some(transposition) = self.transposition() { - ordered_moves.insert(0, transposition.mov); - } - - 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 board = Board::from_FEN(fen); - let mut gm = Grossmeister::new(board); - gm.board.ply += 1; - - // Shuffle kings around, returning to the same position - gm.board.make_move(Move { source: Square::E8, target: Square::F8, kind: MoveKind::Quiet }); - gm.board.make_move(Move { source: Square::B1, target: Square::A1, kind: MoveKind::Quiet }); - gm.board.make_move(Move { source: Square::F8, target: Square::E8, kind: MoveKind::Quiet }); - gm.board.make_move(Move { source: Square::A1, target: Square::B1, kind: MoveKind::Quiet }); - gm.board.print(); - - 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/search.rs b/src/grossmeister/search.rs index 3efa9f8..ff6375c 100644 --- a/src/grossmeister/search.rs +++ b/src/grossmeister/search.rs @@ -1,3 +1,4 @@ +use std::cmp::Ordering; use std::{time::{Instant, Duration}, f32::INFINITY}; use crate::{moves::{Move, MoveKind}, board::io::IO}; @@ -48,7 +49,7 @@ impl Grossmeister { return (self.quiscence(alpha, beta), principal_variation); } - let mut moves = self.generate_pseudolegal_moves(); + let mut moves = self.board.generate_pseudolegal_moves(); moves = self.order_moves(moves, parent_killers.to_vec()); let mut should_pv_search = true; @@ -141,7 +142,7 @@ impl Grossmeister { pub fn quiscence(&mut self, mut alpha: f32, beta: f32) -> f32 { let color = self.board.color(); - let mut moves = self.generate_pseudolegal_moves(); + let mut moves = self.board.generate_pseudolegal_moves(); moves = self.order_moves(moves, Vec::new()); if !self.board.is_king_in_check(color) { @@ -259,6 +260,65 @@ impl Grossmeister { } } + /// 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, killer_moves: Vec) -> Vec { + 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 = moves_with_eval.iter().map(|(m, _)| *m).collect(); + + // Insert killer moves after winning captures + let equal_capture_index = moves_with_eval + .iter() + .position(|(m, eval)| m.is_tactical() && *eval == 0.0) + .unwrap_or(0); + + for killer in killer_moves { + if let Some(index) = ordered_moves.iter().position(|m| *m == killer) { + let mov = ordered_moves.remove(index); + ordered_moves.insert(equal_capture_index, mov); + } + } + + if let Some(transposition) = self.transposition() { + ordered_moves.insert(0, transposition.mov); + } + + ordered_moves + } + + pub fn perft(&mut self, depth: u8, print: bool) -> PerftResult { let mut result = PerftResult::default(); @@ -268,7 +328,7 @@ impl Grossmeister { } let color = self.board.color(); - let moves = self.generate_pseudolegal_moves(); + let moves = self.board.generate_pseudolegal_moves(); if print { println!("Running perft for depth {}. Color to move is {:?}\n{} moves available", depth, color, moves.len()); diff --git a/src/lib.rs b/src/lib.rs index beebe77..93dc573 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -3,4 +3,6 @@ pub mod bitboard; pub mod board; pub mod attacks; pub mod moves; +pub mod player; pub mod grossmeister; + diff --git a/src/player.rs b/src/player.rs new file mode 100644 index 0000000..26cf0cc --- /dev/null +++ b/src/player.rs @@ -0,0 +1,7 @@ +use crate::{board::Board, moves::Move}; + +pub trait Player { + /// Analyze a position on a given board, giving + /// the score for the side to move and Principal Variation. + fn analyze(&self, board: Board) -> (f32, Vec); +} -- cgit v1.2.3