王者荣耀的匹配设计-埃洛算法
回顾2017年的全球手游市场，腾讯推出的《王者荣耀》斩获了综合收入第二，下载量第三的成绩，堪称国货之光。这款游戏随着用户流量从PC到移动端转移的大潮不断成长，以MOBA（多人在线竞技）类游戏dota、英雄联盟为范本，并加以移动化轻量化改进，覆盖了更碎片的时间，更广泛的人群。
拿自己举例，在玩农药的这一年多中，不知不觉就打到了王者段位，厉害程度相当于超级玛丽8-4吧：）。粗略算来，总游戏时间600-700小时，比今年的半数交往对象还长。
如果把普通应用看做一台二手奥拓，那手游至少是辆大奔吧，本着造不出大奔就先拆大奔的心态，在对这款应用不断的使用和上瘾中，也试图找到一些产品背后的设计。目前觉得比较有趣的几个部分是：匹配，评分评级 ，成长流失。今天讨论一下匹配的部分。
不知道在大家玩农药的时候有没有遇到这些困扰：
- 排位五连胜之后又来了一波七连跪，是不是系统故意给我比较强的对手？
- 排位赛为什么要5个英雄才能玩？匹配赛就不需要阿。
- 为什么匹配会遇到黄金玩家，我明明钻石了阿！
相信你看完今天的会对农药的匹配方法有一个比较具体的认知。
在王者荣耀中，最主要的两种游戏模式是匹配赛和排位赛，匹配是5v5标准模式，相当于基本款，排位赛在此基础上会计算等级排名。从最基本的用户需求出发，无论以上那种模式，当某一用户开启一局游戏时，首先需要为他找到4名队友与5名对手，而这9名用户的选择的依据很简单，就是实力相当。（我们在这里先只考虑单排的情况，因为双，三，五排出现时变量太复杂）
如何去衡量实力相当呢？可以再简化一下题干：当有两名旗鼓相当的玩家进行对决后，对决结果该如何影响系统对他们实力的判定呢？如果能够定量的回答这个问题，那就非常厉害了。目前这个问题的最优解是由一个叫匈牙利裔美国物理学家Arpad Elo发明的，所以被命名为Elo rating system，它最早被用于象棋比赛中，目前被公认为衡量各类对弈竞技水平的权威评价方案，广泛用于国际象棋、围棋、足球、篮球比赛中，以及英雄联盟、魔兽世界、dota等竞技对战系统中。
Elo算法成立于以下前提：
- 每个玩家的表现都符合随机变量的正态分布。
- 无论个人在比赛中的表现如何，球员的平均价值都会慢慢增加。
正态分布可以说是统计学中最重要的分布（几乎相当于万金油了），不论考高数还是考概率论，都一定大考特考。上述提到的例子中，任何一名选手的即时表现都是符合正态分布的，因为选手水准的提高是缓慢的，非一蹴而就的，所以代练，作弊都会对系统造成破坏，严厉谴责。生活中类似的例子很多，比如社会收入分布，人群身高分布等等。
第二个条件可以理解为要求玩家主观上都以提升实力为目的，否则整个系统就失去了意义。
Elo算法的逻辑解释
等级分系统通过计算双方的输赢概率，结合竞技后的结果来不断修正玩家的分数。如果一个较高分玩家赢了，那符合系统的预期，少量分数会从低分玩家方扣除，并加给高分玩家。反之，高分玩家会被扣除相对更多的分数，并把这些分数加给低分玩家。
定量计算：
A和B为两名玩家，R代表他们当前的rating，E为预期胜率，所以EA EB=1。
当比赛结束后，实际胜负值S最多有三种情况，胜（1分），平（0.5分），负（0分）RA’ 为一场比赛结束后的新rating：
K是一个常量，代表一次比赛对于选手得分的影响程度。较小的K值意味着较小的影响，不同的比赛性质与阶段可以选择不同的K值，国际象棋大师赛中，K=16；大部分游戏规则中，K=32。通常水平越高的比赛K越小，为了避免少数几场比赛就改变选手的排名。以上公式的证明不展开。
举个栗子感受一下：玩家A排位分数2000，玩家B1800，那么A的预期胜率为：EA=75.97%，EB=24.03%，如果在实际的对决中（取k=32），A胜利，则A将收获7.7分，B将损失7.7分；B胜利，则A将损失24.3分，B将收获24.3分。可以发现，不同结果出现时，每位选手的积分变量也不同。
算法特点
离散性
Elo 算法只需要知道三个要素即可进行迭代：选手赛前积分，对手赛前积分，比赛结果，计算和理解成本都很低（本质是因为积分操作在公式推导时已经被优化了）
初始态的盲目性
Elo rating中新玩家要达到自的合理的积分范围需要较长的时间，这也是算法不断收敛的过程，在实际应用中，我们常会遇见这样的情况：1新玩家 2老玩家开新号。这时我们就需要其他策略来辅助决策定级，如果这一块做的不好，玩家就会觉得对手太强或者太弱，流失率会增高。反观王者荣耀的排位规则中，最低达到6级，最少拥有5个英雄才可以参加，这其实就是一种辅助定级定手段，让系统能够更准确的定位选手能力。同时，农药的匹配模式是完全按照ELO值匹配队友和对手；排位赛是按照段位水平和ELO值综合评判并匹配的，这也能够解释为什么匹配时你会遇到和自己相差甚至一个大段位的队友／对手了，而排位不会。
当然这个特性也不是全然负面，我们经常看到游戏中代练代打等灰色行业大行其道，如果Elo rating更精确敏感，那作弊就会更容易了。
实际应用中的问题
1. 为什么王者荣耀不直接使用Elo积分反应玩家水平？（dota的天梯积分就是直接使用的elo积分）
其实这完全是pm的小手段，我们会发现当用户的积分稳定下来以后，他对单场比赛的分数增减会越来越无感，这种刺激绝对比不上赢了加星星输了扣星星那么明确和有力，而且将数字转化为文字（黄金白银铂金钻石），更易于传播和理解。本质上，还是对于系统反馈的量化和包装。这也属于我们开头提到的轻量化改进中的一环，产品和用户是互相选择的，天梯积分决定了dota的竞技性，排位段位则让王者荣耀有了普适性，才会被新玩家大群体所接受。
2. 理论中都是1v1作战，那5v5时该如何进行Elo 积分？
就像elo积分本身是一种目前的最优解，复杂变量的处理也有不同的处理方法，具体取决于业务需求，所以以下结论是猜想的，未经证实。
可行的方案可能是：将5名选手的elo 积分的算术平均作为团队积分，再根据不同玩家的单场KDA进行积分加权。但此处并未考虑多人排位的情况，假设出现了直男带妹上分，那以上规则不一定继续适用。而且考虑到不同队伍的排位方式不同，是否还应该进行小团队积分加权？（这些都没有数据支持所以暂不讨论）
3. 还有什么产品用的了类似算法吗？
其实只要满足Elo rating成立前提的场景就可以套用该算法，可以根据业务的实际需求不断调整参数值使其更好地服务于系统。举个栗子：
FaceMash – Facebook前身，由扎克伯格于2003在哈佛大学的宿舍创建。FaceMash是哈佛版美女评选网站，每次将两张女生照片放置在一起，让用户选择哪一位更吸引人。网站引起了轰动，并获得哈佛大学学生的欢迎。FaceMash曾在第一夜吸引了450位访问用户，产生了2.2万页面浏览量，上线几天后被哈佛大学关停。所以这个公式也出现在以扎克伯格为蓝本的电影《社交网络》中：
参考资料：
- 微博：https://weibo.com/wzrydonny
- 知乎：https://zhuanlan.zhihu.com/p/28190267
- wikipedia：https://en.wikipedia.org/wiki/Elo_rating_system
- Google：http://blog.hackerearth.com/elo-rating-algorithm
- 王者荣耀公众号
原文作者：阿厮
既然来了，说些什么？