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 --- Cargo.toml | 2 +- ai/.gitignore | 2 - ai/Cargo.toml | 14 ---- ai/src/eval.rs | 145 ----------------------------------- ai/src/lib.rs | 9 --- ai/src/main.rs | 25 ------ ai/src/transposition_table.rs | 157 -------------------------------------- engine/.gitignore | 2 + engine/Cargo.toml | 15 ++++ engine/src/eval.rs | 145 +++++++++++++++++++++++++++++++++++ engine/src/lib.rs | 9 +++ engine/src/main.rs | 22 ++++++ engine/src/transposition_table.rs | 157 ++++++++++++++++++++++++++++++++++++++ model/Cargo.toml | 1 + ui/Cargo.toml | 4 +- 15 files changed, 355 insertions(+), 354 deletions(-) delete mode 100644 ai/.gitignore delete mode 100644 ai/Cargo.toml 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 create mode 100644 engine/.gitignore create mode 100644 engine/Cargo.toml create mode 100644 engine/src/eval.rs create mode 100644 engine/src/lib.rs create mode 100644 engine/src/main.rs create mode 100644 engine/src/transposition_table.rs diff --git a/Cargo.toml b/Cargo.toml index 7c1c288..2dfe5ac 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,7 +1,7 @@ [workspace] resolver = "2" members = [ - "ai", + "engine", "model", "pdn", "ui" diff --git a/ai/.gitignore b/ai/.gitignore deleted file mode 100644 index 96ef6c0..0000000 --- a/ai/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -/target -Cargo.lock diff --git a/ai/Cargo.toml b/ai/Cargo.toml deleted file mode 100644 index 6a4ea61..0000000 --- a/ai/Cargo.toml +++ /dev/null @@ -1,14 +0,0 @@ -[package] -name = "ai" -version = "0.1.0" -authors = ["botahamec"] -edition = "2018" - -# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html - -[dependencies] -model = {path = "../model"} -parking_lot = "0.12" - -[dev-dependencies] -criterion = "0.5" \ No newline at end of file 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, - } - } -} diff --git a/engine/.gitignore b/engine/.gitignore new file mode 100644 index 0000000..96ef6c0 --- /dev/null +++ b/engine/.gitignore @@ -0,0 +1,2 @@ +/target +Cargo.lock diff --git a/engine/Cargo.toml b/engine/Cargo.toml new file mode 100644 index 0000000..87410c5 --- /dev/null +++ b/engine/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "engine" +version = "0.1.0" +authors = ["botahamec"] +edition = "2018" +publish = false + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +model = {path = "../model"} +parking_lot = "0.12" + +[dev-dependencies] +criterion = "0.5" \ No newline at end of file diff --git a/engine/src/eval.rs b/engine/src/eval.rs new file mode 100644 index 0000000..a3265bf --- /dev/null +++ b/engine/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/engine/src/lib.rs b/engine/src/lib.rs new file mode 100644 index 0000000..06f0818 --- /dev/null +++ b/engine/src/lib.rs @@ -0,0 +1,9 @@ +#![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/engine/src/main.rs b/engine/src/main.rs new file mode 100644 index 0000000..59002ec --- /dev/null +++ b/engine/src/main.rs @@ -0,0 +1,22 @@ +use engine::{negamax, CheckersBitBoard, TranspositionTable}; + +const DEPTH: u8 = 18; + +fn main() { + let board = 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 = negamax(i, alpha, beta, board, table.mut_ref()); + + if (eval <= alpha) || (eval >= beta) { + eval = 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!("{:?}", negamax(DEPTH, alpha, beta, board, table.mut_ref(),)); +} diff --git a/engine/src/transposition_table.rs b/engine/src/transposition_table.rs new file mode 100644 index 0000000..2b56a66 --- /dev/null +++ b/engine/src/transposition_table.rs @@ -0,0 +1,157 @@ +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, + } + } +} diff --git a/model/Cargo.toml b/model/Cargo.toml index cdda386..891889a 100644 --- a/model/Cargo.toml +++ b/model/Cargo.toml @@ -3,6 +3,7 @@ name = "model" version = "0.1.0" authors = ["Mike White "] edition = "2018" +publish = false # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html diff --git a/ui/Cargo.toml b/ui/Cargo.toml index 086a7de..c4a1e04 100644 --- a/ui/Cargo.toml +++ b/ui/Cargo.toml @@ -2,9 +2,11 @@ name = "ui" version = "0.1.0" edition = "2018" +publish = false # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] tetra = "0.6" -model = {path = "../model"} \ No newline at end of file +model = {path = "../model"} +engine = {path = "../engine"} \ No newline at end of file -- cgit v1.2.3