Details on XBox TrueSkill Ranking System

rupert0 writes "A research paper on the Microsoft website gives an insight into the way that gamers will be ranked on the new-style Xbox Live. The paper outlines some existing ranking systems, as well." From the article: "The TrueSkill(TM) ranking system is a skill-based ranking system designed to overcome the limitations of existing ranking systems, and to ensure that interesting matches can be reliably arranged within a league. It uses a technique called Bayesian inference for ranking players. Rather than assuming a single fixed skill for each player, the system characterises its belief using a bell-curve belief distribution (also referred to as Gaussian) which is uniquely described by its mean (speak [mju:]) ("peak point") and standard deviation (speak [sigma])("spread")."

Comments

Re:The proof of the pudding is in the tasting

[Joe Random]

I'll believe this method works if I can join a Halo 3 game as a level 1 player and not have my ass kicked.

It's not possible to guarantee that. Even if the ranking system puts you in a game with other newbie players, it has no idea what any of the players' skill levels are prior to them playing their first match. However, after getting your ass kicked a couple of times, the ranking system should be able to more reliably group you with players of an approximately equal skill level.

But it is necessary that your very first game is more likely to have some major asskicking, and you may be on the giving end or the receiving end depending on your prior, unrecorded experience.

Bayesian Inferrence

[NitsujTPU]

Bayesian Inferrence refers to a rather large class of algorithms. It would be nice if something were more specific.

To give a heads up as to what this all is. Bayesian statistics are based on the idea that a probability can be updated based on additional information.

So, perhaps you have a prior of 0.5. There is a 50/50 chance that whoever you're looking at is better than another player.

Ok, so, 0.5 is the prior. Or, perhaps he's one 90% of the games played, so 0.9 is the prior. Now, 50% of games against the 2nd ranked person, he won, but only 20% against the third... and so on. That would be one form of bayesian inferrence.

Other forms? Naive Bayes is a type of, fairly simple machine learning algorithm. There are also graphical models, which are rather advanced bayesian machine learning models.

Re:A Bayesian slight of hand?

[Ralf Herbrich]

Thanks a lot for your comments; you certainly understood the math behind TrueSkill(TM) really well! But there are a few details (that we did not want to bore people with on our web pages) which address all your concerns:

• The first problem you point out is that Bayesian estimates (in general) asymptotically converge to the maximum likelihood estimates and, hence, in the TrueSkill sytem the sigma's would eventually go to zero and not allow for adaptation in the change of the player's "true" skill. This is true for stationary models but not for models with dynamics (think of a Kalman filter, for example). In fact, in the TrueSkill system we have a dynamics factor in our model equation that says that the skill of every gamer can slightly go up or down (zero mean, small variance) between two consecutive games. If you want to see this at work, please go to http://www.research.microsoft.com/mlp/trueskill/Ra nkCalculator.aspx and put every gamer's Sigma at 0.5; then press Recalculate Skill Level Distribution and you will see that the Sigma's after the game are slighly bigger (they should be 0.504). We have worked out the asymptotic value of the uncertainity, sigma, theoretically and compared our solution to empirical findings on 3 million games; our asymptotic limit was close up to 3 digits of precision. This limit is reasonably large to allow constant adaptation for skill changes.
• The second problem you point out is that of a conjugate prior. Unfortunately, there is no conjugate prior for the probit likelihood in any representation. The approximation method we are using is called "Expectation Propagation" (see http://research.microsoft.com/~minka/papers/ep/roa dmap.html) or belief propagation in factor graphs. This IS an "incredibly nice" algorithm, to say it in your words :)
• The third problem you point out is that the whole correlation structure would be gigantic and you are absolutely right when considering that there are millions of people on Xbox Live so this matrix would be couple of million rows times couple of million columns. However, we only save the diagonal of the matrix, that is, the uncertainity in the skill of every gamer. Please note, though, that we do build up the whole correlation structure (temporarily) for all gamers within a game (to make the approximation of the update step as exact as possible).

Best wishes,
Ralf Herbrich & Thore Graepel, Microsoft Research Cambridge (UK)