Implement multithreading

5 files changed, 64 insertions, 6 deletions

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 {
diff --git a/cli/src/eval.rs b/cli/src/eval.rs
index 72fa32a..8076af1 100644
--- a/cli/src/eval.rs
+++ b/cli/src/eval.rs
@@ -1,6 +1,6 @@
 use ai::{CheckersBitBoard, Move};
 pub fn eval(depth: usize) -> f32 {
-	ai::eval(depth, 0.0, 1.0, CheckersBitBoard::starting_position())
+	ai::eval_multithreaded(depth, 0.0, 1.0, CheckersBitBoard::starting_position())
 }
 
 pub fn best_move(depth: usize) -> Move {
diff --git a/model/Cargo.toml b/model/Cargo.toml
index f264a17..cdda386 100644
--- a/model/Cargo.toml
+++ b/model/Cargo.toml
@@ -8,6 +8,7 @@ edition = "2018"
 
 [dependencies]
 serde = { version = "1.0.126", optional = true, features = ["derive"] }
+rayon = "1"
 
 [dev-dependencies]
 proptest = "1.0.0"
diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs
index 98a25e2..7d32a27 100644
--- a/model/src/possible_moves.rs
+++ b/model/src/possible_moves.rs
@@ -1,5 +1,6 @@
 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;
@@ -94,6 +95,8 @@ impl PossibleMovesIter {
 	}
 }
 
+unsafe impl Send for PossibleMovesIter {}
+
 impl Iterator for PossibleMovesIter {
 	type Item = Move;