Online ranking algorithm in scala

Ability.scala

package gaming.online.scala

/**
 * A representation of a player's ability. A normal distribution, really
 */
// private constructor
class Ability private (val mean: Double, val stddev: Double, val variance: Double) {
  
  // Callers of this method cannot use parentheses
  def skill:Double = mean - 3 * stddev
  
  // operator overloading
  def +(other: Ability):Ability =
    Ability.withVariance(mean + other.mean, variance + other.variance)

  override def toString = "mu:%.2f,stddev:%.2f".format(mean, stddev)
}

// methods in this object are like Java's static methods
object Ability {
  def withVariance(mean: Double, variance: Double):Ability =
    new Ability(mean, Math.sqrt(variance), variance)

  def withStddev(mean: Double, stddev: Double):Ability =
    new Ability(mean, stddev, stddev * stddev)
  
  def zero:Ability = withStddev(0, 0)
}

BradleyTerryFullUpdater.scala

package gaming.online.scala

import MoreLists._ // pulls in the implicit converter to MoreLists

/** This is the best performing bayesian online ranking algorithm described in this paper
 * http://www.csie.ntu.edu.tw/~cjlin/papers/online_ranking/
 **/ 
// The main constructor's parameters are declared up here at the class level 
class BradleyTerryFullUpdater(rankAllowance: Double) {
  
  private val betaSquared = { // assigned to the last expression in the block
    val mu = 25.0
    val sigma = mu / 3.0
    val beta = sigma * 0.5
    beta * beta
  }

  /* Methods that return values are defined with an equal sign. Without an equal sign, it returns
   * Unit (akin to void in Java)
   * 
   * This method defines a block of expressions as it's body. The last expression is the return value
   * (similar to lisps, ruby, and sometimes perl)
   */
  def updatePlayerRankings(_teams: List[Team]): List[Player] = {
    if (_teams.isEmpty) return Nil

    // parens and period can be omitted on one-arg methods
    val teams = _teams sorted ByScoreAndSkill.forCalculation
    val ranks = calculateRanks(teams)

    // parens are optional on no-arg methods. Sometimes even prohibited.
    // Style guide says to use parens when the function performs side effects 
    val gamma = 1.0 / teams.size

    // fullUpdate returns a function that expects function as it's input. nice syntax, eh?
    // it is also the last expression in the method and so is the return value
    fullUpdate(teams) { (team, opponentTeam) =>
      val ability = team.ability
      val opponent = opponentTeam.ability

      val c = Math.sqrt(ability.variance + opponent.variance + 2 * betaSquared)
      val p = 1 / (1 + Math.exp((opponent.mean - ability.mean) / c))
      val varianceToC = ability.variance / c

      // getting a value from a map is like calling a function (a map _is_ conceptually a function)
      val s = ranks(team) compare ranks(opponentTeam) match { // pattern matching, yea!
        case x if x < 0 => 1.0
        case 0 => 0.5
        case _ => 0.0
      }

      val omega = varianceToC * (s - p)
      val delta = gamma * varianceToC / c * p * (1 - p) 

      // returning a tuple!
      (omega, delta)
    }
  }

  /* Notice there are two parameter lists. This means fullUpdate returns a function.
   * This is effectually currying.
   * 
   * The returned function expects function as it's input. This is a common idiom that allows for
   * nice syntax. (Look at how it's called.)
   */
  private def fullUpdate(teams: List[Team])(calc: (Team, Team) => (Double, Double)) = {
    // collections are typically immutable. Here's a builder to help out
    val updatedAbilities = List.newBuilder[Player]
    
    val zero = (0.0, 0.0) // tuples!
    for (team <- teams) {
      // List comprehension with a guard clause
      val scores = for (opponent <- teams if opponent != team) yield calc(team, opponent)
      
      // fold left aka reduce. Also notice the tuple unpacking, aka multiple return values
      val (omega, delta) = (zero /: scores) { (a, b) => (a._1 + b._1, a._2 + b._2) }

      updatedAbilities ++= resultingAbilities(team, omega, delta)
    }
    
    updatedAbilities.result 
  }
  
  // Return type can often be omitted (should still specify it on public methods)
  private def calculateRanks(teams: List[Team]) = {
    val ranks = Map.newBuilder[Team, Int] 
    var currentRank = 0;
    /* This next line has two interesting things:
     * 1. It implicitly wraps a List as a MoreLists. see the def of MoreLists for how.
     * 2. That's a function of two parameters passed to spanSimilar 
     */
    for (sameRank <- teams.spanSimilar(_.score - rankAllowance <= _.score)) {
      for (team <- sameRank)
         // "a -> b" is a shortcut for a tuple. Maps are built by adding key -> value tuples
        ranks += team -> currentRank
      currentRank += sameRank.size
    }

    ranks.result
  }
  
    
  private def resultingAbilities(players: Team, omega: Double, delta: Double) = {
    val team = players.ability
    
    // Notice the yield; this means the loop results in an Iterable
    for (player <- players) yield {
      val ability = player.ability
      val mean = ability.mean + ability.variance / team.variance * omega
      val stddev = ability.stddev *
          Math.sqrt(Math.max(1 - ability.variance / team.variance * delta, 0.0001))
      
      new Player(player.id, Ability.withStddev(mean, stddev))
    }
  }
}

Go.scala

package gaming.online.scala

import scala.util.Random

object Go extends App {
  val team1 = new Team(1, 500,
      Player(1, Ability.withStddev(25, 8)),
      Player(2, Ability.withStddev(27, 5)),
      Player(3, Ability.withStddev(22, 3)))
  
  val team2 = new Team(2, 400,
      Player(4, Ability.withStddev(25, 8)),
      Player(5, Ability.withStddev(27, 5)),
      Player(6, Ability.withStddev(22, 3)))
  
  val team3 = new Team(3, 395,
      Player(7, Ability.withStddev(25, 8)),
      Player(8, Ability.withStddev(27, 5)),
      Player(9, Ability.withStddev(22, 3)))
  
  
  val teams = Random shuffle List(team1, team2, team3)
  
  Console.println("Game outcome:")
  Console.println(teams sorted ByScoreAndSkill.forDisplay mkString "\n")
  
  
  val updatedPlayers = new BradleyTerryFullUpdater(10) updatePlayerRankings teams
  
  Console.println()
  Console.println("Updated abilities:")
  Console.println(updatedPlayers sortWith { (a, b) => a.id < b.id } mkString "\n")
}

MoreLists.scala

package gaming.online.scala

/**
 * Pimp-my-library for a list. adds spanSimilar method to lists
 */
class MoreLists[A](list:List[A]) {
  /**
   * Groups elements in a list according to how they relate with each other.
   * 
   * This is similar to calling:
   * 
   * val (head1, tail1) = (list.head, list.tail)
   * val (head2, tail2) = tail1 span { x => f(head1, x) }
   * val (head3, tail3) = tail2 span { x => f(head2, x) }
   * ...
   * List(head1, head2, head3)
   */
  /* The syntax B >: A would look this this in java "public <B super A> spanSimilar(...)"
   * The syntax B <: A would look this this in java "public <B extends A> spanSimilar(...)"
   * At the class level, there is also +A and -A.
   */
  def spanSimilar[B>:A](f: (B, B) => Boolean):List[List[A]] = {
    val acc = List.newBuilder[List[A]]
    
    var cur = list
    while (!cur.isEmpty) {
      val head = cur.head
      val (likeHead, tail) = cur.tail span { x => f(head, x) }
      acc += (head :: likeHead)
      cur = tail
    }
    
    acc.result
  }
  
  // here's a recursive formulation of spanSimilar
  private def spanSimilarRecursive[B>:A](list:List[A], f: (B, B) => Boolean):List[List[A]] = list match {
    case Nil => Nil
    case head :: Nil => List(head) :: Nil
    case head :: tail =>
      val (likeHead, notLikeHead) = tail span { x => f(head, x) }
      (head :: likeHead) :: spanSimilarRecursive(notLikeHead, f)
  }
}

object MoreLists {
  /** This implicitly converts a List to a MoreLists, effectively allowing the caller
   * to use MoreLists methods on a List
   **/
  implicit def list2MoreLists[A](list:List[A]):MoreLists[A] = new MoreLists(list)
}

Ordering.scala

package gaming.online.scala

/**
 * Orderings which sort a team by score and ability.
 * <p>
 * These orderings will produce the same sorted results no matter the initial
 * order of the teams. This is important when using a partial-pair updater
 * instead of a full-pair updater.
 * </p>
 */
object ByScoreAndSkill {

      /**
     * An ordering which gives preference to teams with
     * <ol>
     * <li>Higher score;</li>
     * <li>More players;</li>
     * <li>Higher skill;</li>
     * <li>Lower id</li>
     * </ol>
     * 
     * <p>
     * <b>Rationale for tie-breakers</b> A partial-pair updater only updates
     * players' abilities based on how it compared to the surrounding teams by
     * rank. When two teams tie, one team will be compared with a better team
     * while the other is compared with a worse team, in terms of score. In
     * other words, of these two teams the team this comparator puts first will
     * get attributed a loss while the other team is attributed a win. (Both
     * teams will also be attributed a draw.)
     * </p>
     * <p>
     * The team with less players and equal score likely had better individual
     * ability, and are accordingly attributed the "win."
     * </p>
     * <p>
     * Accounting for number of players, it is assumed a team with higher skill
     * should have beaten a team with lower skill. Thus, this comparator
     * positions the underdog to gain the win.
     * </p>
     * <p>
     * <b>Note:</b> The tie-breaking doesn't matter when using a full-pair
     * updater because a team is always compared to every other team.
     * </p>
     */
  def forCalculation:Ordering[Team] =
    Ordering[(Double, Double, Double, Long)].on[Team] {t => (-t.score, -t.size, -t.skill, t.id) }

    /**
     * An ordering which gives preference to teams with
     * <ol>
     * <li>Higher score;</li>
     * <li>Less players;</li>
     * <li>Lower skill;</li>
     * <li>Higher id</li>
     * </ol>
     * 
     * See the documentation of {@link #forCalculation()} for rationale of the
     * tie-breakers which are flipped in this method to provide better user
     * experience.
     */
  def forDisplay:Ordering[Team] =
    Ordering[(Double, Double, Double, Long)].on[Team] {t => (-t.score, t.size, t.skill, -t.id) }
}

Player.scala

package gaming.online.scala

case class Player(val id:Long, val ability:Ability)

Team.scala

package gaming.online.scala

class Team(val id:Long, val score:Double, val players:Player*) extends Iterable[Player] {
  val ability = (Ability.zero /: players)(_+_.ability)
  
  def skill = ability.skill
  
  def iterator = players.iterator
  
  // no need to implement size, the trait defines a default implementation
  // def size = players.size
  
  // must annotate with override
  override def toString = "Team(id=%d;score=%f;players=%s)".format(id, score, players mkString ",") 
}