Created a transposition table and fixed some bugs

5 files changed, 144 insertions, 17 deletions

diff --git a/ai/src/lib.rs b/ai/src/lib.rs
index 7bee732..426ee47 100644
--- a/ai/src/lib.rs
+++ b/ai/src/lib.rs
@@ -1,8 +1,11 @@
+use crate::transposition_table::TranspositionTableReference;
 pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
 use parking_lot::{Mutex, RwLock};
 use rayon::prelude::*;
 use std::mem::MaybeUninit;
 
+mod transposition_table;
+
 const KING_WORTH: u32 = 2;
 
 fn eval_position(board: CheckersBitBoard) -> f32 {
@@ -42,12 +45,26 @@ pub fn eval_singlethreaded(
 			1.0 - eval_position(board)
 		}
 	} else {
+		let table = TranspositionTableReference::new();
+		if let Some(eval) = table.get(board, depth as u8) {
+			return eval;
+		}
+
 		let turn = board.turn();
 		let mut best_eval = f32::NEG_INFINITY;
 		let moves = PossibleMoves::moves(board);
 
 		if moves.is_empty() {
-			return 0.5;
+			let pos_eval = if board.turn() == PieceColor::Dark {
+				eval_position(board)
+			} else {
+				1.0 - eval_position(board)
+			};
+			return if pos_eval < f32::EPSILON || pos_eval > 1.0 - f32::EPSILON {
+				pos_eval
+			} else {
+				0.5
+			};
 		}
 
 		for current_move in PossibleMoves::moves(board) {
@@ -58,6 +75,9 @@ pub fn eval_singlethreaded(
 				eval_singlethreaded(depth - 1, alpha, beta, board)
 			};
 
+			let table = TranspositionTableReference::new();
+			table.insert(board, current_eval, depth as u8);
+
 			if current_eval >= beta {
 				return beta;
 			}
diff --git a/ai/src/transposition_table.rs b/ai/src/transposition_table.rs
new file mode 100644
index 0000000..4f1e09c
--- /dev/null
+++ b/ai/src/transposition_table.rs
@@ -0,0 +1,96 @@
+use crate::CheckersBitBoard;
+use parking_lot::lock_api::RawMutex;
+use parking_lot::Mutex;
+
+#[cfg(debug_assertions)]
+const TABLE_SIZE: usize = 1_000_000 / std::mem::size_of::<TranspositionTableEntry>();
+
+#[cfg(not(debug_assertions))]
+const TABLE_SIZE: usize = 10_000_000 / std::mem::size_of::<TranspositionTableEntry>();
+
+const EMPTY_ENTRY: Option<TranspositionTableEntry> = None;
+static mut REPLACE_TABLE: [Option<TranspositionTableEntry>; TABLE_SIZE] = [EMPTY_ENTRY; TABLE_SIZE];
+static mut DEPTH_TABLE: [Option<TranspositionTableEntry>; TABLE_SIZE] = [EMPTY_ENTRY; TABLE_SIZE];
+
+#[derive(Copy, Clone, Debug)]
+struct TranspositionTableEntry {
+	board: CheckersBitBoard,
+	eval: f32,
+	depth: u8,
+}
+
+pub struct TranspositionTableReference {
+	replace_table: &'static mut [Option<TranspositionTableEntry>; TABLE_SIZE],
+	depth_table: &'static mut [Option<TranspositionTableEntry>; TABLE_SIZE],
+}
+
+impl TranspositionTableEntry {
+	const fn new(board: CheckersBitBoard, eval: f32, depth: u8) -> Self {
+		Self { board, eval, depth }
+	}
+}
+
+impl TranspositionTableReference {
+	pub fn new() -> Self {
+		Self {
+			replace_table: unsafe { &mut REPLACE_TABLE },
+			depth_table: unsafe { &mut DEPTH_TABLE },
+		}
+	}
+
+	pub fn get(self, board: CheckersBitBoard, depth: u8) -> Option<f32> {
+		// try the replace table
+		let entry = unsafe {
+			self.replace_table
+				.get_unchecked(board.hash_code() as usize % TABLE_SIZE)
+		};
+		if let Some(entry) = *entry {
+			if entry.board == board && entry.depth >= depth {
+				return Some(entry.eval);
+			}
+		}
+
+		// try the depth table
+		let entry = unsafe {
+			self.depth_table
+				.get_unchecked(board.hash_code() as usize % TABLE_SIZE)
+		};
+		match *entry {
+			Some(entry) => {
+				if entry.board == board {
+					if entry.depth >= depth {
+						Some(entry.eval)
+					} else {
+						None
+					}
+				} else {
+					None
+				}
+			}
+			None => None,
+		}
+	}
+
+	pub fn insert(self, board: CheckersBitBoard, eval: f32, depth: u8) {
+		// insert to the replace table
+		let entry = unsafe {
+			self.replace_table
+				.get_unchecked_mut(board.hash_code() as usize % TABLE_SIZE)
+		};
+		*entry = Some(TranspositionTableEntry::new(board, eval, depth));
+
+		// insert to the depth table, only if the new depth is higher
+		let entry = unsafe {
+			self.depth_table
+				.get_unchecked_mut(board.hash_code() as usize % TABLE_SIZE)
+		};
+		match *entry {
+			Some(entry_val) => {
+				if depth >= entry_val.depth {
+					*entry = Some(TranspositionTableEntry::new(board, eval, depth));
+				}
+			}
+			None => *entry = Some(TranspositionTableEntry::new(board, eval, depth)),
+		}
+	}
+}
diff --git a/model/src/board.rs b/model/src/board.rs
index f95d837..a6eba23 100644
--- a/model/src/board.rs
+++ b/model/src/board.rs
@@ -51,7 +51,7 @@ impl PartialEq for CheckersBitBoard {
 impl Hash for CheckersBitBoard {
 	/// Hashes with only the pieces part, to ensure correctness and efficiency
 	fn hash<H: Hasher>(&self, hasher: &mut H) {
-		self.pieces.hash(hasher)
+		self.hash_code().hash(hasher)
 	}
 }
 
@@ -98,6 +98,11 @@ impl CheckersBitBoard {
 		STARTING_BITBOARD
 	}
 
+	#[must_use]
+	pub const fn hash_code(self) -> u64 {
+		(((self.color & self.pieces) as u64) << 32) | (self.pieces as u64)
+	}
+
 	/// Gets the bits that represent where pieces are on the board
 	#[must_use]
 	pub const fn pieces_bits(self) -> u32 {
@@ -634,6 +639,7 @@ impl CheckersBitBoard {
 			.clear_piece(value.wrapping_sub(7) & 31);
 
 		const KING_MASK: u32 = 0b00000100000100000100000100000000;
+		// TODO double jump should only apply to the piece that just moved
 		if (is_king || (((1 << value) & KING_MASK) == 0))
 			&& PossibleMoves::has_jumps(board.flip_turn())
 		{
diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs
index 7d32a27..03950c2 100644
--- a/model/src/possible_moves.rs
+++ b/model/src/possible_moves.rs
@@ -370,18 +370,14 @@ impl PossibleMoves {
 		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 forward_left_movers = not_occupied.rotate_right(7) & friendly_pieces;
+		let forward_right_movers = not_occupied.rotate_right(1) & friendly_pieces;
 		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;
+			backward_left_movers = not_occupied.rotate_left(1) & friendly_kings;
+			backward_right_movers = not_occupied.rotate_left(7) & friendly_kings;
 		} else {
 			backward_left_movers = 0;
 			backward_right_movers = 0;
@@ -405,17 +401,14 @@ impl PossibleMoves {
 		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 backward_left_movers = not_occupied.rotate_left(1) & friendly_pieces;
+		let backward_right_movers = not_occupied.rotate_left(7) & friendly_pieces;
 		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;
+			forward_left_movers = not_occupied.rotate_right(7) & friendly_kings;
+			forward_right_movers = not_occupied.rotate_right(1) & friendly_kings;
 		} else {
 			forward_left_movers = 0;
 			forward_right_movers = 0;
diff --git a/ui/src/main.rs b/ui/src/main.rs
index 2b4bd17..c25c0d7 100644
--- a/ui/src/main.rs
+++ b/ui/src/main.rs
@@ -19,6 +19,7 @@ struct GameState {
 	bit_board: CheckersBitBoard,
 	selected_square: Option<SquareCoordinate>,
 	possible_moves: HashSet<Move>,
+	evaluation: f32,
 }
 
 impl GameState {
@@ -33,6 +34,7 @@ impl GameState {
 			bit_board: CheckersBitBoard::starting_position(),
 			selected_square: None,
 			possible_moves: HashSet::new(),
+			evaluation: 0.5,
 		})
 	}
 }
@@ -75,8 +77,18 @@ impl State for GameState {
 					// safety: this was determined to be in the list of possible moves
 					self.bit_board = unsafe { selected_move.apply_to(self.bit_board) };
 
+					// ai makes a move
+					while self.bit_board.turn() == PieceColor::Light
+						&& !PossibleMoves::moves(self.bit_board).is_empty()
+					{
+						let best_move = ai::best_move(12, self.bit_board);
+						self.bit_board = unsafe { best_move.apply_to(self.bit_board) };
+					}
+
 					self.selected_square = None;
 					self.possible_moves.clear();
+					self.evaluation = ai::eval_multithreaded(12, 0.0, 1.0, self.bit_board);
+					println!("{}", self.evaluation);
 				} else {
 					self.selected_square = Some(square);