portedTrueskill.js

// Generated by CoffeeScript 1.6.2
/*
Implements the player skill estimation algorithm from Herbrich et al.,
"TrueSkill(TM): A Bayesian Skill Rating System".
*/


(function() {
  var AdjustPlayers, BETA, DrawMargin, DrawProbability, EPSILON, Factor, GAMMA, Gaussian, INITIAL_MU, INITIAL_SIGMA, LikelihoodFactor, PriorFactor, SetParameters, SumFactor, TruncateFactor, Variable, Vdraw, Vwin, Wdraw, Wwin, cdf, genId, icdf, len, map, norm, pdf, pow, range, reduce, sqrt, sum, zip,
    __hasProp = {}.hasOwnProperty,
    __extends = function(child, parent) { for (var key in parent) { if (__hasProp.call(parent, key)) child[key] = parent[key]; } function ctor() { this.constructor = child; } ctor.prototype = parent.prototype; child.prototype = new ctor(); child.__super__ = parent.prototype; return child; };

  sqrt = Math.sqrt;

  pow = Math.pow;

  len = function(obj) {
    return obj.length;
  };

  range = function(max) {
    var _i, _results;

    return (function() {
      _results = [];
      for (var _i = 0; 0 <= max ? _i < max : _i > max; 0 <= max ? _i++ : _i--){ _results.push(_i); }
      return _results;
    }).apply(this);
  };

  reduce = function(list, iterator, memo) {
    var i, _i, _len;

    for (_i = 0, _len = list.length; _i < _len; _i++) {
      i = list[_i];
      memo = iterator(memo, i);
    }
    return memo;
  };

  sum = function(list) {
    return reduce(list, (function(i, j) {
      return i + j;
    }), 0);
  };

  map = function(list, func) {
    var i, _i, _len, _results;

    _results = [];
    for (_i = 0, _len = list.length; _i < _len; _i++) {
      i = list[_i];
      _results.push(func(i));
    }
    return _results;
  };

  zip = function(items) {
    var k, minLength, v, _i, _results;

    minLength = reduce((function() {
      var _results;

      _results = [];
      for (k in items) {
        v = items[k];
        _results.push(v);
      }
      return _results;
    })(), (function(memo, arr) {
      return Math.min(memo, arr.length);
    }), Number.MAX_VALUE);
    return map((function() {
      _results = [];
      for (var _i = 0; 0 <= minLength ? _i < minLength : _i > minLength; 0 <= minLength ? _i++ : _i--){ _results.push(_i); }
      return _results;
    }).apply(this), function(index) {
      var item, key, value;

      item = {};
      for (key in items) {
        value = items[key];
        item[key] = value[index];
      }
      return item;
    });
  };

  genId = (function() {
    var currId;

    currId = -1;
    return function() {
      currId++;
      return currId;
    };
  })();

  norm = require("free-gaussian");

  norm = norm(0, 1);

  pdf = function() {
    return norm.pdf.apply(norm, arguments);
  };

  cdf = function() {
    return norm.cdf.apply(norm, arguments);
  };

  icdf = function() {
    return norm.ppf.apply(norm, arguments);
  };

  Vwin = function(t, e) {
    return pdf(t - e) / cdf(t - e);
  };

  Wwin = function(t, e) {
    return Vwin(t, e) * (Vwin(t, e) + t - e);
  };

  Vdraw = function(t, e) {
    return (pdf(-e - t) - pdf(e - t)) / (cdf(e - t) - cdf(-e - t));
  };

  Wdraw = function(t, e) {
    return pow(Vdraw(t, e), 2) + ((e - t) * pdf(e - t) + (e + t) * pdf(e + t)) / (cdf(e - t) - cdf(-e - t));
  };

  Gaussian = (function() {
    /*
    Object representing a gaussian distribution.  Create as:
      new Gaussian({mu=..., sigma=...})
        or
      new Gaussian({pi=..., tau=...})
        or
      new Gaussian()    # gives 0 mean, infinite sigma
    */
    function Gaussian(parms) {
      if (parms == null) {
        parms = {};
      }
      if (parms.pi !== void 0) {
        this.pi = parms["pi"];
        this.tau = parms["tau"];
      } else if (parms.mu !== void 0) {
        this.pi = pow(parms["sigma"], -2);
        this.tau = this.pi * parms["mu"];
      } else {
        this.pi = 0;
        this.tau = 0;
      }
      if (isNaN(this.pi) || isNaN(this.tau)) {
        throw new Error("Gaussian parms can not be NaN");
      }
    }

    Gaussian.prototype.MuSigma = function() {
      /* Return the value of this object as a (mu, sigma) tuple.
      */
      if (this.pi === 0.0) {
        return [0, Infinity];
      } else {
        return [this.tau / this.pi, sqrt(1 / this.pi)];
      }
    };

    Gaussian.prototype.mul = function(other) {
      return new Gaussian({
        "pi": this.pi + other.pi,
        "tau": this.tau + other.tau
      });
    };

    Gaussian.prototype.div = function(other) {
      return new Gaussian({
        "pi": this.pi - other.pi,
        "tau": this.tau - other.tau
      });
    };

    return Gaussian;

  })();

  Variable = (function() {
    /* A variable node in the factor graph.
    */
    function Variable() {
      this.value = new Gaussian();
      this.factors = {};
    }

    Variable.prototype.AttachFactor = function(factor) {
      return this.factors[factor] = new Gaussian();
    };

    Variable.prototype.UpdateMessage = function(factor, message) {
      var old_message;

      old_message = this.factors[factor];
      this.value = this.value.div(old_message).mul(message);
      return this.factors[factor] = message;
    };

    Variable.prototype.UpdateValue = function(factor, value) {
      var old_message;

      old_message = this.factors[factor];
      this.factors[factor] = value.mul(old_message).div(this.value);
      return this.value = value;
    };

    Variable.prototype.GetMessage = function(factor) {
      return this.factors[factor];
    };

    return Variable;

  })();

  Factor = (function() {
    /* Base class for a factor node in the factor graph.
    */
    function Factor(variables) {
      var v, _i, _len;

      this.id = genId();
      this.variables = variables;
      for (_i = 0, _len = variables.length; _i < _len; _i++) {
        v = variables[_i];
        v.AttachFactor(this);
      }
    }

    Factor.prototype.toString = function() {
      return "Factor_" + this.id;
    };

    return Factor;

  })();

  PriorFactor = (function(_super) {
    __extends(PriorFactor, _super);

    /* Connects to a single variable, pushing a fixed (Gaussian) value
    to that variable.
    */


    function PriorFactor(variable, param) {
      PriorFactor.__super__.constructor.call(this, [variable]);
      this.param = param;
    }

    PriorFactor.prototype.Start = function() {
      return this.variables[0].UpdateValue(this, this.param);
    };

    return PriorFactor;

  })(Factor);

  LikelihoodFactor = (function(_super) {
    __extends(LikelihoodFactor, _super);

    /* Connects two variables, the value of one being the mean of the
    message sent to the other.
    */


    function LikelihoodFactor(mean_variable, value_variable, variance) {
      LikelihoodFactor.__super__.constructor.call(this, [mean_variable, value_variable]);
      this.mean = mean_variable;
      this.value = value_variable;
      this.variance = variance;
    }

    LikelihoodFactor.prototype.UpdateValue = function() {
      /* Update the value after a change in the mean (going "down" in
      the TrueSkill factor graph.
      */

      var a, fy, y;

      y = this.mean.value;
      fy = this.mean.GetMessage(this);
      a = 1.0 / (1.0 + this.variance * (y.pi - fy.pi));
      return this.value.UpdateMessage(this, new Gaussian({
        "pi": a * (y.pi - fy.pi),
        "tau": a * (y.tau - fy.tau)
      }));
    };

    LikelihoodFactor.prototype.UpdateMean = function() {
      /* Update the mean after a change in the value (going "up" in
      the TrueSkill factor graph.
      */

      var a, fx, x;

      x = this.value.value;
      fx = this.value.GetMessage(this);
      a = 1.0 / (1.0 + this.variance * (x.pi - fx.pi));
      return this.mean.UpdateMessage(this, new Gaussian({
        "pi": a * (x.pi - fx.pi),
        "tau": a * (x.tau - fx.tau)
      }));
    };

    return LikelihoodFactor;

  })(Factor);

  SumFactor = (function(_super) {
    __extends(SumFactor, _super);

    /* A factor that connects a sum variable with 1 or more terms,
    which are summed after being multiplied by fixed (real)
    coefficients.
    */


    function SumFactor(sum_variable, terms_variables, coeffs) {
      if (len(terms_variables) !== len(coeffs)) {
        throw new Error("assert error");
      }
      this.sum = sum_variable;
      this.terms = terms_variables;
      this.coeffs = coeffs;
      SumFactor.__super__.constructor.call(this, [sum_variable].concat(terms_variables));
    }

    SumFactor.prototype._InternalUpdate = function(variable, y, fy, a) {
      var j, new_pi, new_tau;

      new_pi = map(range(len(a)), function(j) {
        return pow(a[j], 2) / (y[j].pi - fy[j].pi);
      });
      new_pi = 1.0 / sum(new_pi);
      new_tau = new_pi * sum((function() {
        var _i, _len, _ref, _results;

        _ref = range(len(a));
        _results = [];
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          j = _ref[_i];
          _results.push(a[j] * (y[j].tau - fy[j].tau) / (y[j].pi - fy[j].pi));
        }
        return _results;
      })());
      variable.UpdateMessage(this, new Gaussian({
        "pi": new_pi,
        "tau": new_tau
      }));
    };

    SumFactor.prototype.UpdateSum = function() {
      /* Update the sum value ("down" in the factor graph).
      */

      var a, fy, t, y;

      y = (function() {
        var _i, _len, _ref, _results;

        _ref = this.terms;
        _results = [];
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          t = _ref[_i];
          _results.push(t.value);
        }
        return _results;
      }).call(this);
      fy = (function() {
        var _i, _len, _ref, _results;

        _ref = this.terms;
        _results = [];
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          t = _ref[_i];
          _results.push(t.GetMessage(this));
        }
        return _results;
      }).call(this);
      a = this.coeffs;
      this._InternalUpdate(this.sum, y, fy, a);
    };

    SumFactor.prototype.UpdateTerm = function(index) {
      /* Update one of the term values ("up" in the factor graph).
      */

      var a, b, fy, i, v, y;

      b = this.coeffs;
      a = (function() {
        var _i, _len, _ref, _results;

        _ref = range(len(b));
        _results = [];
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          i = _ref[_i];
          if (i !== index) {
            _results.push(-b[i] / b[index]);
          }
        }
        return _results;
      })();
      a.splice(index, 0, 1.0 / b[index]);
      v = this.terms.slice(0);
      v[index] = this.sum;
      y = (function() {
        var _i, _len, _results;

        _results = [];
        for (_i = 0, _len = v.length; _i < _len; _i++) {
          i = v[_i];
          _results.push(i.value);
        }
        return _results;
      })();
      fy = (function() {
        var _i, _len, _results;

        _results = [];
        for (_i = 0, _len = v.length; _i < _len; _i++) {
          i = v[_i];
          _results.push(i.GetMessage(this));
        }
        return _results;
      }).call(this);
      return this._InternalUpdate(this.terms[index], y, fy, a);
    };

    return SumFactor;

  })(Factor);

  TruncateFactor = (function(_super) {
    __extends(TruncateFactor, _super);

    /* A factor for (approximately) truncating the team difference
    distribution based on a win or a draw (the choice of which is
    determined by the functions you pass as V and W).
    */


    function TruncateFactor(variable, V, W, epsilon) {
      TruncateFactor.__super__.constructor.call(this, [variable]);
      this["var"] = variable;
      this.V = V;
      this.W = W;
      this.epsilon = epsilon;
    }

    TruncateFactor.prototype.Update = function() {
      var V, W, args, c, d, fx, new_val, sqrt_c, x;

      x = this["var"].value;
      fx = this["var"].GetMessage(this);
      c = x.pi - fx.pi;
      d = x.tau - fx.tau;
      sqrt_c = sqrt(c);
      args = [d / sqrt_c, this.epsilon * sqrt_c];
      V = this.V.apply(this, args);
      W = this.W.apply(this, args);
      new_val = new Gaussian({
        "pi": c / (1.0 - W),
        "tau": (d + sqrt_c * V) / (1.0 - W)
      });
      return this["var"].UpdateValue(this, new_val);
    };

    return TruncateFactor;

  })(Factor);

  DrawProbability = function(epsilon, beta, total_players) {
    if (total_players == null) {
      total_players = 2;
    }
    /* Compute the draw probability given the draw margin (epsilon).
    */

    return 2 * cdf(epsilon / (sqrt(total_players) * beta)) - 1;
  };

  DrawMargin = function(p, beta, total_players) {
    if (total_players == null) {
      total_players = 2;
    }
    /* Compute the draw margin (epsilon) given the draw probability.
    */

    return icdf((p + 1.0) / 2) * sqrt(total_players) * beta;
  };

  INITIAL_MU = 25.0;

  INITIAL_SIGMA = INITIAL_MU / 3.0;

  BETA = null;

  EPSILON = null;

  GAMMA = null;

  SetParameters = function(beta, epsilon, draw_probability, gamma) {
    if (beta == null) {
      beta = null;
    }
    if (epsilon == null) {
      epsilon = null;
    }
    if (draw_probability == null) {
      draw_probability = null;
    }
    if (gamma == null) {
      gamma = null;
    }
    /*
    Sets three global parameters used in the TrueSkill algorithm.
    beta is a measure of how random the game is.  You can think of it as
    the difference in skill (mean) needed for the better player to have
    an ~80% chance of winning.  A high value means the game is more
    random (I need to be *much* better than you to consistently overcome
    the randomness of the game and beat you 80% of the time); a low
    value is less random (a slight edge in skill is enough to win
    consistently).  The default value of beta is half of INITIAL_SIGMA
    (the value suggested by the Herbrich et al. paper).
    epsilon is a measure of how common draws are.  Instead of specifying
    epsilon directly you can pass draw_probability instead (a number
    from 0 to 1, saying what fraction of games end in draws), and
    epsilon will be determined from that.  The default epsilon
    corresponds to a draw probability of 0.1 (10%).  (You should pass a
    value for either epsilon or draw_probability, not both.)
    gamma is a small amount by which a player's uncertainty (sigma) is
    increased prior to the start of each game.  This allows us to
    account for skills that vary over time; the effect of old games
    on the estimate will slowly disappear unless reinforced by evidence
    from new games.
    */

    if (beta === null) {
      BETA = INITIAL_SIGMA / 2.0;
    } else {
      BETA = beta;
    }
    if (epsilon === null) {
      if (draw_probability === null) {
        draw_probability = 0.10;
      }
      EPSILON = DrawMargin(draw_probability, BETA);
    } else {
      EPSILON = epsilon;
    }
    if (gamma === null) {
      return GAMMA = INITIAL_SIGMA / 100.0;
    } else {
      return GAMMA = gamma;
    }
  };

  SetParameters();

  AdjustPlayers = function(players) {
    /*
    Adjust the skills of a list of players.
    'players' is a list of player objects, for all the players who
    participated in a single game.  A 'player object' is any object with
    a "skill" attribute (a (mu, sigma) tuple) and a "rank" attribute.
    Lower ranks are better; the lowest rank is the overall winner of the
    game.  Equal ranks mean that the two players drew.
    This function updates all the "skill" attributes of the player
    objects to reflect the outcome of the game.  The input list is not
    altered.
    */

    var ds, f, i, p, perf_to_team, ps, skill, skill_to_perf, ss, team_diff, trunc, ts, _i, _j, _k, _l, _len, _len1, _len2, _len3, _len4, _len5, _len6, _len7, _len8, _len9, _m, _n, _o, _p, _q, _r, _ref, _ref1;

    players = players.slice(0);
    players.sort(function(a, b) {
      return a.rank - b.rank;
    });
    ss = (function() {
      var _i, _len, _results;

      _results = [];
      for (_i = 0, _len = players.length; _i < _len; _i++) {
        p = players[_i];
        _results.push(new Variable());
      }
      return _results;
    })();
    ps = (function() {
      var _i, _len, _results;

      _results = [];
      for (_i = 0, _len = players.length; _i < _len; _i++) {
        p = players[_i];
        _results.push(new Variable());
      }
      return _results;
    })();
    ts = (function() {
      var _i, _len, _results;

      _results = [];
      for (_i = 0, _len = players.length; _i < _len; _i++) {
        p = players[_i];
        _results.push(new Variable());
      }
      return _results;
    })();
    ds = (function() {
      var _i, _len, _ref, _results;

      _ref = players.slice(0, -1);
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        p = _ref[_i];
        _results.push(new Variable());
      }
      return _results;
    })();
    skill = (function() {
      var _i, _len, _ref, _results;

      _ref = zip({
        s: ss,
        pl: players
      });
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        i = _ref[_i];
        _results.push(new PriorFactor(i.s, new Gaussian({
          "mu": i.pl.skill[0],
          "sigma": i.pl.skill[1] + GAMMA
        })));
      }
      return _results;
    })();
    skill_to_perf = (function() {
      var _i, _len, _ref, _results;

      _ref = zip({
        s: ss,
        p: ps
      });
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        i = _ref[_i];
        _results.push(new LikelihoodFactor(i.s, i.p, pow(BETA, 2)));
      }
      return _results;
    })();
    perf_to_team = (function() {
      var _i, _len, _ref, _results;

      _ref = zip({
        p: ps,
        t: ts
      });
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        i = _ref[_i];
        _results.push(new SumFactor(i.t, [i.p], [1]));
      }
      return _results;
    })();
    team_diff = (function() {
      var _i, _len, _ref, _results;

      _ref = zip({
        d: ds,
        t1: ts.slice(0, -1),
        t2: ts.slice(1)
      });
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        i = _ref[_i];
        _results.push(new SumFactor(i.d, [i.t1, i.t2], [+1, -1]));
      }
      return _results;
    })();
    trunc = (function() {
      var _i, _len, _ref, _results;

      _ref = zip({
        d: ds,
        pl1: players.slice(0, -1),
        pl2: players.slice(1)
      });
      _results = [];
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        i = _ref[_i];
        _results.push(new TruncateFactor(i.d, (i.pl1.rank === i.pl2.rank ? Vdraw : Vwin), (i.pl1.rank === i.pl2.rank ? Wdraw : Wwin), EPSILON));
      }
      return _results;
    })();
    for (_i = 0, _len = skill.length; _i < _len; _i++) {
      f = skill[_i];
      f.Start();
    }
    for (_j = 0, _len1 = skill_to_perf.length; _j < _len1; _j++) {
      f = skill_to_perf[_j];
      f.UpdateValue();
    }
    for (_k = 0, _len2 = perf_to_team.length; _k < _len2; _k++) {
      f = perf_to_team[_k];
      f.UpdateSum();
    }
    _ref = range(5);
    for (_l = 0, _len3 = _ref.length; _l < _len3; _l++) {
      i = _ref[_l];
      for (_m = 0, _len4 = team_diff.length; _m < _len4; _m++) {
        f = team_diff[_m];
        f.UpdateSum();
      }
      for (_n = 0, _len5 = trunc.length; _n < _len5; _n++) {
        f = trunc[_n];
        f.Update();
      }
      for (_o = 0, _len6 = team_diff.length; _o < _len6; _o++) {
        f = team_diff[_o];
        f.UpdateTerm(0);
        f.UpdateTerm(1);
      }
    }
    for (_p = 0, _len7 = perf_to_team.length; _p < _len7; _p++) {
      f = perf_to_team[_p];
      f.UpdateTerm(0);
    }
    for (_q = 0, _len8 = skill_to_perf.length; _q < _len8; _q++) {
      f = skill_to_perf[_q];
      f.UpdateMean();
    }
    _ref1 = zip({
      s: ss,
      pl: players
    });
    for (_r = 0, _len9 = _ref1.length; _r < _len9; _r++) {
      i = _ref1[_r];
      i.pl.skill = i.s.value.MuSigma();
    }
  };

  exports.AdjustPlayers = AdjustPlayers;

  exports.SetParameters = SetParameters;

  exports.SetInitialMu = function(val) {
    return INITIAL_MU = val;
  };

  exports.SetInitialSigma = function(val) {
    return INITIAL_SIGMA = val;
  };

}).call(this);