Struct GameValue 

pub struct GameValue(GameValueNode);

A canonical finite normal-play game. Numbers use Dyadic<i64>. PartialOrd is the game order: None means fuzzy, not a numeric approximation.

use competitive::algorithm::GameValue;
let zero = GameValue::from(0);
let star = GameValue::nimber(1);
let up = GameValue::from_options([zero.clone()], [star.clone()]);
assert!(up > zero);
assert_eq!(star.partial_cmp(&zero), None);
assert_eq!(star.clone() + star, zero);

Tuple Fields

0: GameValueNode

Implementations

impl GameValue

pub fn nimber(value: u64) -> Self

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

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

    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 number_up_nimber(number: Dyadic<i64>, up: i64, nimber: u64) -> Self

Constructs number + up * ↑ + *nimber without expanding options.

Examples found in repository

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

    pub fn nimber(value: u64) -> Self {
        Self::number_up_nimber(0.into(), 0, value)
    }

    /// Constructs `number + up * ↑ + *nimber` without expanding options.
    pub fn number_up_nimber(number: Dyadic<i64>, up: i64, nimber: u64) -> Self {
        Self(GameValueNode::NumberUpNimber(number, up, nimber))
    }

    pub fn as_number(&self) -> Option<Dyadic<i64>> {
        match self.0 {
            GameValueNode::NumberUpNimber(n, 0, 0) => Some(n),
            _ => None,
        }
    }

    pub fn as_nimber(&self) -> Option<u64> {
        match self.0 {
            GameValueNode::NumberUpNimber(q, 0, n) if q.numerator() == 0 => Some(n),
            _ => None,
        }
    }

    /// Returns `(q, n)` when the value is `q + *n`.
    pub fn as_number_nimber(&self) -> Option<(Dyadic<i64>, u64)> {
        match self.0 {
            GameValueNode::NumberUpNimber(q, 0, n) => Some((q, n)),
            _ => None,
        }
    }

    /// Returns `(q, k, n)` when the value is `q + k↑ + *n`.
    pub fn as_number_up_nimber(&self) -> Option<(Dyadic<i64>, i64, u64)> {
        match self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Some((q, k, n)),
            _ => None,
        }
    }

    /// Returns `(q, k, n, temperatures)` for `q + k↑ + *n + Σ{t|-t}`.
    /// Temperatures are positive and strictly decreasing; the slice may be empty.
    #[allow(clippy::type_complexity)] // Borrows the components without a separate public type.
    pub fn as_switch_sum(&self) -> Option<(Dyadic<i64>, i64, u64, &[Dyadic<i64>])> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Some((*q, *k, *n, &[])),
            GameValueNode::Switches(value) => Some((
                value.number,
                value.up,
                value.nimber,
                &value.temperatures[value.start..],
            )),
            _ => None,
        }
    }

    pub fn outcome(&self) -> PartisanOutcome {
        match self.partial_cmp(&Self::from(0)) {
            Some(Ordering::Greater) => PartisanOutcome::Left,
            Some(Ordering::Less) => PartisanOutcome::Right,
            Some(Ordering::Equal) => PartisanOutcome::Previous,
            None => PartisanOutcome::Next,
        }
    }

    /// Whether the selected starting player can force a win.
    pub fn wins(&self, player: Player) -> bool {
        match player {
            Player::Left => !self.leq(&Self::from(0)),
            Player::Right => !Self::from(0).leq(self),
        }
    }

    /// Removes dominated and reversible options.
    pub fn from_options(
        left: impl IntoIterator<Item = Self>,
        right: impl IntoIterator<Item = Self>,
    ) -> Self {
        Self::from_options_memoized(
            left.into_iter().collect(),
            right.into_iter().collect(),
            &mut HashMap::new(),
        )
    }

    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
        let mut offset = Dyadic::from(0);
        let (single, nimbers, general) = match &self.0 {
            GameValueNode::NumberUpNimber(n, 0, 0) => {
                let option = if n.exponent() == 0 {
                    match player {
                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
                        _ => None,
                    }
                } else {
                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
                    Some(Dyadic::new(numerator, n.exponent() - 1))
                };
                (option.map(Self::from), None, &[][..])
            }
            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
            GameValueNode::NumberUpNimber(q, k, 1)
                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
            {
                (None, Some((*q, 2)), &[][..])
            }
            GameValueNode::NumberUpNimber(q, k, n) => {
                let sign = if *k > 0 { 1 } else { -1 };
                let moves_to_number = (*k > 0) == (player == Player::Left);
                let option = if moves_to_number {
                    Self::from(*q)
                } else {
                    Self::number_up_nimber(*q, k - sign, n ^ 1)
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Switches(value) => {
                let temperatures = &value.temperatures[value.start..];
                let t = if player == Player::Left {
                    temperatures[0]
                } else {
                    -temperatures[0]
                };
                let option = if temperatures.len() == 1 {
                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
                } else {
                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                        number: value.number + t,
                        start: value.start + 1,
                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
                        ..(**value).clone()
                    })))
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Options(q, options) => {
                offset = *q;
                let (left, right) = &**options;
                let moves = if player == Player::Left { left } else { right };
                (None, None, moves.as_slice())
            }
        };
        single
            .into_iter()
            .chain(
                nimbers
                    .into_iter()
                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
            )
            .chain(general.iter().map(move |g| g.translated(offset)))
    }

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }

pub fn as_number(&self) -> Option<Dyadic<i64>>

Examples found in repository

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

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

pub fn as_nimber(&self) -> Option<u64>

Examples found in repository

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

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

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

    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }

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

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

pub fn as_number_nimber(&self) -> Option<(Dyadic<i64>, u64)>

Returns (q, n) when the value is q + *n.

Examples found in repository

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

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

pub fn as_number_up_nimber(&self) -> Option<(Dyadic<i64>, i64, u64)>

Returns (q, k, n) when the value is q + k↑ + *n.

Examples found in repository

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

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

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

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

pub fn as_switch_sum(&self) -> Option<(Dyadic<i64>, i64, u64, &[Dyadic<i64>])>

Returns (q, k, n, temperatures) for q + k↑ + *n + Σ{t|-t}. Temperatures are positive and strictly decreasing; the slice may be empty.

Examples found in repository

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

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

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }
}
impl Sub for GameValue {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        if self.0 == rhs.0 {
            Self::from(0)
        } else {
            self + -rhs
        }
    }
}
impl Sum for GameValue {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }
}
impl PartialEq for GameValue {
    fn eq(&self, rhs: &Self) -> bool {
        match (&self.0, &rhs.0) {
            (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) => {
                return a == b && k == l && n == m;
            }
            (GameValueNode::Switches(_), GameValueNode::Switches(_)) => {
                return self.0 == rhs.0;
            }
            _ => {}
        }
        let mut cache = HashMap::new();
        self.leq_memoized(rhs, &mut cache) && rhs.leq_memoized(self, &mut cache)
    }
}
impl Eq for GameValue {}
impl PartialOrd for GameValue {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        let mut cache = HashMap::new();
        match (
            self.leq_memoized(rhs, &mut cache),
            rhs.leq_memoized(self, &mut cache),
        ) {
            (true, true) => Some(Ordering::Equal),
            (true, false) => Some(Ordering::Less),
            (false, true) => Some(Ordering::Greater),
            (false, false) => None,
        }
    }
}
impl fmt::Display for GameValue {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some((q, k, n, temperatures)) = self.as_switch_sum() {
            let mut separator = "";
            if q.numerator() != 0 || k == 0 && n == 0 && temperatures.is_empty() {
                write!(f, "{q}")?;
                separator = "+";
            }
            if k != 0 {
                f.write_str(separator)?;
                if k.unsigned_abs() != 1 {
                    write!(f, "{}", k.unsigned_abs())?;
                }
                f.write_str(if k > 0 { "↑" } else { "↓" })?;
                separator = "+";
            }
            if n != 0 {
                write!(f, "{separator}*")?;
                if n != 1 {
                    write!(f, "{n}")?;
                }
                separator = "+";
            }
            for t in temperatures {
                write!(f, "{separator}{{{t}|{}}}", -*t)?;
                separator = "+";
            }
            return Ok(());
        }
        f.write_str("{")?;
        for (separator, player) in [("", Player::Left), ("|", Player::Right)] {
            f.write_str(separator)?;
            for (i, g) in self.options(player).enumerate() {
                if i > 0 {
                    f.write_str(",")?;
                }
                write!(f, "{g}")?;
            }
        }
        f.write_str("}")
    }

pub fn outcome(&self) -> PartisanOutcome

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

Whether the selected starting player can force a win.

Examples found in repository

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

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

pub fn from_options( left: impl IntoIterator<Item = Self>, right: impl IntoIterator<Item = Self>, ) -> Self

Removes dominated and reversible options.

Examples found in repository

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

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

pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_

Examples found in repository

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }
}
impl Sub for GameValue {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        if self.0 == rhs.0 {
            Self::from(0)
        } else {
            self + -rhs
        }
    }
}
impl Sum for GameValue {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }
}
impl PartialEq for GameValue {
    fn eq(&self, rhs: &Self) -> bool {
        match (&self.0, &rhs.0) {
            (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) => {
                return a == b && k == l && n == m;
            }
            (GameValueNode::Switches(_), GameValueNode::Switches(_)) => {
                return self.0 == rhs.0;
            }
            _ => {}
        }
        let mut cache = HashMap::new();
        self.leq_memoized(rhs, &mut cache) && rhs.leq_memoized(self, &mut cache)
    }
}
impl Eq for GameValue {}
impl PartialOrd for GameValue {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        let mut cache = HashMap::new();
        match (
            self.leq_memoized(rhs, &mut cache),
            rhs.leq_memoized(self, &mut cache),
        ) {
            (true, true) => Some(Ordering::Equal),
            (true, false) => Some(Ordering::Less),
            (false, true) => Some(Ordering::Greater),
            (false, false) => None,
        }
    }
}
impl fmt::Display for GameValue {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some((q, k, n, temperatures)) = self.as_switch_sum() {
            let mut separator = "";
            if q.numerator() != 0 || k == 0 && n == 0 && temperatures.is_empty() {
                write!(f, "{q}")?;
                separator = "+";
            }
            if k != 0 {
                f.write_str(separator)?;
                if k.unsigned_abs() != 1 {
                    write!(f, "{}", k.unsigned_abs())?;
                }
                f.write_str(if k > 0 { "↑" } else { "↓" })?;
                separator = "+";
            }
            if n != 0 {
                write!(f, "{separator}*")?;
                if n != 1 {
                    write!(f, "{n}")?;
                }
                separator = "+";
            }
            for t in temperatures {
                write!(f, "{separator}{{{t}|{}}}", -*t)?;
                separator = "+";
            }
            return Ok(());
        }
        f.write_str("{")?;
        for (separator, player) in [("", Player::Left), ("|", Player::Right)] {
            f.write_str(separator)?;
            for (i, g) in self.options(player).enumerate() {
                if i > 0 {
                    f.write_str(",")?;
                }
                write!(f, "{g}")?;
            }
        }
        f.write_str("}")
    }

fn from_options_memoized( left: Vec<Self>, right: Vec<Self>, cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>, ) -> Self

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/value.rs (lines 162-166)

    pub fn from_options(
        left: impl IntoIterator<Item = Self>,
        right: impl IntoIterator<Item = Self>,
    ) -> Self {
        Self::from_options_memoized(
            left.into_iter().collect(),
            right.into_iter().collect(),
            &mut HashMap::new(),
        )
    }

    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
        let mut offset = Dyadic::from(0);
        let (single, nimbers, general) = match &self.0 {
            GameValueNode::NumberUpNimber(n, 0, 0) => {
                let option = if n.exponent() == 0 {
                    match player {
                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
                        _ => None,
                    }
                } else {
                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
                    Some(Dyadic::new(numerator, n.exponent() - 1))
                };
                (option.map(Self::from), None, &[][..])
            }
            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
            GameValueNode::NumberUpNimber(q, k, 1)
                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
            {
                (None, Some((*q, 2)), &[][..])
            }
            GameValueNode::NumberUpNimber(q, k, n) => {
                let sign = if *k > 0 { 1 } else { -1 };
                let moves_to_number = (*k > 0) == (player == Player::Left);
                let option = if moves_to_number {
                    Self::from(*q)
                } else {
                    Self::number_up_nimber(*q, k - sign, n ^ 1)
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Switches(value) => {
                let temperatures = &value.temperatures[value.start..];
                let t = if player == Player::Left {
                    temperatures[0]
                } else {
                    -temperatures[0]
                };
                let option = if temperatures.len() == 1 {
                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
                } else {
                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                        number: value.number + t,
                        start: value.start + 1,
                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
                        ..(**value).clone()
                    })))
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Options(q, options) => {
                offset = *q;
                let (left, right) = &**options;
                let moves = if player == Player::Left { left } else { right };
                (None, None, moves.as_slice())
            }
        };
        single
            .into_iter()
            .chain(
                nimbers
                    .into_iter()
                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
            )
            .chain(general.iter().map(move |g| g.translated(offset)))
    }

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

fn leq(&self, rhs: &Self) -> bool

Examples found in repository

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

    pub fn wins(&self, player: Player) -> bool {
        match player {
            Player::Left => !self.leq(&Self::from(0)),
            Player::Right => !Self::from(0).leq(self),
        }
    }

fn leq_memoized( &self, rhs: &Self, cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>, ) -> bool

Examples found in repository

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

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }
}
impl Sub for GameValue {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        if self.0 == rhs.0 {
            Self::from(0)
        } else {
            self + -rhs
        }
    }
}
impl Sum for GameValue {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }
}
impl PartialEq for GameValue {
    fn eq(&self, rhs: &Self) -> bool {
        match (&self.0, &rhs.0) {
            (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) => {
                return a == b && k == l && n == m;
            }
            (GameValueNode::Switches(_), GameValueNode::Switches(_)) => {
                return self.0 == rhs.0;
            }
            _ => {}
        }
        let mut cache = HashMap::new();
        self.leq_memoized(rhs, &mut cache) && rhs.leq_memoized(self, &mut cache)
    }
}
impl Eq for GameValue {}
impl PartialOrd for GameValue {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        let mut cache = HashMap::new();
        match (
            self.leq_memoized(rhs, &mut cache),
            rhs.leq_memoized(self, &mut cache),
        ) {
            (true, true) => Some(Ordering::Equal),
            (true, false) => Some(Ordering::Less),
            (false, true) => Some(Ordering::Greater),
            (false, false) => None,
        }
    }

fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self

Examples found in repository

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

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }

fn sum( &self, rhs: &Self, cache: &mut HashMap<(GameValueNode, GameValueNode), Self>, comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>, ) -> Self

Examples found in repository

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

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }

fn number_offset(&self) -> Dyadic<i64>

Examples found in repository

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

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

fn translated(&self, number: Dyadic<i64>) -> Self

Examples found in repository

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

    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
        let mut offset = Dyadic::from(0);
        let (single, nimbers, general) = match &self.0 {
            GameValueNode::NumberUpNimber(n, 0, 0) => {
                let option = if n.exponent() == 0 {
                    match player {
                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
                        _ => None,
                    }
                } else {
                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
                    Some(Dyadic::new(numerator, n.exponent() - 1))
                };
                (option.map(Self::from), None, &[][..])
            }
            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
            GameValueNode::NumberUpNimber(q, k, 1)
                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
            {
                (None, Some((*q, 2)), &[][..])
            }
            GameValueNode::NumberUpNimber(q, k, n) => {
                let sign = if *k > 0 { 1 } else { -1 };
                let moves_to_number = (*k > 0) == (player == Player::Left);
                let option = if moves_to_number {
                    Self::from(*q)
                } else {
                    Self::number_up_nimber(*q, k - sign, n ^ 1)
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Switches(value) => {
                let temperatures = &value.temperatures[value.start..];
                let t = if player == Player::Left {
                    temperatures[0]
                } else {
                    -temperatures[0]
                };
                let option = if temperatures.len() == 1 {
                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
                } else {
                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                        number: value.number + t,
                        start: value.start + 1,
                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
                        ..(**value).clone()
                    })))
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Options(q, options) => {
                offset = *q;
                let (left, right) = &**options;
                let moves = if player == Player::Left { left } else { right };
                (None, None, moves.as_slice())
            }
        };
        single
            .into_iter()
            .chain(
                nimbers
                    .into_iter()
                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
            )
            .chain(general.iter().map(move |g| g.translated(offset)))
    }

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

fn temperature_hash(t: Dyadic<i64>) -> u64

Examples found in repository

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

    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
        let mut offset = Dyadic::from(0);
        let (single, nimbers, general) = match &self.0 {
            GameValueNode::NumberUpNimber(n, 0, 0) => {
                let option = if n.exponent() == 0 {
                    match player {
                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
                        _ => None,
                    }
                } else {
                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
                    Some(Dyadic::new(numerator, n.exponent() - 1))
                };
                (option.map(Self::from), None, &[][..])
            }
            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
            GameValueNode::NumberUpNimber(q, k, 1)
                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
            {
                (None, Some((*q, 2)), &[][..])
            }
            GameValueNode::NumberUpNimber(q, k, n) => {
                let sign = if *k > 0 { 1 } else { -1 };
                let moves_to_number = (*k > 0) == (player == Player::Left);
                let option = if moves_to_number {
                    Self::from(*q)
                } else {
                    Self::number_up_nimber(*q, k - sign, n ^ 1)
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Switches(value) => {
                let temperatures = &value.temperatures[value.start..];
                let t = if player == Player::Left {
                    temperatures[0]
                } else {
                    -temperatures[0]
                };
                let option = if temperatures.len() == 1 {
                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
                } else {
                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                        number: value.number + t,
                        start: value.start + 1,
                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
                        ..(**value).clone()
                    })))
                };
                (Some(option), None, &[][..])
            }
            GameValueNode::Options(q, options) => {
                offset = *q;
                let (left, right) = &**options;
                let moves = if player == Player::Left { left } else { right };
                (None, None, moves.as_slice())
            }
        };
        single
            .into_iter()
            .chain(
                nimbers
                    .into_iter()
                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
            )
            .chain(general.iter().map(move |g| g.translated(offset)))
    }

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

fn switch_hash(&self) -> u64

Examples found in repository

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

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }
}
impl Sub for GameValue {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        if self.0 == rhs.0 {
            Self::from(0)
        } else {
            self + -rhs
        }
    }
}
impl Sum for GameValue {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }

fn from_switches( q: Dyadic<i64>, k: i64, n: u64, temperatures: Vec<Dyadic<i64>>, fingerprint: u64, ) -> Self

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/value.rs (lines 255-261)

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

    fn leq(&self, rhs: &Self) -> bool {
        self.leq_memoized(rhs, &mut HashMap::new())
    }

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

    fn number_offset(&self) -> Dyadic<i64> {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
            GameValueNode::Switches(v) => v.number,
        }
    }

    fn translated(&self, number: Dyadic<i64>) -> Self {
        if number.numerator() == 0 {
            return self.clone();
        }
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
            GameValueNode::Switches(v) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: v.number + number,
                    ..(**v).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                Self(GameValueNode::Options(*q + number, options.clone()))
            }
        }
    }

    fn temperature_hash(t: Dyadic<i64>) -> u64 {
        let mut hasher = DefaultHasher::new();
        t.hash(&mut hasher);
        hasher.finish()
    }

    fn switch_hash(&self) -> u64 {
        match &self.0 {
            GameValueNode::NumberUpNimber(..) => 0,
            GameValueNode::Switches(v) => v.fingerprint,
            GameValueNode::Options(..) => unreachable!(),
        }
    }

    fn from_switches(
        q: Dyadic<i64>,
        k: i64,
        n: u64,
        temperatures: Vec<Dyadic<i64>>,
        fingerprint: u64,
    ) -> Self {
        if temperatures.is_empty() {
            Self::number_up_nimber(q, k, n)
        } else {
            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                number: q,
                up: k,
                nimber: n,
                fingerprint,
                temperatures: Rc::new(temperatures),
                start: 0,
            })))
        }
    }

    fn switch_difference<'a>(
        mut left: &'a [Dyadic<i64>],
        mut right: &'a [Dyadic<i64>],
    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
        std::iter::from_fn(move || {
            while let (Some(a), Some(b)) = (left.first(), right.first()) {
                if a != b {
                    break;
                }
                left = &left[1..];
                right = &right[1..];
            }
            if left.first() < right.first() {
                std::mem::swap(&mut left, &mut right);
            }
            let (&value, tail) = left.split_first()?;
            left = tail;
            Some(value)
        })
    }

    fn remove_dominated(
        options: &mut Vec<Self>,
        player: Player,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) {
        let mut retained = vec![true; options.len()];
        for i in 0..options.len() {
            let dominated = (0..options.len()).any(|j| {
                i != j
                    && retained[j]
                    && match player {
                        Player::Left => options[i].leq_memoized(&options[j], cache),
                        Player::Right => options[j].leq_memoized(&options[i], cache),
                    }
            });
            retained[i] = !dominated;
        }
        let mut retained = retained.into_iter();
        options.retain(|_| retained.next().unwrap());
    }
}

impl From<i64> for GameValue {
    fn from(value: i64) -> Self {
        Dyadic::from(value).into()
    }
}
impl From<Dyadic<i64>> for GameValue {
    fn from(value: Dyadic<i64>) -> Self {
        Self::number_up_nimber(value, 0, 0)
    }
}
impl Neg for GameValue {
    type Output = Self;
    fn neg(self) -> Self {
        self.negated(&mut HashMap::new())
    }
}
impl Add for GameValue {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
    }
}
impl Sub for GameValue {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        if self.0 == rhs.0 {
            Self::from(0)
        } else {
            self + -rhs
        }
    }
}
impl Sum for GameValue {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
        let mut temperatures = Vec::new();
        let mut fingerprint = 0;
        let mut general = Self::from(0);
        for value in iter {
            if let Some((q, k, n, ts)) = value.as_switch_sum() {
                number = number + q;
                up += k;
                nimber ^= n;
                temperatures.extend_from_slice(ts);
                fingerprint ^= value.switch_hash();
            } else {
                general = general + value;
            }
        }
        temperatures.sort_unstable_by(|a, b| b.cmp(a));
        let mut retained = 0;
        for i in 0..temperatures.len() {
            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
                retained -= 1;
            } else {
                temperatures[retained] = temperatures[i];
                retained += 1;
            }
        }
        temperatures.truncate(retained);
        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
        if general.as_nimber() == Some(0) {
            value
        } else {
            value + general
        }
    }

fn switch_difference<'a>( left: &'a [Dyadic<i64>], right: &'a [Dyadic<i64>], ) -> impl Iterator<Item = Dyadic<i64>> + 'a

Examples found in repository

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

    fn leq_memoized(
        &self,
        rhs: &Self,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> bool {
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            // Both players take the hottest remaining switch. At zero, the tail
            // decides the winner with the turn reversed once per switch.
            let mut number = a;
            let mut odd = false;
            for t in Self::switch_difference(ts, us) {
                // The unplayed alternating tail has the sign of the next term.
                if !odd && number >= b || odd && number <= b {
                    return odd;
                }
                number = if odd { number - t } else { number + t };
                odd = !odd;
            }
            return match number.cmp(&b) {
                Ordering::Less => true,
                Ordering::Greater => false,
                Ordering::Equal => {
                    let up = if odd { l - k } else { k - l };
                    let nimber = n ^ m;
                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
                    wins == odd
                }
            };
        }
        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
            && Rc::ptr_eq(g, h)
        {
            return a <= b;
        }
        // Normalize only memo keys: from_options also compares unreduced candidates.
        let offset = -self.number_offset();
        let left = self.translated(offset).0;
        let right = rhs.translated(offset).0;
        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
            return value;
        }
        // Try explicit options before expanding a compact value.
        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
        if self.as_switch_sum().is_some() {
            sides.swap(0, 1);
        }
        let value = sides.into_iter().all(|(game, other, player)| {
            let mut preferred = |a: &Self, b: &Self| match player {
                Player::Left => b.leq_memoized(a, cache),
                Player::Right => a.leq_memoized(b, cache),
            };
            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
                && n != 0
            {
                let number = Self::from(q);
                !preferred(&number, other)
                    && (preferred(other, &number)
                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
            } else {
                !game.options(player).any(|g| preferred(&g, other))
            }
        });
        cache.entry(left).or_default().insert(right, value);
        value
    }

    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
        match &self.0 {
            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
            GameValueNode::Switches(value) => {
                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
                    number: -value.number,
                    up: -value.up,
                    ..(**value).clone()
                })))
            }
            GameValueNode::Options(q, options) => {
                let key = Rc::as_ptr(options) as usize;
                if let Some(value) = cache.get(&key) {
                    return value.translated(-*q);
                }
                let (left, right) = &**options;
                let value = Self(GameValueNode::Options(
                    0.into(),
                    Rc::new((
                        right.iter().map(|g| g.negated(cache)).collect(),
                        left.iter().map(|g| g.negated(cache)).collect(),
                    )),
                ));
                cache.insert(key, value.clone());
                value.translated(-*q)
            }
        }
    }

    fn sum(
        &self,
        rhs: &Self,
        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
            (&self.0, &rhs.0)
        {
            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
        }
        if let Some(q) = self.as_number() {
            return rhs.translated(q);
        }
        if let Some(q) = rhs.as_number() {
            return self.translated(q);
        }
        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
            (self.as_switch_sum(), rhs.as_switch_sum())
        {
            return Self::from_switches(
                a + b,
                k + l,
                n ^ m,
                Self::switch_difference(ts, us).collect(),
                self.switch_hash() ^ rhs.switch_hash(),
            );
        }
        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
        let (a, b) = (self.number_offset(), rhs.number_offset());
        if a.numerator() != 0 || b.numerator() != 0 {
            return self
                .translated(-a)
                .sum(&rhs.translated(-b), cache, comparisons)
                .translated(a + b);
        }
        let mut key = (self.0.clone(), rhs.0.clone());
        let swap = match (&key.0, &key.1) {
            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
                Rc::as_ptr(a) > Rc::as_ptr(b)
            }
            (GameValueNode::Options(..), _) => true,
            _ => false,
        };
        if swap {
            std::mem::swap(&mut key.0, &mut key.1);
        }
        if let Some(value) = cache.get(&key) {
            return value.clone();
        }
        let mut options = |player| {
            let mut moves = Vec::new();
            for g in self.options(player) {
                moves.push(g.sum(rhs, cache, comparisons));
            }
            for g in rhs.options(player) {
                moves.push(self.sum(&g, cache, comparisons));
            }
            moves
        };
        let value =
            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
        cache.insert(key, value.clone());
        value
    }

fn remove_dominated( options: &mut Vec<Self>, player: Player, cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>, )

Examples found in repository

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

    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 Add for GameValue

type Output = GameValue

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl Clone for GameValue

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for GameValue

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

Formats the value using the given formatter.

impl Display for GameValue

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

Formats the value using the given formatter.

impl Eq for GameValue

impl From<Dyadic<i64>> for GameValue

fn from(value: Dyadic<i64>) -> Self

Converts to this type from the input type.

impl From<i64> for GameValue

fn from(value: i64) -> Self

Converts to this type from the input type.

impl Neg for GameValue

type Output = GameValue

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl PartialEq for GameValue

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

Equality operator ==.

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

Inequality operator !=.

impl PartialOrd for GameValue

fn partial_cmp(&self, rhs: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Sub for GameValue

type Output = GameValue

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl Sum for GameValue

fn sum<I>(iter: I) -> Self

where I: Iterator<Item = Self>,

Takes an iterator and generates Self from the elements by “summing up” the items.