From 207bafde1fa2468d666c7ac894eebee1cf95bed2 Mon Sep 17 00:00:00 2001 From: Micha White Date: Thu, 21 Dec 2023 16:33:09 -0500 Subject: Engine API --- engine/src/eval.rs | 250 ++++++++++++++++++++++---------------- engine/src/lazysort.rs | 6 +- engine/src/lib.rs | 225 +++++++++++++++++++++++++++++++++- engine/src/main.rs | 8 +- engine/src/transposition_table.rs | 8 +- ui/src/main.rs | 14 +-- 6 files changed, 385 insertions(+), 126 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>, + cancel_flag: &AtomicBool, + task: &EvaluationTask, +) -> (Evaluation, Option) { + 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, 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 R, R: Ord> { index: usize, } -impl R, R: Ord> LazySort { - pub fn new(collection: Box<[T]>, sort_by: F) -> Self { +impl R, R: Ord> LazySort { + 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, + transposition_table: TranspositionTable, + + debug: AtomicBool, + frontend: &'a dyn Frontend, + + current_thread: Mutex>>, + current_task: Mutex>>>, + pondering_task: Mutex>>>, +} + +struct EvaluationTask<'a> { + position: CheckersBitBoard, + transposition_table: TranspositionTableRef<'a>, + allowed_moves: Option>, + 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>, +} + +#[derive(Debug, Default, Clone)] +pub struct EvaluationSettings { + pub restrict_moves: Option>, + 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, + depth: Option, + time: Option, +} + +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::>>(); + 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, diff --git a/ui/src/main.rs b/ui/src/main.rs index 43191e5..7ce364e 100644 --- a/ui/src/main.rs +++ b/ui/src/main.rs @@ -82,11 +82,8 @@ 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) }; - let evaluation = engine::current_evaluation( - 7, - self.bit_board, - self.transposition_table.mut_ref(), - ); + let evaluation = + engine::evaluate(7, self.bit_board, self.transposition_table.mut_ref()); println!("AI advantage: {}", evaluation); // ai makes a move @@ -103,11 +100,8 @@ impl State for GameState { self.selected_square = None; self.possible_moves.clear(); - let evaluation = engine::current_evaluation( - 7, - self.bit_board, - self.transposition_table.mut_ref(), - ); + let evaluation = + engine::evaluate(7, self.bit_board, self.transposition_table.mut_ref()); println!("Your advantage: {}", evaluation); } else { self.selected_square = Some(square); -- cgit v1.2.3