shuyi_core/bots/
order.rs

1//! A candidate order made of ranked groups: the few commands worth trying
2//! first, out of hundreds of legal ones.
3//!
4//! A bot that plans ([`TurnPlan`](super::TurnPlan), [`Rollout`](super::Rollout))
5//! tries only the first `candidates` commands of its [`Order`](super::Order).
6//! The legal order cut at ten holds one piece's attack in every flavour
7//! and nothing else, and a planner that never tries its other pieces, a
8//! step towards the goal or the end of its turn stalls (game ADR-0095).
9//! [`ranked_order`] is the generic cure: the game tags each legal command
10//! with a [`Ranked`] group, value and key (or leaves it out), and gets
11//! back
12//!
13//! 1. the groups in ascending order;
14//! 2. in a group, the best value first (a stable sort: ties keep the
15//!    game's order);
16//! 3. in a group, one per key first: the first command of each key comes
17//!    before any second command of a key already listed (a round-robin:
18//!    all firsts, then all seconds…); a command with no key is never held
19//!    back;
20//! 4. the `last` command (the end of the turn), if any, kept within the
21//!    cap: it takes the place of the last of the first `cap` commands, so
22//!    the cap never cuts it.
23//!
24//! A deck-builder's order is this alone: damage plays best first, one per
25//! target first, then draws, then the rest, ending the turn always kept.
26//! A grid game's is [`TacticsOrder`](crate::threat::TacticsOrder), built on
27//! it.
28//!
29//! ```
30//! use shuyi_core::bots::{Ranked, ranked_order};
31//!
32//! let plays = vec![
33//!     Ranked::new("strike a", 0, (5, 0), Some('a')),
34//!     Ranked::new("draw", 1, (0, 0), None),
35//!     Ranked::new("burn a", 0, (4, 0), Some('a')),
36//!     Ranked::new("strike b", 0, (3, 0), Some('b')),
37//! ];
38//! let order = ranked_order(plays.clone(), Some("end turn"), 10);
39//! assert_eq!(order, ["strike a", "strike b", "burn a", "draw", "end turn"]);
40//! assert_eq!(ranked_order(plays, Some("end turn"), 3), ["strike a", "strike b", "end turn"]);
41//! ```
42
43use alloc::vec::Vec;
44use core::cmp::Reverse;
45
46/// One command of a candidate order, as the game ranks it.
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct Ranked<C, K> {
49    /// The command.
50    pub command: C,
51    /// Its group: lower groups come first.
52    pub group: u8,
53    /// Its value in its group: higher comes first.
54    pub value: (i64, i64),
55    /// What it is one of, for one per key first (the target it strikes,
56    /// say); `None` is never held back.
57    pub key: Option<K>,
58}
59
60impl<C, K> Ranked<C, K> {
61    /// `command` in `group`, worth `value`, one of `key`.
62    pub const fn new(command: C, group: u8, value: (i64, i64), key: Option<K>) -> Self {
63        Self {
64            command,
65            group,
66            value,
67            key,
68        }
69    }
70}
71
72/// The first `cap` commands of `items` in the order the module's docs
73/// give: groups ascending, the best value first in a group, one per key
74/// first, and `last`, if any, in place of the last of them. `cap` 0
75/// counts as 1.
76pub fn ranked_order<C, K: Eq>(mut items: Vec<Ranked<C, K>>, last: Option<C>, cap: usize) -> Vec<C> {
77    items.sort_by_key(|item| (item.group, Reverse(item.value)));
78    let rounds = rounds(&items);
79    let mut ranked: Vec<(u8, usize, C)> = items
80        .into_iter()
81        .zip(rounds)
82        .map(|(item, round)| (item.group, round, item.command))
83        .collect();
84    ranked.sort_by_key(|&(group, round, _)| (group, round));
85    keep_last(
86        ranked.into_iter().map(|(_, _, command)| command).collect(),
87        last,
88        cap,
89    )
90}
91
92/// Each item's round in its group: how many items of its group and key
93/// come before it (0 with no key).
94fn rounds<C, K: Eq>(items: &[Ranked<C, K>]) -> Vec<usize> {
95    let mut seen: Vec<(u8, &K, usize)> = Vec::new();
96    items
97        .iter()
98        .map(|item| {
99            let Some(key) = &item.key else {
100                return 0;
101            };
102            if let Some(entry) = seen
103                .iter_mut()
104                .find(|(group, seen, _)| *group == item.group && *seen == key)
105            {
106                entry.2 += 1;
107                entry.2
108            } else {
109                seen.push((item.group, key, 0));
110                0
111            }
112        })
113        .collect()
114}
115
116/// The first `cap` of `order` (0 counts as 1), with `last`, if any, in
117/// place of the last of them.
118pub(crate) fn keep_last<C>(mut order: Vec<C>, last: Option<C>, cap: usize) -> Vec<C> {
119    let cap = cap.max(1);
120    match last {
121        Some(last) => {
122            order.truncate(cap - 1);
123            order.push(last);
124        }
125        None => order.truncate(cap),
126    }
127    order
128}
129
130#[cfg(test)]
131mod tests;
shuyi_core/bots/order.rs

shuyi_core/bots/
order.rs
