trueskill-tt/tests/variance_reduction.rs

//! `expected_variance_reduction`: which matchup best sharpens a given question.

use smallvec::smallvec;
use trueskill_tt::{
    ConstantDrift, ConvergenceOptions, Event, History, InferenceError, Member, Outcome, Team,
    UnknownKeys,
};

type H = History;

fn round(a: &'static str, b: &'static str, sa: f64, sb: f64) -> Event<i64, &'static str> {
    Event {
        time: 1,
        teams: smallvec![
            Team::with_members([Member::new(a)]),
            Team::with_members([Member::new(b)]),
        ],
        outcome: Outcome::scores([sa, sb]),
    }
}

fn base() -> Vec<Event<i64, &'static str>> {
    vec![
        round("a", "b", 5.0, 2.0),
        round("a", "c", 6.0, 1.0),
        round("b", "c", 4.0, 3.0),
        round("c", "d", 2.0, 1.0),
        round("a", "d", 7.0, 2.0),
    ]
}

fn fit(extra: Option<Event<i64, &'static str>>, policy: UnknownKeys) -> H {
    let mut h: History = History::builder()
        .mu(0.0)
        .sigma(6.0)
        .beta(1.0)
        .score_sigma(2.0)
        .drift(ConstantDrift::new(0.0))
        .unknown_keys(policy)
        .convergence(ConvergenceOptions {
            max_iter: 20_000,
            epsilon: 1e-13,
            alpha: 1.0,
        })
        .build();
    let mut ev = base();
    if let Some(e) = extra {
        ev.push(e);
    }
    h.add_events(ev).unwrap();
    let _ = h.converge().unwrap();
    h
}

/// The closed form must equal what actually happens if the matchup is played.
/// This is the assertion that makes the whole call trustworthy: a wrong
/// acquisition function returns plausible numbers and quietly picks worse
/// matchups forever.
#[test]
fn the_closed_form_matches_an_actual_refit() {
    let h = fit(None, UnknownKeys::Reject);
    let target: Vec<(&&str, f64)> = vec![(&"a", 1.0), (&"b", -1.0)];
    let before = h
        .joint()
        .unwrap()
        .posterior_of(&target)
        .unwrap()
        .sigma()
        .powi(2);

    for (x, y) in [("a", "b"), ("c", "d"), ("a", "c"), ("b", "d")] {
        let predicted = h
            .joint()
            .unwrap()
            .expected_variance_reduction(&[&[&x], &[&y]], &target)
            .unwrap();

        let after = fit(Some(round(x, y, 3.0, 1.0)), UnknownKeys::Reject);
        let actual = before
            - after
                .joint()
                .unwrap()
                .posterior_of(&target)
                .unwrap()
                .sigma()
                .powi(2);

        assert!(
            (predicted - actual).abs() / actual.abs() < 1e-9,
            "{x} vs {y}: predicted {predicted}, actual {actual}"
        );
    }
}

/// The reduction cannot depend on the score, because for a Gaussian likelihood
/// the posterior variance update is data-independent. This is why the call
/// needs no expectation despite its name.
#[test]
fn the_outcome_does_not_change_the_reduction() {
    let target: Vec<(&&str, f64)> = vec![(&"a", 1.0), (&"b", -1.0)];
    let h = fit(None, UnknownKeys::Reject);
    let before = h
        .joint()
        .unwrap()
        .posterior_of(&target)
        .unwrap()
        .sigma()
        .powi(2);

    let mut seen = Vec::new();
    for (sa, sb) in [(3.0, 1.0), (100.0, -50.0), (0.0, 0.0)] {
        let after = fit(Some(round("c", "d", sa, sb)), UnknownKeys::Reject);
        seen.push(
            before
                - after
                    .joint()
                    .unwrap()
                    .posterior_of(&target)
                    .unwrap()
                    .sigma()
                    .powi(2),
        );
    }
    for w in seen.windows(2) {
        assert!(
            (w[0] - w[1]).abs() < 1e-12,
            "variance reduction moved with the observed score: {seen:?}"
        );
    }
}

/// The point of the call: it must rank candidate matchups usefully. Playing the
/// pair you are trying to separate helps most; an unrelated pair helps least.
#[test]
fn it_ranks_candidates_by_how_much_they_answer_the_question() {
    let h = fit(None, UnknownKeys::Reject);
    let target: Vec<(&&str, f64)> = vec![(&"a", 1.0), (&"b", -1.0)];

    let direct = h
        .joint()
        .unwrap()
        .expected_variance_reduction(&[&[&"a"], &[&"b"]], &target)
        .unwrap();
    let unrelated = h
        .joint()
        .unwrap()
        .expected_variance_reduction(&[&[&"c"], &[&"d"]], &target)
        .unwrap();

    assert!(direct > 0.0 && unrelated > 0.0);
    assert!(
        direct > 5.0 * unrelated,
        "playing the target pair should dominate: {direct} vs {unrelated}"
    );
}

/// A matchup between two competitors nobody has seen still teaches something
/// about them, but nothing about a target that does not involve them.
#[test]
fn an_unrelated_unseen_matchup_teaches_nothing_about_the_target() {
    let h = fit(None, UnknownKeys::Prior);
    let target: Vec<(&&str, f64)> = vec![(&"a", 1.0), (&"b", -1.0)];

    let reduction = h
        .joint()
        .unwrap()
        .expected_variance_reduction(&[&[&"stranger"], &[&"nobody"]], &target)
        .unwrap();
    assert!(
        reduction.abs() < 1e-12,
        "an unseen pair shares nothing with the target: {reduction}"
    );
}

#[test]
fn shape_errors_are_reported() {
    let h = fit(None, UnknownKeys::Reject);
    let target: Vec<(&&str, f64)> = vec![(&"a", 1.0), (&"b", -1.0)];

    assert!(matches!(
        h.joint()
            .unwrap()
            .expected_variance_reduction(&[&[&"a"]], &target),
        Err(InferenceError::MismatchedShape {
            expected: 2,
            got: 1,
            ..
        })
    ));
    assert!(matches!(
        h.joint()
            .unwrap()
            .expected_variance_reduction(&[&[&"a"], &[&"ghost"]], &target),
        Err(InferenceError::UnknownKey { .. })
    ));
}