TrueSkill評分系統

TrueSkill系統是基於貝葉斯推斷的評分系統，由微軟研究院開發以代替傳統Elo評分，並成功應用於Xbox Live自動匹配系統。TrueSkill評分系統是Glicko評分系統的衍伸，主要用於多人遊戲中。TrueSkill評分系統考慮到了個別玩家水平的不確定性，綜合考慮了各玩家的勝率和可能的水平漲落。當各玩家進行了更多的遊戲後，即使個別玩家的勝率不變，系統也會因為對個別玩家的水平更加了解而改變對玩家的評分。

Rank值的計算公式

這張圖來自微軟的網站，鍾型曲線為某個玩家水平的可能分布，綠色區域15～20代表了Ranking System對的評分。可以看出系統的評分是比較保守的。

TrueSkill假設玩家的水平可以用一個正態分布來表示，而正態分布可以用兩個參數：平均值和方差來完全描述。設Rank值為R，代表玩家水平的正態分布的兩個參數平均值和方差分別為$\mu$和$\sigma$，則系統對玩家的評分即Rank值為

$R=\mu -k\times \sigma$

k值越大則系統的評分越保守。

輸贏對Rank值的影響

下面這張表格來自微軟研究院，此表格給出了8個新手在參與一個8人遊戲後$\mu$和$\sigma$的變化。

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，他們的$\sigma$是最小的，換句話說系統認為他們能力的可能起伏是最小的。這是因為通過這場遊戲我們對他們了解得最多：他們贏了3/4個人，也輸給了4/3個人。而對於第一名Alice，我們只知道她贏了7個人。

如果想知道更詳細的定量分析可以先考慮最簡單的兩人遊戲情況

$\mu _{winner}\longleftarrow \mu _{winner}+{\dfrac {\sigma _{winner}^{2}}{c}}*v({\dfrac {\mu _{winner}-\mu _{loser}}{c}},{\dfrac {\varepsilon }{c}})$

$\mu _{loser}\longleftarrow \mu _{loser}-{\dfrac {\sigma _{loser}^{2}}{c}}*v({\dfrac {\mu _{winner}-\mu _{loser}}{c}},{\dfrac {\varepsilon }{c}})$

$\sigma _{winner}^{2}\longleftarrow \sigma _{winner}^{2}*[1-{\dfrac {\sigma _{winner}^{2}}{c}}*w({\dfrac {\mu _{winner}-\mu _{loser}}{c}},{\dfrac {\varepsilon }{c}})$

$\sigma _{loser}^{2}\longleftarrow \sigma _{loser}^{2}*[1-{\dfrac {\sigma _{loser}^{2}}{c}}*w({\dfrac {\mu _{winner}-\mu _{loser}}{c}},{\dfrac {\varepsilon }{c}})$

$c^{2}=2\beta ^{2}+\sigma _{winner}^{2}+\sigma _{loser}^{2}$

係數$\beta ^{2}$代表的是所有玩家的平均方差。$v$和$w$是兩個函數，比較複雜。ε是「平局參數」。

簡而言之，個別玩家贏了$\mu$ 就增加，輸了$\mu$ 減小；但不論輸贏，$\sigma$都是在減小，所以有可能出現輸了漲分的情況。

如何自動匹配對手

勢均力敵的對手能帶來最精彩的比賽，所以當自動匹配對手時，系統會儘可能的為個別玩家安排可能與水平最為接近的對手。TrueSkill評分系統採用了一個值域為$(0,1)$的函數來描述兩個人是否勢均力敵：結果越接近0代表差距越大，越接近1代表水平越接近。

假設有兩個玩家A和B，他們的參數為$(\mu _{A},\sigma _{A})$ 和 $(\mu _{B},\sigma _{B})$ ，則函數對這兩個玩家的返回值為

$e^{-{\dfrac {(\mu _{A}-\mu _{B})^{2}}{2c^{2}}}}{\sqrt {\dfrac {2\beta ^{2}}{c^{2}}}}$

c的值由如下公式給出

$c^{2}=2\beta ^{2}+\mu _{A}^{2}+\mu _{B}^{2}$

如果兩人有較大幾率被匹配在一起，光是平均值接近還不行（e指數上那一項），還得方差也比較接近才行（d）。

Xbox Live上的應用

在Xbox Live上，系統為每個玩家賦予的初值是μ = 25 以及 σ = 25 / 3，k=3。所以玩家的起始Rank值為

$R=25-3{\dfrac {25}{3}}=0$

外部連結

• Microsoft Research's TrueSkill homepage（頁面存檔備份，存於網際網路檔案館）
• Microsoft Research's TrueSkill paper（頁面存檔備份，存於網際網路檔案館）
• In-depth explanation of the mathematical background（頁面存檔備份，存於網際網路檔案館）