shuyi_core/threat/
order.rs

1//! A planner's candidate order for grid games: [`TacticsOrder`], on
2//! [`ranked_order`](crate::bots::ranked_order)'s idea.
3//!
4//! A planner tries only the first few of hundreds of legal commands. Cut
5//! at ten, the legal order holds one piece's attack in every flavour and
6//! no piece's move, and a planner whose pieces never step towards the
7//! goal or out of danger stalls (game ADR-0095). So a capped list gives
8//! every piece its say before any piece's second, and keeps a step
9//! towards the goal, a step to safety and the end of the turn. The game
10//! tags each legal command with a [`Kind`] ([`OrderHooks::classify`]),
11//! and the order is:
12//!
13//! 1. **strikes**: each piece's best strike on each target, best value
14//!    first. Of a piece's strikes with the same way on the same target,
15//!    only the best (from its best tile) is listed at all; the first per
16//!    `(piece, target)` comes here, so every piece that can strike does
17//!    before any piece's second way;
18//! 2. **the game's pick** ([`OrderHooks::pick`], an AI's own command), if
19//!    it is one of the commands given, isn't [`Kind::End`] or
20//!    [`Kind::Drop`] and isn't listed yet; it is then left out of the
21//!    steps below;
22//! 3. **extras**: the game's own lists ([`Kind::Extra`], heals say), by
23//!    group, then the best value first, one per `once`;
24//! 4. **advances**: per piece, its [`Kind::Step`] whose destination is
25//!    nearest the goals by walking ([`OrderHooks::distance`]), if nearer
26//!    than where the piece stands;
27//! 5. **holds**: per piece, its step whose destination no threat reaches
28//!    ([`OrderHooks::safe`]), nearest the goals, if it isn't its advance;
29//! 6. **the other ways of striking**: the strikes held back in step 1,
30//!    best first;
31//! 7. **the rest**: [`Kind::Other`] and the steps not listed yet, in the
32//!    legal order;
33//! 8. **the end of the turn** ([`Kind::End`]) last, in place of the last
34//!    of the first `cap` commands, so the cap never cuts it.
35//!
36//! Commands tagged [`Kind::Drop`] are left out. Among equals the legal
37//! order decides: the first strike of equal value, the first step of
38//! equal distance, the pieces in the order their first listed command
39//! comes. The order is at most `cap` commands; give the planner the same
40//! cap as its `candidates`.
41
42use alloc::vec::Vec;
43use core::cmp::Reverse;
44
45use crate::bots::order::keep_last;
46use crate::bots::{Order, Sides};
47use crate::grid::Pos;
48
49/// What a legal command is to a [`TacticsOrder`]. `P` is the game's id of
50/// a piece.
51#[derive(Debug, Clone, Copy, PartialEq, Eq)]
52#[non_exhaustive]
53pub enum Kind<P> {
54    /// `piece` strikes `target` (or a tile, `None`) in its way `way` (a
55    /// weapon, an art, a spell: the game's number for it), worth `value`
56    /// (the damage expected dealt, then minus the damage expected taken
57    /// back, say: higher first).
58    Strike {
59        /// The piece striking.
60        piece: P,
61        /// The piece struck, if it strikes one.
62        target: Option<P>,
63        /// Its way of striking.
64        way: u32,
65        /// How good it looks: higher first.
66        value: (i64, i64),
67    },
68    /// One of the game's own lists (heals say), after the game's pick: by
69    /// `group`, lower first, then `value`, higher first. Of the commands
70    /// with the same `once` (a piece, its target and its way), only the
71    /// first by that order is listed; `None` is always listed.
72    Extra {
73        /// Its list: lower first.
74        group: u8,
75        /// How good it looks: higher first.
76        value: (i64, i64),
77        /// What it is one of.
78        once: Option<(P, Option<P>, u32)>,
79    },
80    /// `piece` ends on `dest`, doing nothing else (it waits there): an
81    /// advance, a hold or the rest.
82    Step {
83        /// The piece stepping.
84        piece: P,
85        /// Where it ends.
86        dest: Pos,
87    },
88    /// The end of the turn, kept within the cap (the first one given; a
89    /// second is left out).
90    End,
91    /// Never tried.
92    Drop,
93    /// Anything else: listed after the strikes held back.
94    Other,
95}
96
97/// What a [`TacticsOrder`] asks the game, once per
98/// [`order`](Order::order) call. The game's hooks hold the state's
99/// [`Threats`](super::Threats) and [`GoalDistance`](super::GoalDistance),
100/// built in [`prepare`](OrderHooks::prepare).
101pub trait OrderHooks<R: Sides> {
102    /// The game's id of a piece.
103    type Piece: Eq + Copy;
104
105    /// Called first: build this state's [`Threats`](super::Threats) and
106    /// [`GoalDistance`](super::GoalDistance).
107    fn prepare(&mut self, rules: &R);
108
109    /// What `command` is, called once per legal command, in the legal
110    /// order.
111    fn classify(&mut self, rules: &R, command: &R::Command) -> Kind<Self::Piece>;
112
113    /// The game's own pick (an AI's command), if it has one; it may also
114    /// be a strike or a step, and is listed once.
115    fn pick(&mut self, rules: &R) -> Option<R::Command>;
116
117    /// Where `piece` stands now.
118    fn at(&self, rules: &R, piece: Self::Piece) -> Option<Pos>;
119
120    /// How far `piece` would walk from `from` to the nearest goal; `None`
121    /// with no walk.
122    fn distance(&mut self, rules: &R, piece: Self::Piece, from: Pos) -> Option<u32>;
123
124    /// Whether no threat reaches `at`.
125    fn safe(&self, rules: &R, at: Pos) -> bool;
126}
127
128/// A planner's candidate order for grid games, in eight steps (the
129/// module's docs): every piece's best strike, the game's pick, its extras,
130/// each piece's advance and hold, the other strikes, the rest, and the end
131/// of the turn within `cap`.
132#[derive(Debug, Clone, PartialEq, Eq)]
133#[non_exhaustive]
134pub struct TacticsOrder<H> {
135    /// What the order asks the game.
136    pub hooks: H,
137    /// The most commands it lists; 0 counts as 1. The planner's
138    /// `candidates`.
139    pub cap: usize,
140}
141
142impl<H> TacticsOrder<H> {
143    /// An order asking `hooks`, listing at most `cap` commands.
144    pub const fn new(hooks: H, cap: usize) -> Self {
145        Self { hooks, cap }
146    }
147}
148
149impl<R, H> Order<R> for TacticsOrder<H>
150where
151    R: Sides,
152    R::Command: PartialEq,
153    H: OrderHooks<R>,
154{
155    fn order(&mut self, rules: &R, commands: Vec<R::Command>) -> Vec<R::Command> {
156        let listed = listed(&mut self.hooks, rules, &commands);
157        let mut commands: Vec<Option<R::Command>> = commands.into_iter().map(Some).collect();
158        let mut take = |index: usize| commands[index].take();
159        let order: Vec<R::Command> = listed.order.into_iter().filter_map(&mut take).collect();
160        let end = listed.end.and_then(take);
161        keep_last(order, end, self.cap)
162    }
163}
164
165/// The order as indices of the commands given: every step but the last,
166/// in order, and the end of the turn.
167#[derive(Debug, PartialEq, Eq)]
168struct Listed {
169    order: Vec<usize>,
170    end: Option<usize>,
171}
172
173/// The steps of the order (the module's docs), as indices of `commands`.
174#[derive(Debug, PartialEq, Eq)]
175struct Steps {
176    strikes: Vec<usize>,
177    pick: Option<usize>,
178    extras: Vec<usize>,
179    advances: Vec<usize>,
180    holds: Vec<usize>,
181    held: Vec<usize>,
182    rest: Vec<usize>,
183    end: Option<usize>,
184}
185
186/// The order of `commands` in `rules`, as [`steps`] lists it.
187fn listed<R, H>(hooks: &mut H, rules: &R, commands: &[R::Command]) -> Listed
188where
189    R: Sides,
190    R::Command: PartialEq,
191    H: OrderHooks<R>,
192{
193    let steps = steps(hooks, rules, commands);
194    let not_pick = |index: &usize| steps.pick != Some(*index);
195    let mut order = steps.strikes;
196    order.extend(steps.pick);
197    for step in [
198        steps.extras,
199        steps.advances,
200        steps.holds,
201        steps.held,
202        steps.rest,
203    ] {
204        order.extend(step.into_iter().filter(not_pick));
205    }
206    Listed {
207        order,
208        end: steps.end,
209    }
210}
211
212/// Every step of the order of `commands` in `rules`, each in its order;
213/// the pick may be in another step too.
214fn steps<R, H>(hooks: &mut H, rules: &R, commands: &[R::Command]) -> Steps
215where
216    R: Sides,
217    R::Command: PartialEq,
218    H: OrderHooks<R>,
219{
220    hooks.prepare(rules);
221    let kinds: Vec<Kind<H::Piece>> = commands
222        .iter()
223        .map(|command| hooks.classify(rules, command))
224        .collect();
225    let (strikes, held) = strikes(&kinds);
226    let (advances, holds) = advances_and_holds(hooks, rules, &kinds);
227    let pick = hooks
228        .pick(rules)
229        .and_then(|pick| commands.iter().position(|command| *command == pick))
230        .filter(|&index| !matches!(kinds[index], Kind::End | Kind::Drop))
231        .filter(|index| !strikes.contains(index));
232    let mut end = None;
233    let mut rest = Vec::new();
234    for (index, kind) in kinds.iter().enumerate() {
235        match kind {
236            Kind::End if end.is_none() => end = Some(index),
237            Kind::Other | Kind::Step { .. }
238                if !advances.contains(&index) && !holds.contains(&index) =>
239            {
240                rest.push(index);
241            }
242            _ => {}
243        }
244    }
245    Steps {
246        strikes,
247        pick,
248        extras: extras(&kinds),
249        advances,
250        holds,
251        held,
252        rest,
253        end,
254    }
255}
256
257/// A strike's piece and the piece it strikes.
258type Aim<P> = (P, Option<P>);
259
260/// What an extra is one of: a piece, its target and its way.
261type Once<P> = (P, Option<P>, u32);
262
263/// A strike or an extra of the commands given: its index, what it is one
264/// of, and its group and value.
265struct Entry<O> {
266    index: usize,
267    of: O,
268    rank: (u8, (i64, i64)),
269}
270
271/// The entries `entry` finds in `kinds`, by group, then the best value
272/// first (a stable sort: ties keep the legal order).
273fn ranked<P, O>(
274    kinds: &[Kind<P>],
275    entry: impl Fn(&Kind<P>) -> Option<(O, (u8, (i64, i64)))>,
276) -> Vec<Entry<O>> {
277    let mut entries: Vec<Entry<O>> = kinds
278        .iter()
279        .enumerate()
280        .filter_map(|(index, kind)| entry(kind).map(|(of, rank)| Entry { index, of, rank }))
281        .collect();
282    entries.sort_by_key(|entry| (entry.rank.0, Reverse(entry.rank.1)));
283    entries
284}
285
286/// The strikes of `kinds`, best first, one per piece, target and way: the
287/// first of each piece and target (step 1), and the others (step 6).
288fn strikes<P: Eq + Copy>(kinds: &[Kind<P>]) -> (Vec<usize>, Vec<usize>) {
289    let strikes = ranked(kinds, |kind| match *kind {
290        Kind::Strike {
291            piece,
292            target,
293            way,
294            value,
295        } => Some((((piece, target), way), (0, value))),
296        _ => None,
297    });
298    let mut ways: Vec<(Aim<P>, u32)> = Vec::new();
299    let mut firsts = Vec::new();
300    let mut held = Vec::new();
301    for Entry { index, of, .. } in strikes {
302        if ways.contains(&of) {
303            continue;
304        }
305        if ways.iter().any(|&(aim, _)| aim == of.0) {
306            held.push(index);
307        } else {
308            firsts.push(index);
309        }
310        ways.push(of);
311    }
312    (firsts, held)
313}
314
315/// The extras of `kinds`, by group, then the best value first, the first
316/// of each `once` only (step 3).
317fn extras<P: Eq + Copy>(kinds: &[Kind<P>]) -> Vec<usize> {
318    let extras = ranked(kinds, |kind| match *kind {
319        Kind::Extra { group, value, once } => Some((once, (group, value))),
320        _ => None,
321    });
322    let mut seen: Vec<Once<P>> = Vec::new();
323    let mut out = Vec::new();
324    for Entry { index, of, .. } in extras {
325        if let Some(once) = of {
326            if seen.contains(&once) {
327                continue;
328            }
329            seen.push(once);
330        }
331        out.push(index);
332    }
333    out
334}
335
336/// Each piece's advance and hold among the steps of `kinds` (steps 4 and
337/// 5), in the order of the pieces' first: a piece's best as `(piece,
338/// distance, index)`.
339fn advances_and_holds<R, H>(
340    hooks: &mut H,
341    rules: &R,
342    kinds: &[Kind<H::Piece>],
343) -> (Vec<usize>, Vec<usize>)
344where
345    R: Sides,
346    H: OrderHooks<R>,
347{
348    let mut here: Vec<(H::Piece, Option<u32>)> = Vec::new();
349    let mut advances: Vec<(H::Piece, u32, usize)> = Vec::new();
350    let mut holds: Vec<(H::Piece, u32, usize)> = Vec::new();
351    for (index, kind) in kinds.iter().enumerate() {
352        let Kind::Step { piece, dest } = *kind else {
353            continue;
354        };
355        let Some(there) = hooks.distance(rules, piece, dest) else {
356            continue;
357        };
358        let from = if let Some(&(_, from)) = here.iter().find(|(seen, _)| *seen == piece) {
359            from
360        } else {
361            let from = hooks
362                .at(rules, piece)
363                .and_then(|at| hooks.distance(rules, piece, at));
364            here.push((piece, from));
365            from
366        };
367        if from.is_some_and(|from| there < from) {
368            keep_nearest(&mut advances, piece, there, index);
369        }
370        if hooks.safe(rules, dest) {
371            keep_nearest(&mut holds, piece, there, index);
372        }
373    }
374    let advances: Vec<usize> = advances.into_iter().map(|(_, _, index)| index).collect();
375    let holds = holds
376        .into_iter()
377        .map(|(_, _, index)| index)
378        .filter(|index| !advances.contains(index))
379        .collect();
380    (advances, holds)
381}
382
383/// Keeps step `index` of `piece`, `distance` from the goals, in `best`
384/// if it is the piece's nearest yet (the first among equals).
385fn keep_nearest<P: Eq>(best: &mut Vec<(P, u32, usize)>, piece: P, distance: u32, index: usize) {
386    match best.iter_mut().find(|(seen, _, _)| *seen == piece) {
387        Some(nearest) if distance < nearest.1 => *nearest = (piece, distance, index),
388        Some(_) => {}
389        None => best.push((piece, distance, index)),
390    }
391}
392
393#[cfg(test)]
394mod tests;
shuyi_core/threat/order.rs

shuyi_core/threat/
order.rs
