From 1b379403ab971e188483df5d580c39695db7f44a Mon Sep 17 00:00:00 2001 From: Micha White Date: Wed, 27 Sep 2023 09:35:50 -0400 Subject: Big changes --- ai/Cargo.toml | 5 +- ai/src/eval.rs | 145 +++++++++++++++++++++++++++++++++++ ai/src/lib.rs | 174 ++---------------------------------------- ai/src/main.rs | 25 ++++++ ai/src/transposition_table.rs | 129 +++++++++++++++++++++++-------- 5 files changed, 274 insertions(+), 204 deletions(-) create mode 100644 ai/src/eval.rs create mode 100644 ai/src/main.rs (limited to 'ai') diff --git a/ai/Cargo.toml b/ai/Cargo.toml index 59a4b82..6a4ea61 100644 --- a/ai/Cargo.toml +++ b/ai/Cargo.toml @@ -8,8 +8,7 @@ edition = "2018" [dependencies] model = {path = "../model"} -rayon = "1" -parking_lot = "0.11" +parking_lot = "0.12" [dev-dependencies] -criterion = "0.3" \ No newline at end of file +criterion = "0.5" \ No newline at end of file diff --git a/ai/src/eval.rs b/ai/src/eval.rs new file mode 100644 index 0000000..a3265bf --- /dev/null +++ b/ai/src/eval.rs @@ -0,0 +1,145 @@ +use std::{mem::MaybeUninit, num::NonZeroU8, ops::Neg}; + +use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; + +use crate::transposition_table::TranspositionTableRef; + +const KING_WORTH: u32 = 2; + +fn eval_position(board: CheckersBitBoard) -> f32 { + let light_pieces = board.pieces_bits() & !board.color_bits(); + let dark_pieces = board.pieces_bits() & board.color_bits(); + + let light_peasants = light_pieces & !board.king_bits(); + let dark_peasants = dark_pieces & !board.king_bits(); + + let light_kings = light_pieces & board.king_bits(); + let dark_kings = dark_pieces & board.king_bits(); + + // if we assume the black player doesn't exist, how good is this for white? + let light_eval = + (light_peasants.count_ones() as f32) + ((light_kings.count_ones() * KING_WORTH) as f32); + let dark_eval = + (dark_peasants.count_ones() as f32) + ((dark_kings.count_ones() * KING_WORTH) as f32); + + // avoiding a divide by zero error + if dark_eval + light_eval != 0.0 { + (dark_eval - light_eval) / (dark_eval + light_eval) + } else { + 0.0 + } +} + +fn eval_jumps( + mut alpha: f32, + beta: f32, + board: CheckersBitBoard, + table: TranspositionTableRef, +) -> f32 { + // todo stop checking for jumps twice, but also don't look for slides if there are no jumps + if PossibleMoves::has_jumps(board) { + // todo check if this is useful + // todo make a board for the other player's turn reusable + + let turn = board.turn(); + let mut best_eval = f32::NEG_INFINITY; + let moves = PossibleMoves::moves(board); + + if moves.is_empty() { + return -1.0; + } + + for current_move in moves { + let board = unsafe { current_move.apply_to(board) }; + let current_eval = if board.turn() != turn { + -eval_jumps(-beta, -alpha, board, table) + } else { + eval_jumps(alpha, beta, board, table) + }; + + table.insert(board, current_eval, unsafe { NonZeroU8::new_unchecked(1) }); + + if current_eval >= beta { + return beta; + } + + if best_eval < current_eval { + best_eval = current_eval; + } + if alpha < best_eval { + alpha = best_eval; + } + } + + best_eval + } else if board.turn() == PieceColor::Dark { + eval_position(board) + } else { + -eval_position(board) + } +} + +unsafe fn sort_moves( + a: &Move, + b: &Move, + board: CheckersBitBoard, + table: TranspositionTableRef, +) -> std::cmp::Ordering { + let a_entry = table.get_any_depth(a.apply_to(board)).unwrap_or_default(); + let b_entry = table.get_any_depth(b.apply_to(board)).unwrap_or_default(); + a_entry.total_cmp(&b_entry) +} + +pub fn negamax( + depth: u8, + mut alpha: f32, + beta: f32, + board: CheckersBitBoard, + table: TranspositionTableRef, +) -> f32 { + if depth < 1 { + if board.turn() == PieceColor::Dark { + eval_position(board) + } else { + -eval_position(board) + } + } else { + if let Some(entry) = table.get(board, depth) { + return entry; + } + + let turn = board.turn(); + let mut best_eval = f32::NEG_INFINITY; + let mut moves: Vec = PossibleMoves::moves(board).into_iter().collect(); + moves.sort_unstable_by(|a, b| unsafe { sort_moves(a, b, board, table) }); + + if moves.is_empty() { + return -1.0; + } + + for current_move in moves { + let board = unsafe { current_move.apply_to(board) }; + let current_eval = if board.turn() == turn { + negamax(depth - 1, alpha, beta, board, table) + } else { + -negamax(depth - 1, -beta, -alpha, board, table) + }; + + if best_eval < current_eval { + best_eval = current_eval; + } + + if alpha < best_eval { + alpha = best_eval; + } + + if alpha >= beta { + return best_eval; + } + } + + table.insert(board, best_eval, unsafe { NonZeroU8::new_unchecked(depth) }); + + best_eval + } +} diff --git a/ai/src/lib.rs b/ai/src/lib.rs index 8c49ba7..06f0818 100644 --- a/ai/src/lib.rs +++ b/ai/src/lib.rs @@ -1,171 +1,9 @@ -use crate::transposition_table::TranspositionTableReference; +#![feature(new_uninit)] +#![feature(get_mut_unchecked)] + +pub use eval::negamax; pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; -use parking_lot::{Mutex, RwLock}; -use rayon::prelude::*; -use std::mem::MaybeUninit; +pub use transposition_table::{TranspositionTable, TranspositionTableRef}; +mod eval; mod transposition_table; - -const KING_WORTH: u32 = 2; - -fn eval_position(board: CheckersBitBoard) -> f32 { - let light_pieces = board.pieces_bits() & !board.color_bits(); - let dark_pieces = board.pieces_bits() & board.color_bits(); - - let light_peasants = light_pieces & !board.king_bits(); - let dark_peasants = dark_pieces & !board.king_bits(); - - let light_kings = light_pieces & board.king_bits(); - let dark_kings = dark_pieces & board.king_bits(); - - // if we assume the black player doesn't exist, how good is this for white? - let light_eval = - (light_peasants.count_ones() as f32) + ((light_kings.count_ones() * KING_WORTH) as f32); - let dark_eval = - (dark_peasants.count_ones() as f32) + ((dark_kings.count_ones() * KING_WORTH) as f32); - - // avoiding a divide by zero error - if dark_eval + light_eval != 0.0 { - dark_eval / (dark_eval + light_eval) - } else { - 0.5 - } -} - -pub fn eval_singlethreaded( - depth: usize, - mut alpha: f32, - beta: f32, - board: CheckersBitBoard, -) -> f32 { - if depth <= 1 { - if board.turn() == PieceColor::Dark { - eval_position(board) - } else { - 1.0 - eval_position(board) - } - } else { - let table = TranspositionTableReference::new(); - if let Some(eval) = table.get(board, depth as u8) { - return eval; - } - - let turn = board.turn(); - let mut best_eval = f32::NEG_INFINITY; - let moves = PossibleMoves::moves(board); - - if moves.is_empty() { - return 0.0; - } - - for current_move in PossibleMoves::moves(board) { - let board = unsafe { current_move.apply_to(board) }; - let current_eval = if board.turn() != turn { - 1.0 - eval_singlethreaded(depth - 1, 1.0 - beta, 1.0 - alpha, board) - } else { - eval_singlethreaded(depth - 1, alpha, beta, board) - }; - - let table = TranspositionTableReference::new(); - table.insert(board, current_eval, depth as u8); - - if current_eval >= beta { - return beta; - } - - if best_eval < current_eval { - best_eval = current_eval; - } - if alpha < best_eval { - alpha = best_eval; - } - } - - best_eval - } -} - -pub fn eval_multithreaded(depth: usize, alpha: f32, beta: f32, board: CheckersBitBoard) -> f32 { - if depth <= 1 { - if board.turn() == PieceColor::Dark { - eval_position(board) - } else { - 1.0 - eval_position(board) - } - } else { - let turn = board.turn(); - let best_eval = Mutex::new(f32::NEG_INFINITY); - let keep_going = RwLock::new(true); - let alpha = RwLock::new(alpha); - - let is_still_going = || *keep_going.read(); - let get_alpha = || *alpha.read(); - - let moves = PossibleMoves::moves(board); - - if moves.is_empty() { - let pos_eval = if board.turn() == PieceColor::Dark { - eval_position(board) - } else { - 1.0 - eval_position(board) - }; - return if pos_eval < f32::EPSILON || pos_eval > 1.0 - f32::EPSILON { - pos_eval - } else { - 0.5 - }; - } - - moves.into_iter().par_bridge().for_each(|current_move| { - if is_still_going() { - let board = unsafe { current_move.apply_to(board) }; - let current_eval = if board.turn() != turn { - 1.0 - eval_singlethreaded(depth - 1, 1.0 - beta, 1.0 - get_alpha(), board) - } else { - eval_singlethreaded(depth - 1, get_alpha(), beta, board) - }; - - let mut best = best_eval.lock(); - if current_eval >= beta { - *best = beta; - let mut going_val = keep_going.write(); - *going_val = false; - } - - if *best < current_eval { - *best = current_eval; - } - if get_alpha() < *best { - let mut alpha = alpha.write(); - *alpha = *best; - } - } - }); - - best_eval.into_inner() - } -} - -pub fn best_move(depth: usize, board: CheckersBitBoard) -> Move { - let mut best_eval = 0.0; - let mut best_move = MaybeUninit::uninit(); - let moves = PossibleMoves::moves(board); - - if moves.is_empty() { - panic!("No moves are available") - } - - for current_move in PossibleMoves::moves(board) { - let new_board = unsafe { current_move.apply_to(board) }; - let mut current_eval = eval_multithreaded(depth - 1, best_eval, 1.0, new_board); - if new_board.turn() != board.turn() { - current_eval = 1.0 - current_eval; - } - if current_eval > best_eval { - best_eval = current_eval; - best_move.write(current_move); - } - } - - unsafe { best_move.assume_init() } -} diff --git a/ai/src/main.rs b/ai/src/main.rs new file mode 100644 index 0000000..dcedcb5 --- /dev/null +++ b/ai/src/main.rs @@ -0,0 +1,25 @@ +use ai::TranspositionTable; + +const DEPTH: u8 = 18; + +fn main() { + let board = ai::CheckersBitBoard::starting_position(); + let mut table = TranspositionTable::new(50_000); + let mut alpha = -1.0; + let mut beta = 1.0; + for i in 0..DEPTH { + let mut eval = ai::negamax(i, alpha, beta, board, table.mut_ref()); + + if (eval <= alpha) || (eval >= beta) { + eval = ai::negamax(i, -1.0, 1.0, board, table.mut_ref()); + } + + alpha = f32::max(eval + 0.125, -1.0); + beta = f32::min(eval + 0.125, 1.0); + } + + println!( + "{:?}", + ai::negamax(DEPTH, alpha, beta, board, table.mut_ref(),) + ); +} diff --git a/ai/src/transposition_table.rs b/ai/src/transposition_table.rs index b801789..2b56a66 100644 --- a/ai/src/transposition_table.rs +++ b/ai/src/transposition_table.rs @@ -1,49 +1,44 @@ use crate::CheckersBitBoard; - -#[cfg(debug_assertions)] -const TABLE_SIZE: usize = 1_000_000 / std::mem::size_of::(); - -#[cfg(not(debug_assertions))] -const TABLE_SIZE: usize = 10_000_000 / std::mem::size_of::(); - -const EMPTY_ENTRY: Option = None; -static mut REPLACE_TABLE: [Option; TABLE_SIZE] = [EMPTY_ENTRY; TABLE_SIZE]; -static mut DEPTH_TABLE: [Option; TABLE_SIZE] = [EMPTY_ENTRY; TABLE_SIZE]; +use parking_lot::RwLock; +use std::num::NonZeroU8; #[derive(Copy, Clone, Debug)] struct TranspositionTableEntry { board: CheckersBitBoard, eval: f32, - depth: u8, -} - -pub struct TranspositionTableReference { - replace_table: &'static mut [Option; TABLE_SIZE], - depth_table: &'static mut [Option; TABLE_SIZE], + depth: NonZeroU8, } impl TranspositionTableEntry { - const fn new(board: CheckersBitBoard, eval: f32, depth: u8) -> Self { + const fn new(board: CheckersBitBoard, eval: f32, depth: NonZeroU8) -> Self { Self { board, eval, depth } } } -impl TranspositionTableReference { - pub fn new() -> Self { - Self { - replace_table: unsafe { &mut REPLACE_TABLE }, - depth_table: unsafe { &mut DEPTH_TABLE }, - } - } +pub 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 { + let table_len = self.replace_table.as_ref().len(); + // try the replace table let entry = unsafe { self.replace_table - .get_unchecked(board.hash_code() as usize % TABLE_SIZE) + .as_ref() + .get_unchecked(board.hash_code() as usize % table_len) + .read() }; if let Some(entry) = *entry { - if entry.board == board && entry.depth >= depth { + if entry.board == board && entry.depth.get() >= depth { return Some(entry.eval); } } @@ -51,12 +46,14 @@ impl TranspositionTableReference { // try the depth table let entry = unsafe { self.depth_table - .get_unchecked(board.hash_code() as usize % TABLE_SIZE) + .as_ref() + .get_unchecked(board.hash_code() as usize % table_len) + .read() }; match *entry { Some(entry) => { if entry.board == board { - if entry.depth >= depth { + if entry.depth.get() >= depth { Some(entry.eval) } else { None @@ -69,18 +66,57 @@ impl TranspositionTableReference { } } - pub fn insert(self, board: CheckersBitBoard, eval: f32, depth: u8) { - // insert to the replace table + 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: f32, depth: NonZeroU8) { + let table_len = self.replace_table.as_ref().len(); + + // insert to the replace table + let mut entry = unsafe { self.replace_table - .get_unchecked_mut(board.hash_code() as usize % TABLE_SIZE) + .get_unchecked(board.hash_code() as usize % table_len) + .write() }; *entry = Some(TranspositionTableEntry::new(board, eval, depth)); // insert to the depth table, only if the new depth is higher - let entry = unsafe { + let mut entry = unsafe { self.depth_table - .get_unchecked_mut(board.hash_code() as usize % TABLE_SIZE) + .get_unchecked(board.hash_code() as usize % table_len) + .write() }; match *entry { Some(entry_val) => { @@ -92,3 +128,30 @@ impl TranspositionTableReference { } } } + +impl TranspositionTable { + pub fn new(table_size: usize) -> Self { + let mut replace_table = Box::new_uninit_slice(table_size / 2); + let mut depth_table = Box::new_uninit_slice(table_size / 2); + + for entry in replace_table.iter_mut() { + entry.write(RwLock::new(None)); + } + + for entry in depth_table.iter_mut() { + entry.write(RwLock::new(None)); + } + + Self { + replace_table: unsafe { replace_table.assume_init() }, + depth_table: unsafe { depth_table.assume_init() }, + } + } + + pub fn mut_ref(&mut self) -> TranspositionTableRef { + TranspositionTableRef { + replace_table: &self.replace_table, + depth_table: &self.depth_table, + } + } +} -- cgit v1.2.3