algorithm.rs

//! Algorithm selection and pruning configuration.
//!
//! Rather than one big `if` tree, the solver is built from a couple of
//! separable choices: a [`SamplingScheme`] (how trajectories get sampled) and a
//! [`RegretVariant`] (how regret/average accumulate - see [`crate::regret`]).

pub use crate::regret::RegretVariant;

/// Training algorithm families offered by [`crate::trainer::Trainer`].
///
/// `#[non_exhaustive]`: we may add a variant in a minor release, so any
/// downstream `match` needs a `_` arm to stay compatible.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub enum Algorithm {
    /// External-sampling Monte-Carlo CFR (the workhorse for large games).
    /// Samples all *opponent* and chance action nodes; traverses every action
    /// of the investigating player. See Lanctot et al. 2009, "Monte Carlo
    /// Sampling for Regret Minimization in Extensive Games".
    ExternalSampling,
    /// Chance-sampling MCCFR: samples chance nodes, but traverses every action
    /// of *all* players. Lower variance than external sampling for games with
    /// little chance.
    ChanceSampling,
    /// Outcome-sampling MCCFR: samples a single full trajectory (including the
    /// investigating player's actions) with importance weighting. Memory-light;
    /// higher variance but tiny per-iteration cost.
    OutcomeSampling,
    /// Exact (full-tree) CFR: traverses the whole tree every iteration. No
    /// sampling; reference baseline for small games.
    FullTree,
}

impl Default for Algorithm {
    /// External-sampling MCCFR - the general-purpose workhorse for large games.
    fn default() -> Self {
        Algorithm::ExternalSampling
    }
}

impl Algorithm {
    /// The underlying sampling scheme.
    pub fn sampling(&self) -> SamplingScheme {
        match self {
            Algorithm::ExternalSampling => SamplingScheme::External,
            Algorithm::ChanceSampling => SamplingScheme::Chance,
            Algorithm::OutcomeSampling => SamplingScheme::Outcome,
            Algorithm::FullTree => SamplingScheme::Full,
        }
    }
}

/// Monte-Carlo sampling scheme, kept separate from the regret schedule.
///
/// Also `#[non_exhaustive]`; a later minor release could add a scheme, so
/// `match` on it with a `_` arm.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub enum SamplingScheme {
    /// Sample opponents and chance; full traversal of the target's actions.
    External,
    /// Sample chance only; full traversal of all players' actions.
    Chance,
    /// Sample the entire trajectory (incl. target) with importance weights.
    Outcome,
    /// No sampling - full tree.
    Full,
}

/// Pruning / variance-reduction strategy.
///
/// The idea: skip subtrees whose counterfactual regret is so far negative that
/// touching them is pointless, trading a bounded, safe bias for speed.
///
/// `#[non_exhaustive]`, same as the other enums here. Assume new arms could
/// show up in a minor release and `_`-match accordingly.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub enum Pruning {
    /// No pruning.
    None,
    /// Regret-based *safe* pruning (Brown & Sandholm 2015/2019). Only prunes
    /// information sets whose current average strategy puts (near-)zero
    /// probability on an action *and* whose regret is negative; guarantees no
    /// increase in Nash exploitability beyond the discounting already present.
    Safe,
    /// Probabilistic / Pluribus-style pruning: after a `warmup` number of
    /// iterations, an action whose average-strategy weight is (near) zero is
    /// skipped with probability `probability` on each visit. It does **not**
    /// threshold on positive counterfactual regret (unlike the literal Pluribus
    /// rule); eligibility is the same avg-weight-near-zero test used by
    /// [`Pruning::Safe`], merely made stochastic. Faster than `Safe` pruning but
    /// not provably safe.
    Probabilistic {
        /// Iterations to run unpruned before enabling pruning.
        warmup: u64,
        /// Probability of applying the prune check at a node.
        probability: f64,
    },
}

/// Variance-reduction schemes for the sampling algorithms.
///
/// `#[non_exhaustive]`; minor-release additions only, so keep a `_` arm in your
/// `match`.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub enum VarianceReduction {
    /// No variance reduction; plain importance-weighted sampling.
    None,
    /// Control-variate (baseline) variance reduction for outcome sampling
    /// (VR-MCCFR, Schmid et al. 2019, "Variance Reduction in Monte-Carlo
    /// Counterfactual Regret Minimization"). Each sampled return is centred on a
    /// per-information-set running-mean baseline before being importance
    /// weighted, and the baseline is added back; because the baseline's
    /// expectation equals the quantity being estimated, the estimator stays
    /// unbiased while its variance drops. Only affects [`Algorithm::OutcomeSampling`];
    /// other schemes ignore it.
    ControlVariate,
}

impl Default for VarianceReduction {
    fn default() -> Self {
        VarianceReduction::None
    }
}