Switch to i16 evaluation

2 files changed, 131 insertions, 73 deletions

diff --git a/engine/src/eval.rs b/engine/src/eval.rs
index ca55740..b0b52df 100644
--- a/engine/src/eval.rs
+++ b/engine/src/eval.rs
@@ -1,5 +1,4 @@
 use std::{
-	cmp::Ordering,
 	fmt::{Debug, Display},
 	num::NonZeroU8,
 	ops::Neg,
@@ -11,47 +10,17 @@ use crate::transposition_table::TranspositionTableRef;
 
 const KING_WORTH: u32 = 2;
 
-#[derive(Debug, Clone, Copy, PartialEq)]
-pub enum Evaluation {
-	ForceWin(u32),
-	FloatEval(f32),
-	ForceLoss(u32),
-}
-
-impl PartialOrd for Evaluation {
-	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-		Some(self.cmp(other))
-	}
-}
-
-impl Eq for Evaluation {}
-
-impl Ord for Evaluation {
-	fn cmp(&self, other: &Self) -> Ordering {
-		match self {
-			Evaluation::ForceWin(moves) => match other {
-				Self::ForceWin(other_moves) => moves.cmp(other_moves).reverse(),
-				_ => Ordering::Greater,
-			},
-			Evaluation::FloatEval(eval) => match other {
-				Self::ForceWin(_) => Ordering::Less,
-				Self::FloatEval(other_eval) => eval.total_cmp(other_eval),
-				Self::ForceLoss(_) => Ordering::Greater,
-			},
-			Evaluation::ForceLoss(moves) => match other {
-				Self::ForceLoss(other_moves) => moves.cmp(other_moves),
-				_ => Ordering::Less,
-			},
-		}
-	}
-}
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct Evaluation(i16);
 
 impl Display for Evaluation {
 	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-		match self {
-			Self::ForceWin(moves) => write!(f, "+M{moves}"),
-			Self::FloatEval(eval) => write!(f, "{eval:+}"),
-			Self::ForceLoss(moves) => write!(f, "-M{moves}"),
+		if self.is_force_win() {
+			write!(f, "+M{}", self.force_sequence_length().unwrap())
+		} else if self.is_force_loss() {
+			write!(f, "-M{}", self.force_sequence_length().unwrap())
+		} else {
+			write!(f, "{:+}", self.to_f32().unwrap())
 		}
 	}
 }
@@ -60,41 +29,82 @@ impl Neg for Evaluation {
 	type Output = Self;
 
 	fn neg(self) -> Self::Output {
-		match self {
-			Self::ForceWin(moves) => Self::ForceLoss(moves),
-			Self::FloatEval(eval) => Self::FloatEval(-eval),
-			Self::ForceLoss(moves) => Self::ForceWin(moves),
-		}
+		Self(-self.0)
 	}
 }
 
 impl Evaluation {
-	const WIN: Self = Self::ForceWin(0);
-	const LOSS: Self = Self::ForceLoss(0);
-	const DRAW: Self = Self::FloatEval(0.0);
+	const NULL_MAX: Self = Self(i16::MAX);
+	const NULL_MIN: Self = Self(i16::MIN + 1);
 
-	fn increment(self) -> Self {
-		match self {
-			Self::ForceWin(moves) => Self::ForceWin(moves + 1),
-			Self::FloatEval(_) => self,
-			Self::ForceLoss(moves) => Self::ForceLoss(moves + 1),
+	pub const WIN: Self = Self(i16::MAX - 1);
+	pub const DRAW: Self = Self(0);
+	pub const LOSS: Self = Self(i16::MIN + 2);
+
+	// last fourteen bits set to 1
+	const FORCE_WIN_THRESHOLD: i16 = 0x3FFF;
+
+	pub fn new(eval: f32) -> Self {
+		if eval >= 1.0 {
+			return Self::WIN;
+		} else if eval <= -1.0 {
+			return Self::LOSS;
 		}
+
+		Self((eval * 16384.0) as i16)
 	}
 
-	fn add(self, rhs: f32) -> Self {
-		if let Self::FloatEval(eval) = self {
-			let eval = eval + rhs;
-			if eval >= 1.0 {
-				Self::WIN
-			} else if eval <= 0.0 {
-				Self::LOSS
-			} else {
-				Self::FloatEval(eval)
-			}
+	pub fn to_f32(self) -> Option<f32> {
+		if self.is_force_sequence() {
+			return None;
+		}
+
+		Some(self.0 as f32 / 16384.0)
+	}
+
+	pub fn is_force_win(self) -> bool {
+		self.0 > Self::FORCE_WIN_THRESHOLD
+	}
+
+	pub fn is_force_loss(self) -> bool {
+		self.0 < -Self::FORCE_WIN_THRESHOLD
+	}
+
+	pub fn is_force_sequence(self) -> bool {
+		self.is_force_win() || self.is_force_loss()
+	}
+
+	pub fn force_sequence_length(self) -> Option<u8> {
+		if self == Self::NULL_MAX || self == Self::NULL_MIN {
+			return None;
+		}
+
+		if self.is_force_win() {
+			Some((Self::WIN.0 - self.0) as u8)
+		} else if self.is_force_loss() {
+			Some((self.0 - Self::LOSS.0) as u8)
+		} else {
+			None
+		}
+	}
+
+	fn increment(self) -> Self {
+		if self.is_force_win() {
+			Self(self.0 - 1)
+		} else if self.is_force_loss() {
+			Self(self.0 + 1)
 		} else {
 			self
 		}
 	}
+
+	fn add(self, rhs: f32) -> Self {
+		let Some(eval) = self.to_f32() else {
+			return self;
+		};
+
+		Self::new(eval + rhs)
+	}
 }
 
 fn eval_position(board: CheckersBitBoard) -> Evaluation {
@@ -115,7 +125,7 @@ fn eval_position(board: CheckersBitBoard) -> Evaluation {
 
 	// avoiding a divide by zero error
 	if dark_eval + light_eval != 0.0 {
-		Evaluation::FloatEval((dark_eval - light_eval) / (dark_eval + light_eval))
+		Evaluation::new((dark_eval - light_eval) / (dark_eval + light_eval))
 	} else {
 		Evaluation::DRAW
 	}
@@ -245,28 +255,43 @@ pub fn current_evaluation(
 	board: CheckersBitBoard,
 	table: TranspositionTableRef,
 ) -> Evaluation {
-	let mut alpha = Evaluation::LOSS;
-	let mut beta = Evaluation::WIN;
+	let mut alpha = Evaluation::NULL_MIN;
+	let mut beta = Evaluation::NULL_MAX;
 	for i in 0..depth {
 		let mut eval = negamax(i, alpha, beta, board, table);
 
-		while (eval < alpha) || (eval > beta) {
+		while (eval <= alpha) || (eval >= beta) {
 			eval = negamax(i, alpha, beta, board, table);
 
 			if eval <= alpha {
-				alpha = Evaluation::LOSS;
+				alpha = Evaluation::NULL_MIN;
 			} else if eval >= beta {
-				beta = Evaluation::WIN;
+				beta = Evaluation::NULL_MAX;
 			}
 		}
 
-		alpha = Evaluation::max(eval.add(0.125), Evaluation::LOSS);
-		beta = Evaluation::min(eval.add(-0.125), Evaluation::WIN);
+		if alpha.is_force_loss() {
+			alpha = Evaluation::NULL_MIN;
+		} else {
+			alpha = eval.add(-0.125);
+		}
+
+		if beta.is_force_win() {
+			beta = Evaluation::NULL_MAX;
+		} else {
+			beta = eval.add(0.125);
+		}
 	}
 
 	let mut eval = negamax(depth, alpha, beta, board, table);
 	if (eval <= alpha) || (eval >= beta) {
-		eval = negamax(depth, Evaluation::LOSS, Evaluation::WIN, board, table);
+		eval = negamax(
+			depth,
+			Evaluation::NULL_MIN,
+			Evaluation::NULL_MAX,
+			board,
+			table,
+		);
 	}
 	eval
 }
@@ -274,7 +299,7 @@ pub fn current_evaluation(
 pub fn best_move(depth: u8, board: CheckersBitBoard, table: TranspositionTableRef) -> Move {
 	let moves = PossibleMoves::moves(board).into_iter();
 	let mut best_move = None;
-	let mut best_eval = Evaluation::LOSS;
+	let mut best_eval = Evaluation::NULL_MIN;
 	for current_move in moves {
 		let current_board = unsafe { current_move.apply_to(board) };
 		let current_eval = if board.turn() == current_board.turn() {
@@ -291,3 +316,36 @@ pub fn best_move(depth: u8, board: CheckersBitBoard, table: TranspositionTableRe
 
 	best_move.unwrap()
 }
+
+#[cfg(test)]
+mod tests {
+	use super::*;
+
+	#[test]
+	fn zero_eval() {
+		let draw = Evaluation::new(0.0);
+		assert_eq!(draw, Evaluation::DRAW);
+		assert_eq!(draw.to_f32(), Some(0.0));
+		assert_eq!(draw.to_string(), "+0");
+	}
+
+	#[test]
+	fn comparisons() {
+		assert!(Evaluation::NULL_MAX > Evaluation::WIN);
+		assert!(Evaluation::WIN > Evaluation::new(0.5));
+		assert!(Evaluation::new(0.5) > Evaluation::DRAW);
+		assert!(Evaluation::DRAW > Evaluation::new(-0.5));
+		assert!(Evaluation::new(-0.5) > Evaluation::LOSS);
+		assert!(Evaluation::LOSS > Evaluation::NULL_MIN);
+	}
+
+	#[test]
+	fn negations() {
+		assert_eq!(-Evaluation::NULL_MAX, Evaluation::NULL_MIN);
+		assert_eq!(-Evaluation::NULL_MIN, Evaluation::NULL_MAX);
+		assert_eq!(-Evaluation::WIN, Evaluation::LOSS);
+		assert_eq!(-Evaluation::LOSS, Evaluation::WIN);
+		assert_eq!(-Evaluation::DRAW, Evaluation::DRAW);
+		assert_eq!(-Evaluation::new(0.5), Evaluation::new(-0.5));
+	}
+}
diff --git a/engine/src/main.rs b/engine/src/main.rs
index 6b8bd89..245bd97 100644
--- a/engine/src/main.rs
+++ b/engine/src/main.rs
@@ -5,5 +5,5 @@ const DEPTH: u8 = 18;
 fn main() {
 	let board = CheckersBitBoard::starting_position();
 	let mut table = TranspositionTable::new(50_000);
-	println!("{:?}", current_evaluation(DEPTH, board, table.mut_ref()));
+	println!("{}", current_evaluation(DEPTH, board, table.mut_ref()));
 }