shuyi_core/bots/plan.rs
1//! A turn planner over any [`Determinize`] game: a beam search over its
2//! own side's commands.
3//!
4//! [`TurnPlan`] is for games whose side issues several commands a turn
5//! (each of its pieces acts, cards are played one after another). It
6//! weighs short *sequences* of its own commands, so a first command that
7//! only pays off with a second ("weaken it, then finish it"; a card that
8//! draws, then the card it drew) is chosen for what the sequence does,
9//! not judged alone. It plays each partial turn on copies of the game
10//! where the luck and the hidden things are redrawn ([`Determinize`]),
11//! scores where each copy got to ([`Evaluate`]), and keeps the best few
12//! at each depth to extend by the game's next candidates ([`Order`]).
13//! It never searches the other sides' replies: their danger is the
14//! game's [`Evaluate`] to see, as a player would.
15//!
16//! Every partial turn is played on the same copies, one per seed. A copy
17//! stops where it refuses a command (a piece fell there), where its
18//! side's turn ends, or where the game ends, and is scored there. A
19//! partial turn's candidates are the order of its first copy still
20//! playing. A first command is worth the best partial turn that starts
21//! with it, itself included.
22//!
23//! It returns the first command of the best plan and plans again for the
24//! next command, keeping nothing between decisions but its random number
25//! generator. Its
26//! integers, its softmax and its work units are the rollout bot's: a unit
27//! is one command applied to a copy, and its own randomness is drawn only
28//! at a decision's start and its end, so how the work is sliced
29//! ([`PlanSearch::advance`]) never changes the command (ADR-0027,
30//! ADR-0029).
31
32use alloc::vec::Vec;
33use core::cmp::Reverse;
34
35use serde::{Deserialize, Serialize};
36
37use super::Bot;
38use super::Sides;
39use super::determinize::{Determinize, Evaluate};
40use super::rollout::{
41 Order, Progress, apply_candidate, at_least_one, checked_copy, draw_seeds, pick,
42};
43use crate::rng::SimRng;
44
45/// How a [`TurnPlan`] bot thinks: data, so a persona's settings can be a
46/// file.
47#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
48pub struct PlanSettings {
49 /// How many partial turns are kept at each depth, to be extended at
50 /// the next: the beam. 0 counts as 1.
51 pub width: u32,
52 /// How many of the ordered commands are tried from each partial
53 /// turn, from the first. 0 counts as 1.
54 pub candidates: u32,
55 /// The most of its own commands a plan holds; the side's turn may end
56 /// sooner. 0 counts as 1.
57 pub depth: u32,
58 /// How many copies each partial turn is played on. 0 counts as 1.
59 pub samples: u32,
60 /// How far from the best the first command's pick may stray, in
61 /// points: a command this many points below the best is half as
62 /// likely. 0 always picks the best.
63 pub temperature: u32,
64}
65
66/// A computer player that plans its side's turn on copies of the game: a
67/// beam search over its own commands (the module's docs).
68///
69/// A decision does at most `samples × candidates × (1 + width × (depth -
70/// 1))` units of work, a unit being one command applied to a copy.
71#[derive(Debug, Clone)]
72pub struct TurnPlan<O, E> {
73 order: O,
74 eval: E,
75 settings: PlanSettings,
76 rng: SimRng,
77}
78
79impl<O, E> TurnPlan<O, E> {
80 /// A turn planner whose candidates come from `order` and whose partial
81 /// turns are scored by `eval`, thinking as `settings` says. Its choices
82 /// follow from `seed`.
83 pub fn new(order: O, eval: E, settings: PlanSettings, seed: u64) -> Self {
84 Self {
85 order,
86 eval,
87 settings,
88 rng: SimRng::new(seed),
89 }
90 }
91
92 /// How it thinks.
93 pub fn settings(&self) -> PlanSettings {
94 self.settings
95 }
96
97 /// Starts a decision in `rules`, which is not over: its first commands
98 /// are listed, its seeds drawn and its copies made.
99 /// [`PlanSearch::advance`] does the work.
100 ///
101 /// # Panics
102 ///
103 /// If the game lists no legal command, or the order drops them all;
104 /// with a message naming `determinize` when a copy lists other
105 /// commands than the real state.
106 pub fn search<R>(&mut self, rules: &R) -> PlanSearch<'_, R, O, E>
107 where
108 R: Determinize,
109 R::Command: Clone + PartialEq,
110 O: Order<R>,
111 E: Evaluate<R>,
112 {
113 let legal = rules.legal_commands();
114 let mut firsts = self.order.order(rules, legal.clone());
115 firsts.truncate(at_least_one(self.settings.candidates));
116 assert!(
117 !firsts.is_empty(),
118 "no command to choose from: the game lists none, or its order dropped them all"
119 );
120 let side = rules.side_to_move();
121 let seeds = draw_seeds(&mut self.rng, self.settings.samples);
122 let copies = seeds
123 .iter()
124 .map(|&seed| Sample {
125 state: checked_copy(rules, side, &legal, seed),
126 playing: true,
127 })
128 .collect();
129 PlanSearch {
130 root: rules.clone(),
131 side,
132 seeds,
133 values: alloc::vec![i64::MIN; firsts.len()],
134 parents: alloc::vec![Partial {
135 first: None,
136 copies,
137 candidates: firsts.iter().rev().cloned().collect(),
138 }],
139 firsts,
140 children: Vec::new(),
141 depth: 1,
142 phase: Phase::Between,
143 bot: self,
144 }
145 }
146}
147
148impl<R, O, E> Bot<R> for TurnPlan<O, E>
149where
150 R: Determinize,
151 R::Command: Clone + PartialEq,
152 O: Order<R>,
153 E: Evaluate<R>,
154{
155 /// The first command of the best plan (or, at a temperature, one
156 /// picked by the softmax).
157 ///
158 /// # Panics
159 ///
160 /// As [`TurnPlan::search`] and [`PlanSearch::advance`] do.
161 fn choose(&mut self, rules: &R) -> R::Command {
162 match self.search(rules).work(u64::MAX) {
163 Progress::Chosen(command) => command,
164 Progress::Working => panic!("a decision took more than u64::MAX units"),
165 }
166 }
167}
168
169/// A decision of a [`TurnPlan`] bot under way: its loop state in a value,
170/// so the work can be split over many calls (frames, later).
171pub struct PlanSearch<'a, R: Sides, O, E> {
172 bot: &'a mut TurnPlan<O, E>,
173 /// The state the decision began in.
174 root: R,
175 side: R::Side,
176 /// One per copy of each partial turn.
177 seeds: Vec<u64>,
178 /// The root's candidates: the plans' first commands.
179 firsts: Vec<R::Command>,
180 /// The best score of a partial turn starting with each first command.
181 values: Vec<i64>,
182 /// The partial turns being extended, the next one last: at depth 1,
183 /// the root alone.
184 parents: Vec<Partial<R>>,
185 /// The partial turns built at this depth that may be extended, with
186 /// their scores.
187 children: Vec<(i64, Partial<R>)>,
188 /// How many commands the partial turns being built hold.
189 depth: usize,
190 phase: Phase<R>,
191}
192
193/// Where a search is. Each step of its loop returns the next phase, so no
194/// step can leave the search where it was.
195enum Phase<R: Sides> {
196 /// Between partial turns: the next one is to be started.
197 Between,
198 /// A partial turn being built.
199 Building(Building<R>),
200 /// The decision is made.
201 Chosen(R::Command),
202}
203
204/// A partial turn: its copies, played as far as its commands go.
205struct Partial<R: Sides> {
206 /// The index of its first command in the root's candidates; `None`
207 /// for the root.
208 first: Option<usize>,
209 /// One per seed.
210 copies: Vec<Sample<R>>,
211 /// The commands it is still to be extended by, the next one last.
212 /// Each is taken off as its partial turn is built, so the search
213 /// keeps no count that could run past them.
214 candidates: Vec<R::Command>,
215}
216
217/// A copy of a partial turn.
218struct Sample<R> {
219 state: R,
220 /// Whether its plan goes on: no command was refused, the turn is
221 /// still its side's and the game isn't over.
222 playing: bool,
223}
224
225/// A partial turn being built, one copy at a time.
226struct Building<R: Sides> {
227 first: usize,
228 /// The command its parent's copies are extended by.
229 command: R::Command,
230 copies: Vec<Sample<R>>,
231 /// The sum of its copies' scores.
232 sum: i64,
233}
234
235impl<R, O, E> PlanSearch<'_, R, O, E>
236where
237 R: Determinize,
238 R::Command: Clone + PartialEq,
239 O: Order<R>,
240 E: Evaluate<R>,
241{
242 /// Does at most `units` units of work (commands applied to copies) and
243 /// returns the chosen command once the decision is made, `None` while
244 /// it is working. Once made, it returns the same command again.
245 ///
246 /// # Panics
247 ///
248 /// With a message naming `determinize` when a copy of the root refuses
249 /// one of its candidates: a bug in the game's
250 /// [`Determinize::determinize`].
251 pub fn advance(&mut self, units: u32) -> Option<R::Command> {
252 match self.work(u64::from(units)) {
253 Progress::Chosen(command) => Some(command),
254 Progress::Working => None,
255 }
256 }
257
258 /// [`advance`](Self::advance), on as many as `u64::MAX` units: a
259 /// [`Progress`], which no step can fake, so a search that stopped
260 /// moving fails at once instead of spinning.
261 fn work(&mut self, units: u64) -> Progress<R::Command> {
262 let mut left = units;
263 loop {
264 self.phase = match core::mem::replace(&mut self.phase, Phase::Between) {
265 Phase::Chosen(command) => {
266 self.phase = Phase::Chosen(command.clone());
267 return Progress::Chosen(command);
268 }
269 Phase::Between => self.next(),
270 Phase::Building(building) => {
271 let built = building.copies.len();
272 if built == self.seeds.len() {
273 self.finish(building);
274 Phase::Between
275 } else if self
276 .parents
277 .last()
278 .is_some_and(|parent| !parent.copies[built].playing)
279 {
280 Phase::Building(self.step(building))
281 } else if left == 0 {
282 self.phase = Phase::Building(building);
283 return Progress::Working;
284 } else {
285 left -= 1;
286 Phase::Building(self.step(building))
287 }
288 }
289 };
290 }
291 }
292
293 /// What follows a partial turn: the last parent's next candidate to
294 /// build. A parent with none left is done; at the depth's end, the best
295 /// are kept to extend, or the decision is made.
296 fn next(&mut self) -> Phase<R> {
297 let Some(parent) = self.parents.last_mut() else {
298 if self.children.is_empty() {
299 return Phase::Chosen(self.pick());
300 }
301 let children = core::mem::take(&mut self.children);
302 self.parents = self.deepen(children);
303 return Phase::Between;
304 };
305 let Some(command) = parent.candidates.pop() else {
306 self.parents.pop();
307 return Phase::Between;
308 };
309 // At the root, the candidates left say which first command this is.
310 // Lazily: deeper, a partial turn may have more candidates than the
311 // root has first commands.
312 let first = parent
313 .first
314 .unwrap_or_else(|| self.firsts.len() - parent.candidates.len() - 1);
315 Phase::Building(Building {
316 first,
317 command,
318 copies: Vec::with_capacity(self.seeds.len()),
319 sum: 0,
320 })
321 }
322
323 /// `building` with its next copy: its parent's copy with the candidate
324 /// applied, if that copy is still playing.
325 fn step(&self, mut building: Building<R>) -> Building<R> {
326 let Some(parent) = self.parents.last() else {
327 return building;
328 };
329 let index = building.copies.len();
330 let from = &parent.copies[index];
331 let mut state = from.state.clone();
332 let mut playing = from.playing;
333 if playing {
334 let command = &building.command;
335 if parent.first.is_none() {
336 apply_candidate(&mut state, command, building.first, self.seeds[index]);
337 } else {
338 playing = state.apply(command).is_ok();
339 }
340 playing = playing && state.side_to_move() == self.side && state.outcome().is_none();
341 }
342 let score = self.bot.eval.score(&self.root, &state, self.side);
343 building.sum = building.sum.saturating_add(i64::from(score));
344 building.copies.push(Sample { state, playing });
345 building
346 }
347
348 /// Scores the partial turn just built into its first command's value,
349 /// and keeps it if it may be extended.
350 fn finish(&mut self, building: Building<R>) {
351 let samples = i64::try_from(self.seeds.len()).unwrap_or(i64::MAX);
352 let mean = building.sum.div_euclid(samples);
353 let value = &mut self.values[building.first];
354 *value = (*value).max(mean);
355 let deeper = self.depth < at_least_one(self.bot.settings.depth);
356 if deeper && building.copies.iter().any(|copy| copy.playing) {
357 let partial = Partial {
358 first: Some(building.first),
359 copies: building.copies,
360 candidates: Vec::new(),
361 };
362 self.children.push((mean, partial));
363 }
364 }
365
366 /// Goes a depth deeper: the parents to extend, the `width` best of the
367 /// partial turns just built (the earlier among equals), the next one
368 /// last, each with its candidates: the game's order of its first
369 /// playing copy's legal commands.
370 fn deepen(&mut self, mut children: Vec<(i64, Partial<R>)>) -> Vec<Partial<R>> {
371 children.sort_by_key(|&(score, _)| Reverse(score));
372 children.truncate(at_least_one(self.bot.settings.width));
373 let cap = at_least_one(self.bot.settings.candidates);
374 let mut parents = Vec::with_capacity(children.len());
375 for (_, mut partial) in children {
376 if let Some(copy) = partial.copies.iter().find(|copy| copy.playing) {
377 let legal = copy.state.legal_commands();
378 partial.candidates = self.bot.order.order(©.state, legal);
379 partial.candidates.truncate(cap);
380 partial.candidates.reverse();
381 }
382 parents.push(partial);
383 }
384 parents.reverse();
385 self.depth += 1;
386 parents
387 }
388
389 /// The decision: each first command's best value, then the pick.
390 fn pick(&mut self) -> R::Command {
391 let temperature = self.bot.settings.temperature;
392 let index = pick(&self.values, temperature, &mut self.bot.rng);
393 self.firsts[index].clone()
394 }
395}
396
397#[cfg(test)]
398mod tests;