pub struct ImpartialGraph<'g, G>{
graph: &'g G,
index: Option<GraphIndex<G>>,
grundy: Vec<Option<u64>>,
outcomes: [GraphOutcomes; 2],
generalized_grundy: Vec<Option<(u64, usize)>>,
sums: GraphSums,
}Fields§
§graph: &'g G§index: Option<GraphIndex<G>>§grundy: Vec<Option<u64>>§outcomes: [GraphOutcomes; 2]§generalized_grundy: Vec<Option<(u64, usize)>>§sums: GraphSumsImplementations§
Source§impl<G> ImpartialGraph<'_, G>
impl<G> ImpartialGraph<'_, G>
Sourcefn grundy(&mut self, state: &G::Vertex) -> u64
fn grundy(&mut self, state: &G::Vertex) -> u64
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 69)
68 pub fn value(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, GameValue> {
69 GameAnalysis::new(&mut self.game, |g, s| GameValue::nimber(g.grundy(s)))
70 }
71
72 pub fn outcome(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, GameOutcome> {
73 GameAnalysis::new(&mut self.game, |g, s| g.outcome(s, false))
74 }
75
76 pub fn misere(&mut self) -> Misere<'_, ImpartialGraph<'g, G>> {
77 Misere {
78 game: &mut self.game,
79 }
80 }
81
82 pub fn sum(&mut self) -> GameSum<'_, ImpartialGraph<'g, G>> {
83 GameSum {
84 game: &mut self.game,
85 }
86 }
87
88 pub fn clear_cache(&mut self) {
89 self.game.grundy.clear();
90 self.game.outcomes = std::array::from_fn(|_| GraphOutcomes::default());
91 self.game.generalized_grundy.clear();
92 self.game.sums = GraphSums::default();
93 }
94}
95
96impl<'a, 'g, G> Misere<'a, ImpartialGraph<'g, G>>
97where
98 G: Graph + VertexMap<Option<usize>>,
99{
100 pub fn outcome(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, G::Vertex, GameOutcome, true> {
101 GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
102 }
103}
104impl<'a, 'g, G> GameSum<'a, ImpartialGraph<'g, G>>
105where
106 G: Graph + VertexMap<Option<usize>>,
107{
108 pub fn grundy(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], u64> {
109 GameAnalysis::new(self.game, ImpartialGraph::sum_grundy)
110 }
111}
112impl<'a, 'g, G, const MISERE: bool> GameSum<'a, ImpartialGraph<'g, G>, MISERE>
113where
114 G: Graph + VertexMap<Option<usize>>,
115{
116 /// Normal play combines generalized Grundy values, including cyclic positions.
117 /// Misere explores the sum graph, which can grow exponentially in the component count.
118 pub fn outcome(
119 self,
120 ) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], GameOutcome, MISERE> {
121 GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
122 }
123}
124
125impl<'g, S, L, G, V, const MISERE: bool, E> GameAnalysis<'_, ImpartialGraph<'g, G>, S, V, MISERE, E>
126where
127 S: Copy,
128 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
129 E: FnMut(&mut ImpartialGraph<'g, G>, &S) -> V,
130{
131 /// Values describe the destination position; outcomes are for the next player.
132 pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
133 self.game.prepare();
134 self.game.index_of(*state);
135 self.game
136 .graph
137 .neighbors(*state)
138 .map(|next| {
139 let value = self.eval(&next.to);
140 EvaluatedMove { next, value }
141 })
142 .collect()
143 }
144}
145impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
146where
147 S: Copy,
148 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
149{
150 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
151 self.game.prepare();
152 self.game.index_of(*state);
153 self.game
154 .graph
155 .neighbors(*state)
156 .filter(|next| self.eval(&next.to) == 0)
157 .collect()
158 }
159}
160impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
161where
162 S: Copy,
163 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
164{
165 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
166 self.game.prepare();
167 self.game.index_of(*state);
168 self.game
169 .graph
170 .neighbors(*state)
171 .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
172 .collect()
173 }
174}
175impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
176where
177 S: Copy,
178 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
179{
180 /// Moves to losing positions. To avoid cycling among winning positions,
181 /// repeatedly use `best_move`, which follows the retrograde proof.
182 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
183 self.game.prepare();
184 self.game.index_of(*state);
185 self.game
186 .graph
187 .neighbors(*state)
188 .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
189 .collect()
190 }
191
192 /// A move that guarantees termination when winning, or preserves a draw.
193 /// Returns `None` at terminal or losing positions.
194 pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
195 let outcome = self.eval(state);
196 if outcome == GameOutcome::Lose {
197 return None;
198 }
199 let game = &self.game;
200 let root = game.index_of(*state);
201 let result = &game.outcomes[usize::from(MISERE)];
202 let winner = result.winning[root];
203 for next in game.graph.neighbors(*state) {
204 let id = game.index_of(next.to);
205 if Some(id) == winner
206 || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
207 {
208 return Some(next);
209 }
210 }
211 None
212 }
213}
214
215#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
216impl<'g, S, L, G, V, const MISERE: bool, E>
217 GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
218where
219 S: Copy,
220 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
221 E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
222{
223 pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
224 self.eval(state);
225 let mut result = Vec::new();
226 for (i, &component) in state.iter().enumerate() {
227 for next in self.game.graph.neighbors(component) {
228 let mut to = state.to_vec();
229 to[i] = next.to;
230 let value = self.eval(&to);
231 result.push(EvaluatedMove {
232 next: Neighbor::new(to, (i, next.label)),
233 value,
234 });
235 }
236 }
237 result
238 }
239}
240#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
241impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
242where
243 S: Copy,
244 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
245{
246 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
247 let xor = self.eval(state);
248 let mut result = Vec::new();
249 if xor == 0 {
250 return result;
251 }
252 for (i, component) in state.iter().enumerate() {
253 let target = xor ^ self.game.grundy(component);
254 for next in self.game.graph.neighbors(*component) {
255 if self.game.grundy(&next.to) == target {
256 let mut to = state.to_vec();
257 to[i] = next.to;
258 result.push(Neighbor::new(to, (i, next.label)));
259 }
260 }
261 }
262 result
263 }
264}
265#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
266impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
267where
268 S: Copy,
269 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
270{
271 /// Moves to losing positions; use `best_move` to avoid cycling.
272 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
273 if state.is_empty() {
274 return Vec::new();
275 }
276 if let [single] = state {
277 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
278 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
279 g.outcome(s, MISERE)
280 });
281 return query
282 .winning_moves(single)
283 .into_iter()
284 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
285 .collect();
286 }
287 if self.eval(state) != GameOutcome::Win {
288 return Vec::new();
289 }
290 let mut indices = self.game.sum_indices(state);
291 let game = &self.game;
292 let mut xor = 0;
293 let mut infinite = 0;
294 if !MISERE {
295 for &v in &indices {
296 if let Some((value, _)) = game.generalized_grundy[v] {
297 xor ^= value;
298 } else {
299 infinite += 1;
300 }
301 }
302 }
303 let mut result = Vec::new();
304 for (i, &component) in state.iter().enumerate() {
305 let source = indices[i];
306 for next in game.graph.neighbors(component) {
307 indices[i] = game.index_of(next.to);
308 let wins = if MISERE {
309 let key =
310 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
311 game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
312 } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
313 match game.generalized_grundy[source] {
314 Some((g, _)) => infinite == 0 && xor ^ g == value,
315 None => infinite == 1 && xor == value,
316 }
317 } else {
318 false
319 };
320 if wins {
321 let mut to = state.to_vec();
322 to[i] = next.to;
323 result.push(Neighbor::new(to, (i, next.label)));
324 }
325 }
326 indices[i] = source;
327 }
328 result
329 }
330
331 /// A move that guarantees termination when winning, or preserves a draw.
332 /// Returns `None` at terminal or losing positions.
333 pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
334 if state.is_empty() {
335 return None;
336 }
337 if let [single] = state {
338 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
339 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
340 g.outcome(s, MISERE)
341 });
342 return query
343 .best_move(single)
344 .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
345 }
346 let outcome = self.eval(state);
347 if outcome == GameOutcome::Lose {
348 return None;
349 }
350 let mut indices = self.game.sum_indices(state);
351 let game = &self.game;
352 if MISERE {
353 let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
354 let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
355 for (i, &component) in state.iter().enumerate() {
356 let original = indices[i];
357 for next in game.graph.neighbors(component) {
358 indices[i] = game.index_of(next.to);
359 let key =
360 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
361 let id = game.sums.indices[&key];
362 if Some(id) == winner
363 || outcome == GameOutcome::Draw
364 && game.sums.outcomes.values[id] == GameOutcome::Draw
365 {
366 let mut to = state.to_vec();
367 to[i] = next.to;
368 return Some(Neighbor::new(to, (i, next.label)));
369 }
370 }
371 indices[i] = original;
372 }
373 return None;
374 }
375 let mut xor = 0;
376 let mut infinite = None;
377 let mut multiple = false;
378 for (i, &v) in indices.iter().enumerate() {
379 if let Some((value, _)) = game.generalized_grundy[v] {
380 xor ^= value;
381 } else if infinite.replace(i).is_some() {
382 multiple = true;
383 break;
384 }
385 }
386 if outcome == GameOutcome::Draw {
387 let i = infinite.unwrap();
388 let v = indices[i];
389 let edges = &game.index.as_ref().unwrap().edges;
390 let target = (!multiple).then(|| {
391 let values = edges[v]
392 .iter()
393 .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
394 .collect();
395 game_mex(values)
396 });
397 // Preserve two infinite components, or keep the finite XOR outside
398 // the remaining infinite component's finite follower values.
399 if target.is_none_or(|g| g == xor) {
400 let to = edges[v]
401 .iter()
402 .copied()
403 .find(|&u| {
404 game.generalized_grundy[u].is_none()
405 && target.is_none_or(|g| {
406 !edges[u].iter().any(|&w| {
407 game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
408 })
409 })
410 })
411 .unwrap();
412 let next = game
413 .graph
414 .neighbors(state[i])
415 .find(|next| game.index_of(next.to) == to)
416 .unwrap();
417 let mut to = state.to_vec();
418 to[i] = next.to;
419 return Some(Neighbor::new(to, (i, next.label)));
420 }
421 // The current finite XOR exceeds this mex, so a finite component
422 // can decrease it to the mex without moving the infinite component.
423 xor ^= target.unwrap();
424 infinite = None;
425 }
426 // Reduce the largest (Grundy, counter) pair, then minimize the
427 // destination counter so repeated winning moves terminate.
428 let (i, target) = if let Some(i) = infinite {
429 (i, xor)
430 } else {
431 let (i, (g, _)) = indices
432 .iter()
433 .enumerate()
434 .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
435 .filter(|(_, (g, _))| g ^ xor < *g)
436 .max_by_key(|&(i, g)| (g, Reverse(i)))?;
437 (i, g ^ xor)
438 };
439 let next = game
440 .graph
441 .neighbors(state[i])
442 .filter_map(|next| {
443 let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
444 (g == target).then_some((next, counter))
445 })
446 .min_by_key(|&(_, counter)| counter)?
447 .0;
448 let mut to = state.to_vec();
449 to[i] = next.to;
450 Some(Neighbor::new(to, (i, next.label)))
451 }
452}
453
454impl<G> ImpartialGraph<'_, G>
455where
456 G: Graph + VertexMap<Option<usize>>,
457{
458 fn grundy(&mut self, state: &G::Vertex) -> u64 {
459 self.prepare();
460 let root = self.index_of(*state);
461 let index = self.index.as_ref().unwrap();
462 self.grundy.resize(index.edges.len(), None);
463 if let Some(value) = self.grundy[root] {
464 return value;
465 }
466 let mut active = HashSet::from([root]);
467 let mut stack = vec![(root, index.edges[root].iter())];
468 while let Some((v, moves)) = stack.last_mut() {
469 if let Some(&u) = moves.next() {
470 if self.grundy[u].is_none() {
471 assert!(active.insert(u), "cycle in a finite game");
472 stack.push((u, index.edges[u].iter()));
473 }
474 } else {
475 let values = index.edges[*v]
476 .iter()
477 .map(|&u| self.grundy[u].unwrap())
478 .collect();
479 self.grundy[*v] = Some(game_mex(values));
480 active.remove(v);
481 stack.pop();
482 }
483 }
484 self.grundy[root].unwrap()
485 }
486
487 fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
488 self.prepare();
489 let index = self.index.as_ref().unwrap();
490 let outcome = &mut self.outcomes[usize::from(misere)];
491 if outcome.values.is_empty() {
492 outcome.extend(&index.edges, &index.reverse, misere);
493 }
494 self.outcomes[usize::from(misere)].values[self.index_of(*state)]
495 }
496
497 fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
498 state.iter().fold(0, |value, s| value ^ self.grundy(s))
499 }Sourcefn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome
fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 73)
72 pub fn outcome(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, GameOutcome> {
73 GameAnalysis::new(&mut self.game, |g, s| g.outcome(s, false))
74 }
75
76 pub fn misere(&mut self) -> Misere<'_, ImpartialGraph<'g, G>> {
77 Misere {
78 game: &mut self.game,
79 }
80 }
81
82 pub fn sum(&mut self) -> GameSum<'_, ImpartialGraph<'g, G>> {
83 GameSum {
84 game: &mut self.game,
85 }
86 }
87
88 pub fn clear_cache(&mut self) {
89 self.game.grundy.clear();
90 self.game.outcomes = std::array::from_fn(|_| GraphOutcomes::default());
91 self.game.generalized_grundy.clear();
92 self.game.sums = GraphSums::default();
93 }
94}
95
96impl<'a, 'g, G> Misere<'a, ImpartialGraph<'g, G>>
97where
98 G: Graph + VertexMap<Option<usize>>,
99{
100 pub fn outcome(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, G::Vertex, GameOutcome, true> {
101 GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
102 }
103}
104impl<'a, 'g, G> GameSum<'a, ImpartialGraph<'g, G>>
105where
106 G: Graph + VertexMap<Option<usize>>,
107{
108 pub fn grundy(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], u64> {
109 GameAnalysis::new(self.game, ImpartialGraph::sum_grundy)
110 }
111}
112impl<'a, 'g, G, const MISERE: bool> GameSum<'a, ImpartialGraph<'g, G>, MISERE>
113where
114 G: Graph + VertexMap<Option<usize>>,
115{
116 /// Normal play combines generalized Grundy values, including cyclic positions.
117 /// Misere explores the sum graph, which can grow exponentially in the component count.
118 pub fn outcome(
119 self,
120 ) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], GameOutcome, MISERE> {
121 GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
122 }
123}
124
125impl<'g, S, L, G, V, const MISERE: bool, E> GameAnalysis<'_, ImpartialGraph<'g, G>, S, V, MISERE, E>
126where
127 S: Copy,
128 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
129 E: FnMut(&mut ImpartialGraph<'g, G>, &S) -> V,
130{
131 /// Values describe the destination position; outcomes are for the next player.
132 pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
133 self.game.prepare();
134 self.game.index_of(*state);
135 self.game
136 .graph
137 .neighbors(*state)
138 .map(|next| {
139 let value = self.eval(&next.to);
140 EvaluatedMove { next, value }
141 })
142 .collect()
143 }
144}
145impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
146where
147 S: Copy,
148 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
149{
150 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
151 self.game.prepare();
152 self.game.index_of(*state);
153 self.game
154 .graph
155 .neighbors(*state)
156 .filter(|next| self.eval(&next.to) == 0)
157 .collect()
158 }
159}
160impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
161where
162 S: Copy,
163 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
164{
165 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
166 self.game.prepare();
167 self.game.index_of(*state);
168 self.game
169 .graph
170 .neighbors(*state)
171 .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
172 .collect()
173 }
174}
175impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
176where
177 S: Copy,
178 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
179{
180 /// Moves to losing positions. To avoid cycling among winning positions,
181 /// repeatedly use `best_move`, which follows the retrograde proof.
182 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
183 self.game.prepare();
184 self.game.index_of(*state);
185 self.game
186 .graph
187 .neighbors(*state)
188 .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
189 .collect()
190 }
191
192 /// A move that guarantees termination when winning, or preserves a draw.
193 /// Returns `None` at terminal or losing positions.
194 pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
195 let outcome = self.eval(state);
196 if outcome == GameOutcome::Lose {
197 return None;
198 }
199 let game = &self.game;
200 let root = game.index_of(*state);
201 let result = &game.outcomes[usize::from(MISERE)];
202 let winner = result.winning[root];
203 for next in game.graph.neighbors(*state) {
204 let id = game.index_of(next.to);
205 if Some(id) == winner
206 || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
207 {
208 return Some(next);
209 }
210 }
211 None
212 }
213}
214
215#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
216impl<'g, S, L, G, V, const MISERE: bool, E>
217 GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
218where
219 S: Copy,
220 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
221 E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
222{
223 pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
224 self.eval(state);
225 let mut result = Vec::new();
226 for (i, &component) in state.iter().enumerate() {
227 for next in self.game.graph.neighbors(component) {
228 let mut to = state.to_vec();
229 to[i] = next.to;
230 let value = self.eval(&to);
231 result.push(EvaluatedMove {
232 next: Neighbor::new(to, (i, next.label)),
233 value,
234 });
235 }
236 }
237 result
238 }
239}
240#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
241impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
242where
243 S: Copy,
244 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
245{
246 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
247 let xor = self.eval(state);
248 let mut result = Vec::new();
249 if xor == 0 {
250 return result;
251 }
252 for (i, component) in state.iter().enumerate() {
253 let target = xor ^ self.game.grundy(component);
254 for next in self.game.graph.neighbors(*component) {
255 if self.game.grundy(&next.to) == target {
256 let mut to = state.to_vec();
257 to[i] = next.to;
258 result.push(Neighbor::new(to, (i, next.label)));
259 }
260 }
261 }
262 result
263 }
264}
265#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
266impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
267where
268 S: Copy,
269 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
270{
271 /// Moves to losing positions; use `best_move` to avoid cycling.
272 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
273 if state.is_empty() {
274 return Vec::new();
275 }
276 if let [single] = state {
277 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
278 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
279 g.outcome(s, MISERE)
280 });
281 return query
282 .winning_moves(single)
283 .into_iter()
284 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
285 .collect();
286 }
287 if self.eval(state) != GameOutcome::Win {
288 return Vec::new();
289 }
290 let mut indices = self.game.sum_indices(state);
291 let game = &self.game;
292 let mut xor = 0;
293 let mut infinite = 0;
294 if !MISERE {
295 for &v in &indices {
296 if let Some((value, _)) = game.generalized_grundy[v] {
297 xor ^= value;
298 } else {
299 infinite += 1;
300 }
301 }
302 }
303 let mut result = Vec::new();
304 for (i, &component) in state.iter().enumerate() {
305 let source = indices[i];
306 for next in game.graph.neighbors(component) {
307 indices[i] = game.index_of(next.to);
308 let wins = if MISERE {
309 let key =
310 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
311 game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
312 } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
313 match game.generalized_grundy[source] {
314 Some((g, _)) => infinite == 0 && xor ^ g == value,
315 None => infinite == 1 && xor == value,
316 }
317 } else {
318 false
319 };
320 if wins {
321 let mut to = state.to_vec();
322 to[i] = next.to;
323 result.push(Neighbor::new(to, (i, next.label)));
324 }
325 }
326 indices[i] = source;
327 }
328 result
329 }
330
331 /// A move that guarantees termination when winning, or preserves a draw.
332 /// Returns `None` at terminal or losing positions.
333 pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
334 if state.is_empty() {
335 return None;
336 }
337 if let [single] = state {
338 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
339 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
340 g.outcome(s, MISERE)
341 });
342 return query
343 .best_move(single)
344 .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
345 }
346 let outcome = self.eval(state);
347 if outcome == GameOutcome::Lose {
348 return None;
349 }
350 let mut indices = self.game.sum_indices(state);
351 let game = &self.game;
352 if MISERE {
353 let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
354 let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
355 for (i, &component) in state.iter().enumerate() {
356 let original = indices[i];
357 for next in game.graph.neighbors(component) {
358 indices[i] = game.index_of(next.to);
359 let key =
360 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
361 let id = game.sums.indices[&key];
362 if Some(id) == winner
363 || outcome == GameOutcome::Draw
364 && game.sums.outcomes.values[id] == GameOutcome::Draw
365 {
366 let mut to = state.to_vec();
367 to[i] = next.to;
368 return Some(Neighbor::new(to, (i, next.label)));
369 }
370 }
371 indices[i] = original;
372 }
373 return None;
374 }
375 let mut xor = 0;
376 let mut infinite = None;
377 let mut multiple = false;
378 for (i, &v) in indices.iter().enumerate() {
379 if let Some((value, _)) = game.generalized_grundy[v] {
380 xor ^= value;
381 } else if infinite.replace(i).is_some() {
382 multiple = true;
383 break;
384 }
385 }
386 if outcome == GameOutcome::Draw {
387 let i = infinite.unwrap();
388 let v = indices[i];
389 let edges = &game.index.as_ref().unwrap().edges;
390 let target = (!multiple).then(|| {
391 let values = edges[v]
392 .iter()
393 .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
394 .collect();
395 game_mex(values)
396 });
397 // Preserve two infinite components, or keep the finite XOR outside
398 // the remaining infinite component's finite follower values.
399 if target.is_none_or(|g| g == xor) {
400 let to = edges[v]
401 .iter()
402 .copied()
403 .find(|&u| {
404 game.generalized_grundy[u].is_none()
405 && target.is_none_or(|g| {
406 !edges[u].iter().any(|&w| {
407 game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
408 })
409 })
410 })
411 .unwrap();
412 let next = game
413 .graph
414 .neighbors(state[i])
415 .find(|next| game.index_of(next.to) == to)
416 .unwrap();
417 let mut to = state.to_vec();
418 to[i] = next.to;
419 return Some(Neighbor::new(to, (i, next.label)));
420 }
421 // The current finite XOR exceeds this mex, so a finite component
422 // can decrease it to the mex without moving the infinite component.
423 xor ^= target.unwrap();
424 infinite = None;
425 }
426 // Reduce the largest (Grundy, counter) pair, then minimize the
427 // destination counter so repeated winning moves terminate.
428 let (i, target) = if let Some(i) = infinite {
429 (i, xor)
430 } else {
431 let (i, (g, _)) = indices
432 .iter()
433 .enumerate()
434 .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
435 .filter(|(_, (g, _))| g ^ xor < *g)
436 .max_by_key(|&(i, g)| (g, Reverse(i)))?;
437 (i, g ^ xor)
438 };
439 let next = game
440 .graph
441 .neighbors(state[i])
442 .filter_map(|next| {
443 let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
444 (g == target).then_some((next, counter))
445 })
446 .min_by_key(|&(_, counter)| counter)?
447 .0;
448 let mut to = state.to_vec();
449 to[i] = next.to;
450 Some(Neighbor::new(to, (i, next.label)))
451 }
452}
453
454impl<G> ImpartialGraph<'_, G>
455where
456 G: Graph + VertexMap<Option<usize>>,
457{
458 fn grundy(&mut self, state: &G::Vertex) -> u64 {
459 self.prepare();
460 let root = self.index_of(*state);
461 let index = self.index.as_ref().unwrap();
462 self.grundy.resize(index.edges.len(), None);
463 if let Some(value) = self.grundy[root] {
464 return value;
465 }
466 let mut active = HashSet::from([root]);
467 let mut stack = vec![(root, index.edges[root].iter())];
468 while let Some((v, moves)) = stack.last_mut() {
469 if let Some(&u) = moves.next() {
470 if self.grundy[u].is_none() {
471 assert!(active.insert(u), "cycle in a finite game");
472 stack.push((u, index.edges[u].iter()));
473 }
474 } else {
475 let values = index.edges[*v]
476 .iter()
477 .map(|&u| self.grundy[u].unwrap())
478 .collect();
479 self.grundy[*v] = Some(game_mex(values));
480 active.remove(v);
481 stack.pop();
482 }
483 }
484 self.grundy[root].unwrap()
485 }
486
487 fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
488 self.prepare();
489 let index = self.index.as_ref().unwrap();
490 let outcome = &mut self.outcomes[usize::from(misere)];
491 if outcome.values.is_empty() {
492 outcome.extend(&index.edges, &index.reverse, misere);
493 }
494 self.outcomes[usize::from(misere)].values[self.index_of(*state)]
495 }
496
497 fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
498 state.iter().fold(0, |value, s| value ^ self.grundy(s))
499 }
500
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64
Sourcefn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome
fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome
Sourcefn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome
fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 510)
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }Sourcefn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize>
fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize>
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 290)
272 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
273 if state.is_empty() {
274 return Vec::new();
275 }
276 if let [single] = state {
277 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
278 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
279 g.outcome(s, MISERE)
280 });
281 return query
282 .winning_moves(single)
283 .into_iter()
284 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
285 .collect();
286 }
287 if self.eval(state) != GameOutcome::Win {
288 return Vec::new();
289 }
290 let mut indices = self.game.sum_indices(state);
291 let game = &self.game;
292 let mut xor = 0;
293 let mut infinite = 0;
294 if !MISERE {
295 for &v in &indices {
296 if let Some((value, _)) = game.generalized_grundy[v] {
297 xor ^= value;
298 } else {
299 infinite += 1;
300 }
301 }
302 }
303 let mut result = Vec::new();
304 for (i, &component) in state.iter().enumerate() {
305 let source = indices[i];
306 for next in game.graph.neighbors(component) {
307 indices[i] = game.index_of(next.to);
308 let wins = if MISERE {
309 let key =
310 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
311 game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
312 } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
313 match game.generalized_grundy[source] {
314 Some((g, _)) => infinite == 0 && xor ^ g == value,
315 None => infinite == 1 && xor == value,
316 }
317 } else {
318 false
319 };
320 if wins {
321 let mut to = state.to_vec();
322 to[i] = next.to;
323 result.push(Neighbor::new(to, (i, next.label)));
324 }
325 }
326 indices[i] = source;
327 }
328 result
329 }
330
331 /// A move that guarantees termination when winning, or preserves a draw.
332 /// Returns `None` at terminal or losing positions.
333 pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
334 if state.is_empty() {
335 return None;
336 }
337 if let [single] = state {
338 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
339 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
340 g.outcome(s, MISERE)
341 });
342 return query
343 .best_move(single)
344 .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
345 }
346 let outcome = self.eval(state);
347 if outcome == GameOutcome::Lose {
348 return None;
349 }
350 let mut indices = self.game.sum_indices(state);
351 let game = &self.game;
352 if MISERE {
353 let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
354 let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
355 for (i, &component) in state.iter().enumerate() {
356 let original = indices[i];
357 for next in game.graph.neighbors(component) {
358 indices[i] = game.index_of(next.to);
359 let key =
360 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
361 let id = game.sums.indices[&key];
362 if Some(id) == winner
363 || outcome == GameOutcome::Draw
364 && game.sums.outcomes.values[id] == GameOutcome::Draw
365 {
366 let mut to = state.to_vec();
367 to[i] = next.to;
368 return Some(Neighbor::new(to, (i, next.label)));
369 }
370 }
371 indices[i] = original;
372 }
373 return None;
374 }
375 let mut xor = 0;
376 let mut infinite = None;
377 let mut multiple = false;
378 for (i, &v) in indices.iter().enumerate() {
379 if let Some((value, _)) = game.generalized_grundy[v] {
380 xor ^= value;
381 } else if infinite.replace(i).is_some() {
382 multiple = true;
383 break;
384 }
385 }
386 if outcome == GameOutcome::Draw {
387 let i = infinite.unwrap();
388 let v = indices[i];
389 let edges = &game.index.as_ref().unwrap().edges;
390 let target = (!multiple).then(|| {
391 let values = edges[v]
392 .iter()
393 .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
394 .collect();
395 game_mex(values)
396 });
397 // Preserve two infinite components, or keep the finite XOR outside
398 // the remaining infinite component's finite follower values.
399 if target.is_none_or(|g| g == xor) {
400 let to = edges[v]
401 .iter()
402 .copied()
403 .find(|&u| {
404 game.generalized_grundy[u].is_none()
405 && target.is_none_or(|g| {
406 !edges[u].iter().any(|&w| {
407 game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
408 })
409 })
410 })
411 .unwrap();
412 let next = game
413 .graph
414 .neighbors(state[i])
415 .find(|next| game.index_of(next.to) == to)
416 .unwrap();
417 let mut to = state.to_vec();
418 to[i] = next.to;
419 return Some(Neighbor::new(to, (i, next.label)));
420 }
421 // The current finite XOR exceeds this mex, so a finite component
422 // can decrease it to the mex without moving the infinite component.
423 xor ^= target.unwrap();
424 infinite = None;
425 }
426 // Reduce the largest (Grundy, counter) pair, then minimize the
427 // destination counter so repeated winning moves terminate.
428 let (i, target) = if let Some(i) = infinite {
429 (i, xor)
430 } else {
431 let (i, (g, _)) = indices
432 .iter()
433 .enumerate()
434 .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
435 .filter(|(_, (g, _))| g ^ xor < *g)
436 .max_by_key(|&(i, g)| (g, Reverse(i)))?;
437 (i, g ^ xor)
438 };
439 let next = game
440 .graph
441 .neighbors(state[i])
442 .filter_map(|next| {
443 let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
444 (g == target).then_some((next, counter))
445 })
446 .min_by_key(|&(_, counter)| counter)?
447 .0;
448 let mut to = state.to_vec();
449 to[i] = next.to;
450 Some(Neighbor::new(to, (i, next.label)))
451 }
452}
453
454impl<G> ImpartialGraph<'_, G>
455where
456 G: Graph + VertexMap<Option<usize>>,
457{
458 fn grundy(&mut self, state: &G::Vertex) -> u64 {
459 self.prepare();
460 let root = self.index_of(*state);
461 let index = self.index.as_ref().unwrap();
462 self.grundy.resize(index.edges.len(), None);
463 if let Some(value) = self.grundy[root] {
464 return value;
465 }
466 let mut active = HashSet::from([root]);
467 let mut stack = vec![(root, index.edges[root].iter())];
468 while let Some((v, moves)) = stack.last_mut() {
469 if let Some(&u) = moves.next() {
470 if self.grundy[u].is_none() {
471 assert!(active.insert(u), "cycle in a finite game");
472 stack.push((u, index.edges[u].iter()));
473 }
474 } else {
475 let values = index.edges[*v]
476 .iter()
477 .map(|&u| self.grundy[u].unwrap())
478 .collect();
479 self.grundy[*v] = Some(game_mex(values));
480 active.remove(v);
481 stack.pop();
482 }
483 }
484 self.grundy[root].unwrap()
485 }
486
487 fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
488 self.prepare();
489 let index = self.index.as_ref().unwrap();
490 let outcome = &mut self.outcomes[usize::from(misere)];
491 if outcome.values.is_empty() {
492 outcome.extend(&index.edges, &index.reverse, misere);
493 }
494 self.outcomes[usize::from(misere)].values[self.index_of(*state)]
495 }
496
497 fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
498 state.iter().fold(0, |value, s| value ^ self.grundy(s))
499 }
500
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }Sourcefn prepare(&mut self)
fn prepare(&mut self)
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 133)
132 pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
133 self.game.prepare();
134 self.game.index_of(*state);
135 self.game
136 .graph
137 .neighbors(*state)
138 .map(|next| {
139 let value = self.eval(&next.to);
140 EvaluatedMove { next, value }
141 })
142 .collect()
143 }
144}
145impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
146where
147 S: Copy,
148 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
149{
150 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
151 self.game.prepare();
152 self.game.index_of(*state);
153 self.game
154 .graph
155 .neighbors(*state)
156 .filter(|next| self.eval(&next.to) == 0)
157 .collect()
158 }
159}
160impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
161where
162 S: Copy,
163 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
164{
165 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
166 self.game.prepare();
167 self.game.index_of(*state);
168 self.game
169 .graph
170 .neighbors(*state)
171 .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
172 .collect()
173 }
174}
175impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
176where
177 S: Copy,
178 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
179{
180 /// Moves to losing positions. To avoid cycling among winning positions,
181 /// repeatedly use `best_move`, which follows the retrograde proof.
182 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
183 self.game.prepare();
184 self.game.index_of(*state);
185 self.game
186 .graph
187 .neighbors(*state)
188 .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
189 .collect()
190 }
191
192 /// A move that guarantees termination when winning, or preserves a draw.
193 /// Returns `None` at terminal or losing positions.
194 pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
195 let outcome = self.eval(state);
196 if outcome == GameOutcome::Lose {
197 return None;
198 }
199 let game = &self.game;
200 let root = game.index_of(*state);
201 let result = &game.outcomes[usize::from(MISERE)];
202 let winner = result.winning[root];
203 for next in game.graph.neighbors(*state) {
204 let id = game.index_of(next.to);
205 if Some(id) == winner
206 || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
207 {
208 return Some(next);
209 }
210 }
211 None
212 }
213}
214
215#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
216impl<'g, S, L, G, V, const MISERE: bool, E>
217 GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
218where
219 S: Copy,
220 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
221 E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
222{
223 pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
224 self.eval(state);
225 let mut result = Vec::new();
226 for (i, &component) in state.iter().enumerate() {
227 for next in self.game.graph.neighbors(component) {
228 let mut to = state.to_vec();
229 to[i] = next.to;
230 let value = self.eval(&to);
231 result.push(EvaluatedMove {
232 next: Neighbor::new(to, (i, next.label)),
233 value,
234 });
235 }
236 }
237 result
238 }
239}
240#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
241impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
242where
243 S: Copy,
244 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
245{
246 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
247 let xor = self.eval(state);
248 let mut result = Vec::new();
249 if xor == 0 {
250 return result;
251 }
252 for (i, component) in state.iter().enumerate() {
253 let target = xor ^ self.game.grundy(component);
254 for next in self.game.graph.neighbors(*component) {
255 if self.game.grundy(&next.to) == target {
256 let mut to = state.to_vec();
257 to[i] = next.to;
258 result.push(Neighbor::new(to, (i, next.label)));
259 }
260 }
261 }
262 result
263 }
264}
265#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
266impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
267where
268 S: Copy,
269 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
270{
271 /// Moves to losing positions; use `best_move` to avoid cycling.
272 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
273 if state.is_empty() {
274 return Vec::new();
275 }
276 if let [single] = state {
277 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
278 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
279 g.outcome(s, MISERE)
280 });
281 return query
282 .winning_moves(single)
283 .into_iter()
284 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
285 .collect();
286 }
287 if self.eval(state) != GameOutcome::Win {
288 return Vec::new();
289 }
290 let mut indices = self.game.sum_indices(state);
291 let game = &self.game;
292 let mut xor = 0;
293 let mut infinite = 0;
294 if !MISERE {
295 for &v in &indices {
296 if let Some((value, _)) = game.generalized_grundy[v] {
297 xor ^= value;
298 } else {
299 infinite += 1;
300 }
301 }
302 }
303 let mut result = Vec::new();
304 for (i, &component) in state.iter().enumerate() {
305 let source = indices[i];
306 for next in game.graph.neighbors(component) {
307 indices[i] = game.index_of(next.to);
308 let wins = if MISERE {
309 let key =
310 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
311 game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
312 } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
313 match game.generalized_grundy[source] {
314 Some((g, _)) => infinite == 0 && xor ^ g == value,
315 None => infinite == 1 && xor == value,
316 }
317 } else {
318 false
319 };
320 if wins {
321 let mut to = state.to_vec();
322 to[i] = next.to;
323 result.push(Neighbor::new(to, (i, next.label)));
324 }
325 }
326 indices[i] = source;
327 }
328 result
329 }
330
331 /// A move that guarantees termination when winning, or preserves a draw.
332 /// Returns `None` at terminal or losing positions.
333 pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
334 if state.is_empty() {
335 return None;
336 }
337 if let [single] = state {
338 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
339 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
340 g.outcome(s, MISERE)
341 });
342 return query
343 .best_move(single)
344 .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
345 }
346 let outcome = self.eval(state);
347 if outcome == GameOutcome::Lose {
348 return None;
349 }
350 let mut indices = self.game.sum_indices(state);
351 let game = &self.game;
352 if MISERE {
353 let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
354 let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
355 for (i, &component) in state.iter().enumerate() {
356 let original = indices[i];
357 for next in game.graph.neighbors(component) {
358 indices[i] = game.index_of(next.to);
359 let key =
360 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
361 let id = game.sums.indices[&key];
362 if Some(id) == winner
363 || outcome == GameOutcome::Draw
364 && game.sums.outcomes.values[id] == GameOutcome::Draw
365 {
366 let mut to = state.to_vec();
367 to[i] = next.to;
368 return Some(Neighbor::new(to, (i, next.label)));
369 }
370 }
371 indices[i] = original;
372 }
373 return None;
374 }
375 let mut xor = 0;
376 let mut infinite = None;
377 let mut multiple = false;
378 for (i, &v) in indices.iter().enumerate() {
379 if let Some((value, _)) = game.generalized_grundy[v] {
380 xor ^= value;
381 } else if infinite.replace(i).is_some() {
382 multiple = true;
383 break;
384 }
385 }
386 if outcome == GameOutcome::Draw {
387 let i = infinite.unwrap();
388 let v = indices[i];
389 let edges = &game.index.as_ref().unwrap().edges;
390 let target = (!multiple).then(|| {
391 let values = edges[v]
392 .iter()
393 .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
394 .collect();
395 game_mex(values)
396 });
397 // Preserve two infinite components, or keep the finite XOR outside
398 // the remaining infinite component's finite follower values.
399 if target.is_none_or(|g| g == xor) {
400 let to = edges[v]
401 .iter()
402 .copied()
403 .find(|&u| {
404 game.generalized_grundy[u].is_none()
405 && target.is_none_or(|g| {
406 !edges[u].iter().any(|&w| {
407 game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
408 })
409 })
410 })
411 .unwrap();
412 let next = game
413 .graph
414 .neighbors(state[i])
415 .find(|next| game.index_of(next.to) == to)
416 .unwrap();
417 let mut to = state.to_vec();
418 to[i] = next.to;
419 return Some(Neighbor::new(to, (i, next.label)));
420 }
421 // The current finite XOR exceeds this mex, so a finite component
422 // can decrease it to the mex without moving the infinite component.
423 xor ^= target.unwrap();
424 infinite = None;
425 }
426 // Reduce the largest (Grundy, counter) pair, then minimize the
427 // destination counter so repeated winning moves terminate.
428 let (i, target) = if let Some(i) = infinite {
429 (i, xor)
430 } else {
431 let (i, (g, _)) = indices
432 .iter()
433 .enumerate()
434 .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
435 .filter(|(_, (g, _))| g ^ xor < *g)
436 .max_by_key(|&(i, g)| (g, Reverse(i)))?;
437 (i, g ^ xor)
438 };
439 let next = game
440 .graph
441 .neighbors(state[i])
442 .filter_map(|next| {
443 let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
444 (g == target).then_some((next, counter))
445 })
446 .min_by_key(|&(_, counter)| counter)?
447 .0;
448 let mut to = state.to_vec();
449 to[i] = next.to;
450 Some(Neighbor::new(to, (i, next.label)))
451 }
452}
453
454impl<G> ImpartialGraph<'_, G>
455where
456 G: Graph + VertexMap<Option<usize>>,
457{
458 fn grundy(&mut self, state: &G::Vertex) -> u64 {
459 self.prepare();
460 let root = self.index_of(*state);
461 let index = self.index.as_ref().unwrap();
462 self.grundy.resize(index.edges.len(), None);
463 if let Some(value) = self.grundy[root] {
464 return value;
465 }
466 let mut active = HashSet::from([root]);
467 let mut stack = vec![(root, index.edges[root].iter())];
468 while let Some((v, moves)) = stack.last_mut() {
469 if let Some(&u) = moves.next() {
470 if self.grundy[u].is_none() {
471 assert!(active.insert(u), "cycle in a finite game");
472 stack.push((u, index.edges[u].iter()));
473 }
474 } else {
475 let values = index.edges[*v]
476 .iter()
477 .map(|&u| self.grundy[u].unwrap())
478 .collect();
479 self.grundy[*v] = Some(game_mex(values));
480 active.remove(v);
481 stack.pop();
482 }
483 }
484 self.grundy[root].unwrap()
485 }
486
487 fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
488 self.prepare();
489 let index = self.index.as_ref().unwrap();
490 let outcome = &mut self.outcomes[usize::from(misere)];
491 if outcome.values.is_empty() {
492 outcome.extend(&index.edges, &index.reverse, misere);
493 }
494 self.outcomes[usize::from(misere)].values[self.index_of(*state)]
495 }
496
497 fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
498 state.iter().fold(0, |value, s| value ^ self.grundy(s))
499 }
500
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }
516
517 fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome {
518 let mut xor = 0;
519 let mut infinite = None;
520 for &v in state {
521 if let Some((value, _)) = self.generalized_grundy[v] {
522 xor ^= value;
523 } else if infinite.replace(v).is_some() {
524 return GameOutcome::Draw;
525 }
526 }
527 if let Some(v) = infinite {
528 let can_win = self.index.as_ref().unwrap().edges[v]
529 .iter()
530 .any(|&u| self.generalized_grundy[u].is_some_and(|(value, _)| value == xor));
531 if can_win {
532 GameOutcome::Win
533 } else {
534 GameOutcome::Draw
535 }
536 } else if xor == 0 {
537 GameOutcome::Lose
538 } else {
539 GameOutcome::Win
540 }
541 }
542
543 fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize> {
544 self.prepare();
545 state.iter().map(|&s| self.index_of(s)).collect()
546 }Sourcefn index_of(&self, v: G::Vertex) -> usize
fn index_of(&self, v: G::Vertex) -> usize
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 134)
132 pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
133 self.game.prepare();
134 self.game.index_of(*state);
135 self.game
136 .graph
137 .neighbors(*state)
138 .map(|next| {
139 let value = self.eval(&next.to);
140 EvaluatedMove { next, value }
141 })
142 .collect()
143 }
144}
145impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
146where
147 S: Copy,
148 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
149{
150 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
151 self.game.prepare();
152 self.game.index_of(*state);
153 self.game
154 .graph
155 .neighbors(*state)
156 .filter(|next| self.eval(&next.to) == 0)
157 .collect()
158 }
159}
160impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
161where
162 S: Copy,
163 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
164{
165 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
166 self.game.prepare();
167 self.game.index_of(*state);
168 self.game
169 .graph
170 .neighbors(*state)
171 .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
172 .collect()
173 }
174}
175impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
176where
177 S: Copy,
178 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
179{
180 /// Moves to losing positions. To avoid cycling among winning positions,
181 /// repeatedly use `best_move`, which follows the retrograde proof.
182 pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
183 self.game.prepare();
184 self.game.index_of(*state);
185 self.game
186 .graph
187 .neighbors(*state)
188 .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
189 .collect()
190 }
191
192 /// A move that guarantees termination when winning, or preserves a draw.
193 /// Returns `None` at terminal or losing positions.
194 pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
195 let outcome = self.eval(state);
196 if outcome == GameOutcome::Lose {
197 return None;
198 }
199 let game = &self.game;
200 let root = game.index_of(*state);
201 let result = &game.outcomes[usize::from(MISERE)];
202 let winner = result.winning[root];
203 for next in game.graph.neighbors(*state) {
204 let id = game.index_of(next.to);
205 if Some(id) == winner
206 || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
207 {
208 return Some(next);
209 }
210 }
211 None
212 }
213}
214
215#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
216impl<'g, S, L, G, V, const MISERE: bool, E>
217 GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
218where
219 S: Copy,
220 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
221 E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
222{
223 pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
224 self.eval(state);
225 let mut result = Vec::new();
226 for (i, &component) in state.iter().enumerate() {
227 for next in self.game.graph.neighbors(component) {
228 let mut to = state.to_vec();
229 to[i] = next.to;
230 let value = self.eval(&to);
231 result.push(EvaluatedMove {
232 next: Neighbor::new(to, (i, next.label)),
233 value,
234 });
235 }
236 }
237 result
238 }
239}
240#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
241impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
242where
243 S: Copy,
244 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
245{
246 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
247 let xor = self.eval(state);
248 let mut result = Vec::new();
249 if xor == 0 {
250 return result;
251 }
252 for (i, component) in state.iter().enumerate() {
253 let target = xor ^ self.game.grundy(component);
254 for next in self.game.graph.neighbors(*component) {
255 if self.game.grundy(&next.to) == target {
256 let mut to = state.to_vec();
257 to[i] = next.to;
258 result.push(Neighbor::new(to, (i, next.label)));
259 }
260 }
261 }
262 result
263 }
264}
265#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
266impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
267where
268 S: Copy,
269 G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
270{
271 /// Moves to losing positions; use `best_move` to avoid cycling.
272 pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
273 if state.is_empty() {
274 return Vec::new();
275 }
276 if let [single] = state {
277 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
278 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
279 g.outcome(s, MISERE)
280 });
281 return query
282 .winning_moves(single)
283 .into_iter()
284 .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
285 .collect();
286 }
287 if self.eval(state) != GameOutcome::Win {
288 return Vec::new();
289 }
290 let mut indices = self.game.sum_indices(state);
291 let game = &self.game;
292 let mut xor = 0;
293 let mut infinite = 0;
294 if !MISERE {
295 for &v in &indices {
296 if let Some((value, _)) = game.generalized_grundy[v] {
297 xor ^= value;
298 } else {
299 infinite += 1;
300 }
301 }
302 }
303 let mut result = Vec::new();
304 for (i, &component) in state.iter().enumerate() {
305 let source = indices[i];
306 for next in game.graph.neighbors(component) {
307 indices[i] = game.index_of(next.to);
308 let wins = if MISERE {
309 let key =
310 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
311 game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
312 } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
313 match game.generalized_grundy[source] {
314 Some((g, _)) => infinite == 0 && xor ^ g == value,
315 None => infinite == 1 && xor == value,
316 }
317 } else {
318 false
319 };
320 if wins {
321 let mut to = state.to_vec();
322 to[i] = next.to;
323 result.push(Neighbor::new(to, (i, next.label)));
324 }
325 }
326 indices[i] = source;
327 }
328 result
329 }
330
331 /// A move that guarantees termination when winning, or preserves a draw.
332 /// Returns `None` at terminal or losing positions.
333 pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
334 if state.is_empty() {
335 return None;
336 }
337 if let [single] = state {
338 let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
339 GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
340 g.outcome(s, MISERE)
341 });
342 return query
343 .best_move(single)
344 .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
345 }
346 let outcome = self.eval(state);
347 if outcome == GameOutcome::Lose {
348 return None;
349 }
350 let mut indices = self.game.sum_indices(state);
351 let game = &self.game;
352 if MISERE {
353 let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
354 let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
355 for (i, &component) in state.iter().enumerate() {
356 let original = indices[i];
357 for next in game.graph.neighbors(component) {
358 indices[i] = game.index_of(next.to);
359 let key =
360 GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
361 let id = game.sums.indices[&key];
362 if Some(id) == winner
363 || outcome == GameOutcome::Draw
364 && game.sums.outcomes.values[id] == GameOutcome::Draw
365 {
366 let mut to = state.to_vec();
367 to[i] = next.to;
368 return Some(Neighbor::new(to, (i, next.label)));
369 }
370 }
371 indices[i] = original;
372 }
373 return None;
374 }
375 let mut xor = 0;
376 let mut infinite = None;
377 let mut multiple = false;
378 for (i, &v) in indices.iter().enumerate() {
379 if let Some((value, _)) = game.generalized_grundy[v] {
380 xor ^= value;
381 } else if infinite.replace(i).is_some() {
382 multiple = true;
383 break;
384 }
385 }
386 if outcome == GameOutcome::Draw {
387 let i = infinite.unwrap();
388 let v = indices[i];
389 let edges = &game.index.as_ref().unwrap().edges;
390 let target = (!multiple).then(|| {
391 let values = edges[v]
392 .iter()
393 .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
394 .collect();
395 game_mex(values)
396 });
397 // Preserve two infinite components, or keep the finite XOR outside
398 // the remaining infinite component's finite follower values.
399 if target.is_none_or(|g| g == xor) {
400 let to = edges[v]
401 .iter()
402 .copied()
403 .find(|&u| {
404 game.generalized_grundy[u].is_none()
405 && target.is_none_or(|g| {
406 !edges[u].iter().any(|&w| {
407 game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
408 })
409 })
410 })
411 .unwrap();
412 let next = game
413 .graph
414 .neighbors(state[i])
415 .find(|next| game.index_of(next.to) == to)
416 .unwrap();
417 let mut to = state.to_vec();
418 to[i] = next.to;
419 return Some(Neighbor::new(to, (i, next.label)));
420 }
421 // The current finite XOR exceeds this mex, so a finite component
422 // can decrease it to the mex without moving the infinite component.
423 xor ^= target.unwrap();
424 infinite = None;
425 }
426 // Reduce the largest (Grundy, counter) pair, then minimize the
427 // destination counter so repeated winning moves terminate.
428 let (i, target) = if let Some(i) = infinite {
429 (i, xor)
430 } else {
431 let (i, (g, _)) = indices
432 .iter()
433 .enumerate()
434 .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
435 .filter(|(_, (g, _))| g ^ xor < *g)
436 .max_by_key(|&(i, g)| (g, Reverse(i)))?;
437 (i, g ^ xor)
438 };
439 let next = game
440 .graph
441 .neighbors(state[i])
442 .filter_map(|next| {
443 let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
444 (g == target).then_some((next, counter))
445 })
446 .min_by_key(|&(_, counter)| counter)?
447 .0;
448 let mut to = state.to_vec();
449 to[i] = next.to;
450 Some(Neighbor::new(to, (i, next.label)))
451 }
452}
453
454impl<G> ImpartialGraph<'_, G>
455where
456 G: Graph + VertexMap<Option<usize>>,
457{
458 fn grundy(&mut self, state: &G::Vertex) -> u64 {
459 self.prepare();
460 let root = self.index_of(*state);
461 let index = self.index.as_ref().unwrap();
462 self.grundy.resize(index.edges.len(), None);
463 if let Some(value) = self.grundy[root] {
464 return value;
465 }
466 let mut active = HashSet::from([root]);
467 let mut stack = vec![(root, index.edges[root].iter())];
468 while let Some((v, moves)) = stack.last_mut() {
469 if let Some(&u) = moves.next() {
470 if self.grundy[u].is_none() {
471 assert!(active.insert(u), "cycle in a finite game");
472 stack.push((u, index.edges[u].iter()));
473 }
474 } else {
475 let values = index.edges[*v]
476 .iter()
477 .map(|&u| self.grundy[u].unwrap())
478 .collect();
479 self.grundy[*v] = Some(game_mex(values));
480 active.remove(v);
481 stack.pop();
482 }
483 }
484 self.grundy[root].unwrap()
485 }
486
487 fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
488 self.prepare();
489 let index = self.index.as_ref().unwrap();
490 let outcome = &mut self.outcomes[usize::from(misere)];
491 if outcome.values.is_empty() {
492 outcome.extend(&index.edges, &index.reverse, misere);
493 }
494 self.outcomes[usize::from(misere)].values[self.index_of(*state)]
495 }
496
497 fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
498 state.iter().fold(0, |value, s| value ^ self.grundy(s))
499 }
500
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }
516
517 fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome {
518 let mut xor = 0;
519 let mut infinite = None;
520 for &v in state {
521 if let Some((value, _)) = self.generalized_grundy[v] {
522 xor ^= value;
523 } else if infinite.replace(v).is_some() {
524 return GameOutcome::Draw;
525 }
526 }
527 if let Some(v) = infinite {
528 let can_win = self.index.as_ref().unwrap().edges[v]
529 .iter()
530 .any(|&u| self.generalized_grundy[u].is_some_and(|(value, _)| value == xor));
531 if can_win {
532 GameOutcome::Win
533 } else {
534 GameOutcome::Draw
535 }
536 } else if xor == 0 {
537 GameOutcome::Lose
538 } else {
539 GameOutcome::Win
540 }
541 }
542
543 fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize> {
544 self.prepare();
545 state.iter().map(|&s| self.index_of(s)).collect()
546 }Sourcefn solve_generalized_grundy(&mut self)
fn solve_generalized_grundy(&mut self)
Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/graph.rs (line 509)
501 fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502 match state {
503 [] => return GameOutcome::from_win(misere),
504 [single] => return self.outcome(single, misere),
505 _ => {}
506 }
507 let indices = self.sum_indices(state);
508 if !misere {
509 self.solve_generalized_grundy();
510 return self.sum_normal_outcome(&indices);
511 }
512 let edges = &self.index.as_ref().unwrap().edges;
513 let root = self.sums.prepare(indices, edges);
514 self.sums.outcomes.values[root]
515 }Auto Trait Implementations§
impl<'g, G> Forget for ImpartialGraph<'g, G>
impl<'g, G> Freeze for ImpartialGraph<'g, G>
impl<'g, G> Move for ImpartialGraph<'g, G>
impl<'g, G> RefUnwindSafe for ImpartialGraph<'g, G>
impl<'g, G> Send for ImpartialGraph<'g, G>
impl<'g, G> Sync for ImpartialGraph<'g, G>
impl<'g, G> Unpin for ImpartialGraph<'g, G>
impl<'g, G> UnsafeUnpin for ImpartialGraph<'g, G>
impl<'g, G> UnwindSafe for ImpartialGraph<'g, G>
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more