From bf9e9af7f45433def26d2d2094a04798cb0282c0 Mon Sep 17 00:00:00 2001 From: mrw1593 Date: Tue, 13 Jul 2021 17:54:25 -0400 Subject: Updated docs and tests --- model/src/board.rs | 1178 +++++++++++++++++++++---------------------- model/src/board/tests.rs | 23 + model/src/color.rs | 151 +++--- model/src/moves.rs | 148 +++--- model/src/moves_iter.rs | 287 +++++------ model/src/possible_moves.rs | 671 ++++++++++++------------ 6 files changed, 1284 insertions(+), 1174 deletions(-) (limited to 'model/src') diff --git a/model/src/board.rs b/model/src/board.rs index 0128c89..75c29cb 100644 --- a/model/src/board.rs +++ b/model/src/board.rs @@ -1,589 +1,589 @@ -use crate::possible_moves::PossibleMoves; -use crate::PieceColor; -#[cfg(feature = "serde")] -use serde::{Deserialize, Serialize}; -use std::hash::{Hash, Hasher}; - -#[cfg(test)] -mod tests; - -/// A checker board, -/// organized in the following structure: -/// ```txt -/// 11 05 31 25 -/// 10 04 30 24 -/// 03 29 23 17 -/// 02 28 22 16 -/// 27 21 15 09 -/// 26 20 14 08 -/// 19 13 07 01 -/// 18 12 06 00 -/// ``` -#[derive(Copy, Clone, Debug, Eq)] -#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] -pub struct CheckersBitBoard { - /// If the space contains a piece, it's a 1 - pieces: u32, - /// If the piece is black, 1, otherwise 0 - color: u32, - /// 1 if the piece is a king - kings: u32, - /// The player who has the next turn - turn: PieceColor, -} - -impl Default for CheckersBitBoard { - /// Returns the starting position - fn default() -> Self { - Self::starting_position() - } -} - -impl PartialEq for CheckersBitBoard { - fn eq(&self, other: &Self) -> bool { - self.pieces == other.pieces - && self.pieces & self.color == other.pieces & other.color - && self.pieces & self.kings == other.pieces & other.kings - && self.turn == other.turn - } -} - -impl Hash for CheckersBitBoard { - /// Hashes with only the pieces part, to ensure correctness and efficiency - fn hash(&self, hasher: &mut H) { - self.pieces.hash(hasher) - } -} - -impl CheckersBitBoard { - /// Creates a new Checkers BitBoard - /// - /// # Arguments - /// - /// * `pieces` - Each bit is 1 if the corresponding space contains a piece - /// * `color` - For each space with a piece, the value is 1 if it's dark, and 0 otherwise. - /// Bits for spaces without colors are undefined - /// * `kings` - For each space with a piece, the value is 1 if it's a king, and 0 otherwise. - /// Bits for spaces without colors are undefined - /// - /// # Example - /// - /// ``` - /// // This is the starting position - /// use model::{CheckersBitBoard, PieceColor}; - /// let board = CheckersBitBoard::new(0b11011111101111100111100111100111, - /// 0b00111100001100001100001111001111, - /// 0, - /// PieceColor::Dark); - /// ``` - pub const fn new(pieces: u32, color: u32, kings: u32, turn: PieceColor) -> Self { - Self { - pieces, - color, - kings, - turn, - } - } - - /// Creates a board at the starting position - pub const fn starting_position() -> Self { - const STARTING_BITBOARD: CheckersBitBoard = CheckersBitBoard::new( - 0b11100111100111100111110111111011, - 0b00001100001111001111001111000011, - 0, - PieceColor::Dark, - ); - STARTING_BITBOARD - } - - /// Gets the bits that represent where pieces are on the board - pub const fn pieces_bits(self) -> u32 { - self.pieces - } - - /// Gets the bits that represents the color of each piece on the board - /// - /// # Safety - /// - /// This is inherently unsafe, because this also returns the bits of empty squares - pub const fn color_bits(self) -> u32 { - self.color - } - - /// Gets the bits that represents the status of each piece on the board - /// - /// # Safety - /// - /// This is inherently unsafe, because this also returns the bits of empty squares - pub const fn king_bits(self) -> u32 { - self.kings - } - - /// The player whose turn it is - pub const fn turn(self) -> PieceColor { - self.turn - } - - /// Checks if there's a piece at the given space value - /// - /// # Arguments - /// - /// * `value` - The value of the space to check - /// - /// # Example - /// - /// ``` - /// use model::CheckersBitBoard; - /// let board = CheckersBitBoard::default(); - /// match board.piece_at(0) { - /// true => println!("There's a piece in the bottom right"), - /// false => println!("The bottom right is empty") - /// } - /// ``` - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - pub const fn piece_at(self, value: usize) -> bool { - ((self.pieces >> value) & 1) == 1 - } - - /// Checks the color at the piece in the given location, - /// without checking if there's a piece there - /// - /// # Arguments - /// - /// * `value` - The value of the space to check - /// - /// # Example - /// - /// ``` - /// use model::CheckersBitBoard; - /// use model::PieceColor; - /// let board = CheckersBitBoard::default(); - /// if board.piece_at(0) { - /// match unsafe {board.color_at_unchecked(0)} { - /// PieceColor::Dark => println!("The piece in the bottom right is dark colored"), - /// PieceColor::Light => println!("The piece in the bottom right is light colored") - /// } - /// } - /// ``` - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Checking the color at a square that is empty results in undefined behavior - pub const unsafe fn color_at_unchecked(self, value: usize) -> PieceColor { - if ((self.color >> value) & 1) != 0 { - PieceColor::Dark - } else { - PieceColor::Light - } - } - - /// Checks the color at the piece in the given location. - /// Returns `None` if there isn't a piece there - /// - /// # Arguments - /// - /// * `value` - The value of the space to check - /// - /// # Example - /// - /// ``` - /// use model::CheckersBitBoard; - /// use model::PieceColor; - /// let board = CheckersBitBoard::default(); - /// if let Some(color) = board.color_at(0) { - /// match color { - /// PieceColor::Dark => println!("The piece in the bottom right is dark colored"), - /// PieceColor::Light => println!("The piece in the bottom left is light colored") - /// } - /// } - /// ``` - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - pub const fn color_at(self, value: usize) -> Option { - if self.piece_at(value) { - // safety: if this block runs, then it's already confirmed a piece exists here - Some(unsafe { self.color_at_unchecked(value) }) - } else { - None - } - } - - /// Checks if the given location has a king, without checking if there's a piece there - /// - /// # Arguments - /// - /// * `value` - The value of the space to check - /// - /// # Example - /// - /// ``` - /// use model::CheckersBitBoard; - /// let board = CheckersBitBoard::default(); - /// if board.piece_at(0) { - /// match unsafe {board.king_at_unchecked(0)} { - /// true => println!("The piece in the bottom right is a king"), - /// false => println!("The piece in the bottom right is a peasant") - /// } - /// } - /// ``` - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Checking a square that is empty results in undefined behavior - pub const unsafe fn king_at_unchecked(self, value: usize) -> bool { - ((self.kings >> value) & 1) == 1 - } - - /// Checks if the piece in the given location is a king. - /// Returns `None` if there isn't a piece there - /// - /// # Arguments - /// - /// * `value` - The value of the space to check - /// - /// # Example - /// - /// ``` - /// use model::CheckersBitBoard; - /// let board = CheckersBitBoard::default(); - /// if let Some(status) = board.king_at(0) { - /// match status { - /// true => println!("The piece in the bottom right is a king"), - /// false => println!("The piece in the bottom right is a peasant") - /// } - /// } - /// ``` - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - pub const fn king_at(self, value: usize) -> Option { - if self.piece_at(value) { - // safety: if this block runs, then it's already confirmed a piece exists here - Some(unsafe { self.king_at_unchecked(value) }) - } else { - None - } - } - - pub const fn flip_turn(self) -> Self { - CheckersBitBoard::new(self.pieces, self.color, self.kings, self.turn.flip()) - } - - /// Moves a piece from `start` to `dest`. The original location will be empty. - /// This does not mutate the original board. - /// If a piece already exists at `dest`, it will be overwritten. - /// - /// # Arguments - /// - /// * `start` - The original location of the piece - /// * `dest` - The new location - /// - /// # Panics - /// - /// Panics if `start` or `dest` is greater than or equal to 32 - /// - /// # Safety - /// - /// Results in undefined behavior if `start` does not contain a piece - pub const unsafe fn move_piece_to_unchecked(self, start: usize, dest: usize) -> Self { - // Clears the bit at the starting value - // Sets the bit at the destination value - let pieces = (self.pieces & !(1 << start)) | (1 << dest); - - // Clears the bit at the destination value - // Sets the value at the destination to the value of the start - let color = (self.color & !(1 << dest)) | (((self.color >> start) & 1) << dest); - - // The squares where certain pieces should be promoted - const DARK_PROMOTION_MASK: u32 = 0b10000010000000000000100000100000; - const LIGHT_PROMOTION_MASK: u32 = 0b1000001000001000001; - - // Clears the bit at the destination value - // Sets the value at the destination to the value of the start - // Promotes if the end of the board was reached - let kings = (self.kings & !(1 << dest)) - | (((self.kings >> start) & 1) << dest) - | (self.color & DARK_PROMOTION_MASK) - | (!self.color & LIGHT_PROMOTION_MASK); - - let turn = self.turn.flip(); - - CheckersBitBoard::new(pieces, color, kings, turn) - } - - /// Moves a piece from `value` to `(value + amount) % 32`. The original location will be empty. - /// This does not mutate the original board - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// * `amount` - The amount to shift the location by - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32, - /// or `value + amount` is greater than `usize::MAX` - /// - /// # Safety - /// - /// This results in undefined behavior if `value` does not contain a piece - const unsafe fn move_piece_forward_unchecked(self, value: usize, amount: usize) -> Self { - self.move_piece_to_unchecked(value, (value + amount) & 31) - } - - /// Moves a piece from `value` to `(value - amount) % 32`. The original location will be empty. - /// This does not mutate the original board. - /// If a piece already exists there, then it will be overwritten - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// * `amount` - The amount to shift the location by - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// This results in undefined behavior if `value` does not contain a piece - const unsafe fn move_piece_backward_unchecked(self, value: usize, amount: usize) -> Self { - self.move_piece_to_unchecked(value, value.wrapping_sub(amount) & 31) - } - - /// Tries to move the piece forward and to the left, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the left side of the board results in undefined behavior. - /// Moving from the top of the board results in undefined behavior. - /// A `value` which doesn't contain a piece results in undefined behavior. - pub const unsafe fn move_piece_forward_left_unchecked(self, value: usize) -> Self { - self.move_piece_forward_unchecked(value, 7) - } - - /// Tries to move the piece forward and to the right, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the right side of the board results in undefined behavior. - /// Moving from the top of the board results in undefined behavior. - /// A `value` which doesn't contain a piece results in undefined behavior. - pub const unsafe fn move_piece_forward_right_unchecked(self, value: usize) -> Self { - self.move_piece_forward_unchecked(value, 1) - } - - /// Tries to move the piece backward and to the left, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the left side of the board results in undefined behavior. - /// Moving from the bottom of the board results in undefined behavior. - /// A `value` which doesn't contain a piece results in undefined behavior. - pub const unsafe fn move_piece_backward_left_unchecked(self, value: usize) -> Self { - self.move_piece_backward_unchecked(value, 1) - } - - /// Tries to move the piece backward and to the right, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the right side of the board results in undefined behavior. - /// Moving from the bottom of the board results in undefined behavior. - /// A `value` which doesn't contain a piece results in undefined behavior. - pub const unsafe fn move_piece_backward_right_unchecked(self, value: usize) -> Self { - self.move_piece_backward_unchecked(value, 7) - } - - /// Clears a space on the board. If the space is empty, then this function does nothing. - /// - /// # Arguments - /// - /// * `value` - The value of the space to clear - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - pub const fn clear_piece(self, value: usize) -> Self { - let pieces = self.pieces & !(1 << value); - CheckersBitBoard::new(pieces, self.color, self.kings, self.turn) - } - - /// Tries to jump the piece forward and to the left, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten. - /// The space the piece jumps over is cleared - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the left side of the board results in undefined behavior. - /// Moving from the top of the board results in undefined behavior - pub const unsafe fn jump_piece_forward_left_unchecked(self, value: usize) -> Self { - let not_king = !self.king_at_unchecked(value); - let board = self - .move_piece_forward_unchecked(value, 14) - .clear_piece((value + 7) & 31); - - const KING_MASK: u32 = 0b01000001000000000000010000010000; - if PossibleMoves::has_jumps(board.flip_turn()) - && not_king && (((1 << value) & KING_MASK) == 0) - { - board.flip_turn() - } else { - board - } - } - - /// Tries to move the piece forward and to the right, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// The space the piece jumps over is cleared - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the right side of the board results in undefined behavior. - /// Moving from the top of the board results in undefined behavior - pub const unsafe fn jump_piece_forward_right_unchecked(self, value: usize) -> Self { - let not_king = !self.king_at_unchecked(value); - let board = self - .move_piece_forward_unchecked(value, 2) - .clear_piece((value + 1) & 31); - - const KING_MASK: u32 = 0b01000001000000000000010000010000; - if PossibleMoves::has_jumps(board.flip_turn()) - && not_king && (((1 << value) & KING_MASK) == 0) - { - board.flip_turn() - } else { - board - } - } - - /// Tries to move the piece backward and to the left, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// The space the piece jumps over is cleared - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the left side of the board results in undefined behavior. - /// Moving from the bottom of the board results in undefined behavior - pub const unsafe fn jump_piece_backward_left_unchecked(self, value: usize) -> Self { - let not_king = !self.king_at_unchecked(value); - let board = self - .move_piece_backward_unchecked(value, 2) - .clear_piece(value.wrapping_sub(1) & 31); - - const KING_MASK: u32 = 0b00000000000010000010000010000010; - if PossibleMoves::has_jumps(board.flip_turn()) - && not_king && (((1 << value) & KING_MASK) == 0) - { - board.flip_turn() - } else { - board - } - } - - /// Tries to move the piece backward and to the right, without checking if it's a legal move. - /// If a piece already exists there, then it will be overwritten - /// The space the piece jumps over is cleared - /// - /// # Arguments - /// - /// * `value` - The original location of the piece - /// - /// # Panics - /// - /// Panics if `value` is greater than or equal to 32 - /// - /// # Safety - /// - /// Moving from the right side of the board results in undefined behavior. - /// Moving from the bottom of the board results in undefined behavior - pub const unsafe fn jump_piece_backward_right_unchecked(self, value: usize) -> Self { - let not_king = !self.king_at_unchecked(value); - let board = self - .move_piece_backward_unchecked(value, 14) - .clear_piece(value.wrapping_sub(7) & 31); - - const KING_MASK: u32 = 0b00000000000010000010000010000010; - if PossibleMoves::has_jumps(board.flip_turn()) - && not_king && (((1 << value) & KING_MASK) == 0) - { - board.flip_turn() - } else { - board - } - } -} +use crate::possible_moves::PossibleMoves; +use crate::PieceColor; +#[cfg(feature = "serde")] +use serde::{Deserialize, Serialize}; +use std::hash::{Hash, Hasher}; + +#[cfg(test)] +mod tests; + +/// A checker board, +/// organized in the following structure: +/// ```txt +/// 11 05 31 25 +/// 10 04 30 24 +/// 03 29 23 17 +/// 02 28 22 16 +/// 27 21 15 09 +/// 26 20 14 08 +/// 19 13 07 01 +/// 18 12 06 00 +/// ``` +#[derive(Copy, Clone, Debug, Eq)] +#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] +pub struct CheckersBitBoard { + /// If the space contains a piece, it's a 1 + pieces: u32, + /// If the piece is black, 1, otherwise 0 + color: u32, + /// 1 if the piece is a king + kings: u32, + /// The player who has the next turn + turn: PieceColor, +} + +impl Default for CheckersBitBoard { + /// Returns the starting position + fn default() -> Self { + Self::starting_position() + } +} + +impl PartialEq for CheckersBitBoard { + fn eq(&self, other: &Self) -> bool { + self.pieces == other.pieces + && self.pieces & self.color == other.pieces & other.color + && self.pieces & self.kings == other.pieces & other.kings + && self.turn == other.turn + } +} + +impl Hash for CheckersBitBoard { + /// Hashes with only the pieces part, to ensure correctness and efficiency + fn hash(&self, hasher: &mut H) { + self.pieces.hash(hasher) + } +} + +impl CheckersBitBoard { + /// Creates a new Checkers BitBoard + /// + /// # Arguments + /// + /// * `pieces` - Each bit is 1 if the corresponding space contains a piece + /// * `color` - For each space with a piece, the value is 1 if it's dark, and 0 otherwise. + /// Bits for spaces without colors are undefined + /// * `kings` - For each space with a piece, the value is 1 if it's a king, and 0 otherwise. + /// Bits for spaces without colors are undefined + /// + /// # Example + /// + /// ``` + /// // This is the starting position + /// use model::{CheckersBitBoard, PieceColor}; + /// let board = CheckersBitBoard::new(0b11011111101111100111100111100111, + /// 0b00111100001100001100001111001111, + /// 0, + /// PieceColor::Dark); + /// ``` + pub const fn new(pieces: u32, color: u32, kings: u32, turn: PieceColor) -> Self { + Self { + pieces, + color, + kings, + turn, + } + } + + /// Creates a board at the starting position + pub const fn starting_position() -> Self { + const STARTING_BITBOARD: CheckersBitBoard = CheckersBitBoard::new( + 0b11100111100111100111110111111011, + 0b00001100001111001111001111000011, + 0, + PieceColor::Dark, + ); + STARTING_BITBOARD + } + + /// Gets the bits that represent where pieces are on the board + pub const fn pieces_bits(self) -> u32 { + self.pieces + } + + /// Gets the bits that represents the color of each piece on the board + /// + /// # Safety + /// + /// This is inherently unsafe, because this also returns the bits of empty squares + pub const fn color_bits(self) -> u32 { + self.color + } + + /// Gets the bits that represents the status of each piece on the board + /// + /// # Safety + /// + /// This is inherently unsafe, because this also returns the bits of empty squares + pub const fn king_bits(self) -> u32 { + self.kings + } + + /// The player whose turn it is + pub const fn turn(self) -> PieceColor { + self.turn + } + + /// Checks if there's a piece at the given space value + /// + /// # Arguments + /// + /// * `value` - The value of the space to check + /// + /// # Example + /// + /// ``` + /// use model::CheckersBitBoard; + /// let board = CheckersBitBoard::default(); + /// match board.piece_at(0) { + /// true => println!("There's a piece in the bottom right"), + /// false => println!("The bottom right is empty") + /// } + /// ``` + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + pub const fn piece_at(self, value: usize) -> bool { + ((self.pieces >> value) & 1) == 1 + } + + /// Checks the color at the piece in the given location, + /// without checking if there's a piece there + /// + /// # Arguments + /// + /// * `value` - The value of the space to check + /// + /// # Example + /// + /// ``` + /// use model::CheckersBitBoard; + /// use model::PieceColor; + /// let board = CheckersBitBoard::default(); + /// if board.piece_at(0) { + /// match unsafe {board.color_at_unchecked(0)} { + /// PieceColor::Dark => println!("The piece in the bottom right is dark colored"), + /// PieceColor::Light => println!("The piece in the bottom right is light colored") + /// } + /// } + /// ``` + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Checking the color at a square that is empty results in undefined behavior + pub const unsafe fn color_at_unchecked(self, value: usize) -> PieceColor { + if ((self.color >> value) & 1) != 0 { + PieceColor::Dark + } else { + PieceColor::Light + } + } + + /// Checks the color at the piece in the given location. + /// Returns `None` if there isn't a piece there + /// + /// # Arguments + /// + /// * `value` - The value of the space to check + /// + /// # Example + /// + /// ``` + /// use model::CheckersBitBoard; + /// use model::PieceColor; + /// let board = CheckersBitBoard::default(); + /// if let Some(color) = board.color_at(0) { + /// match color { + /// PieceColor::Dark => println!("The piece in the bottom right is dark colored"), + /// PieceColor::Light => println!("The piece in the bottom left is light colored") + /// } + /// } + /// ``` + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + pub const fn color_at(self, value: usize) -> Option { + if self.piece_at(value) { + // safety: if this block runs, then it's already confirmed a piece exists here + Some(unsafe { self.color_at_unchecked(value) }) + } else { + None + } + } + + /// Checks if the given location has a king, without checking if there's a piece there + /// + /// # Arguments + /// + /// * `value` - The value of the space to check + /// + /// # Example + /// + /// ``` + /// use model::CheckersBitBoard; + /// let board = CheckersBitBoard::default(); + /// if board.piece_at(0) { + /// match unsafe {board.king_at_unchecked(0)} { + /// true => println!("The piece in the bottom right is a king"), + /// false => println!("The piece in the bottom right is a peasant") + /// } + /// } + /// ``` + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Checking a square that is empty results in undefined behavior + pub const unsafe fn king_at_unchecked(self, value: usize) -> bool { + ((self.kings >> value) & 1) == 1 + } + + /// Checks if the piece in the given location is a king. + /// Returns `None` if there isn't a piece there + /// + /// # Arguments + /// + /// * `value` - The value of the space to check + /// + /// # Example + /// + /// ``` + /// use model::CheckersBitBoard; + /// let board = CheckersBitBoard::default(); + /// if let Some(status) = board.king_at(0) { + /// match status { + /// true => println!("The piece in the bottom right is a king"), + /// false => println!("The piece in the bottom right is a peasant") + /// } + /// } + /// ``` + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + pub const fn king_at(self, value: usize) -> Option { + if self.piece_at(value) { + // safety: if this block runs, then it's already confirmed a piece exists here + Some(unsafe { self.king_at_unchecked(value) }) + } else { + None + } + } + + pub const fn flip_turn(self) -> Self { + CheckersBitBoard::new(self.pieces, self.color, self.kings, self.turn.flip()) + } + + /// Moves a piece from `start` to `dest`. The original location will be empty. + /// This does not mutate the original board. + /// If a piece already exists at `dest`, it will be overwritten. + /// + /// # Arguments + /// + /// * `start` - The original location of the piece + /// * `dest` - The new location + /// + /// # Panics + /// + /// Panics if `start` or `dest` is greater than or equal to 32 + /// + /// # Safety + /// + /// Results in undefined behavior if `start` does not contain a piece + pub const unsafe fn move_piece_to_unchecked(self, start: usize, dest: usize) -> Self { + // Clears the bit at the starting value + // Sets the bit at the destination value + let pieces = (self.pieces & !(1 << start)) | (1 << dest); + + // Clears the bit at the destination value + // Sets the value at the destination to the value of the start + let color = (self.color & !(1 << dest)) | (((self.color >> start) & 1) << dest); + + // The squares where certain pieces should be promoted + const DARK_PROMOTION_MASK: u32 = 0b10000010000000000000100000100000; + const LIGHT_PROMOTION_MASK: u32 = 0b1000001000001000001; + + // Clears the bit at the destination value + // Sets the value at the destination to the value of the start + // Promotes if the end of the board was reached + let kings = (self.kings & !(1 << dest)) + | (((self.kings >> start) & 1) << dest) + | (self.color & DARK_PROMOTION_MASK) + | (!self.color & LIGHT_PROMOTION_MASK); + + let turn = self.turn.flip(); + + CheckersBitBoard::new(pieces, color, kings, turn) + } + + /// Moves a piece from `value` to `(value + amount) % 32`. The original location will be empty. + /// This does not mutate the original board + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// * `amount` - The amount to shift the location by + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32, + /// or `value + amount` is greater than `usize::MAX` + /// + /// # Safety + /// + /// This results in undefined behavior if `value` does not contain a piece + const unsafe fn move_piece_forward_unchecked(self, value: usize, amount: usize) -> Self { + self.move_piece_to_unchecked(value, (value + amount) & 31) + } + + /// Moves a piece from `value` to `(value - amount) % 32`. The original location will be empty. + /// This does not mutate the original board. + /// If a piece already exists there, then it will be overwritten + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// * `amount` - The amount to shift the location by + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// This results in undefined behavior if `value` does not contain a piece + const unsafe fn move_piece_backward_unchecked(self, value: usize, amount: usize) -> Self { + self.move_piece_to_unchecked(value, value.wrapping_sub(amount) & 31) + } + + /// Tries to move the piece forward and to the left, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the left side of the board results in undefined behavior. + /// Moving from the top of the board results in undefined behavior. + /// A `value` which doesn't contain a piece results in undefined behavior. + pub const unsafe fn move_piece_forward_left_unchecked(self, value: usize) -> Self { + self.move_piece_forward_unchecked(value, 7) + } + + /// Tries to move the piece forward and to the right, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the right side of the board results in undefined behavior. + /// Moving from the top of the board results in undefined behavior. + /// A `value` which doesn't contain a piece results in undefined behavior. + pub const unsafe fn move_piece_forward_right_unchecked(self, value: usize) -> Self { + self.move_piece_forward_unchecked(value, 1) + } + + /// Tries to move the piece backward and to the left, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the left side of the board results in undefined behavior. + /// Moving from the bottom of the board results in undefined behavior. + /// A `value` which doesn't contain a piece results in undefined behavior. + pub const unsafe fn move_piece_backward_left_unchecked(self, value: usize) -> Self { + self.move_piece_backward_unchecked(value, 1) + } + + /// Tries to move the piece backward and to the right, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the right side of the board results in undefined behavior. + /// Moving from the bottom of the board results in undefined behavior. + /// A `value` which doesn't contain a piece results in undefined behavior. + pub const unsafe fn move_piece_backward_right_unchecked(self, value: usize) -> Self { + self.move_piece_backward_unchecked(value, 7) + } + + /// Clears a space on the board. If the space is empty, then this function does nothing. + /// + /// # Arguments + /// + /// * `value` - The value of the space to clear + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + pub const fn clear_piece(self, value: usize) -> Self { + let pieces = self.pieces & !(1 << value); + CheckersBitBoard::new(pieces, self.color, self.kings, self.turn) + } + + /// Tries to jump the piece forward and to the left, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten. + /// The space the piece jumps over is cleared + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the left side of the board results in undefined behavior. + /// Moving from the top of the board results in undefined behavior + pub const unsafe fn jump_piece_forward_left_unchecked(self, value: usize) -> Self { + let not_king = !self.king_at_unchecked(value); + let board = self + .move_piece_forward_unchecked(value, 14) + .clear_piece((value + 7) & 31); + + const KING_MASK: u32 = 0b01000001000000000000010000010000; + if PossibleMoves::has_jumps(board.flip_turn()) + && not_king && (((1 << value) & KING_MASK) == 0) + { + board.flip_turn() + } else { + board + } + } + + /// Tries to move the piece forward and to the right, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// The space the piece jumps over is cleared + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the right side of the board results in undefined behavior. + /// Moving from the top of the board results in undefined behavior + pub const unsafe fn jump_piece_forward_right_unchecked(self, value: usize) -> Self { + let not_king = !self.king_at_unchecked(value); + let board = self + .move_piece_forward_unchecked(value, 2) + .clear_piece((value + 1) & 31); + + const KING_MASK: u32 = 0b01000001000000000000010000010000; + if PossibleMoves::has_jumps(board.flip_turn()) + && not_king && (((1 << value) & KING_MASK) == 0) + { + board.flip_turn() + } else { + board + } + } + + /// Tries to move the piece backward and to the left, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// The space the piece jumps over is cleared + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the left side of the board results in undefined behavior. + /// Moving from the bottom of the board results in undefined behavior + pub const unsafe fn jump_piece_backward_left_unchecked(self, value: usize) -> Self { + let not_king = !self.king_at_unchecked(value); + let board = self + .move_piece_backward_unchecked(value, 2) + .clear_piece(value.wrapping_sub(1) & 31); + + const KING_MASK: u32 = 0b00000000000010000010000010000010; + if PossibleMoves::has_jumps(board.flip_turn()) + && not_king && (((1 << value) & KING_MASK) == 0) + { + board.flip_turn() + } else { + board + } + } + + /// Tries to move the piece backward and to the right, without checking if it's a legal move. + /// If a piece already exists there, then it will be overwritten + /// The space the piece jumps over is cleared + /// + /// # Arguments + /// + /// * `value` - The original location of the piece + /// + /// # Panics + /// + /// Panics if `value` is greater than or equal to 32 + /// + /// # Safety + /// + /// Moving from the right side of the board results in undefined behavior. + /// Moving from the bottom of the board results in undefined behavior + pub const unsafe fn jump_piece_backward_right_unchecked(self, value: usize) -> Self { + let not_king = !self.king_at_unchecked(value); + let board = self + .move_piece_backward_unchecked(value, 14) + .clear_piece(value.wrapping_sub(7) & 31); + + const KING_MASK: u32 = 0b00000000000010000010000010000010; + if PossibleMoves::has_jumps(board.flip_turn()) + && not_king && (((1 << value) & KING_MASK) == 0) + { + board.flip_turn() + } else { + board + } + } +} diff --git a/model/src/board/tests.rs b/model/src/board/tests.rs index 2afe1da..0de12d5 100644 --- a/model/src/board/tests.rs +++ b/model/src/board/tests.rs @@ -538,6 +538,7 @@ fn test_move_piece_to_default_board() { assert!(board.piece_at(5)); assert_eq!(board.color_at(5).unwrap(), PieceColor::Light); assert!(!board.king_at(5).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -548,6 +549,7 @@ fn test_move_piece_forward_standard() { assert!(board.piece_at(16)); assert_eq!(board.color_at(16).unwrap(), PieceColor::Light); assert!(!board.king_at(16).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -558,6 +560,21 @@ fn test_move_piece_forward_wrap() { assert!(board.piece_at(9)); assert_eq!(board.color_at(9).unwrap(), PieceColor::Dark); assert!(!board.king_at(9).unwrap()); + assert_eq!(board.turn, PieceColor::Light); +} + +#[test] +fn test_move_piece_forward_left_to_king() { + let board = CheckersBitBoard::new(0b10000, 0b10000, 0, PieceColor::Dark); + let board = unsafe { board.move_piece_forward_left_unchecked(4) }; + assert!(board.king_at(5)); +} + +#[test] +fn test_move_piece_backward_left_to_king() { + let board = CheckersBitBoard::new(0b10, 0, 0, PieceColor::Dark); + let board = unsafe { board.move_piece_backward_left_unchecked(1) }; + assert!(board.king_at(0)); } #[test] @@ -568,6 +585,7 @@ fn test_move_piece_backward_standard() { assert!(board.piece_at(15)); assert_eq!(board.color_at(15).unwrap(), PieceColor::Dark); assert!(!board.king_at(15).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -578,6 +596,7 @@ fn test_move_piece_backward_wrap() { assert!(board.piece_at(28)); assert_eq!(board.color_at(28).unwrap(), PieceColor::Light); assert!(!board.king_at(28).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -596,6 +615,7 @@ fn test_jump_forward_left_specific() { assert!(board2.piece_at(14)); assert_eq!(board2.color_at(14).unwrap(), board.color_at(0).unwrap()); assert_eq!(board2.king_at(14).unwrap(), board.king_at(0).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -613,6 +633,7 @@ fn test_jump_forward_right_specific() { assert!(board2.piece_at(20)); assert_eq!(board2.color_at(20).unwrap(), board.color_at(18).unwrap()); assert_eq!(board2.king_at(20).unwrap(), board.king_at(18).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -630,6 +651,7 @@ fn test_jump_backward_left_specific() { assert!(board2.piece_at(23)); assert_eq!(board2.color_at(23).unwrap(), board.color_at(25).unwrap()); assert_eq!(board2.king_at(23).unwrap(), board.king_at(25).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] @@ -647,6 +669,7 @@ fn test_jump_backward_right_specific() { assert!(board2.piece_at(29)); assert_eq!(board2.color_at(29).unwrap(), board.color_at(11).unwrap()); assert_eq!(board2.king_at(29).unwrap(), board.king_at(11).unwrap()); + assert_eq!(board.turn, PieceColor::Light); } #[test] diff --git a/model/src/color.rs b/model/src/color.rs index 3dd2a64..c223c11 100644 --- a/model/src/color.rs +++ b/model/src/color.rs @@ -1,57 +1,94 @@ -#[cfg(feature = "serde")] -use serde::{Deserialize, Serialize}; -use std::fmt::Display; - -/// The color of a piece -#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)] -#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] -pub enum PieceColor { - Light, - Dark, -} - -impl Display for PieceColor { - fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { - write!( - f, - "{}", - match self { - Self::Light => "Light", - Self::Dark => "Dark", - } - ) - } -} - -impl PieceColor { - pub const fn flip(self) -> Self { - // TODO optimize - match self { - PieceColor::Light => PieceColor::Dark, - PieceColor::Dark => PieceColor::Light, - } - } - - pub const fn flip_if(self, statement: bool) -> Self { - if statement { - self.flip() - } else { - self - } - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn light_display() { - assert_eq!(PieceColor::Light.to_string(), "Light"); - } - - #[test] - fn dark_display() { - assert_eq!(PieceColor::Dark.to_string(), "Dark"); - } -} +#[cfg(feature = "serde")] +use serde::{Deserialize, Serialize}; +use std::fmt::Display; + +/// The color of a piece +#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)] +#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))] +pub enum PieceColor { + Light, + Dark, +} + +impl Display for PieceColor { + fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { + write!( + f, + "{}", + match self { + Self::Light => "Light", + Self::Dark => "Dark", + } + ) + } +} + +impl PieceColor { + /// Flips the color + pub const fn flip(self) -> Self { + // TODO optimize + match self { + PieceColor::Light => PieceColor::Dark, + PieceColor::Dark => PieceColor::Light, + } + } + + /// Flips the color if the statement is true + /// + /// # Arguments + /// + /// * `statement` - Flips the color if true + pub const fn flip_if(self, statement: bool) -> Self { + if statement { + self.flip() + } else { + self + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn light_display() { + assert_eq!(PieceColor::Light.to_string(), "Light"); + } + + #[test] + fn dark_display() { + assert_eq!(PieceColor::Dark.to_string(), "Dark"); + } + + #[test] + fn flip() { + let light = PieceColor::Light; + let dark = PieceColor::Dark; + assert_eq!(light.flip(), dark); + assert_eq!(dark.flip(), light); + } + + #[test] + fn flip_if() { + let light = PieceColor::Light; + let dark = PieceColor::Dark; + + assert_eq!(light.flip_if(true), dark); + assert_eq!(light.flip_if(false), light); + assert_eq!(dark.flip_if(true), light); + assert_eq!(dark.flip_if(false), dark); + } + + #[test] + fn test_send() { + fn assert_send() {} + assert_send::(); + } + + #[test] + fn test_sync() { + fn assert_sync() {} + assert_sync::(); + } +} diff --git a/model/src/moves.rs b/model/src/moves.rs index 30024d6..626d85a 100644 --- a/model/src/moves.rs +++ b/model/src/moves.rs @@ -1,59 +1,89 @@ -use crate::CheckersBitBoard; - -#[derive(Copy, Clone, Eq, PartialEq)] -pub enum MoveDirection { - ForwardLeft = 0, - ForwardRight = 1, - BackwardLeft = 2, - BackwardRight = 3, -} - -#[derive(Copy, Clone)] -pub struct Move { - start: u32, - direction: MoveDirection, - jump: bool, -} - -impl Move { - pub const fn new(start: usize, direction: MoveDirection, jump: bool) -> Self { - Self { - start: start as u32, - direction, - jump, - } - } - - pub const unsafe fn apply_to(self, board: CheckersBitBoard) -> CheckersBitBoard { - match self.jump { - false => match self.direction { - MoveDirection::ForwardLeft => { - board.move_piece_forward_left_unchecked(self.start as usize) - } - MoveDirection::ForwardRight => { - board.move_piece_forward_right_unchecked(self.start as usize) - } - MoveDirection::BackwardLeft => { - board.move_piece_backward_left_unchecked(self.start as usize) - } - MoveDirection::BackwardRight => { - board.move_piece_backward_right_unchecked(self.start as usize) - } - }, - true => match self.direction { - MoveDirection::ForwardLeft => { - board.jump_piece_forward_left_unchecked(self.start as usize) - } - MoveDirection::ForwardRight => { - board.jump_piece_forward_right_unchecked(self.start as usize) - } - MoveDirection::BackwardLeft => { - board.jump_piece_backward_left_unchecked(self.start as usize) - } - MoveDirection::BackwardRight => { - board.jump_piece_backward_right_unchecked(self.start as usize) - } - }, - } - } -} +use crate::CheckersBitBoard; + +#[derive(Copy, Clone, Eq, PartialEq)] +pub enum MoveDirection { + ForwardLeft = 0, + ForwardRight = 1, + BackwardLeft = 2, + BackwardRight = 3, +} + +/// A checkers move +#[derive(Copy, Clone)] +pub struct Move { + /// The position of the piece to move + start: u32, + + /// The direction to move to + direction: MoveDirection, + + /// Whether or not it's a jump + jump: bool, +} + +impl Move { + /// Create a new move + /// + /// # Arguments + /// + /// * `start` - The location of the piece that should move + /// * `direction` - The direction the piece should move in + /// * `jump` - Whether or not the piece should jump + pub const fn new(start: usize, direction: MoveDirection, jump: bool) -> Self { + Self { + start: start as u32, + direction, + jump, + } + } + + /// Apply the move to a board. This does not mutate the original board, + /// but instead returns a new one. + /// + /// # Arguments + /// + /// * `board` - The board to apply the move to + /// + /// # Panics + /// + /// Panics if the starting position of this move is greater than or equal to 32 + /// + /// # Safety + /// + /// Applying an illegal move to the board is undefined behavior. + /// This functions results in undefined behavior if: + /// * The piece moves in a direction which would move it outside of the board + /// * The starting position of this move doesn't contain a piece + pub const unsafe fn apply_to(self, board: CheckersBitBoard) -> CheckersBitBoard { + match self.jump { + false => match self.direction { + MoveDirection::ForwardLeft => { + board.move_piece_forward_left_unchecked(self.start as usize) + } + MoveDirection::ForwardRight => { + board.move_piece_forward_right_unchecked(self.start as usize) + } + MoveDirection::BackwardLeft => { + board.move_piece_backward_left_unchecked(self.start as usize) + } + MoveDirection::BackwardRight => { + board.move_piece_backward_right_unchecked(self.start as usize) + } + }, + true => match self.direction { + MoveDirection::ForwardLeft => { + board.jump_piece_forward_left_unchecked(self.start as usize) + } + MoveDirection::ForwardRight => { + board.jump_piece_forward_right_unchecked(self.start as usize) + } + MoveDirection::BackwardLeft => { + board.jump_piece_backward_left_unchecked(self.start as usize) + } + MoveDirection::BackwardRight => { + board.jump_piece_backward_right_unchecked(self.start as usize) + } + }, + } + } +} diff --git a/model/src/moves_iter.rs b/model/src/moves_iter.rs index 307ee96..ffa59b6 100644 --- a/model/src/moves_iter.rs +++ b/model/src/moves_iter.rs @@ -1,143 +1,144 @@ -use crate::moves::{Move, MoveDirection}; -use crate::possible_moves::PossibleMoves; - -const FORWARD_LEFT_SLIDE_SQUARES: [usize; 33] = [ - 1, 3, 3, 4, 6, 6, 7, 8, 9, 12, 12, 12, 13, 14, 15, 16, 17, 19, 19, 20, 21, 22, 23, 24, 27, 27, - 27, 28, 29, 30, 32, 32, 32, -]; -const FORWARD_RIGHT_SLIDE_SQUARES: [usize; 33] = [ - 2, 2, 3, 4, 6, 6, 7, 8, 10, 10, 12, 12, 13, 14, 15, 16, 18, 18, 19, 20, 21, 22, 23, 24, 26, 26, - 27, 28, 29, 30, 32, 32, 32, -]; -const BACKWARD_LEFT_SLIDE_SQUARES: [usize; 33] = [ - 1, 3, 3, 4, 5, 7, 7, 8, 9, 11, 11, 13, 13, 14, 15, 16, 17, 19, 19, 20, 21, 22, 23, 24, 25, 27, - 27, 28, 29, 30, 31, 32, 32, -]; -const BACKWARD_RIGHT_SLIDE_SQUARES: [usize; 33] = [ - 2, 2, 3, 4, 5, 7, 7, 8, 10, 10, 11, 13, 13, 14, 15, 16, 19, 19, 19, 20, 21, 22, 23, 24, 26, 26, - 27, 28, 29, 30, 31, 32, 32, -]; - -const FORWARD_LEFT_JUMP_SQUARES: [usize; 33] = [ - 1, 6, 6, 6, 6, 6, 7, 8, 9, 12, 12, 12, 13, 14, 15, 16, 17, 20, 20, 20, 21, 22, 23, 28, 28, 28, - 28, 28, 29, 32, 32, 32, 32, -]; -const FORWARD_RIGHT_JUMP_SQUARES: [usize; 33] = [ - 2, 2, 3, 6, 6, 6, 7, 12, 12, 12, 12, 12, 13, 14, 15, 18, 18, 18, 19, 20, 21, 22, 23, 26, 26, - 26, 27, 28, 29, 32, 32, 32, 32, -]; -const BACKWARD_LEFT_JUMP_SQUARES: [usize; 33] = [ - 4, 4, 4, 4, 5, 8, 8, 8, 9, 14, 14, 14, 14, 14, 15, 16, 17, 20, 20, 20, 21, 22, 23, 24, 25, 28, - 28, 28, 29, 30, 31, 32, 32, -]; -const BACKWARD_RIGHT_JUMP_SQUARES: [usize; 33] = [ - 2, 2, 3, 4, 5, 10, 10, 10, 10, 10, 11, 14, 14, 14, 15, 20, 20, 20, 20, 20, 21, 22, 23, 26, 26, - 26, 27, 28, 29, 30, 31, 32, 32, -]; - -static SLIDE_ARRAYS: [[usize; 33]; 4] = [ - FORWARD_LEFT_SLIDE_SQUARES, - FORWARD_RIGHT_SLIDE_SQUARES, - BACKWARD_LEFT_SLIDE_SQUARES, - BACKWARD_RIGHT_SLIDE_SQUARES, -]; - -static JUMP_ARRAYS: [[usize; 33]; 4] = [ - FORWARD_LEFT_JUMP_SQUARES, - FORWARD_RIGHT_JUMP_SQUARES, - BACKWARD_LEFT_JUMP_SQUARES, - BACKWARD_RIGHT_JUMP_SQUARES, -]; - -pub struct PossibleMovesIter { - possible_moves: PossibleMoves, - current_square: usize, - current_direction: MoveDirection, - movers: u32, - squares: &'static [usize; 33], -} - -impl From for PossibleMovesIter { - fn from(possible_moves: PossibleMoves) -> Self { - Self { - possible_moves, - current_square: 0, - current_direction: MoveDirection::ForwardLeft, - movers: possible_moves.forward_left_bits(), - squares: unsafe { - if possible_moves.can_jump() { - JUMP_ARRAYS.get_unchecked(0) - } else { - SLIDE_ARRAYS.get_unchecked(0) - } - }, - } - } -} - -impl Iterator for PossibleMovesIter { - type Item = Move; - - fn next(&mut self) -> Option { - loop { - if self.current_square == 32 { - if self.current_direction != MoveDirection::BackwardRight { - self.current_square = 0; - // safety: only results in undefined variant if equal to backward right - // this has already been checked for - self.current_direction = - unsafe { std::mem::transmute((self.current_direction as u8) + 1) }; - self.movers = self - .possible_moves - .get_direction_bits(self.current_direction); - - // safety: the max value of the enum is 3 - unsafe { - self.squares = &*(self.squares as *const [usize; 33]).add(1); - } - } else { - return None; - } - } - - if (self.movers >> self.current_square) & 1 != 0 { - let next_move = Move::new( - self.current_square, - self.current_direction, - self.possible_moves.can_jump(), - ); - - // safety: self.current_square will never be > 32 - // squares does not contain such a value - unsafe { - self.current_square = *self.squares.get_unchecked(self.current_square); - } - - return Some(next_move); - } - - if self.current_square != 32 { - // safety: self.current_square will never be > 32 - // squares does not contain such a value - unsafe { - self.current_square = *self.squares.get_unchecked(self.current_square); - } - } - } - } - - fn size_hint(&self) -> (usize, Option) { - ( - 0, - Some( - (32 - self.current_square) - + 32 * match self.current_direction { - MoveDirection::ForwardLeft => 3, - MoveDirection::ForwardRight => 2, - MoveDirection::BackwardLeft => 1, - MoveDirection::BackwardRight => 0, - }, - ), - ) - } -} +use crate::moves::{Move, MoveDirection}; +use crate::possible_moves::PossibleMoves; + +const FORWARD_LEFT_SLIDE_SQUARES: [usize; 33] = [ + 1, 3, 3, 4, 6, 6, 7, 8, 9, 12, 12, 12, 13, 14, 15, 16, 17, 19, 19, 20, 21, 22, 23, 24, 27, 27, + 27, 28, 29, 30, 32, 32, 32, +]; +const FORWARD_RIGHT_SLIDE_SQUARES: [usize; 33] = [ + 2, 2, 3, 4, 6, 6, 7, 8, 10, 10, 12, 12, 13, 14, 15, 16, 18, 18, 19, 20, 21, 22, 23, 24, 26, 26, + 27, 28, 29, 30, 32, 32, 32, +]; +const BACKWARD_LEFT_SLIDE_SQUARES: [usize; 33] = [ + 1, 3, 3, 4, 5, 7, 7, 8, 9, 11, 11, 13, 13, 14, 15, 16, 17, 19, 19, 20, 21, 22, 23, 24, 25, 27, + 27, 28, 29, 30, 31, 32, 32, +]; +const BACKWARD_RIGHT_SLIDE_SQUARES: [usize; 33] = [ + 2, 2, 3, 4, 5, 7, 7, 8, 10, 10, 11, 13, 13, 14, 15, 16, 19, 19, 19, 20, 21, 22, 23, 24, 26, 26, + 27, 28, 29, 30, 31, 32, 32, +]; + +const FORWARD_LEFT_JUMP_SQUARES: [usize; 33] = [ + 1, 6, 6, 6, 6, 6, 7, 8, 9, 12, 12, 12, 13, 14, 15, 16, 17, 20, 20, 20, 21, 22, 23, 28, 28, 28, + 28, 28, 29, 32, 32, 32, 32, +]; +const FORWARD_RIGHT_JUMP_SQUARES: [usize; 33] = [ + 2, 2, 3, 6, 6, 6, 7, 12, 12, 12, 12, 12, 13, 14, 15, 18, 18, 18, 19, 20, 21, 22, 23, 26, 26, + 26, 27, 28, 29, 32, 32, 32, 32, +]; +const BACKWARD_LEFT_JUMP_SQUARES: [usize; 33] = [ + 4, 4, 4, 4, 5, 8, 8, 8, 9, 14, 14, 14, 14, 14, 15, 16, 17, 20, 20, 20, 21, 22, 23, 24, 25, 28, + 28, 28, 29, 30, 31, 32, 32, +]; +const BACKWARD_RIGHT_JUMP_SQUARES: [usize; 33] = [ + 2, 2, 3, 4, 5, 10, 10, 10, 10, 10, 11, 14, 14, 14, 15, 20, 20, 20, 20, 20, 21, 22, 23, 26, 26, + 26, 27, 28, 29, 30, 31, 32, 32, +]; + +static SLIDE_ARRAYS: [[usize; 33]; 4] = [ + FORWARD_LEFT_SLIDE_SQUARES, + FORWARD_RIGHT_SLIDE_SQUARES, + BACKWARD_LEFT_SLIDE_SQUARES, + BACKWARD_RIGHT_SLIDE_SQUARES, +]; + +static JUMP_ARRAYS: [[usize; 33]; 4] = [ + FORWARD_LEFT_JUMP_SQUARES, + FORWARD_RIGHT_JUMP_SQUARES, + BACKWARD_LEFT_JUMP_SQUARES, + BACKWARD_RIGHT_JUMP_SQUARES, +]; + +pub struct PossibleMovesIter { + possible_moves: PossibleMoves, + current_square: usize, + current_direction: MoveDirection, + movers: u32, + squares: &'static [usize; 33], +} + +impl From for PossibleMovesIter { + fn from(possible_moves: PossibleMoves) -> Self { + Self { + possible_moves, + current_square: 0, + current_direction: MoveDirection::ForwardLeft, + movers: possible_moves.forward_left_bits(), + squares: unsafe { + if possible_moves.can_jump() { + JUMP_ARRAYS.get_unchecked(0) + } else { + SLIDE_ARRAYS.get_unchecked(0) + } + }, + } + } +} + +impl Iterator for PossibleMovesIter { + type Item = Move; + + fn next(&mut self) -> Option { + loop { + if self.current_square == 32 { + if self.current_direction != MoveDirection::BackwardRight { + self.current_square = 0; + // safety: only results in undefined variant if equal to backward right + // this has already been checked for + self.current_direction = + unsafe { std::mem::transmute((self.current_direction as u8) + 1) }; + self.movers = self + .possible_moves + .get_direction_bits(self.current_direction); + + // safety: this iterator stops returning values before this + // can result in undefined behavior + unsafe { + self.squares = &*(self.squares as *const [usize; 33]).add(1); + } + } else { + return None; + } + } + + if (self.movers >> self.current_square) & 1 != 0 { + let next_move = Move::new( + self.current_square, + self.current_direction, + self.possible_moves.can_jump(), + ); + + // safety: self.current_square will never be > 32 + // squares does not contain such a value + unsafe { + self.current_square = *self.squares.get_unchecked(self.current_square); + } + + return Some(next_move); + } + + if self.current_square != 32 { + // safety: self.current_square will never be > 32 + // squares does not contain such a value + unsafe { + self.current_square = *self.squares.get_unchecked(self.current_square); + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + ( + 0, + Some( + (32 - self.current_square) + + 32 * match self.current_direction { + MoveDirection::ForwardLeft => 3, + MoveDirection::ForwardRight => 2, + MoveDirection::BackwardLeft => 1, + MoveDirection::BackwardRight => 0, + }, + ), + ) + } +} diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs index 7d4ac29..8c25520 100644 --- a/model/src/possible_moves.rs +++ b/model/src/possible_moves.rs @@ -1,326 +1,345 @@ -use crate::moves::{Move, MoveDirection}; -use crate::moves_iter::PossibleMovesIter; -use crate::{CheckersBitBoard, PieceColor}; - -#[derive(Copy, Clone, Debug)] -pub struct PossibleMoves { - forward_left_movers: u32, - forward_right_movers: u32, - backward_left_movers: u32, - backward_right_movers: u32, - jump: bool, -} - -impl IntoIterator for PossibleMoves { - type Item = Move; - type IntoIter = PossibleMovesIter; - - fn into_iter(self) -> Self::IntoIter { - self.into() - } -} - -impl PossibleMoves { - const fn slides_dark(board: CheckersBitBoard) -> Self { - const FORWARD_LEFT_MASK: u32 = 0b01111001111110111111001111011011; - const FORWARD_RIGHT_MASK: u32 = 0b01111101111111011111010111011101; - const BACKWARD_LEFT_MASK: u32 = 0b11111011111110111110101110111010; - const BACKWARD_RIGHT_MASK: u32 = 0b11111001111110011110110110111100; - - let not_occupied = !board.pieces_bits(); - let friendly_pieces = board.pieces_bits() & board.color_bits(); - let friendly_kings = friendly_pieces & board.king_bits(); - - let forward_left_movers = - not_occupied.rotate_right(7) & friendly_pieces & FORWARD_LEFT_MASK; - let forward_right_movers = - not_occupied.rotate_right(1) & friendly_pieces & FORWARD_RIGHT_MASK; - let backward_left_movers; - let backward_right_movers; - - if friendly_kings > 0 { - backward_left_movers = - not_occupied.rotate_left(1) & friendly_kings & BACKWARD_LEFT_MASK; - backward_right_movers = - not_occupied.rotate_left(7) & friendly_kings & BACKWARD_RIGHT_MASK; - } else { - backward_left_movers = 0; - backward_right_movers = 0; - } - - Self { - forward_left_movers, - forward_right_movers, - backward_left_movers, - backward_right_movers, - jump: false, - } - } - - const fn slides_light(board: CheckersBitBoard) -> Self { - const FORWARD_LEFT_MASK: u32 = 0b01111001111110111111001111011011; - const FORWARD_RIGHT_MASK: u32 = 0b01111101111111011111010111011101; - const BACKWARD_LEFT_MASK: u32 = 0b11111011111110111110101110111010; - const BACKWARD_RIGHT_MASK: u32 = 0b11111001111110011110110110111100; - - let not_occupied = !board.pieces_bits(); - let friendly_pieces = board.pieces_bits() & !board.color_bits(); - let friendly_kings = friendly_pieces & board.king_bits(); - - let backward_left_movers = - not_occupied.rotate_left(1) & friendly_pieces & BACKWARD_LEFT_MASK; - let backward_right_movers = - not_occupied.rotate_left(7) & friendly_pieces & BACKWARD_RIGHT_MASK; - let forward_left_movers; - let forward_right_movers; - - if friendly_kings > 0 { - forward_left_movers = not_occupied.rotate_right(7) & friendly_kings & FORWARD_LEFT_MASK; - forward_right_movers = - not_occupied.rotate_right(1) & friendly_kings & FORWARD_RIGHT_MASK; - } else { - forward_left_movers = 0; - forward_right_movers = 0; - } - - Self { - forward_left_movers, - forward_right_movers, - backward_left_movers, - backward_right_movers, - jump: false, - } - } - - const fn jumps_dark(board: CheckersBitBoard) -> Self { - const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; - const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; - const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; - const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; - - let not_occupied = !board.pieces_bits(); - let enemy_pieces = board.pieces_bits() & !board.color_bits(); - let friendly_pieces = board.pieces_bits() & board.color_bits(); - let friendly_kings = friendly_pieces & board.king_bits(); - - let forward_left_movers = not_occupied.rotate_right(14) - & enemy_pieces.rotate_right(7) - & friendly_pieces - & FORWARD_LEFT_MASK; - let forward_right_movers = not_occupied.rotate_right(2) - & enemy_pieces.rotate_right(1) - & friendly_pieces - & FORWARD_RIGHT_MASK; - let backward_left_movers; - let backward_right_movers; - - if friendly_kings > 0 { - backward_left_movers = not_occupied.rotate_left(2) - & enemy_pieces.rotate_left(1) - & friendly_kings & BACKWARD_LEFT_MASK; - backward_right_movers = not_occupied.rotate_left(14) - & enemy_pieces.rotate_left(7) - & friendly_kings & BACKWARD_RIGHT_MASK; - } else { - backward_left_movers = 0; - backward_right_movers = 0; - } - - Self { - forward_left_movers, - forward_right_movers, - backward_left_movers, - backward_right_movers, - jump: true, - } - } - - const fn jumps_light(board: CheckersBitBoard) -> Self { - const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; - const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; - const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; - const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; - - let not_occupied = !board.pieces_bits(); - let enemy_pieces = board.pieces_bits() & board.color_bits(); - let friendly_pieces = board.pieces_bits() & !board.color_bits(); - let friendly_kings = friendly_pieces & board.king_bits(); - - let backward_left_movers = not_occupied.rotate_left(2) - & enemy_pieces.rotate_left(1) - & friendly_pieces - & BACKWARD_LEFT_MASK; - let backward_right_movers = not_occupied.rotate_left(14) - & enemy_pieces.rotate_left(7) - & friendly_pieces - & BACKWARD_RIGHT_MASK; - let forward_left_movers; - let forward_right_movers; - - if friendly_kings > 0 { - forward_left_movers = not_occupied.rotate_right(14) - & enemy_pieces.rotate_right(7) - & friendly_kings & FORWARD_LEFT_MASK; - forward_right_movers = not_occupied.rotate_right(2) - & enemy_pieces.rotate_right(1) - & friendly_kings & FORWARD_RIGHT_MASK; - } else { - forward_left_movers = 0; - forward_right_movers = 0; - } - - Self { - forward_left_movers, - forward_right_movers, - backward_left_movers, - backward_right_movers, - jump: true, - } - } - - pub const fn has_jumps_dark(board: CheckersBitBoard) -> bool { - const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; - const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; - const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; - const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; - - let not_occupied = !board.pieces_bits(); - let enemy_pieces = board.pieces_bits() & !board.color_bits(); - let friendly_pieces = board.pieces_bits() & board.color_bits(); - - let forward_left_spaces = - not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK; - let forward_right_spaces = - not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK; - - let forward_spaces = forward_left_spaces | forward_right_spaces; - - if board.king_bits() > 0 { - let backward_left_spaces = - not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK; - let backward_right_spaces = - not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK; - let backward_spaces = backward_left_spaces | backward_right_spaces; - - let forward_spaces = board.king_bits() & backward_spaces; - friendly_pieces & (forward_spaces | backward_spaces) != 0 - } else { - friendly_pieces & forward_spaces != 0 - } - } - - pub const fn has_jumps_light(board: CheckersBitBoard) -> bool { - const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; - const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; - const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; - const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; - - let not_occupied = !board.pieces_bits(); - let enemy_pieces = board.pieces_bits() & board.color_bits(); - let friendly_pieces = board.pieces_bits() & !board.color_bits(); - - let backward_left_spaces = - not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK; - let backward_right_spaces = - not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK; - - let backward_spaces = backward_left_spaces | backward_right_spaces; - - if board.king_bits() > 0 { - let forward_left_spaces = - not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK; - let forward_right_spaces = - not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK; - let forward_spaces = forward_left_spaces | forward_right_spaces; - - let forward_spaces = board.king_bits() & forward_spaces; - friendly_pieces & (forward_spaces | backward_spaces) != 0 - } else { - friendly_pieces & backward_spaces != 0 - } - } - - #[inline(always)] - pub const fn has_jumps(board: CheckersBitBoard) -> bool { - match board.turn() { - PieceColor::Light => Self::has_jumps_light(board), - PieceColor::Dark => Self::has_jumps_dark(board), - } - } - - const fn light_moves(board: CheckersBitBoard) -> Self { - let jumps = Self::jumps_light(board); - if jumps.is_empty() { - Self::slides_light(board) - } else { - jumps - } - } - - const fn dark_moves(board: CheckersBitBoard) -> Self { - let jumps = Self::jumps_dark(board); - if jumps.is_empty() { - Self::slides_dark(board) - } else { - jumps - } - } - - pub const fn moves(board: CheckersBitBoard) -> Self { - match board.turn() { - PieceColor::Dark => Self::dark_moves(board), - PieceColor::Light => Self::light_moves(board), - } - } - - pub const fn is_empty(self) -> bool { - (self.backward_left_movers - | self.forward_left_movers - | self.forward_right_movers - | self.backward_right_movers) - == 0 - } - - pub const fn can_jump(self) -> bool { - self.jump - } - - pub const fn forward_left_bits(self) -> u32 { - self.forward_left_movers - } - - pub const fn get_direction_bits(self, direction: MoveDirection) -> u32 { - match direction { - MoveDirection::ForwardLeft => self.forward_left_movers, - MoveDirection::ForwardRight => self.forward_right_movers, - MoveDirection::BackwardLeft => self.backward_left_movers, - MoveDirection::BackwardRight => self.backward_right_movers, - } - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn same() { - let start = CheckersBitBoard::new( - 0b11100111100111100111110111111011, - 0b00001100001111001111001111000011, - 0, - PieceColor::Dark, - ); - let flip = CheckersBitBoard::new( - 0b11100111100111100111110111111011, - 0b11110011110000110000110000111100, - 0, - PieceColor::Light, - ); - - assert_eq!( - PossibleMoves::has_jumps(start), - PossibleMoves::has_jumps(flip) - ) - } -} +use crate::moves::{Move, MoveDirection}; +use crate::moves_iter::PossibleMovesIter; +use crate::{CheckersBitBoard, PieceColor}; + +#[derive(Copy, Clone, Debug)] +pub struct PossibleMoves { + forward_left_movers: u32, + forward_right_movers: u32, + backward_left_movers: u32, + backward_right_movers: u32, + jump: bool, +} + +impl IntoIterator for PossibleMoves { + type Item = Move; + type IntoIter = PossibleMovesIter; + + fn into_iter(self) -> Self::IntoIter { + self.into() + } +} + +impl PossibleMoves { + const fn slides_dark(board: CheckersBitBoard) -> Self { + const FORWARD_LEFT_MASK: u32 = 0b01111001111110111111001111011011; + const FORWARD_RIGHT_MASK: u32 = 0b01111101111111011111010111011101; + const BACKWARD_LEFT_MASK: u32 = 0b11111011111110111110101110111010; + const BACKWARD_RIGHT_MASK: u32 = 0b11111001111110011110110110111100; + + let not_occupied = !board.pieces_bits(); + let friendly_pieces = board.pieces_bits() & board.color_bits(); + let friendly_kings = friendly_pieces & board.king_bits(); + + let forward_left_movers = + not_occupied.rotate_right(7) & friendly_pieces & FORWARD_LEFT_MASK; + let forward_right_movers = + not_occupied.rotate_right(1) & friendly_pieces & FORWARD_RIGHT_MASK; + let backward_left_movers; + let backward_right_movers; + + if friendly_kings > 0 { + backward_left_movers = + not_occupied.rotate_left(1) & friendly_kings & BACKWARD_LEFT_MASK; + backward_right_movers = + not_occupied.rotate_left(7) & friendly_kings & BACKWARD_RIGHT_MASK; + } else { + backward_left_movers = 0; + backward_right_movers = 0; + } + + Self { + forward_left_movers, + forward_right_movers, + backward_left_movers, + backward_right_movers, + jump: false, + } + } + + const fn slides_light(board: CheckersBitBoard) -> Self { + const FORWARD_LEFT_MASK: u32 = 0b01111001111110111111001111011011; + const FORWARD_RIGHT_MASK: u32 = 0b01111101111111011111010111011101; + const BACKWARD_LEFT_MASK: u32 = 0b11111011111110111110101110111010; + const BACKWARD_RIGHT_MASK: u32 = 0b11111001111110011110110110111100; + + let not_occupied = !board.pieces_bits(); + let friendly_pieces = board.pieces_bits() & !board.color_bits(); + let friendly_kings = friendly_pieces & board.king_bits(); + + let backward_left_movers = + not_occupied.rotate_left(1) & friendly_pieces & BACKWARD_LEFT_MASK; + let backward_right_movers = + not_occupied.rotate_left(7) & friendly_pieces & BACKWARD_RIGHT_MASK; + let forward_left_movers; + let forward_right_movers; + + if friendly_kings > 0 { + forward_left_movers = not_occupied.rotate_right(7) & friendly_kings & FORWARD_LEFT_MASK; + forward_right_movers = + not_occupied.rotate_right(1) & friendly_kings & FORWARD_RIGHT_MASK; + } else { + forward_left_movers = 0; + forward_right_movers = 0; + } + + Self { + forward_left_movers, + forward_right_movers, + backward_left_movers, + backward_right_movers, + jump: false, + } + } + + const fn jumps_dark(board: CheckersBitBoard) -> Self { + const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; + const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; + const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; + const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; + + let not_occupied = !board.pieces_bits(); + let enemy_pieces = board.pieces_bits() & !board.color_bits(); + let friendly_pieces = board.pieces_bits() & board.color_bits(); + let friendly_kings = friendly_pieces & board.king_bits(); + + let forward_left_movers = not_occupied.rotate_right(14) + & enemy_pieces.rotate_right(7) + & friendly_pieces + & FORWARD_LEFT_MASK; + let forward_right_movers = not_occupied.rotate_right(2) + & enemy_pieces.rotate_right(1) + & friendly_pieces + & FORWARD_RIGHT_MASK; + let backward_left_movers; + let backward_right_movers; + + if friendly_kings > 0 { + backward_left_movers = not_occupied.rotate_left(2) + & enemy_pieces.rotate_left(1) + & friendly_kings & BACKWARD_LEFT_MASK; + backward_right_movers = not_occupied.rotate_left(14) + & enemy_pieces.rotate_left(7) + & friendly_kings & BACKWARD_RIGHT_MASK; + } else { + backward_left_movers = 0; + backward_right_movers = 0; + } + + Self { + forward_left_movers, + forward_right_movers, + backward_left_movers, + backward_right_movers, + jump: true, + } + } + + const fn jumps_light(board: CheckersBitBoard) -> Self { + const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; + const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; + const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; + const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; + + let not_occupied = !board.pieces_bits(); + let enemy_pieces = board.pieces_bits() & board.color_bits(); + let friendly_pieces = board.pieces_bits() & !board.color_bits(); + let friendly_kings = friendly_pieces & board.king_bits(); + + let backward_left_movers = not_occupied.rotate_left(2) + & enemy_pieces.rotate_left(1) + & friendly_pieces + & BACKWARD_LEFT_MASK; + let backward_right_movers = not_occupied.rotate_left(14) + & enemy_pieces.rotate_left(7) + & friendly_pieces + & BACKWARD_RIGHT_MASK; + let forward_left_movers; + let forward_right_movers; + + if friendly_kings > 0 { + forward_left_movers = not_occupied.rotate_right(14) + & enemy_pieces.rotate_right(7) + & friendly_kings & FORWARD_LEFT_MASK; + forward_right_movers = not_occupied.rotate_right(2) + & enemy_pieces.rotate_right(1) + & friendly_kings & FORWARD_RIGHT_MASK; + } else { + forward_left_movers = 0; + forward_right_movers = 0; + } + + Self { + forward_left_movers, + forward_right_movers, + backward_left_movers, + backward_right_movers, + jump: true, + } + } + + // TODO make this private + pub const fn has_jumps_dark(board: CheckersBitBoard) -> bool { + const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; + const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; + const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; + const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; + + let not_occupied = !board.pieces_bits(); + let enemy_pieces = board.pieces_bits() & !board.color_bits(); + let friendly_pieces = board.pieces_bits() & board.color_bits(); + + let forward_left_spaces = + not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK; + let forward_right_spaces = + not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK; + + let forward_spaces = forward_left_spaces | forward_right_spaces; + + if board.king_bits() > 0 { + let backward_left_spaces = + not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK; + let backward_right_spaces = + not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK; + let backward_spaces = backward_left_spaces | backward_right_spaces; + + let forward_spaces = board.king_bits() & backward_spaces; + friendly_pieces & (forward_spaces | backward_spaces) != 0 + } else { + friendly_pieces & forward_spaces != 0 + } + } + + // TODO make this private + pub const fn has_jumps_light(board: CheckersBitBoard) -> bool { + const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011; + const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100; + const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000; + const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100; + + let not_occupied = !board.pieces_bits(); + let enemy_pieces = board.pieces_bits() & board.color_bits(); + let friendly_pieces = board.pieces_bits() & !board.color_bits(); + + let backward_left_spaces = + not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK; + let backward_right_spaces = + not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK; + + let backward_spaces = backward_left_spaces | backward_right_spaces; + + if board.king_bits() > 0 { + let forward_left_spaces = + not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK; + let forward_right_spaces = + not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK; + let forward_spaces = forward_left_spaces | forward_right_spaces; + + let forward_spaces = board.king_bits() & forward_spaces; + friendly_pieces & (forward_spaces | backward_spaces) != 0 + } else { + friendly_pieces & backward_spaces != 0 + } + } + + #[inline(always)] + // TODO optimize + pub const fn has_jumps(board: CheckersBitBoard) -> bool { + match board.turn() { + PieceColor::Light => Self::has_jumps_light(board), + PieceColor::Dark => Self::has_jumps_dark(board), + } + } + + const fn light_moves(board: CheckersBitBoard) -> Self { + let jumps = Self::jumps_light(board); + if jumps.is_empty() { + Self::slides_light(board) + } else { + jumps + } + } + + const fn dark_moves(board: CheckersBitBoard) -> Self { + let jumps = Self::jumps_dark(board); + if jumps.is_empty() { + Self::slides_dark(board) + } else { + jumps + } + } + + pub const fn moves(board: CheckersBitBoard) -> Self { + match board.turn() { + PieceColor::Dark => Self::dark_moves(board), + PieceColor::Light => Self::light_moves(board), + } + } + + /// Returns true if no moves are possible + pub const fn is_empty(self) -> bool { + (self.backward_left_movers + | self.forward_left_movers + | self.forward_right_movers + | self.backward_right_movers) + == 0 + } + + /// Returns true if the piece can jump + pub const fn can_jump(self) -> bool { + self.jump + } + + /// Returns the pieces who can move forward left, + /// with undefined behavior for bits where a forward left move is impossible + /// + /// # Safety + /// + /// This function is inherently unsafe because some bits are undefined + // TODO make this unsafe + pub const fn forward_left_bits(self) -> u32 { + self.forward_left_movers + } + + /// Gets the bits for a certain direction, + /// with undefined behavior for bits where the given move is impossible + /// + /// # Safety + /// + /// This function is inherently unsafe because some bits are undefined + // TODO make this unsafe + pub const fn get_direction_bits(self, direction: MoveDirection) -> u32 { + match direction { + MoveDirection::ForwardLeft => self.forward_left_movers, + MoveDirection::ForwardRight => self.forward_right_movers, + MoveDirection::BackwardLeft => self.backward_left_movers, + MoveDirection::BackwardRight => self.backward_right_movers, + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn same() { + let start = CheckersBitBoard::new( + 0b11100111100111100111110111111011, + 0b00001100001111001111001111000011, + 0, + PieceColor::Dark, + ); + let flip = CheckersBitBoard::new( + 0b11100111100111100111110111111011, + 0b11110011110000110000110000111100, + 0, + PieceColor::Light, + ); + + assert_eq!( + PossibleMoves::has_jumps(start), + PossibleMoves::has_jumps(flip) + ) + } +} -- cgit v1.2.3