pub fn memoized_wins<S, I>(
state: &S,
cache: &mut HashMap<S, bool>,
expand: impl FnMut(&S) -> ControlFlow<bool, I>,
advance: impl FnMut(&S, &mut I) -> Option<S>,
misere: bool,
) -> boolExamples found in repository?
crates/competitive/src/algorithm/game_analyzer/impartial.rs (lines 296-308)
295 fn outcome(&mut self, state: &S, misere: bool) -> GameOutcome {
296 let win = memoized_wins(
297 state,
298 &mut self.outcomes[usize::from(misere)],
299 |s| {
300 if !misere && let Some(&value) = self.grundy.get(s) {
301 return ControlFlow::Break(value != 0);
302 }
303 let moves = (self.moves)(s).into_iter().map(|n| n.to);
304 ControlFlow::Continue(moves)
305 },
306 |_, moves| moves.next(),
307 misere,
308 );
309 GameOutcome::from_win(win)
310 }
311
312 fn winning_moves(&mut self, state: &S, misere: bool) -> impl Iterator<Item = Neighbor<S, L>> {
313 (self.moves)(state).into_iter().filter(move |next| {
314 if !misere && let Some(&value) = self.grundy.get(&next.to) {
315 value == 0
316 } else {
317 self.outcome(&next.to, misere) == GameOutcome::Lose
318 }
319 })
320 }
321
322 fn sum_grundy(&mut self, state: &[S]) -> u64 {
323 match state {
324 [] => return 0,
325 [single] => return self.grundy(single),
326 _ => {}
327 }
328 let (xor, odd) = self.reduce_sum(state);
329 odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s))
330 }
331
332 #[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
333 fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
334 let xor = self.sum_grundy(state);
335 let mut result = Vec::new();
336 if xor == 0 {
337 return result;
338 }
339 for (i, component) in state.iter().enumerate() {
340 let target = xor ^ self.grundy(component);
341 for next in (self.moves)(component) {
342 if self.grundy(&next.to) == target {
343 let mut to = state.to_vec();
344 to[i] = next.to;
345 result.push(Neighbor::new(to, (i, next.label)));
346 }
347 }
348 }
349 result
350 }
351
352 fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome {
353 if state.is_empty() {
354 return GameOutcome::from_win(misere);
355 }
356 if let [single] = state {
357 return self.outcome(single, misere);
358 }
359 let win = if misere {
360 if let Some(&win) = self.sums.get(state) {
361 win
362 } else {
363 memoized_wins(
364 &canonical_sum(state.to_vec(), &mut self.sum_ids),
365 &mut self.sums,
366 |_| ControlFlow::Continue((0, None)),
367 |s, (i, moves)| {
368 while *i < s.len() {
369 if *i != 0 && s[*i - 1] == s[*i] {
370 *i += 1;
371 continue;
372 }
373 let iterator =
374 moves.get_or_insert_with(|| (self.moves)(&s[*i]).into_iter());
375 if let Some(next) = iterator.next() {
376 let mut to = s.clone();
377 to[*i] = next.to;
378 return Some(canonical_sum(to, &mut self.sum_ids));
379 }
380 *i += 1;
381 *moves = None;
382 }
383 None
384 },
385 true,
386 )
387 }
388 } else {
389 let (xor, odd) = self.reduce_sum(state);
390 if xor == 0 && odd.len() == 1 {
391 return self.outcome(odd.into_iter().next().unwrap(), false);
392 }
393 odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s)) != 0
394 };
395 GameOutcome::from_win(win)
396 }More examples
crates/competitive/src/algorithm/game_analyzer/partisan.rs (lines 426-440)
424 fn wins(&mut self, state: &S, player: Player, misere: bool) -> bool {
425 let key = (state.clone(), player);
426 memoized_wins(
427 &key,
428 &mut self.outcomes[usize::from(misere)],
429 |(s, p)| {
430 if !misere && let Some(value) = self.values.get(s) {
431 return ControlFlow::Break(value.wins(*p));
432 }
433 let next_player = p.opponent();
434 let moves = partisan_moves(&mut self.left, &mut self.right, s, *p)
435 .map(move |n| (n.to, next_player));
436 ControlFlow::Continue(moves)
437 },
438 |_, moves| moves.next(),
439 misere,
440 )
441 }
442
443 fn sum_wins(&mut self, state: &[S], player: Player, misere: bool) -> bool {
444 match state {
445 [] => return misere,
446 [single] => return self.wins(single, player, misere),
447 _ => {}
448 }
449 let mut normalize = |mut state: Vec<S>| {
450 if !misere {
451 state.retain(|s| {
452 if let Some(value) = self.values.get(s) {
453 return value.as_nimber() != Some(0);
454 }
455 let mut key = (s.clone(), Player::Left);
456 if self.outcomes[0].get(&key) != Some(&false) {
457 return true;
458 }
459 key.1 = Player::Right;
460 self.outcomes[0].get(&key) != Some(&false)
461 });
462 }
463 canonical_sum(state, &mut self.sum_ids)
464 };
465 let state = normalize(state.to_vec());
466 match state.as_slice() {
467 [] => return misere,
468 [single] => return self.wins(single, player, misere),
469 _ => {}
470 }
471 let key = (state, player);
472 memoized_wins(
473 &key,
474 &mut self.sums[usize::from(misere)],
475 |(s, p)| {
476 if !misere
477 && s.iter().all(|s| {
478 self.values
479 .get(s)
480 .is_some_and(|g| g.as_switch_sum().is_some())
481 })
482 {
483 let value: GameValue = s.iter().map(|s| self.values[s].clone()).sum();
484 return ControlFlow::Break(value.wins(*p));
485 }
486 // Losing as starter in every component implies losing in the sum.
487 // One known win is enough if the opponent loses in every other component.
488 if !misere && (!self.values.is_empty() || !self.outcomes[0].is_empty()) {
489 let mut all_lose = true;
490 let mut all_opponent_lose = true;
491 let mut can_win = false;
492 for s in s {
493 let (mut win, mut opponent_win) = (None, None);
494 if !self.outcomes[0].is_empty() {
495 let mut key = (s.clone(), *p);
496 win = self.outcomes[0].get(&key).copied();
497 key.1 = p.opponent();
498 opponent_win = self.outcomes[0].get(&key).copied();
499 }
500 if let Some(value) = self.values.get(s) {
501 win.get_or_insert_with(|| value.wins(*p));
502 opponent_win.get_or_insert_with(|| value.wins(p.opponent()));
503 }
504 can_win = can_win && opponent_win == Some(false)
505 || all_opponent_lose && win == Some(true);
506 all_lose &= win == Some(false);
507 all_opponent_lose &= opponent_win == Some(false);
508 if !all_lose && !all_opponent_lose && !can_win {
509 break;
510 }
511 }
512 if all_lose || can_win {
513 return ControlFlow::Break(can_win);
514 }
515 }
516 ControlFlow::Continue((0, None))
517 },
518 |(s, p), (i, moves)| {
519 while *i < s.len() {
520 if *i != 0 && s[*i - 1] == s[*i] {
521 *i += 1;
522 continue;
523 }
524 let iterator = moves.get_or_insert_with(|| {
525 partisan_moves(&mut self.left, &mut self.right, &s[*i], *p)
526 });
527 if let Some(next) = iterator.next() {
528 let mut to = s.clone();
529 to[*i] = next.to;
530 return Some((normalize(to), p.opponent()));
531 }
532 *i += 1;
533 *moves = None;
534 }
535 None
536 },
537 misere,
538 )
539 }