use std::collections::HashMap;
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};
use crate::BootstrapMethod;
use crate::error::VeridictError;
use crate::stats::bootstrap::{
bca_adjusted_percentiles, bias_correction_z0, hi_index, lo_index, resample_edge_multinomial,
weighted_acceleration,
};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PairRecord {
pub a: usize,
pub b: usize,
pub a_wins: u64,
pub b_wins: u64,
pub draws: u64,
}
#[derive(Debug, Clone)]
pub struct Connectivity {
pub component_of: Vec<usize>,
pub num_components: usize,
}
pub fn strongly_connected_components(n_competitors: usize, pairs: &[PairRecord]) -> Connectivity {
let mut adj = vec![Vec::new(); n_competitors];
let mut radj = vec![Vec::new(); n_competitors];
for p in pairs {
if p.a_wins > 0 {
adj[p.a].push(p.b);
radj[p.b].push(p.a);
}
if p.b_wins > 0 {
adj[p.b].push(p.a);
radj[p.a].push(p.b);
}
if p.draws > 0 {
adj[p.a].push(p.b);
radj[p.b].push(p.a);
adj[p.b].push(p.a);
radj[p.a].push(p.b);
}
}
let mut visited = vec![false; n_competitors];
let mut finish_order = Vec::with_capacity(n_competitors);
for start in 0..n_competitors {
if visited[start] {
continue;
}
visited[start] = true;
let mut stack = vec![(start, 0usize)];
while let Some(&mut (node, ref mut next_idx)) = stack.last_mut() {
if *next_idx < adj[node].len() {
let neighbor = adj[node][*next_idx];
*next_idx += 1;
if !visited[neighbor] {
visited[neighbor] = true;
stack.push((neighbor, 0));
}
} else {
finish_order.push(node);
stack.pop();
}
}
}
let mut component_of = vec![usize::MAX; n_competitors];
let mut num_components = 0;
for &start in finish_order.iter().rev() {
if component_of[start] != usize::MAX {
continue;
}
let comp = num_components;
num_components += 1;
component_of[start] = comp;
let mut stack = vec![start];
while let Some(node) = stack.pop() {
for &neighbor in &radj[node] {
if component_of[neighbor] == usize::MAX {
component_of[neighbor] = comp;
stack.push(neighbor);
}
}
}
}
Connectivity {
component_of,
num_components,
}
}
#[derive(Debug, Clone, Copy)]
pub struct CompetitorFit {
pub component: usize,
pub elo: f64,
}
pub const MAX_ITERATIONS: usize = 10_000;
pub const CONVERGENCE_THRESHOLD: f64 = 1e-9;
pub fn fit_graph(
n_competitors: usize,
pairs: &[PairRecord],
) -> Result<Vec<CompetitorFit>, VeridictError> {
if n_competitors == 0 {
return Err(VeridictError::InvalidThreshold(
"Bradley-Terry graph requires at least one competitor".to_string(),
));
}
for (index, p) in pairs.iter().enumerate() {
if p.a == p.b {
return Err(VeridictError::InvalidThreshold(format!(
"Bradley-Terry pair {index} is a self-pair at competitor {}",
p.a
)));
}
if p.a >= n_competitors || p.b >= n_competitors {
return Err(VeridictError::InvalidThreshold(format!(
"Bradley-Terry pair {index} refers to competitor indices ({}, {}) outside \
0..{n_competitors}",
p.a, p.b
)));
}
if p.a_wins
.checked_add(p.b_wins)
.and_then(|n| n.checked_add(p.draws))
.is_none_or(|n| n == 0)
{
return Err(VeridictError::InvalidThreshold(format!(
"Bradley-Terry pair {index} must contain at least one game and counts must not overflow"
)));
}
}
let connectivity = strongly_connected_components(n_competitors, pairs);
let mut members: Vec<Vec<usize>> = vec![Vec::new(); connectivity.num_components];
for (global_idx, &comp) in connectivity.component_of.iter().enumerate() {
members[comp].push(global_idx);
}
let mut local_index = vec![0usize; n_competitors];
for member_list in &members {
for (local_idx, &global_idx) in member_list.iter().enumerate() {
local_index[global_idx] = local_idx;
}
}
let mut component_pairs: Vec<Vec<PairRecord>> = vec![Vec::new(); connectivity.num_components];
for p in pairs {
let comp = connectivity.component_of[p.a];
if comp == connectivity.component_of[p.b] {
component_pairs[comp].push(PairRecord {
a: local_index[p.a],
b: local_index[p.b],
a_wins: p.a_wins,
b_wins: p.b_wins,
draws: p.draws,
});
}
}
let mut elo = vec![0.0; n_competitors];
for comp in 0..connectivity.num_components {
let n_local = members[comp].len();
if n_local <= 1 {
continue; }
let local_elo = fit_component(n_local, &component_pairs[comp], &members[comp])?;
for (local_idx, &global_idx) in members[comp].iter().enumerate() {
elo[global_idx] = local_elo[local_idx];
}
}
Ok((0..n_competitors)
.map(|i| CompetitorFit {
component: connectivity.component_of[i],
elo: elo[i],
})
.collect())
}
fn fit_component(
n_local: usize,
pairs: &[PairRecord],
members: &[usize],
) -> Result<Vec<f64>, VeridictError> {
let mut pi = vec![1.0; n_local];
let mut last_relative_change = f64::INFINITY;
let mut worst_local = 0usize;
for _ in 0..MAX_ITERATIONS {
let mut wins = vec![0.0; n_local];
let mut denom = vec![0.0; n_local];
for p in pairs {
let n = (p.a_wins + p.b_wins + p.draws) as f64;
wins[p.a] += p.a_wins as f64 + 0.5 * p.draws as f64;
wins[p.b] += p.b_wins as f64 + 0.5 * p.draws as f64;
let shared = n / (pi[p.a] + pi[p.b]);
denom[p.a] += shared;
denom[p.b] += shared;
}
let mut new_pi: Vec<f64> = (0..n_local)
.map(|i| {
if denom[i] > 0.0 {
wins[i] / denom[i]
} else {
pi[i]
}
})
.collect();
let scale = new_pi[0];
for v in &mut new_pi {
*v /= scale;
}
let mut max_relative_change = 0.0_f64;
for i in 0..n_local {
let rel = (new_pi[i] - pi[i]).abs() / pi[i];
if rel > max_relative_change {
max_relative_change = rel;
worst_local = i;
}
}
last_relative_change = max_relative_change;
pi = new_pi;
if max_relative_change < CONVERGENCE_THRESHOLD {
return Ok(pi.iter().map(|&p| 400.0 * p.log10()).collect());
}
}
Err(VeridictError::BradleyTerryDidNotConverge {
iterations: MAX_ITERATIONS,
last_relative_change,
threshold: CONVERGENCE_THRESHOLD,
worst_competitor: members[worst_local],
})
}
pub const CONNECTED_FRACTION_THRESHOLD: f64 = 0.9;
pub fn bootstrap_pairwise_elo_diff_cis(
n_competitors: usize,
pairs: &[PairRecord],
fits: &[CompetitorFit],
resamples: usize,
seed: u64,
confidence: f64,
bootstrap_method: BootstrapMethod,
) -> HashMap<(usize, usize), (f64, f64)> {
let num_workers = std::thread::available_parallelism()
.map(std::num::NonZeroUsize::get)
.unwrap_or(1);
bootstrap_pairwise_elo_diff_cis_with_workers(
n_competitors,
pairs,
fits,
resamples,
seed,
confidence,
bootstrap_method,
num_workers,
)
}
#[allow(clippy::too_many_arguments)]
fn bootstrap_pairwise_elo_diff_cis_with_workers(
n_competitors: usize,
pairs: &[PairRecord],
fits: &[CompetitorFit],
resamples: usize,
seed: u64,
confidence: f64,
bootstrap_method: BootstrapMethod,
num_workers: usize,
) -> HashMap<(usize, usize), (f64, f64)> {
debug_assert!(
resamples > 0,
"bootstrap_pairwise_elo_diff_cis called with zero resamples"
);
let component_of: Vec<usize> = fits.iter().map(|f| f.component).collect();
let mut master_rng = StdRng::seed_from_u64(seed);
let sub_seeds: Vec<u64> = (0..resamples).map(|_| master_rng.random()).collect();
let empty_template = init_draws_map(n_competitors, &component_of);
let num_workers = num_workers.min(resamples).max(1);
let chunk_size = resamples.div_ceil(num_workers).max(1);
let local_maps: Vec<HashMap<(usize, usize), Vec<f64>>> = std::thread::scope(|scope| {
sub_seeds
.chunks(chunk_size)
.map(|chunk| {
let template = &empty_template;
scope.spawn(move || {
let mut local = template.clone();
for &sub_seed in chunk {
let mut rng = StdRng::seed_from_u64(sub_seed);
let resampled = resample_one(pairs, &mut rng);
if let Ok(resampled_fits) = fit_graph(n_competitors, &resampled) {
harvest(&resampled_fits, &mut local);
}
}
local
})
})
.collect::<Vec<_>>()
.into_iter()
.map(|h| h.join().expect("bootstrap worker thread panicked"))
.collect()
});
let mut draws = empty_template;
for local in local_maps {
for (key, mut vals) in local {
draws.entry(key).or_default().append(&mut vals);
}
}
let jackknife = matches!(bootstrap_method, BootstrapMethod::Bca)
.then(|| jackknife_replicates(n_competitors, pairs, &component_of));
finalize_cis(
draws,
resamples,
confidence,
fits,
bootstrap_method,
jackknife.as_ref(),
)
}
#[cfg(test)]
fn bootstrap_pairwise_elo_diff_cis_serial(
n_competitors: usize,
pairs: &[PairRecord],
fits: &[CompetitorFit],
resamples: usize,
seed: u64,
confidence: f64,
) -> HashMap<(usize, usize), (f64, f64)> {
debug_assert!(
resamples > 0,
"bootstrap_pairwise_elo_diff_cis_serial called with zero resamples"
);
let component_of: Vec<usize> = fits.iter().map(|f| f.component).collect();
let mut draws = init_draws_map(n_competitors, &component_of);
let mut rng = StdRng::seed_from_u64(seed);
for _ in 0..resamples {
let resampled = resample_one(pairs, &mut rng);
if let Ok(resampled_fits) = fit_graph(n_competitors, &resampled) {
harvest(&resampled_fits, &mut draws);
}
}
finalize_cis(
draws,
resamples,
confidence,
fits,
BootstrapMethod::Percentile,
None,
)
}
fn init_draws_map(
n_competitors: usize,
original_component_of: &[usize],
) -> HashMap<(usize, usize), Vec<f64>> {
let mut draws = HashMap::new();
for i in 0..n_competitors {
for j in (i + 1)..n_competitors {
if original_component_of[i] == original_component_of[j] {
draws.insert((i, j), Vec::new());
}
}
}
draws
}
fn resample_one(pairs: &[PairRecord], rng: &mut StdRng) -> Vec<PairRecord> {
pairs
.iter()
.map(|p| {
let (a_wins, b_wins, draw_count) =
resample_edge_multinomial(p.a_wins, p.b_wins, p.draws, rng);
PairRecord {
a: p.a,
b: p.b,
a_wins,
b_wins,
draws: draw_count,
}
})
.collect()
}
fn harvest(fits: &[CompetitorFit], draws: &mut HashMap<(usize, usize), Vec<f64>>) {
for (&(i, j), pair_draws) in draws.iter_mut() {
if fits[i].component == fits[j].component {
pair_draws.push(fits[i].elo - fits[j].elo);
}
}
}
type JackknifeReplicates = HashMap<(usize, usize), Vec<(f64, f64)>>;
fn jackknife_replicates(
n_competitors: usize,
pairs: &[PairRecord],
original_component_of: &[usize],
) -> JackknifeReplicates {
let mut replicates: JackknifeReplicates = HashMap::new();
for i in 0..n_competitors {
for j in (i + 1)..n_competitors {
if original_component_of[i] == original_component_of[j] {
replicates.insert((i, j), Vec::new());
}
}
}
for edge_idx in 0..pairs.len() {
let edge = pairs[edge_idx];
for (count, apply_decrement) in [
(
edge.a_wins,
(|e: &mut PairRecord| e.a_wins -= 1) as fn(&mut PairRecord),
),
(
edge.b_wins,
(|e: &mut PairRecord| e.b_wins -= 1) as fn(&mut PairRecord),
),
(
edge.draws,
(|e: &mut PairRecord| e.draws -= 1) as fn(&mut PairRecord),
),
] {
if count == 0 {
continue;
}
let mut perturbed_edge = edge;
apply_decrement(&mut perturbed_edge);
let mut perturbed: Vec<PairRecord> = pairs.to_vec();
if perturbed_edge.a_wins + perturbed_edge.b_wins + perturbed_edge.draws == 0 {
perturbed.remove(edge_idx);
} else {
perturbed[edge_idx] = perturbed_edge;
}
let weight = count as f64;
if let Ok(fits) = fit_graph(n_competitors, &perturbed) {
for (&(i, j), reps) in replicates.iter_mut() {
if fits[i].component == fits[j].component {
reps.push((fits[i].elo - fits[j].elo, weight));
}
}
}
}
}
replicates
}
fn finalize_cis(
draws: HashMap<(usize, usize), Vec<f64>>,
resamples: usize,
confidence: f64,
fits: &[CompetitorFit],
bootstrap_method: BootstrapMethod,
jackknife: Option<&JackknifeReplicates>,
) -> HashMap<(usize, usize), (f64, f64)> {
let alpha = 1.0 - confidence;
let mut result = HashMap::new();
for ((i, j), mut pair_draws) in draws {
let fraction = pair_draws.len() as f64 / resamples as f64;
if fraction < CONNECTED_FRACTION_THRESHOLD {
continue;
}
pair_draws.sort_by(f64::total_cmp);
let n = pair_draws.len();
let original = fits[i].elo - fits[j].elo;
let (p_lo, p_hi) = match bootstrap_method {
BootstrapMethod::Percentile | BootstrapMethod::Basic => {
(alpha / 2.0, 1.0 - alpha / 2.0)
}
BootstrapMethod::Bca => {
let below = pair_draws.iter().filter(|&&v| v < original).count() as f64;
let z0 = bias_correction_z0(below, n);
let empty = Vec::new();
let pair_replicates = jackknife
.and_then(|reps| reps.get(&(i, j)))
.unwrap_or(&empty);
let a = weighted_acceleration(pair_replicates);
bca_adjusted_percentiles(z0, a, confidence)
}
};
let lo_idx = lo_index(p_lo, n);
let hi_idx = hi_index(p_hi, n).max(lo_idx);
let (lo, hi) = (pair_draws[lo_idx], pair_draws[hi_idx]);
let bounds = match bootstrap_method {
BootstrapMethod::Basic => (2.0 * original - hi, 2.0 * original - lo),
BootstrapMethod::Percentile | BootstrapMethod::Bca => (lo, hi),
};
result.insert((i, j), bounds);
}
result
}
#[cfg(test)]
mod tests {
use super::*;
fn assert_close(actual: f64, expected: f64, tol: f64) {
assert!(
(actual - expected).abs() < tol,
"expected {expected}, got {actual}"
);
}
#[test]
fn multi_node_cycle_converges_to_expected_ratings() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 4,
b_wins: 1,
draws: 0,
},
PairRecord {
a: 1,
b: 2,
a_wins: 3,
b_wins: 2,
draws: 0,
},
PairRecord {
a: 2,
b: 0,
a_wins: 1,
b_wins: 4,
draws: 0,
},
];
let fits = fit_graph(3, &pairs).unwrap();
assert_eq!(fits[0].component, fits[1].component);
assert_eq!(fits[1].component, fits[2].component);
assert_close(fits[0].elo, 0.0, 1e-9);
assert_close(fits[1].elo - fits[0].elo, -215.5356238480202, 1e-6);
assert_close(fits[2].elo - fits[0].elo, -268.53764941971946, 1e-6);
}
#[test]
fn fit_graph_rejects_invalid_public_inputs_without_panicking() {
assert!(fit_graph(0, &[]).is_err());
for pair in [
PairRecord {
a: 0,
b: 0,
a_wins: 1,
b_wins: 0,
draws: 0,
},
PairRecord {
a: 0,
b: 2,
a_wins: 1,
b_wins: 0,
draws: 0,
},
PairRecord {
a: 0,
b: 1,
a_wins: 0,
b_wins: 0,
draws: 0,
},
PairRecord {
a: 0,
b: 1,
a_wins: u64::MAX,
b_wins: 1,
draws: 0,
},
] {
assert!(fit_graph(2, &[pair]).is_err());
}
}
#[test]
fn undirected_connected_but_not_strongly_connected_is_detected() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 1,
b_wins: 1,
draws: 0,
}, PairRecord {
a: 2,
b: 3,
a_wins: 1,
b_wins: 1,
draws: 0,
}, PairRecord {
a: 0,
b: 2,
a_wins: 1,
b_wins: 0,
draws: 0,
}, PairRecord {
a: 0,
b: 3,
a_wins: 1,
b_wins: 0,
draws: 0,
}, PairRecord {
a: 1,
b: 2,
a_wins: 1,
b_wins: 0,
draws: 0,
}, PairRecord {
a: 1,
b: 3,
a_wins: 1,
b_wins: 0,
draws: 0,
}, ];
let connectivity = strongly_connected_components(4, &pairs);
assert_eq!(connectivity.num_components, 2);
assert_eq!(connectivity.component_of[0], connectivity.component_of[1]);
assert_eq!(connectivity.component_of[2], connectivity.component_of[3]);
assert_ne!(connectivity.component_of[0], connectivity.component_of[2]);
}
#[test]
fn all_draws_is_not_flagged_disconnected() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 0,
b_wins: 0,
draws: 3,
},
PairRecord {
a: 1,
b: 2,
a_wins: 0,
b_wins: 0,
draws: 3,
},
];
let connectivity = strongly_connected_components(3, &pairs);
assert_eq!(connectivity.num_components, 1);
let fits = fit_graph(3, &pairs).unwrap();
for f in &fits {
assert_close(f.elo, 0.0, 1e-6);
}
}
#[test]
fn disconnected_input_does_not_iterate_to_a_wrong_answer() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 3,
b_wins: 1,
draws: 0,
},
PairRecord {
a: 2,
b: 3,
a_wins: 1,
b_wins: 3,
draws: 0,
},
];
let fits = fit_graph(4, &pairs).unwrap();
assert_eq!(fits[0].component, fits[1].component);
assert_eq!(fits[2].component, fits[3].component);
assert_ne!(fits[0].component, fits[2].component);
assert!(fits[1].elo < fits[0].elo);
assert!(fits[3].elo > fits[2].elo);
}
#[test]
fn singleton_competitor_with_no_games_gets_pinned_elo() {
let pairs = [PairRecord {
a: 0,
b: 1,
a_wins: 2,
b_wins: 2,
draws: 0,
}];
let fits = fit_graph(3, &pairs).unwrap();
assert_ne!(fits[2].component, fits[0].component);
assert_close(fits[2].elo, 0.0, 1e-9);
}
#[test]
fn extreme_lopsided_but_connected_graph_errors_instead_of_hanging() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 1_000_000,
b_wins: 1_000_000,
draws: 0,
},
PairRecord {
a: 2,
b: 3,
a_wins: 1_000_000,
b_wins: 1_000_000,
draws: 0,
},
PairRecord {
a: 0,
b: 2,
a_wins: 1_000_000_000_000_000,
b_wins: 1,
draws: 0,
},
];
match fit_graph(4, &pairs) {
Err(VeridictError::BradleyTerryDidNotConverge { iterations, .. }) => {
assert_eq!(iterations, MAX_ITERATIONS);
}
other => panic!("expected BradleyTerryDidNotConverge, got {other:?}"),
}
}
#[test]
fn two_node_shutout_is_two_singleton_components() {
let pairs = [PairRecord {
a: 0,
b: 1,
a_wins: 5,
b_wins: 0,
draws: 0,
}];
let connectivity = strongly_connected_components(2, &pairs);
assert_eq!(connectivity.num_components, 2);
}
fn fragile_bridge_pairs() -> [PairRecord; 3] {
[
PairRecord {
a: 0,
b: 1,
a_wins: 20,
b_wins: 20,
draws: 0,
},
PairRecord {
a: 2,
b: 3,
a_wins: 20,
b_wins: 20,
draws: 0,
},
PairRecord {
a: 1,
b: 2,
a_wins: 1,
b_wins: 1,
draws: 0,
},
]
}
#[test]
fn fragile_bridge_cross_pairs_degrade_to_no_ci_but_same_side_pairs_keep_one() {
let pairs = fragile_bridge_pairs();
let fits = fit_graph(4, &pairs).unwrap();
assert!(
fits.iter().all(|f| f.component == fits[0].component),
"the original (unresampled) graph must be a single component"
);
let cis = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
2000,
42,
0.95,
BootstrapMethod::Percentile,
);
for cross in [(0, 2), (0, 3), (1, 2), (1, 3)] {
assert!(
!cis.contains_key(&cross),
"{cross:?} should have no reliable CI (fragile bridge)"
);
}
for same_side in [(0, 1), (2, 3)] {
assert!(
cis.contains_key(&same_side),
"{same_side:?} should get a real CI (robust internal edge)"
);
let (lo, hi) = cis[&same_side];
assert!(lo.is_finite() && hi.is_finite() && lo <= hi);
}
}
#[test]
fn bootstrap_cis_are_deterministic_for_a_fixed_seed() {
let pairs = fragile_bridge_pairs();
let fits = fit_graph(4, &pairs).unwrap();
let cis_a = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
500,
7,
0.95,
BootstrapMethod::Percentile,
);
let cis_b = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
500,
7,
0.95,
BootstrapMethod::Percentile,
);
assert_eq!(cis_a, cis_b);
}
#[test]
fn output_is_identical_regardless_of_worker_count() {
let pairs = dense_pairs_for_test(6, 20);
let fits = fit_graph(6, &pairs).unwrap();
let mut results = [1usize, 2, 3, 7, 64].map(|num_workers| {
bootstrap_pairwise_elo_diff_cis_with_workers(
6,
&pairs,
&fits,
200,
42,
0.95,
BootstrapMethod::Percentile,
num_workers,
)
});
let first = results[0].clone();
for other in results.iter_mut().skip(1) {
assert_eq!(
&first, other,
"bootstrap output must be identical regardless of worker count"
);
}
}
#[test]
fn different_seeds_can_change_the_ci() {
let pairs = fragile_bridge_pairs();
let fits = fit_graph(4, &pairs).unwrap();
let cis_a = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
500,
1,
0.95,
BootstrapMethod::Percentile,
);
let cis_b = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
500,
2,
0.95,
BootstrapMethod::Percentile,
);
assert_ne!(cis_a, cis_b);
}
#[test]
fn disconnected_pairs_never_get_a_ci() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 5,
b_wins: 5,
draws: 0,
},
PairRecord {
a: 2,
b: 3,
a_wins: 5,
b_wins: 5,
draws: 0,
},
];
let fits = fit_graph(4, &pairs).unwrap();
let component_of: Vec<usize> = fits.iter().map(|f| f.component).collect();
assert_ne!(component_of[0], component_of[2]);
let cis = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
200,
42,
0.95,
BootstrapMethod::Percentile,
);
for cross in [(0, 2), (0, 3), (1, 2), (1, 3)] {
assert!(!cis.contains_key(&cross));
}
}
fn near_convergence_boundary_pairs() -> [PairRecord; 3] {
[
PairRecord {
a: 0,
b: 1,
a_wins: 100,
b_wins: 100,
draws: 0,
},
PairRecord {
a: 2,
b: 3,
a_wins: 100,
b_wins: 100,
draws: 0,
},
PairRecord {
a: 0,
b: 2,
a_wins: 10_000,
b_wins: 1,
draws: 0,
},
]
}
#[test]
fn resample_near_the_convergence_boundary_does_not_panic_or_propagate_an_error() {
let pairs = near_convergence_boundary_pairs();
let fits = fit_graph(4, &pairs).expect("the real, unresampled data converges");
let cis = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
50,
42,
0.95,
BootstrapMethod::Percentile,
);
for (_, (lo, hi)) in cis {
assert!(lo.is_finite() && hi.is_finite());
}
}
fn dense_pairs_for_test(n: usize, games_per_pair: u64) -> Vec<PairRecord> {
let a_wins = games_per_pair * 3 / 5;
let b_wins = games_per_pair - a_wins;
(0..n)
.flat_map(|i| ((i + 1)..n).map(move |j| (i, j)))
.map(|(a, b)| PairRecord {
a,
b,
a_wins,
b_wins,
draws: 0,
})
.collect()
}
#[test]
fn parallel_matches_serial_within_tolerance_at_high_resamples() {
const TOLERANCE_ELO: f64 = 25.0;
let pairs = dense_pairs_for_test(3, 100);
let fits = fit_graph(3, &pairs).unwrap();
let parallel = bootstrap_pairwise_elo_diff_cis(
3,
&pairs,
&fits,
8000,
11,
0.95,
BootstrapMethod::Percentile,
);
let serial = bootstrap_pairwise_elo_diff_cis_serial(3, &pairs, &fits, 8000, 13, 0.95);
assert_eq!(
parallel.len(),
serial.len(),
"both implementations should find the same pairs reliably connected \
on this well-conditioned graph"
);
for (key, (par_lo, par_hi)) in ¶llel {
let (ser_lo, ser_hi) = serial[key];
assert!(
(par_lo - ser_lo).abs() < TOLERANCE_ELO && (par_hi - ser_hi).abs() < TOLERANCE_ELO,
"pair {key:?}: parallel ({par_lo}, {par_hi}) vs serial ({ser_lo}, {ser_hi}) \
differ by more than {TOLERANCE_ELO} Elo - possible biased sub-seeding"
);
}
}
#[test]
fn per_resample_sub_seeds_are_unique() {
let mut rng = StdRng::seed_from_u64(0x5EED);
let sub_seeds: std::collections::HashSet<u64> = (0..10_000).map(|_| rng.random()).collect();
assert_eq!(sub_seeds.len(), 10_000, "expected 10,000 unique sub-seeds");
}
#[test]
fn resamples_smaller_than_available_parallelism_does_not_panic() {
let pairs = fragile_bridge_pairs();
let fits = fit_graph(4, &pairs).unwrap();
for resamples in [1usize, 10] {
let cis = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
resamples,
42,
0.95,
BootstrapMethod::Percentile,
);
for (_, (lo, hi)) in cis {
assert!(lo.is_finite() && hi.is_finite() && lo <= hi);
}
}
}
#[test]
fn basic_reflects_percentile_exactly() {
let pairs = dense_pairs_for_test(4, 40);
let fits = fit_graph(4, &pairs).unwrap();
let percentile = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
1000,
7,
0.95,
BootstrapMethod::Percentile,
);
let basic = bootstrap_pairwise_elo_diff_cis(
4,
&pairs,
&fits,
1000,
7,
0.95,
BootstrapMethod::Basic,
);
assert_eq!(percentile.len(), basic.len());
for (key, (perc_lo, perc_hi)) in &percentile {
let original = fits[key.0].elo - fits[key.1].elo;
let (basic_lo, basic_hi) = basic[key];
assert_eq!(basic_lo, 2.0 * original - perc_hi);
assert_eq!(basic_hi, 2.0 * original - perc_lo);
}
}
#[test]
fn basic_ci_is_well_formed() {
let pairs = dense_pairs_for_test(5, 30);
let fits = fit_graph(5, &pairs).unwrap();
let cis = bootstrap_pairwise_elo_diff_cis(
5,
&pairs,
&fits,
1000,
42,
0.95,
BootstrapMethod::Basic,
);
assert!(!cis.is_empty());
for (_, (lo, hi)) in cis {
assert!(lo.is_finite() && hi.is_finite() && lo <= hi);
}
}
#[test]
fn bca_ci_is_well_formed() {
let pairs = dense_pairs_for_test(5, 30);
let fits = fit_graph(5, &pairs).unwrap();
let cis =
bootstrap_pairwise_elo_diff_cis(5, &pairs, &fits, 1000, 42, 0.95, BootstrapMethod::Bca);
assert!(!cis.is_empty());
for (_, (lo, hi)) in cis {
assert!(lo.is_finite() && hi.is_finite() && lo <= hi);
}
}
#[test]
fn bca_close_to_percentile_on_a_balanced_graph() {
let pairs = dense_pairs_for_test(3, 100);
let fits = fit_graph(3, &pairs).unwrap();
let percentile = bootstrap_pairwise_elo_diff_cis(
3,
&pairs,
&fits,
20_000,
42,
0.95,
BootstrapMethod::Percentile,
);
let bca = bootstrap_pairwise_elo_diff_cis(
3,
&pairs,
&fits,
20_000,
42,
0.95,
BootstrapMethod::Bca,
);
for (key, (perc_lo, perc_hi)) in &percentile {
let (bca_lo, bca_hi) = bca[key];
assert_close(bca_lo, *perc_lo, 15.0);
assert_close(bca_hi, *perc_hi, 15.0);
}
}
#[test]
fn bca_differs_from_percentile_on_a_skewed_graph() {
let pairs = [
PairRecord {
a: 0,
b: 1,
a_wins: 19,
b_wins: 1,
draws: 0,
},
PairRecord {
a: 1,
b: 2,
a_wins: 19,
b_wins: 1,
draws: 0,
},
PairRecord {
a: 2,
b: 0,
a_wins: 10,
b_wins: 10,
draws: 0,
},
];
let fits = fit_graph(3, &pairs).unwrap();
let percentile = bootstrap_pairwise_elo_diff_cis(
3,
&pairs,
&fits,
10_000,
42,
0.95,
BootstrapMethod::Percentile,
);
let bca = bootstrap_pairwise_elo_diff_cis(
3,
&pairs,
&fits,
10_000,
42,
0.95,
BootstrapMethod::Bca,
);
assert_ne!(percentile, bca);
}
#[test]
fn bca_does_not_panic_when_jackknife_replicates_disconnect_the_pair() {
let pairs = fragile_bridge_pairs();
let fits = fit_graph(4, &pairs).unwrap();
let cis =
bootstrap_pairwise_elo_diff_cis(4, &pairs, &fits, 2000, 42, 0.95, BootstrapMethod::Bca);
for same_side in [(0, 1), (2, 3)] {
let (lo, hi) = cis[&same_side];
assert!(lo.is_finite() && hi.is_finite() && lo <= hi);
}
for cross in [(0, 2), (0, 3), (1, 2), (1, 3)] {
assert!(!cis.contains_key(&cross));
}
}
#[test]
fn jackknife_replicates_matches_closed_form_on_a_2_node_graph() {
use crate::stats::elo::elo_from_score;
let pairs = [PairRecord {
a: 0,
b: 1,
a_wins: 160,
b_wins: 40,
draws: 0,
}];
let reps = jackknife_replicates(2, &pairs, &[0, 0]);
let pair = &reps[&(0, 1)];
assert_eq!(pair.len(), 2);
let (drop_a_win_value, drop_a_win_weight) = pair[0];
let (drop_b_win_value, drop_b_win_weight) = pair[1];
assert_close(drop_a_win_weight, 160.0, 1e-9);
assert_close(drop_b_win_weight, 40.0, 1e-9);
assert_close(drop_a_win_value, -elo_from_score(40.0 / 199.0), 1e-6);
assert_close(drop_b_win_value, -elo_from_score(39.0 / 199.0), 1e-6);
}
#[test]
fn bca_pairwise_ci_matches_pinned_reference_at_fixed_seed() {
let pairs = [PairRecord {
a: 0,
b: 1,
a_wins: 160,
b_wins: 40,
draws: 0,
}];
let fits = fit_graph(2, &pairs).unwrap();
let cis = bootstrap_pairwise_elo_diff_cis(
2,
&pairs,
&fits,
20_000,
42,
0.95,
BootstrapMethod::Bca,
);
let (lo, hi) = cis[&(0, 1)];
assert_close(lo, 172.78363838458742, 1e-6);
assert_close(hi, 294.61000431176035, 1e-6);
let percentile_cis = bootstrap_pairwise_elo_diff_cis(
2,
&pairs,
&fits,
20_000,
42,
0.95,
BootstrapMethod::Percentile,
);
assert_ne!(cis[&(0, 1)], percentile_cis[&(0, 1)]);
}
}