Checkers
Computerwarming the interpreter…
You
I built a Network Checkers game in high school. The source code is long-lost, but I have rebuilt it for you here using the same search engine as Chessmate.
The same engine in ClojureScript:
- The game's state: !game is its atom, which the commands that change it take first
- Start a new game with these players, at once; Take Back goes back to the last one. Returns !game
- Let the computer play both sides, in the game as it stands
- Move from 23 to 19; a jump names every square it lands on, as (checkers/move! !game 22 15 6)
- Let the computer think 2 s a move for White
- Search 8 plies deep for White; 0 for no limit
- Take back the last move, and the computer's reply to yours; with no move, go back to the last game
- Go back to the game as it was after White's first move, as a click on a move does
- Pause the computer; (checkers/resume! !game) goes on
- Turn the board round
- The legal moves: the jumps, when a side must jump
- The board as text, Black's back rank first
- The evaluation of this position, without searching
- The position in FEN
- Print the game as PDN
- Start a new game from a position in FEN
- The game, with what the computer is doing
- Resign the game
The Rules
- English draughts, which America calls checkers: 12 men a side on the 32 dark squares. White moves first here, as in chess, where English draughts has Black first
- A man steps one square diagonally forward; a king, one square diagonally either way
- A piece jumps an enemy piece beside it to the empty square beyond, taking it, and jumps again while it can, all in one move. Men jump forward only
- Whoever can jump must, choosing among the jumps, and must jump as far as the jump chosen goes
- A man that reaches the far row is crowned a king, and its move ends there
- A side with no move, its pieces all taken or blocked, loses. A position that occurs a third time, or forty moves each without a jump or a man moved, is a draw
Drag a piece, or tap it and then its square; a jump by its last square, or square by square · ← ↑ → ↓ move on the board · Enter picks up and puts down · Esc puts down
The Engine
- Chessmate 2026's search, on a Checkers board: a principal variation search with a transposition table, iterative deepening, killer moves, history and late move reductions
- At its horizon it plays out the jumps each side must make, and it searches a side's only move a ply deeper
- It thinks in a background worker, and plays stronger the longer it thinks
- Written in ClojureScript, as it plays at /checkers-cljs, its board, evaluation and search are ported here to Rust, function for function, and compiled to a WebAssembly module of 124 KB, and again for many cores. On one core it plays exactly as the ClojureScript does, the same moves from the same positions searched, and faster
- Where the browser lets it, it searches on every core at once (Multiple Cores, in the settings): each core searches the same position, and they share what they find in one table, as Chessmate does. So it searches several times as many positions a second, and deeper in the same time
- The game, the board and the Listener are still ClojureScript, in this page's Lisp machine, so the game is one game on both pages
This engine:
Source
The engine: 5 files of Rust, 2333 lines, then the worker that runs it and the crate's manifest · the game, in ClojureScript: /checkers-cljs
src/lib.rs · 272 lines
//! Checkers in WebAssembly: checkers.board, checkers.eval and checkers.search, ported from ClojureScript to Rust, which
//! /checkers's background worker runs (../worker.js, with engine.js). The search is the ClojureScript's step for step,
//! and plays node for node as it does; it is only faster, and where the page may share memory it searches on every
//! core (threads.rs).
//!
//! The module's interface is Chessmate's (src/wasm/chessmate/src/lib.rs): plain numbers and one buffer of bytes, `io`,
//! for text both ways: a position in FEN and moves as players write them go in, and reports come out as JSON. It needs
//! two functions of its host: `now`, the clock in milliseconds, which the search reads every 256 nodes, and
//! `on_iteration`, which is handed each completed iteration's report while the search goes on.
//!
//! It is built twice from this source (scripts/chess/build.mjs): for one thread, checkers.wasm, and with atomics and
//! shared memory, checkers-threads.wasm, which searches on every core. That build imports its memory, which the worker
//! shares with the helpers' workers, and a third function of its host, `wake`; and it exports what the helpers need:
//! `stack`, `control`, `helpers` and `help`, and each helper's stack pointer.
mod board;
mod eval;
mod search;
mod threads;
use std::cell::UnsafeCell;
use std::fmt::Write;
use search::{Engine, Options, Report};
extern "C" {
/// The clock, in milliseconds.
fn now() -> f64;
/// A completed iteration's report, as JSON, len bytes of io.
fn on_iteration(len: usize);
}
fn clock() -> f64 {
// Safety: the host's function takes no arguments and returns a number
unsafe { now() }
}
/// The size of io, which holds the longest line a search reports many times over.
const IO_SIZE: usize = 65536;
struct Machine {
engine: Engine,
io: Box<[u8; IO_SIZE]>,
}
struct Global(UnsafeCell<Option<Machine>>);
// Safety: only the worker's own thread, the main thread, reaches the machine, and the host enters the module there once
// at a time: on_iteration's host only reads memory, and calls nothing back. Helper threads enter only `help`, which
// keeps to their own engines (threads.rs).
unsafe impl Sync for Global {}
static MACHINE: Global = Global(UnsafeCell::new(None));
fn machine() -> &'static mut Machine {
// Safety: see Global
unsafe {
(*MACHINE.0.get()).get_or_insert_with(|| Machine {
engine: Engine::new(clock),
io: vec![0; IO_SIZE].into_boxed_slice().try_into().unwrap(),
})
}
}
/// Write text into io, cut to its size, and return its length.
fn put(io: &mut [u8; IO_SIZE], text: &str) -> usize {
let n = text.len().min(IO_SIZE);
io[..n].copy_from_slice(&text.as_bytes()[..n]);
n
}
/// The text the host wrote into io.
fn text(io: &[u8; IO_SIZE], len: usize) -> String {
String::from_utf8_lossy(&io[..len.min(IO_SIZE)]).into_owned()
}
/// A search's report, as JSON with the fields of checkers.worker's replies but their type and id.
fn json(r: &Report) -> String {
let mut s = String::with_capacity(256);
let mv =
r.mv.map_or("null".to_string(), |m| format!("\"{}\"", board::notation(m)));
let mate = r.mate.map_or("null".to_string(), |m| m.to_string());
let pv: Vec<String> = r.pv.iter().map(|m| format!("\"{}\"", m)).collect();
let _ = write!(
s,
"{{\"move\":{},\"score\":{},\"mate\":{},\"depth\":{},\"reached\":{},\"pv\":[{}],\"nodes\":{},\"nps\":{},\"ms\":{}}}",
mv,
r.score,
mate,
r.depth,
r.seldepth,
pv.join(","),
r.nodes,
r.nps as i64,
r.ms as i64
);
s
}
/// Where io is: the host writes text there before a call that reads it, and reads what a call wrote.
#[no_mangle]
pub extern "C" fn io() -> *mut u8 {
machine().io.as_mut_ptr()
}
/// Set the board to the position in FEN, len bytes of io. Returns 0, or when the FEN is refused, minus the length of
/// the reason, written into io.
#[no_mangle]
pub extern "C" fn set_position(len: usize) -> i32 {
let Machine { engine, io } = machine();
match engine.b.set_position(&text(io, len)) {
Ok(()) => 0,
Err(why) => -(put(io, &why) as i32),
}
}
/// Play the move written as players write it, len bytes of io. Returns 0, or when it is not a legal move, minus the
/// length of the reason, written into io.
#[no_mangle]
pub extern "C" fn play(len: usize) -> i32 {
let Machine { engine, io } = machine();
match engine.b.play_notation(&text(io, len)) {
Ok(()) => 0,
Err(why) => -(put(io, &why) as i32),
}
}
/// The computer's move for the position on the board, as checkers.search/think finds it, with its options, NaN for an
/// option not given. Each completed iteration's report goes to on_iteration; the last report is written into io as
/// JSON, and its length returned.
#[no_mangle]
pub extern "C" fn think(ms: f64, max_ms: f64, depth: f64, ply_limit: f64, nodes: f64, contempt: f64) -> usize {
let given = |x: f64| if x.is_nan() { None } else { Some(x) };
let options = Options {
ms,
max_ms: given(max_ms),
depth: depth as i32,
ply_limit: given(ply_limit).map(|p| p as i32),
nodes: given(nodes),
contempt: contempt as i32,
};
let Machine { engine, io } = machine();
let r = engine.think(&options, &mut |r: &Report| {
let len = put(io, &json(r));
// Safety: the host reads len bytes of io, and calls nothing back
unsafe { on_iteration(len) }
});
put(io, &json(&r))
}
/// The evaluation of the position on the board, for the side to move, in hundredths of a man.
#[no_mangle]
pub extern "C" fn evaluate() -> i32 {
eval::evaluate(&machine().engine.b)
}
/// The number of move sequences of depth moves from the position on the board.
#[no_mangle]
pub extern "C" fn perft(depth: i32) -> f64 {
machine().engine.b.perft(depth) as f64
}
/// Forget everything learnt: the table, the history and the killers, the helpers' too.
#[no_mangle]
pub extern "C" fn clear() {
machine().engine.s.clear();
threads::clear();
}
/// Give the transposition table 2^bits entries of 16 bytes each: at most 1 GB, or 128 MB when threaded, whose memory
/// can grow to 256 MB only (build.mjs).
#[no_mangle]
pub extern "C" fn resize(bits: i32) {
let most = if cfg!(feature = "threads") { 23 } else { 26 };
machine().engine.s.resize(bits.clamp(1, most));
}
/// The position on the board in FEN, written into io; returns its length.
#[no_mangle]
pub extern "C" fn fen() -> usize {
let Machine { engine, io } = machine();
put(io, &engine.b.fen())
}
/// The legal moves on the board as players write them, in generation order, separated by spaces, written into io;
/// returns the length.
#[no_mangle]
pub extern "C" fn legal() -> usize {
let Machine { engine, io } = machine();
let moves: Vec<String> = engine.b.legal_moves().into_iter().map(board::notation).collect();
put(io, &moves.join(" "))
}
/// What only the threaded build has: the helpers' side of the interface, and an allocator for many threads.
#[cfg(feature = "threads")]
mod threaded {
use std::alloc::{GlobalAlloc, Layout, System};
use std::hint::spin_loop;
use std::sync::atomic::{
AtomicBool,
Ordering::{Acquire, Relaxed, Release},
};
use crate::{clock, threads};
/// The worker has started n helpers, threads 1 to n, which join each search from now on.
#[no_mangle]
pub extern "C" fn helpers(n: i32) {
threads::set_helpers(n);
}
/// A new stack of bytes for a helper, which its worker points its stack pointer at: the address of its top, where
/// a stack starts, 16-byte aligned as WebAssembly's C ABI wants it. Kept for the module's life.
#[no_mangle]
pub extern "C" fn stack(bytes: usize) -> usize {
let layout = Layout::from_size_align(bytes, 16).unwrap();
// Safety: the layout's size is not 0
let bottom = unsafe { std::alloc::alloc(layout) };
if bottom.is_null() {
std::alloc::handle_alloc_error(layout);
}
bottom as usize + bytes
}
/// Where the words the workers and the page reach are: threads.rs's CONTROL, SEQ, PULSE, SEARCH and ABANDONED, four
/// 32-bit words in that order.
#[no_mangle]
pub extern "C" fn control() -> usize {
threads::control() as usize
}
/// On helper thread t: its part in the search under way, if any. Returns when the search has finished.
#[no_mangle]
pub extern "C" fn help(t: usize) {
threads::help(t, clock);
}
/// Rust's allocator for WebAssembly, dlmalloc, taken in turns under a spin lock: the standard library is prebuilt for
/// one thread, so its allocator has no lock of its own. The search allocates only between iterations, and a helper
/// only as it first joins, so the lock is rarely waited for.
struct Locked;
static LOCK: AtomicBool = AtomicBool::new(false);
fn locked<T>(f: impl FnOnce() -> T) -> T {
while LOCK.compare_exchange_weak(false, true, Acquire, Relaxed).is_err() {
spin_loop();
}
let r = f();
LOCK.store(false, Release);
r
}
// Safety: System's own contracts, one thread at a time
unsafe impl GlobalAlloc for Locked {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
locked(|| System.alloc(layout))
}
unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
locked(|| System.alloc_zeroed(layout))
}
unsafe fn dealloc(&self, p: *mut u8, layout: Layout) {
locked(|| System.dealloc(p, layout))
}
unsafe fn realloc(&self, p: *mut u8, layout: Layout, size: usize) -> *mut u8 {
locked(|| System.realloc(p, layout, size))
}
}
#[global_allocator]
static ALLOCATOR: Locked = Locked;
}src/search.rs · 870 lines
//! Checkers' search, ported from checkers.search, itself Chessmate 2026's search (chessmate.v2.search) step for step
//! where the two games agree. It is negamax, each side maximising the negation of the other's score, with alpha-beta
//! cutoffs, and these of the techniques Chessmate uses:
//!
//! principal variation search the first move with the full window, the rest with a null window, searched again
//! only if they beat it
//! transposition table positions met before, by Zobrist hash, with their scores, depths and best moves
//! iterative deepening depth 1, 2, 3, ... until the time is spent, each iteration ordering the next,
//! within an aspiration window
//! quiescence search at the horizon, the jumps each side must make, until neither has one, so that no
//! exchange is cut off half way
//! move ordering the table's move, jumps by how many pieces they take, killer moves, and the history
//! of quiet moves that caused cutoffs
//! reductions late move reductions, and internal iterative reduction
//! extensions a forced move, a side's only one, is searched a ply deeper
//! draws repetition, and forty moves each without a jump or a man moved
//!
//! Scores are in hundredths of a man, for the side to move. A win in n plies, the other side left without a move, is
//! MATE - n. Every step is the ClojureScript's, in its order, so that the two search node for node alike.
//!
//! Where the page may share memory between workers, the search also runs on every other core, as helper threads that
//! search the same position into the same table (threads.rs, and `help` below). Alone, it is the ClojureScript's.
use std::sync::atomic::{AtomicI32, Ordering::Relaxed};
use std::sync::Arc;
use crate::board::{first_diagonal_of, is_jump, jumps, move_from, notation, Board, QUIET_LIMIT};
use crate::eval::evaluate;
use crate::threads;
pub const INFINITY: i32 = 32000;
pub const MATE: i32 = 31000;
/// Any score beyond this is a win or a loss.
pub const MATE_BOUND: i32 = 30000;
pub const MAX_PLY: i32 = 96;
const MAX_MOVES: i32 = 256;
// Bounds, as the transposition table records them
/// The score is at most this: every move failed low.
const UPPER: i32 = 1;
/// At least this: a move failed high.
const LOWER: i32 = 2;
const EXACT: i32 = 3;
/// The transposition table's words, four per entry (see Search's tt), which every thread of a search reads and writes
/// at once. Each word is read and written whole, and the first is kept XOR'd with the other three, so that an entry
/// read while another thread was writing it, part old and part new, no longer matches its position and counts as a
/// miss, not as another position's score (Hyatt's lockless hashing). A thread alone finds each entry as it left it.
pub struct Table {
words: Box<[AtomicI32]>,
}
impl Table {
/// A table of n words, all 0.
fn new(n: usize) -> Table {
let words = vec![0i32; n].into_boxed_slice(); // zeroed as allocated, not word by word
let len = words.len();
// Safety: AtomicI32 has the size, alignment and bit validity of i32
let words = unsafe {
Box::from_raw(std::ptr::slice_from_raw_parts_mut(
Box::into_raw(words) as *mut AtomicI32,
len,
))
};
Table { words }
}
#[inline(always)]
fn get(&self, i: usize) -> i32 {
self.words[i].load(Relaxed)
}
#[inline(always)]
fn set(&self, i: usize, v: i32) {
self.words[i].store(v, Relaxed)
}
/// Entry e's words: the position's key (the first word unXOR'd), the move, the score, and the depth, bound and
/// generation.
#[inline(always)]
fn entry(&self, e: usize) -> (i32, i32, i32, i32) {
let (w, m, score, info) = (self.get(e), self.get(e + 1), self.get(e + 2), self.get(e + 3));
(w ^ m ^ score ^ info, m, score, info)
}
}
/// What a helper thread takes from the main thread's search as each search starts (threads.rs): the table, and the
/// settings that decide what the table's entries mean, so that the threads' entries agree.
#[cfg_attr(not(feature = "threads"), allow(dead_code))] // only the threaded build has helpers
#[derive(Clone)]
pub struct Settings {
tt: Arc<Table>,
mask: i32,
generation: i32,
contempt: i32,
ply_limit: i32,
/// The deepest iteration.
depth: i32,
}
/// Which iterations helper thread t skips, so that the helpers spread across the depths, ahead of the main thread and
/// behind it, rather than all search the same iteration: Stockfish 9's pattern, which repeats every 20 helpers.
#[cfg_attr(not(feature = "threads"), allow(dead_code))] // only the threaded build has helpers
fn skips(t: usize, depth: i32) -> bool {
const SIZE: [i32; 20] = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4];
const PHASE: [i32; 20] = [0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7];
let i = (t - 1) % 20;
(depth + PHASE[i]) / SIZE[i] % 2 != 0
}
/// The search's state, as checkers.search keeps it in typed arrays.
pub struct Search {
/// Each ply's moves, from ply * MAX_MOVES.
moves: Vec<i32>,
/// The moves' ordering scores.
scores: Vec<i32>,
/// Each ply's quiet moves tried, from ply * 64, for the history's malus.
quiets: Vec<i32>,
/// Two quiet moves per ply that caused cutoffs there.
killers: Vec<i32>,
/// Quiet moves' success, by side * 128 + from * 4 + diagonal.
history: Vec<i32>,
/// The principal variation from each ply, from ply * MAX_PLY.
pv: Vec<i32>,
/// Where each ply's variation ends.
pv_length: Vec<i32>,
stopped: bool,
seldepth: i32,
generation: i32,
mask: i32,
contempt: i32,
/// The best root move of the iteration under way, once one is known, and its score.
root_move: i32,
root_score: i32,
/// The deepest ply any line may reach, the jumps followed included.
ply_limit: i32,
nodes: u64,
/// The clock's reading at which the search stops.
hard: f64,
max_nodes: f64,
/// The transposition table, allocated by the first search that needs it. Four numbers per entry, indexed by the
/// hash's low half: the hash's high half, to tell positions apart; the best move; the score, in the low 16 bits; and
/// the depth + 1 (8 bits), the bound (2 bits) and the search's generation. The helper threads share it (Table).
tt: Arc<Table>,
/// Late move reductions, by depth * 64 + the move's number: more for later moves and deeper searches.
lmr: Vec<i32>,
}
/// What `think` is asked, as checkers.search/think's options.
pub struct Options {
/// The time to aim for, in milliseconds.
pub ms: f64,
/// The time never to exceed: the search stops then, even part way through an iteration. None is ms.
pub max_ms: Option<f64>,
/// The deepest iteration.
pub depth: i32,
/// The deepest ply any line may reach, the jumps followed beyond the iteration's depth included: 95, the most the
/// search's arrays hold, when None.
pub ply_limit: Option<i32>,
/// The most nodes to search, for tests that must not depend on the clock.
pub nodes: Option<f64>,
/// What a draw costs the side to move, in hundredths of a man.
pub contempt: i32,
}
/// A search's report, as think returns it: move None when there is no move, and the side to move has lost.
#[derive(Clone)]
pub struct Report {
pub mv: Option<i32>,
pub score: i32,
pub mate: Option<i32>,
pub depth: i32,
pub seldepth: i32,
/// The line, as players write it.
pub pv: Vec<String>,
pub nodes: u64,
pub ms: f64,
pub nps: f64,
}
/// JavaScript's Math.round, for the times the report gives: to the nearer whole number, halves up.
fn js_round(x: f64) -> f64 {
(x + 0.5).floor()
}
/// A score for the table: a win counted from this position, not from the root.
fn to_table(score: i32, ply: i32) -> i32 {
if score >= MATE_BOUND {
score + ply
} else if score <= -MATE_BOUND {
score - ply
} else {
score
}
}
fn from_table(score: i32, ply: i32) -> i32 {
if score >= MATE_BOUND {
score - ply
} else if score <= -MATE_BOUND {
score + ply
} else {
score
}
}
/// Moves to win for a winning score, negative when the side to move loses; else None.
fn mate_in(score: i32) -> Option<i32> {
if score >= MATE_BOUND {
Some((MATE - score + 1) / 2)
} else if score <= -MATE_BOUND {
Some(-((MATE + score) / 2))
} else {
None
}
}
impl Search {
pub fn new() -> Search {
let (plies, moves) = (MAX_PLY as usize, MAX_MOVES as usize);
let mut lmr = vec![0; 4096];
for d in 1..64 {
for n in 1..64 {
lmr[d * 64 + n] = (0.75 + (d as f64).ln() * (n as f64).ln() / 2.25).floor() as i32;
}
}
Search {
moves: vec![0; plies * moves],
scores: vec![0; plies * moves],
quiets: vec![0; plies * 64],
killers: vec![0; plies * 2],
history: vec![0; 256],
pv: vec![0; plies * plies],
pv_length: vec![0; plies],
stopped: false,
seldepth: 0,
generation: 0,
mask: 0,
contempt: 0,
root_move: 0,
root_score: 0,
ply_limit: 0,
nodes: 0,
hard: 0.0,
max_nodes: 0.0,
tt: Arc::new(Table::new(0)),
lmr,
}
}
/// Give the transposition table 2^bits entries of 16 bytes each: 20 bits is 16 MB.
pub fn resize(&mut self, bits: i32) {
self.tt = Arc::new(Table::new(4 << bits));
self.mask = (1 << bits) - 1;
}
/// Forget everything learnt: the table, the history and the killers.
pub fn clear(&mut self) {
for w in self.tt.words.iter() {
w.store(0, Relaxed);
}
self.history.fill(0);
self.killers.fill(0);
}
}
/// The board and the search, which the search's functions all reach, as checkers' namespaces reach each other's state;
/// and the clock.
pub struct Engine {
pub b: Board,
pub s: Search,
/// The clock, in milliseconds.
pub clock: fn() -> f64,
/// Which thread searches with this engine: 0 the main thread, which keeps the time and reports, 1 and up a helper.
pub thread: usize,
/// A helper's last sight of its main thread's heartbeat: the beat, and when it changed (threads.rs).
pulse: (i32, f64),
}
impl Engine {
pub fn new(clock: fn() -> f64) -> Engine {
Engine {
b: Board::new(),
s: Search::new(),
clock,
thread: 0,
pulse: (0, 0.0),
}
}
/// The engine of helper thread t.
#[cfg_attr(not(feature = "threads"), allow(dead_code))] // only the threaded build has helpers
pub fn helper(clock: fn() -> f64, t: usize) -> Engine {
Engine {
thread: t,
..Engine::new(clock)
}
}
/// Record a search's result for the position on the board. A deeper result for another position is kept unless it
/// is from an earlier search.
fn store(&mut self, depth: i32, bound: i32, score: i32, m: i32, ply: i32) {
let s = &self.s;
let hi = self.b.hash_hi;
let e = 4 * (self.b.hash_lo & s.mask) as usize;
let (key, old, _, info) = s.tt.entry(e);
let generation = s.generation;
let same = key == hi;
if info == 0 || info >> 10 != generation || bound == EXACT || depth + 3 >= (info & 255) - 1 {
let m = if !same || m != 0 { m } else { old };
let score = to_table(score, ply) & 0xFFFF;
let info = (depth + 1) | (bound << 8) | (generation << 10);
s.tt.set(e + 1, m);
s.tt.set(e + 2, score);
s.tt.set(e + 3, info);
s.tt.set(e, hi ^ m ^ score ^ info);
}
}
// Counting nodes, and the clock
/// One more node; every 256 a look at the clock and the node limit.
#[inline(always)]
fn count_node(&mut self) {
self.s.nodes += 1;
let n = self.s.nodes;
if n & 255 == 0 && self.must_stop(n) {
self.s.stopped = true;
}
}
/// Whether the search must stop, n nodes in: the main thread's once the page has given it up, or past its node
/// limit or its time, a heartbeat given first; a helper's once the main thread has finished, or the page has given the
/// search up, or the main thread has stopped beating (its worker ended, every 16,384 nodes a look), its count left
/// for the main thread's reports first.
fn must_stop(&mut self, n: u64) -> bool {
if self.thread == 0 {
threads::beat();
threads::abandoned() || n as f64 >= self.s.max_nodes || (self.clock)() > self.s.hard
} else {
threads::counted(self.thread, n);
threads::stopping() || (n & 16383 == 0 && !threads::beating(&mut self.pulse, (self.clock)()))
}
}
/// A draw, as the side to move at ply sees it: the side to move at the root values it at -contempt, so that it
/// plays on in level positions.
fn draw_score(&self, ply: i32) -> i32 {
if ply & 1 == 0 {
-self.s.contempt
} else {
self.s.contempt
}
}
// Move ordering
/// Where a quiet move's history is kept: its side, its square and the diagonal it steps along.
#[inline(always)]
fn history_index(us: i32, m: i32) -> usize {
((us * 128 + move_from(m) * 4 + first_diagonal_of(m)) & 255) as usize
}
/// How promising m looks, for ordering: the table's move first, then jumps, the more pieces they take the better,
/// and a jump that crowns first among equals; then a man's step to be crowned, then killer moves, then quiet moves by
/// their history.
fn move_score(&self, m: i32, tt_move: i32, k1: i32, k2: i32, us: i32) -> i32 {
if m == tt_move {
30000000
} else if is_jump(m) {
20000000 + 1000 * jumps(m) + if self.b.crowns(m) { 500 } else { 0 }
} else if self.b.crowns(m) {
19000000
} else if m == k1 {
15000000
} else if m == k2 {
14000000
} else {
self.s.history[Engine::history_index(us, m)]
}
}
fn score_moves(&mut self, base: usize, end: usize, tt_move: i32, ply: i32) {
let us = self.b.side;
let k1 = self.s.killers[(ply * 2) as usize];
let k2 = self.s.killers[(ply * 2 + 1) as usize];
for i in base..end {
let m = self.s.moves[i];
self.s.scores[i] = self.move_score(m, tt_move, k1, k2, us);
}
}
/// The best-scored move from place i to end, swapped into place i.
#[inline(always)]
fn pick(&mut self, i: usize, end: usize) -> i32 {
let scores = &mut self.s.scores;
let mut best = i;
for j in i + 1..end {
if scores[j] > scores[best] {
best = j;
}
}
scores.swap(best, i);
self.s.moves.swap(best, i);
self.s.moves[i]
}
/// A quiet move m caused a cutoff at ply: make it a killer, raise its history and lower that of the quiet moves
/// tried before it. The history saturates at +-16,384.
fn reward(&mut self, m: i32, ply: i32, depth: i32, n_quiets: i32) {
let us = self.b.side;
let bonus = 1600.min(16 * depth * depth);
let s = &mut self.s;
let k = (ply * 2) as usize;
if m != s.killers[k] {
s.killers[k + 1] = s.killers[k];
s.killers[k] = m;
}
let i = Engine::history_index(us, m);
let h = s.history[i];
s.history[i] = h + (bonus - h * bonus / 16384);
for j in 0..n_quiets {
let q = s.quiets[(ply * 64 + j) as usize];
if q != m {
let i = Engine::history_index(us, q);
let h = s.history[i];
s.history[i] = h - bonus - h * bonus / 16384;
}
}
}
/// m is the best move at ply so far: the variation from ply is m, then the child's.
fn new_pv(&mut self, m: i32, ply: i32) {
let s = &mut self.s;
let row = (ply * MAX_PLY) as usize;
let child = ((ply + 1) * MAX_PLY) as usize;
let end = s.pv_length[(ply + 1) as usize];
s.pv[row + ply as usize] = m;
for i in (ply + 1)..end {
s.pv[row + i as usize] = s.pv[child + i as usize];
}
s.pv_length[ply as usize] = end.max(ply + 1);
}
// The quiescence search
/// The score of the position once the jumps are played out. A side that can jump must, so it cannot stand on its
/// evaluation while it has a jump: the jumps are searched until a side has none, and there the evaluation is the
/// score, unless that side cannot even step, and has lost.
fn quiesce(&mut self, alpha: i32, beta: i32, ply: i32) -> i32 {
self.s.pv_length[ply as usize] = ply;
self.count_node();
if ply > self.s.seldepth {
self.s.seldepth = ply;
}
if ply >= self.s.ply_limit {
return evaluate(&self.b);
}
let base = (ply * MAX_MOVES) as usize;
let end = self.b.generate(&mut self.s.moves, base, true);
if end == base {
return if self.b.can_step() {
evaluate(&self.b)
} else {
-MATE + ply
};
}
self.score_moves(base, end, 0, ply);
let mut alpha = alpha;
let mut best = -INFINITY;
for i in base..end {
let m = self.pick(i, end);
self.b.make(m);
let score = -self.quiesce(-beta, -alpha, ply + 1);
self.b.unmake();
if self.s.stopped {
return 0;
}
if score >= beta {
return score;
}
if score > best {
if score > alpha {
self.new_pv(m, ply);
}
alpha = alpha.max(score);
best = score;
}
}
best
}
// The main search
/// Search m's reply, m made: the first move with the full window; later ones with a null window, reduced when late
/// and quiet, and searched again at full depth and then with the full window only if they beat alpha (principal
/// variation search). A forced move, the side's only one, is searched a ply deeper.
#[allow(clippy::too_many_arguments)]
fn child(
&mut self,
depth: i32,
alpha: i32,
beta: i32,
ply: i32,
pv: bool,
legal: i32,
quiet: bool,
forced: bool,
killer: bool,
h: i32,
) -> i32 {
let new_depth = if forced { depth } else { depth - 1 };
if legal == 1 {
return -self.search(new_depth, -beta, -alpha, ply + 1, pv);
}
let r = if quiet && depth >= 3 {
let mut r = self.s.lmr[(depth.min(63) * 64 + legal.min(63)) as usize];
if pv {
r -= 1;
}
if killer {
r -= 1;
}
r -= h / 5000;
0.max(r.min(depth - 2))
} else {
0
};
let mut score = -self.search(new_depth - r, -(alpha + 1), -alpha, ply + 1, false);
if score > alpha && r > 0 {
score = -self.search(new_depth, -(alpha + 1), -alpha, ply + 1, false);
}
if pv && score > alpha && score < beta {
-self.search(new_depth, -beta, -alpha, ply + 1, true)
} else {
score
}
}
/// At the root, remember the best move so far and its score: a search stopped part way through an iteration may
/// play it.
fn root_move(&mut self, ply: i32, m: i32, score: i32) {
if ply == 0 {
self.s.root_move = m;
self.s.root_score = score;
}
}
/// Try the moves in order and return the best score, storing the result in the table. A side with no move has lost.
fn moves_loop(&mut self, depth: i32, alpha: i32, beta: i32, ply: i32, pv: bool, tt_move: i32) -> i32 {
let base = (ply * MAX_MOVES) as usize;
let end = self.b.generate(&mut self.s.moves, base, false);
let us = self.b.side;
let k1 = self.s.killers[(ply * 2) as usize];
let k2 = self.s.killers[(ply * 2 + 1) as usize];
let forced = end - base == 1;
let original_alpha = alpha;
if end == base {
return -MATE + ply; // no move: lost
}
self.score_moves(base, end, tt_move, ply);
let mut alpha = alpha;
let mut best = -INFINITY;
let mut best_move = 0;
let mut legal = 0;
let mut n_tried = 0; // quiet moves searched, which the history's malus may lower
for i in base..end {
let m = self.pick(i, end);
let quiet = !is_jump(m);
legal += 1;
let h = if quiet {
self.s.history[Engine::history_index(us, m)]
} else {
0
};
self.b.make(m);
let score = self.child(depth, alpha, beta, ply, pv, legal, quiet, forced, m == k1 || m == k2, h);
self.b.unmake();
if quiet && n_tried < 64 {
self.s.quiets[(ply * 64 + n_tried) as usize] = m;
}
if self.s.stopped {
return 0;
}
if score >= beta {
if quiet {
self.reward(m, ply, depth, 64.min(n_tried + 1));
}
self.store(depth, LOWER, score, m, ply);
self.root_move(ply, m, score);
return score;
}
if score > alpha {
self.new_pv(m, ply);
self.root_move(ply, m, score);
alpha = score;
best = score;
best_move = m;
} else {
best = best.max(score);
}
if quiet {
n_tried += 1;
}
}
self.store(
depth,
if alpha > original_alpha { EXACT } else { UPPER },
best,
best_move,
ply,
);
best
}
/// The score of the position on the board for the side to move, searched depth plies deep (plus extensions, less
/// reductions), within the window alpha to beta, at ply plies from the root. pv is true on the principal variation,
/// which the table never cuts short.
fn search(&mut self, depth: i32, alpha: i32, beta: i32, ply: i32, pv: bool) -> i32 {
self.s.pv_length[ply as usize] = ply;
if self.s.stopped {
return 0; // the caller discards it
}
if ply > 0 && self.b.repetition() {
return self.draw_score(ply);
}
// forty moves each without a jump or a man moved, unless the side to move has no move: then it has lost
if ply > 0 && self.b.halfmove >= QUIET_LIMIT {
return if self.b.has_move() {
self.draw_score(ply)
} else {
-MATE + ply
};
}
if ply >= self.s.ply_limit {
return evaluate(&self.b); // as deep as a line may go
}
// nothing here beats winning now
let alpha = if ply > 0 { alpha.max(-MATE + ply) } else { alpha };
let beta = if ply > 0 { beta.min(MATE - ply - 1) } else { beta };
if alpha >= beta {
return alpha;
}
if depth <= 0 {
return self.quiesce(alpha, beta, ply);
}
self.count_node();
let e = 4 * (self.b.hash_lo & self.s.mask) as usize;
let (key, entry_move, packed, info) = self.s.tt.entry(e);
let hit = key == self.b.hash_hi && info != 0;
let tt_score = from_table((packed << 16) >> 16, ply);
let tt_bound = (info >> 8) & 3;
if hit
&& !pv
&& (info & 255) - 1 >= depth
&& (tt_bound == EXACT
|| (tt_bound == LOWER && tt_score >= beta)
|| (tt_bound == UPPER && tt_score <= alpha))
{
return tt_score; // the table knows
}
let tt_move = if hit { entry_move } else { 0 };
// internal iterative reduction: with no move from the table, search less deep
let depth = if depth >= 4 && tt_move == 0 { depth - 1 } else { depth };
self.moves_loop(depth, alpha, beta, ply, pv, tt_move)
}
// Iterative deepening
/// One iteration, depth plies deep, from the root: within an aspiration window around the last iteration's score,
/// prev, from depth 5, widened each time the score falls outside it. Returns the score, or 0 when stopped.
fn aspire(&mut self, depth: i32, prev: i32) -> i32 {
self.s.seldepth = 0;
self.s.root_move = 0;
let mut delta = 25;
let mut alpha = if depth >= 5 {
(-INFINITY).max(prev - delta)
} else {
-INFINITY
};
let mut beta = if depth >= 5 {
INFINITY.min(prev + delta)
} else {
INFINITY
};
loop {
let s = self.search(depth, alpha, beta, 0, true);
if self.s.stopped {
return s;
} else if s <= alpha {
let lower = (-INFINITY).max(s - 2 * delta);
beta = (alpha + beta) / 2;
alpha = lower;
delta *= 2;
} else if s >= beta {
beta = INFINITY.min(s + 2 * delta);
delta *= 2;
} else {
return s;
}
}
}
/// What the helper threads need of this search to join it, the deepest iteration depth: its table and settings.
pub fn settings(&self, depth: i32) -> Settings {
let s = &self.s;
Settings {
tt: s.tt.clone(),
mask: s.mask,
generation: s.generation,
contempt: s.contempt,
ply_limit: s.ply_limit,
depth,
}
}
/// A helper thread's part in a search (threads.rs): board's position, searched as the main thread searches it, with
/// its settings and into its table, iteration after iteration from depth 1, each within its aspiration window, less
/// the iterations this thread skips (skips), until the main thread has finished. It reports nothing: what it finds
/// reaches the main thread through the table. It keeps its own history and killers, as the main thread does.
#[cfg_attr(not(feature = "threads"), allow(dead_code))] // only the threaded build has helpers
pub fn help(&mut self, board: &Board, settings: &Settings) {
self.b.copy_from(board);
let s = &mut self.s;
s.tt = settings.tt.clone();
s.mask = settings.mask;
s.generation = settings.generation;
s.contempt = settings.contempt;
s.ply_limit = settings.ply_limit;
s.nodes = 0;
s.max_nodes = f64::INFINITY;
s.hard = f64::INFINITY;
s.stopped = false;
s.killers.fill(0);
for h in s.history.iter_mut() {
*h /= 2;
}
self.pulse = (-1, (self.clock)()); // the main thread beats from now
let mut prev = 0;
for d in 1..=settings.depth {
if skips(self.thread, d) {
continue;
}
let score = self.aspire(d, prev);
if self.s.stopped || threads::stopping() {
break;
}
prev = score;
}
threads::counted(self.thread, self.s.nodes);
}
/// The computer's move for the position on the board, which is unchanged afterwards, as checkers.search/think finds
/// it. on_iteration is called with each completed iteration's report. It stops after the iteration at its depth, or
/// when the side to move has one move, or once it has found a win or a loss and looked twice as far again as it is
/// away; and on the clock, when the next iteration would take longer than it has left: once past 30% of its time
/// when the move has held for four iterations, 70% when it has just changed, and 50% otherwise. Returns the report of
/// the last completed iteration, or of the iteration under way if it had already found a better move: the move as
/// players write it, the score in hundredths of a man for the side to move, the moves to a win, negative to a loss,
/// the depth, the deepest ply reached, the line, the nodes, the time and the speed. With no move, the move is None,
/// and the side to move has lost.
pub fn think(&mut self, o: &Options, on_iteration: &mut dyn FnMut(&Report)) -> Report {
let limit = match o.ply_limit {
Some(p) => 1.max(p.min(MAX_PLY - 1)),
None => MAX_PLY - 1,
};
let depth = o.depth.min(limit);
let start = (self.clock)();
let hard = start + o.max_ms.unwrap_or(o.ms);
let legal = self.b.legal_moves();
if legal.is_empty() {
return Report {
mv: None,
score: -MATE,
mate: Some(0),
depth: 0,
seldepth: 0,
pv: Vec::new(),
nodes: 0,
ms: 0.0,
nps: 0.0,
};
}
if self.s.tt.words.is_empty() {
self.s.resize(20);
}
self.s.nodes = 0;
self.s.hard = hard;
self.s.max_nodes = o.nodes.unwrap_or(f64::INFINITY);
self.s.stopped = false;
self.s.contempt = o.contempt;
self.s.ply_limit = limit;
self.s.generation = (self.s.generation + 1) & 1023;
self.s.killers.fill(0);
for h in self.s.history.iter_mut() {
*h /= 2;
}
threads::start(self, depth); // any helper threads join, until the search returns
let mut d = 1;
let mut done: Option<Report> = None;
let mut stable = 0; // how many iterations the move has held for
loop {
let prev = done.as_ref().map_or(0, |r| r.score);
let score = self.aspire(d, prev);
let elapsed = (self.clock)() - start;
let n = self.s.nodes + threads::helper_nodes(); // every thread's, as the reports give them
let partial = self.s.stopped;
let report = |this: &Engine, m: i32, score: i32| {
let length = this.s.pv_length[0];
Report {
mv: Some(m),
score,
mate: mate_in(score),
depth: if partial { d - 1 } else { d },
seldepth: this.s.seldepth,
// the root's variation, when it is m's; a stopped iteration may have found m without writing its line
pv: if length > 0 && this.s.pv[0] == m {
this.s.pv[..length as usize].iter().map(|&m| notation(m)).collect()
} else {
vec![notation(m)]
},
nodes: n,
ms: js_round(elapsed),
nps: if elapsed > 0.0 {
js_round(1000.0 * n as f64 / elapsed)
} else {
0.0
},
}
};
if partial {
// stopped: the iteration under way counts only if it found a new best move
let m = self.s.root_move;
let r = match done {
None if m == 0 => report(self, legal[0], 0),
Some(ref r) if m == 0 || r.mv.map(notation) == Some(notation(m)) => {
let mut r = r.clone();
r.nodes = n;
r.ms = js_round(elapsed);
r
}
_ => report(self, m, self.s.root_score),
};
threads::stop();
return r;
}
let r = report(self, self.s.pv[0], score);
stable = match done {
Some(ref last) if last.mv.map(notation) == r.mv.map(notation) => stable + 1,
_ => 0,
};
on_iteration(&r);
let settled = match stable {
s if s >= 4 => 0.3,
0 => 0.7,
_ => 0.5,
};
if legal.len() == 1
|| d >= depth
|| mate_in(score).is_some_and(|mate| d >= 2 + 2 * mate.abs())
|| elapsed > o.ms * settled
{
threads::stop();
return r;
}
d += 1;
done = Some(r);
}
}
}src/threads.rs · 213 lines
//! Checkers' search on every core at once, where the page may share memory between workers (worker.js), as Chessmate's
//! is (src/wasm/chessmate/src/threads.rs, whose protocol, words and worker this is): Lazy SMP, as Stockfish and most
//! engines since search on many threads. The worker's own thread is the main thread, which searches, keeps the time and
//! reports, as it does alone. Each other thread is a helper, a worker of its own running this same module on the same
//! memory, which searches the same position with its own board and history, into the main thread's transposition
//! table. They share nothing else. The helpers' iterations run ahead of the main thread's and beside it (search.rs,
//! skips), so that the main thread finds positions in the table that a helper has searched already, often deeper than
//! it has itself, and gets deeper sooner. The move is the main thread's.
//!
//! The threads meet through a few words of memory, each read and written whole (atomics). Four of them, CONTROL, the
//! workers and the page reach too, at the address `control` gives:
//!
//! SEQ bumped as each search starts: an idle helper waits in worker.js for it to change, then joins
//! PULSE the main thread's heartbeat: one more every 256 nodes it searches, and from its worker every 250 ms
//! while it waits for the page
//! SEARCH the number of the page's search under way, which worker.js writes before it starts it; 0 for none
//! ABANDONED the number of the last search the page has given up (chess-engine.ts): a search stops once its number
//! is no more than that
//!
//! and the others only the threads:
//!
//! STOP 1 while no search is under way or the one under way is ending, and helpers stop when they see it
//! ACTIVE how many helpers are inside a search
//! NODES each helper's nodes in the search under way, which the main thread's reports add to its own
//!
//! The main thread writes the root, its position and settings, only while STOP is 1 and no helper is ACTIVE; a helper
//! counts itself ACTIVE before it looks at STOP, and reads the root only when STOP is 0. So no helper reads a root
//! half written, and a helper that wakes late, after its search has ended, finds STOP 1 and waits again. As a search
//! ends, the main thread sets STOP and waits for every helper to leave before it returns its move.
//!
//! The page gives a search up through ABANDONED, when Chessmate is to think again or not at all: every thread sees it
//! within 256 nodes, and the worker, its table and its helpers are ready for the next search at once. Ending the worker
//! would not stop the search: WebKit ran on a worker it had ended to the end of its search, on every thread, and
//! Chromium ended its busy helpers only after about ten seconds. So a helper also stops once the main thread's heartbeat
//! has been silent for 250 ms, as when its worker has ended in a search, and its own worker, finding it silent for good,
//! ends itself.
//!
//! Without atomics, where the module is built for one thread (checkers.wasm), no helper ever starts, and start and
//! stop do nothing: the search is the ClojureScript's, node for node.
#![cfg_attr(not(feature = "threads"), allow(dead_code))] // built for one thread, no helper starts
use std::cell::UnsafeCell;
use std::hint::spin_loop;
use std::sync::atomic::{
AtomicI32, AtomicU64,
Ordering::{Relaxed, SeqCst},
};
use crate::board::Board;
use crate::search::{Engine, Settings};
/// The most threads a search runs on, the main thread among them.
pub const MAX_THREADS: usize = 32;
/// SEQ, PULSE, SEARCH and ABANDONED, in that order: see above.
static CONTROL: [AtomicI32; 4] = [const { AtomicI32::new(0) }; 4];
const SEQ: usize = 0;
const PULSE: usize = 1;
const SEARCH: usize = 2;
const ABANDONED: usize = 3;
static STOP: AtomicI32 = AtomicI32::new(1);
static ACTIVE: AtomicI32 = AtomicI32::new(0);
/// How many helpers the worker has started.
static HELPERS: AtomicI32 = AtomicI32::new(0);
static NODES: [AtomicU64; MAX_THREADS] = [const { AtomicU64::new(0) }; MAX_THREADS];
/// How long a helper waits for its main thread's next heartbeat before it stops, in ms.
const SILENCE_MS: f64 = 250.0;
/// Memory every thread can reach, whose threads take turns by the protocol above rather than by a lock.
struct Shared<T>(UnsafeCell<T>);
// Safety: see the protocol above; each helper's engine is only ever touched by its own thread, and by the main thread
// between searches (clear)
unsafe impl<T> Sync for Shared<T> {}
/// The search's root, as the main thread leaves it for the helpers: the position, with the moves that led to it, and
/// the settings.
struct Root {
board: Board,
settings: Settings,
}
// Boxed, so that the statics are null pointers until used, not an engine's worth of bytes each in the module
static ROOT: Shared<Option<Box<Root>>> = Shared(UnsafeCell::new(None));
/// Each helper's engine, by its thread, made at its first search.
static ENGINES: [Shared<Option<Box<Engine>>>; MAX_THREADS] = [const { Shared(UnsafeCell::new(None)) }; MAX_THREADS];
#[cfg(feature = "threads")]
extern "C" {
/// Wake the helpers waiting for SEQ, at at, to change: worker.js's Atomics.notify.
fn wake(at: *const i32);
}
/// Built for one thread, nothing waits.
#[cfg(not(feature = "threads"))]
unsafe fn wake(_: *const i32) {}
/// The worker has started n helpers, threads 1 to n.
pub fn set_helpers(n: i32) {
HELPERS.store(n.clamp(0, MAX_THREADS as i32 - 1), SeqCst);
}
/// Where CONTROL is.
pub fn control() -> *const AtomicI32 {
CONTROL.as_ptr()
}
/// The main thread's heartbeat, every 256 nodes it searches.
#[inline]
pub fn beat() {
CONTROL[PULSE].fetch_add(1, Relaxed);
}
/// Whether a helper's main thread still beats, at now: seen is the beat the helper saw last and when it saw it change.
pub fn beating(seen: &mut (i32, f64), now: f64) -> bool {
let p = CONTROL[PULSE].load(Relaxed);
if p != seen.0 {
*seen = (p, now);
}
now - seen.1 < SILENCE_MS
}
/// Whether the page has given up the search under way: never where it cannot share memory with the worker, whose
/// searches are then never numbered.
#[inline]
pub fn abandoned() -> bool {
let s = CONTROL[SEARCH].load(Relaxed);
s > 0 && s <= CONTROL[ABANDONED].load(Relaxed)
}
/// As main's search starts, before its first iteration: leave the root and the settings for the helpers, and wake them.
/// Nothing without helpers.
pub fn start(main: &Engine, depth: i32) {
if HELPERS.load(SeqCst) == 0 {
return;
}
while ACTIVE.load(SeqCst) != 0 {
spin_loop(); // a helper that woke late is leaving
}
// Safety: STOP is 1 and no helper is ACTIVE, so none reads the root
let root = unsafe { &mut *ROOT.0.get() };
let settings = main.settings(depth);
match root {
Some(r) => {
r.board.copy_from(&main.b);
r.settings = settings;
}
None => {
let mut board = Board::new();
board.copy_from(&main.b);
*root = Some(Box::new(Root { board, settings }));
}
}
for n in NODES.iter() {
n.store(0, SeqCst);
}
STOP.store(0, SeqCst);
CONTROL[SEQ].fetch_add(1, SeqCst);
// Safety: the host's function only notifies the address's waiters
unsafe { wake(CONTROL[SEQ].as_ptr()) }
}
/// As main's search ends: stop the helpers, and wait until every one has left the search.
pub fn stop() {
if HELPERS.load(SeqCst) == 0 {
return;
}
STOP.store(1, SeqCst);
while ACTIVE.load(SeqCst) != 0 {
spin_loop(); // each looks at STOP every 256 nodes
}
}
/// Whether the search under way is ending, for a helper: the main thread has finished, or the page has given it up.
#[inline]
pub fn stopping() -> bool {
STOP.load(Relaxed) != 0 || abandoned()
}
/// Helper thread t has searched n nodes in the search under way.
pub fn counted(t: usize, n: u64) {
NODES[t % MAX_THREADS].store(n, Relaxed);
}
/// The nodes every helper has searched in the search under way, as each last counted them: 0 without helpers.
pub fn helper_nodes() -> u64 {
NODES.iter().map(|n| n.load(Relaxed)).sum()
}
/// Helper thread t's part in the search under way, on its own thread, clock its clock: see the protocol above. Returns
/// once the main thread has finished its search, or at once when none is under way.
pub fn help(t: usize, clock: fn() -> f64) {
ACTIVE.fetch_add(1, SeqCst);
if STOP.load(SeqCst) == 0 && (1..MAX_THREADS).contains(&t) {
// Safety: while STOP is 0 the main thread leaves the root alone, and only this thread touches its engine
if let Some(root) = unsafe { (*ROOT.0.get()).as_ref() } {
let engine = unsafe { (*ENGINES[t].0.get()).get_or_insert_with(|| Box::new(Engine::helper(clock, t))) };
engine.help(&root.board, &root.settings);
}
}
ACTIVE.fetch_sub(1, SeqCst);
}
/// Forget what the helpers have learnt, as the main thread forgets its own: their histories and killers. Their engines
/// are made afresh at their next search. Only between searches.
pub fn clear() {
for e in ENGINES.iter() {
// Safety: between searches STOP is 1, so no helper touches its engine
unsafe { *e.0.get() = None }
}
}src/eval.rs · 148 lines
//! What a Checkers position is worth to the side to move, in hundredths of a man, ported from checkers.eval: a man is
//! 100. Material first, a king worth more than a man, and more still as the board empties. Then what the pieces'
//! squares say:
//!
//! advancement a man is worth more the nearer it is to being crowned: a little in the middlegame, much more in the
//! endgame
//! the centre men on the four squares in the middle of the board, 14, 15, 18 and 19, and kings the further they
//! are from the edges, where they reach most
//! the back rank men left on their own back rank guard it against the other side's crowning, the two that players
//! call the bridge most of all, while the other side has men to crown
//! the endgame the side a man or more ahead is drawn to trade pieces and to bring its kings at the other side's
//! pieces; the side behind to shelter its kings in the double corners
//!
//! Every term but the endgame's is a middlegame and an endgame value, blended by how many pieces are left: 24 pieces is
//! all middlegame, and none all endgame. Every score is the ClojureScript's.
use crate::board::{file_of, kind, row_of, side_of, Board, BLACK, KING, WHITE};
const MAN_VALUE: i32 = 100;
/// A king in the middlegame, and in the endgame.
const KING_MG: i32 = 125;
const KING_EG: i32 = 150;
/// A man's worth by the rows it has advanced, 0 to 6, in the middlegame and in the endgame.
const ADVANCE_MG: [i32; 7] = [0, 1, 2, 3, 5, 7, 9];
const ADVANCE_EG: [i32; 7] = [0, 4, 8, 13, 19, 26, 34];
/// A man's worth for its square, in the middlegame: 14, 15, 18 and 19.
const CENTRE_MAN: [i32; 32] = {
let mut t = [0; 32];
t[13] = 5;
t[14] = 5;
t[17] = 5;
t[18] = 5;
t
};
/// A king's, by how far its square is from the edges.
const CENTRE_KING: [i32; 32] = {
let mut t = [0; 32];
let mut sq = 0;
while sq < 32 {
let (f, r) = (file_of(sq), row_of(sq));
let from_file = if f < 7 - f { f } else { 7 - f };
let from_row = if r < 7 - r { r } else { 7 - r };
t[sq as usize] = 2 * (from_file + from_row);
sq += 1;
}
t
};
/// The bridge, by side: Black's 1 and 3, and White's 30 and 32.
const BRIDGE: [[i32; 2]; 2] = [[0, 2], [29, 31]];
/// Is sq in a double corner, on 1 or 5, or on 28 or 32?
fn double_corner(sq: i32) -> bool {
sq == 0 || sq == 4 || sq == 27 || sq == 31
}
/// A middlegame and an endgame value, weighed by how many pieces are left.
fn blend(mg: i32, eg: i32, pieces: i32) -> i32 {
(mg * pieces + eg * (24 - pieces)) / 24
}
/// How many king's steps apart two squares are on an empty board: each diagonal step changes the file and the row by
/// one, so the larger difference.
fn steps_apart(a: i32, b: i32) -> i32 {
(file_of(a) - file_of(b)).abs().max((row_of(a) - row_of(b)).abs())
}
/// How many steps from sq the nearest of side's pieces is, on an empty board: 8 when it has none.
fn nearest(b: &Board, sq: i32, side: i32) -> i32 {
let mut best = 8;
for i in 0..32 {
let p = b.squares[i as usize];
if p != 0 && side_of(p) == side {
best = best.min(steps_apart(sq, i));
}
}
best
}
/// The endgame's terms, White's less Black's, with ten pieces or fewer, when a side is a man or more ahead by material,
/// lead: trading, the leader's kings drawn towards the other side's pieces, and the other side's kings to the double
/// corners.
fn endgame(b: &Board, lead: i32, pieces: i32) -> i32 {
if pieces > 10 || lead.abs() < MAN_VALUE {
return 0;
}
let ahead = if lead > 0 { WHITE } else { BLACK };
let sign = if lead > 0 { 1 } else { -1 };
let mut score = lead * (24 - pieces) / 48;
for sq in 0..32 {
let p = b.squares[sq as usize];
if p == 0 || kind(p) != KING {
continue;
}
if side_of(p) == ahead {
score -= sign * 3 * nearest(b, sq, ahead ^ 1);
} else if double_corner(sq) {
score -= sign * 8;
}
}
score
}
/// The position's worth to the side to move, in hundredths of a man.
pub fn evaluate(b: &Board) -> i32 {
let [bm, bk, wm, wk] = b.counts;
let pieces = bm + bk + wm + wk;
let king_value = blend(KING_MG, KING_EG, pieces);
let material = (wm * MAN_VALUE + wk * king_value) - (bm * MAN_VALUE + bk * king_value);
// the positional terms: middlegame and endgame, White's less Black's
let (mut mg, mut eg) = (0, 0);
for sq in 0..32 {
let p = b.squares[sq as usize];
if p == 0 {
continue;
}
let white = side_of(p) == WHITE;
let sign = if white { 1 } else { -1 };
if kind(p) == KING {
mg += sign * CENTRE_KING[sq as usize];
eg += sign * CENTRE_KING[sq as usize];
} else {
let advanced = if white { 7 - row_of(sq) } else { row_of(sq) };
// the back rank guards against the other side's men only: its kings are crowned already
let guard = if advanced > 0 || (if white { bm } else { wm }) == 0 {
0
} else {
let bridge = BRIDGE[side_of(p) as usize];
if sq == bridge[0] || sq == bridge[1] {
9
} else {
3
}
};
mg += sign * (ADVANCE_MG[advanced as usize] + CENTRE_MAN[sq as usize] + guard);
eg += sign * ADVANCE_EG[advanced as usize];
}
}
let score = material + blend(mg, eg, pieces) + endgame(b, material, pieces);
if b.side == 0 {
-score
} else {
score
}
}src/board.rs · 830 lines
//! The Checkers board, ported from checkers.board: one position, changed in place by make and taken back by unmake, with
//! the rules of English draughts, which America calls checkers, as the page plays them:
//!
//! the board 8 × 8, played on its 32 dark squares, with a dark square in each player's left-hand corner
//! the men 12 a side, Black's on squares 1 to 12 and White's on 21 to 32; White moves first here, as in chess
//! moving a man steps one square diagonally forward, onto an empty square; a king one square either way
//! jumping a piece takes an enemy piece beside it by jumping over it to the empty square beyond, and goes on
//! jumping with the same piece while it can, all in one move; a man jumps forward only
//! forced jumps whoever can jump must, choosing among the jumps as they like, and must jump as far as the jump they
//! choose goes
//! crowning a man that reaches the far row is crowned a king, and its move ends there
//! the end a side with no move loses; the game is drawn when a position occurs for the third time, or after
//! forty moves each without a jump or a man moved
//!
//! Squares are numbered 1 to 32, as players number them: 1 to 4 on Black's back rank, from White's left, and so on to
//! 29 to 32 on White's. Inside, a square is its number less one, 0 to 31, on a row from 0, Black's back rank, to 7.
//! Pieces are a type, 1 for a man and 2 for a king, plus 8 for White's. Sides are 0 for Black and 1 for White.
//!
//! Every step is the ClojureScript's, in its order: the same moves in the same order, the same hash, the same history.
// Pieces and sides
pub const MAN: i32 = 1;
pub const KING: i32 = 2;
/// Added to a type for White's piece.
pub const WHITE_PIECE: i32 = 8;
pub const BLACK: i32 = 0;
pub const WHITE: i32 = 1;
/// A piece's type: 1 for a man, 2 for a king.
#[inline(always)]
pub fn kind(piece: i32) -> i32 {
piece & 7
}
/// A piece's side: 0 for Black, 1 for White.
#[inline(always)]
pub fn side_of(piece: i32) -> i32 {
piece >> 3
}
// Squares, and the diagonals between them
/// A square's row: 0 on Black's back rank, 7 on White's.
#[inline(always)]
pub const fn row_of(sq: i32) -> i32 {
sq >> 2
}
/// A square's file, 0 to 7 from White's left: the dark squares are files 1, 3, 5 and 7 on Black's back rank and every
/// second row from it, and 0, 2, 4 and 6 on the others.
#[inline(always)]
pub const fn file_of(sq: i32) -> i32 {
2 * (sq & 3) + if row_of(sq) & 1 == 0 { 1 } else { 0 }
}
/// The dark square on file and row, or -1 off the board.
const fn square_at(file: i32, row: i32) -> i32 {
if 0 <= file && file <= 7 && 0 <= row && row <= 7 {
row * 4 + (file >> 1)
} else {
-1
}
}
/// The row where side's men are crowned: the far one.
#[inline(always)]
pub fn crown_row(side: i32) -> i32 {
if side == 0 {
7
} else {
0
}
}
// The four diagonals: 0 and 1 go towards Black's back rank, left and right as White sees them, the way White's men go;
// 2 and 3 towards White's, the way Black's go. A king takes all four.
const DX: [i32; 4] = [-1, 1, -1, 1];
const DY: [i32; 4] = [-1, -1, 1, 1];
/// The square one step along each diagonal from each square, by square * 4 + diagonal, or -1.
pub static STEP: [i32; 128] = hops(1);
/// The square two steps along, where a jump over the step's square lands, or -1.
pub static LEAP: [i32; 128] = hops(2);
const fn hops(k: i32) -> [i32; 128] {
let mut out = [0; 128];
let mut sq = 0;
while sq < 32 {
let mut d = 0;
while d < 4 {
out[(sq * 4 + d) as usize] = square_at(file_of(sq) + k * DX[d as usize], row_of(sq) + k * DY[d as usize]);
d += 1;
}
sq += 1;
}
out
}
/// The first diagonal a piece may take: a king's, all four; a man's, forward only.
#[inline(always)]
fn first_diagonal(piece: i32) -> i32 {
if kind(piece) == KING || side_of(piece) == WHITE {
0
} else {
2
}
}
/// After the last.
#[inline(always)]
fn end_diagonal(piece: i32) -> i32 {
if kind(piece) == KING || side_of(piece) == BLACK {
4
} else {
2
}
}
/// Plies without a jump or a man's move after which the game is drawn: forty moves each.
pub const QUIET_LIMIT: i32 = 80;
/// The history: what each move changed, for unmake and for the repetition test, ten numbers a move.
const UNDO_STRIDE: usize = 10;
pub const MAX_HISTORY: usize = 1024;
// Zobrist keys: pieces at piece * 32 + square, the side at 352, each a low and a high half. Drawn from the same fixed
// mulberry32 sequence as checkers.board's, so that both hash every position alike.
const KEYS: usize = 353;
const SIDE_KEY: usize = 352;
static ZOBRIST: [[i32; 2]; KEYS] = zobrist();
const fn zobrist() -> [[i32; 2]; KEYS] {
let mut keys = [[0; 2]; KEYS];
let mut x: u32 = 0x2545F491;
let mut i = 0;
while i < KEYS {
let mut half = 0;
while half < 2 {
// mulberry32, as ClojureScript computes it with Math.imul and >>>
x = x.wrapping_add(0x6D2B79F5);
let mut t = (x ^ (x >> 15)).wrapping_mul(x | 1);
t ^= t.wrapping_add((t ^ (t >> 7)).wrapping_mul(t | 61));
keys[i][half] = (t ^ (t >> 14)) as i32;
half += 1;
}
i += 1;
}
keys
}
// Moves:
// bits 0 to 4 the square the piece leaves
// bit 5 set for a jump
// bits 6 on the diagonals it takes, two bits each, the first lowest, below a 1 that marks where they end: a step
// takes one, a jump one for each piece it takes. Twelve jumps, all a side's pieces, fit in 31 bits.
pub const JUMP_FLAG: i32 = 32;
/// The move of a piece from the square from, stepping or jumping, along n diagonals, the first in the lowest two bits of
/// diagonals.
#[inline(always)]
pub fn make_move(from: i32, jump: bool, diagonals: i32, n: i32) -> i32 {
from | if jump { JUMP_FLAG } else { 0 } | ((diagonals | (1 << (2 * n))) << 6)
}
#[inline(always)]
pub fn move_from(m: i32) -> i32 {
m & 31
}
#[inline(always)]
pub fn is_jump(m: i32) -> bool {
m & JUMP_FLAG != 0
}
/// A move's diagonals, above their end marker.
#[inline(always)]
fn route(m: i32) -> i32 {
((m as u32) >> 6) as i32
}
/// How many pieces a move takes.
pub fn jumps(m: i32) -> i32 {
if is_jump(m) {
(31 - (route(m) as u32).leading_zeros() as i32) >> 1
} else {
0
}
}
/// The diagonal a move takes first.
#[inline(always)]
pub fn first_diagonal_of(m: i32) -> i32 {
route(m) & 3
}
/// Where a move's piece ends up.
pub fn move_to(m: i32) -> i32 {
let hops = if is_jump(m) { &LEAP } else { &STEP };
let mut sq = move_from(m);
let mut r = route(m);
while r != 1 {
sq = hops[((sq * 4 + (r & 3)) & 127) as usize];
r >>= 2;
}
sq
}
/// The squares a move's piece stands on: where it starts, then where each step or jump lands.
pub fn landings(m: i32) -> Vec<i32> {
let hops = if is_jump(m) { &LEAP } else { &STEP };
let mut sq = move_from(m);
let mut r = route(m);
let mut out = vec![sq];
while r != 1 {
sq = hops[((sq * 4 + (r & 3)) & 127) as usize];
r >>= 2;
out.push(sq);
}
out
}
/// The squares of the pieces a move takes, in the order it takes them.
pub fn taken(m: i32) -> Vec<i32> {
let mut out = Vec::new();
if is_jump(m) {
let mut sq = move_from(m);
let mut r = route(m);
while r != 1 {
let i = ((sq * 4 + (r & 3)) & 127) as usize;
out.push(STEP[i]);
sq = LEAP[i];
r >>= 2;
}
}
out
}
/// A move as players write it: a step as its two squares with a dash, 11-15; a jump as the squares it lands on, from
/// where it starts, with an x, 22x15, or 22x15x6 for two pieces taken.
pub fn notation(m: i32) -> String {
let squares: Vec<String> = landings(m).iter().map(|sq| (sq + 1).to_string()).collect();
squares.join(if is_jump(m) { "x" } else { "-" })
}
/// Clojure's pr-str of a string, for the reasons a FEN is refused: in quotes, with its escapes.
fn pr_str(s: &str) -> String {
let mut out = String::from("\"");
for c in s.chars() {
match c {
'"' => out.push_str("\\\""),
'\\' => out.push_str("\\\\"),
'\u{8}' => out.push_str("\\b"),
'\u{c}' => out.push_str("\\f"),
'\n' => out.push_str("\\n"),
'\r' => out.push_str("\\r"),
'\t' => out.push_str("\\t"),
c => out.push(c),
}
}
out.push('"');
out
}
/// clojure.string/split of s at each sep: JavaScript's split, less the empty strings at its end.
fn split_on(s: &str, sep: char) -> Vec<&str> {
let mut parts: Vec<&str> = s.split(sep).collect();
while parts.last() == Some(&"") {
parts.pop();
}
parts
}
/// JavaScript's whitespace, as \s and trim know it.
fn is_space(c: char) -> bool {
c.is_whitespace() || c == '\u{feff}'
}
/// A list's square or range: `\s*(K?)(\d{1,2})(?:-(\d{1,2}))?\s*`, the whole item: king?, first, last.
fn square_item(item: &str) -> Option<(bool, i32, i32)> {
let s = item.trim_matches(is_space);
let (king, s) = match s.strip_prefix('K') {
Some(rest) => (true, rest),
None => (false, s),
};
let digits = |t: &str| !t.is_empty() && t.len() <= 2 && t.bytes().all(|b| b.is_ascii_digit());
match s.split_once('-') {
Some((a, b)) if digits(a) && digits(b) => Some((king, a.parse().unwrap(), b.parse().unwrap())),
None if digits(s) => {
let a = s.parse().unwrap();
Some((king, a, a))
}
_ => None,
}
}
/// The position, and the state beside it.
pub struct Board {
/// The piece on each square, or 0.
pub squares: [i32; 32],
/// How many men and kings each side has: Black's men, Black's kings, White's men and White's kings.
pub counts: [i32; 4],
/// The side to move.
pub side: i32,
/// Plies since the last jump or man's move.
pub halfmove: i32,
/// Moves made since the position was set, which index the history.
pub ply: i32,
/// The Zobrist hash, low half.
pub hash_lo: i32,
/// And high half.
pub hash_hi: i32,
/// Per move made, by ply: the move, which of the pieces it took were kings, the piece that moved, the halfmove count,
/// the hash's halves and the four counts.
undo: Box<[i32; MAX_HISTORY * UNDO_STRIDE]>,
/// Moves for legal_moves and has_move.
scratch: Vec<i32>,
}
impl Board {
pub fn new() -> Board {
Board {
squares: [0; 32],
counts: [0; 4],
side: 0,
halfmove: 0,
ply: 0,
hash_lo: 0,
hash_hi: 0,
undo: vec![0; MAX_HISTORY * UNDO_STRIDE]
.into_boxed_slice()
.try_into()
.unwrap(),
scratch: vec![0; 256],
}
}
/// Make this board other's position, with the history that leads to it, for a helper thread's search: without
/// allocating, and naming every field, so that a new one cannot be left out.
pub fn copy_from(&mut self, other: &Board) {
let Board {
squares,
counts,
side,
halfmove,
ply,
hash_lo,
hash_hi,
undo,
scratch: _, // scratch
} = other;
self.squares = *squares;
self.counts = *counts;
self.side = *side;
self.halfmove = *halfmove;
self.ply = *ply;
self.hash_lo = *hash_lo;
self.hash_hi = *hash_hi;
let n = *ply as usize * UNDO_STRIDE;
self.undo[..n].copy_from_slice(&undo[..n]);
}
#[inline(always)]
fn toggle(&mut self, k: usize) {
self.hash_lo ^= ZOBRIST[k][0];
self.hash_hi ^= ZOBRIST[k][1];
}
// Putting pieces down and picking them up, keeping the hash and the counts
/// Where a piece is counted in counts.
#[inline(always)]
fn count_slot(piece: i32) -> usize {
(2 * side_of(piece) + kind(piece) - 1) as usize & 3
}
/// Place piece on the empty square sq.
fn put(&mut self, piece: i32, sq: i32) {
self.squares[(sq & 31) as usize] = piece;
self.toggle(((piece * 32 + sq) as usize).min(KEYS - 1));
self.counts[Board::count_slot(piece)] += 1;
}
/// Take the piece off sq, and return it.
fn lift(&mut self, sq: i32) -> i32 {
let piece = self.squares[(sq & 31) as usize];
self.squares[(sq & 31) as usize] = 0;
self.toggle(((piece * 32 + sq) as usize).min(KEYS - 1));
self.counts[Board::count_slot(piece)] -= 1;
piece
}
/// Does move m crown the man that makes it, in the position on the board?
pub fn crowns(&self, m: i32) -> bool {
let piece = self.squares[move_from(m) as usize];
kind(piece) == MAN && row_of(move_to(m)) == crown_row(side_of(piece))
}
// Generating moves
/// Write into out every jump that piece, lifted off the board, can make on from sq, where it stands after n jumps
/// along diagonals: each jump that cannot go on, or that crowns a man, is a move. The pieces it takes are lifted off
/// meanwhile, so that none is jumped twice. Returns whether it could jump at all.
#[allow(clippy::too_many_arguments)]
fn jump_on(
&mut self,
out: &mut [i32],
end: &mut usize,
from: i32,
piece: i32,
sq: i32,
diagonals: i32,
n: i32,
) -> bool {
let them = side_of(piece) ^ 1;
let last = end_diagonal(piece);
let crowning = if kind(piece) == MAN {
crown_row(side_of(piece))
} else {
-1
};
let mut jumped = false;
let mut d = first_diagonal(piece);
while d < last {
let i = ((sq * 4 + d) & 127) as usize;
let to = LEAP[i];
if to >= 0 && self.squares[to as usize] == 0 {
let over = STEP[i] as usize;
let victim = self.squares[over];
if victim != 0 && side_of(victim) == them {
let diagonals = diagonals | (d << (2 * n));
self.squares[over] = 0;
if row_of(to) == crowning || !self.jump_on(out, end, from, piece, to, diagonals, n + 1) {
out[*end] = make_move(from, true, diagonals, n + 1);
*end += 1;
}
self.squares[over] = victim;
jumped = true;
}
}
d += 1;
}
jumped
}
/// Write the side to move's moves into out from index start, and return the index after the last: its jumps, if it
/// has any, as it must jump, and else its steps. With jumps_only, only its jumps, and none when it has none.
pub fn generate(&mut self, out: &mut [i32], start: usize, jumps_only: bool) -> usize {
let us = self.side;
let mut end = start;
for sq in 0..32 {
let piece = self.squares[sq as usize];
if piece != 0 && side_of(piece) == us {
self.squares[sq as usize] = 0; // the jumping piece leaves its square, which a king may land on again
self.jump_on(out, &mut end, sq, piece, sq, 0, 0);
self.squares[sq as usize] = piece;
}
}
if end == start && !jumps_only {
for sq in 0..32 {
let piece = self.squares[sq as usize];
if piece != 0 && side_of(piece) == us {
for d in first_diagonal(piece)..end_diagonal(piece) {
let to = STEP[(sq * 4 + d) as usize];
if to >= 0 && self.squares[to as usize] == 0 {
out[end] = make_move(sq, false, d, 1);
end += 1;
}
}
}
}
}
end
}
/// Has the side to move a step, a move that jumps nothing? With no jump and no step, it has lost.
pub fn can_step(&self) -> bool {
let us = self.side;
(0..32).any(|sq| {
let piece = self.squares[sq as usize];
piece != 0
&& side_of(piece) == us
&& (first_diagonal(piece)..end_diagonal(piece)).any(|d| {
let to = STEP[(sq * 4 + d) as usize];
to >= 0 && self.squares[to as usize] == 0
})
})
}
// Making and unmaking moves
/// Play move m, which generate made for this position. The history keeps what unmake needs: the move, which of the
/// pieces it takes are kings, the piece that moves, the halfmove count, the hash and the counts of pieces.
pub fn make(&mut self, m: i32) {
let from = m & 31;
let jump = m & JUMP_FLAG != 0;
let u = self.ply as usize * UNDO_STRIDE;
let piece = self.squares[from as usize];
let us = side_of(piece);
self.undo[u] = m;
self.undo[u + 2] = piece;
self.undo[u + 3] = self.halfmove;
self.undo[u + 4] = self.hash_lo;
self.undo[u + 5] = self.hash_hi;
self.undo[u + 6..u + 10].copy_from_slice(&self.counts);
self.lift(from);
let mut sq = from;
let mut r = route(m);
let mut i = 0;
let mut kings = 0;
while r != 1 {
let k = ((sq * 4 + (r & 3)) & 127) as usize;
if jump {
let victim = self.lift(STEP[k]);
if kind(victim) == KING {
kings |= 1 << i;
}
sq = LEAP[k];
} else {
sq = STEP[k];
}
r >>= 2;
i += 1;
}
self.undo[u + 1] = kings;
let crowned = kind(piece) == MAN && row_of(sq) == crown_row(us);
self.put(if crowned { piece + 1 } else { piece }, sq);
self.halfmove = if jump || kind(piece) == MAN {
0
} else {
self.halfmove + 1
};
self.toggle(SIDE_KEY);
self.side = us ^ 1;
self.ply += 1;
}
/// Take back the last move make played: the pieces it took are put back along its path, and the hash, the counts and
/// the halfmove count restored from the history.
pub fn unmake(&mut self) {
let h = self.ply - 1;
let u = h as usize * UNDO_STRIDE;
let m = self.undo[u];
let kings = self.undo[u + 1];
let piece = self.undo[u + 2];
let from = m & 31;
let jump = m & JUMP_FLAG != 0;
let them = WHITE_PIECE * (side_of(piece) ^ 1);
let mut sq = from;
let mut r = route(m);
let mut i = 0;
while r != 1 {
let k = ((sq * 4 + (r & 3)) & 127) as usize;
if jump {
self.squares[STEP[k] as usize] = them + if kings & (1 << i) == 0 { MAN } else { KING };
sq = LEAP[k];
} else {
sq = STEP[k];
}
r >>= 2;
i += 1;
}
self.squares[sq as usize] = 0;
self.squares[from as usize] = piece;
self.side = side_of(piece);
self.ply = h;
self.halfmove = self.undo[u + 3];
self.hash_lo = self.undo[u + 4];
self.hash_hi = self.undo[u + 5];
self.counts.copy_from_slice(&self.undo[u + 6..u + 10]);
}
// Draws the search can see
/// Has the position occurred before, since the last jump or man's move? Only kings' moves can repeat a position.
/// Positions before the search's root count too: the game's history is played onto the board first.
pub fn repetition(&self) -> bool {
let h = self.ply;
let oldest = 0.max(h - self.halfmove);
let mut i = h - 2;
while i >= oldest {
let u = i as usize * UNDO_STRIDE;
if self.hash_lo == self.undo[u + 4] && self.hash_hi == self.undo[u + 5] {
return true;
}
i -= 2;
}
false
}
// Positions from and to FEN, as Portable Draughts Notation writes them
/// The position a FEN names, such as "W:W21,22,23,24,25,26,27,28,29,30,31,32:B1,2,3,4,5,6,7,8,9,10,11,12", as
/// checkers.board/read-fen reads it: the side to move, then each side's pieces by square, a king's with a K before
/// it, and ranges such as 1-12. Returns the side and the pieces by square, or the reason it names no position a game
/// can reach, in checkers.board's words.
pub fn read_fen(fen: &str) -> Result<(i32, Vec<(i32, i32)>), String> {
let error = |why: String| format!("Not a position: {} ({})", why, fen);
let trimmed = fen.trim_matches(is_space);
let text = trimmed.strip_suffix('.').unwrap_or(trimmed);
let parts = split_on(text, ':');
let turn = parts.first().map_or("", |t| t.trim_matches(is_space)).to_uppercase();
let side = match turn.as_str() {
"B" => BLACK,
"W" => WHITE,
_ => return Err(error("the side to move is B or W".into())),
};
let mut pieces: Vec<(i32, i32)> = Vec::new();
for l in parts.iter().skip(1) {
if l.chars().all(is_space) {
continue; // blank
}
let l = l.trim_matches(is_space);
let colour = match l
.chars()
.next()
.map(|c| c.to_uppercase().collect::<String>())
.as_deref()
{
Some("W") => WHITE,
Some("B") => BLACK,
_ => return Err(error(format!("a list of pieces starts with W or B: {}", pr_str(l)))),
};
let rest = &l[l.chars().next().map_or(0, |c| c.len_utf8())..];
for item in split_on(rest, ',') {
if item.chars().all(is_space) {
continue;
}
let (king, a, b) = square_item(item).ok_or_else(|| error(format!("no square in {}", pr_str(item))))?;
for n in a..=b {
if !(1..=32).contains(&n) {
return Err(error(format!("there is no square {}", n)));
}
let sq = n - 1;
if pieces.iter().any(|&(s, _)| s == sq) {
return Err(error(format!("square {} is named twice", sq + 1)));
}
if !king && row_of(sq) == crown_row(colour) {
return Err(error(format!("a man on {} would have been crowned", sq + 1)));
}
pieces.push((sq, if king { KING } else { MAN } + colour * WHITE_PIECE));
}
}
}
let of = |s: i32| pieces.iter().filter(|&&(_, p)| side_of(p) == s).count();
if of(BLACK) > 12 {
Err(error("Black has more than 12 pieces".into()))
} else if of(WHITE) > 12 {
Err(error("White has more than 12 pieces".into()))
} else if of(side ^ 1) == 0 {
Err(error("the side that has just moved has no pieces".into()))
} else {
Ok((side, pieces))
}
}
/// Set the board to the position a FEN names, which read_fen checks. The history is emptied, and no jump or man's
/// move is counted before it.
pub fn set_position(&mut self, fen: &str) -> Result<(), String> {
let (side, pieces) = Board::read_fen(fen)?;
self.squares = [0; 32];
self.counts = [0; 4];
self.side = 0;
self.halfmove = 0;
self.ply = 0;
self.hash_lo = 0;
self.hash_hi = 0;
for (sq, piece) in pieces {
self.put(piece, sq);
}
if side == WHITE {
self.side = WHITE;
self.toggle(SIDE_KEY);
}
Ok(())
}
/// The position in FEN: the side to move, then White's pieces and Black's, each side's in the order of their squares.
pub fn fen(&self) -> String {
let of = |s: i32| -> String {
let listed: Vec<String> = (0..32)
.filter_map(|sq| {
let piece = self.squares[sq as usize];
(piece != 0 && side_of(piece) == s)
.then(|| format!("{}{}", if kind(piece) == KING { "K" } else { "" }, sq + 1))
})
.collect();
listed.join(",")
};
format!(
"{}:W{}:B{}",
if self.side == 0 { "B" } else { "W" },
of(WHITE),
of(BLACK)
)
}
/// The side to move's moves, in the order generate makes them. A jump that takes the same pieces as one before it and
/// ends where it does, by another way round, is the same move, and is left out.
pub fn legal_moves(&mut self) -> Vec<i32> {
let mut scratch = std::mem::take(&mut self.scratch);
let end = self.generate(&mut scratch, 0, false);
let mut seen: Vec<(i32, i32, Vec<i32>)> = Vec::new();
let mut found = Vec::new();
for &m in &scratch[..end] {
if is_jump(m) {
let mut t = taken(m);
t.sort_unstable();
let key = (move_from(m), move_to(m), t);
if seen.contains(&key) {
continue;
}
seen.push(key);
}
found.push(m);
}
self.scratch = scratch;
found
}
/// Has the side to move a move? Without one, it has lost.
pub fn has_move(&mut self) -> bool {
let mut scratch = std::mem::take(&mut self.scratch);
let end = self.generate(&mut scratch, 0, false);
self.scratch = scratch;
end > 0
}
/// The legal moves the squares a player names can mean, numbers from 1: where the piece starts and every square it
/// lands on, or where it starts and where it ends.
fn moves_by(&mut self, numbers: &[i32]) -> Vec<i32> {
let squares: Vec<i32> = numbers.iter().map(|n| n - 1).collect();
self.legal_moves()
.into_iter()
.filter(|&m| {
let path = landings(m);
path == squares || (squares.len() == 2 && path[0] == squares[0] && path[path.len() - 1] == squares[1])
})
.collect()
}
/// The legal moves a move written as players write it can mean: 11-15, 22x15, 22x15x6, or 22x6 for the jump from 22
/// that ends on 6. Squares may be joined by a dash, an x or a space, as checkers.board/parse-move splits them, at
/// `\s*[-x\s]\s*`.
pub fn parse_move(&mut self, text: &str) -> Vec<i32> {
let lower = text.trim_matches(is_space).to_lowercase();
let chars: Vec<char> = lower.chars().collect();
let mut parts: Vec<String> = vec![String::new()];
let mut i = 0;
while i < chars.len() {
// a separator here: spaces, then a dash or an x, then spaces; or at least one space alone
let mut j = i;
while j < chars.len() && is_space(chars[j]) {
j += 1;
}
let sep_end = if j < chars.len() && (chars[j] == '-' || chars[j] == 'x') {
let mut k = j + 1;
while k < chars.len() && is_space(chars[k]) {
k += 1;
}
Some(k)
} else if j > i {
Some(j)
} else {
None
};
match sep_end {
Some(k) => {
parts.push(String::new());
i = k;
}
None => {
parts.last_mut().unwrap().push(chars[i]);
i += 1;
}
}
}
while parts.last().is_some_and(|p| p.is_empty()) {
parts.pop(); // clojure.string/split drops the empty strings at the end
}
let square = |p: &String| !p.is_empty() && p.len() <= 2 && p.bytes().all(|b| b.is_ascii_digit());
if parts.len() >= 2 && parts.iter().all(square) {
let numbers: Vec<i32> = parts.iter().map(|p| p.parse().unwrap()).collect();
self.moves_by(&numbers)
} else {
Vec::new()
}
}
/// Play a legal move written as players write it, the first it can mean, or say it is not one.
pub fn play_notation(&mut self, text: &str) -> Result<(), String> {
match self.parse_move(text).first() {
Some(&m) if (self.ply as usize) < MAX_HISTORY - 128 => {
self.make(m);
Ok(())
}
Some(_) => Err(format!("too many moves to play: {}", text)),
None => Err(format!("not a legal move here: {}", text)),
}
}
fn perft_from(&mut self, buffer: &mut [i32], depth: i32, start: usize) -> u64 {
let end = self.generate(buffer, start, false);
if depth == 1 {
return (end - start) as u64;
}
let mut nodes = 0;
for i in start..end {
let m = buffer[i];
self.make(m);
nodes += self.perft_from(buffer, depth - 1, end);
self.unmake();
}
nodes
}
/// How many move sequences of depth moves the position has: the move generator's test.
pub fn perft(&mut self, depth: i32) -> u64 {
if depth <= 0 {
1
} else {
let mut buffer = vec![0; 256 * depth as usize];
self.perft_from(&mut buffer, depth, 0)
}
}
}engine.js · 8 lines
// Checkers' engine, for the WebAssembly worker, ../worker.js, which scripts/chess/build.mjs writes after this into
// public/machine/checkers-wasm-worker.js: its name, its two modules, for one thread and for every core, and how a search's
// request becomes the module's think, with every option checkers.worker takes, NaN for one not given.
self.wasmEngine = {
name: 'checkers',
modules: ['checkers.wasm', 'checkers-threads.wasm'],
think: (wasm, msg, given) => wasm.think(msg.ms ?? 2000, given(msg.maxMs), msg.depth ?? 64, given(msg.plyLimit), given(msg.nodes), msg.contempt ?? 0),
};worker.js · 238 lines
// The background search of the engines in WebAssembly, Chessmate 2026's for /chessmate and Checkers' for /checkers:
// public/machine/chess-wasm-worker.js and public/machine/checkers-wasm-worker.js, each this file after its engine's
// engine.js (src/wasm/chessmate, src/wasm/checkers), which names the engine, its two modules, for one thread and for
// every core, and how a search's request becomes the module's think; scripts/chess/build.mjs compiles each engine's Rust
// into its modules and writes its worker. It answers the page's messages as the ClojureScript builds' workers answer them
// (chessmate.v2.worker, checkers.worker; add-chessmate-v2 D41): a search's started, info and best replies, evaluate,
// perft, clear and ping, and an error for anything else. The engine, the whole search, is the module's; this file only
// carries messages to it and its replies back.
//
// Like the ClojureScript workers, it lives on between the engine's moves, so that its transposition table carries what
// it learnt thinking about one move into the next.
//
// Where the page is cross-origin isolated, so that workers may share memory, it searches on every core the browser
// reports: it runs the threaded module on a memory it shares with a helper for each other core, a worker of this same
// file, which searches beside it into the same table (each engine's threads.rs). Elsewhere it runs the module for one
// thread alone, which plays node for node as the ClojureScript does. There the page gives up a search by number, through
// a word of the shared
// memory this worker hands it (a control reply), and the worker is free for the next at once; elsewhere, by ending the
// worker. Helpers whose worker has ended stop once its heartbeat stops, and then end themselves (threads.rs).
//
// The tests run this file under Node, as the body of a function whose parameter is `self`: they hand it the compiled
// module as self.engineModule, a clock as self.engineClock, and for threads self.engineThreads, the threaded module, the
// number of threads and a function that starts a helper.
(() => {
const ENGINE = self.wasmEngine; // engine.js's: { name, modules: [one thread's, every core's], think(wasm, msg, given) }
const MAX_THREADS = 32; // threads.rs's
// The threaded module's memory, in 64 KB pages: 2 MB at first, and at most 256 MB, as build.mjs links it
const PAGES = 32, MAX_PAGES = 4096;
const STACK = 1 << 20; // each helper's stack, as large as the main thread's
const READY_WAIT_MS = 2000; // how long the first search waits for the helpers to start
const BEAT_MS = 250; // how often the main thread's worker beats while it waits for the page
const SILENT_WAITS = 2; // how many seconds of silence end a waiting helper
const clock = self.engineClock || (() => performance.now());
if (/^\w+ helper \d+$/.test(self.name ?? '')) {
helper();
return;
}
const decoder = new TextDecoder();
const encoder = new TextEncoder();
let wasm = null; // the module's exports, once it has started
let memory = null; // its memory
let helpers = []; // the helpers' workers
let beating = null; // the heartbeat's timer, while there are helpers
let control = null; // where memory is shared: a view of its words, and SEARCH's index in it (threads.rs's CONTROL)
let failed = null; // why it could not start
let searching = null; // the id of the search under way, whose iterations on_iteration reports
let waiting = []; // the messages that came while it was starting
const post = (reply) => self.postMessage(reply);
/** The module's buffer, len bytes of it. Its memory grows as the engine needs, which replaces memory.buffer, so the
* view is made afresh each time, once the buffer's address is known. */
function buffer(len) {
const at = wasm.io();
return new Uint8Array(memory.buffer, at, len);
}
/** Text the module wrote into its buffer, len bytes; copied out first, since a TextDecoder reads no shared memory. */
const read = (len) => decoder.decode(buffer(len).slice());
/** Write text into the module's buffer, and return its length in bytes. */
function write(text) {
const bytes = encoder.encode(String(text));
buffer(bytes.length).set(bytes);
return bytes.length;
}
/** A search's report as an info or best reply: the ClojureScript worker's fields, from the module's JSON. */
const reply = (type, id, len) => ({ type, id, ...JSON.parse(read(len)) });
const iteration = (len) => post(reply('info', searching, len));
/** How many threads to search on: as many as the browser reports cores, or as the worker's address asks for
* (chess-wasm-worker.js?threads=n), at most MAX_THREADS; and one where the page is not cross-origin isolated, since
* workers may share memory only there. */
function threadCount() {
if (self.engineThreads) return Math.min(MAX_THREADS, self.engineThreads.count);
if (!self.crossOriginIsolated) return 1;
let asked = 0;
try { asked = Math.floor(Number(new URL(self.location.href).searchParams.get('threads'))); } catch { /* no address */ }
return Math.max(1, Math.min(MAX_THREADS, asked >= 1 ? asked : self.navigator?.hardwareConcurrency || 1));
}
/** A module, compiled: the one the tests gave, or the file beside this one. */
async function load(file, given) {
if (given) return given;
const r = await fetch(new URL(file, self.location.href));
if (!r.ok) throw new Error(`${file}: ${r.status}`);
return WebAssembly.compile(await r.arrayBuffer());
}
/** One thread: the engine's first module, on its own memory. */
async function startOne() {
const instance = await WebAssembly.instantiate(await load(ENGINE.modules[0], self.engineModule), { env: { now: clock, on_iteration: iteration } });
return [instance.exports, instance.exports.memory];
}
/** n threads: the engine's threaded module, on a memory shared with n - 1 helpers, each handed the module, the memory
* and a stack of its own. They start before the first search: a worker that is searching cannot start another. */
async function startThreads(n) {
const module = await load(ENGINE.modules[1], self.engineThreads?.module);
const shared = new WebAssembly.Memory({ initial: PAGES, maximum: MAX_PAGES, shared: true });
const words = new Int32Array(shared.buffer);
const wake = (at) => Atomics.notify(words, at >>> 2);
const x = (await WebAssembly.instantiate(module, { env: { memory: shared, now: clock, on_iteration: iteration, wake } })).exports;
const at = x.control() >>> 2; // SEQ, then PULSE, SEARCH and ABANDONED
beating = setInterval(() => Atomics.add(words, at + 1, 1), BEAT_MS); // the search beats for itself
beating.unref?.(); // under Node, the tests', it keeps nothing running
const spawn = self.engineThreads?.spawn ?? ((name) => new Worker(self.location.href, { name }));
const started = [];
for (let t = 1; t < n; t++) {
const w = spawn(`${ENGINE.name} helper ${t}`);
helpers.push(w);
started.push(new Promise((done) => {
w.onmessage = done; // ready, or failed: either way no longer starting
w.onerror = (e) => { e?.preventDefault?.(); done(); };
}));
w.postMessage({ module, memory: shared, thread: t, stack: x.stack(STACK) });
}
x.helpers(helpers.length);
await Promise.race([Promise.all(started), new Promise((r) => setTimeout(r, READY_WAIT_MS))]);
control = { words, search: at + 2 };
post({ type: 'control', abandoned: new Int32Array(shared.buffer, 4 * (at + 3), 1) }); // for the page to give searches up
return [x, shared];
}
function endHelpers() {
clearInterval(beating);
helpers.forEach((w) => w.terminate());
helpers = [];
control = null;
}
function flush() {
const queued = waiting;
waiting = [];
queued.forEach(handle);
}
function start() {
endHelpers();
wasm = null;
memory = null;
const threads = threadCount();
if (threads === 1 && self.engineModule) { // the tests', at once
const instance = new WebAssembly.Instance(self.engineModule, { env: { now: clock, on_iteration: iteration } });
[wasm, memory] = [instance.exports, instance.exports.memory];
return;
}
const one = () => { endHelpers(); return startOne(); };
(threads > 1 ? startThreads(threads).catch(one) : startOne())
.then(([x, m]) => { [wasm, memory] = [x, m]; }, (e) => { failed = `the WebAssembly engine could not start: ${e?.message || e}`; })
.then(flush);
}
/** A helper: the threaded module on the main thread's memory, with its own stack, which waits for each search to
* start and searches it until it ends (threads.rs). It never returns to its messages: the worker that started it
* ends it, or, when that worker has ended and its heartbeat has been silent for SILENT_WAITS seconds, it ends itself. */
function helper() {
self.onmessage = ({ data: { module, memory: shared, thread, stack } }) => {
let x;
try {
x = new WebAssembly.Instance(module, { env: { memory: shared, now: clock, on_iteration() {}, wake() {} } }).exports;
x.__stack_pointer.value = stack;
} catch (e) {
self.postMessage({ type: 'error', thread, message: e?.message || String(e) });
return;
}
const words = new Int32Array(shared.buffer), seq = x.control() >>> 2, pulse = seq + 1;
self.postMessage({ type: 'ready', thread });
let beat = Atomics.load(words, pulse), silent = 0;
for (let seen = 0; ;) {
if (Atomics.wait(words, seq, seen, 1000) === 'timed-out') {
const now = Atomics.load(words, pulse);
if (now !== beat) [beat, silent] = [now, 0];
else if (++silent >= SILENT_WAITS) { self.close(); return; }
continue;
}
seen = Atomics.load(words, seq);
x.help(thread);
[beat, silent] = [Atomics.load(words, pulse), 0];
}
};
}
/** Set the board to a request's position: its FEN, then its moves. */
function setPosition(msg) {
const refused = wasm.set_position(write(msg.fen));
if (refused < 0) throw new Error(read(-refused));
for (const m of msg.moves ?? []) {
const illegal = wasm.play(write(m));
if (illegal < 0) throw new Error(read(-illegal));
}
}
const given = (x) => (x == null ? NaN : Number(x));
/** Answer one message from the page, as the ClojureScript workers' handle does. */
function handle(msg) {
const kind = msg?.type, id = msg?.id;
if (!wasm && !failed) { waiting.push(msg); return; }
try {
if (failed && kind !== 'ping') throw new Error(failed);
switch (kind) {
case 'ping': post({ type: 'pong', id }); break;
case 'search': {
post({ type: 'started', id }); // at once: the page waits 5 s for this, not for a result
setPosition(msg);
searching = id;
if (control) Atomics.store(control.words, control.search, msg.seq ?? 0); // its number, by which the page may give it up
const len = ENGINE.think(wasm, msg, given);
post(reply('best', id, len));
break;
}
case 'evaluate': setPosition(msg); post({ type: 'evaluate', id, score: wasm.evaluate() }); break;
case 'perft': {
setPosition(msg);
const t = performance.now(), nodes = wasm.perft(msg.depth);
post({ type: 'perft', id, nodes, ms: performance.now() - t });
break;
}
case 'clear': wasm.clear(); post({ type: 'cleared', id }); break;
default: post({ type: 'error', id, message: `unknown message type ${kind == null ? 'nil' : JSON.stringify(kind)}` });
}
} catch (e) {
post({ type: 'error', id, message: e?.message || String(e) });
if (e instanceof WebAssembly.RuntimeError) start(); // a trap leaves the engine half way: start afresh
} finally {
searching = null;
if (control) Atomics.store(control.words, control.search, 0);
}
}
self.onmessage = (e) => handle(e.data);
start();
})();Cargo.toml · 24 lines
# Checkers' engine in Rust, compiled to WebAssembly for /checkers: a port of checkers.board, checkers.eval and
# checkers.search (src/machine/checkers/checkers), which plays node for node as they do. scripts/chess/build.mjs compiles
# it into public/machine/checkers.wasm, and with its threads feature into public/machine/checkers-threads.wasm, which
# searches on every core.
[package]
name = "checkers"
version = "2026.1.0"
edition = "2021"
publish = false
[lib]
crate-type = ["cdylib"]
path = "src/lib.rs"
[features]
# The threaded build, checkers-threads.wasm, which build.mjs compiles with atomics and shared memory: the helpers'
# exports, the host's `wake`, and an allocator for many threads (lib.rs, threads.rs).
threads = []
[profile.release]
opt-level = 3
lto = true
codegen-units = 1
panic = "abort"