multi_skill/systems/
topcoder_sys.rs

1//! Topcoder system details: https://www.topcoder.com/community/competitive-programming/how-to-compete/ratings
2//! Further analysis: https://web.archive.org/web/20120417104152/http://brucemerry.org.za:80/tc-rating/rating_submit1.pdf
3
4use super::util::{standard_normal_cdf, standard_normal_cdf_inv, Player, Rating, RatingSystem};
5use rayon::prelude::*;
6
7#[derive(Debug)]
8pub struct TopcoderSys {
9    pub weight_multiplier: f64, // must be positive
10}
11
12impl Default for TopcoderSys {
13    fn default() -> Self {
14        Self {
15            weight_multiplier: 1.,
16        }
17    }
18}
19
20impl TopcoderSys {
21    fn win_probability(&self, multiplier: f64, player: &Rating, foe: &Rating) -> f64 {
22        let z = (player.mu - foe.mu) / player.sig.hypot(foe.sig) / multiplier;
23        standard_normal_cdf(z)
24    }
25}
26
27impl RatingSystem for TopcoderSys {
28    fn round_update(&self, contest_weight: f64, standings: Vec<(&mut Player, usize, usize)>) {
29        let num_coders = standings.len() as f64;
30        let ave_rating = standings
31            .iter()
32            .map(|&(ref player, _, _)| player.approx_posterior.mu)
33            .sum::<f64>()
34            / num_coders;
35
36        let c_factor = {
37            let mut mean_vol_sq = standings
38                .iter()
39                .map(|&(ref player, _, _)| player.approx_posterior.sig.powi(2))
40                .sum::<f64>()
41                / num_coders;
42            if num_coders > 1. {
43                mean_vol_sq += standings
44                    .iter()
45                    .map(|&(ref player, _, _)| (player.approx_posterior.mu - ave_rating).powi(2))
46                    .sum::<f64>()
47                    / (num_coders - 1.);
48            }
49            mean_vol_sq.sqrt()
50        };
51
52        let limit_weight = 1. / 0.82 - 1.;
53        let cap_multiplier = self.weight_multiplier * (1. + limit_weight)
54            / (1. + limit_weight * self.weight_multiplier);
55
56        let new_ratings: Vec<(Rating, f64)> = standings
57            .par_iter()
58            .map(|(player, lo, hi)| {
59                let old_rating = player.approx_posterior.mu;
60                let vol_sq = player.approx_posterior.sig.powi(2);
61
62                let mut weight = contest_weight * self.weight_multiplier;
63                let ex_rank = standings
64                    .iter()
65                    .map(|&(ref foe, _, _)| {
66                        self.win_probability(
67                            weight,
68                            &foe.approx_posterior,
69                            &player.approx_posterior,
70                        )
71                    })
72                    .sum::<f64>();
73                let ac_rank = 0.5 * (1 + lo + hi) as f64;
74
75                // cdf(-perf) = rank / num_coders
76                //   => perf  = -inverse_cdf(rank / num_coders)
77                let ex_perf = -standard_normal_cdf_inv(ex_rank / num_coders);
78                let ac_perf = -standard_normal_cdf_inv(ac_rank / num_coders);
79                let perf_as = old_rating + c_factor * (ac_perf - ex_perf);
80
81                let num_contests = player.event_history.len() as f64;
82                weight *= 1. / (0.82 - 0.42 / num_contests) - 1.;
83                if old_rating >= 2500. {
84                    weight *= 0.8;
85                } else if old_rating >= 2000. {
86                    weight *= 0.9;
87                }
88
89                let mut cap = 150. + 1500. / (num_contests + 1.);
90                cap *= cap_multiplier;
91
92                let try_rating = (old_rating + weight * perf_as) / (1. + weight);
93                let new_rating = try_rating.max(old_rating - cap).min(old_rating + cap);
94                let new_vol =
95                    ((try_rating - old_rating).powi(2) / weight + vol_sq / (1. + weight)).sqrt();
96
97                (
98                    Rating {
99                        mu: new_rating,
100                        sig: new_vol,
101                    },
102                    perf_as,
103                )
104            })
105            .collect();
106
107        standings.into_par_iter().zip(new_ratings).for_each(
108            |((player, _, _), (new_rating, new_perf))| {
109                player.update_rating(new_rating, new_perf);
110            },
111        );
112    }
113}
multi_skill/systems/topcoder_sys.rs

multi_skill/systems/
topcoder_sys.rs
