Whole-History Rating: A Bayesian Rating System …

1 Whole-History Rating : A Bayesian RatingSystem for Players of Time-Varying StrengthR mi CoulomUniversit Charles de Gaulle, INRIA SEQUEL, CNRS GRAPPA, Lille, Rating (WHR) is a new method to estimatethe time-varying strengths of players involved in paired comparisons. Likemany variations of the Elo Rating System , the Whole-History approach isbased on the dynamic Bradley-Terry model. But, instead of using incre-mental approximations, WHR directly computes the exact maximum aposteriori over the whole Rating history of all players. This additional ac-curacy comes at a higher computational cost than traditional methods,but computation is still fast enough to be easily applied in real time tolarge-scale game servers (a new game is added in less than second).

2 Experiments demonstrate that, in comparison to Elo, Glicko, TrueSkill,and decayed- history algorithms, WHR produces better IntroductionInstitutions that organize competitive activities, such as sports or games, oftenrely on ratings systems. Rating systems provide an estimation of the strength ofcompetitors. This strength estimation makes it possible to set up more balancedmatches, motivate competitors by providing them with a measurement of theirprogress, and make predictions about the outcomes of future every institution designed its own Rating System , so many algorithmsexist. The following discussion summarizes the main kinds of Rating Rating Rating systems do not consider the variationin time of the strengths of players.

3 They are appropriate for Rating humansover a short period of time, or for Rating computers. An effective method for astatic Rating System consists in using Bayesian inference with the Bradley-Terrymodel [1]. But static Rating systems are not adapted to situations where playersmay make significant Rating Rating systems, such as the FIDE Rating System [4], Glicko [7], or TrueSkill [8] store a small amount of data foreach player (one number indicating strength, and sometimes another indicat-ing uncertainty). After each game, this data is updated for the participants inthe game. The Rating of the winner is increased, and the Rating of the loser CoulomIncremental Rating systems can handle players of time-varying strength, butdo not make optimal use of data.

4 For instance, if two players,AandB, enter therating System at the same time and play many games against each other, andnone against established opponents, then their relative strength will be correctlyestimated, but not their strength with respect to the other players. If playerAthen plays against established opponents, and its Rating changes, then the ratingof playerBshould change too. But incremental Rating systems would leaveB srating Rating order to fix the deficiencies of incre-mental Rating systems, a static Rating algorithm may be applied, limited to recentgames. This idea may be refined by giving a decaying weight to games, eitherexponential or linear1.

5 With this decay, old games are progressively forgotten,which allows to measure the progress of decayed- history approach solves some problems of incremental ratingsystems, but also has some flaws. The main problem is that the decay of gameweights generates a very fast increase in the uncertainty of player ratings . Thisis unlike incremental systems that assume that Rating uncertainty grows likethe square root of time. With the decayed- history approach, players who stopplaying for a while may experience huge jumps in their ratings when they startplaying again, and players who play very frequently may have the feeling thattheir Rating is stuck. If players don t all play at the same frequency, there is nogood way to tune the speed of the Bayesian approach that may be more theoreti-cally sound than decayed history consists in using the same model as incrementalalgorithms, but with less approximations.

6 The weakness of algorithms like Glickoand TrueSkill lies in the inaccuracies of representing the probability distribu-tion with just one value and one variance for every player, ignoring of incremental algorithms already proposed to correct inaccuracies byrunning several passes of the algorithm forward and backward in time [10, 5, 7,2]. Edwards [3], with Edo ratings , proposed a method to directly estimate themaximum a posteriori on the exact WHR algorithm presented in this paper is similar in principle to Edoratings, although the numerical method is different (Edo uses MM [9], whereasWHR uses the more efficient Newton s method). On his web site, Edwards wrotethat Edo ratings are not particularly suitable to the regular updating of currentratings.

7 Experiments presented in this paper clearly indicate that he underesti-mated his idea: evaluating ratings of the past more accurately helps to evaluatecurrent ratings : the prediction rate obtained with WHR outperforms decayedhistory and incremental algorithms. Also, the WHR algorithm allows to rapidlyupdate ratings after the addition of one game, making it suitable for large-scalereal-time estimation of idea is often credited to Ken Thompson (for instance, by Sonas [14]), but Icould not find a more precise referenceWhole- history Ratings3 Paper 2 presents the dynamic Bradley-Terry model, Section 3is the WHR algorithm, and Section 4 presents experiment results on data of theKGS Go The Dynamic Bradley-Terry ModelThis section briefly presents the dynamic Bradley-Terry model [6] that is thebasis for the WHR Notations Player number:i {1.}

8 ,N}, integer index Elo Rating of playeriat timet:Ri(t), real number. Rating of playeriat timet: i(t), defined by i(t) = 10Ri(t)400. Natural Rating of playeriat timet:ri(t) = ln i(t) =Ri(t)ln ratings are familiar to chess players, but are on a rather arbitrary andinconvenient scale. Natural ratings will be used most of the time in this paper,because they make calculations Bradley-Terry ModelThe Bradley-Terry model for paired comparisons gives the probability of winninga game as a function of ratings :P(playeribeats playerjat timet) = i(t) i(t) + j(t).The Bradley-Terry model may be generalized to handle draws, advantage ofplaying first, teams, and multi-player games [9].

9 In this paper, only the simpleformulation will be used, but it would be straightforward to generalize the WHRalgorithm to those more complex Bayesian InferenceThe principle of Bayesian Inference consists in computing a probability distribu-tion over player ratings ( ) from the observation of game results (G) by invertingthe model thanks to Bayes formula:p( |G) =P(G| )p( )P(G).In this formula,p( )is a prior distribution over (lower-casepis usedfor probability densities), andP(G)is a normalizing (G| )is theBradley-Terry model described in the previous ( |G)is called the pos-terior distribution of . The value of that maximizesp( |G)is the maximum aposteriori, and may be used as an estimation of the strengths of players, derivedfrom the observation of their game PriorIn the dynamic Bradley-Terry model, the prior has two roles.

10 First, a priorprobability distribution over the range of ratings is applied. This way, the ratingof a player with 100% wins does not go to infinity. Also, a prior controls thevariation of the ratings in time, to avoid huge jumps in the dynamic Bradley-Terry model, the prior that controls the variation ofratings in time is a Wiener process:ri(t2) ri(t1) N(0,|t2 t1|w2).wis a parameter of the model, that indicates the variability of ratings in extreme case ofw= 0would mean static realizations of a Wiener process are plotted on Figure 1. The Wienerprocess is a model for Brownian motion, and can be simulated by adding anindependent normally-distributed random value at each time step.