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
  17 def calc_g(phi):
  18     return 1 / math.sqrt(1 + (3 * phi ** 2) / (math.pi ** 2))
  19
  20
  21 def calc_e(mu, mu_j, phi_j):
  22     return 1. / (1 + math.exp(-calc_g(phi_j) * (mu - mu_j)))
  23
  24
  25 def calc_v(gs, es):
  26     """ Estimated variance of the team or player's ratings based only on game outcomes. """
  27     total = 0.0
  28     for i in range(len(gs)):
  29         total += (gs[i] ** 2) * es[i] * (1-es[i])
  30
  31     return 1. / total
  32
  33
  34 def calc_delta(v, gs, es, results):
  35     """
  36     Compute the estimated improvement in rating by comparing the pre-period rating to the
  37     performance rating based only on game outcomes.
  38     """
  39     total = 0.0
  40     for i in range(len(gs)):
  41         total += gs[i] * (results[i] - es[i])
  42
  43     return v * total
  44
  45
  46 def calc_sigma_bar(sigma, delta, phi, v, tau=TAU):
  47     """ Compute the new volatility. """
  48     epsilon = 0.000001
  49     A = a = math.log(sigma**2)
  50
  51     # pre-compute some terms
  52     delta_sq = delta ** 2
  53     phi_sq = phi ** 2
  54
  55     def f(x):
  56         e_up_x = math.e ** x
  57         term_a = (e_up_x * (delta_sq - phi_sq - v - e_up_x)) / (2 * (phi_sq + v + e_up_x) ** 2)
  58         term_b = (x - a) / tau ** 2
  59         return term_a - term_b
  60
  61     if delta_sq > (phi_sq + v):
  62         B = math.log(delta_sq - phi_sq - v)
  63     else:
  64         k = 1
  65         while f(a - k * tau) < 0:
  66             k += 1
  67         B = a - k * tau
  68
  69     fa, fb = f(A), f(B)
  70     while abs(B - A) > epsilon:
  71         C = A + (A - B) * (fa / (fb - fa))
  72         fc = f(C)
  73
  74         if fc * fb < 0:
  75             A, fa = B, fb
  76         else:
  77             fa /= 2
  78
  79         B, fb = C, fc
  80
  81         # DEBUG
  82         # log.debug("A={}, B={}, C={}, fA={}, fB={}, fC={}".format(A, B, C, fa, fb, fc))
  83
  84     return math.e ** (A / 2)
  85
  86
  87 def rate(player, opponents, results):
  88     """
  89     Calculate the ratings improvement for a given player, provided their opponents and
  90     corresponding results versus them.
  91     """
  92     p_g2 = player.to_glicko2()
  93
  94     gs = []
  95     es = []
  96     for i in range(len(opponents)):
  97         o_g2 = opponents[i].to_glicko2()
  98         gs.append(calc_g(o_g2.phi))
  99         es.append(calc_e(p_g2.mu, o_g2.mu, o_g2.phi))
 100
 101         # DEBUG
 102         # log.debug("j={} muj={} phij={} g={} e={} s={}"
 103                   # .format(i+1, o_g2.mu, o_g2.phi, gs[i], es[i], results[i]))
 104
 105     v = calc_v(gs, es)
 106     delta = calc_delta(v, gs, es, results)
 107     sigma_bar = calc_sigma_bar(p_g2.sigma, delta, p_g2.phi, v)
 108
 109     phi_tmp = math.sqrt(p_g2.phi ** 2 + sigma_bar ** 2)
 110     phi_bar = 1/math.sqrt((1/phi_tmp**2) + (1/v))
 111
 112     sum_terms = 0.0
 113     for i in range(len(opponents)):
 114         sum_terms += gs[i] * (results[i] - es[i])
 115
 116     mu_bar = p_g2.mu + phi_bar**2 * sum_terms
 117
 118     new_rating = PlayerGlicko(player.player_id, player.game_type_cd, player.category, mu_bar,
 119                               phi_bar, sigma_bar).from_glicko2()
 120
 121     # DEBUG
 122     # log.debug("v={}".format(v))
 123     # log.debug("delta={}".format(delta))
 124     # log.debug("sigma_temp={}".format(sigma_temp))
 125     # log.debug("sigma_bar={}".format(sigma_bar))
 126     # log.debug("phi_bar={}".format(phi_bar))
 127     # log.debug("mu_bar={}".format(mu_bar))
 128     # log.debug("new_rating: {} {} {}".format(new_rating.mu, new_rating.phi, new_rating.sigma))
 129
 130     return new_rating
 131
 132
 133 class KReduction:
 134     """
 135     Scale the points gained or lost for players based on time played in the given game.
 136     """
 137     def __init__(self, full_time=600, min_time=120, min_ratio=0.5):
 138         # full time is the time played to count the player in a game
 139         self.full_time = full_time
 140
 141         # min time is the time played to count the player at all in a game
 142         self.min_time = min_time
 143
 144         # min_ratio is the ratio of the game's time to be played to be counted fully (provided
 145         # they went past `full_time` and `min_time` above.
 146         self.min_ratio = min_ratio
 147
 148     def eval(self, my_time, match_time):
 149         # kick out players who didn't play enough of the match
 150         if my_time < self.min_time:
 151             return 0.0
 152
 153         if my_time < self.min_ratio * match_time:
 154             return 0.0
 155
 156         # scale based on time played versus what is defined as `full_time`
 157         if my_time < self.full_time:
 158             k = my_time / float(self.full_time)
 159         else:
 160             k = 1.0
 161
 162         return k
 163
 164
 165 # Parameters for reduction of points
 166 KREDUCTION = KReduction()
 167
 168
 169 class GlickoWIP(object):
 170     """ A work-in-progress Glicko value. """
 171     def __init__(self, pg):
 172         """
 173         Initialize a GlickoWIP instance.
 174         :param pg: the player's PlayerGlicko record.
 175         """
 176         # the player's current (or base) PlayerGlicko record
 177         self.pg = pg
 178
 179         # the list of k factors for each game in the ranking period
 180         self.ks = []
 181
 182         # the list of opponents (PlayerGlicko or PlayerGlickoBase) in the ranking period
 183         self.opponents = []
 184
 185         # the list of results for those games in the ranking period
 186         self.results = []
 187
 188
 189 class GlickoProcessor(object):
 190     """
 191     Processes the given list games using the Glicko2 algorithm.
 192     """
 193     def __init__(self, session):
 194         """
 195         Create a GlickoProcessor instance.
 196
 197         :param session: the SQLAlchemy session to use for fetching/saving records.
 198         :param game_ids: the list of game_ids that need to be processed.
 199         """
 200         self.session = session
 201         self.wips = {}
 202
 203     def scorefactor(self, si, sj, game_type_cd):
 204         """
 205         Calculate the real scorefactor of the game. This is how players
 206         actually performed, which is compared to their expected performance.
 207
 208         :param si: the score per second of player I
 209         :param sj: the score per second of player J
 210         :param game_type_cd: the game type of the game in question
 211         :return: float
 212         """
 213         scorefactor_real = si / float(si + sj)
 214
 215         # duels are done traditionally - a win nets
 216         # full points, not the score factor
 217         if game_type_cd == 'duel':
 218             # player i won
 219             if scorefactor_real > 0.5:
 220                 scorefactor_real = 1.0
 221             # player j won
 222             elif scorefactor_real < 0.5:
 223                 scorefactor_real = 0.0
 224             # nothing to do here for draws
 225
 226         return scorefactor_real
 227
 228     def pingfactor(self, pi, pj):
 229         """
 230         Calculate the ping differences between the two players, but only if both have them.
 231
 232         :param pi: the latency of player I
 233         :param pj: the latency of player J
 234         :return: float
 235         """
 236         if pi is None or pj is None or pi < 0 or pj < 0:
 237             # default to a draw
 238             return 0.5
 239
 240         else:
 241             return float(pi)/(pi+pj)
 242
 243     def load(self, game_id):
 244         """
 245         Load all of the needed information from the database.
 246         """
 247         try:
 248             game = self.session.query(Game).filter(Game.game_id==game_id).one()
 249         except:
 250             log.error("Game ID {} not found.".format(game_id))
 251             return
 252
 253         try:
 254             pgstats_raw = self.session.query(PlayerGameStat)\
 255                 .filter(PlayerGameStat.game_id==game_id)\
 256                 .filter(PlayerGameStat.player_id > 2)\
 257                 .all()
 258
 259             # ensure warmup isn't included in the pgstat records
 260             for pgstat in pgstats_raw:
 261                 if pgstat.alivetime > game.duration:
 262                     pgstat.alivetime = game.duration
 263         except:
 264             log.error("Error fetching player_game_stat records for game {}".format(self.game_id))
 265             return
 266
 267     def process(self):
 268         """
 269         Calculate the Glicko2 ratings, deviations, and volatility updates for the records loaded.
 270         :return: bool
 271         """
 272         pass
 273
 274     def save(self, session):
 275         """
 276         Put all changed PlayerElo and PlayerGameStat instances into the
 277         session to be updated or inserted upon commit.
 278         """
 279         pass
 280
 281
 282 def main():
 283     # the example in the actual Glicko2 paper, for verification purposes
 284     pA = PlayerGlicko(1, "duel", mu=1500, phi=200)
 285     pB = PlayerGlicko(2, "duel", mu=1400, phi=30)
 286     pC = PlayerGlicko(3, "duel", mu=1550, phi=100)
 287     pD = PlayerGlicko(4, "duel", mu=1700, phi=300)
 288
 289     opponents = [pB, pC, pD]
 290     results = [1, 0, 0]
 291
 292     rate(pA, opponents, results)
 293
 294
 295 if __name__ == "__main__":
 296      sys.exit(main())