From 3eb00a060e60c75b1b32eeb48478555354ad50e9 Mon Sep 17 00:00:00 2001 From: Ant Zucaro Date: Fri, 6 Jan 2012 16:36:09 -0500 Subject: [PATCH] Initial debug version of elo ranking. --- xonstat/elo.py | 99 ++++++++++++++++++++++++++++++++ xonstat/models.py | 111 ++++++++++++++++++++++++++++++++++++ xonstat/views/submission.py | 17 +++--- 3 files changed, 220 insertions(+), 7 deletions(-) create mode 100755 xonstat/elo.py diff --git a/xonstat/elo.py b/xonstat/elo.py new file mode 100755 index 0000000..4ba3553 --- /dev/null +++ b/xonstat/elo.py @@ -0,0 +1,99 @@ +import sys +import math +import random + +class EloParms: + def __init__(self, global_K = 15, initial = 100, floor = 100, logdistancefactor = math.log(10)/float(400), maxlogdistance = math.log(10)): + self.global_K = global_K + self.initial = initial + self.floor = floor + self.logdistancefactor = logdistancefactor + self.maxlogdistance = maxlogdistance + + +class KReduction: + def __init__(self, fulltime, mintime, minratio, games_min, games_max, games_factor): + self.fulltime = fulltime + self.mintime = mintime + self.minratio = minratio + self.games_min = games_min + self.games_max = games_max + self.games_factor = games_factor + + def eval(self, mygames, mytime, matchtime): + if mytime < self.mintime: + return 0 + if mytime < self.minratio * matchtime: + return 0 + if mytime < self.fulltime: + k = mytime / float(self.fulltime) + else: + k = 1.0 + if mygames >= self.games_max: + k *= self.games_factor + elif mygames > self.games_min: + k *= 1.0 - (1.0 - self.games_factor) * (mygames - self.games_min) / float(self.games_max - self.games_min) + return k + + +# For team games where multiple scores and elos are at play, the elos +# must be adjusted according to their strength relative to the player +# in the next-lowest scoreboard position. +def update(elos, ep): + for x in elos: + if x.elo == None: + x.elo = ep.initial + x.eloadjust = 0 + if len(elos) < 2: + return elos + for i in xrange(0, len(elos)): + ei = elos[i] + for j in xrange(i+1, len(elos)): + ej = elos[j] + si = ei.score + sj = ej.score + + # normalize scores + ofs = min(0, si, sj) + si -= ofs + sj -= ofs + if si + sj == 0: + si, sj = 1, 1 # a draw + + # real score factor + scorefactor_real = si / float(si + sj) + + # estimated score factor by elo + elodiff = min(ep.maxlogdistance, max(-ep.maxlogdistance, (ei.elo - ej.elo) * ep.logdistancefactor)) + scorefactor_elo = 1 / (1 + math.exp(-elodiff)) + + # how much adjustment is good? + # scorefactor(elodiff) = 1 / (1 + e^(-elodiff * logdistancefactor)) + # elodiff(scorefactor) = -ln(1/scorefactor - 1) / logdistancefactor + # elodiff'(scorefactor) = 1 / ((scorefactor) (1 - scorefactor) logdistancefactor) + # elodiff'(scorefactor) >= 4 / logdistancefactor + + # adjust'(scorefactor) = K1 + K2 + + # so we want: + # K1 + K2 <= 4 / logdistancefactor <= elodiff'(scorefactor) + # as we then don't overcompensate + + adjustment = scorefactor_real - scorefactor_elo + ei.eloadjust += adjustment + ej.eloadjust -= adjustment + for x in elos: + x.elo = max(x.elo + x.eloadjust * x.k * ep.global_K / float(len(elos) - 1), ep.floor) + x.games += 1 + return elos + + +# parameters for K reduction +# this may be touched even if the DB already exists +KREDUCTION = KReduction(600, 120, 0.5, 0, 32, 0.2) + +# parameters for chess elo +# only global_K may be touched even if the DB already exists +# we start at K=200, and fall to K=40 over the first 20 games +ELOPARMS = EloParms(global_K = 200) + diff --git a/xonstat/models.py b/xonstat/models.py index f7ec2fb..8e47e74 100755 --- a/xonstat/models.py +++ b/xonstat/models.py @@ -1,10 +1,15 @@ +import logging import sqlalchemy +from datetime import timedelta from sqlalchemy.orm import mapper from sqlalchemy.orm import scoped_session from sqlalchemy.orm import sessionmaker from sqlalchemy.ext.declarative import declarative_base +from xonstat.elo import KREDUCTION, ELOPARMS from xonstat.util import strip_colors, html_colors, pretty_date +log = logging.getLogger(__name__) + DBSession = scoped_session(sessionmaker()) Base = declarative_base() @@ -77,6 +82,97 @@ class Game(object): def fuzzy_date(self): return pretty_date(self.start_dt) + def process_elos(self, session, game_type_cd=None): + if game_type_cd is None: + game_type_cd = self.game_type_cd + + scores = {} + alivetimes = {} + for (p,s,a) in session.query(PlayerGameStat.player_id, + PlayerGameStat.score, PlayerGameStat.alivetime).\ + filter(PlayerGameStat.game_id==self.game_id).\ + filter(PlayerGameStat.alivetime > timedelta(seconds=0)).\ + filter(PlayerGameStat.player_id > 2).\ + all(): + scores[p] = s + alivetimes[p] = a.seconds + + player_ids = scores.keys() + + elos = {} + for e in session.query(PlayerElo).\ + filter(PlayerElo.player_id.in_(player_ids)).\ + filter(PlayerElo.game_type_cd==game_type_cd).all(): + elos[e.player_id] = e + + # ensure that all player_ids have an elo record + for pid in player_ids: + if pid not in elos.keys(): + elos[pid] = PlayerElo(pid, game_type_cd) + + for pid in player_ids: + elos[pid].k = KREDUCTION.eval(elos[pid].games, alivetimes[pid], 0) + + elos = self.update_elos(elos, scores, ELOPARMS) + + # add the elos to the session for committing + for e in elos: + session.add(elos[e]) + + # TODO: duels are also logged as DM for elo purposes + + def update_elos(self, elos, scores, ep): + eloadjust = {} + for pid in elos.keys(): + eloadjust[pid] = 0 + + # need to turn this into a list to iterate based + # on numerical index + elos = list(elos) + + if len(elos) < 2: + return elos + for i in xrange(0, len(elos)): + ei = elos[i] + for j in xrange(i+1, len(elos)): + ej = elos[j] + si = scores[ei.player_id] + sj = scores[ej.player_id] + + # normalize scores + ofs = min(0, si, sj) + si -= ofs + sj -= ofs + if si + sj == 0: + si, sj = 1, 1 # a draw + + # real score factor + scorefactor_real = si / float(si + sj) + + # estimated score factor by elo + elodiff = min(ep.maxlogdistance, max(-ep.maxlogdistance, (ei.elo - ej.elo) * ep.logdistancefactor)) + scorefactor_elo = 1 / (1 + math.exp(-elodiff)) + + # how much adjustment is good? + # scorefactor(elodiff) = 1 / (1 + e^(-elodiff * logdistancefactor)) + # elodiff(scorefactor) = -ln(1/scorefactor - 1) / logdistancefactor + # elodiff'(scorefactor) = 1 / ((scorefactor) (1 - scorefactor) logdistancefactor) + # elodiff'(scorefactor) >= 4 / logdistancefactor + + # adjust'(scorefactor) = K1 + K2 + + # so we want: + # K1 + K2 <= 4 / logdistancefactor <= elodiff'(scorefactor) + # as we then don't overcompensate + + adjustment = scorefactor_real - scorefactor_elo + eloadjust[ei.player_id] += adjustment + eloadjust[ei.player_id] -= adjustment + for e in elos: + e.elo = max(e.elo + eloadjust[e.player_id] * e.k * ep.global_K / float(len(elos) - 1), ep.floor) + e.games += 1 + return elos + class PlayerGameStat(object): def __init__(self, player_game_stat_id=None, create_dt=None): @@ -143,6 +239,19 @@ class PlayerNick(object): return "" % (self.player_id, self.stripped_nick) +class PlayerElo(object): + def __init__(self, player_id=None, game_type_cd=None): + self.player_id = player_id + self.game_type_cd = game_type_cd + self.elo = 0 + self.k = 0.0 + self.score = 0 + + def __repr__(self): + return "" % (self.player_id, self.game_type_cd, + self.elo) + + def initialize_db(engine=None): DBSession.configure(bind=engine) Base.metadata.bind = engine @@ -163,6 +272,7 @@ def initialize_db(engine=None): player_weapon_stats_table = MetaData.tables['player_weapon_stats'] servers_table = MetaData.tables['servers'] player_nicks_table = MetaData.tables['player_nicks'] + player_elos_table = MetaData.tables['player_elos'] # now map the tables and the objects together mapper(PlayerAchievement, achievements_table) @@ -177,3 +287,4 @@ def initialize_db(engine=None): mapper(PlayerWeaponStat, player_weapon_stats_table) mapper(Server, servers_table) mapper(PlayerNick, player_nicks_table) + mapper(PlayerElo, player_elos_table) diff --git a/xonstat/views/submission.py b/xonstat/views/submission.py index bbdac59..ec0f57b 100755 --- a/xonstat/views/submission.py +++ b/xonstat/views/submission.py @@ -544,9 +544,9 @@ def stats_submit(request): "----- END REQUEST BODY -----\n\n") (idfp, status) = verify_request(request) - if not idfp: - log.debug("ERROR: Unverified request") - raise pyramid.httpexceptions.HTTPUnauthorized("Unverified request") + #if not idfp: + #log.debug("ERROR: Unverified request") + #raise pyramid.httpexceptions.HTTPUnauthorized("Unverified request") (game_meta, players) = parse_body(request) @@ -562,9 +562,9 @@ def stats_submit(request): log.debug("ERROR: Not enough real players") raise pyramid.httpexceptions.HTTPOk("OK") - if is_blank_game(players): - log.debug("ERROR: Blank game") - raise pyramid.httpexceptions.HTTPOk("OK") + #if is_blank_game(players): + #log.debug("ERROR: Blank game") + #raise pyramid.httpexceptions.HTTPOk("OK") # FIXME: if we have two players and game type is 'dm', # change this into a 'duel' gametype. This should be @@ -605,9 +605,12 @@ def stats_submit(request): create_player_stats(session=session, player=player, game=game, player_events=player_events) + # update elos + game.process_elos(session) + session.commit() log.debug('Success! Stats recorded.') return Response('200 OK') except Exception as e: session.rollback() - return e + raise e -- 2.39.2