Engine API

5 files changed, 381 insertions, 116 deletions

diff --git a/engine/src/eval.rs b/engine/src/eval.rs
index 5754343..4d7d540 100644
--- a/engine/src/eval.rs
+++ b/engine/src/eval.rs
@@ -1,12 +1,15 @@
-use std::{
-	fmt::{Debug, Display},
-	num::NonZeroU8,
-	ops::Neg,
-};
+use std::fmt::{Debug, Display};
+use std::num::NonZeroU8;
+use std::ops::Neg;
+use std::sync::atomic::AtomicBool;
+use std::sync::Arc;
+use std::time::Instant;
 
 use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
 
-use crate::{lazysort::LazySort, transposition_table::TranspositionTableRef};
+use crate::lazysort::LazySort;
+use crate::transposition_table::TranspositionTableRef;
+use crate::{EvaluationTask, Frontend};
 
 const KING_WORTH: u32 = 2;
 
@@ -131,55 +134,6 @@ fn eval_position(board: CheckersBitBoard) -> Evaluation {
 	}
 }
 
-fn eval_jumps(
-	mut alpha: Evaluation,
-	beta: Evaluation,
-	board: CheckersBitBoard,
-	table: TranspositionTableRef,
-) -> Evaluation {
-	// 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 = Evaluation::LOSS;
-		let moves = PossibleMoves::moves(board);
-
-		if moves.is_empty() {
-			return Evaluation::LOSS;
-		}
-
-		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).increment()
-			} else {
-				eval_jumps(alpha, beta, board, table).increment()
-			};
-
-			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,
 	board: CheckersBitBoard,
@@ -195,38 +149,58 @@ pub fn negamax(
 	mut alpha: Evaluation,
 	beta: Evaluation,
 	board: CheckersBitBoard,
-	table: TranspositionTableRef,
-) -> Evaluation {
+	allowed_moves: Option<Arc<[Move]>>,
+	cancel_flag: &AtomicBool,
+	task: &EvaluationTask,
+) -> (Evaluation, Option<Move>) {
+	task.nodes_explored
+		.fetch_add(1, std::sync::atomic::Ordering::Release);
+
 	if depth < 1 {
 		if board.turn() == PieceColor::Dark {
-			eval_position(board)
+			(eval_position(board), None)
 		} else {
-			-eval_position(board)
+			(-eval_position(board), None)
 		}
 	} else {
+		let table = task.transposition_table;
 		if let Some(entry) = table.get(board, depth) {
-			return entry;
+			return (entry, None);
 		}
 
 		let turn = board.turn();
-		let mut best_eval = Evaluation::LOSS;
-		let moves: Box<[Move]> = PossibleMoves::moves(board).into_iter().collect();
+		let mut best_eval = Evaluation::NULL_MIN;
+		let mut best_move = None;
+		let moves: Arc<[Move]> = if let Some(moves) = allowed_moves {
+			moves
+		} else {
+			PossibleMoves::moves(board).into_iter().collect()
+		};
 
 		if moves.is_empty() {
-			return Evaluation::LOSS;
+			return (Evaluation::LOSS, None);
 		}
 
-		let sorter = LazySort::new(moves, |m| unsafe { sort_moves(m, board, table) });
+		let sorter = LazySort::new(&moves, |m| unsafe { sort_moves(m, board, table) });
 		for current_move in sorter.into_iter() {
+			if cancel_flag.load(std::sync::atomic::Ordering::Acquire) {
+				return (best_eval, best_move);
+			}
+
 			let board = unsafe { current_move.apply_to(board) };
 			let current_eval = if board.turn() == turn {
-				negamax(depth - 1, alpha, beta, board, table).increment()
+				negamax(depth - 1, alpha, beta, board, None, cancel_flag, task)
+					.0
+					.increment()
 			} else {
-				-negamax(depth - 1, -beta, -alpha, board, table).increment()
+				-negamax(depth - 1, -beta, -alpha, board, None, cancel_flag, task)
+					.0
+					.increment()
 			};
 
 			if best_eval < current_eval {
 				best_eval = current_eval;
+				best_move = Some(current_move);
 			}
 
 			if alpha < best_eval {
@@ -234,28 +208,90 @@ pub fn negamax(
 			}
 
 			if alpha >= beta {
-				return best_eval;
+				return (best_eval, best_move);
 			}
 		}
 
 		table.insert(board, best_eval, unsafe { NonZeroU8::new_unchecked(depth) });
 
-		best_eval
+		(best_eval, best_move)
 	}
 }
 
-pub fn current_evaluation(
-	depth: u8,
-	board: CheckersBitBoard,
-	table: TranspositionTableRef,
-) -> Evaluation {
+pub fn evaluate(task: Arc<EvaluationTask>, frontend: &dyn Frontend) -> Evaluation {
+	let board = task.position;
+	let cancel_flag = &task.cancel_flag;
+
+	let allowed_moves = task.allowed_moves.clone();
+	let limits = task.limits;
+	let max_depth = limits.depth;
+	let max_nodes = limits.nodes;
+	let max_time = limits.time.map(|d| Instant::now() + d.div_f32(2.0));
+
 	let mut alpha = Evaluation::NULL_MIN;
 	let mut beta = Evaluation::NULL_MAX;
-	for i in 0..depth {
-		let mut eval = negamax(i, alpha, beta, board, table);
+	let mut depth = 0;
+	let mut eval = Evaluation::DRAW;
+	let mut best_move = None;
+	loop {
+		if let Some(max_depth) = max_depth {
+			if depth > max_depth.get() {
+				break;
+			}
+		}
+
+		if let Some(max_time) = max_time {
+			if Instant::now() > max_time {
+				break;
+			}
+		}
+
+		if let Some(max_nodes) = max_nodes {
+			if task
+				.nodes_explored
+				.load(std::sync::atomic::Ordering::Acquire)
+				> max_nodes.get()
+			{
+				break;
+			}
+		}
+
+		let em = negamax(
+			depth,
+			alpha,
+			beta,
+			board,
+			allowed_moves.clone(),
+			cancel_flag,
+			&task,
+		);
+
+		// prevent incomplete search from overwriting evaluation
+		if cancel_flag.load(std::sync::atomic::Ordering::Acquire) {
+			break;
+		}
+
+		eval = em.0;
+		best_move = em.1;
 
 		while (eval <= alpha) || (eval >= beta) {
-			eval = negamax(i, alpha, beta, board, table);
+			let em = negamax(
+				depth,
+				alpha,
+				beta,
+				board,
+				allowed_moves.clone(),
+				cancel_flag,
+				&task,
+			);
+
+			// prevent incomplete search from overwriting evaluation
+			if cancel_flag.load(std::sync::atomic::Ordering::Acquire) {
+				break;
+			}
+
+			eval = em.0;
+			best_move = em.1;
 
 			if eval <= alpha {
 				alpha = Evaluation::NULL_MIN;
@@ -275,40 +311,46 @@ pub fn current_evaluation(
 		} else {
 			beta = eval.add(0.125);
 		}
-	}
 
-	let mut eval = negamax(depth, alpha, beta, board, table);
-	if (eval <= alpha) || (eval >= beta) {
-		eval = negamax(
-			depth,
-			Evaluation::NULL_MIN,
-			Evaluation::NULL_MAX,
-			board,
-			table,
-		);
+		depth += 1;
 	}
-	eval
-}
 
-pub fn best_move(depth: u8, board: CheckersBitBoard, table: TranspositionTableRef) -> Move {
-	let moves = PossibleMoves::moves(board).into_iter();
-	let mut best_move = None;
-	let mut best_eval = Evaluation::NULL_MIN;
-	for current_move in moves {
-		let current_board = unsafe { current_move.apply_to(board) };
-		let current_eval = if board.turn() == current_board.turn() {
-			current_evaluation(depth - 1, current_board, table)
-		} else {
-			-current_evaluation(depth - 1, current_board, table)
-		};
-
-		if current_eval >= best_eval {
-			best_eval = current_eval;
-			best_move = Some(current_move);
+	// ponder
+	if let Some(best_move) = best_move {
+		// If the best move has not been found yet, then no move will be
+		// reported. This should be very rare. This technically is not allowed
+		// by the UCI specification, but if someone stops it this quickly, they
+		// probably didn't care about the best move anyway.
+		frontend.report_best_move(best_move);
+
+		if task.ponder {
+			let board = unsafe { best_move.apply_to(board) };
+
+			let mut depth = 0;
+			loop {
+				if task
+					.end_ponder_flag
+					.load(std::sync::atomic::Ordering::Acquire)
+				{
+					break;
+				}
+
+				negamax(
+					depth,
+					Evaluation::NULL_MIN,
+					Evaluation::NULL_MAX,
+					board,
+					None,
+					&task.end_ponder_flag,
+					&task,
+				);
+
+				depth += 1;
+			}
 		}
 	}
 
-	best_move.unwrap()
+	eval
 }
 
 #[cfg(test)]
diff --git a/engine/src/lazysort.rs b/engine/src/lazysort.rs
index e2d6a3f..bec372c 100644
--- a/engine/src/lazysort.rs
+++ b/engine/src/lazysort.rs
@@ -10,10 +10,10 @@ pub struct LazySortIter<T, F: Fn(&T) -> R, R: Ord> {
 	index: usize,
 }
 
-impl<T, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
-	pub fn new(collection: Box<[T]>, sort_by: F) -> Self {
+impl<T: Clone, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
+	pub fn new(collection: &[T], sort_by: F) -> Self {
 		Self {
-			collection,
+			collection: collection.into(),
 			sort_by,
 			sorted: 0,
 		}
diff --git a/engine/src/lib.rs b/engine/src/lib.rs
index 6cb7e33..6a12b83 100644
--- a/engine/src/lib.rs
+++ b/engine/src/lib.rs
@@ -1,7 +1,15 @@
 #![feature(new_uninit)]
-#![feature(get_mut_unchecked)]
 
-pub use eval::{best_move, current_evaluation, negamax};
+use std::num::{NonZeroU8, NonZeroUsize};
+use std::sync::atomic::{AtomicBool, AtomicU8, AtomicUsize, Ordering};
+use std::sync::Arc;
+use std::thread::JoinHandle;
+use std::time::{Duration, Instant};
+
+use parking_lot::Mutex;
+
+use eval::{evaluate, Evaluation};
+
 pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
 pub use transposition_table::{TranspositionTable, TranspositionTableRef};
 
@@ -9,3 +17,216 @@ mod eval;
 mod lazysort;
 mod tablebase;
 mod transposition_table;
+
+pub const ENGINE_NAME: &str = "Ampere";
+pub const ENGINE_AUTHOR: &str = "Mica White";
+
+pub struct Engine<'a> {
+	position: Mutex<CheckersBitBoard>,
+	transposition_table: TranspositionTable,
+
+	debug: AtomicBool,
+	frontend: &'a dyn Frontend,
+
+	current_thread: Mutex<Option<JoinHandle<Evaluation>>>,
+	current_task: Mutex<Option<Arc<EvaluationTask<'a>>>>,
+	pondering_task: Mutex<Option<Arc<EvaluationTask<'a>>>>,
+}
+
+struct EvaluationTask<'a> {
+	position: CheckersBitBoard,
+	transposition_table: TranspositionTableRef<'a>,
+	allowed_moves: Option<Arc<[Move]>>,
+	limits: ActualLimit,
+	ponder: bool,
+	cancel_flag: AtomicBool,
+	end_ponder_flag: AtomicBool,
+
+	start_time: Instant,
+	current_depth: AtomicU8,
+	selective_depth: AtomicU8,
+	nodes_explored: AtomicUsize,
+	principle_variation: Mutex<Vec<Move>>,
+}
+
+#[derive(Debug, Default, Clone)]
+pub struct EvaluationSettings {
+	pub restrict_moves: Option<Arc<[Move]>>,
+	pub ponder: bool,
+	pub clock: Clock,
+	pub search_until: SearchLimit,
+}
+
+impl EvaluationSettings {
+	fn get_limits(&self, this_color: PieceColor) -> ActualLimit {
+		match &self.search_until {
+			SearchLimit::Infinite => ActualLimit::default(),
+			SearchLimit::Limited(limit) => *limit,
+			SearchLimit::Auto => ActualLimit {
+				nodes: None,
+				depth: NonZeroU8::new(30),
+				time: Some(self.clock.recommended_time(this_color)),
+			},
+		}
+	}
+}
+
+#[derive(Debug, Clone)]
+pub enum Clock {
+	Unlimited,
+	TimePerMove(Duration),
+	ChessClock {
+		white_time_remaining: Duration,
+		black_time_remaining: Duration,
+		white_increment: Duration,
+		black_increment: Duration,
+		moves_until_next_time_control: Option<(u32, Duration)>,
+	},
+}
+
+impl Clock {
+	fn recommended_time(&self, this_color: PieceColor) -> Duration {
+		match self {
+			Self::Unlimited => Duration::from_secs(60 * 5), // 5 minutes
+			Self::TimePerMove(time) => *time,
+			Self::ChessClock {
+				white_time_remaining,
+				black_time_remaining,
+				white_increment,
+				black_increment,
+				moves_until_next_time_control,
+			} => {
+				let my_time = match this_color {
+					PieceColor::Dark => black_time_remaining,
+					PieceColor::Light => white_time_remaining,
+				};
+				let my_increment = match this_color {
+					PieceColor::Dark => black_increment,
+					PieceColor::Light => white_increment,
+				};
+
+				// TODO this could certainly be better
+				let moves_to_go = moves_until_next_time_control.map(|m| m.0).unwrap_or(50);
+
+				(my_time.checked_div(moves_to_go).unwrap_or(*my_time) + *my_increment).div_f32(1.25)
+			}
+		}
+	}
+}
+
+impl Default for Clock {
+	fn default() -> Self {
+		Self::TimePerMove(Duration::from_secs(60 * 5))
+	}
+}
+
+#[derive(Debug, Default, Clone)]
+pub enum SearchLimit {
+	#[default]
+	Auto,
+	Infinite,
+	Limited(ActualLimit),
+}
+
+#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
+pub struct ActualLimit {
+	nodes: Option<NonZeroUsize>,
+	depth: Option<NonZeroU8>,
+	time: Option<Duration>,
+}
+
+pub trait Frontend: Sync {
+	fn debug(&self, msg: &str);
+
+	fn report_best_move(&self, best_move: Move);
+}
+
+impl<'a> Engine<'a> {
+	pub fn new(transposition_table_size: usize, frontend: &'a dyn Frontend) -> Self {
+		Self {
+			position: Mutex::new(CheckersBitBoard::starting_position()),
+			transposition_table: TranspositionTable::new(transposition_table_size),
+
+			debug: AtomicBool::new(false),
+			frontend,
+
+			current_thread: Mutex::new(None),
+			current_task: Mutex::new(None),
+			pondering_task: Mutex::new(None),
+		}
+	}
+
+	pub fn set_debug(&self, debug: bool) {
+		self.debug.store(debug, Ordering::Release);
+	}
+
+	pub fn reset_position(&self) {
+		self.set_position(CheckersBitBoard::starting_position())
+	}
+
+	pub fn set_position(&self, position: CheckersBitBoard) {
+		let mut position_ptr = self.position.lock();
+		*position_ptr = position;
+	}
+
+	pub fn start_evaluation(&'static self, settings: EvaluationSettings) {
+		// finish the pondering thread
+		let mut pondering_task = self.pondering_task.lock();
+		if let Some(task) = pondering_task.take() {
+			task.end_ponder_flag.store(true, Ordering::Release);
+		}
+
+		let position = *self.position.lock();
+		let transposition_table = self.transposition_table.get_ref();
+		let limits = settings.get_limits(position.turn());
+		let allowed_moves = settings.restrict_moves;
+		let ponder = settings.ponder;
+		let cancel_flag = AtomicBool::new(false);
+		let end_ponder_flag = AtomicBool::new(false);
+
+		let start_time = Instant::now();
+		let current_depth = AtomicU8::new(0);
+		let selective_depth = AtomicU8::new(0);
+		let nodes_explored = AtomicUsize::new(0);
+		let principle_variation = Mutex::new(Vec::new());
+
+		let task = EvaluationTask {
+			position,
+			transposition_table,
+			allowed_moves,
+			limits,
+			ponder,
+			cancel_flag,
+			end_ponder_flag,
+
+			start_time,
+			current_depth,
+			selective_depth,
+			nodes_explored,
+			principle_variation,
+		};
+
+		let task = Arc::new(task);
+		let task_ref = task.clone();
+		let mut task_ptr = self.current_task.lock();
+		*task_ptr = Some(task);
+
+		if ponder {
+			let mut pondering_task = self.pondering_task.lock();
+			*pondering_task = Some(task_ref.clone());
+		}
+
+		let thread = std::thread::spawn(move || evaluate(task_ref, self.frontend));
+		let mut thread_ptr = self.current_thread.lock();
+		*thread_ptr = Some(thread);
+	}
+
+	pub fn stop_evaluation(&self) -> Option<()> {
+		let current_task = self.current_task.lock().take()?;
+		current_task.cancel_flag.store(true, Ordering::Release);
+
+		self.current_thread.lock().take();
+
+		Some(())
+	}
+}
diff --git a/engine/src/main.rs b/engine/src/main.rs
index 8e438fd..afc132f 100644
--- a/engine/src/main.rs
+++ b/engine/src/main.rs
@@ -1,4 +1,4 @@
-use engine::{current_evaluation, CheckersBitBoard, TranspositionTable};
+use engine::{CheckersBitBoard, TranspositionTable};
 use mimalloc::MiMalloc;
 
 #[global_allocator]
@@ -7,7 +7,7 @@ static ALLOCATOR: MiMalloc = MiMalloc;
 const DEPTH: u8 = 18;
 
 fn main() {
-	let board = CheckersBitBoard::starting_position();
-	let mut table = TranspositionTable::new(50_000);
-	println!("{}", current_evaluation(DEPTH, board, table.mut_ref()));
+	//let board = CheckersBitBoard::starting_position();
+	//let mut table = TranspositionTable::new(50_000);
+	//println!("{}", current_evaluation(DEPTH, board, table.get_ref()));
 }
diff --git a/engine/src/transposition_table.rs b/engine/src/transposition_table.rs
index 96b3809..9fc16d0 100644
--- a/engine/src/transposition_table.rs
+++ b/engine/src/transposition_table.rs
@@ -131,8 +131,10 @@ impl<'a> TranspositionTableRef<'a> {
 
 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);
+		let table_size =
+			table_size / 2 / std::mem::size_of::<RwLock<Option<TranspositionTableEntry>>>();
+		let mut replace_table = Box::new_uninit_slice(table_size);
+		let mut depth_table = Box::new_uninit_slice(table_size);
 
 		for entry in replace_table.iter_mut() {
 			entry.write(RwLock::new(None));
@@ -148,7 +150,7 @@ impl TranspositionTable {
 		}
 	}
 
-	pub fn mut_ref(&mut self) -> TranspositionTableRef {
+	pub fn get_ref(&self) -> TranspositionTableRef {
 		TranspositionTableRef {
 			replace_table: &self.replace_table,
 			depth_table: &self.depth_table,