pub fn partisan_moves<S, L, FL, FR, IL, IR>(
left: &mut FL,
right: &mut FR,
state: &S,
player: Player,
) -> impl Iterator<Item = Neighbor<S, L>> + use<S, L, FL, FR, IL, IR>where
FL: FnMut(&S) -> IL,
FR: FnMut(&S) -> IR,
IL: IntoIterator<Item = Neighbor<S, L>>,
IR: IntoIterator<Item = Neighbor<S, L>>,Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/partisan.rs (line 213)
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 }
411
412 fn outcome(&mut self, state: &S, misere: bool) -> PartisanOutcome {
413 match (
414 self.wins(state, Player::Left, misere),
415 self.wins(state, Player::Right, misere),
416 ) {
417 (true, true) => PartisanOutcome::Next,
418 (false, false) => PartisanOutcome::Previous,
419 (true, false) => PartisanOutcome::Left,
420 (false, true) => PartisanOutcome::Right,
421 }
422 }
423
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 }