1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! Topcoder system details: https://www.topcoder.com/community/competitive-programming/how-to-compete/ratings
//! Further analysis: https://web.archive.org/web/20120417104152/http://brucemerry.org.za:80/tc-rating/rating_submit1.pdf

use super::util::{standard_normal_cdf, standard_normal_cdf_inv, Player, Rating, RatingSystem};
use rayon::prelude::*;

#[derive(Debug)]
pub struct TopcoderSys {
    pub weight_multiplier: f64, // must be positive
}

impl Default for TopcoderSys {
    fn default() -> Self {
        Self {
            weight_multiplier: 1.,
        }
    }
}

impl TopcoderSys {
    fn win_probability(&self, multiplier: f64, player: &Rating, foe: &Rating) -> f64 {
        let z = (player.mu - foe.mu) / player.sig.hypot(foe.sig) / multiplier;
        standard_normal_cdf(z)
    }
}

impl RatingSystem for TopcoderSys {
    fn round_update(&self, contest_weight: f64, standings: Vec<(&mut Player, usize, usize)>) {
        let num_coders = standings.len() as f64;
        let ave_rating = standings
            .iter()
            .map(|&(ref player, _, _)| player.approx_posterior.mu)
            .sum::<f64>()
            / num_coders;

        let c_factor = {
            let mut mean_vol_sq = standings
                .iter()
                .map(|&(ref player, _, _)| player.approx_posterior.sig.powi(2))
                .sum::<f64>()
                / num_coders;
            if num_coders > 1. {
                mean_vol_sq += standings
                    .iter()
                    .map(|&(ref player, _, _)| (player.approx_posterior.mu - ave_rating).powi(2))
                    .sum::<f64>()
                    / (num_coders - 1.);
            }
            mean_vol_sq.sqrt()
        };

        let limit_weight = 1. / 0.82 - 1.;
        let cap_multiplier = self.weight_multiplier * (1. + limit_weight)
            / (1. + limit_weight * self.weight_multiplier);

        let new_ratings: Vec<(Rating, f64)> = standings
            .par_iter()
            .map(|(player, lo, hi)| {
                let old_rating = player.approx_posterior.mu;
                let vol_sq = player.approx_posterior.sig.powi(2);

                let mut weight = contest_weight * self.weight_multiplier;
                let ex_rank = standings
                    .iter()
                    .map(|&(ref foe, _, _)| {
                        self.win_probability(
                            weight,
                            &foe.approx_posterior,
                            &player.approx_posterior,
                        )
                    })
                    .sum::<f64>();
                let ac_rank = 0.5 * (1 + lo + hi) as f64;

                // cdf(-perf) = rank / num_coders
                //   => perf  = -inverse_cdf(rank / num_coders)
                let ex_perf = -standard_normal_cdf_inv(ex_rank / num_coders);
                let ac_perf = -standard_normal_cdf_inv(ac_rank / num_coders);
                let perf_as = old_rating + c_factor * (ac_perf - ex_perf);

                let num_contests = player.event_history.len() as f64;
                weight *= 1. / (0.82 - 0.42 / num_contests) - 1.;
                if old_rating >= 2500. {
                    weight *= 0.8;
                } else if old_rating >= 2000. {
                    weight *= 0.9;
                }

                let mut cap = 150. + 1500. / (num_contests + 1.);
                cap *= cap_multiplier;

                let try_rating = (old_rating + weight * perf_as) / (1. + weight);
                let new_rating = try_rating.max(old_rating - cap).min(old_rating + cap);
                let new_vol =
                    ((try_rating - old_rating).powi(2) / weight + vol_sq / (1. + weight)).sqrt();

                (
                    Rating {
                        mu: new_rating,
                        sig: new_vol,
                    },
                    perf_as,
                )
            })
            .collect();

        standings.into_par_iter().zip(new_ratings).for_each(
            |((player, _, _), (new_rating, new_perf))| {
                player.update_rating(new_rating, new_perf);
            },
        );
    }
}