From 7e73782a7d51b40a558b74793c1d6c1abdea857d Mon Sep 17 00:00:00 2001 From: Botahamec Date: Thu, 8 Jul 2021 20:32:44 -0400 Subject: here's what i have so far --- model/Cargo.toml | 18 + model/benches/bitboard.rs | 96 +++++ model/proptest-regressions/board/tests.txt | 8 + model/src/board.rs | 589 +++++++++++++++++++++++++ model/src/board/tests.rs | 662 +++++++++++++++++++++++++++++ model/src/color.rs | 57 +++ model/src/lib.rs | 10 + model/src/moves.rs | 59 +++ model/src/moves_iter.rs | 143 +++++++ model/src/possible_moves.rs | 326 ++++++++++++++ 10 files changed, 1968 insertions(+) create mode 100644 model/Cargo.toml create mode 100644 model/benches/bitboard.rs create mode 100644 model/proptest-regressions/board/tests.txt create mode 100644 model/src/board.rs create mode 100644 model/src/board/tests.rs create mode 100644 model/src/color.rs create mode 100644 model/src/lib.rs create mode 100644 model/src/moves.rs create mode 100644 model/src/moves_iter.rs create mode 100644 model/src/possible_moves.rs (limited to 'model') diff --git a/model/Cargo.toml b/model/Cargo.toml new file mode 100644 index 0000000..f264a17 --- /dev/null +++ b/model/Cargo.toml @@ -0,0 +1,18 @@ +[package] +name = "model" +version = "0.1.0" +authors = ["Mike White "] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +serde = { version = "1.0.126", optional = true, features = ["derive"] } + +[dev-dependencies] +proptest = "1.0.0" +criterion = "0.3" + +[[bench]] +name = "bitboard" +harness = false \ No newline at end of file diff --git a/model/benches/bitboard.rs b/model/benches/bitboard.rs new file mode 100644 index 0000000..231f860 --- /dev/null +++ b/model/benches/bitboard.rs @@ -0,0 +1,96 @@ +use criterion::{black_box, criterion_group, criterion_main, Criterion}; +use model::CheckersBitBoard; +use std::collections::hash_map::DefaultHasher; +use std::hash::Hash; + +fn clone(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("clone", |b| b.iter(|| black_box(board.clone()))); +} + +fn hash(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + let mut hasher = DefaultHasher::new(); + c.bench_function("hash", |b| b.iter(|| board.hash(black_box(&mut hasher)))); +} + +fn default(c: &mut Criterion) { + c.bench_function("default", |b| { + b.iter(|| black_box(CheckersBitBoard::default())) + }); +} + +fn eq(c: &mut Criterion) { + let board1 = CheckersBitBoard::default(); + let board2 = CheckersBitBoard::default(); + c.bench_function("equal", |b| { + b.iter(|| black_box(board1) == black_box(board2)) + }); +} + +fn default_const(c: &mut Criterion) { + c.bench_function("default (const)", |b| { + b.iter(|| black_box(CheckersBitBoard::starting_position())) + }); +} + +fn new(c: &mut Criterion) { + c.bench_function("new", |b| { + b.iter(|| CheckersBitBoard::new(black_box(7328), black_box(174), black_box(27590))) + }); +} + +fn piece_at(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("piece", |b| b.iter(|| board.piece_at(black_box(0)))); +} + +fn color_at_unchecked(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("color (unsafe)", |b| { + b.iter(|| unsafe { board.color_at_unchecked(black_box(1)) }) + }); +} + +fn king_at_unchecked(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("king (unsafe)", |b| { + b.iter(|| unsafe { board.king_at_unchecked(black_box(2)) }) + }); +} + +fn color_at(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("color (safe - filled)", |b| { + b.iter(|| board.color_at(black_box(3))) + }); + + c.bench_function("color (safe - empty)", |b| { + b.iter(|| board.color_at(black_box(2))) + }); +} + +fn king_at(c: &mut Criterion) { + let board = CheckersBitBoard::starting_position(); + c.bench_function("king (safe - filled)", |b| { + b.iter(|| board.king_at(black_box(4))) + }); + + c.bench_function("king (safe - empty)", |b| { + b.iter(|| board.king_at(black_box(9))) + }); +} + +criterion_group!( + bitboard, clone, + hash, eq, + default, + default_const, + new, + piece_at, + color_at_unchecked, + king_at_unchecked, + color_at, + king_at, +); +criterion_main!(bitboard); diff --git a/model/proptest-regressions/board/tests.txt b/model/proptest-regressions/board/tests.txt new file mode 100644 index 0000000..3261322 --- /dev/null +++ b/model/proptest-regressions/board/tests.txt @@ -0,0 +1,8 @@ + +cc 3bbe506c845861580c16a52b227d9cd54564f6c16ed3ed0d2fb9ef376a442027 # shrinks to p = 1870702296, c = 727253032, k = 0, v = 0 +cc 82957097e53375440d4b8cc902cbb6a2fcd5f064484e30b8357490f720a4c9de # shrinks to p = 3676936387, c = 12254398, k = 0 +cc 77e7e59300115333b1315248284cd51ef694fe50e2372e6b7590307d99c3149f # shrinks to p = 1038876672, c = 2140405760, k = 0 +cc 6457fde5f0dbcbe0bdbccb381f2d93e73da398575430094e435cff50687ec3f4 # shrinks to p = 1095727536, c = 489620144, k = 0 +cc f7e8862b474becba204cb1a69be1ebe00474a36ff379a55a899cac65768f9723 # shrinks to p = 285212672, c = 81920000, k = 2315255808, v = 24 +cc e1ac7da29052dd94064e44f2fffe93d0b1cfcd66d2f91f1c16683ccc35d631a1 # shrinks to p = 687865856, c = 1543503872, k = 134217728, v = 24 +cc 947a98c8bd714a6fbaf973b6473ebb9896eff2b6573ff9a8bc2fb9e7409bb8d1 # shrinks to p = 256848745, c = 0, k = 691954520, v = 0 diff --git a/model/src/board.rs b/model/src/board.rs new file mode 100644 index 0000000..0128c89 --- /dev/null +++ b/model/src/board.rs @@ -0,0 +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 + } + } +} diff --git a/model/src/board/tests.rs b/model/src/board/tests.rs new file mode 100644 index 0000000..2afe1da --- /dev/null +++ b/model/src/board/tests.rs @@ -0,0 +1,662 @@ +use std::collections::hash_map::DefaultHasher; + +use proptest::prelude::*; + +use super::*; + +proptest! { + #[test] + fn test_bitboard_new(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX) { + let board = CheckersBitBoard::new(p, c, k, PieceColor::Dark); + assert_eq!(p, board.pieces); + assert_eq!(c, board.color); + assert_eq!(k, board.kings); + } + + #[test] + fn test_bits_fns(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + assert_eq!(p, board.pieces_bits()); + assert_eq!(c, board.color_bits()); + assert_eq!(k, board.king_bits()); + } + + #[test] + fn test_bitboard_hash(pieces in 0u32..=u32::MAX, color in 0u32..=u32::MAX, kings in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX) { + let board1 = CheckersBitBoard { + pieces, color, kings, turn: PieceColor::Dark + }; + let board2 = CheckersBitBoard { + pieces, + color: c, + kings: k, + turn: PieceColor::Dark + }; + let mut hasher1 = DefaultHasher::new(); + let mut hasher2 = DefaultHasher::new(); + board1.hash(&mut hasher1); + board2.hash(&mut hasher2); + assert_eq!(hasher1.finish(), hasher2.finish()); + } + + #[test] + fn test_bitboard_eq_identical(pieces in 0u32..=u32::MAX, color in 0u32..u32::MAX, kings in 0u32..=u32::MAX) { + let board1 = CheckersBitBoard {pieces, color, kings, turn: PieceColor::Dark}; + let board2 = CheckersBitBoard {pieces, color, kings, turn: PieceColor::Dark}; + assert_eq!(board1, board2); + } + + #[test] + fn test_bitboard_eq_empty(c1 in 0u32..u32::MAX, k1 in 0u32..=u32::MAX, c2 in 0u32..u32::MAX, k2 in 0u32..=u32::MAX) { + let board1 = CheckersBitBoard {pieces: 0, color: c1, kings: k1, turn: PieceColor::Dark}; + let board2 = CheckersBitBoard {pieces: 0, color: c2, kings: k2, turn: PieceColor::Dark}; + assert_eq!(board1, board2); + } + + #[test] + fn test_piece_at(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + board.piece_at(v); + } + + #[test] + fn test_color_at_unchecked(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + unsafe {board.color_at_unchecked(v);} + } + + #[test] + fn test_king_at_unchecked(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + unsafe {board.king_at_unchecked(v);} + } + + #[test] + fn test_color_at(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + board.color_at(v); + } + + #[test] + fn test_king_at(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + board.king_at(v); + } + + #[test] + fn test_move_piece_to(p in 0u32..=u32::MAX, c in 0u32..=u32::MAX, k in 0u32..=u32::MAX, s in 0usize..32, e in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, + color: c, + kings: k, + turn: PieceColor::Dark + }; + unsafe {board.move_piece_to_unchecked(s, e)}; + } + + #[test] + fn test_move_forward(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX, v in 0usize..32, a in 0usize..usize::MAX) { + if a <= usize::MAX - v { // so there's no overflow + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + unsafe {board.move_piece_forward_unchecked(v, a)}; + } + } + + #[test] + fn test_move_backward(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX, v in 0usize..32, a in 0usize..usize::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + unsafe {board.move_piece_backward_unchecked(v, a)}; + } + + #[test] + fn test_move_forward_left(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + if board.piece_at(0) { + let board2 = unsafe {board.move_piece_forward_left_unchecked(0)}; + assert_eq!(board2.color_at(7), board.color_at(0)); + assert_eq!(board2.king_at(7), board.king_at(0)); + } + } + + #[test] + fn test_move_forward_right(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + if board.piece_at(18) { + let board2 = unsafe {board.move_piece_forward_right_unchecked(18)}; + assert_eq!(board2.color_at(19), board.color_at(18)); + assert_eq!(board2.king_at(19), board.king_at(18)); + } + } + + #[test] + fn test_move_backward_left(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + if board.piece_at(25) { + let board2 = unsafe {board.move_piece_backward_left_unchecked(25)}; + assert_eq!(board2.color_at(24), board.color_at(25)); + assert_eq!(board2.king_at(24), board.king_at(25)); + } + } + + #[test] + fn test_move_backward_right(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + if board.piece_at(11) { + let board2 = unsafe {board.move_piece_backward_right_unchecked(11)}; + assert_eq!(board2.color_at(4), board.color_at(11)); + assert_eq!(board2.king_at(4), board.king_at(11)); + } + } + + #[test] + fn test_clear_piece(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX, v in 0usize..32) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + let board = board.clear_piece(v); + assert!(!board.piece_at(v)); + } + + #[test] + fn test_jump_forward_left(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + unsafe { + if board.piece_at(0) && board.piece_at(7) && !board.piece_at(14) && board.color_at_unchecked(0) != board.color_at_unchecked(7) { + let board2 = board.jump_piece_forward_left_unchecked(0); + assert!(!board2.piece_at(0)); + assert!(!board2.piece_at(7)); + assert!(board2.piece_at(14)); + assert_eq!(board2.color_at_unchecked(14), board.color_at_unchecked(0)); + assert_eq!(board2.king_at_unchecked(14), board.king_at_unchecked(0)); + } + } + } + + #[test] + fn test_jump_forward_right(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + unsafe { + if board.piece_at(18) && board.piece_at(19) && !board.piece_at(20) && board.color_at_unchecked(18) != board.color_at_unchecked(19) { + let board2 = board.jump_piece_forward_right_unchecked(18); + assert!(!board2.piece_at(18)); + assert!(!board2.piece_at(19)); + assert!(board2.piece_at(20)); + assert_eq!(board2.color_at_unchecked(20), board.color_at_unchecked(18)); + assert_eq!(board2.king_at_unchecked(20), board.king_at_unchecked(18)); + } + } + } + + #[test] + fn test_jump_backward_left(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + unsafe { + if board.piece_at(25) && board.piece_at(24) && !board.piece_at(23) && board.color_at_unchecked(25) != board.color_at_unchecked(24) { + let board2 = board.jump_piece_backward_left_unchecked(25); + assert!(!board2.piece_at(25)); + assert!(!board2.piece_at(24)); + assert!(board2.piece_at(23)); + assert_eq!(board2.color_at_unchecked(23), board.color_at_unchecked(25)); + assert_eq!(board2.king_at_unchecked(23), board.king_at_unchecked(25)); + } + } + } + + #[test] + fn test_jump_backward_right(p in 0..u32::MAX, c in 0..u32::MAX, k in 0..u32::MAX) { + let board = CheckersBitBoard { + pieces: p, color: c, kings: k, turn: PieceColor::Dark + }; + + unsafe { + if board.piece_at(11) && board.piece_at(4) && !board.piece_at(29) && board.color_at_unchecked(11) != board.color_at_unchecked(4) { + let board2 = board.jump_piece_backward_right_unchecked(11); + assert!(!board2.piece_at(11)); + assert!(!board2.piece_at(4)); + assert!(board2.piece_at(29)); + assert_eq!(board2.color_at_unchecked(29), board.color_at_unchecked(11)); + assert_eq!(board2.king_at_unchecked(29), board.king_at_unchecked(11)); + } + } + } +} + +#[test] +fn test_piece_at_empty_board() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 0, + turn: PieceColor::Dark, + }; + + // There should be no piece in any space + for i in 0..32 { + assert!(!board.piece_at(i)) + } +} + +#[test] +fn test_piece_at_space_zero() { + let board = CheckersBitBoard { + pieces: 1, + color: 0, + kings: 0, + turn: PieceColor::Dark, + }; + assert!(board.piece_at(0)); // There should be a piece in space 0 + + // There should be no piece in any other square + for i in 1..32 { + assert!(!board.piece_at(i)) + } +} + +#[test] +fn test_color_at_unchecked_all_light() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 0, + turn: PieceColor::Dark, + }; + + // All squares should be light + for i in 0..32 { + assert_eq!(unsafe { board.color_at_unchecked(i) }, PieceColor::Light) + } +} + +#[test] +fn test_color_at_unchecked_all_dark() { + let board = CheckersBitBoard { + pieces: 0, + color: u32::MAX, + kings: 0, + turn: PieceColor::Dark, + }; + + // All squares should be dark + for i in 0..32 { + assert_eq!(unsafe { board.color_at_unchecked(i) }, PieceColor::Dark) + } +} + +#[test] +fn test_king_at_unchecked_all_kings() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: u32::MAX, + turn: PieceColor::Dark, + }; + + // All squares should be kings + for i in 0..32 { + assert!(unsafe { board.king_at_unchecked(i) }) + } +} + +#[test] +fn test_king_at_unchecked_one_king() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 1, + turn: PieceColor::Dark, + }; + + assert!(unsafe { board.king_at_unchecked(0) }); + + // All other squares should be peasants + for i in 1..32 { + assert!(!unsafe { board.king_at_unchecked(i) }) + } +} + +#[test] +fn test_default_bitboard() { + let board = CheckersBitBoard::default(); + let exemptions = vec![2, 28, 22, 16, 27, 21, 15, 9]; + let black = vec![11, 5, 31, 25, 10, 4, 30, 24, 3, 29, 23, 17]; + + for i in 0..32 { + if !exemptions.contains(&i) { + assert!(board.piece_at(i)); + assert!(!unsafe { board.king_at_unchecked(i) }); + + if black.contains(&i) { + assert_eq!(unsafe { board.color_at_unchecked(i) }, PieceColor::Dark) + } else { + assert_eq!(unsafe { board.color_at_unchecked(i) }, PieceColor::Light) + } + } else { + assert!(!board.piece_at(i)) + } + } +} + +#[test] +fn test_bitboard_eq_default() { + let board1 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 0b11110011110000110000110000111100, + kings: 0, + turn: PieceColor::Dark, + }; + let board2 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 0b11110011110000110000110000111100, + kings: 0, + turn: PieceColor::Dark, + }; + assert_eq!(board1, board2); +} + +#[test] +fn test_bitboard_neq_color() { + let board1 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 0b11110011110000110000110000111100, + kings: 0, + turn: PieceColor::Dark, + }; + let board2 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 465413646, + kings: 0, + turn: PieceColor::Dark, + }; + assert_ne!(board1, board2); +} + +#[test] +fn test_bitboard_neq_kings() { + let board1 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 0b11110011110000110000110000111100, + kings: 0, + turn: PieceColor::Dark, + }; + let board2 = CheckersBitBoard { + pieces: 0b11100111100111100111110111111011, + color: 0b11110011110000110000110000111100, + kings: 465413646, + turn: PieceColor::Dark, + }; + assert_ne!(board1, board2); +} + +#[test] +fn test_color_at_empty() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 0, + turn: PieceColor::Dark, + }; + + for i in 0..32 { + assert_eq!(board.color_at(i), None) + } +} + +#[test] +fn test_color_at_specified_empty_colors() { + let board = CheckersBitBoard { + pieces: 0, + color: 0b01, + kings: 0, + turn: PieceColor::Dark, + }; + + for i in 0..32 { + assert_eq!(board.color_at(i), None) + } +} + +#[test] +fn test_color_at_some_colors() { + let board = CheckersBitBoard { + pieces: 3, + color: 0b01, + kings: 0, + turn: PieceColor::Dark, + }; + + assert_eq!(board.color_at(0), Some(PieceColor::Dark)); + assert_eq!(board.color_at(1), Some(PieceColor::Light)); + + for i in 2..32 { + assert_eq!(board.color_at(i), None) + } +} + +#[test] +fn test_king_at_empty() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 0, + turn: PieceColor::Dark, + }; + + for i in 0..32 { + assert_eq!(board.king_at(i), None) + } +} + +#[test] +fn test_king_at_specified_empty_colors() { + let board = CheckersBitBoard { + pieces: 0, + color: 0, + kings: 0b01, + turn: PieceColor::Dark, + }; + + for i in 0..32 { + assert_eq!(board.king_at(i), None) + } +} + +#[test] +fn test_king_at_some_colors() { + let board = CheckersBitBoard { + pieces: 3, + color: 0, + kings: 0b01, + turn: PieceColor::Dark, + }; + + assert_eq!(board.king_at(0), Some(true)); + assert_eq!(board.king_at(1), Some(false)); + + for i in 2..32 { + assert_eq!(board.king_at(i), None) + } +} + +#[test] +fn test_move_piece_to_default_board() { + let board = CheckersBitBoard::default(); + let board = unsafe { board.move_piece_to_unchecked(0, 5) }; + assert!(!board.piece_at(0)); + assert!(board.piece_at(5)); + assert_eq!(board.color_at(5).unwrap(), PieceColor::Light); + assert!(!board.king_at(5).unwrap()); +} + +#[test] +fn test_move_piece_forward_standard() { + let board = CheckersBitBoard::default(); + let board = unsafe { board.move_piece_forward_unchecked(14, 2) }; // go to 16 + assert!(!board.piece_at(14)); + assert!(board.piece_at(16)); + assert_eq!(board.color_at(16).unwrap(), PieceColor::Light); + assert!(!board.king_at(16).unwrap()); +} + +#[test] +fn test_move_piece_forward_wrap() { + let board = CheckersBitBoard::default(); + let board = unsafe { board.move_piece_forward_unchecked(31, 10) }; // go to 9 + assert!(!board.piece_at(31)); + assert!(board.piece_at(9)); + assert_eq!(board.color_at(9).unwrap(), PieceColor::Dark); + assert!(!board.king_at(9).unwrap()); +} + +#[test] +fn test_move_piece_backward_standard() { + let board = CheckersBitBoard::default(); + let board = unsafe { board.move_piece_backward_unchecked(29, 14) }; // go to 15 + assert!(!board.piece_at(29)); + assert!(board.piece_at(15)); + assert_eq!(board.color_at(15).unwrap(), PieceColor::Dark); + assert!(!board.king_at(15).unwrap()); +} + +#[test] +fn test_move_piece_backward_wrap() { + let board = CheckersBitBoard::default(); + let board = unsafe { board.move_piece_backward_unchecked(0, 4) }; // go to 28 + assert!(!board.piece_at(0)); + assert!(board.piece_at(28)); + assert_eq!(board.color_at(28).unwrap(), PieceColor::Light); + assert!(!board.king_at(28).unwrap()); +} + +#[test] +// the specific tests have special values, and are different from the property tests +fn test_jump_forward_left_specific() { + let board = CheckersBitBoard { + pieces: 0b10000001, + color: 1, + kings: 0, + turn: PieceColor::Dark, + }; + + let board2 = unsafe { board.jump_piece_forward_left_unchecked(0) }; + assert!(!board2.piece_at(0)); + assert!(!board2.piece_at(7)); + 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()); +} + +#[test] +fn test_jump_forward_right_specific() { + let board = CheckersBitBoard { + pieces: 0b11000000000000000000, + color: 0b10000000000000000000, + kings: 0, + turn: PieceColor::Dark, + }; + + let board2 = unsafe { board.jump_piece_forward_right_unchecked(18) }; + assert!(!board2.piece_at(18)); + assert!(!board2.piece_at(19)); + 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()); +} + +#[test] +fn test_jump_backward_left_specific() { + let board = CheckersBitBoard { + pieces: 0b110000000000000000000000000, + color: 0b100000000000000000000000000, + kings: 0, + turn: PieceColor::Dark, + }; + + let board2 = unsafe { board.jump_piece_backward_left_unchecked(25) }; + assert!(!board2.piece_at(25)); + assert!(!board2.piece_at(24)); + 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()); +} + +#[test] +fn test_jump_backward_right_specific() { + let board = CheckersBitBoard { + pieces: 0b100000010000, + color: 0b10000, + kings: 0, + turn: PieceColor::Dark, + }; + + let board2 = unsafe { board.jump_piece_backward_right_unchecked(11) }; + assert!(!board2.piece_at(11)); + assert!(!board2.piece_at(4)); + 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()); +} + +#[test] +fn test_send() { + fn assert_send() {} + assert_send::(); +} + +#[test] +fn test_sync() { + fn assert_sync() {} + assert_sync::(); +} diff --git a/model/src/color.rs b/model/src/color.rs new file mode 100644 index 0000000..3dd2a64 --- /dev/null +++ b/model/src/color.rs @@ -0,0 +1,57 @@ +#[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"); + } +} diff --git a/model/src/lib.rs b/model/src/lib.rs new file mode 100644 index 0000000..7b21be5 --- /dev/null +++ b/model/src/lib.rs @@ -0,0 +1,10 @@ +mod board; +mod color; +mod moves; +mod moves_iter; +mod possible_moves; + +pub use board::CheckersBitBoard; +pub use color::PieceColor; +pub use moves::Move; +pub use possible_moves::PossibleMoves; diff --git a/model/src/moves.rs b/model/src/moves.rs new file mode 100644 index 0000000..30024d6 --- /dev/null +++ b/model/src/moves.rs @@ -0,0 +1,59 @@ +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) + } + }, + } + } +} diff --git a/model/src/moves_iter.rs b/model/src/moves_iter.rs new file mode 100644 index 0000000..307ee96 --- /dev/null +++ b/model/src/moves_iter.rs @@ -0,0 +1,143 @@ +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, + }, + ), + ) + } +} diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs new file mode 100644 index 0000000..7d4ac29 --- /dev/null +++ b/model/src/possible_moves.rs @@ -0,0 +1,326 @@ +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) + ) + } +} -- cgit v1.2.3