competitive/algorithm/
game_analyzer.rs

1use super::{Dyadic, Graph, Neighbor, TopologicalSortExt, UsizeGraph, VertexMap};
2use std::{
3    borrow::Borrow,
4    collections::{HashMap, HashSet},
5    hash::Hash,
6    marker::PhantomData,
7    ops::ControlFlow,
8};
9
10pub use graph::*;
11pub use impartial::*;
12pub use partisan::*;
13pub use scoring::*;
14pub use value::GameValue;
15
16mod graph;
17mod impartial;
18mod partisan;
19mod scoring;
20mod value;
21
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
23pub enum Player {
24    Left,
25    Right,
26}
27
28impl Player {
29    pub fn opponent(self) -> Self {
30        match self {
31            Self::Left => Self::Right,
32            Self::Right => Self::Left,
33        }
34    }
35}
36
37/// Outcome for the player whose turn it is. A draw is an infinite play.
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39pub enum GameOutcome {
40    Win,
41    Draw,
42    Lose,
43}
44
45impl GameOutcome {
46    fn from_win(win: bool) -> Self {
47        if win { Self::Win } else { Self::Lose }
48    }
49}
50
51#[derive(Debug, Clone, Copy, PartialEq, Eq)]
52pub enum PartisanOutcome {
53    Next,
54    Previous,
55    Left,
56    Right,
57}
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct GameMismatch<S, V> {
61    pub state: S,
62    pub expected: V,
63    pub actual: V,
64}
65
66#[derive(Debug, Clone, PartialEq, Eq)]
67pub struct EvaluatedMove<S, L, V> {
68    pub next: Neighbor<S, L>,
69    pub value: V,
70}
71
72/// Owns a fixed game definition and reusable analysis caches.
73/// Move generators may collect statistics, but must keep the rules unchanged.
74/// Closure-based games must be finite and acyclic; detected cycles panic.
75/// Outcome queries stop exploring a position once a winning move is found.
76/// Use `impartial_graph` for Win/Draw/Lose analysis of cyclic graphs.
77///
78/// ```
79/// use competitive::algorithm::{GameAnalyzer, GameOutcome};
80/// let mut nim = GameAnalyzer::new().impartial(|&n: &usize| 0..n);
81/// assert_eq!(nim.grundy().eval(&3), 3);
82/// assert_eq!(nim.sum().grundy().eval(&[3, 3]), 0);
83/// assert_eq!(nim.misere().outcome().eval(&1), GameOutcome::Lose);
84/// assert_eq!(nim.outcome().eval(&1), GameOutcome::Win);
85/// assert_eq!(nim.grundy().verify(0..10, |&n| n as u64), None);
86/// ```
87#[derive(Default)]
88pub struct GameAnalyzer<G = ()> {
89    game: G,
90}
91
92impl GameAnalyzer {
93    pub fn new() -> Self {
94        Self::default()
95    }
96}
97
98pub struct GameAnalysis<'a, G, S, V, const MISERE: bool = false, F = fn(&mut G, &S) -> V>
99where
100    S: ?Sized,
101{
102    game: &'a mut G,
103    evaluate: F,
104    marker: PhantomData<fn(&S) -> V>,
105}
106
107impl<'a, G, S, V, const MISERE: bool, F> GameAnalysis<'a, G, S, V, MISERE, F>
108where
109    S: ?Sized,
110    F: FnMut(&mut G, &S) -> V,
111{
112    pub fn eval(&mut self, state: &S) -> V {
113        (self.evaluate)(self.game, state)
114    }
115
116    /// Keeps the input items, their order and duplicates; dependency states are omitted.
117    pub fn table<T>(&mut self, states: impl IntoIterator<Item = T>) -> Vec<(T, V)>
118    where
119        T: Borrow<S>,
120    {
121        states
122            .into_iter()
123            .map(|state| {
124                let value = self.eval(state.borrow());
125                (state, value)
126            })
127            .collect()
128    }
129
130    /// Returns the first mismatch in input order, or `None` if the range agrees.
131    pub fn verify<T>(
132        &mut self,
133        states: impl IntoIterator<Item = T>,
134        mut expected: impl FnMut(&S) -> V,
135    ) -> Option<GameMismatch<T, V>>
136    where
137        T: Borrow<S>,
138        V: PartialEq,
139    {
140        for state in states {
141            let expected = expected(state.borrow());
142            let actual = self.eval(state.borrow());
143            if actual != expected {
144                return Some(GameMismatch {
145                    state,
146                    expected,
147                    actual,
148                });
149            }
150        }
151        None
152    }
153
154    fn new(game: &'a mut G, evaluate: F) -> Self {
155        Self {
156            game,
157            evaluate,
158            marker: PhantomData,
159        }
160    }
161}
162
163pub struct Misere<'a, G> {
164    game: &'a mut G,
165}
166
167pub struct GameSum<'a, G, const MISERE: bool = false> {
168    game: &'a mut G,
169}
170
171impl<'a, G> Misere<'a, G> {
172    pub fn sum(self) -> GameSum<'a, G, true> {
173        GameSum { game: self.game }
174    }
175}
176
177impl<'a, G> GameSum<'a, G> {
178    pub fn misere(self) -> GameSum<'a, G, true> {
179        GameSum { game: self.game }
180    }
181}
182
183fn game_mex(mut values: Vec<u64>) -> u64 {
184    for i in 0..values.len() {
185        while values[i] < values.len() as u64 {
186            let j = values[i] as usize;
187            if values[j] == values[i] {
188                break;
189            }
190            values.swap(i, j);
191        }
192    }
193    values
194        .iter()
195        .enumerate()
196        .position(|(i, &g)| i as u64 != g)
197        .unwrap_or(values.len()) as u64
198}
199
200fn canonical_sum<S>(mut state: Vec<S>, ids: &mut HashMap<S, usize>) -> Vec<S>
201where
202    S: Clone + Eq + Hash,
203{
204    for s in &state {
205        if !ids.contains_key(s) {
206            ids.insert(s.clone(), ids.len());
207        }
208    }
209    state.sort_unstable_by_key(|s| ids[s]);
210    state
211}
212
213fn memoized_game<S, V, I, A, T>(
214    state: &S,
215    cache: &mut HashMap<S, V>,
216    active: &mut HashSet<S>,
217    expand: &mut impl FnMut(&S) -> ControlFlow<V, (I, A)>,
218    advance: &mut impl FnMut(&S, &mut I) -> Option<(S, T)>,
219    feed: &mut impl FnMut(&mut A, T, V) -> ControlFlow<V>,
220    finish: &mut impl FnMut(&S, A) -> V,
221) -> V
222where
223    S: Clone + Eq + Hash,
224    V: Clone,
225{
226    if let Some(value) = cache.get(state) {
227        return value.clone();
228    }
229    assert!(active.insert(state.clone()), "cycle in a finite game");
230    let value = match expand(state) {
231        ControlFlow::Break(value) => value,
232        ControlFlow::Continue((mut moves, mut accumulator)) => 'search: {
233            while let Some((next, edge)) = advance(state, &mut moves) {
234                let child = memoized_game(&next, cache, active, expand, advance, feed, finish);
235                if let ControlFlow::Break(value) = feed(&mut accumulator, edge, child) {
236                    break 'search value;
237                }
238            }
239            finish(state, accumulator)
240        }
241    };
242    active.remove(state);
243    cache.insert(state.clone(), value.clone());
244    value
245}
246
247fn memoized_wins<S, I>(
248    state: &S,
249    cache: &mut HashMap<S, bool>,
250    mut expand: impl FnMut(&S) -> ControlFlow<bool, I>,
251    mut advance: impl FnMut(&S, &mut I) -> Option<S>,
252    misere: bool,
253) -> bool
254where
255    S: Clone + Eq + Hash,
256{
257    memoized_game(
258        state,
259        cache,
260        &mut HashSet::new(),
261        &mut |s| expand(s).map_continue(|moves| (moves, false)),
262        &mut |s, moves| advance(s, moves).map(|next| (next, ())),
263        &mut |has_moves, (), child| {
264            *has_moves = true;
265            if child {
266                ControlFlow::Continue(())
267            } else {
268                ControlFlow::Break(true)
269            }
270        },
271        &mut |_, has_moves| !has_moves && misere,
272    )
273}
competitive/algorithm/game_analyzer.rs

competitive/algorithm/
game_analyzer.rs
