From f7a7bf20a99b1d52ef5f936705611ce24a1006b7 Mon Sep 17 00:00:00 2001 From: Micha White Date: Wed, 27 Sep 2023 09:41:01 -0400 Subject: Edited some of the crates --- ai/src/eval.rs | 145 -------------------------------------- ai/src/lib.rs | 9 --- ai/src/main.rs | 25 ------- ai/src/transposition_table.rs | 157 ------------------------------------------ 4 files changed, 336 deletions(-) delete mode 100644 ai/src/eval.rs delete mode 100644 ai/src/lib.rs delete mode 100644 ai/src/main.rs delete mode 100644 ai/src/transposition_table.rs (limited to 'ai/src') diff --git a/ai/src/eval.rs b/ai/src/eval.rs deleted file mode 100644 index a3265bf..0000000 --- a/ai/src/eval.rs +++ /dev/null @@ -1,145 +0,0 @@ -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 deleted file mode 100644 index 06f0818..0000000 --- a/ai/src/lib.rs +++ /dev/null @@ -1,9 +0,0 @@ -#![feature(new_uninit)] -#![feature(get_mut_unchecked)] - -pub use eval::negamax; -pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves}; -pub use transposition_table::{TranspositionTable, TranspositionTableRef}; - -mod eval; -mod transposition_table; diff --git a/ai/src/main.rs b/ai/src/main.rs deleted file mode 100644 index dcedcb5..0000000 --- a/ai/src/main.rs +++ /dev/null @@ -1,25 +0,0 @@ -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 deleted file mode 100644 index 2b56a66..0000000 --- a/ai/src/transposition_table.rs +++ /dev/null @@ -1,157 +0,0 @@ -use crate::CheckersBitBoard; -use parking_lot::RwLock; -use std::num::NonZeroU8; - -#[derive(Copy, Clone, Debug)] -struct TranspositionTableEntry { - board: CheckersBitBoard, - eval: f32, - depth: NonZeroU8, -} - -impl TranspositionTableEntry { - const fn new(board: CheckersBitBoard, eval: f32, depth: NonZeroU8) -> Self { - Self { board, eval, depth } - } -} - -pub struct TranspositionTable { - replace_table: Box<[RwLock>]>, - 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 - .as_ref() - .get_unchecked(board.hash_code() as usize % table_len) - .read() - }; - if let Some(entry) = *entry { - if entry.board == board && entry.depth.get() >= depth { - return Some(entry.eval); - } - } - - // try the depth table - let entry = unsafe { - self.depth_table - .as_ref() - .get_unchecked(board.hash_code() as usize % table_len) - .read() - }; - match *entry { - Some(entry) => { - if entry.board == board { - if entry.depth.get() >= depth { - Some(entry.eval) - } else { - None - } - } else { - None - } - } - None => None, - } - } - - pub fn get_any_depth(self, board: CheckersBitBoard) -> Option { - let table_len = self.replace_table.as_ref().len(); - - // try the depth table - let entry = unsafe { - self.depth_table - .as_ref() - .get_unchecked(board.hash_code() as usize % table_len) - .read() - }; - if let Some(entry) = *entry { - if entry.board == board { - return Some(entry.eval); - } - } - - // try the replace table - let entry = unsafe { - self.replace_table - .as_ref() - .get_unchecked(board.hash_code() as usize % table_len) - .read() - }; - match *entry { - Some(entry) => { - if entry.board == board { - Some(entry.eval) - } else { - None - } - } - None => None, - } - } - - pub fn insert(&self, board: CheckersBitBoard, eval: f32, depth: NonZeroU8) { - let table_len = self.replace_table.as_ref().len(); - - // insert to the replace table - let mut entry = unsafe { - self.replace_table - .get_unchecked(board.hash_code() as usize % table_len) - .write() - }; - *entry = Some(TranspositionTableEntry::new(board, eval, depth)); - - // insert to the depth table, only if the new depth is higher - let mut entry = unsafe { - self.depth_table - .get_unchecked(board.hash_code() as usize % table_len) - .write() - }; - match *entry { - Some(entry_val) => { - if depth >= entry_val.depth { - *entry = Some(TranspositionTableEntry::new(board, eval, depth)); - } - } - None => *entry = Some(TranspositionTableEntry::new(board, eval, depth)), - } - } -} - -impl TranspositionTable { - pub fn new(table_size: usize) -> Self { - let mut replace_table = Box::new_uninit_slice(table_size / 2); - let mut depth_table = Box::new_uninit_slice(table_size / 2); - - for entry in replace_table.iter_mut() { - entry.write(RwLock::new(None)); - } - - for entry in depth_table.iter_mut() { - entry.write(RwLock::new(None)); - } - - Self { - replace_table: unsafe { replace_table.assume_init() }, - depth_table: unsafe { depth_table.assume_init() }, - } - } - - pub fn mut_ref(&mut self) -> TranspositionTableRef { - TranspositionTableRef { - replace_table: &self.replace_table, - depth_table: &self.depth_table, - } - } -} -- cgit v1.2.3