shuyi_core/bots/
rollout.rs

1//! A rollout bot over any [`Determinize`] game: flat Monte Carlo.
2//!
3//! [`Rollout`] tries each of a few good-looking commands many times on
4//! copies of the game where the luck and the hidden things are redrawn
5//! ([`Determinize`]), plays each copy on a little way with simple players
6//! ([`Playout`]), and picks the command whose copies ended best
7//! ([`Evaluate`]). It searches one level, its own next command, so it
8//! suits games that branch too much for a tree of every side's replies.
9//!
10//! Everything is in integers: the scores, their means and the softmax that
11//! picks (base 2, the temperature in points). It thinks in work units,
12//! never time: a unit is one command applied to a copy. Its own randomness
13//! comes from its seed, drawn only at a decision's start and its end, so
14//! how the work is sliced ([`RolloutSearch::advance`]) never changes the
15//! command (ADR-0027).
16
17use alloc::vec::Vec;
18
19use serde::{Deserialize, Serialize};
20
21use super::Bot;
22use super::Sides;
23use super::determinize::{Determinize, Evaluate};
24use crate::rng::SimRng;
25
26/// The game's list of candidates, from the real state's
27/// [`legal_commands`](crate::TurnRules::legal_commands): it may drop commands
28/// (ones the game never wants tried) and puts the most promising first.
29/// It returns only commands from the list it is given.
30pub trait Order<R: Sides> {
31    /// `commands` (the legal commands of `rules`), dropped and reordered.
32    fn order(&mut self, rules: &R, commands: Vec<R::Command>) -> Vec<R::Command>;
33}
34
35impl<R: Sides, F: FnMut(&R, Vec<R::Command>) -> Vec<R::Command>> Order<R> for F {
36    fn order(&mut self, rules: &R, commands: Vec<R::Command>) -> Vec<R::Command> {
37        self(rules, commands)
38    }
39}
40
41/// The legal commands as the game lists them.
42#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
43pub struct Unordered;
44
45impl<R: Sides> Order<R> for Unordered {
46    fn order(&mut self, _: &R, commands: Vec<R::Command>) -> Vec<R::Command> {
47        commands
48    }
49}
50
51/// How a copy is played on after the candidate, for whichever side is to
52/// move: a game matches on [`side_to_move`](Sides::side_to_move) to use
53/// its baseline for one side and its enemy mind for another.
54///
55/// Its randomness, if any, comes from the copy (whose luck was redrawn),
56/// so it needs no seed of its own. Every [`Bot`] is one.
57pub trait Playout<R: Sides> {
58    /// The next command in the copy `rules`, which is not over.
59    fn command(&mut self, rules: &R) -> R::Command;
60}
61
62impl<R: Sides, B: Bot<R>> Playout<R> for B {
63    fn command(&mut self, rules: &R) -> R::Command {
64        self.choose(rules)
65    }
66}
67
68/// When a playout stops, short of the game's end.
69#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
70pub enum Horizon {
71    /// After the side to move has changed this many times (the
72    /// candidate's own change included).
73    Sides(u32),
74    /// After [`Sides::turn`] has gone up this many.
75    Turns(u32),
76}
77
78/// How a [`Rollout`] bot thinks: data, so a persona's settings can be a
79/// file. Build it with [`RolloutSettings::new`] (ADR-0039).
80#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
81#[non_exhaustive]
82pub struct RolloutSettings {
83    /// How many of the ordered commands are tried, from the first. 0
84    /// counts as 1.
85    pub candidates: u32,
86    /// How many copies each candidate is played out on. 0 counts as 1.
87    pub samples: u32,
88    /// When a playout stops.
89    pub horizon: Horizon,
90    /// The most commands a playout applies after the candidate, so a
91    /// playout player that never ends its side's move can't run forever.
92    pub commands: u32,
93    /// How far from the best the pick may stray, in points: a candidate
94    /// this many points below the best is half as likely. 0 always picks
95    /// the best.
96    pub temperature: u32,
97}
98
99impl RolloutSettings {
100    /// The first `candidates` commands tried, each played out on `samples`
101    /// copies until `horizon`, at most `commands` commands a playout, the
102    /// pick straying by `temperature`.
103    #[must_use]
104    pub const fn new(
105        candidates: u32,
106        samples: u32,
107        horizon: Horizon,
108        commands: u32,
109        temperature: u32,
110    ) -> Self {
111        Self {
112            candidates,
113            samples,
114            horizon,
115            commands,
116            temperature,
117        }
118    }
119}
120
121/// A computer player that plans on copies of the game: flat Monte Carlo
122/// (the module's docs).
123///
124/// A decision does at most `candidates × samples × (commands + 1)` units
125/// of work, a unit being one command applied to a copy.
126#[derive(Debug, Clone)]
127pub struct Rollout<O, P, E> {
128    order: O,
129    playout: P,
130    eval: E,
131    settings: RolloutSettings,
132    rng: SimRng,
133}
134
135impl<O, P, E> Rollout<O, P, E> {
136    /// A rollout bot whose candidates come from `order`, played out by
137    /// `playout` and scored by `eval`, thinking as `settings` says. Its
138    /// choices follow from `seed`.
139    pub fn new(order: O, playout: P, eval: E, settings: RolloutSettings, seed: u64) -> Self {
140        Self {
141            order,
142            playout,
143            eval,
144            settings,
145            rng: SimRng::new(seed),
146        }
147    }
148
149    /// How it thinks.
150    pub fn settings(&self) -> RolloutSettings {
151        self.settings
152    }
153
154    /// Starts a decision in `rules`, which is not over: its candidates are
155    /// listed and its seeds drawn. [`RolloutSearch::advance`] does the
156    /// work.
157    ///
158    /// # Panics
159    ///
160    /// If the game lists no legal command, or the order drops them all.
161    pub fn search<R>(&mut self, rules: &R) -> RolloutSearch<'_, R, O, P, E>
162    where
163        R: Determinize,
164        R::Command: Clone + PartialEq,
165        O: Order<R>,
166        P: Playout<R>,
167        E: Evaluate<R>,
168    {
169        let legal = rules.legal_commands();
170        let mut candidates = self.order.order(rules, legal.clone());
171        candidates.truncate(at_least_one(self.settings.candidates));
172        assert!(
173            !candidates.is_empty(),
174            "no command to choose from: the game lists none, or its order dropped them all"
175        );
176        let seeds = draw_seeds(&mut self.rng, self.settings.samples);
177        let mut playouts: Vec<(usize, u64)> = (0..candidates.len())
178            .flat_map(|candidate| seeds.iter().map(move |&seed| (candidate, seed)))
179            .collect();
180        playouts.reverse();
181        RolloutSearch {
182            root: rules.clone(),
183            side: rules.side_to_move(),
184            legal,
185            sums: alloc::vec![0; candidates.len()],
186            candidates,
187            seeds,
188            playouts,
189            playing: None,
190            chosen: None,
191            bot: self,
192        }
193    }
194}
195
196impl<R, O, P, E> Bot<R> for Rollout<O, P, E>
197where
198    R: Determinize,
199    R::Command: Clone + PartialEq,
200    O: Order<R>,
201    P: Playout<R>,
202    E: Evaluate<R>,
203{
204    /// The command whose playouts ended best (or, at a temperature, one
205    /// picked by the softmax).
206    ///
207    /// # Panics
208    ///
209    /// As [`Rollout::search`] and [`RolloutSearch::advance`] do.
210    fn choose(&mut self, rules: &R) -> R::Command {
211        match self.search(rules).work(u64::MAX) {
212            Progress::Chosen(command) => command,
213            Progress::Working => panic!("a decision took more than u64::MAX units"),
214        }
215    }
216}
217
218/// A decision of a [`Rollout`] bot under way: its loop state in a value,
219/// so the work can be split over many calls (frames, later).
220pub struct RolloutSearch<'a, R: Sides, O, P, E> {
221    bot: &'a mut Rollout<O, P, E>,
222    /// The state the decision began in.
223    root: R,
224    side: R::Side,
225    /// The root's legal commands, which every copy must list too.
226    legal: Vec<R::Command>,
227    candidates: Vec<R::Command>,
228    seeds: Vec<u64>,
229    /// Each candidate's sum of scores.
230    sums: Vec<i64>,
231    /// The playouts still to start, as a candidate and a seed, the next
232    /// one last: each candidate on every seed, in order. Each is taken
233    /// off as it starts, so the search keeps no count that could run past
234    /// them.
235    playouts: Vec<(usize, u64)>,
236    playing: Option<Playing<R>>,
237    chosen: Option<R::Command>,
238}
239
240/// A playout under way.
241struct Playing<R: Sides> {
242    candidate: usize,
243    copy: R,
244    side: R::Side,
245    /// How many times the side to move has changed since the root.
246    changes: u32,
247    /// The commands applied after the candidate (refused ones included).
248    played: u32,
249}
250
251impl<R, O, P, E> RolloutSearch<'_, R, O, P, E>
252where
253    R: Determinize,
254    R::Command: Clone + PartialEq,
255    O: Order<R>,
256    P: Playout<R>,
257    E: Evaluate<R>,
258{
259    /// Does at most `units` units of work (commands applied to copies) and
260    /// returns the chosen command once the decision is made, `None` while
261    /// it is working. Once made, it returns the same command again.
262    ///
263    /// # Panics
264    ///
265    /// With a message naming `determinize` when a copy lists other
266    /// commands than the real state, or refuses a candidate: a bug in the
267    /// game's [`Determinize::determinize`].
268    pub fn advance(&mut self, units: u32) -> Option<R::Command> {
269        match self.work(u64::from(units)) {
270            Progress::Chosen(command) => Some(command),
271            Progress::Working => None,
272        }
273    }
274
275    /// [`advance`](Self::advance), on as many as `u64::MAX` units: a
276    /// [`Progress`], which no step can fake, so a search that stopped
277    /// moving fails at once instead of spinning.
278    fn work(&mut self, units: u64) -> Progress<R::Command> {
279        let mut left = units;
280        loop {
281            if let Some(chosen) = &self.chosen {
282                return Progress::Chosen(chosen.clone());
283            }
284            let Some(mut playing) = self.playing.take() else {
285                if left == 0 && !self.playouts.is_empty() {
286                    return Progress::Working;
287                }
288                if let Some((candidate, seed)) = self.playouts.pop() {
289                    left -= 1;
290                    self.playing = Some(self.start(candidate, seed));
291                } else {
292                    self.chosen = Some(self.pick());
293                }
294                continue;
295            };
296            if self.over(&playing) {
297                self.finish(&playing);
298            } else if left == 0 {
299                self.playing = Some(playing);
300                return Progress::Working;
301            } else {
302                left -= 1;
303                let command = self.bot.playout.command(&playing.copy);
304                playing.played += 1;
305                if playing.copy.apply(&command).is_ok() {
306                    note_side(&mut playing);
307                    self.playing = Some(playing);
308                } else {
309                    self.finish(&playing);
310                }
311            }
312        }
313    }
314
315    /// A playout of `candidate` on `seed`: a copy from `determinize`,
316    /// checked, with its candidate applied.
317    fn start(&self, candidate: usize, seed: u64) -> Playing<R> {
318        let mut copy = checked_copy(&self.root, self.side, &self.legal, seed);
319        apply_candidate(&mut copy, &self.candidates[candidate], candidate, seed);
320        let mut playing = Playing {
321            candidate,
322            copy,
323            side: self.side,
324            changes: 0,
325            played: 0,
326        };
327        note_side(&mut playing);
328        playing
329    }
330
331    /// Whether `playing` is done: the game ended, the horizon is reached,
332    /// or it applied its `commands`.
333    fn over(&self, playing: &Playing<R>) -> bool {
334        let settings = self.bot.settings;
335        let reached = match settings.horizon {
336            Horizon::Sides(changes) => playing.changes >= changes,
337            Horizon::Turns(turns) => playing.copy.turn().saturating_sub(self.root.turn()) >= turns,
338        };
339        reached || playing.played >= settings.commands || playing.copy.outcome().is_some()
340    }
341
342    /// Scores a finished playout into its candidate's sum.
343    fn finish(&mut self, playing: &Playing<R>) {
344        let score = self.bot.eval.score(&self.root, &playing.copy, self.side);
345        let sum = &mut self.sums[playing.candidate];
346        *sum = sum.saturating_add(i64::from(score));
347    }
348
349    /// The decision: each candidate's mean score, then the pick.
350    fn pick(&mut self) -> R::Command {
351        let samples = i64::try_from(self.seeds.len()).unwrap_or(i64::MAX);
352        let means: Vec<i64> = self
353            .sums
354            .iter()
355            .map(|sum| sum.div_euclid(samples))
356            .collect();
357        let temperature = self.bot.settings.temperature;
358        let index = pick(&means, temperature, &mut self.bot.rng);
359        self.candidates[index].clone()
360    }
361}
362
363/// Counts a change of the side to move in `playing`.
364fn note_side<R: Sides>(playing: &mut Playing<R>) {
365    let side = playing.copy.side_to_move();
366    if side != playing.side {
367        playing.side = side;
368        playing.changes = playing.changes.saturating_add(1);
369    }
370}
371
372/// How far a search got on the units it was given. It has no default,
373/// so a mutant of a search's step can't return one and leave the search
374/// spinning in place.
375pub(super) enum Progress<C> {
376    /// The units ran out first.
377    Working,
378    /// The decision is made.
379    Chosen(C),
380}
381
382/// `samples` seeds for a decision's copies (at least 1), each two draws
383/// from `rng`, high half first.
384pub(super) fn draw_seeds(rng: &mut SimRng, samples: u32) -> Vec<u64> {
385    (0..at_least_one(samples))
386        .map(|_| {
387            let high = u64::from(rng.next_u32());
388            let low = u64::from(rng.next_u32());
389            (high << 32) + low
390        })
391        .collect()
392}
393
394/// `root`'s copy for `side` from `seed`, checked to list `legal` (the
395/// root's legal commands) with `side` to move.
396///
397/// # Panics
398///
399/// With a message naming `determinize` when it doesn't.
400pub(super) fn checked_copy<R: Determinize>(
401    root: &R,
402    side: R::Side,
403    legal: &[R::Command],
404    seed: u64,
405) -> R
406where
407    R::Command: PartialEq,
408{
409    let copy = root.determinize(side, seed);
410    assert!(
411        copy.side_to_move() == side && copy.legal_commands() == legal,
412        "determinize changed the commands at the root (seed {seed}): a copy must list \
413         the state's legal commands, in the same order"
414    );
415    copy
416}
417
418/// Applies the root's candidate number `index` to a root's `copy` made
419/// from `seed`.
420///
421/// # Panics
422///
423/// With a message naming `determinize` when the copy refuses it.
424pub(super) fn apply_candidate<R: Determinize>(
425    copy: &mut R,
426    candidate: &R::Command,
427    index: usize,
428    seed: u64,
429) {
430    let applied = copy.apply(candidate).is_ok();
431    assert!(
432        applied,
433        "the copy from determinize refused candidate {index} (seed {seed}): a copy must \
434         accept the state's legal commands"
435    );
436}
437
438/// `n`, but at least 1, as a length.
439pub(super) fn at_least_one(n: u32) -> usize {
440    usize::try_from(n.max(1)).unwrap_or(usize::MAX)
441}
442
443/// The index `means` pick: at `temperature` 0 the best (the first among
444/// equals); otherwise a base-2 softmax, a mean `temperature` points below
445/// the best weighing half as much, and one draw from `rng`.
446pub(super) fn pick(means: &[i64], temperature: u32, rng: &mut SimRng) -> usize {
447    let best = means.iter().copied().max().unwrap_or(0);
448    let best_index = means.iter().position(|&mean| mean == best).unwrap_or(0);
449    if temperature == 0 {
450        return best_index;
451    }
452    let weights: Vec<u64> = means
453        .iter()
454        .map(|&mean| {
455            let below = (best - mean).saturating_mul(1 << 16) / i64::from(temperature);
456            u64::from(exp2_q16(-below))
457        })
458        .collect();
459    let shift = fit_shift(weights.iter().sum());
460    let weights: Vec<u64> = weights.iter().map(|weight| weight >> shift).collect();
461    let total = u32::try_from(weights.iter().sum::<u64>()).unwrap_or(u32::MAX);
462    share(&weights, u64::from(rng.roll_below(total))).unwrap_or(best_index)
463}
464
465/// How many halvings bring `total` into a `u32`, for one draw.
466fn fit_shift(total: u64) -> u32 {
467    (total >> 32).bit_width()
468}
469
470/// The index whose share of `weights`, laid end to end, holds `roll`;
471/// `None` past their sum.
472fn share(weights: &[u64], mut roll: u64) -> Option<usize> {
473    for (index, &weight) in weights.iter().enumerate() {
474        if roll < weight {
475            return Some(index);
476        }
477        roll -= weight;
478    }
479    None
480}
481
482/// `2^(-k/16)` in 16.16 fixed point, for `k` in `0..16`.
483const EXP2_FRACTIONS: [u32; 16] = [
484    65536, 62757, 60097, 57549, 55109, 52773, 50535, 48393, 46341, 44376, 42495, 40693, 38968,
485    37316, 35734, 34219,
486];
487
488/// `2^x` in 16.16 fixed point (`1 << 16` is 1), for `x` in 16.16 at most
489/// 0; a positive `x` counts as 0. The whole part is a shift, the fraction
490/// comes from a 16-entry table, read straight between its entries. More
491/// than 32 halvings down is 0.
492pub fn exp2_q16(x: i64) -> u32 {
493    let down = x.min(0).unsigned_abs();
494    let halvings = u32::try_from(down >> 16).unwrap_or(u32::MAX);
495    let fraction = down & 0xFFFF;
496    let entry = usize::try_from(fraction >> 12).unwrap_or(0);
497    let high = u64::from(EXP2_FRACTIONS[entry]);
498    let low = EXP2_FRACTIONS
499        .get(entry + 1)
500        .map_or(u64::from(EXP2_FRACTIONS[0]) >> 1, |&next| u64::from(next));
501    let value = high - (((high - low) * (fraction & 0xFFF)) >> 12);
502    let value = value.checked_shr(halvings).unwrap_or(0);
503    u32::try_from(value).unwrap_or(0)
504}
505
506#[cfg(test)]
507mod tests;
shuyi_core/bots/rollout.rs

shuyi_core/bots/
rollout.rs
