diff options
Diffstat (limited to 'src/board/mod.rs')
-rw-r--r-- | src/board/mod.rs | 700 |
1 files changed, 700 insertions, 0 deletions
diff --git a/src/board/mod.rs b/src/board/mod.rs new file mode 100644 index 0000000..10d0a73 --- /dev/null +++ b/src/board/mod.rs @@ -0,0 +1,700 @@ +use crate::{bitboard::{Bitboard, serialize_bitboard, bitscan, pop_count}, moves::{Move, MoveKind}, attacks::Attacks, square::Square}; +mod engine; + +pub enum CastlingSide { + King, + Queen, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct Board { + pub pieces: [Bitboard; 12], + + pub occupancy: Bitboard, + pub ply: u16, + + /// En passsant target square + pub ep_target: Option<Square>, + + /// Castling rights indexed by Color and CastlingSide + /// ``` + /// let can_castle = castling_rights[Color::White as usize][CastlingSide::Queen as usize]; + /// ``` + pub castling_rights: [[bool; 2]; 2], + + attacks: Attacks, +} + + +#[derive(Debug, Clone, Copy, PartialEq, Eq, num_enum::FromPrimitive)] +#[repr(usize)] +pub enum PieceType { + #[default] + Pawn, + Knight, + Bishop, + Rook, + Queen, + King, + PawnBlack, + KnightBlack, + BishopBlack, + RookBlack, + QueenBlack, + KingBlack, +} + +const PIECE_CHARS: [&str; 12] = [ + "♟︎", "♞", "♝", "♜", "♛", "♚", + "♙", "♘", "♗", "♖", "♕", "♔", +]; + + +#[allow(unused)] +impl Board { + #[allow(non_snake_case)] + pub fn from_FEN(fen: String) -> Self { + let mut pieces = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; + + let mut rank = 7; + let mut file = 0i32; + + for character in fen.chars() { + let index = rank * 8 + file; + let position = 1 << index.clamp(0, 63); + + if character.is_numeric() { + let digit = match character.to_digit(10) { + None => todo!("What to do here?"), + Some(digit) => digit, + }; + if digit > 0 && digit <= 8 { + file += digit as i32; + } + } else { + match character { + 'P' => pieces[PieceType::Pawn as usize] |= position, + 'N' => pieces[PieceType::Knight as usize] |= position, + 'B' => pieces[PieceType::Bishop as usize] |= position, + 'R' => pieces[PieceType::Rook as usize] |= position, + 'Q' => pieces[PieceType::Queen as usize] |= position, + 'K' => pieces[PieceType::King as usize] |= position, + 'p' => pieces[PieceType::PawnBlack as usize] |= position, + 'n' => pieces[PieceType::KnightBlack as usize] |= position, + 'b' => pieces[PieceType::BishopBlack as usize] |= position, + 'r' => pieces[PieceType::RookBlack as usize] |= position, + 'q' => pieces[PieceType::QueenBlack as usize] |= position, + 'k' => pieces[PieceType::KingBlack as usize] |= position, + '/' => { + rank -= 1; + file = -1; // So it becomes 0 + }, + ' ' => { break }, // TODO: break for now, parse everything else later + '-' => {}, // TODO + 'w' => {}, // TODO + _ => todo!("Unexpected character!"), + } + file += 1; + } + } + + let mut board = Self { + pieces, + occupancy: 0, + ply: 0, + attacks: Attacks::new(), + castling_rights: [[true; 2]; 2], // TODO: actualy parse from FEN + ep_target: None, + }; + board.update_occupancy(); + board + } + + pub fn new() -> Self { + let default_fen = String::from("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"); + Self::from_FEN(default_fen) + } + + /// Color to move at this ply + fn color(&self) -> Color { + Color::from(self.ply as u8 % 2) + } + + fn update_occupancy(&mut self) { + self.occupancy = 0; + // TODO: reduce + for piece in self.pieces { + self.occupancy |= piece; + } + } + + fn empty(&self) -> Bitboard { + !self.occupancy + } + + fn pieces_by_color(&self, color: Color) -> &[Bitboard] { + match color { + Color::White => &self.pieces[0..6], + Color::Black => &self.pieces[6..12], + } + } + + fn color_occupancy(&self, color: Color) -> Bitboard { + let mut occupancy = 0; + for piece in self.pieces_by_color(color) { + occupancy |= piece; + } + occupancy + } + + pub fn color_to_move(&self) -> Color { + Color::from((self.ply % 2) as u8) + } + + pub fn print(&self) { + println!(); + for rank in (0..8).rev() { + print!("{}|", rank + 1); + for file in 0..8 { + let index = rank * 8 + file; + let position: Bitboard = 1 << index; + let mut found = false; + for (piece_type, piece_bitboard) in self.pieces.iter().enumerate() { + if (piece_bitboard & position) > 0 { + found = true; + print!("{} ", PIECE_CHARS[piece_type]); + } + } + if !found { + print!(". "); + } + } + println!(); + } + println!(" a b c d e f g h"); + } + + pub fn generate_pseudolegal_moves(&self, color: Color) -> Vec<Move> { + let mut moves = Vec::with_capacity(1024); + let opponent_occupancy = self.color_occupancy(color.flip()); + let empty = self.empty(); + let available_targets = opponent_occupancy | empty; + let player_pieces = self.pieces_by_color(color); + + for (piece_type, piece) in player_pieces.iter().enumerate() { + match PieceType::from(piece_type) { + PieceType::Pawn => { + for source in serialize_bitboard(*piece) { + let ep_bitboard = match self.ep_target { + Some(square) => square.to_bitboard(), + None => 0, + }; + for target in serialize_bitboard(self.attacks.pawn[color as usize][source as usize] & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + for target in serialize_bitboard(self.attacks.pawn[color as usize][source as usize] & ep_bitboard) { + moves.push(Move { source, target, kind: MoveKind::EnPassant }); + } + for target in serialize_bitboard(self.attacks.pawn_pushes[color as usize][source as usize] & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + } + + // 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 serialize_bitboard(*piece & able_to_double_push_mask) { + for target in serialize_bitboard(self.attacks.pawn_double_pushes[color as usize][source as usize] & empty) { + moves.push(Move { source, target, kind: MoveKind::DoublePush }); + }; + } + } + PieceType::King => { + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.king[source as usize] & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + for target in serialize_bitboard(self.attacks.king[source as usize] & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + + // 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 serialize_bitboard(player_pieces[PieceType::Rook as usize]) + .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] { + moves.push(Move { + source: king_home_position, + target: king_home_position.west_one().west_one(), + kind: MoveKind::Castle, + }) + } + }, + 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] { + moves.push(Move { + source: king_home_position, + target: king_home_position.east_one().east_one(), + kind: MoveKind::Castle, + }) + } + }, + _ => {}, + } + } + } + } + } + PieceType::Knight => { + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.knight[source as usize] & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + for target in serialize_bitboard(self.attacks.knight[source as usize] & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + } + } + PieceType::Bishop => { + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.bishop(self.occupancy, source) & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + for target in serialize_bitboard(self.attacks.bishop(self.occupancy, source) & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + } + } + PieceType::Rook => { + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.rook(self.occupancy, source) & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + } + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.rook(self.occupancy, source) & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + } + } + PieceType::Queen => { + for source in serialize_bitboard(*piece) { + for target in serialize_bitboard(self.attacks.queen(self.occupancy, source) & empty) { + moves.push(Move { source, target, kind: MoveKind::Quiet }); + }; + for target in serialize_bitboard(self.attacks.queen(self.occupancy, source) & opponent_occupancy) { + moves.push(Move { source, target, kind: MoveKind::Capture }); + }; + } + } + _ => todo!("Incorrect piece type") + } + } + moves + } + + /// *Blindlessly* apply a move without any validation + /// Move should be validated beforehand + pub fn make_move(&mut self, mov: Move) -> Option<PieceType> { + let move_source_bb = mov.source.to_bitboard(); + let move_target_bb = mov.target.to_bitboard(); + + // Remove existing piece (if any) from target square + let mut captured_piece = match self.pieces + .iter() + .enumerate() + .find(|(piece_type, bitboard)| *bitboard & mov.target.to_bitboard() > 0) + { + Some((target_piece, _)) => { + self.pieces[target_piece] ^= move_target_bb; + Some(PieceType::from(target_piece)) + }, + None => None, + }; + + // En Passant captures diffirently + if mov.kind == MoveKind::EnPassant { + debug_assert!(captured_piece.is_none(), "No capture should be found at this point"); + let captured_bb = Square::from_coords(mov.source.rank(), mov.target.file()).to_bitboard(); + captured_piece = match self.pieces + .iter() + .enumerate() + .find(|(piece_type, bitboard)| *bitboard & captured_bb > 0) + { + Some((pawn_type, _)) => { + self.pieces[pawn_type] ^= captured_bb; + Some(PieceType::from(pawn_type)) + } + None => panic!("Pawn captured by En Passant was not found"), + } + } + + // Move a piece from source square to target + let source_piece = match self.pieces + .iter() + .enumerate() + .find(|(piece_type, bitboard)| *bitboard & mov.source.to_bitboard() > 0) + { + Some((source_piece, _)) => { + self.pieces[source_piece] ^= move_source_bb; + self.occupancy ^= move_source_bb; + + self.pieces[source_piece] |= move_target_bb; + self.occupancy |= move_target_bb; + PieceType::from(source_piece) + }, + None => panic!("Move is malformed: source piece not found"), + }; + + // When castling, also move a rook + if mov.kind == MoveKind::Castle { + debug_assert!(mov.source.file() == 4, "Castle can only be done from E file"); + let (rook_source_file, rook_target_file) = match mov.target.file() { + 2 => (0, 3), + 6 => (7, 5), + _ => panic!("Malformed castle, target square invalid: {:?}", mov), + }; + let rook_source_bb = Square::from_coords(mov.target.rank(), rook_source_file).to_bitboard(); + let rook_target_bb = Square::from_coords(mov.target.rank(), rook_target_file).to_bitboard(); + + match self.pieces + .iter() + .enumerate() + .find(|(rook_type, bitboard)| *bitboard & rook_source_bb > 0) + { + Some((rook_type, _)) => { + self.pieces[rook_type] ^= rook_source_bb; + self.occupancy ^= rook_source_bb; + + self.pieces[rook_type] |= rook_target_bb; + self.occupancy |= rook_target_bb; + }, + None => panic!("Rook was not found when castling"), + } + } + + // Double push should set En Passant target square + self.ep_target = if mov.kind == MoveKind::DoublePush { + match mov.source.rank() { + 1 => Some(mov.source.nort_one()), + 6 => Some(mov.source.sout_one()), + rank => panic!("Double-push was used from invalid rank({}) when trying to make {:?}", rank, mov), + } + } else { None }; + + // Withdraw castling rights when moving rooks or king + match source_piece { + PieceType::King => { + self.castling_rights[Color::from_piece(source_piece) as usize][CastlingSide::King as usize] = false; + self.castling_rights[Color::from_piece(source_piece) as usize][CastlingSide::Queen as usize] = false; + }, + PieceType::Rook => { + match mov.source.file() { + 0 => self.castling_rights[Color::from_piece(source_piece) as usize][CastlingSide::Queen as usize] = false, + 7 => self.castling_rights[Color::from_piece(source_piece) as usize][CastlingSide::King as usize] = false, + _ => {}, + } + }, + _ => {}, + } + + self.ply += 1; + + captured_piece + } + + /// Completely reverse make_move as if it never happened + pub fn unmake_move(&mut self, mov: Move, captured_piece: Option<PieceType>, previous_ep_target: Option<Square>, previous_castling_rights: [[bool; 2]; 2]) { + let move_source_bb = mov.source.to_bitboard(); + let move_target_bb = mov.target.to_bitboard(); + + // Move a piece from target square back to source square + match self.pieces + .iter() + .enumerate() + .find(|(piece_type, bitboard)| *bitboard & mov.target.to_bitboard() > 0) + { + Some((source_piece, _)) => { + self.pieces[source_piece] ^= move_target_bb; + self.occupancy ^= move_target_bb; + + self.pieces[source_piece] |= move_source_bb; + self.occupancy |= move_source_bb; + }, + None => panic!("Trying to unmake move which was not made: no piece was found on target square"), + }; + + // If unmaking castle, also return rook to its place + if mov.kind == MoveKind::Castle { + let (rook_source_file, rook_target_file) = match mov.target.file() { + 2 => (0, 3), + 6 => (7, 5), + _ => panic!("Malformed castle, target square invalid: {:?}", mov), + }; + let rook_source_bb = Square::from_coords(mov.target.rank(), rook_source_file).to_bitboard(); + let rook_target_bb = Square::from_coords(mov.target.rank(), rook_target_file).to_bitboard(); + + match self.pieces + .iter() + .enumerate() + .find(|(rook_type, bitboard)| *bitboard & rook_target_bb > 0) + { + Some((rook_type, _)) => { + self.pieces[rook_type] |= rook_source_bb; + self.occupancy |= rook_source_bb; + + self.pieces[rook_type] ^= rook_target_bb; + self.occupancy ^= rook_target_bb; + }, + None => panic!("Rook was not found when castling"), + } + } + + // Return captured piece to target square + match captured_piece { + Some(target_piece) => { + match mov.kind { + // Return pawn captured by En Passant pawn if needed + MoveKind::EnPassant => { + let original_dead_pawn_bb = Square::from_coords(mov.source.rank(), mov.target.file()).to_bitboard(); + self.pieces[target_piece as usize] |= original_dead_pawn_bb; + self.occupancy |= original_dead_pawn_bb; + }, + _ => { + self.pieces[target_piece as usize] |= move_target_bb; + self.occupancy |= move_target_bb; + }, + } + }, + None => {} + } + + + self.ep_target = previous_ep_target; + self.castling_rights = previous_castling_rights; + self.ply -= 1; + } + + fn is_square_attacked(&self, square: Square, attacker_color: Color) -> bool { + let square_bb = square.to_bitboard(); + for (piece_type, piece) in self.pieces_by_color(attacker_color).iter().enumerate() { + match PieceType::from(piece_type) { + PieceType::Pawn => { + if (self.attacks.pawn[attacker_color.flip() as usize][square as usize] & piece > 0) { + return true + } + } + PieceType::Knight => { + if (self.attacks.knight[square as usize] & piece > 0) { + return true + } + } + PieceType::Bishop => { + if (self.attacks.bishop(self.occupancy, square) & piece > 0) { + return true + } + } + PieceType::Rook => { + if (self.attacks.rook(self.occupancy, square) & piece > 0) { + return true + } + } + PieceType::Queen => { + if (self.attacks.queen(self.occupancy, square) & piece > 0) { + return true + } + } + PieceType::King => {} + _ => panic!("Unexpected piece type! Pieces by color should be considered white") + } + } + false + } + + fn is_king_in_check(&self, color: Color) -> bool { + let king_bb = match color { + Color::White => self.pieces[PieceType::King as usize], + Color::Black => self.pieces[PieceType::KingBlack as usize], + }; + let square = bitscan(king_bb); + self.is_square_attacked(square, color.flip()) + } +} + + +#[derive(Debug, Clone, Copy, PartialEq, num_enum::FromPrimitive)] +#[repr(u8)] +pub enum Color { + #[default] + White, + Black, +} +impl Color { + pub fn flip(&self) -> Self { + match self { + Self::White => Self::Black, + Self::Black => Self::White, + } + } + pub fn from_piece(piece: PieceType) -> Self { + if (piece as u8) < 6 { + Self::White + } else { + Self::Black + } + } +} + +#[cfg(test)] +mod tests { + use std::f32::INFINITY; + + use super::*; + use crate::{bitboard::{pop_count, bitscan, print}, square::Square}; + + #[test] + fn square_enum() { + assert_eq!(Square::A1 as u8, 0); + assert_eq!(Square::F1 as u8, 5); + assert_eq!(Square::H8 as u8, 63); + } + + #[test] + fn new_from_default_fen() { + let board = Board::new(); + + board.print(); + print(board.empty(), "Empty squares"); + + assert_eq!(pop_count(board.pieces[PieceType::Pawn as usize]), 8); + assert_eq!(pop_count(board.pieces[PieceType::Knight as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::Bishop as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::Rook as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::Queen as usize]), 1); + assert_eq!(pop_count(board.pieces[PieceType::King as usize]), 1); + + assert_eq!(pop_count(board.pieces[PieceType::PawnBlack as usize]), 8); + assert_eq!(pop_count(board.pieces[PieceType::KnightBlack as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::BishopBlack as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::RookBlack as usize]), 2); + assert_eq!(pop_count(board.pieces[PieceType::QueenBlack as usize]), 1); + assert_eq!(pop_count(board.pieces[PieceType::KingBlack as usize]), 1); + + assert_eq!(bitscan(board.pieces[PieceType::King as usize]), Square::E1); + assert_eq!(bitscan(board.pieces[PieceType::QueenBlack as usize]), Square::D8); + + assert_eq!(pop_count(board.occupancy), 32); + assert_eq!(pop_count(board.empty()), 32); + assert_eq!(pop_count(board.color_occupancy(Color::White)), 16); + assert_eq!(pop_count(board.color_occupancy(Color::Black)), 16); + } + + #[test] + fn generate_pseudolegal_moves_starting_position() { + let board = Board::new(); + let moves = board.generate_pseudolegal_moves(Color::White); + let black_moves = board.generate_pseudolegal_moves(Color::Black); + + assert_eq!(moves.len(), 20); + assert_eq!(black_moves.len(), 20); + + for mov in moves { + mov.print(); + } + } + + #[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); + let initial_board = board.clone(); + board.print(); + + let black_move = Move { source: Square::F7, target: Square::F5, kind: MoveKind::Quiet }; + println!("\n{:?}", black_move); + + match board.make_move(black_move) { + Some(..) => panic!("No piece should be captured"), + None => {}, + }; + + board.print(); + + assert!(board.pieces[PieceType::PawnBlack as usize] & Square::F7.to_bitboard() == 0); + assert!(board.pieces[PieceType::PawnBlack as usize] & Square::F5.to_bitboard() > 0); + assert!(board.ply == 1); + + let white_move = Move { source: Square::D2, target: Square::A5, kind: MoveKind::Capture }; + println!("\n{:?}", white_move); + + match board.make_move(white_move) { + Some(captured) => assert!(captured == PieceType::PawnBlack), + None => panic!("A piece should be captured"), + }; + + board.print(); + + assert!(board.pieces[PieceType::PawnBlack as usize] & Square::A5.to_bitboard() == 0, "Target piece should be captured"); + assert!(board.pieces[PieceType::Queen as usize] & Square::D2.to_bitboard() == 0); + assert!(board.pieces[PieceType::Queen as usize] & Square::A5.to_bitboard() > 0); + assert_ne!(board.occupancy, initial_board.occupancy, "Occupancy should change after make_move"); + assert!(board.ply == 2); + } + + #[test] + fn unmake_move() { + let fen = String::from("q1b2k2/5p1p/4p1pb/pPPp4/3N4/3nPB2/P2QKnR1/1R6 w - - 0 25"); + let mut board = Board::from_FEN(fen); + let initial_board = board.clone(); + + let mov = Move { source: Square::D2, target: Square::A5, kind: MoveKind::Capture }; + + board.print(); + + let captured_piece = board.make_move(mov); + board.print(); + + board.unmake_move(mov, captured_piece, None, board.castling_rights); + board.print(); + + assert_eq!(board, initial_board, "Board state after unmake_move should be the same as before make_move"); + } + + #[test] + fn is_square_attacked() { + let board = Board::new(); + + assert_eq!(board.is_square_attacked(Square::E2, Color::White), true); + assert_eq!(board.is_square_attacked(Square::E2, Color::Black), false); + assert_eq!(board.is_square_attacked(Square::E4, Color::White), false); + assert_eq!(board.is_square_attacked(Square::B6, Color::Black), true); + } + +} |