From fdb2804883deb31e3aeb15bbe588dcc9b7b76bd0 Mon Sep 17 00:00:00 2001 From: Mica White Date: Mon, 8 Dec 2025 19:56:48 -0500 Subject: Stuff --- engine/src/c_abi.rs | 403 ++++++++++++++++++++++++++++ engine/src/engine.rs | 548 +++++++++++++++++++------------------- engine/src/eval.rs | 331 ++++++++++++----------- engine/src/info.rs | 27 ++ engine/src/lazysort.rs | 174 ++++++------ engine/src/lib.rs | 38 +-- engine/src/main.rs | 141 ++++++---- engine/src/search.rs | 530 ++++++++++++++++++------------------ engine/src/tablebase.rs | 372 +++++++++++++------------- engine/src/transposition_table.rs | 354 ++++++++++++------------ 10 files changed, 1707 insertions(+), 1211 deletions(-) create mode 100755 engine/src/c_abi.rs mode change 100644 => 100755 engine/src/engine.rs mode change 100644 => 100755 engine/src/eval.rs create mode 100755 engine/src/info.rs mode change 100644 => 100755 engine/src/lazysort.rs mode change 100644 => 100755 engine/src/lib.rs mode change 100644 => 100755 engine/src/main.rs mode change 100644 => 100755 engine/src/search.rs mode change 100644 => 100755 engine/src/tablebase.rs mode change 100644 => 100755 engine/src/transposition_table.rs (limited to 'engine/src') diff --git a/engine/src/c_abi.rs b/engine/src/c_abi.rs new file mode 100755 index 0000000..6a7f35f --- /dev/null +++ b/engine/src/c_abi.rs @@ -0,0 +1,403 @@ +use core::ffi::{c_int, c_ulonglong}; +use std::ffi::CString; +use std::num::{NonZeroU8, NonZeroUsize}; +use std::sync::atomic::AtomicBool; +use std::time::Duration; + +use model::{CheckersBitBoard, Move, MoveDirection, PieceColor}; + +use crate::{ + ActualLimit, Clock, Engine, EvalInfo, Evaluation, EvaluationSettings, Frontend, SearchLimit, +}; + +#[repr(C)] +struct CFrontend { + debug_fn: extern "C" fn(*const u8), + info_fn: extern "C" fn(*const EvalInfo), + bestmove_fn: extern "C" fn(*const Move), +} + +impl Frontend for CFrontend { + fn debug(&self, msg: &str) { + (self.debug_fn)(msg.as_bytes().as_ptr()) + } + + fn info(&self, info: EvalInfo) { + (self.info_fn)(&info) + } + + fn report_best_move(&self, best_move: Move) { + (self.bestmove_fn)(&best_move) + } +} + +#[repr(C)] +struct EvalResult { + evaluation: Box, + best_move: Option>, +} + +#[no_mangle] +extern "C" fn ampere_new_engine(hash_size: c_ulonglong, frontend: &CFrontend) -> Box> { + Box::new(Engine::new(hash_size as usize, frontend)) +} + +#[no_mangle] +extern "C" fn ampere_set_debug(engine: &Engine<'_>, debug: bool) { + engine.set_debug(debug) +} + +#[no_mangle] +extern "C" fn ampere_islegal(engine: &Engine<'_>, ampere_move: &Move) -> bool { + engine.is_legal_move(*ampere_move) +} + +#[no_mangle] +extern "C" fn ampere_current_position(engine: &Engine<'_>) -> Box { + Box::new(engine.current_position()) +} + +#[no_mangle] +extern "C" fn ampere_reset_position(engine: &Engine<'_>) { + engine.reset_position(); +} + +#[no_mangle] +extern "C" fn ampere_set_position(engine: &Engine<'_>, board: &CheckersBitBoard) { + engine.set_position(*board); +} + +#[no_mangle] +extern "C" fn ampere_play_move(engine: &Engine<'_>, ampere_move: &Move) -> bool { + engine.apply_move(*ampere_move).is_some() +} + +#[no_mangle] +extern "C" fn ampere_evaluate( + engine: &'static Engine<'_>, + cancel: Option<&AtomicBool>, + nodes: c_int, + depth: c_int, + time: Option<&Clock>, +) -> EvalResult { + let limits = if nodes == 0 && depth == 0 && time.is_none() { + SearchLimit::Auto + } else { + let time = time.cloned().unwrap_or(Clock::Unlimited); + + SearchLimit::Limited(ActualLimit { + nodes: NonZeroUsize::new(nodes as usize), + depth: NonZeroU8::new(depth as u8), + time: Some(time.recommended_time(engine.current_position().turn)), + }) + }; + + let (eval, best) = engine.evaluate( + cancel, + EvaluationSettings { + restrict_moves: None, + ponder: false, + clock: Clock::Unlimited, + search_until: limits, + }, + ); + + let evaluation = Box::new(eval); + let best_move = best.map(Box::new); + + EvalResult { + evaluation, + best_move, + } +} + +#[no_mangle] +extern "C" fn ampere_starteval_limited( + engine: &'static Engine<'_>, + ponder: bool, + nodes: c_int, + depth: c_int, + time: c_int, +) { + let limits = if nodes == 0 && depth == 0 && time == 0 { + SearchLimit::Auto + } else { + let time = if time == 0 { + None + } else { + Some(Duration::from_millis(time as u64)) + }; + + SearchLimit::Limited(ActualLimit { + nodes: NonZeroUsize::new(nodes as usize), + depth: NonZeroU8::new(depth as u8), + time, + }) + }; + + engine.start_evaluation(EvaluationSettings { + restrict_moves: None, + ponder, + clock: Clock::Unlimited, + search_until: limits, + }) +} + +#[no_mangle] +extern "C" fn ampere_starteval_unlimited(engine: &'static Engine<'_>, ponder: bool) { + engine.start_evaluation(EvaluationSettings { + restrict_moves: None, + ponder, + clock: Clock::Unlimited, + search_until: SearchLimit::Infinite, + }) +} + +#[no_mangle] +extern "C" fn ampere_stopeval(engine: &Engine<'_>) -> bool { + engine.stop_evaluation().is_some() +} + +#[no_mangle] +extern "C" fn ampere_destroy_engine(engine: Box>) { + drop(engine) +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_nodes(info: &EvalInfo) -> c_ulonglong { + info.nodes_searched as c_ulonglong +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_evaluation(info: &EvalInfo) -> *const Evaluation { + &info.evaluation +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_bestmove(info: &EvalInfo) -> Option<&Move> { + info.current_best_move.as_ref() +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_depth(info: &EvalInfo) -> c_int { + info.current_depth as c_int +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_nodespersec(info: &EvalInfo) -> c_ulonglong { + info.nodes_per_second() as c_ulonglong +} + +#[no_mangle] +extern "C" fn ampere_evalinfo_elapsed(info: &EvalInfo) -> c_ulonglong { + info.elapsed_milliseconds() as c_ulonglong +} + +#[no_mangle] +extern "C" fn ampere_board_starting_position() -> Box { + Box::new(CheckersBitBoard::starting_position()) +} + +#[no_mangle] +extern "C" fn ampere_board_new( + pieces: u32, + color: u32, + kings: u32, + turn: PieceColor, +) -> Box { + Box::new(CheckersBitBoard::new(pieces, color, kings, turn)) +} + +#[no_mangle] +extern "C" fn ampere_clock_unlimited() -> Box { + Box::new(Clock::Unlimited) +} + +#[no_mangle] +extern "C" fn ampere_clock_timepermove(millis: c_int) -> Box { + Box::new(Clock::TimePerMove(Duration::from_millis(millis as u64))) +} + +#[no_mangle] +extern "C" fn ampere_clock_incremental( + white_time: c_int, + black_time: c_int, + white_inc: c_int, + black_inc: c_int, + moves_to_time_control: c_int, + time_control: c_int, +) -> Box { + let moves_until_next_time_control = if time_control == 0 { + None + } else { + Some(( + moves_to_time_control as u32, + Duration::from_millis(time_control as u64), + )) + }; + + Box::new(Clock::Incremental { + white_time_remaining: Duration::from_millis(white_time as u64), + black_time_remaining: Duration::from_millis(black_time as u64), + white_increment: Duration::from_millis(white_inc as u64), + black_increment: Duration::from_millis(black_inc as u64), + moves_until_next_time_control, + }) +} + +#[no_mangle] +extern "C" fn ampere_clock_destroy(clock: Box) { + drop(clock) +} + +#[no_mangle] +extern "C" fn ampere_board_clone(board: &CheckersBitBoard) -> Box { + Box::new(*board) +} + +#[no_mangle] +extern "C" fn ampere_board_equal(a: &CheckersBitBoard, b: &CheckersBitBoard) -> bool { + *a == *b +} + +#[no_mangle] +extern "C" fn ampere_board_hash(board: &CheckersBitBoard) -> u64 { + board.hash_code() +} + +#[no_mangle] +extern "C" fn ampere_board_pieces(board: &mut CheckersBitBoard) -> &mut u32 { + &mut board.pieces +} + +#[no_mangle] +extern "C" fn ampere_board_colors(board: &mut CheckersBitBoard) -> &mut u32 { + &mut board.color +} + +#[no_mangle] +extern "C" fn ampere_board_kings(board: &mut CheckersBitBoard) -> &mut u32 { + &mut board.kings +} + +#[no_mangle] +extern "C" fn ampere_board_turn(board: &mut CheckersBitBoard) -> &mut PieceColor { + &mut board.turn +} + +#[no_mangle] +extern "C" fn ampere_board_has_piece_at(board: &CheckersBitBoard, square: c_int) -> bool { + board.piece_at(square as usize) +} + +#[no_mangle] +unsafe extern "C" fn ampere_board_color_at(board: &CheckersBitBoard, square: c_int) -> PieceColor { + board.color_at_unchecked(square as usize) +} + +#[no_mangle] +unsafe extern "C" fn ampere_board_king_at(board: &CheckersBitBoard, square: c_int) -> bool { + board.king_at_unchecked(square as usize) +} + +#[no_mangle] +unsafe extern "C" fn ampere_board_move_piece( + board: &mut CheckersBitBoard, + start: c_int, + dest: c_int, +) { + *board = board.move_piece_to_unchecked(start as usize, dest as usize); +} + +#[no_mangle] +extern "C" fn ampere_board_clear_piece(board: &mut CheckersBitBoard, square: c_int) { + *board = board.clear_piece(square as usize); +} + +#[no_mangle] +extern "C" fn ampere_board_destroy(board: Box) { + drop(board) +} + +#[no_mangle] +extern "C" fn ampere_eval_is_force_win(evaluation: &Evaluation) -> bool { + evaluation.is_force_win() +} + +#[no_mangle] +extern "C" fn ampere_eval_is_force_loss(evaluation: &Evaluation) -> bool { + evaluation.is_force_loss() +} + +#[no_mangle] +extern "C" fn ampere_eval_is_force_seq(evaluation: &Evaluation) -> bool { + evaluation.is_force_sequence() +} + +#[no_mangle] +unsafe extern "C" fn ampere_eval_forceseq_len(evaluation: &Evaluation) -> c_int { + evaluation.force_sequence_length().unwrap_unchecked() as c_int +} + +#[no_mangle] +unsafe extern "C" fn ampere_eval_tofloat(evaluation: &Evaluation) -> f32 { + evaluation.to_f32_unchecked() +} + +#[no_mangle] +extern "C" fn ampere_eval_destroy(evaluation: Box) { + drop(evaluation) +} + +#[no_mangle] +extern "C" fn ampere_move_new(start: c_int, direction: MoveDirection, jump: bool) -> Box { + Box::new(Move::new(start as usize, direction, jump)) +} + +#[no_mangle] +extern "C" fn ampere_move_clone(ampere_move: &Move) -> Box { + Box::new(*ampere_move) +} + +#[no_mangle] +extern "C" fn ampere_move_equal(a: &Move, b: &Move) -> bool { + *a == *b +} + +#[no_mangle] +unsafe extern "C" fn ampere_move_string(m: &Move, buffer: *mut u8) { + let buffer = std::slice::from_raw_parts_mut(buffer, 6); + let string = CString::new(m.to_string().as_bytes()).unwrap_unchecked(); + let bytes = string.as_bytes_with_nul(); + buffer[..bytes.len()].copy_from_slice(bytes) +} + +#[no_mangle] +extern "C" fn ampere_move_start(ampere_move: &Move) -> c_int { + ampere_move.start() as c_int +} + +#[no_mangle] +extern "C" fn ampere_move_direction(ampere_move: &Move) -> MoveDirection { + ampere_move.direction() +} + +#[no_mangle] +extern "C" fn ampere_move_is_jump(ampere_move: &Move) -> bool { + ampere_move.is_jump() +} + +#[no_mangle] +unsafe extern "C" fn ampere_move_jump_position(ampere_move: &Move) -> c_int { + ampere_move.jump_position() as c_int +} + +#[no_mangle] +extern "C" fn ampere_move_end(ampere_move: &Move) -> c_int { + ampere_move.end_position() as c_int +} + +#[no_mangle] +extern "C" fn ampere_move_destroy(ampere_move: Box) { + drop(ampere_move) +} diff --git a/engine/src/engine.rs b/engine/src/engine.rs old mode 100644 new mode 100755 index 6402f21..479e0ef --- a/engine/src/engine.rs +++ b/engine/src/engine.rs @@ -1,273 +1,275 @@ -use std::num::{NonZeroU8, NonZeroUsize}; -use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering}; -use std::sync::Arc; -use std::thread::JoinHandle; -use std::time::Duration; - -use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; -use parking_lot::Mutex; - -use crate::eval::Evaluation; -use crate::search::search; -use crate::{TranspositionTable, TranspositionTableRef}; - -pub const ENGINE_NAME: &str = "Ampere"; -pub const ENGINE_AUTHOR: &str = "Mica White"; -pub const ENGINE_ABOUT: &str = "Ampere Checkers Bot v1.0\nCopyright Mica White"; - -type EvalThread = JoinHandle<(Evaluation, Option)>; - -pub struct Engine<'a> { - position: Mutex, - transposition_table: TranspositionTable, - - debug: AtomicBool, - frontend: &'a dyn Frontend, - - current_thread: Mutex>, - current_task: Mutex>>>, - pondering_task: Mutex>>>, -} - -pub struct EvaluationTask<'a> { - pub position: CheckersBitBoard, - pub transposition_table: TranspositionTableRef<'a>, - pub allowed_moves: Option>, - pub limits: ActualLimit, - pub ponder: bool, - pub cancel_flag: AtomicBool, - pub end_ponder_flag: AtomicBool, - - pub nodes_explored: AtomicUsize, -} - -#[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), - Standard { - 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::Standard { - 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)] -#[repr(C)] -pub struct ActualLimit { - pub nodes: Option, - pub depth: Option, - pub 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 is_legal_move(&self, checker_move: Move) -> bool { - let position = self.position.lock(); - PossibleMoves::moves(*position).contains(checker_move) - } - - pub fn current_position(&self) -> CheckersBitBoard { - *self.position.lock() - } - - 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 apply_move(&self, checker_move: Move) -> Option<()> { - unsafe { - if self.is_legal_move(checker_move) { - let mut position = self.position.lock(); - *position = checker_move.apply_to(*position); - Some(()) - } else { - None - } - } - } - - pub fn evaluate( - &self, - cancel: Option<&AtomicBool>, - settings: EvaluationSettings, - ) -> (Evaluation, Option) { - // 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 cancel_flag = AtomicBool::new(false); - let end_ponder_flag = AtomicBool::new(false); - - let nodes_explored = AtomicUsize::new(0); - - let task = EvaluationTask { - position, - transposition_table, - allowed_moves, - limits, - ponder: false, - cancel_flag, - end_ponder_flag, - - nodes_explored, - }; - - search(Arc::new(task), self.frontend, cancel) - } - - 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 nodes_explored = AtomicUsize::new(0); - - let task = EvaluationTask { - position, - transposition_table, - allowed_moves, - limits, - ponder, - cancel_flag, - end_ponder_flag, - - nodes_explored, - }; - - 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 || search(task_ref, self.frontend, None)); - 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); - - let _ = self.current_thread.lock().take()?.join(); - - Some(()) - } -} +use std::num::{NonZeroU8, NonZeroUsize}; +use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering}; +use std::sync::Arc; +use std::thread::JoinHandle; +use std::time::Duration; + +use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; +use parking_lot::Mutex; + +use crate::eval::Evaluation; +use crate::search::search; +use crate::{EvalInfo, TranspositionTable, TranspositionTableRef}; + +pub const ENGINE_NAME: &str = "Ampere"; +pub const ENGINE_AUTHOR: &str = "Mica White"; +pub const ENGINE_ABOUT: &str = "Ampere Checkers Bot v1.0\nCopyright Mica White"; + +type EvalThread = JoinHandle<(Evaluation, Option)>; + +pub struct Engine<'a> { + position: Mutex, + transposition_table: TranspositionTable, + + debug: AtomicBool, + frontend: &'a dyn Frontend, + + current_thread: Mutex>, + current_task: Mutex>>>, + pondering_task: Mutex>>>, +} + +pub struct EvaluationTask<'a> { + pub position: CheckersBitBoard, + pub transposition_table: TranspositionTableRef<'a>, + pub allowed_moves: Option>, + pub limits: ActualLimit, + pub ponder: bool, + pub cancel_flag: AtomicBool, + pub end_ponder_flag: AtomicBool, + + pub nodes_explored: AtomicUsize, +} + +#[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), + Incremental { + white_time_remaining: Duration, + black_time_remaining: Duration, + white_increment: Duration, + black_increment: Duration, + moves_until_next_time_control: Option<(u32, Duration)>, + }, +} + +impl Clock { + pub(crate) fn recommended_time(&self, this_color: PieceColor) -> Duration { + match self { + Self::Unlimited => Duration::from_secs(60 * 5), // 5 minutes + Self::TimePerMove(time) => time.div_f32(2.0), + Self::Incremental { + 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 * 2).unwrap_or(*my_time) + *my_increment + } + } + } +} + +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)] +#[repr(C)] +pub struct ActualLimit { + pub nodes: Option, + pub depth: Option, + pub time: Option, +} + +pub trait Frontend: Sync { + fn debug(&self, msg: &str); + + fn info(&self, info: EvalInfo); + + 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 is_legal_move(&self, checker_move: Move) -> bool { + let position = self.position.lock(); + PossibleMoves::moves(*position).contains(checker_move) + } + + pub fn current_position(&self) -> CheckersBitBoard { + *self.position.lock() + } + + 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 apply_move(&self, checker_move: Move) -> Option<()> { + unsafe { + if self.is_legal_move(checker_move) { + let mut position = self.position.lock(); + *position = checker_move.apply_to(*position); + Some(()) + } else { + None + } + } + } + + pub fn evaluate( + &self, + cancel: Option<&AtomicBool>, + settings: EvaluationSettings, + ) -> (Evaluation, Option) { + // 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 cancel_flag = AtomicBool::new(false); + let end_ponder_flag = AtomicBool::new(false); + + let nodes_explored = AtomicUsize::new(0); + + let task = EvaluationTask { + position, + transposition_table, + allowed_moves, + limits, + ponder: false, + cancel_flag, + end_ponder_flag, + + nodes_explored, + }; + + search(Arc::new(task), self.frontend, cancel) + } + + 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 nodes_explored = AtomicUsize::new(0); + + let task = EvaluationTask { + position, + transposition_table, + allowed_moves, + limits, + ponder, + cancel_flag, + end_ponder_flag, + + nodes_explored, + }; + + 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 || search(task_ref, self.frontend, None)); + 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); + + let _ = self.current_thread.lock().take()?.join(); + + Some(()) + } +} diff --git a/engine/src/eval.rs b/engine/src/eval.rs old mode 100644 new mode 100755 index 94849ce..a666913 --- a/engine/src/eval.rs +++ b/engine/src/eval.rs @@ -1,160 +1,171 @@ -use std::fmt::{self, Display}; -use std::ops::Neg; - -use model::CheckersBitBoard; - -const KING_WORTH: u32 = 2; - -#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct Evaluation(i16); - -impl Display for Evaluation { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - if self.is_force_win() { - write!(f, "+M{}", self.force_sequence_length().unwrap()) - } else if self.is_force_loss() { - write!(f, "-M{}", self.force_sequence_length().unwrap()) - } else { - write!(f, "{:+}", self.to_f32().unwrap()) - } - } -} - -impl Neg for Evaluation { - type Output = Self; - - fn neg(self) -> Self::Output { - Self(-self.0) - } -} - -impl Evaluation { - pub(crate) const NULL_MAX: Self = Self(i16::MAX); - pub(crate) const NULL_MIN: Self = Self(i16::MIN + 1); - - pub const WIN: Self = Self(i16::MAX - 1); - pub const DRAW: Self = Self(0); - pub const LOSS: Self = Self(i16::MIN + 2); - - // last fourteen bits set to 1 - const FORCE_WIN_THRESHOLD: i16 = 0x3FFF; - - pub fn new(eval: f32) -> Self { - if eval >= 1.0 { - return Self::WIN; - } else if eval <= -1.0 { - return Self::LOSS; - } - - Self((eval * 16384.0) as i16) - } - - pub fn to_f32(self) -> Option { - if self.is_force_sequence() { - return None; - } - - Some(self.0 as f32 / 16384.0) - } - - pub fn is_force_win(self) -> bool { - self.0 > Self::FORCE_WIN_THRESHOLD - } - - pub fn is_force_loss(self) -> bool { - self.0 < -Self::FORCE_WIN_THRESHOLD - } - - pub fn is_force_sequence(self) -> bool { - self.is_force_win() || self.is_force_loss() - } - - pub fn force_sequence_length(self) -> Option { - if self == Self::NULL_MAX || self == Self::NULL_MIN { - return None; - } - - if self.is_force_win() { - Some((Self::WIN.0 - self.0) as u8) - } else if self.is_force_loss() { - Some((self.0 - Self::LOSS.0) as u8) - } else { - None - } - } - - pub fn increment(self) -> Self { - if self.is_force_win() { - Self(self.0 - 1) - } else if self.is_force_loss() { - Self(self.0 + 1) - } else { - self - } - } - - pub fn add_f32(self, rhs: f32) -> Self { - let Some(eval) = self.to_f32() else { - return self; - }; - - Self::new(eval + rhs) - } -} - -pub fn eval_position(board: CheckersBitBoard) -> Evaluation { - 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 { - Evaluation::new((dark_eval - light_eval) / (dark_eval + light_eval)) - } else { - Evaluation::DRAW - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn zero_eval() { - let draw = Evaluation::new(0.0); - assert_eq!(draw, Evaluation::DRAW); - assert_eq!(draw.to_f32(), Some(0.0)); - assert_eq!(draw.to_string(), "+0"); - } - - #[test] - fn comparisons() { - assert!(Evaluation::NULL_MAX > Evaluation::WIN); - assert!(Evaluation::WIN > Evaluation::new(0.5)); - assert!(Evaluation::new(0.5) > Evaluation::DRAW); - assert!(Evaluation::DRAW > Evaluation::new(-0.5)); - assert!(Evaluation::new(-0.5) > Evaluation::LOSS); - assert!(Evaluation::LOSS > Evaluation::NULL_MIN); - } - - #[test] - fn negations() { - assert_eq!(-Evaluation::NULL_MAX, Evaluation::NULL_MIN); - assert_eq!(-Evaluation::NULL_MIN, Evaluation::NULL_MAX); - assert_eq!(-Evaluation::WIN, Evaluation::LOSS); - assert_eq!(-Evaluation::LOSS, Evaluation::WIN); - assert_eq!(-Evaluation::DRAW, Evaluation::DRAW); - assert_eq!(-Evaluation::new(0.5), Evaluation::new(-0.5)); - } -} +use std::fmt::{self, Display}; +use std::ops::Neg; + +use model::CheckersBitBoard; + +const KING_WORTH: u32 = 2; + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct Evaluation(i16); + +impl Display for Evaluation { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if self.is_force_win() { + write!(f, "+W{}", self.force_sequence_length().unwrap()) + } else if self.is_force_loss() { + write!(f, "-W{}", self.force_sequence_length().unwrap()) + } else { + write!(f, "{:+}", self.to_f32().unwrap()) + } + } +} + +impl Neg for Evaluation { + type Output = Self; + + fn neg(self) -> Self::Output { + Self(-self.0) + } +} + +impl Evaluation { + pub(crate) const NULL_MAX: Self = Self(i16::MAX); + pub(crate) const NULL_MIN: Self = Self(i16::MIN + 1); + + pub const WIN: Self = Self(i16::MAX - 1); + pub const DRAW: Self = Self(0); + pub const LOSS: Self = Self(i16::MIN + 2); + + // last fourteen bits set to 1 + const FORCE_WIN_THRESHOLD: i16 = 0x3FFF; + // divisor for converting to a float + const MAX_FLOAT: f32 = 16384.0; + + pub fn new(eval: f32) -> Self { + if eval >= 1.0 { + return Self::WIN; + } else if eval <= -1.0 { + return Self::LOSS; + } + + Self((eval * 16384.0) as i16) + } + + pub fn to_f32(self) -> Option { + if self.is_force_sequence() { + return None; + } + + Some(self.0 as f32 / Self::MAX_FLOAT) + } + + /// Converts to an `f32` without checking to see if the game if a force + /// sequence. + /// + /// # Safety + /// Results in undefined behavior if the evaluation is a force sequence + pub unsafe fn to_f32_unchecked(self) -> f32 { + self.0 as f32 / Self::MAX_FLOAT + } + + pub fn is_force_win(self) -> bool { + self.0 > Self::FORCE_WIN_THRESHOLD + } + + pub fn is_force_loss(self) -> bool { + self.0 < -Self::FORCE_WIN_THRESHOLD + } + + pub fn is_force_sequence(self) -> bool { + self.is_force_win() || self.is_force_loss() + } + + pub fn force_sequence_length(self) -> Option { + if self == Self::NULL_MAX || self == Self::NULL_MIN { + return None; + } + + if self.is_force_win() { + Some((Self::WIN.0 - self.0) as u8) + } else if self.is_force_loss() { + Some((self.0 - Self::LOSS.0) as u8) + } else { + None + } + } + + pub fn increment(self) -> Self { + if self.is_force_win() { + Self(self.0 - 1) + } else if self.is_force_loss() { + Self(self.0 + 1) + } else { + self + } + } + + pub fn add_f32(self, rhs: f32) -> Self { + let Some(eval) = self.to_f32() else { + return self; + }; + + Self::new(eval + rhs) + } +} + +pub fn eval_position(board: CheckersBitBoard) -> Evaluation { + 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 { + Evaluation::new((dark_eval - light_eval) / (dark_eval + light_eval)) + } else { + Evaluation::DRAW + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn zero_eval() { + let draw = Evaluation::new(0.0); + assert_eq!(draw, Evaluation::DRAW); + assert_eq!(draw.to_f32(), Some(0.0)); + assert_eq!(draw.to_string(), "+0"); + } + + #[test] + fn comparisons() { + assert!(Evaluation::NULL_MAX > Evaluation::WIN); + assert!(Evaluation::WIN > Evaluation::new(0.5)); + assert!(Evaluation::new(0.5) > Evaluation::DRAW); + assert!(Evaluation::DRAW > Evaluation::new(-0.5)); + assert!(Evaluation::new(-0.5) > Evaluation::LOSS); + assert!(Evaluation::LOSS > Evaluation::NULL_MIN); + } + + #[test] + fn negations() { + assert_eq!(-Evaluation::NULL_MAX, Evaluation::NULL_MIN); + assert_eq!(-Evaluation::NULL_MIN, Evaluation::NULL_MAX); + assert_eq!(-Evaluation::WIN, Evaluation::LOSS); + assert_eq!(-Evaluation::LOSS, Evaluation::WIN); + assert_eq!(-Evaluation::DRAW, Evaluation::DRAW); + assert_eq!(-Evaluation::new(0.5), Evaluation::new(-0.5)); + } +} diff --git a/engine/src/info.rs b/engine/src/info.rs new file mode 100755 index 0000000..4588941 --- /dev/null +++ b/engine/src/info.rs @@ -0,0 +1,27 @@ +use std::marker::PhantomData; +use std::time::Instant; + +use model::Move; + +use crate::Evaluation; + +#[derive(Debug, Clone, Copy)] +pub struct EvalInfo { + pub start_time: Instant, + pub nodes_searched: usize, + pub evaluation: Evaluation, + pub current_best_move: Option, + pub current_depth: u8, + pub(crate) _unused: PhantomData<()>, +} + +impl EvalInfo { + pub fn nodes_per_second(&self) -> usize { + let elapsed = self.start_time.elapsed().as_secs_f64(); + (self.nodes_searched as f64 / elapsed) as usize + } + + pub fn elapsed_milliseconds(self) -> u32 { + self.start_time.elapsed().as_millis() as u32 + } +} diff --git a/engine/src/lazysort.rs b/engine/src/lazysort.rs old mode 100644 new mode 100755 index f028778..9d54fe5 --- a/engine/src/lazysort.rs +++ b/engine/src/lazysort.rs @@ -1,87 +1,87 @@ -use arrayvec::ArrayVec; - -pub struct LazySort R, R: Ord, const CAPACITY: usize> { - collection: ArrayVec, - sorted: usize, - sort_by: F, -} - -pub struct LazySortIter R, R: Ord, const CAPACITY: usize> { - sorter: LazySort, - index: usize, -} - -impl R, R: Ord, const CAPACITY: usize> LazySort { - pub fn new(collection: impl IntoIterator, sort_by: F) -> Self { - Self { - collection: collection.into_iter().collect(), - sort_by, - sorted: 0, - } - } - - pub fn is_empty(&self) -> bool { - self.collection.is_empty() - } -} - -impl R, R: Ord, const CAPACITY: usize> LazySort { - fn sort(&mut self, index: usize) { - let mut min: Option = None; - let mut min_index = None; - for i in index..self.collection.len() { - if let Some(min) = &mut min { - let res = (self.sort_by)(&self.collection[i]); - if res < *min { - *min = res; - min_index = Some(i); - } - } - } - - if let Some(min_index) = min_index { - self.collection.swap(index, min_index); - } - } - - fn sort_between(&mut self, start: usize, end: usize) { - for i in start..=end { - self.sort(i); - } - } - - pub fn get(&mut self, index: usize) -> Option<&T> { - if index >= self.sorted { - self.sort_between(self.sorted, index); - self.sorted = index; - } - - self.collection.get(index) - } -} - -impl R, R: Ord, const CAPACITY: usize> IntoIterator - for LazySort -{ - type IntoIter = LazySortIter; - type Item = T; - - fn into_iter(self) -> Self::IntoIter { - LazySortIter { - sorter: self, - index: 0, - } - } -} - -impl R, R: Ord, const CAPACITY: usize> Iterator - for LazySortIter -{ - type Item = T; - - fn next(&mut self) -> Option { - let r = self.sorter.get(self.index); - self.index += 1; - r.cloned() - } -} +use arrayvec::ArrayVec; + +pub struct LazySort R, R: Ord, const CAPACITY: usize> { + collection: ArrayVec, + sorted: usize, + sort_by: F, +} + +pub struct LazySortIter R, R: Ord, const CAPACITY: usize> { + sorter: LazySort, + index: usize, +} + +impl R, R: Ord, const CAPACITY: usize> LazySort { + pub fn new(collection: impl IntoIterator, sort_by: F) -> Self { + Self { + collection: collection.into_iter().collect(), + sort_by, + sorted: 0, + } + } + + pub fn is_empty(&self) -> bool { + self.collection.is_empty() + } +} + +impl R, R: Ord, const CAPACITY: usize> LazySort { + fn sort(&mut self, index: usize) { + let mut min: Option = None; + let mut min_index = None; + for i in index..self.collection.len() { + if let Some(min) = &mut min { + let res = (self.sort_by)(&self.collection[i]); + if res < *min { + *min = res; + min_index = Some(i); + } + } + } + + if let Some(min_index) = min_index { + self.collection.swap(index, min_index); + } + } + + fn sort_between(&mut self, start: usize, end: usize) { + for i in start..=end { + self.sort(i); + } + } + + pub fn get(&mut self, index: usize) -> Option<&T> { + if index >= self.sorted { + self.sort_between(self.sorted, index); + self.sorted = index; + } + + self.collection.get(index) + } +} + +impl R, R: Ord, const CAPACITY: usize> IntoIterator + for LazySort +{ + type IntoIter = LazySortIter; + type Item = T; + + fn into_iter(self) -> Self::IntoIter { + LazySortIter { + sorter: self, + index: 0, + } + } +} + +impl R, R: Ord, const CAPACITY: usize> Iterator + for LazySortIter +{ + type Item = T; + + fn next(&mut self) -> Option { + let r = self.sorter.get(self.index); + self.index += 1; + r.cloned() + } +} diff --git a/engine/src/lib.rs b/engine/src/lib.rs old mode 100644 new mode 100755 index d87c225..7c5bd7f --- a/engine/src/lib.rs +++ b/engine/src/lib.rs @@ -1,18 +1,20 @@ -#![feature(new_uninit)] -#![feature(maybe_uninit_uninit_array)] -#![feature(maybe_uninit_slice)] - -pub use engine::{ - ActualLimit, Clock, Engine, EvaluationSettings, Frontend, SearchLimit, ENGINE_ABOUT, - ENGINE_AUTHOR, ENGINE_NAME, -}; -pub use eval::Evaluation; -pub use model::{CheckersBitBoard, Move, MoveDirection, Piece, PieceColor, PossibleMoves}; -pub use transposition_table::{TranspositionTable, TranspositionTableRef}; - -pub mod c_abi; -mod engine; -mod eval; -mod lazysort; -mod search; -mod transposition_table; +#![feature(new_uninit)] +#![feature(maybe_uninit_uninit_array)] +#![feature(maybe_uninit_slice)] + +pub use engine::{ + ActualLimit, Clock, Engine, EvaluationSettings, Frontend, SearchLimit, ENGINE_ABOUT, + ENGINE_AUTHOR, ENGINE_NAME, +}; +pub use eval::Evaluation; +pub use info::EvalInfo; +pub use model::{CheckersBitBoard, Move, MoveDirection, Piece, PieceColor, PossibleMoves}; +pub use transposition_table::{TranspositionTable, TranspositionTableRef}; + +mod c_abi; +mod engine; +mod eval; +mod info; +mod lazysort; +mod search; +mod transposition_table; diff --git a/engine/src/main.rs b/engine/src/main.rs old mode 100644 new mode 100755 index d4bcc48..187ff89 --- a/engine/src/main.rs +++ b/engine/src/main.rs @@ -1,58 +1,83 @@ -use std::num::NonZeroU8; - -use engine::{ActualLimit, Engine, EvaluationSettings, Frontend}; -use mimalloc::MiMalloc; -use model::CheckersBitBoard; - -#[global_allocator] -static ALLOCATOR: MiMalloc = MiMalloc; - -const DEPTH: u8 = 19; - -struct BasicFrontend; - -impl Frontend for BasicFrontend { - fn debug(&self, msg: &str) { - println!("{msg}"); - } - - fn report_best_move(&self, best_move: model::Move) { - println!("{best_move}"); - } -} - -fn main() { - let engine = Box::leak(Box::new(Engine::new(1_000_000, &BasicFrontend))); - let (_, best) = engine.evaluate( - None, - EvaluationSettings { - restrict_moves: None, - ponder: false, - clock: engine::Clock::Unlimited, - search_until: engine::SearchLimit::Limited(ActualLimit { - nodes: None, - depth: Some(NonZeroU8::new(DEPTH).unwrap()), - time: None, - }), - }, - ); - engine.set_position(CheckersBitBoard::new( - 4294967295, - 2206409603, - 3005432691, - model::PieceColor::Light, - )); - engine.evaluate( - None, - EvaluationSettings { - restrict_moves: None, - ponder: false, - clock: engine::Clock::Unlimited, - search_until: engine::SearchLimit::Limited(ActualLimit { - nodes: None, - depth: Some(NonZeroU8::new(DEPTH).unwrap()), - time: None, - }), - }, - ); -} +use std::{num::NonZeroU8, time::Instant}; + +use engine::{ActualLimit, Engine, EvalInfo, EvaluationSettings, Frontend}; +use mimalloc::MiMalloc; +use model::CheckersBitBoard; + +#[global_allocator] +static ALLOCATOR: MiMalloc = MiMalloc; + +const DEPTH: u8 = 19; + +struct BasicFrontend; + +impl Frontend for BasicFrontend { + fn debug(&self, msg: &str) { + println!("{msg}"); + } + + fn info(&self, _info: EvalInfo) {} + + fn report_best_move(&self, best_move: model::Move) { + println!("{best_move}"); + } +} + +fn main() { + let engine = Box::leak(Box::new(Engine::new(1_000_000, &BasicFrontend))); + let start = Instant::now(); + engine.evaluate( + None, + EvaluationSettings { + restrict_moves: None, + ponder: false, + clock: engine::Clock::Unlimited, + search_until: engine::SearchLimit::Limited(ActualLimit { + nodes: None, + depth: Some(NonZeroU8::new(DEPTH).unwrap()), + time: None, + }), + }, + ); + println!("{} ms", start.elapsed().as_millis()); + engine.set_position(CheckersBitBoard::new( + 4294967295, + 2206409603, + 3005432691, + model::PieceColor::Light, + )); + engine.evaluate( + None, + EvaluationSettings { + restrict_moves: None, + ponder: false, + clock: engine::Clock::Unlimited, + search_until: engine::SearchLimit::Limited(ActualLimit { + nodes: None, + depth: Some(NonZeroU8::new(DEPTH).unwrap()), + time: None, + }), + }, + ); + // TODO test FEN W:W19,20,21,24,25,26,27,28,29,30,32:B1,2,4,6,7,8,9,11,12,15,17,18 + println!("test"); + engine.set_position(CheckersBitBoard::new( + 3615436253, + 75309505, + 0, + model::PieceColor::Light, + )); + engine.evaluate( + None, + EvaluationSettings { + restrict_moves: None, + ponder: false, + clock: engine::Clock::Unlimited, + search_until: engine::SearchLimit::Limited(ActualLimit { + nodes: None, + depth: Some(NonZeroU8::new(DEPTH).unwrap()), + time: None, + }), + }, + ); +} diff --git a/engine/src/search.rs b/engine/src/search.rs old mode 100644 new mode 100755 index 4326ac6..fd8162a --- a/engine/src/search.rs +++ b/engine/src/search.rs @@ -1,252 +1,278 @@ -use std::num::NonZeroU8; -use std::sync::{atomic::AtomicBool, Arc}; -use std::time::Instant; - -use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; - -use crate::engine::EvaluationTask; -use crate::Frontend; -use crate::{ - eval::{eval_position, Evaluation}, - lazysort::LazySort, - TranspositionTableRef, -}; - -unsafe fn sort_moves( - a: &Move, - board: CheckersBitBoard, - table: TranspositionTableRef, -) -> Evaluation { - table - .get_any_depth(a.apply_to(board)) - .unwrap_or(Evaluation::DRAW) -} - -pub fn negamax( - depth: u8, - mut alpha: Evaluation, - beta: Evaluation, - board: CheckersBitBoard, - 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), None) - } else { - (-eval_position(board), None) - } - } else { - let table = task.transposition_table; - if let Some((entry, best_move)) = table.get(board, depth) { - return (entry, Some(best_move)); - } - - let turn = board.turn(); - let mut best_eval = Evaluation::NULL_MIN; - let mut best_move = None; - - let sort_fn = |m: &Move| unsafe { sort_moves(m, board, table) }; - let sorter: LazySort = - if let Some(moves) = allowed_moves { - LazySort::new(moves.iter().cloned(), sort_fn) - } else { - let moves = PossibleMoves::moves(board); - LazySort::new(moves, sort_fn) - }; - - if sorter.is_empty() { - return (Evaluation::LOSS, None); - } - - 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, None, cancel_flag, task) - .0 - .increment() - } else { - -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 { - alpha = best_eval; - } - - if alpha >= beta { - return (best_eval, best_move); - } - } - - // safety: we already checked that the list isn't empty, so there must - // be at least one move here - let best_move = unsafe { best_move.unwrap_unchecked() }; - // safety: in the case of a zero depth, a different branch is taken - let depth = unsafe { NonZeroU8::new_unchecked(depth) }; - table.insert(board, best_eval, best_move, depth); - - (best_eval, Some(best_move)) - } -} - -pub fn search( - task: Arc, - frontend: &dyn Frontend, - cancel: Option<&AtomicBool>, -) -> (Evaluation, Option) { - let board = task.position; - let cancel_flag = cancel.unwrap_or(&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; - let mut depth = 0; - let mut eval = Evaluation::DRAW; - let mut best_move = None; - loop { - // don't leave search is no good moves have been found - if best_move.is_some() { - 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 best_move.is_some() && cancel_flag.load(std::sync::atomic::Ordering::Acquire) { - break; - } - - eval = em.0; - best_move = em.1; - - while (eval <= alpha) || (eval >= beta) { - let em = negamax( - depth, - alpha, - beta, - board, - allowed_moves.clone(), - cancel_flag, - &task, - ); - - // prevent incomplete search from overwriting evaluation - if best_move.is_some() && cancel_flag.load(std::sync::atomic::Ordering::Acquire) { - break; - } - - eval = em.0; - best_move = em.1; - - if eval <= alpha { - alpha = Evaluation::NULL_MIN; - } else if eval >= beta { - beta = Evaluation::NULL_MAX; - } - } - - if alpha.is_force_loss() { - alpha = Evaluation::NULL_MIN; - } else { - alpha = eval.add_f32(-0.125); - } - - if beta.is_force_win() { - beta = Evaluation::NULL_MAX; - } else { - beta = eval.add_f32(0.125); - } - - if eval.is_force_sequence() { - // we don't need to search any deeper - return (eval, best_move); - } - - depth += 1; - } - - // 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; - } - } - } - - (eval, best_move) -} +use std::marker::PhantomData; +use std::num::NonZeroU8; +use std::sync::{atomic::AtomicBool, Arc}; +use std::time::Instant; + +use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; + +use crate::engine::EvaluationTask; +use crate::{ + eval::{eval_position, Evaluation}, + lazysort::LazySort, + TranspositionTableRef, +}; +use crate::{EvalInfo, Frontend}; + +unsafe fn sort_moves( + a: &Move, + board: CheckersBitBoard, + table: TranspositionTableRef, +) -> Evaluation { + table + .get_any_depth(a.apply_to(board)) + .unwrap_or(Evaluation::DRAW) +} + +pub fn negamax( + depth: u8, + mut alpha: Evaluation, + beta: Evaluation, + board: CheckersBitBoard, + 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), None) + } else { + (-eval_position(board), None) + } + } else { + let table = task.transposition_table; + if let Some((entry, best_move)) = table.get(board, depth) { + return (entry, Some(best_move)); + } + + let turn = board.turn(); + let mut best_eval = Evaluation::NULL_MIN; + let mut best_move = None; + + let sort_fn = |m: &Move| unsafe { sort_moves(m, board, table) }; + let sorter: LazySort = + if let Some(moves) = allowed_moves { + LazySort::new(moves.iter().cloned(), sort_fn) + } else { + let moves = PossibleMoves::moves(board); + LazySort::new(moves, sort_fn) + }; + + if sorter.is_empty() { + return (Evaluation::LOSS, None); + } + + 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, None, cancel_flag, task) + .0 + .increment() + } else { + -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 { + alpha = best_eval; + } + + if alpha >= beta { + return (best_eval, best_move); + } + } + + // safety: we already checked that the list isn't empty, so there must + // be at least one move here + let best_move = unsafe { best_move.unwrap_unchecked() }; + // safety: in the case of a zero depth, a different branch is taken + let depth = unsafe { NonZeroU8::new_unchecked(depth) }; + table.insert(board, best_eval, best_move, depth); + + (best_eval, Some(best_move)) + } +} + +pub fn search( + task: Arc, + frontend: &dyn Frontend, + cancel: Option<&AtomicBool>, +) -> (Evaluation, Option) { + let board = task.position; + let cancel_flag = cancel.unwrap_or(&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 start_time = Instant::now(); + let max_time = limits.time.map(|d| start_time + d); + + let mut alpha = Evaluation::NULL_MIN; + let mut beta = Evaluation::NULL_MAX; + let mut depth = 0; + let mut eval = Evaluation::DRAW; + let mut best_move = None; + loop { + // don't leave search is no good moves have been found + if best_move.is_some() { + 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; + } + } + } else { + // we don't need to do this every time + let mut possible_moves = PossibleMoves::moves(board).into_iter(); + let (_, max_size) = possible_moves.size_hint(); + if max_size == Some(1) { + // don't spend too much time thinking about a single possible move + eval = task + .transposition_table + .get_any_depth(board) + .unwrap_or_else(|| eval_position(board)); + best_move = possible_moves.next(); + break; + } + } + + let em = negamax( + depth, + alpha, + beta, + board, + allowed_moves.clone(), + cancel_flag, + &task, + ); + + // prevent incomplete search from overwriting evaluation + if best_move.is_some() && cancel_flag.load(std::sync::atomic::Ordering::Acquire) { + break; + } + + eval = em.0; + best_move = em.1; + + while (eval <= alpha) || (eval >= beta) { + let em = negamax( + depth, + alpha, + beta, + board, + allowed_moves.clone(), + cancel_flag, + &task, + ); + + // prevent incomplete search from overwriting evaluation + if best_move.is_some() && cancel_flag.load(std::sync::atomic::Ordering::Acquire) { + break; + } + + eval = em.0; + best_move = em.1; + + if eval <= alpha { + alpha = Evaluation::NULL_MIN; + } else if eval >= beta { + beta = Evaluation::NULL_MAX; + } + } + + if alpha.is_force_loss() { + alpha = Evaluation::NULL_MIN; + } else { + alpha = eval.add_f32(-0.125); + } + + if beta.is_force_win() { + beta = Evaluation::NULL_MAX; + } else { + beta = eval.add_f32(0.125); + } + + if eval.is_force_sequence() { + // we don't need to search any deeper + return (eval, best_move); + } + + frontend.info(EvalInfo { + start_time, + nodes_searched: task + .nodes_explored + .load(std::sync::atomic::Ordering::Relaxed), + evaluation: eval, + current_best_move: best_move, + current_depth: depth, + _unused: PhantomData, + }); + + depth += 1; + } + + // 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; + } + } + } + + (eval, best_move) +} diff --git a/engine/src/tablebase.rs b/engine/src/tablebase.rs old mode 100644 new mode 100755 index 87bf404..b56bea4 --- a/engine/src/tablebase.rs +++ b/engine/src/tablebase.rs @@ -1,186 +1,186 @@ -use std::{io, string::FromUtf8Error}; - -use byteorder::{BigEndian, ReadBytesExt}; -use model::{CheckersBitBoard, PieceColor}; -use thiserror::Error; - -const MAGIC: u32 = u32::from_be_bytes(*b".amp"); -const SUPPORTED_VERSION: u16 = 0; -const MAX_TABLE_LENGTH: u64 = 5_000_000_000; - -#[derive(Debug, Clone, PartialEq)] -pub struct Tablebase { - header: FileHeader, - entries: Box<[Option]>, -} - -#[derive(Debug, Clone, PartialEq, Eq)] -struct FileHeader { - /// The version of Ampere Tablebase Format being used - version: u16, - /// The magic number multiplied by board hash values - magic_factor: u64, - /// The number of entries in the tablebase - entries_count: u64, - /// The length of the table needed in-memory - table_length: u64, - /// The type of game the tablebase is for - game_type: GameType, - /// The name of the tablebase - tablebase_name: Box, - /// The tablebase author - author_name: Box, - /// The Unix timestamp indicating when the tablebase was created - publication_time: u64, -} - -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -struct GameType { - /// The type of game being played - game_type: Game, - /// The color that makes the first move - start_color: PieceColor, - /// The width of the board - board_width: u8, - /// The height of the board - board_height: u8, - /// The move notation - notation: MoveNotation, - /// True if the bottom-left square is a playing square - invert_flag: bool, -} - -#[repr(u8)] -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -enum Game { - EnglishDraughts = 21, -} - -#[repr(u8)] -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -enum MoveNotation { - /// Standard Chess Notation, like e5 - Standard = 0, - /// Alpha-numeric square representation, like e7-e5 - Alpha = 1, - /// Numeric square representation, like 11-12 - Numeric = 2, -} - -#[derive(Debug, Clone, Copy, PartialEq)] -struct TablebaseEntry { - board: CheckersBitBoard, - evaluation: f32, - depth: u8, -} - -#[derive(Debug, Error)] -enum TablebaseFileError { - #[error("Invalid tablebase: the magic header field was incorrect")] - MagicError, - #[error("This version of the tablebase format is unsupported. Only {SUPPORTED_VERSION} is supported")] - UnsupportedVersion(u16), - #[error("The table is too large. The length of the table is {} entries, but the max is only {}", .found, .max)] - TableTooLarge { found: u64, max: u64 }, - #[error("The game type for this tablebase is unsupported. Only standard American Checkers is supported")] - UnsupportedGameType(u8), - #[error("A string was not valid UTF-8: {}", .0)] - InvalidString(#[from] FromUtf8Error), - #[error(transparent)] - IoError(#[from] io::Error), -} - -fn read_header(reader: &mut impl ReadBytesExt) -> Result { - // magic is used to verify that the file is valid - let magic = reader.read_u32::()?; - if magic != MAGIC { - return Err(TablebaseFileError::MagicError); - } - - read_reserved_bytes::<2>(reader)?; - - let version = reader.read_u16::()?; - if version != SUPPORTED_VERSION { - return Err(TablebaseFileError::UnsupportedVersion(version)); - } - - let magic_factor = reader.read_u64::()?; - let entries_count = reader.read_u64::()?; - let table_length = reader.read_u64::()?; - - if table_length > MAX_TABLE_LENGTH { - return Err(TablebaseFileError::TableTooLarge { - found: table_length, - max: MAX_TABLE_LENGTH, - }); - } - - let game_type = read_game_type(reader)?; - let publication_time = reader.read_u64::()?; - let tablebase_name_len = reader.read_u8()?; - let author_name_len = reader.read_u8()?; - let _ = read_reserved_bytes::<14>(reader); - - let tablebase_name = read_string(reader, tablebase_name_len)?; - let author_name = read_string(reader, author_name_len)?; - - Ok(FileHeader { - version, - magic_factor, - entries_count, - table_length, - game_type, - publication_time, - tablebase_name, - author_name, - }) -} - -fn read_reserved_bytes(reader: &mut impl ReadBytesExt) -> io::Result<()> { - reader.read_exact([0; NUM_BYTES].as_mut_slice())?; - Ok(()) -} - -#[derive(Debug, Error)] -enum ReadStringError { - #[error(transparent)] - InvalidUtf8(#[from] FromUtf8Error), - #[error(transparent)] - IoError(#[from] io::Error), -} - -fn read_string(reader: &mut impl ReadBytesExt, len: u8) -> Result, TablebaseFileError> { - let mut buffer = vec![0; len as usize]; - reader.read_exact(&mut buffer)?; - Ok(String::from_utf8(buffer)?.into_boxed_str()) -} - -fn read_game_type(reader: &mut impl ReadBytesExt) -> Result { - read_reserved_bytes::<1>(reader)?; - let game_type = reader.read_u8()?; - let start_color = reader.read_u8()?; - let board_width = reader.read_u8()?; - let board_height = reader.read_u8()?; - let invert_flag = reader.read_u8()?; - let notation = reader.read_u8()?; - read_reserved_bytes::<1>(reader)?; - - if game_type != 21 - || start_color != 1 - || board_width != 8 - || board_height != 8 - || invert_flag != 1 - || notation != 2 - { - Err(TablebaseFileError::UnsupportedGameType(game_type)) - } else { - Ok(GameType { - game_type: Game::EnglishDraughts, - start_color: PieceColor::Dark, - board_width: 8, - board_height: 8, - notation: MoveNotation::Numeric, - invert_flag: true, - }) - } -} +use std::{io, string::FromUtf8Error}; + +use byteorder::{BigEndian, ReadBytesExt}; +use model::{CheckersBitBoard, PieceColor}; +use thiserror::Error; + +const MAGIC: u32 = u32::from_be_bytes(*b".amp"); +const SUPPORTED_VERSION: u16 = 0; +const MAX_TABLE_LENGTH: u64 = 5_000_000_000; + +#[derive(Debug, Clone, PartialEq)] +pub struct Tablebase { + header: FileHeader, + entries: Box<[Option]>, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct FileHeader { + /// The version of Ampere Tablebase Format being used + version: u16, + /// The magic number multiplied by board hash values + magic_factor: u64, + /// The number of entries in the tablebase + entries_count: u64, + /// The length of the table needed in-memory + table_length: u64, + /// The type of game the tablebase is for + game_type: GameType, + /// The name of the tablebase + tablebase_name: Box, + /// The tablebase author + author_name: Box, + /// The Unix timestamp indicating when the tablebase was created + publication_time: u64, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +struct GameType { + /// The type of game being played + game_type: Game, + /// The color that makes the first move + start_color: PieceColor, + /// The width of the board + board_width: u8, + /// The height of the board + board_height: u8, + /// The move notation + notation: MoveNotation, + /// True if the bottom-left square is a playing square + invert_flag: bool, +} + +#[repr(u8)] +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum Game { + EnglishDraughts = 21, +} + +#[repr(u8)] +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum MoveNotation { + /// Standard Chess Notation, like e5 + Standard = 0, + /// Alpha-numeric square representation, like e7-e5 + Alpha = 1, + /// Numeric square representation, like 11-12 + Numeric = 2, +} + +#[derive(Debug, Clone, Copy, PartialEq)] +struct TablebaseEntry { + board: CheckersBitBoard, + evaluation: f32, + depth: u8, +} + +#[derive(Debug, Error)] +enum TablebaseFileError { + #[error("Invalid tablebase: the magic header field was incorrect")] + MagicError, + #[error("This version of the tablebase format is unsupported. Only {SUPPORTED_VERSION} is supported")] + UnsupportedVersion(u16), + #[error("The table is too large. The length of the table is {} entries, but the max is only {}", .found, .max)] + TableTooLarge { found: u64, max: u64 }, + #[error("The game type for this tablebase is unsupported. Only standard American Checkers is supported")] + UnsupportedGameType(u8), + #[error("A string was not valid UTF-8: {}", .0)] + InvalidString(#[from] FromUtf8Error), + #[error(transparent)] + IoError(#[from] io::Error), +} + +fn read_header(reader: &mut impl ReadBytesExt) -> Result { + // magic is used to verify that the file is valid + let magic = reader.read_u32::()?; + if magic != MAGIC { + return Err(TablebaseFileError::MagicError); + } + + read_reserved_bytes::<2>(reader)?; + + let version = reader.read_u16::()?; + if version != SUPPORTED_VERSION { + return Err(TablebaseFileError::UnsupportedVersion(version)); + } + + let magic_factor = reader.read_u64::()?; + let entries_count = reader.read_u64::()?; + let table_length = reader.read_u64::()?; + + if table_length > MAX_TABLE_LENGTH { + return Err(TablebaseFileError::TableTooLarge { + found: table_length, + max: MAX_TABLE_LENGTH, + }); + } + + let game_type = read_game_type(reader)?; + let publication_time = reader.read_u64::()?; + let tablebase_name_len = reader.read_u8()?; + let author_name_len = reader.read_u8()?; + let _ = read_reserved_bytes::<14>(reader); + + let tablebase_name = read_string(reader, tablebase_name_len)?; + let author_name = read_string(reader, author_name_len)?; + + Ok(FileHeader { + version, + magic_factor, + entries_count, + table_length, + game_type, + publication_time, + tablebase_name, + author_name, + }) +} + +fn read_reserved_bytes(reader: &mut impl ReadBytesExt) -> io::Result<()> { + reader.read_exact([0; NUM_BYTES].as_mut_slice())?; + Ok(()) +} + +#[derive(Debug, Error)] +enum ReadStringError { + #[error(transparent)] + InvalidUtf8(#[from] FromUtf8Error), + #[error(transparent)] + IoError(#[from] io::Error), +} + +fn read_string(reader: &mut impl ReadBytesExt, len: u8) -> Result, TablebaseFileError> { + let mut buffer = vec![0; len as usize]; + reader.read_exact(&mut buffer)?; + Ok(String::from_utf8(buffer)?.into_boxed_str()) +} + +fn read_game_type(reader: &mut impl ReadBytesExt) -> Result { + read_reserved_bytes::<1>(reader)?; + let game_type = reader.read_u8()?; + let start_color = reader.read_u8()?; + let board_width = reader.read_u8()?; + let board_height = reader.read_u8()?; + let invert_flag = reader.read_u8()?; + let notation = reader.read_u8()?; + read_reserved_bytes::<1>(reader)?; + + if game_type != 21 + || start_color != 1 + || board_width != 8 + || board_height != 8 + || invert_flag != 1 + || notation != 2 + { + Err(TablebaseFileError::UnsupportedGameType(game_type)) + } else { + Ok(GameType { + game_type: Game::EnglishDraughts, + start_color: PieceColor::Dark, + board_width: 8, + board_height: 8, + notation: MoveNotation::Numeric, + invert_flag: true, + }) + } +} diff --git a/engine/src/transposition_table.rs b/engine/src/transposition_table.rs old mode 100644 new mode 100755 index 290ba68..e3cd59a --- a/engine/src/transposition_table.rs +++ b/engine/src/transposition_table.rs @@ -1,177 +1,177 @@ -use crate::{eval::Evaluation, CheckersBitBoard}; -use model::Move; -use parking_lot::RwLock; -use std::num::NonZeroU8; - -#[derive(Copy, Clone, Debug)] -struct TranspositionTableEntry { - board: CheckersBitBoard, - eval: Evaluation, - best_move: Move, - depth: NonZeroU8, -} - -impl TranspositionTableEntry { - const fn new( - board: CheckersBitBoard, - eval: Evaluation, - best_move: Move, - depth: NonZeroU8, - ) -> Self { - Self { - board, - eval, - best_move, - depth, - } - } -} - -pub struct TranspositionTable { - replace_table: Box<[RwLock>]>, - depth_table: Box<[RwLock>]>, -} - -#[derive(Copy, Clone, Debug)] -pub struct TranspositionTableRef<'a> { - replace_table: &'a [RwLock>], - depth_table: &'a [RwLock>], -} - -impl<'a> TranspositionTableRef<'a> { - pub fn get(self, board: CheckersBitBoard, depth: u8) -> Option<(Evaluation, Move)> { - 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, entry.best_move)); - } - } - - // 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, entry.best_move)) - } else { - None - } - } else { - None - } - } - None => None, - } - } - - pub fn get_any_depth(self, board: CheckersBitBoard) -> Option { - 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: Evaluation, - best_move: Move, - 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, best_move, 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, best_move, depth)); - } - } - None => *entry = Some(TranspositionTableEntry::new(board, eval, best_move, depth)), - } - } -} - -impl TranspositionTable { - pub fn new(table_size: usize) -> Self { - 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)); - } - - 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 get_ref(&self) -> TranspositionTableRef { - TranspositionTableRef { - replace_table: &self.replace_table, - depth_table: &self.depth_table, - } - } -} +use crate::{eval::Evaluation, CheckersBitBoard}; +use model::Move; +use parking_lot::RwLock; +use std::num::NonZeroU8; + +#[derive(Copy, Clone, Debug)] +struct TranspositionTableEntry { + board: CheckersBitBoard, + eval: Evaluation, + best_move: Move, + depth: NonZeroU8, +} + +impl TranspositionTableEntry { + const fn new( + board: CheckersBitBoard, + eval: Evaluation, + best_move: Move, + depth: NonZeroU8, + ) -> Self { + Self { + board, + eval, + best_move, + depth, + } + } +} + +pub struct TranspositionTable { + replace_table: Box<[RwLock>]>, + depth_table: Box<[RwLock>]>, +} + +#[derive(Copy, Clone, Debug)] +pub struct TranspositionTableRef<'a> { + replace_table: &'a [RwLock>], + depth_table: &'a [RwLock>], +} + +impl<'a> TranspositionTableRef<'a> { + pub fn get(self, board: CheckersBitBoard, depth: u8) -> Option<(Evaluation, Move)> { + 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, entry.best_move)); + } + } + + // 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, entry.best_move)) + } else { + None + } + } else { + None + } + } + None => None, + } + } + + pub fn get_any_depth(self, board: CheckersBitBoard) -> Option { + 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: Evaluation, + best_move: Move, + 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, best_move, 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, best_move, depth)); + } + } + None => *entry = Some(TranspositionTableEntry::new(board, eval, best_move, depth)), + } + } +} + +impl TranspositionTable { + pub fn new(table_size: usize) -> Self { + 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)); + } + + 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 get_ref(&self) -> TranspositionTableRef { + TranspositionTableRef { + replace_table: &self.replace_table, + depth_table: &self.depth_table, + } + } +} -- cgit v1.2.3