TrueSkill
TrueSkill is a Bayesian ranking algorithm developed by Microsoft Research and used in the Xbox matchmaking system built to address some perceived flaws in the Elo rating system. It is an extension of the Glicko rating system to multiplayer games.[1][2]
TrueSkill maintains a belief on the skill of each player; every time a player plays a game, the system accordingly changes the perceived skill of the player and acquires more confidence about this perception.
Calculation
Published formulas for Trueskill are not complete, and some needed functions are simply shown as graphs. Some of the math is spelled out in the paper.
A player's skill is represented as a normal distribution characterized by a mean value of (mu, representing perceived skill) and a variance of (sigma, representing how much "confidence" the system has in the player's value). As such can be interpreted as the probability that the player's "true" skill is .
On Xbox Live, players start with and ; always increases after a win and always decreases after a loss. The extent of actual updates depends on each player's and on how "surprising" the outcome is to the system. Unbalanced games, for example, result in either negligible updates when the favorite wins, or huge updates when the favorite loses surprisingly.
Factor graphs are used to "pack up" each team into pairs on which the update formulas are run; the skill updates are then correctly distributed to each player.
Player ranks are displayed as the conservative estimate of their skill, . This is conservative, because the system is 99% sure that the player's skill is actually higher than what is displayed as their rank.
The system can be used with arbitrary scales, but Microsoft uses a scale from 0 to 50 for Xbox Live. Hence, players start with a rank of . This means that a new player's defeat results in a large sigma loss, which partially or completely compensates their mu loss. This explains why people may gain ranks from losses.
Use in other projects
TrueSkill is patented,[3] and the name is trademarked, so therefore it is limited to Microsoft projects and commercial projects that obtain a license to use the algorithm.
See also
- Elo rating system
- Glicko rating system
- Software Patents
References
- ↑ "TrueSkill Ranking System FAQ - Microsoft Research". microsoft.com. Retrieved 2011-02-02.
- ↑ "TrueSkill: A Bayesian Skill Rating System". MIT Press. 2007. Retrieved 2011-02-02.
- ↑ "US Patent Application 20090227313: Determining Relative Skills of Players".
External links
- Microsoft Research's TrueSkill homepage
- Microsoft Research's TrueSkill paper
- In-depth explanation of the mathematical background