Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
456 lines (426 sloc) 11.1 KB
/*
* File: elo.c
* Author: GGZ Dev Team
* Project: GGZ Server (moved from ggzdmod/ggzstats)
* Date: 5/07/2002 (moved from ggz_stats.c)
* Desc: GGZ game module stat functions - ELO ratings
* $Id: elo.c,v 1.1 2002/10/28 04:56:55 jdorje Exp $
*
* Copyright (C) 2001-2002 GGZ Dev Team.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*/
#include "elo.h"
/* FIXME: this table is about the ugliest thing ever. It holds the CDF's of
the normalized normal distribution. */
static double ztable[301] = {
0.0013498974275996112,
0.0013948866316060848,
0.0014412413183508832,
0.0014889981559605414,
0.001538194637014656,
0.001588869092024936,
0.0016410607029800905,
0.0016948095169527777,
0.001750156459762453,
0.0018071433496901768,
0.0018658129112387178,
0.0019262087889329593,
0.0019883755611550535,
0.002052358754007555,
0.0021182048551989241,
0.0021859613279451295,
0.0022556766248800209,
0.002327400201968588,
0.0024011825324152247,
0.0024770751205606678,
0.0025551305157595627,
0.0026354023262312176,
0.0027179452328760512,
0.0028028150030493526,
0.0028900685042839713,
0.0029797637179544423,
0.0030719597528726106,
0.0031667168588071504,
0.0032640964399167638,
0.0033641610680892331,
0.0034669744961752791,
0.0035726016711090103,
0.0036811087469041937,
0.003792563097516688,
0.0039070333295626036,
0.0040245892948822526,
0.0041453021029385084,
0.0042692441330391961,
0.0043964890463726869,
0.0045271117978451514,
0.0046611886477079811,
0.0047987971729647194,
0.0049400162785444568,
0.0050849262082311442,
0.005233608555335667,
0.0053861462730993015,
0.0055426236848157839,
0.0057031264936595605,
0.0058677417922075592,
0.0060365580716419398,
0.0062096652306207201,
0.0063871545838029564,
0.0065691188700164327,
0.00675565226005298,
0.0069468503640799373,
0.0071428102386527081,
0.0073436303933163138,
0.0075494107967811197,
0.0077602528826604122,
0.0079762595547552273,
0.0081975351918731065,
0.0084241856521673486,
0.0086563182769826552,
0.0088940418941937938,
0.0091374668210232324,
0.0093867048663250907,
0.0096418693323204185,
0.0099030750157714231,
0.010170438208581323,
0.01044407669780506,
0.010724109765059997,
0.011010658185321376,
0.01130384422509112,
0.011603791639926586,
0.011910625671316843,
0.012224473042894923,
0.012545461955972614,
0.012873722084387529,
0.01320938456864984,
0.0135525820093787,
0.013903448460015899,
0.01426211941880845,
0.014628731820047924,
0.015003424024558676,
0.015386335809424667,
0.015777608356947082,
0.016177384242823556,
0.016585807423542764,
0.017003023222986247,
0.017429178318231431,
0.017864420724550745,
0.018308899779600374,
0.018762766126796393,
0.019226171697872219,
0.019699269694617383,
0.0201822145697933,
0.020675162007226688,
0.021178268901080211,
0.021691693334300266,
0.022215594556245999,
0.022750132959500013,
0.023295467792401992,
0.023851764485976978,
0.024419185453399439,
0.024997895303140116,
0.025588059631423632,
0.026189844992999645,
0.026803418870745443,
0.027428949644120293,
0.028066606556483631,
0.028716559681294385,
0.029378979887203005,
0.030054038802049154,
0.03074190877577504,
0.031442762842267435,
0.032156774680134892,
0.032884118572433452,
0.033624969365345592,
0.034379502425825104,
0.03514789359821513,
0.035930319159845292,
0.036726955775621406,
0.03753798045161244,
0.038363570487644771,
0.03920390342891289,
0.040059157016615887,
0.040929509137628106,
0.041815137773216382,
0.042716220946811212,
0.043632936670844613,
0.044565462892666607,
0.045513977439549824,
0.046478657962796821,
0.047459681880963556,
0.048457226322209723,
0.049471468065793944,
0.050502583482726904,
0.05155074847559854,
0.052616138417595104,
0.053698928090725517,
0.054799291623271407,
0.055917402426483021,
0.057053433130537734,
0.058207555519782628,
0.059379940467282288,
0.06057075786869176,
0.061780176575479129,
0.063008364327519828,
0.064255487685086599,
0.065521711960259965,
0.066807201147784379,
0.06811211785539717,
0.069436623233655514,
0.070780876905290446,
0.072145036894116166,
0.073529259553522797,
0.074933699494582784,
0.076358509513802353,
0.077803840520547174,
0.079269841464176316,
0.080756659260914632,
0.082264438720498823,
0.083793322472628884,
0.085343450893260786,
0.086914962030774756,
0.088507991532053798,
0.090122672568510254,
0.091759135762094657,
0.093417509111326291,
0.095097917917381369,
0.096800484710277135,
0.098525329175190968,
0.10027256807895296,
0.10204231519675117,
0.10383468123908968,
0.10564977377903884,
0.10748769717981899,
0.10934855252275771,
0.11123243753566175,
0.11313944652164465,
0.11506967028845272,
0.11702319607832912,
0.11900010749846002,
0.12100048445204298,
0.1230244030700216,
0.12507193564352681,
0.12714315055706898,
0.12923811222252168,
0.13135688101394061,
0.13349951320325965,
0.13566606089690608,
0.13785657197337792,
0.14007109002182488,
0.1423096542816758,
0.14457229958335321,
0.14685905629011764,
0.14916995024108309,
0.15150500269544415,
0.15386423027795648,
0.15624764492571003,
0.15865525383623708,
0.1610870594169927,
0.1635430592362484,
0.16602324597543822,
0.16852760738299372,
0.17105612622970845,
0.1736087802656674,
0.17618554217877852,
0.17878637955494342,
0.18141125483990161,
0.18406012530278404,
0.18673294300140969,
0.18942965474935874,
0.192150202084855,
0.19489452124148976,
0.19766254312081705,
0.2004541932668526,
0.2032693918425032,
0.20610805360795725,
0.20897008790106242,
0.21185539861971758,
0.21476388420630449,
0.21769543763418348,
0.22064994639627722,
0.22362729249576385,
0.22662735243890197,
0.22964999723000723,
0.23269509236859903,
0.23576249784873582,
0.23885206816055621,
0.24196365229403949,
0.24509709374500249,
0.24825223052334316,
0.25142889516354494,
0.25462691473745036,
0.25784611086931519,
0.26108629975314901,
0.26434729217234998,
0.2676288935216391,
0.27093090383129681,
0.27425311779370587,
0.27759532479220023,
0.28095730893222093,
0.28433884907477647,
0.28773971887220517,
0.29115968680623477,
0.29459851622833394,
0.29805596540234741,
0.30153178754940763,
0.30502573089511137,
0.30853753871895068,
0.31206694940598489,
0.31561369650073978,
0.31917750876331719,
0.32275811022769929,
0.3263552202622283,
0.32996855363224042,
0.33359782056483578,
0.33724272681575818,
0.34090297373836298,
0.34457825835464639,
0.34826827342831013,
0.35197270753983279,
0.35569124516351835,
0.35942356674649178,
0.36316934878960927,
0.36692826393024869,
0.37069998102694834,
0.37448416524585493,
0.37828047814894639,
0.38208857778398969,
0.38590811877619485,
0.38973875242152484,
0.39358012678161919,
0.39743188678028851,
0.40129367430153673,
0.40516512828906587,
0.40904588484721671,
0.41293557734330005,
0.41683383651126915,
0.4207402905566856,
0.42465456526292905,
0.42857628409859905,
0.43250506832605989,
0.43644053711107383,
0.44038230763347214,
0.44432999519880867,
0.44828321335094301,
0.45224157398549714,
0.45620468746413118,
0.46017216272958139,
0.46414360742140437,
0.46811862799236997,
0.47209682982544549,
0.47607781735131321,
0.4800611941663635,
0.4840465631511035,
0.48803352658892385,
0.49202168628516352,
0.49601064368641357,
0.5
};
/* Looks like ELO uses a standard deviation of 200. */
#define STD_DEV (double)200.0
#define INCR (double)(1.0 / 100.0)
static double get_normal_cdf(double z)
{
/* This may not be worth the trouble... */
if (z < 0)
return 1 - get_normal_cdf(-z);
/* outside of our range */
if (z > 3)
return 1.0;
/* There are 100 entries per std-dev, and they're in reverse order,
AND they're for the lower end of the CDF. */
return 1 - ztable[300 - (int) (z * 100.0 + 0.5)];
}
static double elo_integrate_part(double val, double incr,
int num, int i, double *ratings)
{
double prob, myrating = ratings[i];
int j;
prob = get_normal_cdf(val + incr) - get_normal_cdf(val);
for (j = 0; j < num; j++) {
double prob2;
double ratingdiff = myrating - ratings[j];
if (j == i)
continue;
prob2 = get_normal_cdf(val + ratingdiff);
prob *= prob2;
}
return prob;
}
/* Returns ELO-style probability of winning determined by integration num is
number of players i is player being considered ratings is ratings of all
players */
static double elo_integrate_all(int num, int i, double *ratings)
{
double prob = 0, p;
for (p = -3; p < 3; p += INCR) {
prob += elo_integrate_part(p, INCR, num, i, ratings);
}
return prob;
}
static void elo_compute_expectations(int num, float *ratings, float *probs)
{
double *myratings = new double[num];
int i;
double sum = 0;
/* "normalize" the ratings */
for (i = 0; i < num; i++) {
myratings[i] = ratings[i];
myratings[i] /= STD_DEV;
}
for (i = 0; i < num; i++) {
probs[i] = elo_integrate_all(num, i, myratings);
sum += probs[i];
}
/* dbg_msg(GGZ_DBG_STATS, "Probabilities sum to %f; normalizing.", sum); */
for (i = 0; i < num; i++)
probs[i] /= sum;
delete [] myratings;
}
void elo_recalculate_ratings(int num_players, float *player_ratings,
int *player_teams, int num_teams,
float *team_ratings, float *team_winners)
{
float *team_probs = new float[num_teams];
int i;
/* Calculate the probability for each player to win, ELO-style. */
elo_compute_expectations(num_teams, team_ratings, team_probs);
/* Debugging data */
for (i = 0; i < num_players; i++) {
int team = num_teams > 0 ? player_teams[i] : i;
/* dbg_msg(GGZ_DBG_STATS,
"Player %d has rating %f, expectation %f.", i,
team_ratings[team], team_probs[team]); */
}
/* Calculate new ratings for all players. */
for (i = 0; i < num_players; i++) {
int team = num_teams > 0 ? player_teams[i] : i;
float K, diff;
/* FIXME: this is the chess distribution; games should be
able to set their own. */
if (player_ratings[i] < 2000)
K = 30.0;
else if (player_ratings[i] > 2400)
K = 10.0;
else
K = 130.0 - player_ratings[i] / 20.0;
diff = K * (team_winners[team] - team_probs[team]);
player_ratings[i] += diff;
/* dbg_msg(GGZ_DBG_STATS,
"Player %d has new rating %f (slope %f).", i,
player_ratings[i], K); */
}
delete [] team_probs;
}