X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=xonstat%2Fglicko.py;h=85d2641c80f7575e00479ff3710f81b046aaf402;hb=e26be81d2e0ce455c83f432527c73de63b464187;hp=9f63675a80966c8f014da6a3a44a5f2d3b241bed;hpb=07404f81356ac938328932bdda2ea01894b09fda;p=xonotic%2Fxonstat.git diff --git a/xonstat/glicko.py b/xonstat/glicko.py index 9f63675..85d2641 100644 --- a/xonstat/glicko.py +++ b/xonstat/glicko.py @@ -2,50 +2,19 @@ import logging import math import sys +from xonstat.models import PlayerGlicko, Game, PlayerGameStat + log = logging.getLogger(__name__) # DEBUG # log.addHandler(logging.StreamHandler()) # log.setLevel(logging.DEBUG) -# the default initial rating value -MU = 1500 - -# the default ratings deviation value -PHI = 350 - -# the default volatility value -SIGMA = 0.06 - # the default system volatility constant -#TAU = 0.3 -TAU = 0.5 - -# the ratio to convert from/to glicko2 -GLICKO2_SCALE = 173.7178 +TAU = 0.3 - -class PlayerGlicko(object): - def __init__(self, mu=MU, phi=PHI, sigma=SIGMA): - self.mu = mu - self.phi = phi - self.sigma = sigma - - def to_glicko2(self): - """ Convert a rating to the Glicko2 scale. """ - return PlayerGlicko( - mu=(self.mu - MU) / GLICKO2_SCALE, - phi=self.phi / GLICKO2_SCALE, - sigma=self.sigma - ) - - def from_glicko2(self): - """ Convert a rating to the original Glicko scale. """ - return PlayerGlicko( - mu=self.mu * GLICKO2_SCALE + MU, - phi=self.phi * GLICKO2_SCALE, - sigma=self.sigma - ) +# how much ping influences results +LATENCY_TREND_FACTOR = 0.2 def calc_g(phi): @@ -112,7 +81,8 @@ def calc_sigma_bar(sigma, delta, phi, v, tau=TAU): B, fb = C, fc - log.debug("A={}, B={}, C={}, fA={}, fB={}, fC={}".format(A, B, C, fa, fb, fc)) + # DEBUG + # log.debug("A={}, B={}, C={}, fA={}, fB={}, fC={}".format(A, B, C, fa, fb, fc)) return math.e ** (A / 2) @@ -148,7 +118,8 @@ def rate(player, opponents, results): mu_bar = p_g2.mu + phi_bar**2 * sum_terms - new_rating = PlayerGlicko(mu_bar, phi_bar, sigma_bar).from_glicko2() + new_rating = PlayerGlicko(player.player_id, player.game_type_cd, player.category, mu_bar, + phi_bar, sigma_bar).from_glicko2() # DEBUG # log.debug("v={}".format(v)) @@ -162,11 +133,249 @@ def rate(player, opponents, results): return new_rating +class KReduction: + """ + Scale the points gained or lost for players based on time played in the given game. + """ + def __init__(self, full_time=600, min_time=120, min_ratio=0.5): + # full time is the time played to count the player in a game + self.full_time = full_time + + # min time is the time played to count the player at all in a game + self.min_time = min_time + + # min_ratio is the ratio of the game's time to be played to be counted fully (provided + # they went past `full_time` and `min_time` above. + self.min_ratio = min_ratio + + def eval(self, my_time, match_time): + # kick out players who didn't play enough of the match + if my_time < self.min_time: + return 0.0 + + if my_time < self.min_ratio * match_time: + return 0.0 + + # scale based on time played versus what is defined as `full_time` + if my_time < self.full_time: + k = my_time / float(self.full_time) + else: + k = 1.0 + + return k + + +# Parameters for reduction of points +KREDUCTION = KReduction() + + +class GlickoWIP(object): + """ A work-in-progress Glicko value. """ + def __init__(self, pg): + """ + Initialize a GlickoWIP instance. + :param pg: the player's PlayerGlicko record. + """ + # the player's current (or base) PlayerGlicko record + self.pg = pg + + # the list of k factors for each game in the ranking period + self.k_factors = [] + + # the list of ping factors for each game in the ranking period + self.ping_factors = [] + + # the list of opponents (PlayerGlicko or PlayerGlickoBase) in the ranking period + self.opponents = [] + + # the list of results for those games in the ranking period + self.results = [] + + +class GlickoProcessor(object): + """ + Processes an arbitrary list games using the Glicko2 algorithm. + """ + def __init__(self, session): + """ + Create a GlickoProcessor instance. + + :param session: the SQLAlchemy session to use for fetching/saving records. + """ + self.session = session + self.wips = {} + + def _pingratio(self, pi, pj): + """ + Calculate the ping differences between the two players, but only if both have them. + + :param pi: the latency of player I + :param pj: the latency of player J + :return: float + """ + if pi is None or pj is None or pi < 0 or pj < 0: + # default to a draw + return 0.5 + + else: + return float(pi)/(pi+pj) + + def _load_game(self, game_id): + try: + game = self.session.query(Game).filter(Game.game_id==game_id).one() + return game + except Exception as e: + log.error("Game ID {} not found.".format(game_id)) + log.error(e) + raise e + + def _load_pgstats(self, game): + """ + Retrieve the game stats from the database for the game in question. + + :param game: the game record whose player stats will be retrieved + :return: list of PlayerGameStat + """ + try: + pgstats_raw = self.session.query(PlayerGameStat)\ + .filter(PlayerGameStat.game_id==game.game_id)\ + .filter(PlayerGameStat.player_id > 2)\ + .all() + + except Exception as e: + log.error("Error fetching player_game_stat records for game {}".format(game.game_id)) + log.error(e) + raise e + + pgstats = [] + for pgstat in pgstats_raw: + # ensure warmup isn't included in the pgstat records + if pgstat.alivetime > game.duration: + pgstat.alivetime = game.duration + + # ensure players played enough of the match to be included + k = KREDUCTION.eval(pgstat.alivetime.total_seconds(), game.duration.total_seconds()) + if k <= 0.0: + continue + else: + pgstats.append(pgstat) + + return pgstats + + def _load_glicko_wip(self, player_id, game_type_cd, category): + """ + Retrieve a PlayerGlicko record from the database. + + :param player_id: the player ID to fetch + :param game_type_cd: the game type code + :param category: the category of glicko to retrieve + :return: PlayerGlicko + """ + if (player_id, game_type_cd, category) in self.wips: + return self.wips[(player_id, game_type_cd, category)] + + try: + pg = self.session.query(PlayerGlicko)\ + .filter(PlayerGlicko.player_id==player_id)\ + .filter(PlayerGlicko.game_type_cd==game_type_cd)\ + .filter(PlayerGlicko.category==category)\ + .one() + + except: + pg = PlayerGlicko(player_id, game_type_cd, category) + + # cache this in the wips dict + wip = GlickoWIP(pg) + self.wips[(player_id, game_type_cd, category)] = wip + + return wip + + def load(self, game_id): + """ + Load all of the needed information from the database. Compute results for each player pair. + """ + game = self._load_game(game_id) + pgstats = self._load_pgstats(game) + game_type_cd = game.game_type_cd + category = game.category + + # calculate results: + # wipi/j => work in progress record for player i/j + # ki/j => k reduction value for player i/j + # si/j => score per second for player i/j + # pi/j => ping ratio for player i/j + for i in xrange(0, len(pgstats)): + wipi = self._load_glicko_wip(pgstats[i].player_id, game_type_cd, category) + ki = KREDUCTION.eval(pgstats[i].alivetime.total_seconds(), + game.duration.total_seconds()) + si = pgstats[i].score/float(game.duration.total_seconds()) + + for j in xrange(i+1, len(pgstats)): + # ping factor is opponent-specific + pi = self._pingratio(pgstats[i].avg_latency, pgstats[j].avg_latency) + pj = 1.0 - pi + + wipj = self._load_glicko_wip(pgstats[j].player_id, game_type_cd, category) + kj = KREDUCTION.eval(pgstats[j].alivetime.total_seconds(), + game.duration.total_seconds()) + sj = pgstats[j].score/float(game.duration.seconds) + + # normalize scores + ofs = min(0.0, si, sj) + si -= ofs + sj -= ofs + if si + sj == 0: + si, sj = 1, 1 # a draw + + scorefactor_i = si / float(si + sj) + scorefactor_j = 1.0 - si + + wipi.k_factors.append(ki) + wipi.ping_factors.append(pi) + wipi.opponents.append(wipj.pg) + wipi.results.append(scorefactor_i) + + wipj.k_factors.append(kj) + wipj.ping_factors.append(pj) + wipj.opponents.append(wipi.pg) + wipj.results.append(scorefactor_j) + + def process(self): + """ + Calculate the Glicko2 ratings, deviations, and volatility updates for the records loaded. + """ + for wip in self.wips.values(): + new_pg = rate(wip.pg, wip.opponents, wip.results) + + log.debug("New rating for player {} before factors: mu={} phi={} sigma={}" + .format(pg.player_id, new_pg.mu, new_pg.phi, new_pg.sigma)) + + avg_k_factor = sum(wip.k_factors)/len(wip.k_factors) + avg_ping_factor = LATENCY_TREND_FACTOR * sum(wip.ping_factors)/len(wip.ping_factors) + + points_delta = (new_pg.mu - wip.pg.mu) * avg_k_factor * avg_ping_factor + + wip.pg.mu += points_delta + wip.pg.phi = new_pg.phi + wip.pg.sigma = new_pg.sigma + + log.debug("New rating for player {} after factors: mu={} phi={} sigma={}" + .format(wip.pg.player_id, wip.pg.mu, wip.pg.phi, wip.pg.sigma)) + + def save(self, session): + """ + Put all changed PlayerElo and PlayerGameStat instances into the + session to be updated or inserted upon commit. + """ + pass + + def main(): - pA = PlayerGlicko(mu=1500, phi=200) - pB = PlayerGlicko(mu=1400, phi=30) - pC = PlayerGlicko(mu=1550, phi=100) - pD = PlayerGlicko(mu=1700, phi=300) + # the example in the actual Glicko2 paper, for verification purposes + pA = PlayerGlicko(1, "duel", mu=1500, phi=200) + pB = PlayerGlicko(2, "duel", mu=1400, phi=30) + pC = PlayerGlicko(3, "duel", mu=1550, phi=100) + pD = PlayerGlicko(4, "duel", mu=1700, phi=300) opponents = [pB, pC, pD] results = [1, 0, 0] @@ -175,4 +384,4 @@ def main(): if __name__ == "__main__": - sys.exit(main()) + sys.exit(main())