Last active
August 23, 2016 21:22
-
-
Save grignaak/44ff01043729fa78218fc360223059f6 to your computer and use it in GitHub Desktop.
Online ranking algorithm in rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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