cp_validator/

rating.rs

//! OpenSkill Bayesian rating implementation.
//!
//! Implements the Thurstone-Mosteller model used by OpenSkill for pairwise
//! skill estimation. Each player (contributor or peer) has a mean skill
//! estimate (mu) and an uncertainty (sigma). Ratings update through pairwise
//! comparisons using truncated Gaussian updates.
//!
//! Per CP-015 section 8: the core algorithm follows Weng and Lin (2011),
//! adapted from the TrueSkill framework.

use serde::{Deserialize, Serialize};
use std::f64::consts::{FRAC_1_SQRT_2, PI};

/// Performance variance parameter. Represents the standard deviation of
/// performance around true skill. Set to default_mu / 6 following the
/// TrueSkill convention.
const BETA: f64 = 25.0 / 6.0;

/// Minimum sigma floor to prevent sigma from collapsing to zero.
const KAPPA: f64 = 0.0001;

/// Default mean skill for a new player.
pub const DEFAULT_MU: f64 = 25.0;

/// Default uncertainty for a new player (mu / 3).
pub const DEFAULT_SIGMA: f64 = 25.0 / 3.0; // 8.333...

/// An OpenSkill Bayesian rating with mean skill estimate and uncertainty.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct Rating {
    /// Mean skill estimate.
    pub mu: f64,
    /// Uncertainty (standard deviation of the skill belief).
    pub sigma: f64,
}

impl Rating {
    /// Create a new rating with the given mu and sigma.
    pub fn new(mu: f64, sigma: f64) -> Self {
        Self { mu, sigma }
    }

    /// Conservative skill estimate: mu - 2*sigma.
    ///
    /// This is the lower bound of a ~95% confidence interval for the
    /// player's true skill. It penalizes uncertainty, meaning players
    /// with few observations are ranked lower than confidently-good players.
    pub fn conservative_score(&self) -> f64 {
        self.mu - 2.0 * self.sigma
    }
}

impl Default for Rating {
    fn default() -> Self {
        Self {
            mu: DEFAULT_MU,
            sigma: DEFAULT_SIGMA,
        }
    }
}

/// Standard normal probability density function.
fn normal_pdf(x: f64) -> f64 {
    (-0.5 * x * x).exp() / (2.0 * PI).sqrt()
}

/// Standard normal cumulative distribution function.
///
/// Uses an approximation based on the complementary error function.
/// Accurate to about 1.5e-7 relative error.
fn normal_cdf(x: f64) -> f64 {
    0.5 * erfc(-x * FRAC_1_SQRT_2)
}

/// Complementary error function approximation.
///
/// Uses the rational approximation from Abramowitz and Stegun (1964),
/// formula 7.1.26, which provides accuracy to about 1.5e-7.
fn erfc(x: f64) -> f64 {
    // For negative x, use erfc(-x) = 2 - erfc(x)
    if x < 0.0 {
        return 2.0 - erfc(-x);
    }

    let t = 1.0 / (1.0 + 0.3275911 * x);
    let poly = t
        * (0.254829592
            + t * (-0.284496736 + t * (1.421413741 + t * (-1.453152027 + t * 1.061405429))));

    poly * (-x * x).exp()
}

/// Perform a pairwise rating update after a comparison where the winner
/// demonstrated higher quality than the loser.
///
/// Returns the updated (winner_rating, loser_rating).
///
/// Per CP-015 section 8: follows the Thurstone-Mosteller model. The update
/// magnitude depends on the surprise of the outcome. If the winner was already
/// rated much higher than the loser, the update is small. If the loser was
/// rated higher (an upset), the update is large.
pub fn pairwise_update(winner: &Rating, loser: &Rating) -> (Rating, Rating) {
    let sigma_w_sq = winner.sigma * winner.sigma;
    let sigma_l_sq = loser.sigma * loser.sigma;

    // c combines performance variance with rating uncertainties
    let c = (2.0 * BETA * BETA + sigma_w_sq + sigma_l_sq).sqrt();

    // t is the normalized skill difference
    let t = (winner.mu - loser.mu) / c;

    // Truncated Gaussian update functions
    let cdf_t = normal_cdf(t);

    // Guard against division by zero when cdf_t is extremely small.
    // This happens when the winner is rated far below the loser.
    if cdf_t < 1e-15 {
        // The outcome is so surprising that we apply maximum update.
        // Fall back to a large but bounded update.
        let v = 10.0; // Capped v value
        let w = v * (v + t.abs());

        let new_winner = Rating::new(
            winner.mu + (sigma_w_sq / c) * v,
            winner.sigma * (1.0 - (sigma_w_sq / (c * c)) * w).max(KAPPA).sqrt(),
        );
        let new_loser = Rating::new(
            loser.mu - (sigma_l_sq / c) * v,
            loser.sigma * (1.0 - (sigma_l_sq / (c * c)) * w).max(KAPPA).sqrt(),
        );
        return (new_winner, new_loser);
    }

    let v = normal_pdf(t) / cdf_t;
    let w = v * (v + t);

    // Winner update: mu increases, sigma decreases
    let new_winner_mu = winner.mu + (sigma_w_sq / c) * v;
    let new_winner_sigma = winner.sigma * (1.0 - (sigma_w_sq / (c * c)) * w).max(KAPPA).sqrt();

    // Loser update: mu decreases, sigma decreases
    let new_loser_mu = loser.mu - (sigma_l_sq / c) * v;
    let new_loser_sigma = loser.sigma * (1.0 - (sigma_l_sq / (c * c)) * w).max(KAPPA).sqrt();

    (
        Rating::new(new_winner_mu, new_winner_sigma),
        Rating::new(new_loser_mu, new_loser_sigma),
    )
}

#[cfg(test)]
mod tests {
    use super::*;

    const EPSILON: f64 = 1e-6;

    #[test]
    fn test_default_rating() {
        let r = Rating::default();
        assert!((r.mu - 25.0).abs() < EPSILON);
        assert!((r.sigma - 8.333333333333334).abs() < EPSILON);
    }

    #[test]
    fn test_conservative_score_default() {
        let r = Rating::default();
        // mu - 2*sigma = 25.0 - 2*8.333 = 8.333
        let score = r.conservative_score();
        assert!((score - (25.0 - 2.0 * DEFAULT_SIGMA)).abs() < EPSILON);
        assert!(score > 8.0 && score < 9.0);
    }

    #[test]
    fn test_conservative_score_high_certainty() {
        let r = Rating::new(30.0, 1.0);
        // mu - 2*sigma = 30 - 2 = 28
        assert!((r.conservative_score() - 28.0).abs() < EPSILON);
    }

    #[test]
    fn test_conservative_score_high_uncertainty() {
        let r = Rating::new(30.0, 10.0);
        // mu - 2*sigma = 30 - 20 = 10
        assert!((r.conservative_score() - 10.0).abs() < EPSILON);
    }

    #[test]
    fn test_normal_pdf_at_zero() {
        // pdf(0) = 1/sqrt(2*pi) ≈ 0.3989
        let val = normal_pdf(0.0);
        assert!((val - 0.3989422804014327).abs() < 1e-10);
    }

    #[test]
    fn test_normal_pdf_symmetry() {
        assert!((normal_pdf(1.0) - normal_pdf(-1.0)).abs() < 1e-10);
        assert!((normal_pdf(2.5) - normal_pdf(-2.5)).abs() < 1e-10);
    }

    #[test]
    fn test_normal_cdf_at_zero() {
        // cdf(0) = 0.5
        assert!((normal_cdf(0.0) - 0.5).abs() < 1e-6);
    }

    #[test]
    fn test_normal_cdf_at_large_positive() {
        // cdf(5) ≈ 1.0
        assert!((normal_cdf(5.0) - 1.0).abs() < 1e-5);
    }

    #[test]
    fn test_normal_cdf_at_large_negative() {
        // cdf(-5) ≈ 0.0
        assert!(normal_cdf(-5.0) < 1e-5);
    }

    #[test]
    fn test_normal_cdf_known_values() {
        // cdf(1) ≈ 0.8413
        assert!((normal_cdf(1.0) - 0.8413).abs() < 1e-3);
        // cdf(-1) ≈ 0.1587
        assert!((normal_cdf(-1.0) - 0.1587).abs() < 1e-3);
        // cdf(2) ≈ 0.9772
        assert!((normal_cdf(2.0) - 0.9772).abs() < 1e-3);
    }

    #[test]
    fn test_pairwise_equal_ratings() {
        let a = Rating::default();
        let b = Rating::default();

        let (winner, loser) = pairwise_update(&a, &b);

        // Winner should gain skill, loser should lose skill
        assert!(winner.mu > a.mu);
        assert!(loser.mu < b.mu);

        // Both should have reduced uncertainty
        assert!(winner.sigma < a.sigma);
        assert!(loser.sigma < b.sigma);

        // Updates should be symmetric for equal starting ratings
        let gain = winner.mu - a.mu;
        let loss = b.mu - loser.mu;
        assert!((gain - loss).abs() < 1e-10);
    }

    #[test]
    fn test_pairwise_expected_outcome() {
        // When the higher-rated player wins, the update should be small
        let strong = Rating::new(30.0, 5.0);
        let weak = Rating::new(20.0, 5.0);

        let (new_strong, new_weak) = pairwise_update(&strong, &weak);

        // Strong player still wins, weak still loses
        assert!(new_strong.mu > strong.mu);
        assert!(new_weak.mu < weak.mu);

        // But the magnitude should be small because this was expected
        let gain = new_strong.mu - strong.mu;
        assert!(gain < 2.0, "Expected small gain for expected outcome, got {}", gain);
    }

    #[test]
    fn test_pairwise_upset() {
        // When the lower-rated player wins, the update should be large
        let strong = Rating::new(30.0, 5.0);
        let weak = Rating::new(20.0, 5.0);

        // Weak player wins (upset)
        let (new_weak, _new_strong) = pairwise_update(&weak, &strong);

        // The weak player gains more than in the expected case
        let gain = new_weak.mu - weak.mu;
        assert!(gain > 1.0, "Expected larger gain for upset, got {}", gain);
    }

    #[test]
    fn test_pairwise_sigma_never_negative() {
        // Even after many updates, sigma should remain positive
        let mut a = Rating::default();
        let mut b = Rating::default();

        for _ in 0..100 {
            let (new_a, new_b) = pairwise_update(&a, &b);
            a = new_a;
            b = new_b;
        }

        assert!(a.sigma > 0.0);
        assert!(b.sigma > 0.0);
    }

    #[test]
    fn test_pairwise_sigma_decreases() {
        let a = Rating::default();
        let b = Rating::default();

        let (winner, loser) = pairwise_update(&a, &b);

        // Sigma should decrease for both players after an observation
        assert!(winner.sigma < a.sigma);
        assert!(loser.sigma < b.sigma);
    }

    #[test]
    fn test_convergence_consistent_winner() {
        // A player that always wins should converge to a high rating
        let mut winner = Rating::default();
        let mut loser = Rating::default();

        for _ in 0..50 {
            let (new_w, new_l) = pairwise_update(&winner, &loser);
            winner = new_w;
            loser = new_l;
        }

        // Winner should be well above the starting mu
        assert!(winner.mu > 35.0, "Winner mu should be high, got {}", winner.mu);
        // Loser should be well below
        assert!(loser.mu < 15.0, "Loser mu should be low, got {}", loser.mu);

        // Both should have reduced uncertainty after 50 rounds
        // (sigma converges slowly in the Thurstone-Mosteller model due to KAPPA floor)
        assert!(winner.sigma < 4.0, "Winner sigma should be low, got {}", winner.sigma);
        assert!(loser.sigma < 4.0, "Loser sigma should be low, got {}", loser.sigma);

        // Conservative scores should reflect the separation
        assert!(winner.conservative_score() > loser.conservative_score());
    }

    #[test]
    fn test_transitivity() {
        // If A beats B and B beats C, A's rating should be above C's
        let mut a = Rating::default();
        let mut b = Rating::default();
        let mut c = Rating::default();

        // A beats B five times
        for _ in 0..5 {
            let (new_a, new_b) = pairwise_update(&a, &b);
            a = new_a;
            b = new_b;
        }

        // B beats C five times
        for _ in 0..5 {
            let (new_b, new_c) = pairwise_update(&b, &c);
            b = new_b;
            c = new_c;
        }

        // A > B > C in conservative score
        assert!(a.conservative_score() > b.conservative_score());
        assert!(b.conservative_score() > c.conservative_score());
        assert!(a.conservative_score() > c.conservative_score());
    }

    #[test]
    fn test_rating_serialization() {
        let r = Rating::new(28.5, 6.1);
        let json = serde_json::to_string(&r).unwrap();
        let deserialized: Rating = serde_json::from_str(&json).unwrap();
        assert!((deserialized.mu - r.mu).abs() < EPSILON);
        assert!((deserialized.sigma - r.sigma).abs() < EPSILON);
    }

    #[test]
    fn test_erfc_basic_values() {
        // erfc(0) = 1.0
        assert!((erfc(0.0) - 1.0).abs() < 1e-6);
        // erfc(large) ≈ 0
        assert!(erfc(5.0) < 1e-5);
        // erfc(-large) ≈ 2
        assert!((erfc(-5.0) - 2.0).abs() < 1e-5);
    }

    #[test]
    fn test_pairwise_with_different_sigmas() {
        // A certain player vs an uncertain player
        let certain = Rating::new(25.0, 2.0);
        let uncertain = Rating::new(25.0, 8.0);

        let (new_certain, new_uncertain) = pairwise_update(&certain, &uncertain);

        // Both gain/lose, but the uncertain player's sigma should shrink more
        assert!(new_certain.mu > certain.mu);
        assert!(new_uncertain.mu < uncertain.mu);

        // The uncertain player's rating should change more
        let certain_change = (new_certain.mu - certain.mu).abs();
        let uncertain_change = (new_uncertain.mu - uncertain.mu).abs();
        assert!(
            uncertain_change > certain_change,
            "Uncertain player should change more: {} vs {}",
            uncertain_change,
            certain_change
        );
    }

    #[test]
    fn test_conservative_score_ordering() {
        // A player with high mu but high sigma should rank lower than
        // a player with moderate mu but low sigma
        let uncertain_good = Rating::new(35.0, 10.0);
        let certain_moderate = Rating::new(28.0, 2.0);

        // 35 - 20 = 15 vs 28 - 4 = 24
        assert!(
            certain_moderate.conservative_score() > uncertain_good.conservative_score(),
            "Certain moderate ({}) should outrank uncertain good ({})",
            certain_moderate.conservative_score(),
            uncertain_good.conservative_score()
        );
    }
}