TrueSkill评分系统

TrueSkill系统是基于贝叶斯推断的评分系统,由微软研究院开发以代替传统Elo评分,并成功应用于Xbox Live自动匹配系统。TrueSkill评分系统是Glicko英语Glicko rating system评分系统的衍伸,主要用于多人游戏中[1][2]。TrueSkill评分系统考虑到了个别玩家水平的不确定性,综合考虑了各玩家的胜率和可能的水平涨落。当各玩家进行了更多的游戏后,即使个别玩家的胜率不变,系统也会因为对个别玩家的水平更加了解而改变对玩家的评分。

Rank值的计算公式

 
这张图来自微软的网站,钟型曲线为某个玩家水平的可能分布,绿色区域15~20代表了Ranking System对的评分。可以看出系统的评分是比较保守的。

TrueSkill假设玩家的水平可以用一个常态分布来表示,而常态分布可以用两个参数:平均值和方差来完全描述。设Rank值为R,代表玩家水平的常态分布的两个参数平均值和方差分别为  ,则系统对玩家的评分即Rank值为

 

k值越大则系统的评分越保守。

输赢对Rank值的影响

下面这张表格来自微软研究院[3],此表格给出了8个新手在参与一个8人游戏后  的变化。

Name Outcome Pre-Game μ Pre-Game σ Post-Game μ Post-Game σ
Alice 1st 25 8.3 36.771 5.749
Bob 2nd 25 8.3 32.242 5.133
Chris 3rd 25 8.3 29.074 4.943
Darren 4th 25 8.3 26.322 4.874
Eve 5th 25 8.3 23.678 4.874
Fabien 6th 25 8.3 20.926 4.943
George 7th 25 8.3 17.758 5.133
Hillary 8th 25 8.3 13.229 5.749

这里有个很有意思的现象:注意第四名Darren和第五名Eve,他们的 是最小的,换句话说系统认为他们能力的可能起伏是最小的。这是因为通过这场游戏我们对他们了解得最多:他们赢了3/4个人,也输给了4/3个人。而对于第一名Alice,我们只知道她赢了7个人。

如果想知道更详细的定量分析可以先考虑最简单的两人游戏情况

 
 
 
 
 

系数 代表的是所有玩家的平均方差。  是两个函数,比较复杂。ε是“平局参数”。

简而言之,个别玩家赢了  就增加,输了  减小;但不论输赢, 都是在减小,所以有可能出现输了涨分的情况。

如何自动匹配对手

势均力敌的对手能带来最精彩的比赛,所以当自动匹配对手时,系统会尽可能的为个别玩家安排可能与水平最为接近的对手。TrueSkill评分系统采用了一个值域为 的函数来描述两个人是否势均力敌:结果越接近0代表差距越大,越接近1代表水平越接近。

假设有两个玩家A和B,他们的参数为   ,则函数对这两个玩家的返回值为

 

c的值由如下公式给出

 

如果两人有较大几率被匹配在一起,光是平均值接近还不行(e指数上那一项),还得方差也比较接近才行(d)。

Xbox Live上的应用

在Xbox Live上,系统为每个玩家赋予的初值是μ = 25 以及 σ = 25 / 3,k=3。所以玩家的起始Rank值为

 

参考资料

  1. ^ TrueSkill™ Ranking System FAQ - Microsoft Research. microsoft.com. [2011-02-02]. (原始内容存档于2011-03-18). 
  2. ^ TrueSkill™: A Bayesian Skill Rating System (PDF). MIT Press. 2007 [2011-02-02]. (原始内容存档 (PDF)于2011-04-09). 
  3. ^ TrueSkill™ Ranking System: Details. =microsoft.com. [2011-06-12]. (原始内容存档于2011-06-05). 

外部链接