use crate::knowledge::{Knowledge, analyze};
use crate::{Cell, Color, GameResult, Move, Position, Seat};
#[cfg(not(target_arch = "wasm32"))]
use std::time::{Duration, Instant};
#[cfg(target_arch = "wasm32")]
use wasm_bindgen::prelude::*;
const DEFAULT_EXPLORATION: f64 = 0.2;
const DEFAULT_RAVE_EQUIVALENCE: f64 = 1_000.0;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum MctsStrategy {
PlainUct,
UctRave,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum RolloutPolicy {
Random,
SaveBridge,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum KnowledgePolicy {
Disabled,
InferiorCells { min_visits: u32 },
}
impl KnowledgePolicy {
pub const fn min_visits(self) -> Option<u32> {
match self {
Self::Disabled => None,
Self::InferiorCells { min_visits } => Some(min_visits),
}
}
}
impl RolloutPolicy {
pub const fn as_str(self) -> &'static str {
match self {
Self::Random => "random",
Self::SaveBridge => "save-bridge",
}
}
}
impl MctsStrategy {
pub const fn as_str(self) -> &'static str {
match self {
Self::PlainUct => "plain-uct",
Self::UctRave => "uct-rave",
}
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct MctsOptions {
pub max_simulations: u32,
pub soft_time_ms: u32,
pub exploration: f64,
pub strategy: MctsStrategy,
pub rave_equivalence: f64,
pub rollout_policy: RolloutPolicy,
pub knowledge_policy: KnowledgePolicy,
pub use_virtual_connections: bool,
pub seed: u64,
}
impl Default for MctsOptions {
fn default() -> Self {
MCTS_PRESETS[MCTS_PRESETS.len() - 1].options
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct MctsPreset {
pub name: &'static str,
pub options: MctsOptions,
}
pub const MCTS_PRESETS: [MctsPreset; 6] = [
preset("beginner", 200, 50),
preset("easy", 1_000, 100),
preset("medium", 4_000, 200),
preset("hard", 20_000, 500),
preset("expert", 80_000, 1_300),
preset("maximum", 200_000, 2_000),
];
const fn preset(name: &'static str, max_simulations: u32, soft_time_ms: u32) -> MctsPreset {
MctsPreset {
name,
options: MctsOptions {
max_simulations,
soft_time_ms,
exploration: DEFAULT_EXPLORATION,
strategy: MctsStrategy::UctRave,
rave_equivalence: DEFAULT_RAVE_EQUIVALENCE,
rollout_policy: RolloutPolicy::SaveBridge,
knowledge_policy: KnowledgePolicy::InferiorCells { min_visits: 32 },
use_virtual_connections: true,
seed: 1,
},
}
}
pub fn mcts_preset(name: &str) -> Option<MctsPreset> {
MCTS_PRESETS
.iter()
.copied()
.find(|preset| preset.name == name)
}
#[derive(Clone, Debug, PartialEq)]
pub struct MctsMoveStats {
pub mv: Move,
pub visits: u32,
pub expected_score: f64,
pub rave_visits: u32,
pub rave_expected_score: f64,
pub proven_winner: Option<Seat>,
pub proof_distance: Option<u16>,
}
#[derive(Clone, Debug, PartialEq)]
pub struct MctsReport {
pub best_move: Option<Move>,
pub strategy: MctsStrategy,
pub rave_equivalence: f64,
pub rollout_policy: RolloutPolicy,
pub knowledge_policy: KnowledgePolicy,
pub virtual_connections_enabled: bool,
pub simulations: u32,
pub tree_nodes: u32,
pub root_visits: u32,
pub expected_score: f64,
pub elapsed_ms: u32,
pub rollout_moves: u64,
pub bridge_replies: u64,
pub knowledge_nodes: u32,
pub pruned_moves: u32,
pub must_play_nodes: u32,
pub root_pruned_moves: u32,
pub root_must_play_moves: u32,
pub virtual_connections: u32,
pub semi_connections: u32,
pub connection_search_truncated_nodes: u32,
pub proven_nodes: u32,
pub solver_propagations: u32,
pub proven_winner: Option<Seat>,
pub proof_distance: Option<u16>,
pub root_moves: Vec<MctsMoveStats>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Proof {
winner: Seat,
distance: Option<u16>,
}
struct Node {
position: Position,
parent: Option<usize>,
incoming_move: Option<Move>,
children: Vec<usize>,
permutation_offset: u16,
permutation_step: u16,
next_slot: u16,
swap_unexpanded: bool,
visits: u32,
value_sum: f64,
rave_visits: u32,
rave_value_sum: f64,
knowledge: Option<Knowledge>,
proof: Option<Proof>,
}
impl Node {
fn new(
position: Position,
parent: Option<usize>,
incoming_move: Option<Move>,
random: &mut SplitMix64,
) -> Self {
let cells = position.size().cell_count();
let proof = match position.result() {
GameResult::Win(winner) => Some(Proof {
winner,
distance: Some(0),
}),
GameResult::Ongoing => None,
};
Self {
position,
parent,
incoming_move,
children: Vec::new(),
permutation_offset: random.index(usize::from(cells)) as u16,
permutation_step: coprime_step(cells, random),
next_slot: 0,
swap_unexpanded: position.swap_available(),
visits: 0,
value_sum: 0.0,
rave_visits: 0,
rave_value_sum: 0.0,
knowledge: None,
proof,
}
}
fn next_unexpanded(&mut self) -> Option<Move> {
if self.swap_unexpanded {
self.swap_unexpanded = false;
return Some(Move::Swap);
}
let cells = self.position.size().cell_count();
while self.next_slot < cells {
let dense = (u32::from(self.permutation_offset)
+ u32::from(self.next_slot) * u32::from(self.permutation_step))
% u32::from(cells);
self.next_slot += 1;
let cell = crate::Cell::from_dense(dense as u16, self.position.size());
let mv = Move::Place(cell);
if self.position.is_legal(mv) && self.knowledge.is_none_or(|info| info.allows(mv)) {
return Some(mv);
}
}
None
}
fn allows(&self, mv: Move) -> bool {
self.knowledge.is_none_or(|knowledge| knowledge.allows(mv))
}
fn expansion_exhausted(&self) -> bool {
!self.swap_unexpanded && self.next_slot >= self.position.size().cell_count()
}
}
pub struct MctsSearcher {
nodes: Vec<Node>,
random: SplitMix64,
}
impl Default for MctsSearcher {
fn default() -> Self {
Self::new()
}
}
impl MctsSearcher {
pub fn new() -> Self {
Self {
nodes: Vec::with_capacity(16_384),
random: SplitMix64(1),
}
}
pub fn search(&mut self, position: Position, options: MctsOptions) -> MctsReport {
self.nodes.clear();
self.random = SplitMix64(options.seed);
self.nodes
.push(Node::new(position, None, None, &mut self.random));
let root_seat = position.seat_to_move();
let clock = Clock::new(options.soft_time_ms);
let mut simulations = 0;
let mut rollout_moves = 0;
let mut bridge_replies = 0;
let mut counters = SearchCounters::default();
if position.result() == GameResult::Ongoing {
for simulation in 0..options.max_simulations.max(1) {
if simulation > 0 && simulation % 16 == 0 && clock.expired() {
break;
}
let rollout = self.run_simulation(root_seat, options, &mut counters);
rollout_moves += u64::from(rollout.moves);
bridge_replies += u64::from(rollout.bridge_replies);
simulations += 1;
if self.nodes[0]
.proof
.is_some_and(|proof| proof.winner == root_seat)
&& !self.nodes[0].children.is_empty()
{
break;
}
}
}
let mut root_moves = self.nodes[0]
.children
.iter()
.filter(|&&index| {
self.nodes[0].allows(
self.nodes[index]
.incoming_move
.expect("root children have moves"),
)
})
.map(|&index| {
let child = &self.nodes[index];
MctsMoveStats {
mv: child.incoming_move.expect("root children have moves"),
visits: child.visits,
expected_score: child.proof.map_or_else(
|| mean_score(child),
|proof| f64::from(proof.winner == root_seat),
),
rave_visits: child.rave_visits,
rave_expected_score: rave_mean_score(child),
proven_winner: child.proof.map(|proof| proof.winner),
proof_distance: child.proof.and_then(|proof| proof.distance),
}
})
.collect::<Vec<_>>();
root_moves.sort_by(|left, right| compare_root_moves(left, right, root_seat));
let best_move = root_moves.first().map(|stats| stats.mv);
let expected_score = self.nodes[0].proof.map_or_else(
|| root_moves.first().map_or(0.5, |stats| stats.expected_score),
|proof| f64::from(proof.winner == root_seat),
);
MctsReport {
best_move,
strategy: options.strategy,
rave_equivalence: options.rave_equivalence,
rollout_policy: options.rollout_policy,
knowledge_policy: options.knowledge_policy,
virtual_connections_enabled: options.use_virtual_connections,
simulations,
tree_nodes: self.nodes.len() as u32,
root_visits: self.nodes[0].visits,
expected_score,
elapsed_ms: clock.elapsed_ms(),
rollout_moves,
bridge_replies,
knowledge_nodes: counters.knowledge_nodes,
pruned_moves: counters.pruned_moves,
must_play_nodes: counters.must_play_nodes,
root_pruned_moves: self.nodes[0]
.knowledge
.map_or(0, |knowledge| knowledge.pruned.count()),
root_must_play_moves: self.nodes[0]
.knowledge
.and_then(|knowledge| knowledge.must_play)
.map_or(0, |moves| moves.count()),
virtual_connections: counters.virtual_connections,
semi_connections: counters.semi_connections,
connection_search_truncated_nodes: counters.connection_search_truncated_nodes,
proven_nodes: counters.proven_nodes,
solver_propagations: counters.solver_propagations,
proven_winner: self.nodes[0].proof.map(|proof| proof.winner),
proof_distance: self.nodes[0].proof.and_then(|proof| proof.distance),
root_moves,
}
}
fn run_simulation(
&mut self,
root_seat: Seat,
options: MctsOptions,
counters: &mut SearchCounters,
) -> RolloutSummary {
let mut node = 0;
loop {
if self.nodes[node].position.result() != GameResult::Ongoing
|| (node != 0 && self.nodes[node].proof.is_some())
{
break;
}
self.prepare_knowledge(
node,
options.knowledge_policy,
options.use_virtual_connections,
counters,
);
if node != 0 && self.nodes[node].proof.is_some() {
break;
}
let next_move = self.nodes[node].next_unexpanded();
if let Some(mv) = next_move {
let position = self.nodes[node]
.position
.play(mv)
.expect("tree expansion uses legal moves");
let child = self.nodes.len();
self.nodes
.push(Node::new(position, Some(node), Some(mv), &mut self.random));
self.nodes[node].children.push(child);
node = child;
break;
}
if self.nodes[node].children.is_empty() {
break;
}
node = self.select_child(node, root_seat, options);
}
let last_move = self.nodes[node].incoming_move.and_then(Move::cell);
let rollout = self.nodes[node].proof.map_or_else(
|| {
self.rollout(
self.nodes[node].position,
root_seat,
last_move,
options.rollout_policy,
)
},
|proof| Rollout {
score: f64::from(proof.winner == root_seat),
moves: 0,
bridge_replies: 0,
trace: MoveTrace::default(),
},
);
let mut trace = rollout.trace;
let mut current = Some(node);
while let Some(index) = current {
let parent = self.nodes[index].parent;
self.nodes[index].visits += 1;
self.nodes[index].value_sum += rollout.score;
if options.strategy == MctsStrategy::UctRave {
self.update_rave(index, trace, rollout.score);
}
if let (Some(parent), Some(mv)) = (parent, self.nodes[index].incoming_move) {
trace.prepend(self.nodes[parent].position.color_to_move(), mv);
}
self.refresh_proof(index, counters);
current = parent;
}
RolloutSummary {
moves: rollout.moves,
bridge_replies: rollout.bridge_replies,
}
}
fn prepare_knowledge(
&mut self,
node: usize,
policy: KnowledgePolicy,
use_virtual_connections: bool,
counters: &mut SearchCounters,
) {
let Some(min_visits) = policy.min_visits() else {
return;
};
if self.nodes[node].knowledge.is_some()
|| (node != 0 && self.nodes[node].visits < min_visits)
{
return;
}
let knowledge = analyze(self.nodes[node].position, use_virtual_connections);
counters.knowledge_nodes += 1;
counters.pruned_moves += knowledge.pruned.count();
counters.must_play_nodes += u32::from(knowledge.must_play.is_some());
counters.virtual_connections += knowledge.virtual_connections;
counters.semi_connections += knowledge.semi_connections;
counters.connection_search_truncated_nodes +=
u32::from(knowledge.connection_search_truncated);
if let Some(winner) = knowledge.proven_winner {
self.nodes[node].proof = Some(Proof {
winner,
distance: None,
});
counters.proven_nodes += 1;
}
self.nodes[node].knowledge = Some(knowledge);
}
fn select_child(&self, parent: usize, root_seat: Seat, options: MctsOptions) -> usize {
let node = &self.nodes[parent];
let mover = node.position.seat_to_move();
let root_turn = node.position.seat_to_move() == root_seat;
let log_parent = f64::from(node.visits.max(1)).ln();
let allowed = node
.children
.iter()
.copied()
.filter(|&child| {
node.allows(
self.nodes[child]
.incoming_move
.expect("children have moves"),
)
})
.collect::<Vec<_>>();
if let Some(winning) = allowed
.iter()
.copied()
.filter(|&child| {
self.nodes[child]
.proof
.is_some_and(|proof| proof.winner == mover)
})
.min_by_key(|&child| {
(
self.nodes[child]
.proof
.expect("filtered proof")
.distance
.unwrap_or(u16::MAX),
self.nodes[child]
.incoming_move
.expect("children have moves")
.order_key(),
)
})
{
return winning;
}
let unresolved = allowed
.iter()
.copied()
.filter(|&child| self.nodes[child].proof.is_none())
.collect::<Vec<_>>();
if !unresolved.is_empty() {
return unresolved
.into_iter()
.max_by(|&left, &right| {
let score = |index| {
let child = &self.nodes[index];
selection_score(child, root_turn, log_parent, options)
};
score(left).total_cmp(&score(right)).then_with(|| {
self.nodes[right]
.incoming_move
.expect("children have moves")
.order_key()
.cmp(
&self.nodes[left]
.incoming_move
.expect("children have moves")
.order_key(),
)
})
})
.expect("unresolved selection requires a child");
}
allowed
.into_iter()
.max_by_key(|&child| {
(
self.nodes[child]
.proof
.expect("all children proven")
.distance
.unwrap_or(u16::MAX),
std::cmp::Reverse(
self.nodes[child]
.incoming_move
.expect("children have moves")
.order_key(),
),
)
})
.expect("selection requires a child")
}
fn refresh_proof(&mut self, node: usize, counters: &mut SearchCounters) {
if self.nodes[node].proof.is_some()
|| self.nodes[node].position.result() != GameResult::Ongoing
{
return;
}
let mover = self.nodes[node].position.seat_to_move();
let allowed = self.nodes[node]
.children
.iter()
.copied()
.filter(|&child| {
self.nodes[node].allows(
self.nodes[child]
.incoming_move
.expect("children have moves"),
)
})
.collect::<Vec<_>>();
let proof = if let Some(proof) = allowed
.iter()
.filter_map(|&child| self.nodes[child].proof)
.filter(|proof| proof.winner == mover)
.min_by_key(|proof| proof.distance.unwrap_or(u16::MAX))
{
Some(Proof {
winner: mover,
distance: proof.distance.map(|distance| distance.saturating_add(1)),
})
} else if self.nodes[node].expansion_exhausted()
&& !allowed.is_empty()
&& allowed.iter().all(|&child| {
self.nodes[child]
.proof
.is_some_and(|proof| proof.winner == mover.other())
})
{
Some(Proof {
winner: mover.other(),
distance: allowed
.iter()
.try_fold(0, |longest, &child| {
self.nodes[child]
.proof
.and_then(|proof| proof.distance)
.map(|distance| longest.max(distance))
})
.map(|distance| distance.saturating_add(1)),
})
} else {
None
};
if let Some(proof) = proof {
self.nodes[node].proof = Some(proof);
counters.proven_nodes += 1;
counters.solver_propagations += 1;
}
}
fn update_rave(&mut self, node: usize, trace: MoveTrace, score: f64) {
let color = self.nodes[node].position.color_to_move();
let child_count = self.nodes[node].children.len();
for slot in 0..child_count {
let child = self.nodes[node].children[slot];
let Some(cell) = self.nodes[child]
.incoming_move
.expect("children have moves")
.cell()
else {
continue;
};
if trace.contains(color, cell) {
self.nodes[child].rave_visits += 1;
self.nodes[child].rave_value_sum += score;
}
}
}
fn rollout(
&mut self,
mut position: Position,
root_seat: Seat,
mut last_move: Option<Cell>,
policy: RolloutPolicy,
) -> Rollout {
if let GameResult::Win(winner) = position.result() {
return Rollout {
score: f64::from(winner == root_seat),
moves: 0,
bridge_replies: 0,
trace: MoveTrace::default(),
};
}
let mut moves = 0;
let mut trace = MoveTrace::default();
let mut crossed_swap = false;
let mut bridge_replies = 0;
if position.swap_available() {
if self.random.next() & 1 == 0 {
position = position.play(Move::Swap).expect("swap is available");
moves += 1;
crossed_swap = true;
last_move = None;
} else {
position.rollout_decline_swap();
}
}
let mut empty = position.empty_cells();
for index in (1..empty.len()).rev() {
let other = self.random.index(index + 1);
empty.swap(index, other);
}
let empty_count = empty.len();
let mut cursor = 0;
while moves - u32::from(crossed_swap) < empty_count as u32 {
let response = (policy != RolloutPolicy::Random)
.then(|| last_move.and_then(|cell| self.random_bridge_response(position, cell)))
.flatten();
let cell = if let Some(response) = response {
bridge_replies += 1;
response
} else {
loop {
let cell = empty[cursor];
cursor += 1;
if position.color_at(cell).is_none() {
break cell;
}
}
};
if !crossed_swap {
trace.insert(position.color_to_move(), cell);
}
position.rollout_place(cell);
moves += 1;
last_move = Some(cell);
}
let winner = position.winner_on_full_board();
Rollout {
score: f64::from(winner == root_seat),
moves,
bridge_replies,
trace,
}
}
fn random_bridge_response(&mut self, position: Position, attacked: Cell) -> Option<Cell> {
let (responses, count) =
crate::patterns::bridge_responses(position, position.color_to_move(), attacked);
(count > 0).then(|| responses[self.random.index(count)])
}
}
fn mean_score(node: &Node) -> f64 {
node.value_sum / f64::from(node.visits.max(1))
}
fn rave_mean_score(node: &Node) -> f64 {
if node.rave_visits == 0 {
0.5
} else {
node.rave_value_sum / f64::from(node.rave_visits)
}
}
fn compare_root_moves(
left: &MctsMoveStats,
right: &MctsMoveStats,
root_seat: Seat,
) -> std::cmp::Ordering {
let rank = |stats: &MctsMoveStats| match stats.proven_winner {
Some(winner) if winner == root_seat => 2,
None => 1,
Some(_) => 0,
};
rank(right)
.cmp(&rank(left))
.then_with(|| match (left.proven_winner, right.proven_winner) {
(Some(left_winner), Some(right_winner))
if left_winner == root_seat && right_winner == root_seat =>
{
proof_distance_rank(left.proof_distance)
.cmp(&proof_distance_rank(right.proof_distance))
}
(Some(left_winner), Some(right_winner))
if left_winner != root_seat && right_winner != root_seat =>
{
proof_distance_rank(right.proof_distance)
.cmp(&proof_distance_rank(left.proof_distance))
}
_ => right
.visits
.cmp(&left.visits)
.then_with(|| right.expected_score.total_cmp(&left.expected_score)),
})
.then_with(|| left.mv.order_key().cmp(&right.mv.order_key()))
}
fn proof_distance_rank(distance: Option<u16>) -> u16 {
distance.unwrap_or(u16::MAX)
}
fn selection_score(node: &Node, root_turn: bool, log_parent: f64, options: MctsOptions) -> f64 {
let orient = |score| if root_turn { score } else { 1.0 - score };
let direct = orient(mean_score(node));
let exploration =
options.exploration.max(0.0) * (log_parent / f64::from(node.visits.max(1))).sqrt();
if options.strategy == MctsStrategy::PlainUct || node.rave_visits == 0 {
return direct + exploration;
}
let visits = f64::from(node.visits);
let rave_visits = f64::from(node.rave_visits);
let equivalence = options.rave_equivalence.max(1.0);
let beta = rave_visits / (visits + rave_visits + 4.0 * visits * rave_visits / equivalence);
(direct + exploration) * (1.0 - beta) + orient(rave_mean_score(node)) * beta
}
#[derive(Clone, Copy, Default)]
struct MoveTrace {
red: [u64; 9],
blue: [u64; 9],
}
impl MoveTrace {
fn insert(&mut self, color: Color, cell: Cell) {
let bits = match color {
Color::Red => &mut self.red,
Color::Blue => &mut self.blue,
};
let index = usize::from(cell.index());
bits[index / 64] |= 1_u64 << (index % 64);
}
fn contains(self, color: Color, cell: Cell) -> bool {
let bits = match color {
Color::Red => &self.red,
Color::Blue => &self.blue,
};
let index = usize::from(cell.index());
bits[index / 64] & (1_u64 << (index % 64)) != 0
}
fn clear(&mut self) {
*self = Self::default();
}
fn prepend(&mut self, color: Color, mv: Move) {
match mv {
Move::Place(cell) => self.insert(color, cell),
Move::Swap => self.clear(),
}
}
}
struct Rollout {
score: f64,
moves: u32,
bridge_replies: u32,
trace: MoveTrace,
}
struct RolloutSummary {
moves: u32,
bridge_replies: u32,
}
#[derive(Default)]
struct SearchCounters {
knowledge_nodes: u32,
pruned_moves: u32,
must_play_nodes: u32,
virtual_connections: u32,
semi_connections: u32,
connection_search_truncated_nodes: u32,
proven_nodes: u32,
solver_propagations: u32,
}
fn coprime_step(cells: u16, random: &mut SplitMix64) -> u16 {
loop {
let candidate = 1 + random.index(usize::from(cells - 1)) as u16;
if gcd(candidate, cells) == 1 {
return candidate;
}
}
}
const fn gcd(mut left: u16, mut right: u16) -> u16 {
while right != 0 {
let remainder = left % right;
left = right;
right = remainder;
}
left
}
struct SplitMix64(u64);
impl SplitMix64 {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut value = self.0;
value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
value ^ (value >> 31)
}
fn index(&mut self, length: usize) -> usize {
debug_assert!(length > 0);
(self.next() as usize) % length
}
}
#[cfg(not(target_arch = "wasm32"))]
struct Clock {
started: Instant,
deadline: Option<Instant>,
}
#[cfg(not(target_arch = "wasm32"))]
impl Clock {
fn new(milliseconds: u32) -> Self {
let started = Instant::now();
Self {
started,
deadline: (milliseconds > 0)
.then(|| started + Duration::from_millis(u64::from(milliseconds))),
}
}
fn expired(&self) -> bool {
self.deadline
.is_some_and(|deadline| Instant::now() >= deadline)
}
fn elapsed_ms(&self) -> u32 {
self.started.elapsed().as_millis().min(u128::from(u32::MAX)) as u32
}
}
#[cfg(target_arch = "wasm32")]
#[wasm_bindgen]
extern "C" {
#[wasm_bindgen(js_namespace = performance, js_name = now)]
fn performance_now() -> f64;
}
#[cfg(target_arch = "wasm32")]
struct Clock {
started: f64,
deadline: Option<f64>,
}
#[cfg(target_arch = "wasm32")]
impl Clock {
fn new(milliseconds: u32) -> Self {
let started = performance_now();
Self {
started,
deadline: (milliseconds > 0).then(|| started + f64::from(milliseconds)),
}
}
fn expired(&self) -> bool {
self.deadline
.is_some_and(|deadline| performance_now() >= deadline)
}
fn elapsed_ms(&self) -> u32 {
(performance_now() - self.started).clamp(0.0, f64::from(u32::MAX)) as u32
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{BoardSize, SwapRule};
#[test]
fn amaf_uses_stone_color_after_the_pie_rule_swap() {
let position = Position::new(BoardSize::new(9).unwrap(), SwapRule::Enabled)
.play("e5".parse().unwrap())
.unwrap()
.play(Move::Swap)
.unwrap();
assert_eq!(position.color_to_move(), Color::Blue);
let mv: Move = "f5".parse().unwrap();
let mut random = SplitMix64(1);
let root = Node::new(position, None, None, &mut random);
let child = Node::new(position.play(mv).unwrap(), Some(0), Some(mv), &mut random);
let mut searcher = MctsSearcher {
nodes: vec![root, child],
random,
};
searcher.nodes[0].children.push(1);
let cell = mv.cell().unwrap();
let mut wrong_color = MoveTrace::default();
wrong_color.insert(Color::Red, cell);
searcher.update_rave(0, wrong_color, 1.0);
assert_eq!(searcher.nodes[1].rave_visits, 0);
let mut correct_color = MoveTrace::default();
correct_color.insert(Color::Blue, cell);
searcher.update_rave(0, correct_color, 1.0);
assert_eq!(searcher.nodes[1].rave_visits, 1);
assert_eq!(searcher.nodes[1].rave_value_sum, 1.0);
}
#[test]
fn rollout_swap_does_not_leak_amaf_evidence_across_the_color_change() {
let position = Position::new(BoardSize::new(9).unwrap(), SwapRule::Enabled)
.play("e5".parse().unwrap())
.unwrap();
let mut saw_swap = false;
let mut saw_decline = false;
for seed in 0..16 {
let mut searcher = MctsSearcher {
nodes: Vec::new(),
random: SplitMix64(seed),
};
let rollout = searcher.rollout(position, Seat::Two, None, RolloutPolicy::Random);
if rollout.moves == 81 {
saw_swap = true;
assert_eq!(rollout.trace.red, [0; 9]);
assert_eq!(rollout.trace.blue, [0; 9]);
} else {
saw_decline = true;
assert!(rollout.trace.red != [0; 9]);
assert!(rollout.trace.blue != [0; 9]);
}
}
assert!(saw_swap && saw_decline);
}
#[test]
fn save_bridge_finds_the_other_carrier() {
let moves = ["d4", "a1", "e5", "e4"].map(|mv| mv.parse().expect("valid move"));
let position =
Position::from_moves(BoardSize::new(9).unwrap(), SwapRule::Disabled, &moves).unwrap();
let attacked = "e4".parse::<Move>().unwrap().cell().unwrap();
let expected = "d5".parse::<Move>().unwrap().cell().unwrap();
let (responses, count) =
crate::patterns::bridge_responses(position, position.color_to_move(), attacked);
assert_eq!(&responses[..count], &[expected]);
}
#[test]
fn adjacent_stones_do_not_create_a_bridge_response() {
let moves = ["d4", "a1", "e4", "d5"].map(|mv| mv.parse().expect("valid move"));
let position =
Position::from_moves(BoardSize::new(9).unwrap(), SwapRule::Disabled, &moves).unwrap();
let attacked = "d5".parse::<Move>().unwrap().cell().unwrap();
let (_, count) =
crate::patterns::bridge_responses(position, position.color_to_move(), attacked);
assert_eq!(count, 0);
}
#[test]
fn tree_swap_is_an_amaf_boundary() {
let cell = Cell::new(2, 3).unwrap();
let mut trace = MoveTrace::default();
trace.insert(Color::Red, cell);
trace.prepend(Color::Blue, Move::Swap);
assert!(!trace.contains(Color::Red, cell));
trace.prepend(Color::Blue, Move::Place(cell));
assert!(trace.contains(Color::Blue, cell));
}
#[test]
fn solver_propagates_a_winning_child() {
let position = Position::new(BoardSize::for_test(3), SwapRule::Disabled);
let mut random = SplitMix64(1);
let mut root = Node::new(position, None, None, &mut random);
let mv = Move::Place(Cell::new(1, 1).unwrap());
let mut child = Node::new(position.play(mv).unwrap(), Some(0), Some(mv), &mut random);
child.proof = Some(Proof {
winner: Seat::One,
distance: Some(2),
});
root.children.push(1);
let mut searcher = MctsSearcher {
nodes: vec![root, child],
random,
};
searcher.refresh_proof(0, &mut SearchCounters::default());
assert_eq!(
searcher.nodes[0].proof,
Some(Proof {
winner: Seat::One,
distance: Some(3),
})
);
}
#[test]
fn solver_proves_a_loss_only_after_every_move_is_proven() {
let position = Position::new(BoardSize::for_test(3), SwapRule::Disabled);
let mut random = SplitMix64(1);
let mut root = Node::new(position, None, None, &mut random);
root.next_slot = position.size().cell_count();
let mut nodes = vec![root];
for (distance, mv) in position.legal_moves().into_iter().enumerate() {
let mut child = Node::new(position.play(mv).unwrap(), Some(0), Some(mv), &mut random);
child.proof = Some(Proof {
winner: Seat::Two,
distance: Some(distance as u16),
});
nodes.push(child);
let child = nodes.len() - 1;
nodes[0].children.push(child);
}
let mut searcher = MctsSearcher { nodes, random };
searcher.refresh_proof(0, &mut SearchCounters::default());
assert_eq!(
searcher.nodes[0].proof,
Some(Proof {
winner: Seat::Two,
distance: Some(9),
})
);
}
#[test]
fn solver_does_not_invent_a_distance_for_a_knowledge_proof() {
let position = Position::new(BoardSize::for_test(3), SwapRule::Disabled);
let mut random = SplitMix64(1);
let mut root = Node::new(position, None, None, &mut random);
let mv = Move::Place(Cell::new(1, 1).unwrap());
let mut child = Node::new(position.play(mv).unwrap(), Some(0), Some(mv), &mut random);
child.proof = Some(Proof {
winner: Seat::One,
distance: None,
});
root.children.push(1);
let mut searcher = MctsSearcher {
nodes: vec![root, child],
random,
};
searcher.refresh_proof(0, &mut SearchCounters::default());
assert_eq!(
searcher.nodes[0].proof,
Some(Proof {
winner: Seat::One,
distance: None,
})
);
}
#[test]
fn virtual_connection_key_ends_a_solved_root_search() {
let moves = ["b1", "c1", "a3", "c2"].map(|mv| mv.parse().unwrap());
let position =
Position::from_moves(BoardSize::for_test(3), SwapRule::Disabled, &moves).unwrap();
let report = MctsSearcher::new().search(
position,
MctsOptions {
max_simulations: 100,
soft_time_ms: 0,
knowledge_policy: KnowledgePolicy::InferiorCells { min_visits: 32 },
..MctsOptions::default()
},
);
assert_eq!(report.best_move, Some("b2".parse().unwrap()));
assert_eq!(report.proven_winner, Some(position.seat_to_move()));
assert_eq!(report.proof_distance, None);
assert_eq!(report.simulations, 1);
assert!(report.virtual_connections > 0);
assert!(report.semi_connections > 0);
}
#[test]
fn rave_blends_the_complete_uct_score() {
let position = Position::new(BoardSize::new(9).unwrap(), SwapRule::Disabled);
let mut random = SplitMix64(1);
let mut node = Node::new(position, None, None, &mut random);
node.visits = 10;
node.value_sum = 6.0;
node.rave_visits = 10;
node.rave_value_sum = 8.0;
let options = MctsOptions {
max_simulations: 1,
soft_time_ms: 0,
exploration: 1.0,
strategy: MctsStrategy::UctRave,
rave_equivalence: 40.0,
rollout_policy: RolloutPolicy::Random,
knowledge_policy: KnowledgePolicy::Disabled,
use_virtual_connections: false,
seed: 1,
};
let beta = 10.0 / (10.0 + 10.0 + 4.0 * 10.0 * 10.0 / 40.0);
let exploration = (100.0_f64.ln() / 10.0).sqrt();
let expected = (0.6 + exploration) * (1.0 - beta) + 0.8 * beta;
let actual = selection_score(&node, true, 100.0_f64.ln(), options);
assert!((actual - expected).abs() < 1e-12);
}
#[test]
fn selection_orients_direct_and_rave_scores_for_the_opponent() {
let position = Position::new(BoardSize::new(9).unwrap(), SwapRule::Disabled);
let mut random = SplitMix64(1);
let mut node = Node::new(position, None, None, &mut random);
node.visits = 10;
node.value_sum = 7.0;
node.rave_visits = 10;
node.rave_value_sum = 9.0;
let options = MctsOptions {
max_simulations: 1,
soft_time_ms: 0,
exploration: 0.0,
strategy: MctsStrategy::UctRave,
rave_equivalence: 40.0,
rollout_policy: RolloutPolicy::Random,
knowledge_policy: KnowledgePolicy::Disabled,
use_virtual_connections: false,
seed: 1,
};
let beta = 10.0 / (10.0 + 10.0 + 4.0 * 10.0 * 10.0 / 40.0);
let expected = 0.3 * (1.0 - beta) + 0.1 * beta;
let actual = selection_score(&node, false, 0.0, options);
assert!((actual - expected).abs() < 1e-12);
}
}