pub fn memoized_game<S, V, I, A, T>(
state: &S,
cache: &mut HashMap<S, V>,
active: &mut HashSet<S>,
expand: &mut impl FnMut(&S) -> ControlFlow<V, (I, A)>,
advance: &mut impl FnMut(&S, &mut I) -> Option<(S, T)>,
feed: &mut impl FnMut(&mut A, T, V) -> ControlFlow<V>,
finish: &mut impl FnMut(&S, A) -> V,
) -> VExamples found in repository?
crates/competitive/src/algorithm/game_analyzer/impartial.rs (lines 100-116)
88 pub fn fold<V, C>(
89 &mut self,
90 mut combine: C,
91 ) -> GameAnalysis<'_, Impartial<S, F>, S, V, false, impl FnMut(&mut Impartial<S, F>, &S) -> V>
92 where
93 V: Clone,
94 C: FnMut(&S, &[(L, V)]) -> V,
95 {
96 let mut cache = HashMap::new();
97 GameAnalysis::new(
98 &mut self.game,
99 move |game: &mut Impartial<S, F>, state: &S| {
100 memoized_game(
101 state,
102 &mut cache,
103 &mut HashSet::new(),
104 &mut |s| {
105 ControlFlow::Continue((
106 (game.moves)(s).into_iter().map(|n| (n.to, n.label)),
107 Vec::new(),
108 ))
109 },
110 &mut |_, moves| moves.next(),
111 &mut |values, label, value| {
112 values.push((label, value));
113 ControlFlow::Continue(())
114 },
115 &mut |s, values| combine(s, &values),
116 )
117 },
118 )
119 }
120}
121
122impl<'a, S, L, F, I> Misere<'a, Impartial<S, F>>
123where
124 S: Clone + Eq + Hash,
125 F: FnMut(&S) -> I,
126 I: IntoIterator<Item = Neighbor<S, L>>,
127{
128 pub fn outcome(self) -> GameAnalysis<'a, Impartial<S, F>, S, GameOutcome, true> {
129 GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
130 }
131}
132impl<'a, S, L, F, I> GameSum<'a, Impartial<S, F>>
133where
134 S: Clone + Eq + Hash,
135 F: FnMut(&S) -> I,
136 I: IntoIterator<Item = Neighbor<S, L>>,
137{
138 pub fn grundy(self) -> GameAnalysis<'a, Impartial<S, F>, [S], u64> {
139 GameAnalysis::new(self.game, Impartial::sum_grundy)
140 }
141}
142impl<'a, S, L, F, I, const MISERE: bool> GameSum<'a, Impartial<S, F>, MISERE>
143where
144 S: Clone + Eq + Hash,
145 F: FnMut(&S) -> I,
146 I: IntoIterator<Item = Neighbor<S, L>>,
147{
148 pub fn outcome(self) -> GameAnalysis<'a, Impartial<S, F>, [S], GameOutcome, MISERE> {
149 GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
150 }
151}
152
153impl<S, L, F, I, V, const MISERE: bool, E> GameAnalysis<'_, Impartial<S, F>, S, V, MISERE, E>
154where
155 F: FnMut(&S) -> I,
156 I: IntoIterator<Item = Neighbor<S, L>>,
157 E: FnMut(&mut Impartial<S, F>, &S) -> V,
158{
159 pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
160 (self.game.moves)(state)
161 .into_iter()
162 .map(|next| {
163 let value = self.eval(&next.to);
164 EvaluatedMove { next, value }
165 })
166 .collect()
167 }
168}
169
170impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, u64>
171where
172 S: Clone + Eq + Hash,
173 F: FnMut(&S) -> I,
174 I: IntoIterator<Item = Neighbor<S, L>>,
175{
176 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
177 self.game.winning_moves(state, false).collect()
178 }
179}
180impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, GameValue>
181where
182 S: Clone + Eq + Hash,
183 F: FnMut(&S) -> I,
184 I: IntoIterator<Item = Neighbor<S, L>>,
185{
186 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
187 self.game.winning_moves(state, false).collect()
188 }
189}
190impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, S, GameOutcome, MISERE>
191where
192 S: Clone + Eq + Hash,
193 F: FnMut(&S) -> I,
194 I: IntoIterator<Item = Neighbor<S, L>>,
195{
196 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
197 self.game.winning_moves(state, MISERE).collect()
198 }
199}
200
201#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
202impl<S, L, F, I, V, const MISERE: bool, E> GameAnalysis<'_, Impartial<S, F>, [S], V, MISERE, E>
203where
204 S: Clone,
205 F: FnMut(&S) -> I,
206 I: IntoIterator<Item = Neighbor<S, L>>,
207 E: FnMut(&mut Impartial<S, F>, &[S]) -> V,
208{
209 pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
210 let mut result = Vec::new();
211 for (i, component) in state.iter().enumerate() {
212 for next in (self.game.moves)(component) {
213 let mut to = state.to_vec();
214 to[i] = next.to;
215 let value = self.eval(&to);
216 result.push(EvaluatedMove {
217 next: Neighbor::new(to, (i, next.label)),
218 value,
219 });
220 }
221 }
222 result
223 }
224}
225#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
226impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, [S], u64>
227where
228 S: Clone + Eq + Hash,
229 F: FnMut(&S) -> I,
230 I: IntoIterator<Item = Neighbor<S, L>>,
231{
232 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
233 self.game.sum_winning_moves(state)
234 }
235}
236#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
237impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, [S], GameOutcome, MISERE>
238where
239 S: Clone + Eq + Hash,
240 F: FnMut(&S) -> I,
241 I: IntoIterator<Item = Neighbor<S, L>>,
242{
243 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
244 if let [single] = state {
245 return self
246 .game
247 .winning_moves(single, MISERE)
248 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
249 .collect();
250 }
251 if !MISERE {
252 return self.game.sum_winning_moves(state);
253 }
254 let mut result = Vec::new();
255 for (i, component) in state.iter().enumerate() {
256 for next in (self.game.moves)(component) {
257 let mut to = state.to_vec();
258 to[i] = next.to;
259 if self.eval(&to) == GameOutcome::Lose {
260 result.push(Neighbor::new(to, (i, next.label)));
261 }
262 }
263 }
264 result
265 }
266}
267
268impl<S, L, F, I> Impartial<S, F>
269where
270 S: Clone + Eq + Hash,
271 F: FnMut(&S) -> I,
272 I: IntoIterator<Item = Neighbor<S, L>>,
273{
274 fn grundy(&mut self, state: &S) -> u64 {
275 memoized_game(
276 state,
277 &mut self.grundy,
278 &mut HashSet::new(),
279 &mut |s| {
280 if self.outcomes[0].get(s) == Some(&false) {
281 return ControlFlow::Break(0);
282 }
283 let moves = (self.moves)(s).into_iter().map(|n| (n.to, ()));
284 ControlFlow::Continue((moves, Vec::new()))
285 },
286 &mut |_, moves| moves.next(),
287 &mut |values, (), value| {
288 values.push(value);
289 ControlFlow::Continue(())
290 },
291 &mut |_, values| game_mex(values),
292 )
293 }More examples
crates/competitive/src/algorithm/game_analyzer.rs (line 234)
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}crates/competitive/src/algorithm/game_analyzer/scoring.rs (lines 58-81)
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 }crates/competitive/src/algorithm/game_analyzer/partisan.rs (lines 125-146)
106 pub fn fold<V, C>(
107 &mut self,
108 mut combine: C,
109 ) -> GameAnalysis<
110 '_,
111 Partisan<S, FL, FR>,
112 S,
113 V,
114 false,
115 impl FnMut(&mut Partisan<S, FL, FR>, &S) -> V,
116 >
117 where
118 V: Clone,
119 C: FnMut(&S, &[(Player, L, V)]) -> V,
120 {
121 let mut cache = HashMap::new();
122 GameAnalysis::new(
123 &mut self.game,
124 move |game: &mut Partisan<S, FL, FR>, state: &S| {
125 memoized_game(
126 state,
127 &mut cache,
128 &mut HashSet::new(),
129 &mut |s| {
130 let moves = (game.left)(s)
131 .into_iter()
132 .map(|n| (n.to, (Player::Left, n.label)))
133 .chain(
134 (game.right)(s)
135 .into_iter()
136 .map(|n| (n.to, (Player::Right, n.label))),
137 );
138 ControlFlow::Continue((moves, Vec::new()))
139 },
140 &mut |_, moves| moves.next(),
141 &mut |values, (player, label), value| {
142 values.push((player, label, value));
143 ControlFlow::Continue(())
144 },
145 &mut |s, values| combine(s, &values),
146 )
147 },
148 )
149 }
150}
151impl<'a, S, L, FL, FR, IL, IR> Misere<'a, Partisan<S, FL, FR>>
152where
153 S: Clone + Eq + Hash,
154 FL: FnMut(&S) -> IL,
155 FR: FnMut(&S) -> IR,
156 IL: IntoIterator<Item = Neighbor<S, L>>,
157 IR: IntoIterator<Item = Neighbor<S, L>>,
158{
159 pub fn outcome(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, S, PartisanOutcome, true> {
160 GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
161 }
162}
163impl<'a, S, L, FL, FR, IL, IR> GameSum<'a, Partisan<S, FL, FR>>
164where
165 S: Clone + Eq + Hash,
166 FL: FnMut(&S) -> IL,
167 FR: FnMut(&S) -> IR,
168 IL: IntoIterator<Item = Neighbor<S, L>>,
169 IR: IntoIterator<Item = Neighbor<S, L>>,
170{
171 pub fn value(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, [S], GameValue> {
172 GameAnalysis::new(self.game, |g, state: &[S]| {
173 state.iter().map(|s| g.value(s)).sum()
174 })
175 }
176}
177impl<'a, S, L, FL, FR, IL, IR, const MISERE: bool> GameSum<'a, Partisan<S, FL, FR>, MISERE>
178where
179 S: Clone + Eq + Hash,
180 FL: FnMut(&S) -> IL,
181 FR: FnMut(&S) -> IR,
182 IL: IntoIterator<Item = Neighbor<S, L>>,
183 IR: IntoIterator<Item = Neighbor<S, L>>,
184{
185 /// Explores reachable sum positions, including the player to move.
186 /// Reuses cached sums of numbers, ups, nimbers and switches in normal play.
187 pub fn outcome(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, [S], PartisanOutcome, MISERE> {
188 GameAnalysis::new(self.game, |g, s| {
189 match (
190 g.sum_wins(s, Player::Left, MISERE),
191 g.sum_wins(s, Player::Right, MISERE),
192 ) {
193 (true, true) => PartisanOutcome::Next,
194 (false, false) => PartisanOutcome::Previous,
195 (true, false) => PartisanOutcome::Left,
196 (false, true) => PartisanOutcome::Right,
197 }
198 })
199 }
200}
201
202impl<S, L, FL, FR, IL, IR, V, const MISERE: bool, E>
203 GameAnalysis<'_, Partisan<S, FL, FR>, S, V, MISERE, E>
204where
205 FL: FnMut(&S) -> IL,
206 FR: FnMut(&S) -> IR,
207 IL: IntoIterator<Item = Neighbor<S, L>>,
208 IR: IntoIterator<Item = Neighbor<S, L>>,
209 E: FnMut(&mut Partisan<S, FL, FR>, &S) -> V,
210{
211 /// Values describe the destination game for both choices of starting player.
212 pub fn moves(&mut self, state: &S, player: Player) -> Vec<EvaluatedMove<S, L, V>> {
213 partisan_moves(&mut self.game.left, &mut self.game.right, state, player)
214 .map(|next| {
215 let value = self.eval(&next.to);
216 EvaluatedMove { next, value }
217 })
218 .collect()
219 }
220}
221
222impl<S, L, FL, FR, IL, IR> GameAnalysis<'_, Partisan<S, FL, FR>, S, GameValue>
223where
224 FL: FnMut(&S) -> IL,
225 FR: FnMut(&S) -> IR,
226 IL: IntoIterator<Item = Neighbor<S, L>>,
227 IR: IntoIterator<Item = Neighbor<S, L>>,
228{
229 pub fn compare(&mut self, left: &S, right: &S) -> Option<Ordering> {
230 self.eval(left).partial_cmp(&self.eval(right))
231 }
232
233 /// Undominated moves for the selected player; incomparable alternatives remain.
234 pub fn undominated_moves(&mut self, state: &S, player: Player) -> Vec<Neighbor<S, L>> {
235 let moves = self.moves(state, player);
236 let preferred = if player == Player::Left {
237 Ordering::Greater
238 } else {
239 Ordering::Less
240 };
241 let best = moves.iter().try_fold(None, |best, m| {
242 let (q, k, n) = m.value.as_number_up_nimber()?;
243 let pair = (q, k);
244 Some(Some(match best {
245 Some((previous, nimber)) => match pair.cmp(&previous) {
246 Ordering::Equal => (previous, if nimber == Some(n) { nimber } else { None }),
247 order if order == preferred => (pair, Some(n)),
248 _ => (previous, nimber),
249 },
250 None => (pair, Some(n)),
251 }))
252 });
253 if let Some(best) = best {
254 return moves
255 .into_iter()
256 .filter(|m| {
257 let (q, k, n) = m.value.as_number_up_nimber().unwrap();
258 best.is_some_and(|((b, l), nimber)| {
259 q == b && (k == l || k.abs_diff(l) == 1 && nimber == Some(n ^ 1))
260 })
261 })
262 .map(|m| m.next)
263 .collect();
264 }
265 let mut dominated = vec![false; moves.len()];
266 for i in 0..moves.len() {
267 if dominated[i] {
268 continue;
269 }
270 for j in i + 1..moves.len() {
271 if dominated[j] {
272 continue;
273 }
274 let order = moves[i].value.partial_cmp(&moves[j].value);
275 if order == Some(preferred) {
276 dominated[j] = true;
277 } else if order == Some(preferred.reverse()) {
278 dominated[i] = true;
279 break;
280 }
281 }
282 }
283 moves
284 .into_iter()
285 .zip(dominated)
286 .filter(|(_, d)| !d)
287 .map(|(m, _)| m.next)
288 .collect()
289 }
290}
291impl<S, L, FL, FR, IL, IR, const MISERE: bool>
292 GameAnalysis<'_, Partisan<S, FL, FR>, S, PartisanOutcome, MISERE>
293where
294 S: Clone + Eq + Hash,
295 FL: FnMut(&S) -> IL,
296 FR: FnMut(&S) -> IR,
297 IL: IntoIterator<Item = Neighbor<S, L>>,
298 IR: IntoIterator<Item = Neighbor<S, L>>,
299{
300 /// Whether the selected starting player can force a win.
301 pub fn wins(&mut self, state: &S, player: Player) -> bool {
302 self.game.wins(state, player, MISERE)
303 }
304
305 pub fn winning_moves(&mut self, state: &S, player: Player) -> Vec<Neighbor<S, L>> {
306 partisan_moves(&mut self.game.left, &mut self.game.right, state, player)
307 .filter(|next| !self.game.wins(&next.to, player.opponent(), MISERE))
308 .collect()
309 }
310}
311
312#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
313impl<S, L, FL, FR, IL, IR, V, const MISERE: bool, E>
314 GameAnalysis<'_, Partisan<S, FL, FR>, [S], V, MISERE, E>
315where
316 S: Clone,
317 FL: FnMut(&S) -> IL,
318 FR: FnMut(&S) -> IR,
319 IL: IntoIterator<Item = Neighbor<S, L>>,
320 IR: IntoIterator<Item = Neighbor<S, L>>,
321 E: FnMut(&mut Partisan<S, FL, FR>, &[S]) -> V,
322{
323 pub fn moves(
324 &mut self,
325 state: &[S],
326 player: Player,
327 ) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
328 let mut result = Vec::new();
329 for (i, component) in state.iter().enumerate() {
330 for next in partisan_moves(&mut self.game.left, &mut self.game.right, component, player)
331 {
332 let mut to = state.to_vec();
333 to[i] = next.to;
334 let value = self.eval(&to);
335 result.push(EvaluatedMove {
336 next: Neighbor::new(to, (i, next.label)),
337 value,
338 });
339 }
340 }
341 result
342 }
343}
344#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
345impl<S, L, FL, FR, IL, IR, const MISERE: bool>
346 GameAnalysis<'_, Partisan<S, FL, FR>, [S], PartisanOutcome, MISERE>
347where
348 S: Clone + Eq + Hash,
349 FL: FnMut(&S) -> IL,
350 FR: FnMut(&S) -> IR,
351 IL: IntoIterator<Item = Neighbor<S, L>>,
352 IR: IntoIterator<Item = Neighbor<S, L>>,
353{
354 /// Whether the selected starting player can force a win.
355 pub fn wins(&mut self, state: &[S], player: Player) -> bool {
356 self.game.sum_wins(state, player, MISERE)
357 }
358
359 pub fn winning_moves(
360 &mut self,
361 state: &[S],
362 player: Player,
363 ) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
364 let mut result = Vec::new();
365 for (i, component) in state.iter().enumerate() {
366 for next in partisan_moves(&mut self.game.left, &mut self.game.right, component, player)
367 {
368 let mut to = state.to_vec();
369 to[i] = next.to;
370 if !self.game.sum_wins(&to, player.opponent(), MISERE) {
371 result.push(Neighbor::new(to, (i, next.label)));
372 }
373 }
374 }
375 result
376 }
377}
378
379impl<S, L, FL, FR, IL, IR> Partisan<S, FL, FR>
380where
381 S: Clone + Eq + Hash,
382 FL: FnMut(&S) -> IL,
383 FR: FnMut(&S) -> IR,
384 IL: IntoIterator<Item = Neighbor<S, L>>,
385 IR: IntoIterator<Item = Neighbor<S, L>>,
386{
387 fn value(&mut self, state: &S) -> GameValue {
388 memoized_game(
389 state,
390 &mut self.values,
391 &mut HashSet::new(),
392 &mut |s| {
393 let moves = (self.left)(s)
394 .into_iter()
395 .map(|n| (n.to, Player::Left))
396 .chain((self.right)(s).into_iter().map(|n| (n.to, Player::Right)));
397 ControlFlow::Continue((moves, (Vec::new(), Vec::new())))
398 },
399 &mut |_, moves| moves.next(),
400 &mut |(left, right), player, value| {
401 if player == Player::Left {
402 left.push(value)
403 } else {
404 right.push(value)
405 }
406 ControlFlow::Continue(())
407 },
408 &mut |_, (left, right)| GameValue::from_options(left, right),
409 )
410 }