Enum Player 

pub enum Player {
    Left,
    Right,
}

Variants

Left

Right

Implementations

impl Player

pub fn opponent(self) -> Self

Examples found in repository

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

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

crates/competitive/src/algorithm/game_analyzer/value.rs (line 354)

    fn from_options_memoized(
        mut left: Vec<Self>,
        mut right: Vec<Self>,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        loop {
            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
                let l = left.iter().filter_map(Self::as_number).max();
                let r = right.iter().filter_map(Self::as_number).min();
                if let Some(n) = Dyadic::simplest_between(l, r) {
                    return n.into();
                }
                let (l, r) = (l.unwrap(), r.unwrap());
                if l == r {
                    return Self::number_up_nimber(l, 0, 1);
                }
                let (sum, difference) = (l + r, l - r);
                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
                return Self::from_switches(
                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
                    0,
                    0,
                    vec![temperature],
                    Self::temperature_hash(temperature),
                );
            }
            if !right.is_empty()
                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
            {
                let nimber = |g: &Self| {
                    g.as_number_nimber()
                        .filter(|&(q, _)| q == number)
                        .map(|(_, n)| n)
                };
                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
                if let (Some(l), Some(r)) = (l, r) {
                    let value = game_mex(l);
                    if value == game_mex(r) {
                        return Self::number_up_nimber(number, 0, value);
                    }
                }
            }
            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
                if replies.len() != 1 {
                    continue;
                }
                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
                    if moves.len() == 1
                        && moves[0].as_number() == Some(q)
                        && (k == 0 || k.signum() == sign)
                    {
                        return Self::number_up_nimber(q, k + sign, n ^ 1);
                    }
                    if k == 0 && n == 0 && moves.len() == 2 {
                        let a = moves[0].as_number_nimber();
                        let b = moves[1].as_number_nimber();
                        if (a == Some((q, 0)) && b == Some((q, 1)))
                            || (a == Some((q, 1)) && b == Some((q, 0)))
                        {
                            return Self::number_up_nimber(q, sign, 1);
                        }
                    }
                }
            }
            if left.len() == 1
                && right.len() == 1
                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
                    (left[0].as_switch_sum(), right[0].as_switch_sum())
                && k == l
                && n == m
                && ts == us
                && a > b
            {
                let (sum, difference) = (a + b, a - b);
                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
                if ts.first().is_none_or(|&t| temperature > t) {
                    return Self::from_switches(
                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
                        k,
                        n,
                        std::iter::once(temperature)
                            .chain(ts.iter().copied())
                            .collect(),
                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
                    );
                }
            }
            let count = left.len() + right.len();
            Self::remove_dominated(&mut left, Player::Left, cache);
            Self::remove_dominated(&mut right, Player::Right, cache);
            if count != left.len() + right.len() {
                continue;
            }
            let options = Rc::new((left, right));
            let game = Self(GameValueNode::Options(0.into(), options.clone()));
            // Bypasses preserve the game, so all checks use the same candidate.
            let mut reversible = Vec::new();
            for player in [Player::Left, Player::Right] {
                let moves = match player {
                    Player::Left => &options.0,
                    Player::Right => &options.1,
                };
                for (i, g) in moves.iter().enumerate() {
                    if let Some((q, n)) = g.as_number_nimber()
                        && n > 1
                    {
                        let number = Self::from(q);
                        let (lower, upper) = match player {
                            Player::Left => (&game, &number),
                            Player::Right => (&number, &game),
                        };
                        // A strict inequality against q excludes every reply q + *m.
                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
                            continue;
                        }
                    }
                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
                        Player::Left => r.leq_memoized(&game, cache),
                        Player::Right => game.leq_memoized(r, cache),
                    }) {
                        reversible.push((player, i, reply));
                    }
                }
            }
            if reversible.is_empty() {
                return game;
            }
            drop(game);
            (left, right) = Rc::unwrap_or_clone(options);
            for (player, i, reply) in reversible.into_iter().rev() {
                let moves = if player == Player::Left {
                    &mut left
                } else {
                    &mut right
                };
                moves.remove(i);
                moves.extend(reply.options(player));
            }
        }
    }

Trait Implementations

impl Clone for Player

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Copy for Player

impl Debug for Player

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for Player

impl Hash for Player

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for Player

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for Player