ai_othello/
search.rs

1use crate::{
2    Evaluation, EvaluationProfile, GameResult, Move, MoveList, Position, Square, evaluate,
3};
4
5const INFINITY: i32 = 40_000;
6const TERMINAL: i32 = 30_000;
7
8/// Search score with exact results kept outside the heuristic band.
9#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
10pub struct Score(i32);
11
12impl Score {
13    pub const fn raw(self) -> i32 {
14        self.0
15    }
16
17    pub const fn kind(self) -> ScoreKind {
18        if self.0 >= TERMINAL {
19            ScoreKind::Win {
20                margin: (self.0 - TERMINAL) as u8,
21            }
22        } else if self.0 <= -TERMINAL {
23            ScoreKind::Loss {
24                margin: (-self.0 - TERMINAL) as u8,
25            }
26        } else {
27            ScoreKind::Estimate(self.0)
28        }
29    }
30
31    const fn negated(self) -> Self {
32        Self(-self.0)
33    }
34}
35
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37pub enum ScoreKind {
38    Win { margin: u8 },
39    Draw,
40    Loss { margin: u8 },
41    Estimate(i32),
42}
43
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45pub struct SearchConfig {
46    pub depth: u8,
47    pub evaluator: EvaluationProfile,
48    pub exact_endgame_empties: u8,
49}
50
51impl SearchConfig {
52    pub const fn fixed_depth(depth: u8, evaluator: EvaluationProfile) -> Self {
53        Self {
54            depth,
55            evaluator,
56            exact_endgame_empties: 0,
57        }
58    }
59}
60
61/// A named search depth and exact-endgame threshold for interactive play.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub struct SearchPreset {
64    pub name: &'static str,
65    pub depth: u8,
66    pub exact_endgame_empties: u8,
67}
68
69impl SearchPreset {
70    pub const fn config(self, evaluator: EvaluationProfile) -> SearchConfig {
71        SearchConfig {
72            depth: self.depth,
73            evaluator,
74            exact_endgame_empties: self.exact_endgame_empties,
75        }
76    }
77}
78
79/// The built-in strength ladder, ordered from least to most search work.
80pub const SEARCH_PRESETS: [SearchPreset; 6] = [
81    SearchPreset {
82        name: "beginner",
83        depth: 1,
84        exact_endgame_empties: 0,
85    },
86    SearchPreset {
87        name: "easy",
88        depth: 2,
89        exact_endgame_empties: 0,
90    },
91    SearchPreset {
92        name: "medium",
93        depth: 4,
94        exact_endgame_empties: 2,
95    },
96    SearchPreset {
97        name: "hard",
98        depth: 5,
99        exact_endgame_empties: 4,
100    },
101    SearchPreset {
102        name: "expert",
103        depth: 6,
104        exact_endgame_empties: 8,
105    },
106    SearchPreset {
107        name: "maximum",
108        depth: 7,
109        exact_endgame_empties: 8,
110    },
111];
112
113/// Finds a built-in strength preset by its lowercase name.
114pub fn search_preset(name: &str) -> Option<SearchPreset> {
115    SEARCH_PRESETS
116        .iter()
117        .copied()
118        .find(|preset| preset.name == name)
119}
120
121#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
122pub struct SearchStats {
123    pub nodes: u64,
124    pub leaves: u64,
125    pub cutoffs: u64,
126    pub passes: u64,
127    pub exact_nodes: u64,
128    pub max_ply: u8,
129}
130
131#[derive(Debug, Clone, PartialEq, Eq)]
132pub struct Candidate {
133    pub mv: Move,
134    pub score: Score,
135    pub nodes: u64,
136    pub cutoffs: u64,
137    pub flipped: u64,
138}
139
140/// Complete result of one search.
141#[derive(Debug, Clone, PartialEq, Eq)]
142pub struct SearchReport {
143    pub config: SearchConfig,
144    pub best_move: Option<Move>,
145    pub score: Score,
146    pub exact: bool,
147    pub principal_variation: Vec<Move>,
148    pub candidates: Vec<Candidate>,
149    pub evaluation: Evaluation,
150    pub stats: SearchStats,
151}
152
153#[derive(Debug, Clone, Copy)]
154struct Line {
155    moves: [Move; 64],
156    len: u8,
157}
158
159impl Default for Line {
160    fn default() -> Self {
161        Self {
162            moves: [Move::Pass; 64],
163            len: 0,
164        }
165    }
166}
167
168impl Line {
169    fn prepend(mv: Move, child: Self) -> Self {
170        let mut line = Self::default();
171        line.moves[0] = mv;
172        let child_len = usize::from(child.len).min(63);
173        if child_len > 0 {
174            line.moves[1..=child_len].copy_from_slice(&child.moves[..child_len]);
175        }
176        line.len = child_len as u8 + 1;
177        line
178    }
179
180    fn to_vec(self) -> Vec<Move> {
181        self.moves[..usize::from(self.len)].to_vec()
182    }
183}
184
185#[derive(Debug, Clone, Copy)]
186struct NodeResult {
187    score: Score,
188    line: Line,
189}
190
191struct Searcher<F: Fn() -> bool> {
192    config: SearchConfig,
193    stats: SearchStats,
194    should_stop: F,
195    stopped: bool,
196}
197
198impl<F: Fn() -> bool> Searcher<F> {
199    fn stop_requested(&mut self) -> bool {
200        if self.stopped || (self.should_stop)() {
201            self.stopped = true;
202        }
203        self.stopped
204    }
205
206    fn node(
207        &mut self,
208        position: &mut Position,
209        depth: u8,
210        ply: u8,
211        mut alpha: Score,
212        beta: Score,
213    ) -> Option<NodeResult> {
214        if self.stop_requested() {
215            return None;
216        }
217        self.stats.nodes += 1;
218        self.stats.max_ply = self.stats.max_ply.max(ply);
219        if position.empty_count() <= self.config.exact_endgame_empties {
220            self.stats.exact_nodes += 1;
221        }
222        if let Some(score) = terminal_score(*position) {
223            self.stats.leaves += 1;
224            return Some(NodeResult {
225                score,
226                line: Line::default(),
227            });
228        }
229        let exact = position.empty_count() <= self.config.exact_endgame_empties;
230        if depth == 0 && !exact {
231            self.stats.leaves += 1;
232            return Some(NodeResult {
233                score: Score(evaluate(*position, self.config.evaluator).total),
234                line: Line::default(),
235            });
236        }
237
238        let mut best = Score(-INFINITY);
239        let mut best_move = None;
240        let mut best_line = Line::default();
241        for mv in ordered_moves(*position) {
242            if mv == Move::Pass {
243                self.stats.passes += 1;
244            }
245            let undo = position
246                .make_move(mv)
247                .expect("generated moves must be legal");
248            let next_depth = if mv == Move::Pass {
249                depth
250            } else {
251                depth.saturating_sub(1)
252            };
253            let child = self.node(
254                position,
255                next_depth,
256                ply + 1,
257                beta.negated(),
258                alpha.negated(),
259            );
260            position.unmake_move(undo);
261            let child = child?;
262            let score = child.score.negated();
263            if score > best || (score == best && prefer(mv, best_move)) {
264                best = score;
265                best_move = Some(mv);
266                best_line = Line::prepend(mv, child.line);
267            }
268            alpha = alpha.max(score);
269            if alpha >= beta {
270                self.stats.cutoffs += 1;
271                break;
272            }
273        }
274        Some(NodeResult {
275            score: best,
276            line: best_line,
277        })
278    }
279}
280
281/// Searches `position` to the configured depth.
282pub fn search(position: Position, config: SearchConfig) -> SearchReport {
283    search_until(position, config, || false)
284        .expect("a search with a constant false stop signal must complete")
285}
286
287/// Search a fixed depth while polling a cooperative stop signal at node entry.
288/// A stopped partial result is discarded.
289pub fn search_until<F: Fn() -> bool>(
290    position: Position,
291    config: SearchConfig,
292    should_stop: F,
293) -> Option<SearchReport> {
294    let exact = position.empty_count() <= config.exact_endgame_empties;
295    let evaluation = evaluate(position, config.evaluator);
296    let mut searcher = Searcher {
297        config,
298        stats: SearchStats {
299            nodes: 1,
300            ..SearchStats::default()
301        },
302        should_stop,
303        stopped: false,
304    };
305    if searcher.stop_requested() {
306        return None;
307    }
308    if let Some(score) = terminal_score(position) {
309        searcher.stats.leaves = 1;
310        return Some(SearchReport {
311            config,
312            best_move: None,
313            score,
314            exact: true,
315            principal_variation: Vec::new(),
316            candidates: Vec::new(),
317            evaluation,
318            stats: searcher.stats,
319        });
320    }
321    if config.depth == 0 && !exact {
322        searcher.stats.leaves = 1;
323        return Some(SearchReport {
324            config,
325            best_move: None,
326            score: Score(evaluation.total),
327            exact: false,
328            principal_variation: Vec::new(),
329            candidates: Vec::new(),
330            evaluation,
331            stats: searcher.stats,
332        });
333    }
334
335    let mut best = Score(-INFINITY);
336    let mut best_move = None;
337    let mut best_line = Line::default();
338    let mut candidates = Vec::new();
339    for mv in ordered_moves(position) {
340        if searcher.stop_requested() {
341            return None;
342        }
343        if mv == Move::Pass {
344            searcher.stats.passes += 1;
345        }
346        let before_nodes = searcher.stats.nodes;
347        let before_cutoffs = searcher.stats.cutoffs;
348        let flipped = mv.square().map_or(0, |square| position.flips_for(square));
349        let mut child_position = position;
350        child_position
351            .make_move(mv)
352            .expect("generated moves must be legal");
353        let next_depth = if mv == Move::Pass {
354            config.depth
355        } else {
356            config.depth.saturating_sub(1)
357        };
358        let child = searcher.node(
359            &mut child_position,
360            next_depth,
361            1,
362            Score(-INFINITY),
363            Score(INFINITY),
364        )?;
365        let score = child.score.negated();
366        candidates.push(Candidate {
367            mv,
368            score,
369            nodes: searcher.stats.nodes - before_nodes,
370            cutoffs: searcher.stats.cutoffs - before_cutoffs,
371            flipped,
372        });
373        if score > best || (score == best && prefer(mv, best_move)) {
374            best = score;
375            best_move = Some(mv);
376            best_line = Line::prepend(mv, child.line);
377        }
378    }
379
380    Some(SearchReport {
381        config,
382        best_move,
383        score: best,
384        exact,
385        principal_variation: best_line.to_vec(),
386        candidates,
387        evaluation,
388        stats: searcher.stats,
389    })
390}
391
392fn terminal_score(position: Position) -> Option<Score> {
393    match position.result() {
394        GameResult::Ongoing => None,
395        GameResult::Draw { .. } => Some(Score(0)),
396        GameResult::Win {
397            winner,
398            black,
399            white,
400        } => {
401            let margin = i32::from(black.abs_diff(white));
402            if winner == position.side_to_move() {
403                Some(Score(TERMINAL + margin))
404            } else {
405                Some(Score(-TERMINAL - margin))
406            }
407        }
408    }
409}
410
411fn ordered_moves(position: Position) -> MoveList {
412    const CORNERS: [u8; 4] = [0, 7, 56, 63];
413    let legal = position.legal_moves();
414    if legal.as_slice() == [Move::Pass] {
415        return legal;
416    }
417    let mut ordered = MoveList::default();
418    for index in CORNERS {
419        let mv = Move::Place(Square::new(index));
420        if legal.as_slice().contains(&mv) {
421            ordered.push(mv);
422        }
423    }
424    for mv in legal {
425        if !ordered.as_slice().contains(&mv) {
426            ordered.push(mv);
427        }
428    }
429    ordered
430}
431
432fn prefer(candidate: Move, current: Option<Move>) -> bool {
433    current.is_none_or(|mv| candidate < mv)
434}
ai_othello/search.rs

ai_othello/
search.rs
