Skip to content

Instantly share code, notes, and snippets.

@grignaak
Last active August 23, 2016 21:22
Show Gist options
  • Save grignaak/44ff01043729fa78218fc360223059f6 to your computer and use it in GitHub Desktop.
Save grignaak/44ff01043729fa78218fc360223059f6 to your computer and use it in GitHub Desktop.
Online ranking algorithm in rust
use std::cmp::Ordering;
pub struct Ability {
mean: f64,
variance: f64,
}
impl Ability {
pub fn zero() -> Self {
Self::with_stddev(0.0, 0.0)
}
pub fn with_stddev(mean: f64, stddev: f64) -> Self {
Self::with_variance(mean, stddev*stddev)
}
pub fn with_variance(mean: f64, variance: f64) -> Self {
Ability { mean: mean, variance: variance }
}
pub fn stddev(&self) -> f64 { self.variance.sqrt() }
pub fn mean(&self) -> f64 { self.mean }
pub fn skill(&self) -> u64 {
let truth = self.mean - (3.0 * self.stddev());
// nobody wants to see a zero skill, nor something out of range
// also integers are cool (for human consumption)
truth.max(1.0).min(50.0) as u64
}
}
pub struct Player {
pub name: String,
pub ability: Ability,
}
pub struct TeamResult {
pub score: u64,
pub team: Vec<Player>,
}
const BETA : f64 = (25.0 / 3.0) / 2.0;
const BETA_SQUARED: f64 = BETA * BETA;
pub fn update_abilities(game: &[TeamResult]) -> Vec<Player> {
if game.is_empty() {
return Vec::new();
}
let mut teams: Vec<_> = game.iter()
.map(|t| (t.score, &t.team, team_ability(&t.team)))
.collect();
let mut updated_players: Vec<Player> = Vec::new();
let gamma = 1.0 / (game.len() as f64);
for &(score, ref players, ref team_ability) in teams.iter() {
let mut Omega = 0.0;
let mut Delta = 0.0;
for &(opponent_score, _, ref opponent_ability) in teams.iter() {
if (opponent_ability as *const Ability) == (team_ability as *const Ability) {
continue;
}
let c = (team_ability.variance + opponent_ability.variance + 2.0 * BETA_SQUARED).sqrt();
let p = 1.0 / (1.0 + ((opponent_ability.mean - team_ability.mean) / c).exp());
let variance_over_c = team_ability.variance / c;
let s = match score.cmp(&opponent_score) {
Ordering::Greater => 1.0,
Ordering::Less => 0.0,
_ => 0.5,
};
Omega += variance_over_c * (s - p);
Delta += gamma * (variance_over_c / c) * p * (1.0 - p);
}
updated_players.append(&mut resulting_abilities(&players, team_ability.variance, Omega, Delta));
}
updated_players
}
fn resulting_abilities(players: &[Player], team_variance: f64, Omega: f64, Delta: f64) -> Vec<Player> {
players.into_iter()
.map(|p| {
let ability = &p.ability;
let contribution = ability.variance / team_variance;
let new_ability = Ability::with_stddev(
ability.mean + Omega * contribution,
ability.stddev() * (1.0 - Delta * contribution).max(0.01).sqrt().max(0.1));
Player {
name: p.name.to_owned(),
ability: new_ability,
}
})
.collect()
}
fn team_ability(team : &[Player]) -> Ability {
let mut ability = Ability::zero();
for player in team.iter() {
ability.mean += player.ability.mean;
ability.variance += player.ability.variance;
}
ability
}
mod ability;
use ability::{ update_abilities, Ability, Player, TeamResult };
fn main() {
fn team(players: &[(&str, f64, f64)]) -> Vec<Player> {
players.iter()
.map(|&(name, mu, sigma)| Player { name: name.to_owned(), ability: Ability::with_stddev(mu, sigma) } )
.collect()
}
let ppm = team(&[("peter", 37.0, 3.1), ("paul", 19.3, 8.1), ("mary", 27.1, 8.2)]);
let beatles = team(&[("john", 48.7, 0.1), ("paul", 49.2, 0.1), ("george", 47.6, 0.4), ("ringo", 37.1, 3.2)]);
let monkees = team(&[("michael", 19.7, 4.3), ("mickey", 20.4, 5.2), ("davy", 26.1, 3.7), ("peter", 18.2, 4.3)]);
let game = [
TeamResult { score: 20, team: ppm },
TeamResult { score: 41, team: beatles },
TeamResult { score: 18, team: monkees },
];
for ref player in update_abilities(&game).iter() {
let ability = &player.ability;
println!("{name:10}: {skill:2}, ({mu}, {sigma})",
name=&player.name, skill=ability.skill(), mu=ability.mean(), sigma=ability.stddev());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment