Abstract

In this talk I will present a Bayesian approach to ranking a set of objects based on the possibly partial or noisy rankings of small subsets of objects. Rankings are represented by assigning a latent real-valued variable (skill, urgency, value) to each object and sorting the objects according to the magnitude of the latent variables. The system maintains a Gaussian belief about the value of each object in terms of mean and variance. I will discuss approximate message passing in factor graphs as the computational technique to address the problem of inference.

After presenting theoretical and algorithmic aspects of the system, I will outline two applications:

• TrueSkill™ – Ranking of players: The system is used to provide matchmaking and leaderboard functionality based on the estimated skills of players. An implementation of the system is currently at the heart of ranking and matchmaking in the online gaming service Xbox Live, used by 1 million players playing approximately 500,000 ranked matches every 24 hours.

• Liberty – Ranking of potential moves in Computer Go: The system is used to learn the values of local patterns based on the moves played in a given position. The “winner” is determined by observing which one of the legal moves in a given position has been played by an expert player. The result is a probability distribution over moves for a given position. It can serve, for example, as fast stand-alone Go engine of respectable playing strength. The current system plays at 10-15 kyu and correctly predicts expert moves in 34% of the cases.