competitive/algorithm/game_analyzer/
scoring.rs

1use super::{
2    ControlFlow, EvaluatedMove, GameAnalysis, GameAnalyzer, Hash, HashMap, HashSet, Neighbor,
3    memoized_game,
4};
5
6#[derive(Debug, Clone, Copy, PartialEq, Eq)]
7pub enum Turn {
8    Same,
9    Other,
10}
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct ScoreMove<S, L = ()> {
14    pub next: Neighbor<S, L>,
15    pub reward: i64,
16    pub turn: Turn,
17}
18
19pub struct Scoring<S, F, T> {
20    moves: F,
21    terminal: T,
22    scores: HashMap<S, i64>,
23}
24
25impl GameAnalyzer {
26    /// Scores and rewards are measured for the player whose turn it is.
27    /// `terminal` returns `Some(score)` at terminal states and `None` elsewhere.
28    pub fn scoring<S, L, F, T, I>(self, moves: F, terminal: T) -> GameAnalyzer<Scoring<S, F, T>>
29    where
30        F: FnMut(&S) -> I,
31        I: IntoIterator<Item = ScoreMove<S, L>>,
32        T: FnMut(&S) -> Option<i64>,
33    {
34        GameAnalyzer {
35            game: Scoring {
36                moves,
37                terminal,
38                scores: HashMap::new(),
39            },
40        }
41    }
42}
43
44impl<S, F, T> GameAnalyzer<Scoring<S, F, T>> {
45    pub fn clear_cache(&mut self) {
46        self.game.scores.clear();
47    }
48}
49impl<S, L, F, T, I> GameAnalyzer<Scoring<S, F, T>>
50where
51    S: Clone + Eq + Hash,
52    F: FnMut(&S) -> I,
53    I: IntoIterator<Item = ScoreMove<S, L>>,
54    T: FnMut(&S) -> Option<i64>,
55{
56    pub fn score(&mut self) -> GameAnalysis<'_, Scoring<S, F, T>, S, i64> {
57        GameAnalysis::new(&mut self.game, |g, state| {
58            memoized_game(
59                state,
60                &mut g.scores,
61                &mut HashSet::new(),
62                &mut |s| {
63                    if let Some(value) = (g.terminal)(s) {
64                        return ControlFlow::Break(value);
65                    }
66                    let moves = (g.moves)(s)
67                        .into_iter()
68                        .map(|m| (m.next.to, (m.reward, m.turn)));
69                    ControlFlow::Continue((moves, None))
70                },
71                &mut |_, moves| moves.next(),
72                &mut |best: &mut Option<i64>, (reward, turn), child| {
73                    let value = match turn {
74                        Turn::Same => reward + child,
75                        Turn::Other => reward - child,
76                    };
77                    *best = Some(best.map_or(value, |b| b.max(value)));
78                    ControlFlow::Continue(())
79                },
80                &mut |_, best| best.expect("nonterminal scoring state has no moves"),
81            )
82        })
83    }
84}
85impl<S, L, F, T, I> GameAnalysis<'_, Scoring<S, F, T>, S, i64>
86where
87    F: FnMut(&S) -> I,
88    I: IntoIterator<Item = ScoreMove<S, L>>,
89    T: FnMut(&S) -> Option<i64>,
90{
91    /// Values include the reward and are measured for the current player.
92    pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, i64>> {
93        self.evaluated_moves(state).collect()
94    }
95
96    pub fn best_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
97        let mut result = Vec::new();
98        let mut best = None;
99        for m in self.evaluated_moves(state) {
100            if best.is_none_or(|best| m.value > best) {
101                result.clear();
102                best = Some(m.value);
103            }
104            if best == Some(m.value) {
105                result.push(m.next);
106            }
107        }
108        result
109    }
110
111    fn evaluated_moves(&mut self, state: &S) -> impl Iterator<Item = EvaluatedMove<S, L, i64>> {
112        let terminal = (self.game.terminal)(state).is_some();
113        let mut moves = (!terminal)
114            .then(|| (self.game.moves)(state).into_iter())
115            .into_iter()
116            .flatten()
117            .peekable();
118        assert!(
119            terminal || moves.peek().is_some(),
120            "nonterminal scoring state has no moves"
121        );
122        moves.map(|m| {
123            let child = self.eval(&m.next.to);
124            let value = match m.turn {
125                Turn::Same => m.reward + child,
126                Turn::Other => m.reward - child,
127            };
128            EvaluatedMove {
129                next: m.next,
130                value,
131            }
132        })
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use super::*;
139    use crate::tools::Xorshift;
140
141    #[test]
142    fn minimax_and_moves() {
143        let mut rng = Xorshift::default();
144        let mut edges = vec![Vec::new(); 64];
145        for (i, moves) in edges.iter_mut().enumerate().skip(1) {
146            for to in 0..i {
147                if to == 0 || rng.rand(4) == 0 {
148                    moves.push(ScoreMove {
149                        next: Neighbor::new(to, to),
150                        reward: rng.rand(21) as i64 - 10,
151                        turn: if rng.rand(2) == 0 {
152                            Turn::Same
153                        } else {
154                            Turn::Other
155                        },
156                    });
157                }
158            }
159            if i % 2 == 0 {
160                // Duplicate every option so any optimum has distinct labeled ties.
161                let extra: Vec<_> = moves
162                    .iter()
163                    .map(|m| ScoreMove {
164                        next: Neighbor::new(m.next.to, m.next.label + i),
165                        ..*m
166                    })
167                    .collect();
168                moves.extend(extra);
169            }
170        }
171        let terminal: Vec<_> = (0..edges.len())
172            .map(|s| {
173                if s == 0 {
174                    Some(-7)
175                } else {
176                    (s == 1 || s > 2 && rng.rand(4) == 0).then(|| rng.rand(21) as i64 - 10)
177                }
178            })
179            .collect();
180        let mut game =
181            GameAnalyzer::new().scoring(|&s: &usize| edges[s].clone(), |&s: &usize| terminal[s]);
182        // Fixed-player minimax also tracks whose turn it is, instead of negamax.
183        let mut scores = vec![[0i64; 2]; edges.len()];
184        for i in 0..edges.len() {
185            if let Some(value) = terminal[i] {
186                scores[i] = [value, -value];
187                continue;
188            }
189            for p in 0..2 {
190                let candidates = edges[i].iter().map(|m| {
191                    let next_player = p ^ usize::from(m.turn == Turn::Other);
192                    scores[m.next.to][next_player] + if p == 0 { m.reward } else { -m.reward }
193                });
194                scores[i][p] = if p == 0 {
195                    candidates.max()
196                } else {
197                    candidates.min()
198                }
199                .unwrap();
200            }
201        }
202        assert_eq!(game.score().verify(0..edges.len(), |&s| scores[s][0]), None);
203        for (s, expected) in scores.iter().enumerate() {
204            let best = game.score().best_moves(&s);
205            assert_eq!(best.is_empty(), terminal[s].is_some());
206            let moves: Vec<_> = edges[s]
207                .iter()
208                .filter(|_| terminal[s].is_none())
209                .map(|m| EvaluatedMove {
210                    next: m.next,
211                    value: m.reward + scores[m.next.to][usize::from(m.turn == Turn::Other)],
212                })
213                .collect();
214            assert_eq!(game.score().moves(&s), moves.clone());
215            assert_eq!(
216                best,
217                moves
218                    .iter()
219                    .filter(|m| m.value == expected[0])
220                    .map(|m| m.next)
221                    .collect::<Vec<_>>()
222            );
223        }
224    }
225}
competitive/algorithm/game_analyzer/scoring.rs

competitive/algorithm/game_analyzer/
scoring.rs
