Struct Impartial 

pub struct Impartial<S, F> {
    moves: F,
    grundy: HashMap<S, u64>,
    outcomes: [HashMap<S, bool>; 2],
    sums: HashMap<Vec<S>, bool>,
    sum_ids: HashMap<S, usize>,
}

Fields

moves: F

grundy: HashMap<S, u64>

outcomes: [HashMap<S, bool>; 2]

sums: HashMap<Vec<S>, bool>

sum_ids: HashMap<S, usize>

Implementations

impl<S, L, F, I> Impartial<S, F>

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

fn grundy(&mut self, state: &S) -> u64

Examples found in repository

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

    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))
    }
}

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>> {
        (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
    }
}

impl<S, L, F, I> Impartial<S, F>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    fn grundy(&mut self, state: &S) -> u64 {
        memoized_game(
            state,
            &mut self.grundy,
            &mut HashSet::new(),
            &mut |s| {
                if self.outcomes[0].get(s) == Some(&false) {
                    return ControlFlow::Break(0);
                }
                let moves = (self.moves)(s).into_iter().map(|n| (n.to, ()));
                ControlFlow::Continue((moves, Vec::new()))
            },
            &mut |_, moves| moves.next(),
            &mut |values, (), value| {
                values.push(value);
                ControlFlow::Continue(())
            },
            &mut |_, values| game_mex(values),
        )
    }

    fn outcome(&mut self, state: &S, misere: bool) -> GameOutcome {
        let win = memoized_wins(
            state,
            &mut self.outcomes[usize::from(misere)],
            |s| {
                if !misere && let Some(&value) = self.grundy.get(s) {
                    return ControlFlow::Break(value != 0);
                }
                let moves = (self.moves)(s).into_iter().map(|n| n.to);
                ControlFlow::Continue(moves)
            },
            |_, moves| moves.next(),
            misere,
        );
        GameOutcome::from_win(win)
    }

    fn winning_moves(&mut self, state: &S, misere: bool) -> impl Iterator<Item = Neighbor<S, L>> {
        (self.moves)(state).into_iter().filter(move |next| {
            if !misere && let Some(&value) = self.grundy.get(&next.to) {
                value == 0
            } else {
                self.outcome(&next.to, misere) == GameOutcome::Lose
            }
        })
    }

    fn sum_grundy(&mut self, state: &[S]) -> u64 {
        match state {
            [] => return 0,
            [single] => return self.grundy(single),
            _ => {}
        }
        let (xor, odd) = self.reduce_sum(state);
        odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s))
    }

    #[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
    fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.sum_grundy(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.grundy(component);
            for next in (self.moves)(component) {
                if self.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }

    fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome {
        if state.is_empty() {
            return GameOutcome::from_win(misere);
        }
        if let [single] = state {
            return self.outcome(single, misere);
        }
        let win = if misere {
            if let Some(&win) = self.sums.get(state) {
                win
            } else {
                memoized_wins(
                    &canonical_sum(state.to_vec(), &mut self.sum_ids),
                    &mut self.sums,
                    |_| ControlFlow::Continue((0, None)),
                    |s, (i, moves)| {
                        while *i < s.len() {
                            if *i != 0 && s[*i - 1] == s[*i] {
                                *i += 1;
                                continue;
                            }
                            let iterator =
                                moves.get_or_insert_with(|| (self.moves)(&s[*i]).into_iter());
                            if let Some(next) = iterator.next() {
                                let mut to = s.clone();
                                to[*i] = next.to;
                                return Some(canonical_sum(to, &mut self.sum_ids));
                            }
                            *i += 1;
                            *moves = None;
                        }
                        None
                    },
                    true,
                )
            }
        } else {
            let (xor, odd) = self.reduce_sum(state);
            if xor == 0 && odd.len() == 1 {
                return self.outcome(odd.into_iter().next().unwrap(), false);
            }
            odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s)) != 0
        };
        GameOutcome::from_win(win)
    }

fn outcome(&mut self, state: &S, misere: bool) -> GameOutcome

Examples found in repository

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

    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))
    }
}

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>> {
        (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
    }
}

impl<S, L, F, I> Impartial<S, F>
where
    S: Clone + Eq + Hash,
    F: FnMut(&S) -> I,
    I: IntoIterator<Item = Neighbor<S, L>>,
{
    fn grundy(&mut self, state: &S) -> u64 {
        memoized_game(
            state,
            &mut self.grundy,
            &mut HashSet::new(),
            &mut |s| {
                if self.outcomes[0].get(s) == Some(&false) {
                    return ControlFlow::Break(0);
                }
                let moves = (self.moves)(s).into_iter().map(|n| (n.to, ()));
                ControlFlow::Continue((moves, Vec::new()))
            },
            &mut |_, moves| moves.next(),
            &mut |values, (), value| {
                values.push(value);
                ControlFlow::Continue(())
            },
            &mut |_, values| game_mex(values),
        )
    }

    fn outcome(&mut self, state: &S, misere: bool) -> GameOutcome {
        let win = memoized_wins(
            state,
            &mut self.outcomes[usize::from(misere)],
            |s| {
                if !misere && let Some(&value) = self.grundy.get(s) {
                    return ControlFlow::Break(value != 0);
                }
                let moves = (self.moves)(s).into_iter().map(|n| n.to);
                ControlFlow::Continue(moves)
            },
            |_, moves| moves.next(),
            misere,
        );
        GameOutcome::from_win(win)
    }

    fn winning_moves(&mut self, state: &S, misere: bool) -> impl Iterator<Item = Neighbor<S, L>> {
        (self.moves)(state).into_iter().filter(move |next| {
            if !misere && let Some(&value) = self.grundy.get(&next.to) {
                value == 0
            } else {
                self.outcome(&next.to, misere) == GameOutcome::Lose
            }
        })
    }

    fn sum_grundy(&mut self, state: &[S]) -> u64 {
        match state {
            [] => return 0,
            [single] => return self.grundy(single),
            _ => {}
        }
        let (xor, odd) = self.reduce_sum(state);
        odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s))
    }

    #[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
    fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.sum_grundy(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.grundy(component);
            for next in (self.moves)(component) {
                if self.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }

    fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome {
        if state.is_empty() {
            return GameOutcome::from_win(misere);
        }
        if let [single] = state {
            return self.outcome(single, misere);
        }
        let win = if misere {
            if let Some(&win) = self.sums.get(state) {
                win
            } else {
                memoized_wins(
                    &canonical_sum(state.to_vec(), &mut self.sum_ids),
                    &mut self.sums,
                    |_| ControlFlow::Continue((0, None)),
                    |s, (i, moves)| {
                        while *i < s.len() {
                            if *i != 0 && s[*i - 1] == s[*i] {
                                *i += 1;
                                continue;
                            }
                            let iterator =
                                moves.get_or_insert_with(|| (self.moves)(&s[*i]).into_iter());
                            if let Some(next) = iterator.next() {
                                let mut to = s.clone();
                                to[*i] = next.to;
                                return Some(canonical_sum(to, &mut self.sum_ids));
                            }
                            *i += 1;
                            *moves = None;
                        }
                        None
                    },
                    true,
                )
            }
        } else {
            let (xor, odd) = self.reduce_sum(state);
            if xor == 0 && odd.len() == 1 {
                return self.outcome(odd.into_iter().next().unwrap(), false);
            }
            odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s)) != 0
        };
        GameOutcome::from_win(win)
    }

fn winning_moves( &mut self, state: &S, misere: bool, ) -> impl Iterator<Item = Neighbor<S, L>>

Examples found in repository

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

    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
    }

fn sum_grundy(&mut self, state: &[S]) -> u64

Examples found in repository

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

    fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.sum_grundy(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.grundy(component);
            for next in (self.moves)(component) {
                if self.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }

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

Examples found in repository

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

    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
    }

fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome

Examples found in repository

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

    pub fn outcome(self) -> GameAnalysis<'a, Impartial<S, F>, [S], GameOutcome, MISERE> {
        GameAnalysis::new(self.game, |g, s| g.sum_outcome(s, MISERE))
    }

fn reduce_sum<'a>(&self, state: &'a [S]) -> (u64, HashSet<&'a S>)

Examples found in repository

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

    fn sum_grundy(&mut self, state: &[S]) -> u64 {
        match state {
            [] => return 0,
            [single] => return self.grundy(single),
            _ => {}
        }
        let (xor, odd) = self.reduce_sum(state);
        odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s))
    }

    #[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
    fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        let xor = self.sum_grundy(state);
        let mut result = Vec::new();
        if xor == 0 {
            return result;
        }
        for (i, component) in state.iter().enumerate() {
            let target = xor ^ self.grundy(component);
            for next in (self.moves)(component) {
                if self.grundy(&next.to) == target {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }

    fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome {
        if state.is_empty() {
            return GameOutcome::from_win(misere);
        }
        if let [single] = state {
            return self.outcome(single, misere);
        }
        let win = if misere {
            if let Some(&win) = self.sums.get(state) {
                win
            } else {
                memoized_wins(
                    &canonical_sum(state.to_vec(), &mut self.sum_ids),
                    &mut self.sums,
                    |_| ControlFlow::Continue((0, None)),
                    |s, (i, moves)| {
                        while *i < s.len() {
                            if *i != 0 && s[*i - 1] == s[*i] {
                                *i += 1;
                                continue;
                            }
                            let iterator =
                                moves.get_or_insert_with(|| (self.moves)(&s[*i]).into_iter());
                            if let Some(next) = iterator.next() {
                                let mut to = s.clone();
                                to[*i] = next.to;
                                return Some(canonical_sum(to, &mut self.sum_ids));
                            }
                            *i += 1;
                            *moves = None;
                        }
                        None
                    },
                    true,
                )
            }
        } else {
            let (xor, odd) = self.reduce_sum(state);
            if xor == 0 && odd.len() == 1 {
                return self.outcome(odd.into_iter().next().unwrap(), false);
            }
            odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s)) != 0
        };
        GameOutcome::from_win(win)
    }