Big changes

13 files changed, 409 insertions, 373 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 71c8ba9..6907ca9 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -2,10 +2,14 @@
 members = [

 	"model",

 	"ai",

-	"cli",

 	"ui"

 ]

 

+[profile.dev]

+opt-level = 3

+

 [profile.release]

 lto = true

-panic = 'abort'
\ No newline at end of file
+panic = 'abort'

+incremental = false

+codegen-units = 1

diff --git a/ai/Cargo.toml b/ai/Cargo.toml
index 59a4b82..6a4ea61 100644
--- a/ai/Cargo.toml
+++ b/ai/Cargo.toml
@@ -8,8 +8,7 @@ edition = "2018"
 
 [dependencies]
 model = {path = "../model"}
-rayon = "1"
-parking_lot = "0.11"
+parking_lot = "0.12"
 
 [dev-dependencies]
-criterion = "0.3"
\ No newline at end of file
+criterion = "0.5"
\ No newline at end of file
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,
+		}
+	}
+}
diff --git a/cli/Cargo.toml b/cli/Cargo.toml
deleted file mode 100644
index 093c594..0000000
--- a/cli/Cargo.toml
+++ /dev/null
@@ -1,12 +0,0 @@
-[package]
-name = "cli"
-version = "0.1.0"
-authors = ["Mike White <botahamec@outlook.com>"]
-edition = "2018"
-
-# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
-
-[dependencies]
-clap = "2"
-ai = {path = "../ai"}
-rayon = "1.5"
\ No newline at end of file
diff --git a/cli/src/eval.rs b/cli/src/eval.rs
deleted file mode 100644
index 8076af1..0000000
--- a/cli/src/eval.rs
+++ /dev/null
@@ -1,8 +0,0 @@
-use ai::{CheckersBitBoard, Move};
-pub fn eval(depth: usize) -> f32 {
-	ai::eval_multithreaded(depth, 0.0, 1.0, CheckersBitBoard::starting_position())
-}
-
-pub fn best_move(depth: usize) -> Move {
-	ai::best_move(depth, CheckersBitBoard::starting_position())
-}
diff --git a/cli/src/main.rs b/cli/src/main.rs
deleted file mode 100644
index d230398..0000000
--- a/cli/src/main.rs
+++ /dev/null
@@ -1,86 +0,0 @@
-use ai::CheckersBitBoard;
-use clap::{App, Arg, SubCommand};
-
-mod eval;
-mod perft;
-
-fn main() {
-	let matches = App::new("Ampere")
-		.version("0.1")
-		.author("Botahamec <botahamec@outlook.com>")
-		.about("An American Checkers AI")
-		.subcommand(
-			SubCommand::with_name("perft")
-				.about("Calculate the number of possible moves")
-				.arg(
-					Arg::with_name("depth")
-						.required(true)
-						.short("d")
-						.takes_value(true)
-						.help("The depth to go to"),
-				),
-		)
-		.subcommand(
-			SubCommand::with_name("eval")
-				.about("Calculate the advantage")
-				.arg(
-					Arg::with_name("depth")
-						.required(true)
-						.short("d")
-						.takes_value(true)
-						.help("The depth to go to"),
-				),
-		)
-		.subcommand(
-			SubCommand::with_name("best")
-				.about("Calculate the best move")
-				.arg(
-					Arg::with_name("depth")
-						.required(true)
-						.short("d")
-						.takes_value(true)
-						.help("The depth to go to"),
-				),
-		)
-		.get_matches();
-
-	if let Some(matches) = matches.subcommand_matches("perft") {
-		println!(
-			"{}",
-			perft::positions(
-				CheckersBitBoard::starting_position(),
-				matches
-					.value_of("depth")
-					.unwrap()
-					.parse::<usize>()
-					.expect("Error: not a valid number")
-			)
-		);
-	}
-
-	if let Some(matches) = matches.subcommand_matches("eval") {
-		println!(
-			"{}",
-			eval::eval(
-				matches
-					.value_of("depth")
-					.unwrap()
-					.parse::<usize>()
-					.expect("Error: not a valid number")
-			)
-		);
-	}
-
-	if let Some(matches) = matches.subcommand_matches("best") {
-		println!(
-			"{}",
-			eval::best_move(
-				matches
-					.value_of("depth")
-					.unwrap()
-					.parse()
-					.expect("Error: not a valid number")
-			)
-		)
-	}
-}
diff --git a/cli/src/perft.rs b/cli/src/perft.rs
deleted file mode 100644
index 535aec0..0000000
--- a/cli/src/perft.rs
+++ /dev/null
@@ -1,26 +0,0 @@
-use ai::{CheckersBitBoard, Move, PossibleMoves};
-use rayon::prelude::*;
-use std::fmt::{Display, Formatter};
-
-#[derive(Clone)]
-struct PerftResult {
-	result: Vec<(Move, usize)>,
-}
-
-pub fn positions(board: CheckersBitBoard, depth: usize) -> usize {
-	let moves = PossibleMoves::moves(board);
-
-	if depth == 0 {
-		1
-	} else {
-		let mut total = 0;
-
-		for current_move in moves {
-			// safety: we got this move out of the list of possible moves, so it's definitely valid
-			let board = unsafe { current_move.apply_to(board) };
-			total += positions(board, depth - 1);
-		}
-
-		total
-	}
-}
diff --git a/model/src/board.rs b/model/src/board.rs
index e110575..1cc8d1c 100644
--- a/model/src/board.rs
+++ b/model/src/board.rs
@@ -100,7 +100,7 @@ impl CheckersBitBoard {
 
 	#[must_use]
 	pub const fn hash_code(self) -> u64 {
-		(((self.color & self.pieces) as u64) << 32) | (self.pieces as u64)
+		(((self.color & self.pieces) as u64) << 32) | (((!self.color & self.pieces) as u64) << 32)
 	}
 
 	/// Gets the bits that represent where pieces are on the board
diff --git a/model/src/coordinates.rs b/model/src/coordinates.rs
index 7aea88b..c821e1f 100644
--- a/model/src/coordinates.rs
+++ b/model/src/coordinates.rs
@@ -71,26 +71,24 @@ impl SquareCoordinate {
 			} else {
 				None
 			}
+		} else if self.file % 2 == 1 {
+			let column_value = match self.file {
+				1 => 19,
+				3 => 13,
+				5 => 7,
+				7 => 1,
+				_ => unreachable!(),
+			};
+			let row_value = match self.rank {
+				1 => 0,
+				3 => 8,
+				5 => 16,
+				7 => 24,
+				_ => unreachable!(),
+			};
+			Some((column_value + row_value) % 32)
 		} else {
-			if self.file % 2 == 1 {
-				let column_value = match self.file {
-					1 => 19,
-					3 => 13,
-					5 => 7,
-					7 => 1,
-					_ => unreachable!(),
-				};
-				let row_value = match self.rank {
-					1 => 0,
-					3 => 8,
-					5 => 16,
-					7 => 24,
-					_ => unreachable!(),
-				};
-				Some((column_value + row_value) % 32)
-			} else {
-				None
-			}
+			None
 		}
 	}
 }
diff --git a/model/src/possible_moves.rs b/model/src/possible_moves.rs
index 0feee6e..5140bb7 100644
--- a/model/src/possible_moves.rs
+++ b/model/src/possible_moves.rs
@@ -110,6 +110,7 @@ impl Iterator for PossibleMovesIter {
 
 	fn next(&mut self) -> Option<Self::Item> {
 		if self.length > self.index {
+			debug_assert!(self.index < POSSIBLE_MOVES_ITER_SIZE);
 			let next_move = unsafe { self.moves.as_ref().get_unchecked(self.index).assume_init() };
 			self.index += 1;
 			Some(next_move)
@@ -137,17 +138,22 @@ impl Iterator for PossibleMovesIter {
 	where
 		Self: Sized,
 	{
-		Some(unsafe {
-			self.moves
-				.as_ref()
-				.get_unchecked(self.length - 1)
-				.assume_init()
-		})
+		debug_assert!(self.length <= POSSIBLE_MOVES_ITER_SIZE);
+		if self.length == 0 {
+			None
+		} else {
+			Some(unsafe {
+				self.moves
+					.as_ref()
+					.get_unchecked(self.length - 1)
+					.assume_init()
+			})
+		}
 	}
 
 	// TODO test
 	fn nth(&mut self, n: usize) -> Option<Self::Item> {
-		if self.length - self.index < n {
+		if self.length == 0 || self.length - self.index < n {
 			None
 		} else {
 			self.index += n;
@@ -469,11 +475,21 @@ impl PossibleMoves {
 			backward_right_movers = 0;
 		}
 
+		let can_jump = if forward_left_movers != 0
+			|| forward_right_movers != 0
+			|| backward_left_movers != 0
+			|| backward_right_movers != 0
+		{
+			2
+		} else {
+			0
+		};
+
 		Self {
 			forward_left_movers,
 			forward_right_movers,
 			backward_left_movers,
-			backward_right_movers: backward_right_movers | 2,
+			backward_right_movers: backward_right_movers | can_jump,
 		}
 	}
 
@@ -511,11 +527,92 @@ impl PossibleMoves {
 			forward_right_movers = 0;
 		}
 
+		let can_jump = if forward_left_movers != 0
+			|| forward_right_movers != 0
+			|| backward_left_movers != 0
+			|| backward_right_movers != 0
+		{
+			2
+		} else {
+			0
+		};
+
 		Self {
 			forward_left_movers,
 			forward_right_movers,
 			backward_left_movers,
-			backward_right_movers: backward_right_movers | 2,
+			backward_right_movers: backward_right_movers | can_jump,
+		}
+	}
+
+	const fn has_jumps_dark(board: CheckersBitBoard) -> bool {
+		const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011;
+		const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100;
+		const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000;
+		const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100;
+
+		let not_occupied = !board.pieces_bits();
+		let enemy_pieces = board.pieces_bits() & !board.color_bits();
+		let friendly_pieces = board.pieces_bits() & board.color_bits();
+
+		let forward_left_spaces =
+			not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK;
+		let forward_right_spaces =
+			not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK;
+
+		let forward_spaces = forward_left_spaces | forward_right_spaces;
+
+		if board.king_bits() > 0 {
+			let backward_left_spaces =
+				not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK;
+			let backward_right_spaces =
+				not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK;
+			let backward_spaces = backward_left_spaces | backward_right_spaces;
+
+			let backward_spaces = board.king_bits() & backward_spaces;
+			friendly_pieces & (forward_spaces | backward_spaces) != 0
+		} else {
+			friendly_pieces & forward_spaces != 0
+		}
+	}
+
+	const fn has_jumps_light(board: CheckersBitBoard) -> bool {
+		const FORWARD_LEFT_MASK: u32 = 0b00110000111100111111001111000011;
+		const FORWARD_RIGHT_MASK: u32 = 0b00111100111111001111000011001100;
+		const BACKWARD_LEFT_MASK: u32 = 0b11110011111100111100001100110000;
+		const BACKWARD_RIGHT_MASK: u32 = 0b11111100111100001100110000111100;
+
+		let not_occupied = !board.pieces_bits();
+		let enemy_pieces = board.pieces_bits() & board.color_bits();
+		let friendly_pieces = board.pieces_bits() & !board.color_bits();
+
+		let backward_left_spaces =
+			not_occupied.rotate_left(2) & enemy_pieces.rotate_left(1) & BACKWARD_LEFT_MASK;
+		let backward_right_spaces =
+			not_occupied.rotate_left(14) & enemy_pieces.rotate_left(7) & BACKWARD_RIGHT_MASK;
+
+		let backward_spaces = backward_left_spaces | backward_right_spaces;
+
+		if board.king_bits() > 0 {
+			let forward_left_spaces =
+				not_occupied.rotate_right(14) & enemy_pieces.rotate_right(7) & FORWARD_LEFT_MASK;
+			let forward_right_spaces =
+				not_occupied.rotate_right(2) & enemy_pieces.rotate_right(1) & FORWARD_RIGHT_MASK;
+			let forward_spaces = forward_left_spaces | forward_right_spaces;
+
+			let forward_spaces = board.king_bits() & forward_spaces;
+			friendly_pieces & (forward_spaces | backward_spaces) != 0
+		} else {
+			friendly_pieces & backward_spaces != 0
+		}
+	}
+
+	#[inline(always)]
+	// TODO optimize
+	pub const fn has_jumps(board: CheckersBitBoard) -> bool {
+		match board.turn() {
+			PieceColor::Light => Self::has_jumps_light(board),
+			PieceColor::Dark => Self::has_jumps_dark(board),
 		}
 	}
 
@@ -643,13 +740,12 @@ mod tests {
 				Some(p) => p,
 				None => handle_alloc_error(layout),
 			};
-		let iter = PossibleMovesIter {
+
+		PossibleMovesIter {
 			moves: ptr,
 			index: 0,
 			length: 0,
-		};
-
-		iter
+		}
 	}
 
 	fn setup_add_move_to_iter_invalid() -> (PossibleMovesIter, PossibleMoves) {
@@ -692,8 +788,8 @@ mod tests {
 		);
 
 		assert_eq!(
-			PossibleMoves::has_jumps_at(start, 0),
-			PossibleMoves::has_jumps_at(flip, 0)
+			PossibleMoves::has_jumps(start),
+			PossibleMoves::has_jumps(flip)
 		)
 	}