From f1d3cf99a122c63e09f33ca30d6c09fd29d66a24 Mon Sep 17 00:00:00 2001
From: Mike White <botahamec@outlook.com>
Date: Sat, 18 Sep 2021 12:25:15 -0400
Subject: Implement multithreading

---
 ai/Cargo.toml |  2 ++
 ai/src/lib.rs | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 59 insertions(+), 5 deletions(-)

(limited to 'ai')

diff --git a/ai/Cargo.toml b/ai/Cargo.toml
index 64f7dcc..59a4b82 100644
--- a/ai/Cargo.toml
+++ b/ai/Cargo.toml
@@ -8,6 +8,8 @@ edition = "2018"
 
 [dependencies]
 model = {path = "../model"}
+rayon = "1"
+parking_lot = "0.11"
 
 [dev-dependencies]
 criterion = "0.3"
\ No newline at end of file
diff --git a/ai/src/lib.rs b/ai/src/lib.rs
index 17b5441..350c580 100644
--- a/ai/src/lib.rs
+++ b/ai/src/lib.rs
@@ -1,4 +1,6 @@
 pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
+use parking_lot::{Mutex, RwLock};
+use rayon::prelude::*;
 use std::mem::MaybeUninit;
 
 const KING_WORTH: u32 = 2;
@@ -27,18 +29,24 @@ fn eval_position(board: CheckersBitBoard) -> f32 {
 	}
 }
 
-pub fn eval(depth: usize, mut alpha: f32, beta: f32, board: CheckersBitBoard) -> f32 {
-	if depth == 0 {
+pub fn eval_singlethreaded(
+	depth: usize,
+	mut alpha: f32,
+	beta: f32,
+	board: CheckersBitBoard,
+) -> f32 {
+	if depth <= 1 {
 		eval_position(board)
 	} else {
 		let turn = board.turn();
 		let mut best_eval = f32::NEG_INFINITY;
+
 		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(depth - 1, 1.0 - beta, 1.0 - alpha, board)
+				1.0 - eval_singlethreaded(depth - 1, 1.0 - beta, 1.0 - alpha, board)
 			} else {
-				eval(depth - 1, alpha, beta, board)
+				eval_singlethreaded(depth - 1, alpha, beta, board)
 			};
 
 			if current_eval >= beta {
@@ -57,11 +65,55 @@ pub fn eval(depth: usize, mut alpha: f32, beta: f32, board: CheckersBitBoard) ->
 	}
 }
 
+pub fn eval_multithreaded(depth: usize, alpha: f32, beta: f32, board: CheckersBitBoard) -> f32 {
+	if depth <= 1 {
+		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();
+		PossibleMoves::moves(board)
+			.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();
 	for current_move in PossibleMoves::moves(board) {
-		let current_eval = eval(depth - 1, best_eval, 1.0, unsafe {
+		let current_eval = eval_multithreaded(depth - 1, best_eval, 1.0, unsafe {
 			current_move.apply_to(board)
 		});
 		if current_eval > best_eval {
-- 
cgit v1.2.3