《皇室战争》天梯机制探究：“匹配杀”算法解析

写在最前面的：皇室战争的天梯分数使用的是ELO算法，我会大致的介绍一下该算法的思想。 Supercell的团队会对原始ELO算法做一些调整(比如对W值重新定义与K值的调整)，但是根本思路是不会改变的。 为了保证文章尽可能的通俗易懂，我会尽量减少推导与公式的部分。 在理解了该算法的思路之后请各位自己思考一下匹配杀的可能性，我也就不再赘述了。 P.S.文章有复制的内容，会在最后标在参考文献里。 写在最前面的结论 如果一名选手的实际ELO分数与天梯ELO分数相同(即天梯分数就是其真实水平)，并且ELO天梯存在所谓“匹配杀”机制，那么无论是对这名选手进行“匹配杀”还是由这名选手对对手进行“匹配杀”都会影响其胜率，进而放大其ELO分数的误差区间，使得该ELO机制变得无法准确判断选手的真实实力——这与 ELO算法的设计意图相违背。 所以并没有什么所谓的“匹配杀机制”存在。 ELO等级分的由来 ELO等级分体系是根据它的推广者埃洛(elo)教授名字命名的，它是一种以数值表示的体系，将等级差别转化为分数或取胜概率，反之亦然。当今多数竞技项目的等级分体系都是建立在ELO体系之上的，如国际象棋、围棋、台球等。 国际象棋等级分与称号没有必然的联系，但等级分由于是根据比赛成绩进行一定的科学计算得来的，随着比赛次数越来越多，就越来越准确地反映出一个人的真实水 平。而称号是通过参加一些比赛，根据规定按照获得的名次而申报的一种头衔。等级分的计算后来被国内的围棋及象棋引入，但影响力远没有国际象棋大。 在埃洛的等级分系统之前，世界上有许多类似系统，有些是数字式的，有些则采用其它的方式。比如：在二十世纪三十年代，美国通信国际象棋联盟(The Correspondence Chess League of America)就有自己的等级分系统；而在欧洲，INGO系统则非常流行；美国国际象棋协会(USCF)也有一套由肯尼斯.哈克尼斯 (Kenneth.Harkness)发明的等级分系统。埃洛则提供了一套全新的系统。它具有一些直观特性(如：1500分表示一名普通棋手，2000分 表示一名俱乐部强手，2500分则代表一名国际特级大师级棋手)。同时，该系统又是依据统计学的基础设计的，这对于系统的可行性非常重要。显然，如果一套系统不能准确反映棋手真正实力的话，那么它将毫无用处。

1960年，美国国际象棋协会(USCF)采纳了埃洛教授的等级分系统。国际棋联于1970年也采纳了这套系统。 ELO等级分的原理 ELO等级分的计算则是从一个时间点开始有一个初始分，然后随着每次比赛，根据比赛结果和对手的等级分，进行自己等级分的修正，进而在多次比赛后收敛得到接近选手真实水平的积分。 即使粗略看比赛成绩表，也能够看出选手的表现是有起伏的，也就是有“状态”之分。强手未必恒定表现好于弱手；每人之状态在不同的日子不同的比赛里都会有好 坏不同。而总的来说整个生涯里每一点上，一名选手的表现将大致围绕在某个平均水平上下波动，有时会有背离，而出现大背离的情况比出现小背离的情况频率要低。于是我们有了ELO体系的第一个假定，用标准统计术语表述就是：可以建立这么一个等级量表(rating scale)，某个体在这个表里的不同表现将正态分布。 第二个假定牵涉到了等级量表区间间隔的定义。简单地说，在某一个特定的实力范畴里，尽管可能存在实力上的差异，但总的来说可以预期没有谁比谁好或差很多。由此可以定量划分区间。

等级量表 ELO体系使用一个叫“区间尺度”(interval scale)的定义，即等级差别是可能性方面的唯一重要因素。这是指对阵双方谁有多大机会胜/负/和，唯一影响因素在于他们之间的等级差别，这样排除了难以确定的“状态好坏”(第一假定：个人的总体表现大致是正态分布的)，也排除了具体谁对谁的影响(第二假定：某一特定实力范畴里，相互之间的差别一般可预期不会出现太大意外)。 因 此即使出现“爆冷"或“克星”，也视为偶发情况，因为ELO体系是建立在样本足够大量的统计基础上的。而且个体的等级也是动态反映的。有一个概念叫“标准 分类间隔”(class interval)，简单说就是某一个等级里最高与最低之间的差别。在国际象棋里，FIDE(虽I]国际棋联)采用每200分为一个间隔的分类法，并且给 每一个间隔取一个名字或排名以更好分辨。FIDE的等级分分隔表中，将1700分选择作为普通水平业余棋手的实力值，将2000分选择作为区分大师与业余 者之间的分界线。 关于第二假定的另一个表述方法：在某一分段区间内的选手，水平大致相同，胜出的期望也大致相同。 那么在样本量足够大的情况下，我们可以认为，出现异常情况(期望胜率大于50%时失败)是可以被允许的。

正态分布函数

我们知道，强手未必总是胜过弱手，于是就使用一个“正态分布函数”(Normal Distribution Function)来代表一名棋手的波动表现，这是统计学上的概念。 从这个函数里可以得出另一个函数叫“正态概率函数”(normal probability function)，这个就定义了根据比赛对抗结果可得出的等级差别，或者根据已知的等级差别可得出的预期比赛对抗结果。它是这样的：


值，就是以等级分差别D为自变量计算出来的预期取胜可能性(预期得分率)，因为选手在比赛中的表现更接近于Logistic分布，它可近似用下面这个公式来计算：


于是我们可以把典型数值事先都计算出来编成一张表，到时要计算等级分变化时只需查表找出对应数字就是。它叫“百分比预期值表”(Percentage Expectancy Table)，简称PE表，如下图所示。


举例：当A的ELO分比B高100分时，查表可知A与B对战时A的胜率为64%，B的胜率为36%。当前等级分公式表现等级分公式，假如用在一个长时期里，就不能精确反映棋手的实力了。更精确的方法是把各表现等级分综合计算以尽可能正确反映棋手的当前实力。所形成的数字就叫棋手等级分(player rating)或简称等级 分(rating)。(当然也会有些偶然变数，但没有表现等级分那么明显。)


其中：Rn是赛事后的新等级分；Ro是赛事前的原等级分；K是单局得分的等级分点值，它是一个系数，取值有约定的；W是实际对局得分(胜得1、和得0.5)；We是在原等级分基础上的预期对局得分。 这个公式是用来在连续基础上(也就是每局或每个赛事之后)计算新等级分的。它把最新的表现调整考虑进先前的等级分中。 它的逻辑意义是一个棋手的表现高于他的预期得分以及低于他的预期失分。 因 为在皇室战争中平局双方奖杯数都为0，所以Supercell应该把这部分的公式改得更加简单了——W实际对局得分改成“胜得1、负、和得0”，而K的取 值是一个可以自己定义的分段函数，这我们就不知道了。我自己计算的结果是在3000杯以上，K的值在17.5左右，仅供参考。 并且从公式中显然可知在一次对战后双方的增加杯数与减少杯数并不一定相等。 魔 兽世界：早期竞技场的K值应该在32(超过2200可能在16)，队伍的积分即是匹配分，不太高的K值导致积分收敛性强，即积分2500+的积分已经排到 参与人数前1%。积分的最高值更加取决参与人数。新版本的竞技场匹配分与实际积分已经分离，这样做主要是为了队伍更好的定位(高分队用更少的场次进入到自 己的积分段，冲击更高的分段)。 DOTA2：大体猜测采用的是均衡的K值，通过估分系统玩家的起始积分在(2500-4500)附近，每 场比赛结束默认分差为25(赢了加25分，输了扣25分)。比如每次匹配都是实力一致的选手，即胜率0.5，那么K=50(实际情况会复杂的多，多人组 队，跨积分段匹配，低分抱大腿之类)。按现在玩家数量7000分(2015年9月27日)可以排到前500，再过一年随着玩家数量的增多，7000分可能 只能排到前1000甚至2000。

ELO排名的特点与不足

ELO积分具有离散型，它一直伴随着选手的，选手的每一场比赛过后，埃洛积分根据比赛对手的埃洛分和比赛的结果对选手的埃洛分进行修正。所以新的埃洛分的计算只跟三个因素有关： 选手赛前的埃洛分 比赛对手埃洛分 比赛结果 每个选手从最初进入评价系统中开始，都会有一个初始等级分，而这个初始等级分与这个选手的水平之间还没有开始建立任何联系，选手需要在评价系统中进行几场甚至几十场的比赛后，他对应的等级分才能逐步趋近与其真实水平。 那么在选手对应的等级分趋近于其真实水平之前的比赛中，等级分就不能够反应其实力了。 假 如选手A和选手B的ELO分都是1700分，真实情况也还是有可能二者的竞技实力还是相差较多。假设选手A只进行了较少的比赛就将ELO分提升到1700 分，而选手B则是进行了很多场比赛，最终ELO分稳定在1700分左右。那么这时，选手A的ELO分就是不稳定的，还未收敛的，也就是说，选手A的ELO 分还没有通过足够的比赛来反应其真实的实力，还需要若干比赛的结果来稳定ELO分。 这也不是说选手B的ELO分稳定下来了，选手B的收敛过程就结束了。选手B可能通过研究卡组，提升技术，氪金，提高了自己的水平，这时，他通过比赛自己的ELO分又会重新从稳定进入收敛过程。所以说，收敛过程在等级分机制中是一直存在的。正是由于收敛过程的存在，会让ELO分对选手真实水平的反应，在一定范围内不是那么准确。

ELO的群集递减

从应用等级分评价体系的比赛项目团体的角度来看，选手都是从初始等级分进入系统的，而AFK后则一般携带较高的等级分离开系统，所以，随着等级分机制的运转，群体中的总体等级分是由减少的趋势的。


图为2007年1月到2010年1月国际象棋棋联注册棋手的等级分分布情况，左图为真实数据连成的曲线图，右侧为拟合后的图形。可以看到从2007年到2010年每年棋联总体的等级分都是呈减少的趋势的。 而在CR中因为用户的持续增多所以会导致ELO分数和不断暴涨，使得每个区间内的分数差的判别能力贬值，所以SC引入了赛季重置的机制，保证游戏中ELO的分数和不会因为用户暴增而膨胀过多，使得在每一个赛季中依靠ELO分的判断选手能力的标准不会有大的变动。 如果在将来CR的新加入用户数量所增加的ELO分数无法维持住当前的ELO总和时，Supercell只需要调整上述公式中的K值即可对CR的ELO系统做出动态平衡。 PS.根据某坊间更新泄露，有可能会在4000杯以上增加一个杯数收益减半的奥林匹斯竞技场(真伪未知)，如果这是真的，Supercell只需要将处于该竞技场的玩家的K值减为传说竞技场的一半即可(加分减半扣分照常的话则需要继续讨论)。 最简单的自动匹配算法与皇室战争匹配机制猜想 由ELO算法的设计思路可知，ELO系统的核心理念是将等级差别转化为分数或取胜概率，反之亦然，如果在匹配中进行所谓“克制卡牌”的“匹配杀”，这就与ELO算法的基本思路相违背，无法形成一个ELO天梯环境。 为了让天梯环境中的选手们自动的尽快进行比赛，我们需要有一套自动的匹配算法，让空闲没有进行比赛的选两两结对进行比赛。

在 天梯环境中，我们采用的方法是在匹配队列中取出第一个节点，找到与之分数最接近的一个节点，然后将两个节点取出进行比赛。一直这样操作，直到匹配队列为 空。一旦匹配队列为空，或者只剩一个节点，那么一轮比赛就结束了。我们可以让这样的循环不停的继续下去，那么就模拟出了一套使用ELO等级分进行评价的天 梯环境了，流程图如下。


这是一个最简单的天梯自动匹配算法，而SC的实际算法比这个还要稍微复杂一点，以下为我做出的SC匹配算法机制的猜想。 由SC之前出的关于维护高杯段天梯环境的公告与钟老板的实测视频，我们可以知道SC的天梯匹配对上述算法加了一个最短重复匹配间隔来遏制送分，即：在A与B对战后至少要与另外3个人进行对战才有可能重新匹配到B。 根 据经验，为了提高ELO分数的收敛速度，真实水平高于其ELO分数的玩家更有可能连胜，而连胜的玩家更有可能遇到ELO分数比他高更多的对手以加速其 ELO分数向其真实水平分数(向上)收敛。而根据百分比预期值表，该玩家的胜率则在不断降低，更有可能失败。当连败时，有可能其ELO分数已经高于真实水 平的ELO分数，所以该玩家更有可能遇到分数比他低的对手加速(向下)收敛，机制与连胜时同理。(不过因为连败时的心态影响会导致水平波动，参见“正态分 布函数”段，所以这就可以解释虽然连败时玩家胜率根据百分比预期值表在不断增加，但是因为实际ELO水平因为水平波动而下降所以导致真实胜率并不如预期表 上的高从而导致连败喷几百分——头脑冷静后再一路打回这几百分。)

相关阅读：《皇室战争》体验报告：游戏时长被无限拉长