Edited some of the crates

6 files changed, 350 insertions, 0 deletions

diff --git a/engine/.gitignore b/engine/.gitignore
new file mode 100644
index 0000000..96ef6c0
--- /dev/null
+++ b/engine/.gitignore
@@ -0,0 +1,2 @@
+/target
+Cargo.lock
diff --git a/engine/Cargo.toml b/engine/Cargo.toml
new file mode 100644
index 0000000..87410c5
--- /dev/null
+++ b/engine/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "engine"
+version = "0.1.0"
+authors = ["botahamec"]
+edition = "2018"
+publish = false
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+model = {path = "../model"}
+parking_lot = "0.12"
+
+[dev-dependencies]
+criterion = "0.5"
\ No newline at end of file
diff --git a/engine/src/eval.rs b/engine/src/eval.rs
new file mode 100644
index 0000000..a3265bf
--- /dev/null
+++ b/engine/src/eval.rs
@@ -0,0 +1,145 @@
+use std::{mem::MaybeUninit, num::NonZeroU8, ops::Neg};
+
+use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
+
+use crate::transposition_table::TranspositionTableRef;
+
+const KING_WORTH: u32 = 2;
+
+fn eval_position(board: CheckersBitBoard) -> f32 {
+	let light_pieces = board.pieces_bits() & !board.color_bits();
+	let dark_pieces = board.pieces_bits() & board.color_bits();
+
+	let light_peasants = light_pieces & !board.king_bits();
+	let dark_peasants = dark_pieces & !board.king_bits();
+
+	let light_kings = light_pieces & board.king_bits();
+	let dark_kings = dark_pieces & board.king_bits();
+
+	// if we assume the black player doesn't exist, how good is this for white?
+	let light_eval =
+		(light_peasants.count_ones() as f32) + ((light_kings.count_ones() * KING_WORTH) as f32);
+	let dark_eval =
+		(dark_peasants.count_ones() as f32) + ((dark_kings.count_ones() * KING_WORTH) as f32);
+
+	// avoiding a divide by zero error
+	if dark_eval + light_eval != 0.0 {
+		(dark_eval - light_eval) / (dark_eval + light_eval)
+	} else {
+		0.0
+	}
+}
+
+fn eval_jumps(
+	mut alpha: f32,
+	beta: f32,
+	board: CheckersBitBoard,
+	table: TranspositionTableRef,
+) -> f32 {
+	// todo stop checking for jumps twice, but also don't look for slides if there are no jumps
+	if PossibleMoves::has_jumps(board) {
+		// todo check if this is useful
+		// todo make a board for the other player's turn reusable
+
+		let turn = board.turn();
+		let mut best_eval = f32::NEG_INFINITY;
+		let moves = PossibleMoves::moves(board);
+
+		if moves.is_empty() {
+			return -1.0;
+		}
+
+		for current_move in moves {
+			let board = unsafe { current_move.apply_to(board) };
+			let current_eval = if board.turn() != turn {
+				-eval_jumps(-beta, -alpha, board, table)
+			} else {
+				eval_jumps(alpha, beta, board, table)
+			};
+
+			table.insert(board, current_eval, unsafe { NonZeroU8::new_unchecked(1) });
+
+			if current_eval >= beta {
+				return beta;
+			}
+
+			if best_eval < current_eval {
+				best_eval = current_eval;
+			}
+			if alpha < best_eval {
+				alpha = best_eval;
+			}
+		}
+
+		best_eval
+	} else if board.turn() == PieceColor::Dark {
+		eval_position(board)
+	} else {
+		-eval_position(board)
+	}
+}
+
+unsafe fn sort_moves(
+	a: &Move,
+	b: &Move,
+	board: CheckersBitBoard,
+	table: TranspositionTableRef,
+) -> std::cmp::Ordering {
+	let a_entry = table.get_any_depth(a.apply_to(board)).unwrap_or_default();
+	let b_entry = table.get_any_depth(b.apply_to(board)).unwrap_or_default();
+	a_entry.total_cmp(&b_entry)
+}
+
+pub fn negamax(
+	depth: u8,
+	mut alpha: f32,
+	beta: f32,
+	board: CheckersBitBoard,
+	table: TranspositionTableRef,
+) -> f32 {
+	if depth < 1 {
+		if board.turn() == PieceColor::Dark {
+			eval_position(board)
+		} else {
+			-eval_position(board)
+		}
+	} else {
+		if let Some(entry) = table.get(board, depth) {
+			return entry;
+		}
+
+		let turn = board.turn();
+		let mut best_eval = f32::NEG_INFINITY;
+		let mut moves: Vec<Move> = PossibleMoves::moves(board).into_iter().collect();
+		moves.sort_unstable_by(|a, b| unsafe { sort_moves(a, b, board, table) });
+
+		if moves.is_empty() {
+			return -1.0;
+		}
+
+		for current_move in moves {
+			let board = unsafe { current_move.apply_to(board) };
+			let current_eval = if board.turn() == turn {
+				negamax(depth - 1, alpha, beta, board, table)
+			} else {
+				-negamax(depth - 1, -beta, -alpha, board, table)
+			};
+
+			if best_eval < current_eval {
+				best_eval = current_eval;
+			}
+
+			if alpha < best_eval {
+				alpha = best_eval;
+			}
+
+			if alpha >= beta {
+				return best_eval;
+			}
+		}
+
+		table.insert(board, best_eval, unsafe { NonZeroU8::new_unchecked(depth) });
+
+		best_eval
+	}
+}
diff --git a/engine/src/lib.rs b/engine/src/lib.rs
new file mode 100644
index 0000000..06f0818
--- /dev/null
+++ b/engine/src/lib.rs
@@ -0,0 +1,9 @@
+#![feature(new_uninit)]
+#![feature(get_mut_unchecked)]
+
+pub use eval::negamax;
+pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
+pub use transposition_table::{TranspositionTable, TranspositionTableRef};
+
+mod eval;
+mod transposition_table;
diff --git a/engine/src/main.rs b/engine/src/main.rs
new file mode 100644
index 0000000..59002ec
--- /dev/null
+++ b/engine/src/main.rs
@@ -0,0 +1,22 @@
+use engine::{negamax, CheckersBitBoard, TranspositionTable};
+
+const DEPTH: u8 = 18;
+
+fn main() {
+	let board = CheckersBitBoard::starting_position();
+	let mut table = TranspositionTable::new(50_000);
+	let mut alpha = -1.0;
+	let mut beta = 1.0;
+	for i in 0..DEPTH {
+		let mut eval = negamax(i, alpha, beta, board, table.mut_ref());
+
+		if (eval <= alpha) || (eval >= beta) {
+			eval = negamax(i, -1.0, 1.0, board, table.mut_ref());
+		}
+
+		alpha = f32::max(eval + 0.125, -1.0);
+		beta = f32::min(eval + 0.125, 1.0);
+	}
+
+	println!("{:?}", negamax(DEPTH, alpha, beta, board, table.mut_ref(),));
+}
diff --git a/engine/src/transposition_table.rs b/engine/src/transposition_table.rs
new file mode 100644
index 0000000..2b56a66
--- /dev/null
+++ b/engine/src/transposition_table.rs
@@ -0,0 +1,157 @@
+use crate::CheckersBitBoard;
+use parking_lot::RwLock;
+use std::num::NonZeroU8;
+
+#[derive(Copy, Clone, Debug)]
+struct TranspositionTableEntry {
+	board: CheckersBitBoard,
+	eval: f32,
+	depth: NonZeroU8,
+}
+
+impl TranspositionTableEntry {
+	const fn new(board: CheckersBitBoard, eval: f32, depth: NonZeroU8) -> Self {
+		Self { board, eval, depth }
+	}
+}
+
+pub struct TranspositionTable {
+	replace_table: Box<[RwLock<Option<TranspositionTableEntry>>]>,
+	depth_table: Box<[RwLock<Option<TranspositionTableEntry>>]>,
+}
+
+#[derive(Copy, Clone, Debug)]
+pub struct TranspositionTableRef<'a> {
+	replace_table: &'a [RwLock<Option<TranspositionTableEntry>>],
+	depth_table: &'a [RwLock<Option<TranspositionTableEntry>>],
+}
+
+impl<'a> TranspositionTableRef<'a> {
+	pub fn get(self, board: CheckersBitBoard, depth: u8) -> Option<f32> {
+		let table_len = self.replace_table.as_ref().len();
+
+		// try the replace table
+		let entry = unsafe {
+			self.replace_table
+				.as_ref()
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.read()
+		};
+		if let Some(entry) = *entry {
+			if entry.board == board && entry.depth.get() >= depth {
+				return Some(entry.eval);
+			}
+		}
+
+		// try the depth table
+		let entry = unsafe {
+			self.depth_table
+				.as_ref()
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.read()
+		};
+		match *entry {
+			Some(entry) => {
+				if entry.board == board {
+					if entry.depth.get() >= depth {
+						Some(entry.eval)
+					} else {
+						None
+					}
+				} else {
+					None
+				}
+			}
+			None => None,
+		}
+	}
+
+	pub fn get_any_depth(self, board: CheckersBitBoard) -> Option<f32> {
+		let table_len = self.replace_table.as_ref().len();
+
+		// try the depth table
+		let entry = unsafe {
+			self.depth_table
+				.as_ref()
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.read()
+		};
+		if let Some(entry) = *entry {
+			if entry.board == board {
+				return Some(entry.eval);
+			}
+		}
+
+		// try the replace table
+		let entry = unsafe {
+			self.replace_table
+				.as_ref()
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.read()
+		};
+		match *entry {
+			Some(entry) => {
+				if entry.board == board {
+					Some(entry.eval)
+				} else {
+					None
+				}
+			}
+			None => None,
+		}
+	}
+
+	pub fn insert(&self, board: CheckersBitBoard, eval: f32, depth: NonZeroU8) {
+		let table_len = self.replace_table.as_ref().len();
+
+		// insert to the replace table
+		let mut entry = unsafe {
+			self.replace_table
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.write()
+		};
+		*entry = Some(TranspositionTableEntry::new(board, eval, depth));
+
+		// insert to the depth table, only if the new depth is higher
+		let mut entry = unsafe {
+			self.depth_table
+				.get_unchecked(board.hash_code() as usize % table_len)
+				.write()
+		};
+		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)),
+		}
+	}
+}
+
+impl TranspositionTable {
+	pub fn new(table_size: usize) -> Self {
+		let mut replace_table = Box::new_uninit_slice(table_size / 2);
+		let mut depth_table = Box::new_uninit_slice(table_size / 2);
+
+		for entry in replace_table.iter_mut() {
+			entry.write(RwLock::new(None));
+		}
+
+		for entry in depth_table.iter_mut() {
+			entry.write(RwLock::new(None));
+		}
+
+		Self {
+			replace_table: unsafe { replace_table.assume_init() },
+			depth_table: unsafe { depth_table.assume_init() },
+		}
+	}
+
+	pub fn mut_ref(&mut self) -> TranspositionTableRef {
+		TranspositionTableRef {
+			replace_table: &self.replace_table,
+			depth_table: &self.depth_table,
+		}
+	}
+}