游戏排名算法：Elo、Glicko、TrueSkill

news/2024/10/11 2:18:06

Elo rating system

Elo等级分制度（英语：Elo rating system）是指由匈牙利裔美国物理学家Arpad Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估公认的权威标准。

两个选手（player）在排名系统的不同，可以用来预测比赛结果。两个具有相同排名（rating）的选手相互竞争时，不管哪一方获胜都会得到相同的得分（score）。如果一个选手的排名（rating）比他的对手高100分，则得64%；如果差距是200分，那么排名高的选手的期望得分(expected score)应为76%。（可以理解为，获胜的机率更高）

一个选手的Elo rating由一个数字表示，它的增减依赖于排名选手间的比赛结果。在每场游戏后，获胜者将从失利方获得分数。胜者和败者间的排名的不同，决定着在一场比赛后总分数的获得和丢失。在高排名选手和低排名选手间的系列赛中，高排名的选手按理应会获得更多的胜利。如果高排名选手获胜，那么只会从低排名选手处获得很少的排名分（rating point）。然而，如果低排名选分爆冷获胜（upset win），可以获得许多排名分。低排名选手在平局的情况下也能从高排名选手处获得少量的得分。这意味着该排名系统是自动调整的（self-correcting）。长期来看，一个选手的排名如果太低，应比排名系统的预测做得更好，这样才能获得排名分，直到排名开始反映出他们真正的实力。

ELO等级分制度是基于统计学的一个评估棋手水平的方法。美国国际象棋协会在1960年首先使用这种计分方法。由于它比先前的方法更公平客观，这种方法很快流行开来。1970年国际棋联正式开始使用等级分制度。Elo模型原先采用正态分布。但是实践显明棋手的表现并非呈正态分布，所以现在的等级分计分系统通常使用的是逻辑分布。（如下）

（由于我自己制作的观感较差，看着像一条直线，所以就借助网上的图了，侵删）

计分方法

假设棋手A和B的当前等级分分别为$R_{A}$和$R_{B}$，则按Logistic distribution A对B的胜率期望值当为：

\[E_{A}=\frac {1}{1+10^{(R_{B}-R_{A})/400}} \]

类似B对A的胜率为：

\[E_{B}=\frac {1}{1+10^{(R_{A}-R_{B})/400}} \]

假如一位棋手在比赛中的真实得分$S_{A}$（胜=1分，和=0.5分，负=0分）和他的胜率期望值$E_{A}$不同，则他的等级分要作相应的调整。具体的数学公式为：

\[R_{A}^{\prime }=R_{A}+K(S_{A}-E_{A}) \]

以下是我瞎写的代码：

static void elo_nowRated(int ra, int rb, /*int aPos, int bPos,*/ double sa) {double sb = 0;if (sa == 0) {sb = 1;} else if (sa == 0.5) {sb = 0.5;} else {sb = 0;}double ea = 1 / (1 + std::pow(10.0, (rb - ra) / 400.0));double eb = 1 / (1 + std::pow(10.0, (ra - rb) / 400.0));double resa = 0, resb = 0;double K = 0;if (sa == 1) {//a wins
//      std::cout << "HERE! a wins!" << std::endl;if (0 <= ra && ra <= 2099) {K = 32.0;} else if (2100 <= ra && ra <= 2399) {K = 24.0;} else if (2400 <= ra) {K = 16.0;} else {std::cerr << "ERROR in elo_nowRated function!" << "\n";return;}
//        std::cout << K << std::endl;resa = K * (sa - ea);resb = K * (sb - eb);std::cout << resa << " " << resb << std::endl;
//          if (aPos == youPos) {
//              yourRated = leaderBoard[aPos].rated;
//          } else if (bPos == youPos) {
//              yourRated = leaderBoard[bPos].rated;
//          }} else if (sb == 1) {//b wins
//      std::cout << "HERE! b wins!" << std::endl;if (0 <= rb && rb <= 2099) {K = 32.0;} else if (2100 <= rb && rb <= 2399) {K = 24.0;} else if (2400 <= rb) {K = 16.0;} else {std::cerr << "ERROR in elo_nowRated function!" << "\n";return;}
//        std::cout << K << std::endl;resa = K * (sa - ea);resb = K * (sb - eb);std::cout << resa << " " << resb << std::endl;
//          leaderBoard[bPos].rated = rb + floor(resb);
//          leaderBoard[aPos].rated = ra + floor(resa);
//          if (aPos == youPos) {
//              yourRated = leaderBoard[aPos].rated;
//          } else if (bPos == youPos) {
//              yourRated = leaderBoard[bPos].rated;
//          }}
}

Glicko

鉴于Elo rating system的一个问题，即积分的可信度的问题，人们设计出了新的计分系统——Glicko。举个例子，Henry与Pablo两个人的积分均为1700，Henry胜了，按照Elo的计分规则，Pablo和Henry应分别扣除和增加16分，可Henry已经好久没进行游戏了，而Pablo每天都在进行——显然，Pablo的分数更有可信度，而Henry的积分并不可信，这就对Pablo不公平了。

虽然很多情况下并不是这么极端，但我觉得把选手评分的可信度考虑进入是很有必要的。因此Glicko系统扩展了Elo，将不再是仅计算选手评分（可以视为选手实力的“最佳猜测”），还加入了“评分误差”（RD，ratings deviation），从统计术语的概念来说，RD用于衡量一个评分的不确定度（RD值越高，评分越不可信）。高RD值意味着选手并不频繁地进行对战，或者该选手仅进行了很少次数的对战，而低RD值说明选手会很经常地进行对抗比赛。

在Glicko 系统中，选手的评分仅根据对战的结果而改变，但其RD值改变同事取决于游戏结果和未进行游戏的时间长度。该系统的一个特征是游戏的结果经常会减少选手的RD值，而未进行对战的时间则经常会增长选手的RD值。造成这个现象的原因是因为选手玩的局数越多，关于选手能力的信息就学习到越多，评分也就越真实；而随着时间流失，我们对玩家实力就越不确定，反映在RD值上就是增长。

一个很有趣的发现是在Glicko系统中，双方评分的变化并不像Elo那样经常是相同的。例如A选手的评分增长了X，在Elo系统中对手B的评分会减少X，而在Glicko系统中并非如此。实际上，在Glicko中，对手B的评分减少取决于双方的RD值。

由于Glicko系统会同时用评分和RD值、以区间的形式评定选手实力，因此相较于仅使用评分更具有实际意义。此处应用95%置信区间，那么区间下限是选手评分减去2倍的RD值，区间上限是选手评分加上2倍的RD值。例如一个选手的评分是1850、RD值是50，那么他的实际实力区间为1750~1950。选手的RD值越小，该区间越窄，也就是说我们有95%的把握可以确定选手的实力在一个较小的区间值。

为了应用该算法，我们需要对发生在同一个“评分周期（rating period）”的所有游戏进行计算。一个评分周期可以长达数月，也可以短到一分钟。在前面的例子中，选手的评分和RD值在评分周期的一开始是已知的，对战的结果是可观测的，那么在评分周期结束时就可以根据计算更新选手的评分和RD值（同时该值可以作为下一评分周期的前置评分和RD）。当每个选手在评分周期中稳定地进行5~10局对战时，Glicko系统表现得最好。评分周期的时间长度由相关人员自行设定。

若选手没有评分，则其评分通常被设为1500，评分标准差为350。

测算标准差

新的评分标准差RD可使用旧的评分标准差$RD_{0}$计算：

\[RD=\min ({\sqrt {{RD_{0}}^{2}+c^{2}t}},350) \]

t为自上次比赛至现在的时间长度（评分期），350则是新选手的评分标准差。若选手在一个评分期间内进行了多场比赛，此算法会将进行的比赛作为一场看待。评分期根据选手进行比赛的频繁程度，可能长至七个月，短至几分钟。常数c根据选手在特定时间段内的技术不确定性计算而来，计算方法可能通过数据分析，或是估算选手的评分标准差将在什么时候达到未评分选手的评分标准差得来。若一名选手的评分标准差将在100个评分期间内达到350的不确定度，则评分标准差为50的玩家的常数c可通过解$350=\sqrt {50^{2}+100c^{2}}$的方式计算而来。或$c=\sqrt {(350^{2}-50^{2})/100}\approx 34.6$

测算新评分

在经过m场比赛后，选手的新评分可通过下列等式计算：

\[r=r_{0}+{\frac {q}{{\frac {1}{RD^{2}}}+{\frac {1}{d^{2}}}}}\sum _{i=1}^{m}{g(RD_{i})(s_{i}-E(s|r_{0},r_{i},RD_{i}))} \]

其中：

\[g(RD_{i})=\frac {1}{\sqrt {1+{\frac {3q^{2}(RD_{i}^{2})}{\pi ^{2}}}}} \]

\[E(s|r,r_{i},RD_{i})=\frac {1}{1+10^{\left({\frac {g(RD_{i})(r_{0}-r_{i})}{-400}}\right)}} \]

\[q=\frac {\ln(10)}{400}=0.00575646273 \]

\[d^{2}=\frac{1}{q^{2}\sum _{i=1}^{m}{(g(RD_{i}))^{2}E(s|r_{0},r_{i},RD_{i})(1-E(s|r_{0},r_{i},RD_{i}))}} \]

$r_{i}$表示选手个人的评分；
$s_{i}$表示每场比赛后的结果。胜利为1，平局为$\frac {1}{2}$，失败为0。
测算新评分标准差

原先用于计算评分标准差的函数应增大标准差值，进而反应模型中一定非观察时间内，玩家的技术不确定性的增长。随后，评分标准差将在几场游戏后更新：

\[RD’=\sqrt {({\frac {1}{RD^{2}}}+{\frac {1}{d^{2}}})^{-1}} \]

虽然略显麻烦，但是它的好处就是相较于Elo能更加精确地评估一位选手的实力。

TrueSkill

在电子竞技游戏中，特别是当有多名选手参加比赛的时候需要平衡队伍间的水平，让游戏比赛更加有意思。这样的一个参赛选手能力平衡系统通常包含以下三个模块：

一个包含跟踪所有玩家比赛结果，记录玩家能力的模块。
一个对比赛成员进行配对的模块。
一个公布比赛中各成员能力的模块。

事实上目前已经有的游戏评分系统是Elo评分，但是Elo评分仅只是两名选手参加的游戏。TrueSkill系统是基于贝叶斯推断的评分系统，由微软研究院开发以代替传统Elo评分，并成功应用于Xbox Live自动匹配系统。TrueSkill评分系统是Glicko评分系统的衍伸，主要用于多人游戏中。TrueSkill评分系统考虑到了你水平的不确定性，综合考虑了玩家的胜率和可能的水平涨落。当玩家进行了更多的游戏后，即使你的胜率不变，系统也会因为对你的水平更加了解而改变对你的评分。

相较Elo评价系统，TrueSkill的优势在于：

适用于复杂的组队形式，更具一般性。
置于更完善的建模体系，容易扩展。
继承了贝叶斯建模的好的特点。
怎样进行能力计算

TrueSkill排名系统是针对玩家能力进行设计的，以克服现有排名系统的局限性，确保比赛双方的公平性，可以在联赛中作为排名系统使用。它为玩家排名使用的为贝叶斯定理。系统的特点是假设每一个玩家的能力不是固定的，其能力水平的表现为一个钟型曲线（正态分布或高斯分布）。

（侵删）

绿色区域15～20代表了Ranking System对的评分。可以看出系统的评分是比较保守的。$\sigma$越小则越靠近$\mu$，相应的玩家的能力水平就较高。总的来说玩家的水平受“平均得分”和“玩家稳定性”综合影响。

由于TrueSkill排名系统使用高斯信仰分布来描述一个玩家的能力，也就意味着玩家的能力始终落在4倍的$\sigma$内（概率为99.993666%）。从微软追踪的65万玩家数据显示，有99.99%都落在了3倍的$\sigma$内。有趣的是，TrueSkill排名系统可以使用1作为最初的不确定性做所有的计算，将相乘$\mu$和$\sigma$可以缩放到任何其他的范围。假设所有的计算都以初始值$\mu$=3和$\sigma$=1，如果一个玩家有50级，几乎所有的$\mu$的发生是在±3倍的初始$\sigma$，$\sigma$可得50/6 = 8.3。两个玩家最大的区别在于$\mu$值得大小。假设$\sigma$相当，那么$\mu$高的玩家赢得机会就越大，这一原则也适用在TrueSkill排名系统。但并不表示$\mu$高的就一定会赢。在单个的配对比赛中，玩家的个人表现与玩家的能力是相当的，游戏结果也是有个人表现决定的。因此，可以认为能力的一个玩家在TrueSkill的排名是在大量游戏中的平均表现。个人表现的变化原则是能力表现的一个参数。

怎样更新能力值

TrueSkill排名系统只会根据比赛结果更新$\mu$和$\sigma$，它假设的情况为一个玩家的表现围绕着他的能力水品进行变化，如果一个玩家玩一个基于点数的游戏，他战胜了所有的其他10个对手和他和战胜了另外一场比赛只有一个对手的积分是一样的，但是这样两场比赛确实反映了不同选手的能力情况。通常会使$\sigma$下降。在计算一场新的比赛结果之前，TrueSkill排名系统会计算比赛的排名与选手在比赛前的排名的变化情况。排名的变化最终影响了玩家技能的不确定性$\sigma$。这个参数可以被TrueSkill用来记录玩家的技能的变化。并且$\sigma$永远不可能为0。

下面这张表格来自微软研究院，此表格给出了8个新手在参与一个8人游戏后$\mu$和$\sigma$的变化。

这里有个很有意思的现象：注意第四名Darren和第五名Eve，他们的$\sigma$是最小的，换句话说系统认为他们能力的可能起伏是最小的。这是因为通过这场游戏我们对他们了解得最多：他们赢了3/4个人，也输给了4/3个人。而对于第一名Alice，我们只知道她赢了7个人。如果想知道更详细的定量分析可以先考虑最简单的两人游戏情况。

\[\begin{aligned}&\mu_{winner} \longleftarrow \mu_{winner}+\frac{\sigma_{winner}^{2}}{c} * v(\frac{\mu_{winner}-\mu_{loser }}{c}, \frac{\varepsilon}{c}) \\&\mu_{loser} \longleftarrow \mu_ {loser}-\frac{\sigma_{loser}^{2}}{c} * v(\frac{\mu_{winner}-\mu_{loser}}{c}, \frac{\varepsilon}{c}) \\&\sigma_{winner}^{2} \longleftarrow \sigma_{winner}^{2} *[1-\frac{\sigma_{winner}^{2}}{c} * w(\frac{\mu_{vinner}-\mu_{loser}}{c}, \frac{\varepsilon}{c}). \\&\sigma_{loser}^{2}<\sigma_{loser}^{2} * [1-\frac{\sigma_{loser}^{2}}{c} * w(\frac{\mu_{winner}-\mu_{loser}}{c}, \frac{\varepsilon}{c}). \\&c^{2}=2 \beta^{2}+\sigma_{winner}^{2}+\sigma_{loser}^{2}\end{aligned} \]

在上述的方程式中，唯一未知的就是选手的表现。另外还有就是游戏的模式。系数$\beta ^2$代表的是所有玩家的平均方差。v(.,.) 和w(.,.)是两个函数，比较复杂。$\varepsilon $是个与游戏模式有关的参数。简而言之，你赢了$\mu$就增加，输了$\mu$减小；但不论输赢，$\sigma$都是在减小，所以有可能出现输了涨分的情况。

怎样进行选手匹配

势均力敌的对手能带来最精彩的比赛，所以当自动匹配对手时，系统会尽可能的为你安排可能与水平最为接近的玩家。TrueSkill评分系统采用了一个值域为(0,1)的函数来描述两个人是否势均力敌：结果越接近0代表差距越大，越接近1代表水平越接近。假设有两个玩家A和B，他们的参数为$(\mu _{A},\sigma _{A})$和$(\mu _{B},\sigma _{B})$，则函数对这两个玩家的返回值为

\[e^{-\frac{(\mu_{A}-\mu_{B})^{2}}{2 c^{2}}} \sqrt{\frac{2 \beta^{2}}{c^{2}}} \]

c的值由如下公式给出

\[c^{2}=2 \beta^{2}+\mu_{A}^{2}+\mu_{B}^{2} \]

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

怎样创建能力排行榜

TrueSkill假设玩家的水平可以用一个正态分布来表示，而正态分布可以用两个参数：平均值和方差来完全描述。设Rank值为R，代表玩家水平的正态分布的两个参数平均值和方差分别为$\mu$和$\sigma$，则系统对玩家的评分即Rank值为 R=$\mu$-k$\sigma$。k值越大则系统的评分越保守。在Xbox Live上，系统为每个玩家赋予的初值是$\mu = 25$以及 $\sigma = 25/3$，k=3。所以玩家的起始Rank值为R=25-325/3=0。