-
-
Notifications
You must be signed in to change notification settings - Fork 2.2k
/
RatingCalculator.java
380 lines (319 loc) · 12 KB
/
RatingCalculator.java
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
/*
* Copyright (C) 2013 Jeremy Gooch <http://www.linkedin.com/in/jeremygooch/>
*
* The licence covering the contents of this file is described in the file LICENCE.txt,
* which should have been included as part of the distribution containing this file.
*/
package org.goochjs.glicko2;
import java.util.List;
import org.joda.time.DateTime;
import org.joda.time.Duration;
/**
* This is the main calculation engine based on the contents of Glickman's paper.
* http://www.glicko.net/glicko/glicko2.pdf
*
* @author Jeremy Gooch
*
*/
public class RatingCalculator {
private final static double DEFAULT_RATING = 1500.0;
private final static double DEFAULT_DEVIATION = 350;
private final static double DEFAULT_VOLATILITY = 0.06;
private final static double DEFAULT_TAU = 0.75;
private final static double MULTIPLIER = 173.7178;
private final static double CONVERGENCE_TOLERANCE = 0.000001;
private final static int ITERATION_MAX = 1000;
private final static double DAYS_PER_MILLI = 1.0 / (1000 * 60 * 60 * 24);
private final double tau; // constrains volatility over time
private final double defaultVolatility;
private double ratingPeriodsPerMilli;
/**
* Standard constructor, taking default values for volatility
*/
public RatingCalculator() {
tau = DEFAULT_TAU;
defaultVolatility = DEFAULT_VOLATILITY;
}
/**
*
* @param initVolatility Initial volatility for new ratings
* @param tau How volatility changes over time
*/
public RatingCalculator(double initVolatility, double tau) {
this.defaultVolatility = initVolatility;
this.tau = tau;
}
/**
*
* @param initVolatility Initial volatility for new ratings
* @param tau How volatility changes over time
*/
public RatingCalculator(double initVolatility, double tau, double ratingPeriodsPerDay) {
this.defaultVolatility = initVolatility;
this.tau = tau;
this.ratingPeriodsPerMilli = ratingPeriodsPerDay * DAYS_PER_MILLI;
}
/**
* <p>Run through all players within a resultset and calculate their new ratings.</p>
* <p>Players within the resultset who did not compete during the rating period
* will have see their deviation increase (in line with Prof Glickman's paper).</p>
* <p>Note that this method will clear the results held in the association resultset.</p>
*
* @param results
*/
public void updateRatings(RatingPeriodResults results) {
updateRatings(results, false);
}
/**
* <p>Run through all players within a resultset and calculate their new ratings.</p>
* <p>Players within the resultset who did not compete during the rating period
* will have see their deviation increase (in line with Prof Glickman's paper).</p>
* <p>Note that this method will clear the results held in the association resultset.</p>
*
* @param results
* @param ratingPeriodEndDate
* @param ratingPeriodLengthMillis
*/
public void updateRatings(RatingPeriodResults results, boolean skipDeviationIncrease) {
for ( Rating player : results.getParticipants() ) {
double elapsedRatingPeriods = skipDeviationIncrease ? 0 : 1;
if ( results.getResults(player).size() > 0 ) {
calculateNewRating(player, results.getResults(player), elapsedRatingPeriods);
} else {
// if a player does not compete during the rating period, then only Step 6 applies.
// the player's rating and volatility parameters remain the same but deviation increases
player.setWorkingRating(player.getGlicko2Rating());
player.setWorkingRatingDeviation(calculateNewRD(player.getGlicko2RatingDeviation(), player.getVolatility(), elapsedRatingPeriods));
player.setWorkingVolatility(player.getVolatility());
}
}
// now iterate through the participants and confirm their new ratings
for ( Rating player : results.getParticipants() ) {
player.finaliseRating();
}
// lastly, clear the result set down in anticipation of the next rating period
results.clear();
}
/**
* This is the formula defined in step 6. It is also used for players
* who have not competed during the rating period.
*
* @param player
* @param ratingPeriodEndDate
* @param reverse
* @return new rating deviation
*/
public double previewDeviation(Rating player, DateTime ratingPeriodEndDate, boolean reverse) {
double elapsedRatingPeriods = 0;
if ( ratingPeriodsPerMilli != 0 && player.getLastRatingPeriodEndDate() != null ) {
Duration interval = new Duration(player.getLastRatingPeriodEndDate(), ratingPeriodEndDate);
elapsedRatingPeriods = interval.getMillis() * ratingPeriodsPerMilli;
}
if (reverse) {
elapsedRatingPeriods = -elapsedRatingPeriods;
}
double newRD = calculateNewRD(player.getGlicko2RatingDeviation(), player.getVolatility(), elapsedRatingPeriods);
return convertRatingDeviationToOriginalGlickoScale(newRD);
}
/**
* This is the function processing described in step 5 of Glickman's paper.
*
* @param player
* @param results
* @param elapsedRatingPeriods
*/
private void calculateNewRating(Rating player, List<Result> results, double elapsedRatingPeriods) throws RuntimeException {
double phi = player.getGlicko2RatingDeviation();
double sigma = player.getVolatility();
double a = Math.log( Math.pow(sigma, 2) );
double delta = delta(player, results);
double v = v(player, results);
// step 5.2 - set the initial values of the iterative algorithm to come in step 5.4
double A = a;
double B;
if ( Math.pow(delta, 2) > Math.pow(phi, 2) + v ) {
B = Math.log( Math.pow(delta, 2) - Math.pow(phi, 2) - v );
} else {
double k = 1;
B = a - ( k * Math.abs(tau));
while ( f(B , delta, phi, v, a, tau) < 0 ) {
k++;
B = a - ( k * Math.abs(tau));
}
}
// step 5.3
double fA = f(A , delta, phi, v, a, tau);
double fB = f(B , delta, phi, v, a, tau);
// step 5.4
int iterations = 0;
while ( Math.abs(B - A) > CONVERGENCE_TOLERANCE && iterations < ITERATION_MAX) {
++iterations;
// System.out.println(String.format("%f - %f (%f) > %f", B, A, Math.abs(B - A), CONVERGENCE_TOLERANCE));
double C = A + (( (A-B)*fA ) / (fB - fA));
double fC = f(C , delta, phi, v, a, tau);
if ( fC * fB <= 0 ) {
A = B;
fA = fB;
} else {
fA = fA / 2.0;
}
B = C;
fB = fC;
}
if (iterations == ITERATION_MAX) {
System.out.println(String.format("Convergence fail at %d iterations", iterations));
System.out.println(player.toString());
for ( Result result: results ) {
System.out.println(result.toString());
}
throw new RuntimeException("Convergence fail");
}
double newSigma = Math.exp( A/2.0 );
player.setWorkingVolatility(newSigma);
// Step 6
double phiStar = calculateNewRD( phi, newSigma, elapsedRatingPeriods );
// Step 7
double newPhi = 1.0 / Math.sqrt(( 1.0 / Math.pow(phiStar, 2) ) + ( 1.0 / v ));
// note that the newly calculated rating values are stored in a "working" area in the Rating object
// this avoids us attempting to calculate subsequent participants' ratings against a moving target
player.setWorkingRating(
player.getGlicko2Rating()
+ ( Math.pow(newPhi, 2) * outcomeBasedRating(player, results)));
player.setWorkingRatingDeviation(newPhi);
player.incrementNumberOfResults(results.size());
}
private double f(double x, double delta, double phi, double v, double a, double tau) {
return ( Math.exp(x) * ( Math.pow(delta, 2) - Math.pow(phi, 2) - v - Math.exp(x) ) /
(2.0 * Math.pow( Math.pow(phi, 2) + v + Math.exp(x), 2) )) -
( ( x - a ) / Math.pow(tau, 2) );
}
/**
* This is the first sub-function of step 3 of Glickman's paper.
*
* @param deviation
* @return
*/
private double g(double deviation) {
return 1.0 / ( Math.sqrt( 1.0 + ( 3.0 * Math.pow(deviation, 2) / Math.pow(Math.PI,2) )));
}
/**
* This is the second sub-function of step 3 of Glickman's paper.
*
* @param playerRating
* @param opponentRating
* @param opponentDeviation
* @return
*/
private double E(double playerRating, double opponentRating, double opponentDeviation) {
return 1.0 / (1.0 + Math.exp( -1.0 * g(opponentDeviation) * ( playerRating - opponentRating )));
}
/**
* This is the main function in step 3 of Glickman's paper.
*
* @param player
* @param results
* @return
*/
private double v(Rating player, List<Result> results) {
double v = 0.0;
for ( Result result: results ) {
v = v + (
( Math.pow( g(result.getOpponent(player).getGlicko2RatingDeviation()), 2) )
* E(player.getGlicko2Rating(),
result.getOpponent(player).getGlicko2Rating(),
result.getOpponent(player).getGlicko2RatingDeviation())
* ( 1.0 - E(player.getGlicko2Rating(),
result.getOpponent(player).getGlicko2Rating(),
result.getOpponent(player).getGlicko2RatingDeviation())
));
}
return 1/v;
}
/**
* This is a formula as per step 4 of Glickman's paper.
*
* @param player
* @param results
* @return delta
*/
private double delta(Rating player, List<Result> results) {
return v(player, results) * outcomeBasedRating(player, results);
}
/**
* This is a formula as per step 4 of Glickman's paper.
*
* @param player
* @param results
* @return expected rating based on game outcomes
*/
private double outcomeBasedRating(Rating player, List<Result> results) {
double outcomeBasedRating = 0;
for ( Result result: results ) {
outcomeBasedRating = outcomeBasedRating
+ ( g(result.getOpponent(player).getGlicko2RatingDeviation())
* ( result.getScore(player) - E(
player.getGlicko2Rating(),
result.getOpponent(player).getGlicko2Rating(),
result.getOpponent(player).getGlicko2RatingDeviation() ))
);
}
return outcomeBasedRating;
}
/**
* This is the formula defined in step 6. It is also used for players
* who have not competed during the rating period.
*
* @param phi
* @param sigma
* @param elapsedRatingPeriods
* @return new rating deviation
*/
private double calculateNewRD(double phi, double sigma, double elapsedRatingPeriods) {
return Math.sqrt( Math.pow(phi, 2) + elapsedRatingPeriods * Math.pow(sigma, 2) );
}
/**
* Converts from the value used within the algorithm to a rating in the same range as traditional Elo et al
*
* @param rating in Glicko2 scale
* @return rating in Glicko scale
*/
public static double convertRatingToOriginalGlickoScale(double rating) {
return ( ( rating * MULTIPLIER ) + DEFAULT_RATING );
}
/**
* Converts from a rating in the same range as traditional Elo et al to the value used within the algorithm
*
* @param rating in Glicko scale
* @return rating in Glicko2 scale
*/
public static double convertRatingToGlicko2Scale(double rating) {
return ( ( rating - DEFAULT_RATING ) / MULTIPLIER ) ;
}
/**
* Converts from the value used within the algorithm to a rating deviation in the same range as traditional Elo et al
*
* @param ratingDeviation in Glicko2 scale
* @return ratingDeviation in Glicko scale
*/
public static double convertRatingDeviationToOriginalGlickoScale(double ratingDeviation) {
return ( ratingDeviation * MULTIPLIER ) ;
}
/**
* Converts from a rating deviation in the same range as traditional Elo et al to the value used within the algorithm
*
* @param ratingDeviation in Glicko scale
* @return ratingDeviation in Glicko2 scale
*/
public static double convertRatingDeviationToGlicko2Scale(double ratingDeviation) {
return ( ratingDeviation / MULTIPLIER );
}
public double getDefaultRating() {
return DEFAULT_RATING;
}
public double getDefaultVolatility() {
return defaultVolatility;
}
public double getDefaultRatingDeviation() {
return DEFAULT_DEVIATION;
}
}