multi_skill/systems/
codeforces_sys.rs

1//! Codeforces system details: https://codeforces.com/blog/entry/20762
2
3use super::util::{
4    robust_average, standard_logistic_cdf, Player, Rating, RatingSystem, TANH_MULTIPLIER,
5};
6use rayon::prelude::*;
7
8#[derive(Debug)]
9pub struct CodeforcesSys {
10    pub beta: f64, // must be positive, only affects scale, since CF ignores SIG_NEWBIE
11    pub weight_multiplier: f64, // must be positive
12}
13
14impl Default for CodeforcesSys {
15    fn default() -> Self {
16        Self {
17            beta: 400. * TANH_MULTIPLIER / std::f64::consts::LN_10,
18            weight_multiplier: 1.,
19        }
20    }
21}
22
23impl CodeforcesSys {
24    // ratings is a list of the participants, ordered from first to last place
25    // returns: performance of the player in ratings[id] who tied against ratings[lo..hi]
26    fn compute_performance(
27        &self,
28        sig_perf: f64,
29        better: &[Rating],
30        worse: &[Rating],
31        all: &[Rating],
32        my_rating: Rating,
33    ) -> f64 {
34        // The conversion is 2*rank - 1/my_sig = 2*pos_offset + tied_offset = pos - neg + all
35        // Note: the caller currently guarantees that every .sig equals sig_perf
36        let pos_offset: f64 = better.iter().map(|rating| rating.sig.recip()).sum();
37        let neg_offset: f64 = worse.iter().map(|rating| rating.sig.recip()).sum();
38        let all_offset: f64 = all.iter().map(|rating| rating.sig.recip()).sum();
39
40        let ac_rank = 0.5 * (pos_offset - neg_offset + all_offset + my_rating.sig.recip());
41        let ex_rank = 0.5 / my_rating.sig
42            + all
43                .iter()
44                .map(|rating| self.win_probability(sig_perf, rating, &my_rating) / rating.sig)
45                .sum::<f64>();
46
47        let geo_rank = (ac_rank * ex_rank).sqrt();
48        let geo_offset = 2. * geo_rank - my_rating.sig.recip() - all_offset;
49        let geo_rating = robust_average(
50            all.iter().cloned().map(Into::into),
51            TANH_MULTIPLIER * geo_offset,
52            0.,
53        );
54        geo_rating
55    }
56
57    fn win_probability(&self, sig_perf: f64, player: &Rating, foe: &Rating) -> f64 {
58        let z = (player.mu - foe.mu) / sig_perf;
59        standard_logistic_cdf(z)
60    }
61}
62
63impl RatingSystem for CodeforcesSys {
64    fn round_update(&self, contest_weight: f64, standings: Vec<(&mut Player, usize, usize)>) {
65        let sig_perf = self.beta / contest_weight.sqrt();
66        let all_ratings: Vec<Rating> = standings
67            .par_iter()
68            .map(|(player, _, _)| Rating {
69                mu: player.approx_posterior.mu,
70                sig: sig_perf,
71            })
72            .collect();
73
74        standings
75            .into_par_iter()
76            .zip(all_ratings.par_iter())
77            .for_each(|((player, lo, hi), &my_rating)| {
78                let geo_perf = self.compute_performance(
79                    sig_perf,
80                    &all_ratings[..lo],
81                    &all_ratings[hi + 1..],
82                    &all_ratings,
83                    my_rating,
84                );
85                let weight = contest_weight * self.weight_multiplier;
86                let mu = (my_rating.mu + weight * geo_perf) / (1. + weight);
87                let sig = player.approx_posterior.sig;
88                player.update_rating(Rating { mu, sig }, geo_perf);
89            });
90    }
91}
multi_skill/systems/codeforces_sys.rs

multi_skill/systems/
codeforces_sys.rs
