Skip to main content

ai_backgammon/
search.rs

1use crate::{DICE_OUTCOMES, Dice, Equity, Play, PlayOutcome, Position, evaluate_position};
2#[cfg(not(target_arch = "wasm32"))]
3use std::time::{Duration, Instant};
4
5#[cfg(all(target_arch = "wasm32", feature = "wasm"))]
6use wasm_bindgen::prelude::*;
7
8const DEFAULT_TT_ENTRIES: usize = 1 << 15;
9
10#[derive(Clone, Copy, Debug, Eq, PartialEq)]
11/// Limits for one iterative-deepening expectimax search.
12pub struct SearchOptions {
13    /// Maximum number of complete future checker turns.
14    pub max_depth: u8,
15    /// Maximum decision nodes; zero is treated as one to preserve a fallback.
16    pub node_limit: u64,
17    /// Soft wall-clock limit in milliseconds; zero disables it.
18    pub soft_time_ms: u32,
19}
20
21impl Default for SearchOptions {
22    fn default() -> Self {
23        SEARCH_PRESETS[SEARCH_PRESETS.len() - 1].options
24    }
25}
26
27#[derive(Clone, Copy, Debug, Eq, PartialEq)]
28pub struct SearchPreset {
29    pub name: &'static str,
30    pub options: SearchOptions,
31}
32
33pub const SEARCH_PRESETS: [SearchPreset; 6] = [
34    preset("beginner", 0, 1, 20),
35    preset("easy", 1, 1_000, 50),
36    preset("medium", 2, 5_000, 120),
37    preset("hard", 2, 20_000, 300),
38    preset("expert", 3, 80_000, 650),
39    preset("maximum", 4, 250_000, 1_000),
40];
41
42const fn preset(
43    name: &'static str,
44    max_depth: u8,
45    node_limit: u64,
46    soft_time_ms: u32,
47) -> SearchPreset {
48    SearchPreset {
49        name,
50        options: SearchOptions {
51            max_depth,
52            node_limit,
53            soft_time_ms,
54        },
55    }
56}
57
58pub fn search_preset(name: &str) -> Option<SearchPreset> {
59    SEARCH_PRESETS
60        .iter()
61        .copied()
62        .find(|preset| preset.name == name)
63}
64
65#[derive(Clone, Debug, PartialEq)]
66/// The last fully completed iteration and a legal fallback if search stopped early.
67pub struct SearchReport {
68    /// Selected complete play, or `None` when the supplied position is terminal.
69    pub best_play: Option<Play>,
70    /// Outcome probabilities from the root side-to-move's perspective.
71    pub equity: Equity,
72    /// Deepest fully completed iteration.
73    pub depth: u8,
74    /// Visited decision nodes.
75    pub nodes: u64,
76    /// Enumerated dice outcomes.
77    pub chance_nodes: u64,
78    /// Exact-depth transposition-table hits.
79    pub tt_hits: u64,
80    /// Whether a node, time, or caller cancellation limit interrupted search.
81    pub stopped: bool,
82}
83
84#[derive(Clone, Copy, Debug)]
85struct Entry {
86    key: u64,
87    depth: u8,
88    equity: Equity,
89    occupied: bool,
90}
91
92impl Default for Entry {
93    fn default() -> Self {
94        Self {
95            key: 0,
96            depth: 0,
97            equity: Equity::zero(),
98            occupied: false,
99        }
100    }
101}
102
103pub struct Searcher {
104    table: Vec<Entry>,
105    nodes: u64,
106    node_limit: u64,
107    chance_nodes: u64,
108    tt_hits: u64,
109    stopped: bool,
110    deadline: Deadline,
111}
112
113impl Default for Searcher {
114    fn default() -> Self {
115        Self::new()
116    }
117}
118
119impl Searcher {
120    pub fn new() -> Self {
121        Self::with_table_entries(DEFAULT_TT_ENTRIES)
122    }
123
124    /// Creates a searcher with a fixed-size table; zero disables the table.
125    pub fn with_table_entries(entries: usize) -> Self {
126        Self {
127            table: vec![Entry::default(); entries],
128            nodes: 0,
129            node_limit: 0,
130            chance_nodes: 0,
131            tt_hits: 0,
132            stopped: false,
133            deadline: Deadline::disabled(),
134        }
135    }
136
137    /// Searches complete plays for known `dice` using iterative deepening.
138    pub fn search(
139        &mut self,
140        position: Position,
141        dice: Dice,
142        options: SearchOptions,
143    ) -> SearchReport {
144        self.search_until(position, dice, options, || false)
145    }
146
147    /// Searches until a normal limit or a caller-provided cancellation signal fires.
148    pub fn search_until<F: Fn() -> bool>(
149        &mut self,
150        position: Position,
151        dice: Dice,
152        options: SearchOptions,
153        should_stop: F,
154    ) -> SearchReport {
155        self.nodes = 0;
156        self.node_limit = options.node_limit.max(1);
157        self.chance_nodes = 0;
158        self.tt_hits = 0;
159        self.stopped = false;
160        self.deadline = Deadline::after(options.soft_time_ms);
161        self.table.fill(Entry::default());
162
163        if position.game_outcome().is_some() {
164            return self.report(None, evaluate_position(position), 0);
165        }
166
167        let outcomes = position.legal_outcomes(dice);
168        let Some(fallback) = outcomes.first() else {
169            return self.report(None, evaluate_position(position), 0);
170        };
171        let mut best_play = fallback.representative().clone();
172        let mut best_equity = evaluate_position(fallback.position()).reversed();
173        let mut completed_depth = 0;
174
175        for depth in 1..=options.max_depth {
176            if self.should_stop(&should_stop) {
177                break;
178            }
179            let Some((play, equity)) = self.search_root(position, dice, depth, &should_stop) else {
180                break;
181            };
182            best_play = play;
183            best_equity = equity;
184            completed_depth = depth;
185            if best_equity.expected_points().abs() == 3.0 {
186                break;
187            }
188        }
189
190        self.report(Some(best_play), best_equity, completed_depth)
191    }
192
193    fn search_root<F: Fn() -> bool>(
194        &mut self,
195        position: Position,
196        dice: Dice,
197        depth: u8,
198        should_stop: &F,
199    ) -> Option<(Play, Equity)> {
200        let outcomes = ordered_outcomes(position, dice);
201        let mut best: Option<(Play, Equity)> = None;
202        for outcome in outcomes {
203            if !self.visit(should_stop) {
204                return None;
205            }
206            let equity = self
207                .chance_value(outcome.position(), depth - 1, should_stop)?
208                .reversed();
209            if better(equity, outcome.representative(), best.as_ref()) {
210                best = Some((outcome.representative().clone(), equity));
211            }
212        }
213        best
214    }
215
216    fn chance_value<F: Fn() -> bool>(
217        &mut self,
218        position: Position,
219        depth: u8,
220        should_stop: &F,
221    ) -> Option<Equity> {
222        let key = position.hash();
223        if let Some(equity) = self.probe(key, depth) {
224            return Some(equity);
225        }
226        if position.game_outcome().is_some() || depth == 0 {
227            let equity = evaluate_position(position);
228            self.store(key, depth, equity);
229            return Some(equity);
230        }
231
232        let mut total = Equity::zero();
233        for outcome in DICE_OUTCOMES {
234            if self.should_stop(should_stop) {
235                return None;
236            }
237            self.chance_nodes += 1;
238            let equity = self.decision_value(position, outcome.dice, depth, should_stop)?;
239            total.add_weighted(equity, f32::from(outcome.weight) / 36.0);
240        }
241        self.store(key, depth, total);
242        Some(total)
243    }
244
245    fn decision_value<F: Fn() -> bool>(
246        &mut self,
247        position: Position,
248        dice: Dice,
249        depth: u8,
250        should_stop: &F,
251    ) -> Option<Equity> {
252        let mut best: Option<(Play, Equity)> = None;
253        for outcome in ordered_outcomes(position, dice) {
254            if !self.visit(should_stop) {
255                return None;
256            }
257            let equity = self
258                .chance_value(outcome.position(), depth - 1, should_stop)?
259                .reversed();
260            if better(equity, outcome.representative(), best.as_ref()) {
261                best = Some((outcome.representative().clone(), equity));
262            }
263        }
264        best.map(|(_, equity)| equity)
265    }
266
267    fn visit<F: Fn() -> bool>(&mut self, should_stop: &F) -> bool {
268        if self.nodes >= self.node_limit || self.should_stop(should_stop) {
269            self.stopped = true;
270            return false;
271        }
272        self.nodes += 1;
273        true
274    }
275
276    fn should_stop<F: Fn() -> bool>(&mut self, should_stop: &F) -> bool {
277        if self.stopped || self.deadline.expired() || should_stop() {
278            self.stopped = true;
279            true
280        } else {
281            false
282        }
283    }
284
285    fn probe(&mut self, key: u64, depth: u8) -> Option<Equity> {
286        if self.table.is_empty() {
287            return None;
288        }
289        let entry = self.table[key as usize % self.table.len()];
290        if entry.occupied && entry.key == key && entry.depth == depth {
291            self.tt_hits += 1;
292            Some(entry.equity)
293        } else {
294            None
295        }
296    }
297
298    fn store(&mut self, key: u64, depth: u8, equity: Equity) {
299        if self.table.is_empty() {
300            return;
301        }
302        let index = key as usize % self.table.len();
303        self.table[index] = Entry {
304            key,
305            depth,
306            equity,
307            occupied: true,
308        };
309    }
310
311    fn report(&self, best_play: Option<Play>, equity: Equity, depth: u8) -> SearchReport {
312        SearchReport {
313            best_play,
314            equity,
315            depth,
316            nodes: self.nodes,
317            chance_nodes: self.chance_nodes,
318            tt_hits: self.tt_hits,
319            stopped: self.stopped,
320        }
321    }
322}
323
324fn ordered_outcomes(position: Position, dice: Dice) -> Vec<PlayOutcome> {
325    let mut outcomes = position.legal_outcomes(dice);
326    outcomes.sort_by(|left, right| {
327        evaluate_position(right.position())
328            .reversed()
329            .expected_points()
330            .total_cmp(
331                &evaluate_position(left.position())
332                    .reversed()
333                    .expected_points(),
334            )
335            .then_with(|| left.representative().cmp(right.representative()))
336    });
337    outcomes
338}
339
340fn better(equity: Equity, play: &Play, best: Option<&(Play, Equity)>) -> bool {
341    let Some((best_play, best_equity)) = best else {
342        return true;
343    };
344    equity.expected_points() > best_equity.expected_points()
345        || (equity.expected_points() == best_equity.expected_points() && play < best_play)
346}
347
348#[cfg(not(target_arch = "wasm32"))]
349struct Deadline(Option<Instant>);
350
351#[cfg(not(target_arch = "wasm32"))]
352impl Deadline {
353    fn disabled() -> Self {
354        Self(None)
355    }
356
357    fn after(milliseconds: u32) -> Self {
358        Self(
359            (milliseconds > 0)
360                .then(|| Instant::now() + Duration::from_millis(u64::from(milliseconds))),
361        )
362    }
363
364    fn expired(&self) -> bool {
365        self.0.is_some_and(|deadline| Instant::now() >= deadline)
366    }
367}
368
369#[cfg(all(target_arch = "wasm32", feature = "wasm"))]
370#[wasm_bindgen]
371extern "C" {
372    #[wasm_bindgen(js_namespace = performance, js_name = now)]
373    fn performance_now() -> f64;
374}
375
376#[cfg(all(target_arch = "wasm32", feature = "wasm"))]
377struct Deadline(Option<f64>);
378
379#[cfg(all(target_arch = "wasm32", feature = "wasm"))]
380impl Deadline {
381    fn disabled() -> Self {
382        Self(None)
383    }
384
385    fn after(milliseconds: u32) -> Self {
386        Self((milliseconds > 0).then(|| performance_now() + f64::from(milliseconds)))
387    }
388
389    fn expired(&self) -> bool {
390        self.0.is_some_and(|deadline| performance_now() >= deadline)
391    }
392}
393
394#[cfg(all(target_arch = "wasm32", not(feature = "wasm")))]
395struct Deadline;
396
397#[cfg(all(target_arch = "wasm32", not(feature = "wasm")))]
398impl Deadline {
399    const fn disabled() -> Self {
400        Self
401    }
402
403    const fn after(_milliseconds: u32) -> Self {
404        Self
405    }
406
407    const fn expired(&self) -> bool {
408        false
409    }
410}