Struct Partisan 

pub struct Partisan<S, FL, FR> {
    left: FL,
    right: FR,
    values: HashMap<S, GameValue>,
    outcomes: [HashMap<(S, Player), bool>; 2],
    sums: [HashMap<(Vec<S>, Player), bool>; 2],
    sum_ids: HashMap<S, usize>,
}

Fields

left: FL

right: FR

values: HashMap<S, GameValue>

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

sums: [HashMap<(Vec<S>, Player), bool>; 2]

sum_ids: HashMap<S, usize>

Implementations

impl<S, L, FL, FR, IL, IR> 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>>,

fn value(&mut self, state: &S) -> GameValue

Examples found in repository

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

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

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

Examples found in repository

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

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

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

Examples found in repository

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

    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
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
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.sum_wins(state, player, MISERE)
    }

    pub fn winning_moves(
        &mut self,
        state: &[S],
        player: Player,
    ) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        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;
                if !self.game.sum_wins(&to, player.opponent(), MISERE) {
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }
}

impl<S, L, FL, FR, IL, IR> 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>>,
{
    fn value(&mut self, state: &S) -> GameValue {
        memoized_game(
            state,
            &mut self.values,
            &mut HashSet::new(),
            &mut |s| {
                let moves = (self.left)(s)
                    .into_iter()
                    .map(|n| (n.to, Player::Left))
                    .chain((self.right)(s).into_iter().map(|n| (n.to, Player::Right)));
                ControlFlow::Continue((moves, (Vec::new(), Vec::new())))
            },
            &mut |_, moves| moves.next(),
            &mut |(left, right), player, value| {
                if player == Player::Left {
                    left.push(value)
                } else {
                    right.push(value)
                }
                ControlFlow::Continue(())
            },
            &mut |_, (left, right)| GameValue::from_options(left, right),
        )
    }

    fn outcome(&mut self, state: &S, misere: bool) -> PartisanOutcome {
        match (
            self.wins(state, Player::Left, misere),
            self.wins(state, Player::Right, misere),
        ) {
            (true, true) => PartisanOutcome::Next,
            (false, false) => PartisanOutcome::Previous,
            (true, false) => PartisanOutcome::Left,
            (false, true) => PartisanOutcome::Right,
        }
    }

    fn wins(&mut self, state: &S, player: Player, misere: bool) -> bool {
        let key = (state.clone(), player);
        memoized_wins(
            &key,
            &mut self.outcomes[usize::from(misere)],
            |(s, p)| {
                if !misere && let Some(value) = self.values.get(s) {
                    return ControlFlow::Break(value.wins(*p));
                }
                let next_player = p.opponent();
                let moves = partisan_moves(&mut self.left, &mut self.right, s, *p)
                    .map(move |n| (n.to, next_player));
                ControlFlow::Continue(moves)
            },
            |_, moves| moves.next(),
            misere,
        )
    }

    fn sum_wins(&mut self, state: &[S], player: Player, misere: bool) -> bool {
        match state {
            [] => return misere,
            [single] => return self.wins(single, player, misere),
            _ => {}
        }
        let mut normalize = |mut state: Vec<S>| {
            if !misere {
                state.retain(|s| {
                    if let Some(value) = self.values.get(s) {
                        return value.as_nimber() != Some(0);
                    }
                    let mut key = (s.clone(), Player::Left);
                    if self.outcomes[0].get(&key) != Some(&false) {
                        return true;
                    }
                    key.1 = Player::Right;
                    self.outcomes[0].get(&key) != Some(&false)
                });
            }
            canonical_sum(state, &mut self.sum_ids)
        };
        let state = normalize(state.to_vec());
        match state.as_slice() {
            [] => return misere,
            [single] => return self.wins(single, player, misere),
            _ => {}
        }
        let key = (state, player);
        memoized_wins(
            &key,
            &mut self.sums[usize::from(misere)],
            |(s, p)| {
                if !misere
                    && s.iter().all(|s| {
                        self.values
                            .get(s)
                            .is_some_and(|g| g.as_switch_sum().is_some())
                    })
                {
                    let value: GameValue = s.iter().map(|s| self.values[s].clone()).sum();
                    return ControlFlow::Break(value.wins(*p));
                }
                // Losing as starter in every component implies losing in the sum.
                // One known win is enough if the opponent loses in every other component.
                if !misere && (!self.values.is_empty() || !self.outcomes[0].is_empty()) {
                    let mut all_lose = true;
                    let mut all_opponent_lose = true;
                    let mut can_win = false;
                    for s in s {
                        let (mut win, mut opponent_win) = (None, None);
                        if !self.outcomes[0].is_empty() {
                            let mut key = (s.clone(), *p);
                            win = self.outcomes[0].get(&key).copied();
                            key.1 = p.opponent();
                            opponent_win = self.outcomes[0].get(&key).copied();
                        }
                        if let Some(value) = self.values.get(s) {
                            win.get_or_insert_with(|| value.wins(*p));
                            opponent_win.get_or_insert_with(|| value.wins(p.opponent()));
                        }
                        can_win = can_win && opponent_win == Some(false)
                            || all_opponent_lose && win == Some(true);
                        all_lose &= win == Some(false);
                        all_opponent_lose &= opponent_win == Some(false);
                        if !all_lose && !all_opponent_lose && !can_win {
                            break;
                        }
                    }
                    if all_lose || can_win {
                        return ControlFlow::Break(can_win);
                    }
                }
                ControlFlow::Continue((0, None))
            },
            |(s, p), (i, moves)| {
                while *i < s.len() {
                    if *i != 0 && s[*i - 1] == s[*i] {
                        *i += 1;
                        continue;
                    }
                    let iterator = moves.get_or_insert_with(|| {
                        partisan_moves(&mut self.left, &mut self.right, &s[*i], *p)
                    });
                    if let Some(next) = iterator.next() {
                        let mut to = s.clone();
                        to[*i] = next.to;
                        return Some((normalize(to), p.opponent()));
                    }
                    *i += 1;
                    *moves = None;
                }
                None
            },
            misere,
        )
    }

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

Examples found in repository

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

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

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,
{
    /// Values describe the destination game for both choices of starting player.
    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
    }
}
#[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
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.sum_wins(state, player, MISERE)
    }

    pub fn winning_moves(
        &mut self,
        state: &[S],
        player: Player,
    ) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        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;
                if !self.game.sum_wins(&to, player.opponent(), MISERE) {
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
        }
        result
    }