xonstat/glicko.py

   1 import logging
   2 import math
   3 import sys
   4
   5 from xonstat.models import PlayerGlicko, Game, PlayerGameStat
   6
   7 log = logging.getLogger(__name__)
   8
   9 # DEBUG
  10 # log.addHandler(logging.StreamHandler())
  11 # log.setLevel(logging.DEBUG)
  12
  13 # the default system volatility constant
  14 TAU = 0.3
  15
  16 # how much ping influences results
  17 LATENCY_TREND_FACTOR = 0.2
  18
  19
  20 def calc_g(phi):
  21     return 1 / math.sqrt(1 + (3 * phi ** 2) / (math.pi ** 2))
  22
  23
  24 def calc_e(mu, mu_j, phi_j):
  25     return 1. / (1 + math.exp(-calc_g(phi_j) * (mu - mu_j)))
  26
  27
  28 def calc_v(gs, es):
  29     """ Estimated variance of the team or player's ratings based only on game outcomes. """
  30     total = 0.0
  31     for i in range(len(gs)):
  32         total += (gs[i] ** 2) * es[i] * (1-es[i])
  33
  34     return 1. / total
  35
  36
  37 def calc_delta(v, gs, es, results):
  38     """
  39     Compute the estimated improvement in rating by comparing the pre-period rating to the
  40     performance rating based only on game outcomes.
  41     """
  42     total = 0.0
  43     for i in range(len(gs)):
  44         total += gs[i] * (results[i] - es[i])
  45
  46     return v * total
  47
  48
  49 def calc_sigma_bar(sigma, delta, phi, v, tau=TAU):
  50     """ Compute the new volatility. """
  51     epsilon = 0.000001
  52     A = a = math.log(sigma**2)
  53
  54     # pre-compute some terms
  55     delta_sq = delta ** 2
  56     phi_sq = phi ** 2
  57
  58     def f(x):
  59         e_up_x = math.e ** x
  60         term_a = (e_up_x * (delta_sq - phi_sq - v - e_up_x)) / (2 * (phi_sq + v + e_up_x) ** 2)
  61         term_b = (x - a) / tau ** 2
  62         return term_a - term_b
  63
  64     if delta_sq > (phi_sq + v):
  65         B = math.log(delta_sq - phi_sq - v)
  66     else:
  67         k = 1
  68         while f(a - k * tau) < 0:
  69             k += 1
  70         B = a - k * tau
  71
  72     fa, fb = f(A), f(B)
  73     while abs(B - A) > epsilon:
  74         C = A + (A - B) * (fa / (fb - fa))
  75         fc = f(C)
  76
  77         if fc * fb < 0:
  78             A, fa = B, fb
  79         else:
  80             fa /= 2
  81
  82         B, fb = C, fc
  83
  84         # DEBUG
  85         # log.debug("A={}, B={}, C={}, fA={}, fB={}, fC={}".format(A, B, C, fa, fb, fc))
  86
  87     return math.e ** (A / 2)
  88
  89
  90 def rate(player, opponents, results):
  91     """
  92     Calculate the ratings improvement for a given player, provided their opponents and
  93     corresponding results versus them.
  94     """
  95     if len(opponents) == 0 or len(results) == 0:
  96         return player
  97
  98     p_g2 = player.to_glicko2()
  99
 100     gs = []
 101     es = []
 102     for i in range(len(opponents)):
 103         o_g2 = opponents[i].to_glicko2()
 104         gs.append(calc_g(o_g2.phi))
 105         es.append(calc_e(p_g2.mu, o_g2.mu, o_g2.phi))
 106
 107         # DEBUG
 108         # log.debug("j={} muj={} phij={} g={} e={} s={}"
 109                   # .format(i+1, o_g2.mu, o_g2.phi, gs[i], es[i], results[i]))
 110
 111     v = calc_v(gs, es)
 112     delta = calc_delta(v, gs, es, results)
 113     sigma_bar = calc_sigma_bar(p_g2.sigma, delta, p_g2.phi, v)
 114
 115     phi_tmp = math.sqrt(p_g2.phi ** 2 + sigma_bar ** 2)
 116     phi_bar = 1/math.sqrt((1/phi_tmp**2) + (1/v))
 117
 118     sum_terms = 0.0
 119     for i in range(len(opponents)):
 120         sum_terms += gs[i] * (results[i] - es[i])
 121
 122     mu_bar = p_g2.mu + phi_bar**2 * sum_terms
 123
 124     new_rating = PlayerGlicko(player.player_id, player.game_type_cd, player.category, mu_bar,
 125                               phi_bar, sigma_bar).from_glicko2()
 126
 127     # DEBUG
 128     # log.debug("v={}".format(v))
 129     # log.debug("delta={}".format(delta))
 130     # log.debug("sigma_temp={}".format(sigma_temp))
 131     # log.debug("sigma_bar={}".format(sigma_bar))
 132     # log.debug("phi_bar={}".format(phi_bar))
 133     # log.debug("mu_bar={}".format(mu_bar))
 134     # log.debug("new_rating: {} {} {}".format(new_rating.mu, new_rating.phi, new_rating.sigma))
 135
 136     return new_rating
 137
 138
 139 class KReduction:
 140     """
 141     Scale the points gained or lost for players based on time played in the given game.
 142     """
 143     def __init__(self, full_time=600, min_time=120, min_ratio=0.5):
 144         # full time is the time played to count the player in a game
 145         self.full_time = full_time
 146
 147         # min time is the time played to count the player at all in a game
 148         self.min_time = min_time
 149
 150         # min_ratio is the ratio of the game's time to be played to be counted fully (provided
 151         # they went past `full_time` and `min_time` above.
 152         self.min_ratio = min_ratio
 153
 154     def eval(self, my_time, match_time):
 155         # kick out players who didn't play enough of the match
 156         if my_time < self.min_time:
 157             return 0.0
 158
 159         if my_time < self.min_ratio * match_time:
 160             return 0.0
 161
 162         # scale based on time played versus what is defined as `full_time`
 163         if my_time < self.full_time:
 164             k = my_time / float(self.full_time)
 165         else:
 166             k = 1.0
 167
 168         return k
 169
 170
 171 # Parameters for reduction of points
 172 KREDUCTION = KReduction()
 173
 174
 175 class GlickoWIP(object):
 176     """ A work-in-progress Glicko value. """
 177     def __init__(self, pg):
 178         """
 179         Initialize a GlickoWIP instance.
 180         :param pg: the player's PlayerGlicko record.
 181         """
 182         # the player's current (or base) PlayerGlicko record
 183         self.pg = pg
 184
 185         # the list of k factors for each game in the ranking period
 186         self.k_factors = []
 187
 188         # the list of ping factors for each game in the ranking period
 189         self.ping_factors = []
 190
 191         # the list of opponents (PlayerGlicko or PlayerGlickoBase) in the ranking period
 192         self.opponents = []
 193
 194         # the list of results for those games in the ranking period
 195         self.results = []
 196
 197
 198 class GlickoProcessor(object):
 199     """
 200     Processes an arbitrary list games using the Glicko2 algorithm.
 201     """
 202     def __init__(self, session):
 203         """
 204         Create a GlickoProcessor instance.
 205
 206         :param session: the SQLAlchemy session to use for fetching/saving records.
 207         """
 208         self.session = session
 209         self.wips = {}
 210
 211     def _pingratio(self, pi, pj):
 212         """
 213         Calculate the ping differences between the two players, but only if both have them.
 214
 215         :param pi: the latency of player I
 216         :param pj: the latency of player J
 217         :return: float
 218         """
 219         if pi is None or pj is None or pi < 0 or pj < 0:
 220             # default to a draw
 221             return 0.5
 222
 223         else:
 224             return float(pi)/(pi+pj)
 225
 226     def _load_game(self, game_id):
 227         try:
 228             game = self.session.query(Game).filter(Game.game_id==game_id).one()
 229             return game
 230         except Exception as e:
 231             log.error("Game ID {} not found.".format(game_id))
 232             log.error(e)
 233             raise e
 234
 235     def _load_pgstats(self, game):
 236         """
 237         Retrieve the game stats from the database for the game in question.
 238
 239         :param game: the game record whose player stats will be retrieved
 240         :return: list of PlayerGameStat
 241         """
 242         try:
 243             pgstats_raw = self.session.query(PlayerGameStat)\
 244                 .filter(PlayerGameStat.game_id==game.game_id)\
 245                 .filter(PlayerGameStat.player_id > 2)\
 246                 .all()
 247
 248             return pgstats_raw
 249
 250         except Exception as e:
 251             log.error("Error fetching player_game_stat records for game {}".format(game.game_id))
 252             log.error(e)
 253             raise e
 254
 255     def _filter_pgstats(self, game, pgstats_raw):
 256         """
 257         Filter the raw game stats so that all of them are Glicko-eligible.
 258
 259         :param pgstats_raw: the list of raw PlayerGameStat
 260         :return: list of PlayerGameStat
 261         """
 262         pgstats = []
 263         for pgstat in pgstats_raw:
 264             # ensure warmup isn't included in the pgstat records
 265             if pgstat.alivetime > game.duration:
 266                 pgstat.alivetime = game.duration
 267
 268             # ensure players played enough of the match to be included
 269             k = KREDUCTION.eval(pgstat.alivetime.total_seconds(), game.duration.total_seconds())
 270             if k <= 0.0:
 271                 continue
 272             elif pgstat.player_id <= 2:
 273                 continue
 274             else:
 275                 pgstats.append(pgstat)
 276
 277         return pgstats
 278
 279     def _load_glicko_wip(self, player_id, game_type_cd, category):
 280         """
 281         Retrieve a PlayerGlicko record from the database or local cache.
 282
 283         :param player_id: the player ID to fetch
 284         :param game_type_cd: the game type code
 285         :param category: the category of glicko to retrieve
 286         :return: PlayerGlicko
 287         """
 288         if (player_id, game_type_cd, category) in self.wips:
 289             return self.wips[(player_id, game_type_cd, category)]
 290
 291         try:
 292             pg = self.session.query(PlayerGlicko)\
 293                      .filter(PlayerGlicko.player_id==player_id)\
 294                      .filter(PlayerGlicko.game_type_cd==game_type_cd)\
 295                      .filter(PlayerGlicko.category==category)\
 296                      .one()
 297
 298         except:
 299             pg = PlayerGlicko(player_id, game_type_cd, category)
 300
 301         # cache this in the wips dict
 302         wip = GlickoWIP(pg)
 303         self.wips[(player_id, game_type_cd, category)] = wip
 304
 305         return wip
 306
 307     def load(self, game_id, game=None, pgstats=None):
 308         """
 309         Load all of the needed information from the database. Compute results for each player pair.
 310         """
 311         if game is None:
 312             game = self._load_game(game_id)
 313
 314         if pgstats is None:
 315             pgstats = self._load_pgstats(game)
 316
 317         pgstats = self._filter_pgstats(game, pgstats)
 318
 319         game_type_cd = game.game_type_cd
 320         category = game.category
 321
 322         # calculate results:
 323         #   wipi/j => work in progress record for player i/j
 324         #   ki/j   => k reduction value for player i/j
 325         #   si/j   => score per second for player i/j
 326         #   pi/j   => ping ratio for player i/j
 327         for i in xrange(0, len(pgstats)):
 328             wipi = self._load_glicko_wip(pgstats[i].player_id, game_type_cd, category)
 329             ki = KREDUCTION.eval(pgstats[i].alivetime.total_seconds(),
 330                                  game.duration.total_seconds())
 331             si = pgstats[i].score/float(game.duration.total_seconds())
 332
 333             for j in xrange(i+1, len(pgstats)):
 334                 # ping factor is opponent-specific
 335                 pi = self._pingratio(pgstats[i].avg_latency, pgstats[j].avg_latency)
 336                 pj = 1.0 - pi
 337
 338                 wipj = self._load_glicko_wip(pgstats[j].player_id, game_type_cd, category)
 339                 kj = KREDUCTION.eval(pgstats[j].alivetime.total_seconds(),
 340                                      game.duration.total_seconds())
 341                 sj = pgstats[j].score/float(game.duration.seconds)
 342
 343                 # normalize scores
 344                 ofs = min(0.0, si, sj)
 345                 si -= ofs
 346                 sj -= ofs
 347                 if si + sj == 0:
 348                     si, sj = 1, 1 # a draw
 349
 350                 scorefactor_i = si / float(si + sj)
 351                 scorefactor_j = 1.0 - si
 352
 353                 wipi.k_factors.append(ki)
 354                 wipi.ping_factors.append(pi)
 355                 wipi.opponents.append(wipj.pg)
 356                 wipi.results.append(scorefactor_i)
 357
 358                 wipj.k_factors.append(kj)
 359                 wipj.ping_factors.append(pj)
 360                 wipj.opponents.append(wipi.pg)
 361                 wipj.results.append(scorefactor_j)
 362
 363     def process(self):
 364         """
 365         Calculate the Glicko2 ratings, deviations, and volatility updates for the records loaded.
 366         """
 367         for wip in self.wips.values():
 368             new_pg = rate(wip.pg, wip.opponents, wip.results)
 369
 370             log.debug("New rating for player {} before factors: mu={} phi={} sigma={}"
 371                       .format(new_pg.player_id, new_pg.mu, new_pg.phi, new_pg.sigma))
 372
 373             avg_k_factor = sum(wip.k_factors)/len(wip.k_factors)
 374             avg_ping_factor = LATENCY_TREND_FACTOR * sum(wip.ping_factors)/len(wip.ping_factors)
 375
 376             points_delta = (new_pg.mu - wip.pg.mu) * avg_k_factor * avg_ping_factor
 377
 378             wip.pg.mu += points_delta
 379             wip.pg.phi = new_pg.phi
 380             wip.pg.sigma = new_pg.sigma
 381
 382             log.debug("New rating for player {} after factors: mu={} phi={} sigma={}"
 383                       .format(wip.pg.player_id, wip.pg.mu, wip.pg.phi, wip.pg.sigma))
 384
 385     def save(self):
 386         """
 387         Put all changed PlayerElo and PlayerGameStat instances into the
 388         session to be updated or inserted upon commit.
 389         """
 390         for wip in self.wips.values():
 391             self.session.add(wip.pg)
 392
 393         self.session.commit()
 394
 395
 396 def main():
 397     # the example in the actual Glicko2 paper, for verification purposes
 398     pA = PlayerGlicko(1, "duel", mu=1500, phi=200)
 399     pB = PlayerGlicko(2, "duel", mu=1400, phi=30)
 400     pC = PlayerGlicko(3, "duel", mu=1550, phi=100)
 401     pD = PlayerGlicko(4, "duel", mu=1700, phi=300)
 402
 403     opponents = [pB, pC, pD]
 404     results = [1, 0, 0]
 405
 406     rate(pA, opponents, results)
 407
 408
 409 if __name__ == "__main__":
 410      sys.exit(main())