[文章] 硬核!TeD为啥会排世界第七?解密ELO排名算法

作者:西恩war32021-04-12 12:45:18

(作者是一个在谷歌做Google Assistant(Google的语音助手,等同苹果的Siri)的码农,平时会做一些语音识别相关的实验和分析,但不是正牌的统计学毕业生,只是个冒牌的语音识别方向的曾经的研究生/现在的码农,所以如果有错误的话欢迎指出。)

为什么我会写一篇这么技(没)术(人)向(看)的文章呢?

我的初衷是希望带大家了解这个ELO排名系统,让大家知道这个系统的科学性,合理性,以及短板在哪里。

希望经过这篇文章之后,水友们以后看到主播/魔坛等借用ELO排名来讨论选手水平的时候,第一时间不再是是“这个排名系统是辣鸡,明明XXX选手就是玩蛇/下棋而已,不然世界第一没有争议”等等(如果有,你们可以发这篇文章给他们看看)。

作者已经把全部复杂的数学公式全部跳过,我会把论文的链接附在文中,方便有兴趣的同学查阅。

Elo算法的背景

首先Elo(读音是“伊 low”)不是什么魔兽争霸3原创的排名系统,它是由美国物理学家Arpad Elo在1960年代提出的一个排名系统,用以对世界上所有国际象棋选手进行排名,并能够大致根据选手的分数差别来大致估计选手A对阵选手B的时候,有多大概率会赢。

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

物理学家Arpad Elo

时至今日,Elo排名系统已经被广泛运用到各种竞技类项目的排名当中,包括MMA,美国橄榄球,篮球,还有各种电竞项目,比如LOL,CSGO等项目中。(可以参考https://leagueoflegends.fandom.com/wiki/Elo_rating_system 看看LOL是怎么用Elo算法来计算选手排名的)

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

去年6月某一时期的围棋ELO世界排名

现代的Elo排名都是基于原版Elo算法的一种改进,但是都是基于同一个算法框架上的微调,所以我来简单介绍一下Elo算法的框架。

Arpad Elo设计算法的时候,提出一个假设:如果一个选手的真实水平分数是1800,那么他/她在某一天和别人打比赛的时候,实际临场表现的水平分数的概率是一个以1800为中轴的正态分布图:

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

比如这里有两个选手,小蓝和小红。

如果我们只考虑小红,且小红的真实水平分是1700,那么小红打比赛的时候,表现分以1700为中轴线,正态分布向两边减少。

也就是说,小红在某时某地的某一场比赛中表现分为1700分附近的概率最高,而突然鼠标坏了、表现严重失常、表现分仅为1200分,或者打鸡血爆种、发挥超常、表现分达到2200分的概率,就都很低了。

Arpad Elo设计的算法里面的规则就是,如果一个选手A比选手B低400分,那么选手B赢的概率就是选手A的10倍,如果选手A比选手B低800分,那么选手B赢的概率就是选手A的100倍,他定义了一个公式,来判断已知选手A分数和选手B分数的情况下,选手A赢的概率为:

忽略前面的推导过程,反正这个公式就是为了推导出来某一场比赛里面选手A赢的概率。(因为我们前面提过,Elo发明这个算法的时候就是为了排名,并在一场比赛开始之前根据两个选手的Elo分就可以猜一个选手赢的概率)。

然后他同时定义了如何更新一个选手的分数的公式:

新的分数=老分数+K(分数-期望分数)

我们现在用的魔兽3Elo算法

我们这里有请两个工具人选手,来举例一个比较极端的栗子,假设我们有:

菜鸡云玩家选手肥柴48(人如其名48级选手),假设Elo分1600。

很强的选手Infi,假设Elo分2000。

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

假设Infi比肥柴Elo分数高400分(其实实际上高大概3000分吧…不过为了举例)。

按照定义,因为Infi比肥柴高400分,那么如果一场他们俩的比赛里面,Infi赢的概率是肥柴赢的概率的10倍,所以Infi赢的概率大概是91%,肥柴赢的概率大概是9%。

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

这个时候,假设肥柴突然被我猴儿上身,竟然在一场比赛里面赢了Infi,那么,肥柴新的分数应该怎么算?

这个时候,肥柴的新分数就是1600+K(1-0.09),其中1600是肥柴的现在的分数,K是一个预设值,后面会解释,而1代表的是肥柴赢了,他的分数为1,0.09是9%。

也就是说,肥柴最后的分数会加1600+0.91K,几乎吃了整个K,所以分数会暴涨。反过来,如果肥柴按大家所想的,输给了Infi,那么肥柴的新分数是1600+K(0-0.09)。0代表的是实际分数,因为输了他的得分为0,所以他的新分数是1600-0.09K,只减少了K的很小一部分。

同理,Infi在和肥柴打完之后,如果出乎意料的输了,那么Infi新的分数是2000-0.91K,几乎减少了整个K。

如果按预计的赢了,新分数是2000+0.09K,也就是几乎没变化。

就是这样,Elo框架只需要知道对方的分数差距,就能猜测双方的获胜概率。如果出现冷门,会让低分选手快速提分,而正常的“虐菜”,也不会让低分选手的分数快速掉下去。

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

此战过后15sui的ELO积分从2200出头暴涨到了2300分

对于上面提到的K值:K是根据实际应用里面选择的一个值。

如果K设得很大,那么输赢一场分数波动就非常大,优点是可以快速让新的玩家从完全没分很快地平均到他的大致水平。

如果K设置得很小,那么输赢一场比赛区别就不大,这样可以保护一个选手不会因为一场失误而快速掉分。

在实际应用中,K有时候是根据不同分段定义的不同的值,例如在国际象棋世界排名里面就有这个规定,不同段位的K值不同。在魔兽争霸3的warcraft3.info应用里面,作者我联系了warcraft3.info的程序员,可惜的是,当初开发这个Elo页面的程序员已经不再开发这个网站(之前魔坛的新闻也报道过他决定不再开发这网站的推特),所以截至我写文章的时候我并不知道这个K值是怎么定义的。

希望我有一天会看到warcraft3.info的源代码,这样我就能知道他是怎么定义的了,如果我知道了,我可能会写一篇更新文。

ELO算法的改良与发展

上述就是Elo算法了,它的优点就是非常快,新的分数不需要考虑别的选手,就根据A和B现有的分就可以直接算出新的分数。

但是缺点也很明显,比如,我们可以假设每个选手的表现都是正态分布的,但是每个选手的正态分布图都一样吗?

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

Elo之后的其他数学家就给出了这样的模型,如果选手小蓝的正态分布图特别“扁”,小红的正态分布图特别“高”怎么办?

也就是说小蓝选手特别“神经刀”,出现神级表现和打得像40级云玩家的概率比一般选手都大;而小红则特别稳定,几乎水平从来不变,这种情况怎么办?

他们三个,谁最“神经刀”?

如果遇到这种情况,选手A赢选手B的概率就要用更加复杂的数学公式推导了,后人把这种新的算法命名为“TrueSkill算法”。

( https://en.wikipedia.org/wiki/TrueSkill)

总之,就是有很多不同的数学家提出了很多不同的模型。

在2008年的时候,研究员Rémi Coulom发明了“Whole-History Rating算法”,一个基于Elo框架的再改进版,论文地址:

https://www.remi-coulom.fr/WHR/WHR.pdf 。

这个算法被证明,在特定情况下判断一个选手A会赢选手B的概率,比现有的其他算法,都要高一些,缺点是计算时间要更久。但是因为计算概率的准确性,现在被很多职业体育,职业电竞排名使用,比如MMA,国际围棋选手排名等。

我们现在https://warcraft3.info/stats/elo_ranking 上面的Elo排名,就是基于这个“Whole-History Rating算法”。

而在目前(除非我孤陋寡闻了..如果是的话恳请告诉我让我学习一下哈),似乎是估计在某一天选手A能赢选手B的概率最为准确的算法之一。

又是一个看得让人睡着的图,反正这个图就是一个数学模型,它推测的是,如果一个选手A在x轴的第0天分数是r0,那么他/她随着时间的推移(x轴的增加),真实水平的变化有95%的概率是这个躺下来的正态分布图里面包着的。

总之,就是聪明的研究员数学家们,想出来了很多数学模型,来改良Elo一开始的那个选手赢别人概率的猜测。

现在的Whole-History Rating算法,已经基本上是现有算法里面最准确的。

而如果一个选手不打比赛了,但是过了一段时间这个选手又开始打比赛了,这个算法会猜测,这个选手在消失的这段时间里,可能会提高/降低自己的水平,根据这个95%的概率图来增减他赢的概率。

基本上,后来的Elo改进版,都是在改进如何估计某一天A能赢B的概率。这方面有很多数学研究,而魔兽3现在用的Elo也是其中一个最能准确估计概率的模型。

我大概想说的是,并不是像很多水友说的,“随便定义的一个排名”,而这个排名系统,可能确实是我们目前能做到的最好的排名了。

那么问题来了,貌似现在的ELO排名很奇葩?

“为啥VortiX比Lawliet排名还高?好像没怎么见过这人啊?”

“排在第7名的Ted是什么情况?”

硬核!TeD为啥会排世界第七?层层解密ELO排名算法

既然说到这Whole-History Rating算法,算是比较精准的Elo框架下的排名算法,为啥水友还是觉得这个排名很奇怪呢?

了解了ELO排名的基本原理后,大家也可以推测一下发生这种现象的原因。容小码农先喝口小茶,明天中午,码完代码后,继续为大家解密ELO诡异的排名背后的原因~