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)]
11pub struct SearchOptions {
13 pub max_depth: u8,
15 pub node_limit: u64,
17 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)]
66pub struct SearchReport {
68 pub best_play: Option<Play>,
70 pub equity: Equity,
72 pub depth: u8,
74 pub nodes: u64,
76 pub chance_nodes: u64,
78 pub tt_hits: u64,
80 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 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 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 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}