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). 

外部連結