summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--engine/src/eval.rs17
-rw-r--r--engine/src/lazysort.rs33
-rw-r--r--engine/src/lib.rs3
-rw-r--r--engine/src/stackvec.rs99
-rw-r--r--model/src/possible_moves.rs44
5 files changed, 144 insertions, 52 deletions
diff --git a/engine/src/eval.rs b/engine/src/eval.rs
index 4d7d540..01f07f6 100644
--- a/engine/src/eval.rs
+++ b/engine/src/eval.rs
@@ -171,17 +171,20 @@ pub fn negamax(
let turn = board.turn();
let mut best_eval = Evaluation::NULL_MIN;
let mut best_move = None;
- let moves: Arc<[Move]> = if let Some(moves) = allowed_moves {
- moves
- } else {
- PossibleMoves::moves(board).into_iter().collect()
- };
- if moves.is_empty() {
+ let sort_fn = |m: &Move| unsafe { sort_moves(m, board, table) };
+ let sorter: LazySort<Move, _, Evaluation, { PossibleMoves::MAX_POSSIBLE_MOVES }> =
+ 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);
}
- let sorter = LazySort::new(&moves, |m| unsafe { sort_moves(m, board, table) });
for current_move in sorter.into_iter() {
if cancel_flag.load(std::sync::atomic::Ordering::Acquire) {
return (best_eval, best_move);
diff --git a/engine/src/lazysort.rs b/engine/src/lazysort.rs
index bec372c..ba32ee8 100644
--- a/engine/src/lazysort.rs
+++ b/engine/src/lazysort.rs
@@ -1,28 +1,31 @@
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub struct LazySort<T, F: Fn(&T) -> R, R: Ord> {
- collection: Box<[T]>,
+use crate::stackvec::StackVec;
+
+pub struct LazySort<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> {
+ collection: StackVec<T, CAPACITY>,
sorted: usize,
sort_by: F,
}
-pub struct LazySortIter<T, F: Fn(&T) -> R, R: Ord> {
- sorter: LazySort<T, F, R>,
+pub struct LazySortIter<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> {
+ sorter: LazySort<T, F, R, CAPACITY>,
index: usize,
}
-impl<T: Clone, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
- pub fn new(collection: &[T], sort_by: F) -> Self {
+impl<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> LazySort<T, F, R, CAPACITY> {
+ pub fn new(collection: impl IntoIterator<Item = T>, sort_by: F) -> Self {
Self {
- collection: collection.into(),
+ collection: collection.into_iter().collect(),
sort_by,
sorted: 0,
}
}
- fn len(&self) -> usize {
- self.collection.len()
+ pub fn is_empty(&self) -> bool {
+ self.collection.is_empty()
}
+}
+impl<T: Clone, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> LazySort<T, F, R, CAPACITY> {
fn sort(&mut self, index: usize) {
let mut min: Option<R> = None;
let mut min_index = None;
@@ -56,8 +59,10 @@ impl<T: Clone, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
}
}
-impl<T: Copy, F: Fn(&T) -> R, R: Ord> IntoIterator for LazySort<T, F, R> {
- type IntoIter = LazySortIter<T, F, R>;
+impl<T: Copy, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> IntoIterator
+ for LazySort<T, F, R, CAPACITY>
+{
+ type IntoIter = LazySortIter<T, F, R, CAPACITY>;
type Item = T;
fn into_iter(self) -> Self::IntoIter {
@@ -68,7 +73,9 @@ impl<T: Copy, F: Fn(&T) -> R, R: Ord> IntoIterator for LazySort<T, F, R> {
}
}
-impl<T: Copy, F: Fn(&T) -> R, R: Ord> Iterator for LazySortIter<T, F, R> {
+impl<T: Copy, F: Fn(&T) -> R, R: Ord, const CAPACITY: usize> Iterator
+ for LazySortIter<T, F, R, CAPACITY>
+{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
diff --git a/engine/src/lib.rs b/engine/src/lib.rs
index 27a1f2d..fdb50e6 100644
--- a/engine/src/lib.rs
+++ b/engine/src/lib.rs
@@ -1,4 +1,6 @@
#![feature(new_uninit)]
+#![feature(maybe_uninit_uninit_array)]
+#![feature(maybe_uninit_slice)]
use std::num::{NonZeroU8, NonZeroUsize};
use std::sync::atomic::{AtomicBool, AtomicU8, AtomicUsize, Ordering};
@@ -15,6 +17,7 @@ pub use transposition_table::{TranspositionTable, TranspositionTableRef};
mod eval;
mod lazysort;
+mod stackvec;
mod tablebase;
mod transposition_table;
diff --git a/engine/src/stackvec.rs b/engine/src/stackvec.rs
new file mode 100644
index 0000000..9c00461
--- /dev/null
+++ b/engine/src/stackvec.rs
@@ -0,0 +1,99 @@
+use std::mem::MaybeUninit;
+use std::ops::{Deref, DerefMut};
+
+pub struct StackVec<T, const CAPACITY: usize> {
+ values: [MaybeUninit<T>; CAPACITY],
+ len: usize,
+}
+
+impl<T, const CAPACITY: usize> Deref for StackVec<T, CAPACITY> {
+ type Target = [T];
+
+ fn deref(&self) -> &Self::Target {
+ self.as_slice()
+ }
+}
+
+impl<T, const CAPACITY: usize> DerefMut for StackVec<T, CAPACITY> {
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ self.as_mut_slice()
+ }
+}
+
+impl<T, const CAPACITY: usize> FromIterator<T> for StackVec<T, CAPACITY> {
+ fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
+ let mut this = Self::new();
+ for item in iter {
+ this.push(item);
+ }
+
+ this
+ }
+}
+
+impl<T, const CAPACITY: usize> StackVec<T, CAPACITY> {
+ pub fn new() -> Self {
+ Self {
+ values: MaybeUninit::uninit_array(),
+ len: 0,
+ }
+ }
+
+ pub fn capcity(&self) -> usize {
+ CAPACITY
+ }
+
+ pub fn len(&self) -> usize {
+ self.len
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len == 0
+ }
+
+ pub fn as_slice(&self) -> &[T] {
+ // safety: the first `len` elements are guaranteed to be initialized
+ unsafe { MaybeUninit::slice_assume_init_ref(&self.values[..self.len]) }
+ }
+
+ pub fn as_mut_slice(&mut self) -> &mut [T] {
+ // safety: the first `len` elements are guaranteed to be initialized
+ unsafe { MaybeUninit::slice_assume_init_mut(&mut self.values[..self.len]) }
+ }
+
+ pub fn as_ptr(&self) -> *const T {
+ self.values.as_ptr().cast()
+ }
+
+ pub fn as_mut_ptr(&mut self) -> *mut T {
+ self.values.as_mut_ptr().cast()
+ }
+
+ pub fn try_push(&mut self, value: T) -> Option<()> {
+ self.values.get_mut(self.len)?.write(value);
+ self.len += 1;
+ Some(())
+ }
+
+ pub fn push(&mut self, value: T) {
+ self.values[self.len].write(value);
+ self.len += 1;
+ }
+
+ pub fn pop(&mut self) -> Option<T> {
+ if self.is_empty() {
+ return None;
+ }
+
+ // safety: this value will no longer be used, and the value is valid
+ // because it appears in the valid part of the array
+ unsafe {
+ self.len -= 1;
+ Some(std::ptr::read(self.as_ptr().add(self.len())))
+ }
+ }
+
+ pub fn clear(&mut self) {
+ self.len = 0;
+ }
+}
diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs
index 0319d93..bdb4775 100644
--- a/model/src/possible_moves.rs
+++ b/model/src/possible_moves.rs
@@ -1,12 +1,10 @@
use crate::moves::{Move, MoveDirection};
use crate::{CheckersBitBoard, PieceColor};
-use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
use std::mem::MaybeUninit;
-use std::ptr::NonNull;
// The maximum number of available moves in any given position
-const POSSIBLE_MOVES_ITER_SIZE: usize = 42;
+pub const POSSIBLE_MOVES_ITER_SIZE: usize = 50;
/// A struct containing the possible moves in a particular checkers position
#[derive(Copy, Clone, Debug)]
@@ -20,7 +18,7 @@ pub struct PossibleMoves {
/// An iterator of possible checkers moves for a particular position
pub struct PossibleMovesIter {
/// A pointer to an array of possibly uninitialized checkers moves
- moves: NonNull<[MaybeUninit<Move>; POSSIBLE_MOVES_ITER_SIZE]>,
+ moves: [MaybeUninit<Move>; POSSIBLE_MOVES_ITER_SIZE],
/// The current index into the moves array
index: usize,
@@ -165,29 +163,15 @@ impl Iterator for PossibleMovesIter {
}
}
-impl Drop for PossibleMovesIter {
- fn drop(&mut self) {
- let layout = Layout::array::<MaybeUninit<Move>>(POSSIBLE_MOVES_ITER_SIZE).unwrap();
- unsafe { dealloc(self.moves.as_ptr() as *mut u8, layout) }
- }
-}
-
impl IntoIterator for PossibleMoves {
type Item = Move;
type IntoIter = PossibleMovesIter;
// TODO test
fn into_iter(self) -> Self::IntoIter {
- let layout = Layout::array::<MaybeUninit<Move>>(POSSIBLE_MOVES_ITER_SIZE).unwrap();
- let allocated_mem = unsafe { alloc(layout) };
- let ptr =
- match NonNull::new(allocated_mem as *mut [MaybeUninit<Move>; POSSIBLE_MOVES_ITER_SIZE])
- {
- Some(p) => p,
- None => handle_alloc_error(layout),
- };
+ let moves = [MaybeUninit::uninit(); POSSIBLE_MOVES_ITER_SIZE];
let mut iter = PossibleMovesIter {
- moves: ptr,
+ moves,
index: 0,
length: 0,
};
@@ -378,6 +362,10 @@ impl IntoIterator for PossibleMoves {
impl PossibleMoves {
// TODO test
+
+ /// The highest possible number of valid moves
+ pub const MAX_POSSIBLE_MOVES: usize = POSSIBLE_MOVES_ITER_SIZE;
+
const fn slides_dark(board: CheckersBitBoard) -> Self {
const FORWARD_LEFT_MASK: u32 = 0b01111001111110111111001111011011;
const FORWARD_RIGHT_MASK: u32 = 0b01111101111111011111010111011101;
@@ -754,17 +742,9 @@ mod tests {
use super::*;
fn setup_empty_iter() -> PossibleMovesIter {
- let layout = Layout::array::<MaybeUninit<Move>>(POSSIBLE_MOVES_ITER_SIZE).unwrap();
- let allocated_mem = unsafe { alloc(layout) };
- let ptr =
- match NonNull::new(allocated_mem as *mut [MaybeUninit<Move>; POSSIBLE_MOVES_ITER_SIZE])
- {
- Some(p) => p,
- None => handle_alloc_error(layout),
- };
-
+ let moves = [MaybeUninit::uninit(); POSSIBLE_MOVES_ITER_SIZE];
PossibleMovesIter {
- moves: ptr,
+ moves,
index: 0,
length: 0,
}
@@ -822,10 +802,10 @@ mod tests {
let mut iter = setup_empty_iter();
iter.length = 2;
- let ptr = unsafe { iter.moves.as_mut() }.get_mut(0).unwrap();
+ let ptr = iter.moves.as_mut().get_mut(0).unwrap();
*ptr = MaybeUninit::new(test_move1);
- let ptr = unsafe { iter.moves.as_mut() }.get_mut(1).unwrap();
+ let ptr = iter.moves.as_mut().get_mut(1).unwrap();
*ptr = MaybeUninit::new(test_move2);
let recieved_move = iter.next();
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-04 07:53:58 +0000