summaryrefslogtreecommitdiff
path: root/ai/src
diff options
context:
space:
mode:
Diffstat (limited to 'ai/src')
-rw-r--r--ai/src/eval.rs145
-rw-r--r--ai/src/lib.rs174
-rw-r--r--ai/src/main.rs25
-rw-r--r--ai/src/transposition_table.rs129
4 files changed, 272 insertions, 201 deletions
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<Move> = 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::<TranspositionTableEntry>();
-
-#[cfg(not(debug_assertions))]
-const TABLE_SIZE: usize = 10_000_000 / std::mem::size_of::<TranspositionTableEntry>();
-
-const EMPTY_ENTRY: Option<TranspositionTableEntry> = None;
-static mut REPLACE_TABLE: [Option<TranspositionTableEntry>; TABLE_SIZE] = [EMPTY_ENTRY; TABLE_SIZE];
-static mut DEPTH_TABLE: [Option<TranspositionTableEntry>; 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<TranspositionTableEntry>; TABLE_SIZE],
- depth_table: &'static mut [Option<TranspositionTableEntry>; 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<Option<TranspositionTableEntry>>]>,
+ depth_table: Box<[RwLock<Option<TranspositionTableEntry>>]>,
+}
+#[derive(Copy, Clone, Debug)]
+pub struct TranspositionTableRef<'a> {
+ replace_table: &'a [RwLock<Option<TranspositionTableEntry>>],
+ depth_table: &'a [RwLock<Option<TranspositionTableEntry>>],
+}
+
+impl<'a> TranspositionTableRef<'a> {
pub fn get(self, board: CheckersBitBoard, depth: u8) -> Option<f32> {
+ 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<f32> {
+ 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,
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-04 11:50:54 +0000