Struct GameAnalysis 

pub struct GameAnalysis<'a, G, S, V, const MISERE: bool = false, F = fn(&mut G, &S) -> V>
where
    S: ?Sized,
{
    game: &'a mut G,
    evaluate: F,
    marker: PhantomData<fn(&S) -> V>,
}

Fields

game: &'a mut G

evaluate: F

marker: PhantomData<fn(&S) -> V>

Implementations

impl<'g, S, L, G, V, const MISERE: bool, E> GameAnalysis<'_, ImpartialGraph<'g, G>, S, V, MISERE, E>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>, E: FnMut(&mut ImpartialGraph<'g, G>, &S) -> V,

pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>>

Values describe the destination position; outcomes are for the next player.

impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

Moves to losing positions. To avoid cycling among winning positions, repeatedly use best_move, which follows the retrograde proof.

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 282)

    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return Vec::new();
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .winning_moves(single)
                .into_iter()
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
                .collect();
        }
        if self.eval(state) != GameOutcome::Win {
            return Vec::new();
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        let mut xor = 0;
        let mut infinite = 0;
        if !MISERE {
            for &v in &indices {
                if let Some((value, _)) = game.generalized_grundy[v] {
                    xor ^= value;
                } else {
                    infinite += 1;
                }
            }
        }
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            let source = indices[i];
            for next in game.graph.neighbors(component) {
                indices[i] = game.index_of(next.to);
                let wins = if MISERE {
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
                } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
                    match game.generalized_grundy[source] {
                        Some((g, _)) => infinite == 0 && xor ^ g == value,
                        None => infinite == 1 && xor == value,
                    }
                } else {
                    false
                };
                if wins {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
            indices[i] = source;
        }
        result
    }

pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>>

A move that guarantees termination when winning, or preserves a draw. Returns None at terminal or losing positions.

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 343)

    pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return None;
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .best_move(single)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
        }
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        if MISERE {
            let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
            let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
            for (i, &component) in state.iter().enumerate() {
                let original = indices[i];
                for next in game.graph.neighbors(component) {
                    indices[i] = game.index_of(next.to);
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    let id = game.sums.indices[&key];
                    if Some(id) == winner
                        || outcome == GameOutcome::Draw
                            && game.sums.outcomes.values[id] == GameOutcome::Draw
                    {
                        let mut to = state.to_vec();
                        to[i] = next.to;
                        return Some(Neighbor::new(to, (i, next.label)));
                    }
                }
                indices[i] = original;
            }
            return None;
        }
        let mut xor = 0;
        let mut infinite = None;
        let mut multiple = false;
        for (i, &v) in indices.iter().enumerate() {
            if let Some((value, _)) = game.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(i).is_some() {
                multiple = true;
                break;
            }
        }
        if outcome == GameOutcome::Draw {
            let i = infinite.unwrap();
            let v = indices[i];
            let edges = &game.index.as_ref().unwrap().edges;
            let target = (!multiple).then(|| {
                let values = edges[v]
                    .iter()
                    .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
                    .collect();
                game_mex(values)
            });
            // Preserve two infinite components, or keep the finite XOR outside
            // the remaining infinite component's finite follower values.
            if target.is_none_or(|g| g == xor) {
                let to = edges[v]
                    .iter()
                    .copied()
                    .find(|&u| {
                        game.generalized_grundy[u].is_none()
                            && target.is_none_or(|g| {
                                !edges[u].iter().any(|&w| {
                                    game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
                                })
                            })
                    })
                    .unwrap();
                let next = game
                    .graph
                    .neighbors(state[i])
                    .find(|next| game.index_of(next.to) == to)
                    .unwrap();
                let mut to = state.to_vec();
                to[i] = next.to;
                return Some(Neighbor::new(to, (i, next.label)));
            }
            // The current finite XOR exceeds this mex, so a finite component
            // can decrease it to the mex without moving the infinite component.
            xor ^= target.unwrap();
            infinite = None;
        }
        // Reduce the largest (Grundy, counter) pair, then minimize the
        // destination counter so repeated winning moves terminate.
        let (i, target) = if let Some(i) = infinite {
            (i, xor)
        } else {
            let (i, (g, _)) = indices
                .iter()
                .enumerate()
                .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
                .filter(|(_, (g, _))| g ^ xor < *g)
                .max_by_key(|&(i, g)| (g, Reverse(i)))?;
            (i, g ^ xor)
        };
        let next = game
            .graph
            .neighbors(state[i])
            .filter_map(|next| {
                let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
                (g == target).then_some((next, counter))
            })
            .min_by_key(|&(_, counter)| counter)?
            .0;
        let mut to = state.to_vec();
        to[i] = next.to;
        Some(Neighbor::new(to, (i, next.label)))
    }

impl<'g, S, L, G, V, const MISERE: bool, E> GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>, E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,

pub fn moves( &mut self, state: &[S], ) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>>

impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,

pub fn winning_moves( &mut self, state: &[S], ) -> Vec<Neighbor<Vec<S>, (usize, L)>>

impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>

where S: Copy, G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,

pub fn winning_moves( &mut self, state: &[S], ) -> Vec<Neighbor<Vec<S>, (usize, L)>>

Moves to losing positions; use best_move to avoid cycling.

pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>>

A move that guarantees termination when winning, or preserves a draw. Returns None at terminal or losing positions.

impl<S, L, F, I, V, const MISERE: bool, E> GameAnalysis<'_, Impartial<S, F>, S, V, MISERE, E>

where F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>, E: FnMut(&mut Impartial<S, F>, &S) -> V,

pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>>

impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, u64>

where S: Clone + Eq + Hash, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, GameValue>

where S: Clone + Eq + Hash, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, S, GameOutcome, MISERE>

where S: Clone + Eq + Hash, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>,

pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

impl<S, L, F, I, V, const MISERE: bool, E> GameAnalysis<'_, Impartial<S, F>, [S], V, MISERE, E>

where S: Clone, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>, E: FnMut(&mut Impartial<S, F>, &[S]) -> V,

pub fn moves( &mut self, state: &[S], ) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>>

impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, [S], u64>

where S: Clone + Eq + Hash, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>,

pub fn winning_moves( &mut self, state: &[S], ) -> Vec<Neighbor<Vec<S>, (usize, L)>>

impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, [S], GameOutcome, MISERE>

where S: Clone + Eq + Hash, F: FnMut(&S) -> I, I: IntoIterator<Item = Neighbor<S, L>>,

pub fn winning_moves( &mut self, state: &[S], ) -> Vec<Neighbor<Vec<S>, (usize, L)>>

impl<S, L, FL, FR, IL, IR, V, const MISERE: bool, E> GameAnalysis<'_, Partisan<S, FL, FR>, S, V, MISERE, E>

where FL: FnMut(&S) -> IL, FR: FnMut(&S) -> IR, IL: IntoIterator<Item = Neighbor<S, L>>, IR: IntoIterator<Item = Neighbor<S, L>>, E: FnMut(&mut Partisan<S, FL, FR>, &S) -> V,

pub fn moves( &mut self, state: &S, player: Player, ) -> Vec<EvaluatedMove<S, L, V>>

Values describe the destination game for both choices of starting player.

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/partisan.rs (line 235)

    pub fn undominated_moves(&mut self, state: &S, player: Player) -> Vec<Neighbor<S, L>> {
        let moves = self.moves(state, player);
        let preferred = if player == Player::Left {
            Ordering::Greater
        } else {
            Ordering::Less
        };
        let best = moves.iter().try_fold(None, |best, m| {
            let (q, k, n) = m.value.as_number_up_nimber()?;
            let pair = (q, k);
            Some(Some(match best {
                Some((previous, nimber)) => match pair.cmp(&previous) {
                    Ordering::Equal => (previous, if nimber == Some(n) { nimber } else { None }),
                    order if order == preferred => (pair, Some(n)),
                    _ => (previous, nimber),
                },
                None => (pair, Some(n)),
            }))
        });
        if let Some(best) = best {
            return moves
                .into_iter()
                .filter(|m| {
                    let (q, k, n) = m.value.as_number_up_nimber().unwrap();
                    best.is_some_and(|((b, l), nimber)| {
                        q == b && (k == l || k.abs_diff(l) == 1 && nimber == Some(n ^ 1))
                    })
                })
                .map(|m| m.next)
                .collect();
        }
        let mut dominated = vec![false; moves.len()];
        for i in 0..moves.len() {
            if dominated[i] {
                continue;
            }
            for j in i + 1..moves.len() {
                if dominated[j] {
                    continue;
                }
                let order = moves[i].value.partial_cmp(&moves[j].value);
                if order == Some(preferred) {
                    dominated[j] = true;
                } else if order == Some(preferred.reverse()) {
                    dominated[i] = true;
                    break;
                }
            }
        }
        moves
            .into_iter()
            .zip(dominated)
            .filter(|(_, d)| !d)
            .map(|(m, _)| m.next)
            .collect()
    }

impl<S, L, FL, FR, IL, IR> GameAnalysis<'_, Partisan<S, FL, FR>, S, GameValue>

where FL: FnMut(&S) -> IL, FR: FnMut(&S) -> IR, IL: IntoIterator<Item = Neighbor<S, L>>, IR: IntoIterator<Item = Neighbor<S, L>>,

pub fn compare(&mut self, left: &S, right: &S) -> Option<Ordering>

pub fn undominated_moves( &mut self, state: &S, player: Player, ) -> Vec<Neighbor<S, L>>

Undominated moves for the selected player; incomparable alternatives remain.

impl<S, L, FL, FR, IL, IR, const MISERE: bool> GameAnalysis<'_, Partisan<S, FL, FR>, S, PartisanOutcome, MISERE>

where S: Clone + Eq + Hash, FL: FnMut(&S) -> IL, FR: FnMut(&S) -> IR, IL: IntoIterator<Item = Neighbor<S, L>>, IR: IntoIterator<Item = Neighbor<S, L>>,

pub fn wins(&mut self, state: &S, player: Player) -> bool

Whether the selected starting player can force a win.

pub fn winning_moves( &mut self, state: &S, player: Player, ) -> Vec<Neighbor<S, L>>

impl<S, L, FL, FR, IL, IR, V, const MISERE: bool, E> GameAnalysis<'_, Partisan<S, FL, FR>, [S], V, MISERE, E>

where S: Clone, FL: FnMut(&S) -> IL, FR: FnMut(&S) -> IR, IL: IntoIterator<Item = Neighbor<S, L>>, IR: IntoIterator<Item = Neighbor<S, L>>, E: FnMut(&mut Partisan<S, FL, FR>, &[S]) -> V,

pub fn moves( &mut self, state: &[S], player: Player, ) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>>

impl<S, L, FL, FR, IL, IR, const MISERE: bool> GameAnalysis<'_, Partisan<S, FL, FR>, [S], PartisanOutcome, MISERE>

where S: Clone + Eq + Hash, FL: FnMut(&S) -> IL, FR: FnMut(&S) -> IR, IL: IntoIterator<Item = Neighbor<S, L>>, IR: IntoIterator<Item = Neighbor<S, L>>,

pub fn wins(&mut self, state: &[S], player: Player) -> bool

Whether the selected starting player can force a win.

pub fn winning_moves( &mut self, state: &[S], player: Player, ) -> Vec<Neighbor<Vec<S>, (usize, L)>>

impl<S, L, F, T, I> GameAnalysis<'_, Scoring<S, F, T>, S, i64>

where F: FnMut(&S) -> I, I: IntoIterator<Item = ScoreMove<S, L>>, T: FnMut(&S) -> Option<i64>,

pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, i64>>

Values include the reward and are measured for the current player.

pub fn best_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>>

fn evaluated_moves( &mut self, state: &S, ) -> impl Iterator<Item = EvaluatedMove<S, L, i64>>

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/scoring.rs (line 93)

    pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, i64>> {
        self.evaluated_moves(state).collect()
    }

    pub fn best_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        let mut result = Vec::new();
        let mut best = None;
        for m in self.evaluated_moves(state) {
            if best.is_none_or(|best| m.value > best) {
                result.clear();
                best = Some(m.value);
            }
            if best == Some(m.value) {
                result.push(m.next);
            }
        }
        result
    }

impl<'a, G, S, V, const MISERE: bool, F> GameAnalysis<'a, G, S, V, MISERE, F>

where S: ?Sized, F: FnMut(&mut G, &S) -> V,

pub fn eval(&mut self, state: &S) -> V

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/impartial.rs (line 163)

    pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
        (self.game.moves)(state)
            .into_iter()
            .map(|next| {
                let value = self.eval(&next.to);
                EvaluatedMove { next, value }
            })
            .collect()
    }
}

impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, u64>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.winning_moves(state, false).collect()
    }
}
impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, S, GameValue>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.winning_moves(state, false).collect()
    }
}
impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, S, GameOutcome, MISERE>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.winning_moves(state, MISERE).collect()
    }
}

#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, F, I, V, const MISERE: bool, E> GameAnalysis<'_, Impartial<S, F>, [S], V, MISERE, E>
where
    S: Clone,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
    E: FnMut(&mut Impartial<S, F>, &[S]) -> V,
{
    pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
        let mut result = Vec::new();
        for (i, component) in state.iter().enumerate() {
            for next in (self.game.moves)(component) {
                let mut to = state.to_vec();
                to[i] = next.to;
                let value = self.eval(&to);
                result.push(EvaluatedMove {
                    next: Neighbor::new(to, (i, next.label)),
                    value,
                });
            }
        }
        result
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, F, I> GameAnalysis<'_, Impartial<S, F>, [S], u64>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        self.game.sum_winning_moves(state)
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, F, I, const MISERE: bool> GameAnalysis<'_, Impartial<S, F>, [S], GameOutcome, MISERE>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        if let [single] = state {
            return self
                .game
                .winning_moves(single, MISERE)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
                .collect();
        }
        if !MISERE {
            return self.game.sum_winning_moves(state);
        }
        let mut result = Vec::new();
        for (i, component) in state.iter().enumerate() {
            for next in (self.game.moves)(component) {
                let mut to = state.to_vec();
                to[i] = next.to;
                if self.eval(&to) == GameOutcome::Lose {
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }

crates/competitive/src/algorithm/game_analyzer.rs (line 124)

    pub fn table<T>(&mut self, states: impl IntoIterator<Item = T>) -> Vec<(T, V)>
    where
        T: Borrow<S>,
    {
        states
            .into_iter()
            .map(|state| {
                let value = self.eval(state.borrow());
                (state, value)
            })
            .collect()
    }

    /// Returns the first mismatch in input order, or `None` if the range agrees.
    pub fn verify<T>(
        &mut self,
        states: impl IntoIterator<Item = T>,
        mut expected: impl FnMut(&S) -> V,
    ) -> Option<GameMismatch<T, V>>
    where
        T: Borrow<S>,
        V: PartialEq,
    {
        for state in states {
            let expected = expected(state.borrow());
            let actual = self.eval(state.borrow());
            if actual != expected {
                return Some(GameMismatch {
                    state,
                    expected,
                    actual,
                });
            }
        }
        None
    }

crates/competitive/src/algorithm/game_analyzer/partisan.rs (line 215)

    pub fn moves(&mut self, state: &S, player: Player) -> Vec<EvaluatedMove<S, L, V>> {
        partisan_moves(&mut self.game.left, &mut self.game.right, state, player)
            .map(|next| {
                let value = self.eval(&next.to);
                EvaluatedMove { next, value }
            })
            .collect()
    }
}

impl<S, L, FL, FR, IL, IR> GameAnalysis<'_, Partisan<S, FL, FR>, S, GameValue>
where
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn compare(&mut self, left: &S, right: &S) -> Option<Ordering> {
        self.eval(left).partial_cmp(&self.eval(right))
    }

    /// Undominated moves for the selected player; incomparable alternatives remain.
    pub fn undominated_moves(&mut self, state: &S, player: Player) -> Vec<Neighbor<S, L>> {
        let moves = self.moves(state, player);
        let preferred = if player == Player::Left {
            Ordering::Greater
        } else {
            Ordering::Less
        };
        let best = moves.iter().try_fold(None, |best, m| {
            let (q, k, n) = m.value.as_number_up_nimber()?;
            let pair = (q, k);
            Some(Some(match best {
                Some((previous, nimber)) => match pair.cmp(&previous) {
                    Ordering::Equal => (previous, if nimber == Some(n) { nimber } else { None }),
                    order if order == preferred => (pair, Some(n)),
                    _ => (previous, nimber),
                },
                None => (pair, Some(n)),
            }))
        });
        if let Some(best) = best {
            return moves
                .into_iter()
                .filter(|m| {
                    let (q, k, n) = m.value.as_number_up_nimber().unwrap();
                    best.is_some_and(|((b, l), nimber)| {
                        q == b && (k == l || k.abs_diff(l) == 1 && nimber == Some(n ^ 1))
                    })
                })
                .map(|m| m.next)
                .collect();
        }
        let mut dominated = vec![false; moves.len()];
        for i in 0..moves.len() {
            if dominated[i] {
                continue;
            }
            for j in i + 1..moves.len() {
                if dominated[j] {
                    continue;
                }
                let order = moves[i].value.partial_cmp(&moves[j].value);
                if order == Some(preferred) {
                    dominated[j] = true;
                } else if order == Some(preferred.reverse()) {
                    dominated[i] = true;
                    break;
                }
            }
        }
        moves
            .into_iter()
            .zip(dominated)
            .filter(|(_, d)| !d)
            .map(|(m, _)| m.next)
            .collect()
    }
}
impl<S, L, FL, FR, IL, IR, const MISERE: bool>
    GameAnalysis<'_, Partisan<S, FL, FR>, S, PartisanOutcome, MISERE>
where
    S: Clone + Eq + Hash,
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
{
    /// Whether the selected starting player can force a win.
    pub fn wins(&mut self, state: &S, player: Player) -> bool {
        self.game.wins(state, player, MISERE)
    }

    pub fn winning_moves(&mut self, state: &S, player: Player) -> Vec<Neighbor<S, L>> {
        partisan_moves(&mut self.game.left, &mut self.game.right, state, player)
            .filter(|next| !self.game.wins(&next.to, player.opponent(), MISERE))
            .collect()
    }
}

#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, FL, FR, IL, IR, V, const MISERE: bool, E>
    GameAnalysis<'_, Partisan<S, FL, FR>, [S], V, MISERE, E>
where
    S: Clone,
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
    E: FnMut(&mut Partisan<S, FL, FR>, &[S]) -> V,
{
    pub fn moves(
        &mut self,
        state: &[S],
        player: Player,
    ) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
        let mut result = Vec::new();
        for (i, component) in state.iter().enumerate() {
            for next in partisan_moves(&mut self.game.left, &mut self.game.right, component, player)
            {
                let mut to = state.to_vec();
                to[i] = next.to;
                let value = self.eval(&to);
                result.push(EvaluatedMove {
                    next: Neighbor::new(to, (i, next.label)),
                    value,
                });
            }
        }
        result
    }

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 139)

    pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .map(|next| {
                let value = self.eval(&next.to);
                EvaluatedMove { next, value }
            })
            .collect()
    }
}
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to) == 0)
            .collect()
    }
}
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
            .collect()
    }
}
impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    /// Moves to losing positions. To avoid cycling among winning positions,
    /// repeatedly use `best_move`, which follows the retrograde proof.
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
            .collect()
    }

    /// A move that guarantees termination when winning, or preserves a draw.
    /// Returns `None` at terminal or losing positions.
    pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let game = &self.game;
        let root = game.index_of(*state);
        let result = &game.outcomes[usize::from(MISERE)];
        let winner = result.winning[root];
        for next in game.graph.neighbors(*state) {
            let id = game.index_of(next.to);
            if Some(id) == winner
                || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
            {
                return Some(next);
            }
        }
        None
    }
}

#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<'g, S, L, G, V, const MISERE: bool, E>
    GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
    E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
{
    pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
        self.eval(state);
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            for next in self.game.graph.neighbors(component) {
                let mut to = state.to_vec();
                to[i] = next.to;
                let value = self.eval(&to);
                result.push(EvaluatedMove {
                    next: Neighbor::new(to, (i, next.label)),
                    value,
                });
            }
        }
        result
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.eval(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.game.grundy(component);
            for next in self.game.graph.neighbors(*component) {
                if self.game.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    /// Moves to losing positions; use `best_move` to avoid cycling.
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return Vec::new();
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .winning_moves(single)
                .into_iter()
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
                .collect();
        }
        if self.eval(state) != GameOutcome::Win {
            return Vec::new();
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        let mut xor = 0;
        let mut infinite = 0;
        if !MISERE {
            for &v in &indices {
                if let Some((value, _)) = game.generalized_grundy[v] {
                    xor ^= value;
                } else {
                    infinite += 1;
                }
            }
        }
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            let source = indices[i];
            for next in game.graph.neighbors(component) {
                indices[i] = game.index_of(next.to);
                let wins = if MISERE {
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
                } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
                    match game.generalized_grundy[source] {
                        Some((g, _)) => infinite == 0 && xor ^ g == value,
                        None => infinite == 1 && xor == value,
                    }
                } else {
                    false
                };
                if wins {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
            indices[i] = source;
        }
        result
    }

    /// A move that guarantees termination when winning, or preserves a draw.
    /// Returns `None` at terminal or losing positions.
    pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return None;
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .best_move(single)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
        }
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        if MISERE {
            let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
            let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
            for (i, &component) in state.iter().enumerate() {
                let original = indices[i];
                for next in game.graph.neighbors(component) {
                    indices[i] = game.index_of(next.to);
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    let id = game.sums.indices[&key];
                    if Some(id) == winner
                        || outcome == GameOutcome::Draw
                            && game.sums.outcomes.values[id] == GameOutcome::Draw
                    {
                        let mut to = state.to_vec();
                        to[i] = next.to;
                        return Some(Neighbor::new(to, (i, next.label)));
                    }
                }
                indices[i] = original;
            }
            return None;
        }
        let mut xor = 0;
        let mut infinite = None;
        let mut multiple = false;
        for (i, &v) in indices.iter().enumerate() {
            if let Some((value, _)) = game.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(i).is_some() {
                multiple = true;
                break;
            }
        }
        if outcome == GameOutcome::Draw {
            let i = infinite.unwrap();
            let v = indices[i];
            let edges = &game.index.as_ref().unwrap().edges;
            let target = (!multiple).then(|| {
                let values = edges[v]
                    .iter()
                    .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
                    .collect();
                game_mex(values)
            });
            // Preserve two infinite components, or keep the finite XOR outside
            // the remaining infinite component's finite follower values.
            if target.is_none_or(|g| g == xor) {
                let to = edges[v]
                    .iter()
                    .copied()
                    .find(|&u| {
                        game.generalized_grundy[u].is_none()
                            && target.is_none_or(|g| {
                                !edges[u].iter().any(|&w| {
                                    game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
                                })
                            })
                    })
                    .unwrap();
                let next = game
                    .graph
                    .neighbors(state[i])
                    .find(|next| game.index_of(next.to) == to)
                    .unwrap();
                let mut to = state.to_vec();
                to[i] = next.to;
                return Some(Neighbor::new(to, (i, next.label)));
            }
            // The current finite XOR exceeds this mex, so a finite component
            // can decrease it to the mex without moving the infinite component.
            xor ^= target.unwrap();
            infinite = None;
        }
        // Reduce the largest (Grundy, counter) pair, then minimize the
        // destination counter so repeated winning moves terminate.
        let (i, target) = if let Some(i) = infinite {
            (i, xor)
        } else {
            let (i, (g, _)) = indices
                .iter()
                .enumerate()
                .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
                .filter(|(_, (g, _))| g ^ xor < *g)
                .max_by_key(|&(i, g)| (g, Reverse(i)))?;
            (i, g ^ xor)
        };
        let next = game
            .graph
            .neighbors(state[i])
            .filter_map(|next| {
                let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
                (g == target).then_some((next, counter))
            })
            .min_by_key(|&(_, counter)| counter)?
            .0;
        let mut to = state.to_vec();
        to[i] = next.to;
        Some(Neighbor::new(to, (i, next.label)))
    }

crates/competitive/src/algorithm/game_analyzer/scoring.rs (line 123)

    fn evaluated_moves(&mut self, state: &S) -> impl Iterator<Item = EvaluatedMove<S, L, i64>> {
        let terminal = (self.game.terminal)(state).is_some();
        let mut moves = (!terminal)
            .then(|| (self.game.moves)(state).into_iter())
            .into_iter()
            .flatten()
            .peekable();
        assert!(
            terminal || moves.peek().is_some(),
            "nonterminal scoring state has no moves"
        );
        moves.map(|m| {
            let child = self.eval(&m.next.to);
            let value = match m.turn {
                Turn::Same => m.reward + child,
                Turn::Other => m.reward - child,
            };
            EvaluatedMove {
                next: m.next,
                value,
            }
        })
    }

pub fn table<T>(&mut self, states: impl IntoIterator<Item = T>) -> Vec<(T, V)>

where T: Borrow<S>,

Keeps the input items, their order and duplicates; dependency states are omitted.

pub fn verify<T>( &mut self, states: impl IntoIterator<Item = T>, expected: impl FnMut(&S) -> V, ) -> Option<GameMismatch<T, V>>

where T: Borrow<S>, V: PartialEq,

Returns the first mismatch in input order, or None if the range agrees.

fn new(game: &'a mut G, evaluate: F) -> Self

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/impartial.rs (line 75)

    pub fn grundy(&mut self) -> GameAnalysis<'_, Impartial<S, F>, S, u64> {
        GameAnalysis::new(&mut self.game, Impartial::grundy)
    }

    pub fn value(&mut self) -> GameAnalysis<'_, Impartial<S, F>, S, GameValue> {
        GameAnalysis::new(&mut self.game, |g, s| GameValue::nimber(g.grundy(s)))
    }

    pub fn outcome(&mut self) -> GameAnalysis<'_, Impartial<S, F>, S, GameOutcome> {
        GameAnalysis::new(&mut self.game, |g, s| g.outcome(s, false))
    }

    /// `combine` receives each move's label and the value of its destination.
    #[allow(clippy::type_complexity)] // The query owns the fold and its cache.
    pub fn fold<V, C>(
        &mut self,
        mut combine: C,
    ) -> GameAnalysis<'_, Impartial<S, F>, S, V, false, impl FnMut(&mut Impartial<S, F>, &S) -> V>
    where
        V: Clone,
        C: FnMut(&S, &[(L, V)]) -> V,
    {
        let mut cache = HashMap::new();
        GameAnalysis::new(
            &mut self.game,
            move |game: &mut Impartial<S, F>, state: &S| {
                memoized_game(
                    state,
                    &mut cache,
                    &mut HashSet::new(),
                    &mut |s| {
                        ControlFlow::Continue((
                            (game.moves)(s).into_iter().map(|n| (n.to, n.label)),
                            Vec::new(),
                        ))
                    },
                    &mut |_, moves| moves.next(),
                    &mut |values, label, value| {
                        values.push((label, value));
                        ControlFlow::Continue(())
                    },
                    &mut |s, values| combine(s, &values),
                )
            },
        )
    }
}

impl<'a, S, L, F, I> Misere<'a, Impartial<S, F>>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn outcome(self) -> GameAnalysis<'a, Impartial<S, F>, S, GameOutcome, true> {
        GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
    }
}
impl<'a, S, L, F, I> GameSum<'a, Impartial<S, F>>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn grundy(self) -> GameAnalysis<'a, Impartial<S, F>, [S], u64> {
        GameAnalysis::new(self.game, Impartial::sum_grundy)
    }
}
impl<'a, S, L, F, I, const MISERE: bool> GameSum<'a, Impartial<S, F>, MISERE>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn outcome(self) -> GameAnalysis<'a, Impartial<S, F>, [S], GameOutcome, MISERE> {
        GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
    }

crates/competitive/src/algorithm/game_analyzer/partisan.rs (line 97)

    pub fn value(&mut self) -> GameAnalysis<'_, Partisan<S, FL, FR>, S, GameValue> {
        GameAnalysis::new(&mut self.game, Partisan::value)
    }

    pub fn outcome(&mut self) -> GameAnalysis<'_, Partisan<S, FL, FR>, S, PartisanOutcome> {
        GameAnalysis::new(&mut self.game, |g, s| g.outcome(s, false))
    }

    /// `combine` receives all Left options followed by all Right options.
    #[allow(clippy::type_complexity)] // The query owns the fold and its cache.
    pub fn fold<V, C>(
        &mut self,
        mut combine: C,
    ) -> GameAnalysis<
        '_,
        Partisan<S, FL, FR>,
        S,
        V,
        false,
        impl FnMut(&mut Partisan<S, FL, FR>, &S) -> V,
    >
    where
        V: Clone,
        C: FnMut(&S, &[(Player, L, V)]) -> V,
    {
        let mut cache = HashMap::new();
        GameAnalysis::new(
            &mut self.game,
            move |game: &mut Partisan<S, FL, FR>, state: &S| {
                memoized_game(
                    state,
                    &mut cache,
                    &mut HashSet::new(),
                    &mut |s| {
                        let moves = (game.left)(s)
                            .into_iter()
                            .map(|n| (n.to, (Player::Left, n.label)))
                            .chain(
                                (game.right)(s)
                                    .into_iter()
                                    .map(|n| (n.to, (Player::Right, n.label))),
                            );
                        ControlFlow::Continue((moves, Vec::new()))
                    },
                    &mut |_, moves| moves.next(),
                    &mut |values, (player, label), value| {
                        values.push((player, label, value));
                        ControlFlow::Continue(())
                    },
                    &mut |s, values| combine(s, &values),
                )
            },
        )
    }
}
impl<'a, S, L, FL, FR, IL, IR> Misere<'a, Partisan<S, FL, FR>>
where
    S: Clone + Eq + Hash,
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn outcome(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, S, PartisanOutcome, true> {
        GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
    }
}
impl<'a, S, L, FL, FR, IL, IR> GameSum<'a, Partisan<S, FL, FR>>
where
    S: Clone + Eq + Hash,
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
{
    pub fn value(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, [S], GameValue> {
        GameAnalysis::new(self.game, |g, state: &[S]| {
            state.iter().map(|s| g.value(s)).sum()
        })
    }
}
impl<'a, S, L, FL, FR, IL, IR, const MISERE: bool> GameSum<'a, Partisan<S, FL, FR>, MISERE>
where
    S: Clone + Eq + Hash,
    FL: FnMut(&S) -> IL,
    FR: FnMut(&S) -> IR,
    IL: IntoIterator<Item = Neighbor<S, L>>,
    IR: IntoIterator<Item = Neighbor<S, L>>,
{
    /// Explores reachable sum positions, including the player to move.
    /// Reuses cached sums of numbers, ups, nimbers and switches in normal play.
    pub fn outcome(self) -> GameAnalysis<'a, Partisan<S, FL, FR>, [S], PartisanOutcome, MISERE> {
        GameAnalysis::new(self.game, |g, s| {
            match (
                g.sum_wins(s, Player::Left, MISERE),
                g.sum_wins(s, Player::Right, MISERE),
            ) {
                (true, true) => PartisanOutcome::Next,
                (false, false) => PartisanOutcome::Previous,
                (true, false) => PartisanOutcome::Left,
                (false, true) => PartisanOutcome::Right,
            }
        })
    }

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 65)

    pub fn grundy(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, u64> {
        GameAnalysis::new(&mut self.game, ImpartialGraph::grundy)
    }

    pub fn value(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, GameValue> {
        GameAnalysis::new(&mut self.game, |g, s| GameValue::nimber(g.grundy(s)))
    }

    pub fn outcome(&mut self) -> GameAnalysis<'_, ImpartialGraph<'g, G>, G::Vertex, GameOutcome> {
        GameAnalysis::new(&mut self.game, |g, s| g.outcome(s, false))
    }

    pub fn misere(&mut self) -> Misere<'_, ImpartialGraph<'g, G>> {
        Misere {
            game: &mut self.game,
        }
    }

    pub fn sum(&mut self) -> GameSum<'_, ImpartialGraph<'g, G>> {
        GameSum {
            game: &mut self.game,
        }
    }

    pub fn clear_cache(&mut self) {
        self.game.grundy.clear();
        self.game.outcomes = std::array::from_fn(|_| GraphOutcomes::default());
        self.game.generalized_grundy.clear();
        self.game.sums = GraphSums::default();
    }
}

impl<'a, 'g, G> Misere<'a, ImpartialGraph<'g, G>>
where
    G: Graph + VertexMap<Option<usize>>,
{
    pub fn outcome(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, G::Vertex, GameOutcome, true> {
        GameAnalysis::new(self.game, |g, s| g.outcome(s, true))
    }
}
impl<'a, 'g, G> GameSum<'a, ImpartialGraph<'g, G>>
where
    G: Graph + VertexMap<Option<usize>>,
{
    pub fn grundy(self) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], u64> {
        GameAnalysis::new(self.game, ImpartialGraph::sum_grundy)
    }
}
impl<'a, 'g, G, const MISERE: bool> GameSum<'a, ImpartialGraph<'g, G>, MISERE>
where
    G: Graph + VertexMap<Option<usize>>,
{
    /// Normal play combines generalized Grundy values, including cyclic positions.
    /// Misere explores the sum graph, which can grow exponentially in the component count.
    pub fn outcome(
        self,
    ) -> GameAnalysis<'a, ImpartialGraph<'g, G>, [G::Vertex], GameOutcome, MISERE> {
        GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
    }
}

impl<'g, S, L, G, V, const MISERE: bool, E> GameAnalysis<'_, ImpartialGraph<'g, G>, S, V, MISERE, E>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
    E: FnMut(&mut ImpartialGraph<'g, G>, &S) -> V,
{
    /// Values describe the destination position; outcomes are for the next player.
    pub fn moves(&mut self, state: &S) -> Vec<EvaluatedMove<S, L, V>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .map(|next| {
                let value = self.eval(&next.to);
                EvaluatedMove { next, value }
            })
            .collect()
    }
}
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, u64>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to) == 0)
            .collect()
    }
}
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameValue>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to).as_nimber() == Some(0))
            .collect()
    }
}
impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, S, GameOutcome, MISERE>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    /// Moves to losing positions. To avoid cycling among winning positions,
    /// repeatedly use `best_move`, which follows the retrograde proof.
    pub fn winning_moves(&mut self, state: &S) -> Vec<Neighbor<S, L>> {
        self.game.prepare();
        self.game.index_of(*state);
        self.game
            .graph
            .neighbors(*state)
            .filter(|next| self.eval(&next.to) == GameOutcome::Lose)
            .collect()
    }

    /// A move that guarantees termination when winning, or preserves a draw.
    /// Returns `None` at terminal or losing positions.
    pub fn best_move(&mut self, state: &S) -> Option<Neighbor<S, L>> {
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let game = &self.game;
        let root = game.index_of(*state);
        let result = &game.outcomes[usize::from(MISERE)];
        let winner = result.winning[root];
        for next in game.graph.neighbors(*state) {
            let id = game.index_of(next.to);
            if Some(id) == winner
                || outcome == GameOutcome::Draw && result.values[id] == GameOutcome::Draw
            {
                return Some(next);
            }
        }
        None
    }
}

#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<'g, S, L, G, V, const MISERE: bool, E>
    GameAnalysis<'_, ImpartialGraph<'g, G>, [S], V, MISERE, E>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
    E: FnMut(&mut ImpartialGraph<'g, G>, &[S]) -> V,
{
    pub fn moves(&mut self, state: &[S]) -> Vec<EvaluatedMove<Vec<S>, (usize, L), V>> {
        self.eval(state);
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            for next in self.game.graph.neighbors(component) {
                let mut to = state.to_vec();
                to[i] = next.to;
                let value = self.eval(&to);
                result.push(EvaluatedMove {
                    next: Neighbor::new(to, (i, next.label)),
                    value,
                });
            }
        }
        result
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, G> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], u64>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.eval(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.game.grundy(component);
            for next in self.game.graph.neighbors(*component) {
                if self.game.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
impl<S, L, G, const MISERE: bool> GameAnalysis<'_, ImpartialGraph<'_, G>, [S], GameOutcome, MISERE>
where
    S: Copy,
    G: Graph<Vertex = S, Label = L> + VertexMap<Option<usize>>,
{
    /// Moves to losing positions; use `best_move` to avoid cycling.
    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return Vec::new();
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .winning_moves(single)
                .into_iter()
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
                .collect();
        }
        if self.eval(state) != GameOutcome::Win {
            return Vec::new();
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        let mut xor = 0;
        let mut infinite = 0;
        if !MISERE {
            for &v in &indices {
                if let Some((value, _)) = game.generalized_grundy[v] {
                    xor ^= value;
                } else {
                    infinite += 1;
                }
            }
        }
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            let source = indices[i];
            for next in game.graph.neighbors(component) {
                indices[i] = game.index_of(next.to);
                let wins = if MISERE {
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
                } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
                    match game.generalized_grundy[source] {
                        Some((g, _)) => infinite == 0 && xor ^ g == value,
                        None => infinite == 1 && xor == value,
                    }
                } else {
                    false
                };
                if wins {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
            indices[i] = source;
        }
        result
    }

    /// A move that guarantees termination when winning, or preserves a draw.
    /// Returns `None` at terminal or losing positions.
    pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return None;
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .best_move(single)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
        }
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        if MISERE {
            let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
            let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
            for (i, &component) in state.iter().enumerate() {
                let original = indices[i];
                for next in game.graph.neighbors(component) {
                    indices[i] = game.index_of(next.to);
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    let id = game.sums.indices[&key];
                    if Some(id) == winner
                        || outcome == GameOutcome::Draw
                            && game.sums.outcomes.values[id] == GameOutcome::Draw
                    {
                        let mut to = state.to_vec();
                        to[i] = next.to;
                        return Some(Neighbor::new(to, (i, next.label)));
                    }
                }
                indices[i] = original;
            }
            return None;
        }
        let mut xor = 0;
        let mut infinite = None;
        let mut multiple = false;
        for (i, &v) in indices.iter().enumerate() {
            if let Some((value, _)) = game.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(i).is_some() {
                multiple = true;
                break;
            }
        }
        if outcome == GameOutcome::Draw {
            let i = infinite.unwrap();
            let v = indices[i];
            let edges = &game.index.as_ref().unwrap().edges;
            let target = (!multiple).then(|| {
                let values = edges[v]
                    .iter()
                    .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
                    .collect();
                game_mex(values)
            });
            // Preserve two infinite components, or keep the finite XOR outside
            // the remaining infinite component's finite follower values.
            if target.is_none_or(|g| g == xor) {
                let to = edges[v]
                    .iter()
                    .copied()
                    .find(|&u| {
                        game.generalized_grundy[u].is_none()
                            && target.is_none_or(|g| {
                                !edges[u].iter().any(|&w| {
                                    game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
                                })
                            })
                    })
                    .unwrap();
                let next = game
                    .graph
                    .neighbors(state[i])
                    .find(|next| game.index_of(next.to) == to)
                    .unwrap();
                let mut to = state.to_vec();
                to[i] = next.to;
                return Some(Neighbor::new(to, (i, next.label)));
            }
            // The current finite XOR exceeds this mex, so a finite component
            // can decrease it to the mex without moving the infinite component.
            xor ^= target.unwrap();
            infinite = None;
        }
        // Reduce the largest (Grundy, counter) pair, then minimize the
        // destination counter so repeated winning moves terminate.
        let (i, target) = if let Some(i) = infinite {
            (i, xor)
        } else {
            let (i, (g, _)) = indices
                .iter()
                .enumerate()
                .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
                .filter(|(_, (g, _))| g ^ xor < *g)
                .max_by_key(|&(i, g)| (g, Reverse(i)))?;
            (i, g ^ xor)
        };
        let next = game
            .graph
            .neighbors(state[i])
            .filter_map(|next| {
                let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
                (g == target).then_some((next, counter))
            })
            .min_by_key(|&(_, counter)| counter)?
            .0;
        let mut to = state.to_vec();
        to[i] = next.to;
        Some(Neighbor::new(to, (i, next.label)))
    }

crates/competitive/src/algorithm/game_analyzer/scoring.rs (lines 57-82)

    pub fn score(&mut self) -> GameAnalysis<'_, Scoring<S, F, T>, S, i64> {
        GameAnalysis::new(&mut self.game, |g, state| {
            memoized_game(
                state,
                &mut g.scores,
                &mut HashSet::new(),
                &mut |s| {
                    if let Some(value) = (g.terminal)(s) {
                        return ControlFlow::Break(value);
                    }
                    let moves = (g.moves)(s)
                        .into_iter()
                        .map(|m| (m.next.to, (m.reward, m.turn)));
                    ControlFlow::Continue((moves, None))
                },
                &mut |_, moves| moves.next(),
                &mut |best: &mut Option<i64>, (reward, turn), child| {
                    let value = match turn {
                        Turn::Same => reward + child,
                        Turn::Other => reward - child,
                    };
                    *best = Some(best.map_or(value, |b| b.max(value)));
                    ControlFlow::Continue(())
                },
                &mut |_, best| best.expect("nonterminal scoring state has no moves"),
            )
        })
    }