Created a transposition table and fixed some bugs

2 files changed, 117 insertions, 1 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)),
+		}
+	}
+}