积分等级那些事

之前看到有人求助一个积分算法，这里的积分不是微积分里的积分，准确来说是等级积分算法。

场景描述：奥运会个人排行榜。如张三打了1场比赛，1场胜利，那么胜率即为100%，李四打了100场比赛，80场胜利，那么胜率即为80%，王五打了10000场比赛，7000场胜利，那么胜率即为70%，

如果按照胜率排名：张三>李四>王五，显然不合理，打的少的概率反而高了，还有没有好的排名算法，求指导 www.oschina.net/question/22…

这个问题是个不错的问题，早年我自己做小游戏的时候也摸索过。此问题下面的回答也有人提到了Elo，今天就讲讲这个算法。

可能有人热衷《王者荣耀》这样的游戏，虽然我对腾讯系的游戏毫无好感，也从没玩过，但听过一二。有时会看到有人发牢骚，王者排位五连胜后遭遇九连跪，是不是游戏操控胜率？又有人会想到，我能不能在高段位去虐新手刷积分，这其实都是积分等级制度需要考虑的事情。

其实在对战类的游戏里，是有一套既定的积分制度的，那就是 Elo Rating System。

Elo Rating System是由匈牙利裔美国物理学家Arpad Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估的公认的权威方法。被广泛用于国际象棋、围棋、足球、篮球等运动。网络游戏英雄联盟、魔兽世界内的竞技对战系统也采用此分级制度。

ELO算法中文网络已经有很多文章介绍其应用和原理了，这里仅对已有资料的一个总结，然后加上一些自己的理解。

那么它究竟是如何实现对象的评价和排名的呢？以游戏中的竞技玩法积分排名为例说明。

Elo会赋予每位玩家一个相同的初始积分，并进行以下计算：

根据积分差计算双方获胜概率；
得出游戏后的积分变化。

计算公式

EA：玩家A的胜率期望值 EA=1/{1+10^[(RB-RA)/400]} EB：玩家B的胜率期望值（可以看出，EA+EB = 1） EB=1/{1+10^[(RA-RB)/400]}

R’A=RA+K(SA-EA)

其中： RA：玩家A当前积分 RB：玩家B当前积分 R’A：玩家A游戏后积分 K：常量系数，后文会说明具体作用 SA/SB：实际结果胜负分，胜 = 1，平 = 0.5，负= 0

演算过程：

假设两位当前积分为RA = 1900，RB = 1500的玩家相互竞技时， EA = 1/{1+10^[(1500-1900)/400]} ≈ 0.91 EB = 1/{1+10^[(1900-1500)/400]} ≈ 0.09

我们来看图

可见，当双方积分达到400（1900-1500）分的分差时候，A的获胜概率是91%，B的获胜概率则很低了。而分差为0时，则各有50%的胜率。

然后就是计算对局后的得分了，当K = 32时，假设玩家A胜出，SA = 1，SB = 0，则：
R’A = 1900 + 32*(1-0.91) ≈ 1903，玩家A获得3分
R’B = 1500 + 32*(0-0.09) ≈ 1497，玩家B失去3分

分母中的400：

为什么是400，而不是100、200或者1000呢？

从积分差上看，这个值影响着对战双方的获胜期望。当双方积分差相同时，这个值越大，双方的获胜概率越接近。当这个值等于400时，若双方分差为100，积分较高的一方获胜期望约为64%。

还是没解释为什么这个值就非得是400。我看了下相关英文paper，没找到其出处。我认为400是Elo本人选择的，是基于整个国际象棋的积分制度对应得出来的一个参数，也不是非400不可。作为参考，国际象棋积分制度规定，2005分是起点积分，当今男子最高水平一般2750以上为超一流，极少数在状态巅峰时超过2800（例如小卡、克拉、托帕、阿南德等曾超过2800）,2700以上为国际一流。大多数国际特级大师2500分以上。职业棋手至少能达到2200以上，业余强手可达在2000分左右，一般爱好者在1700－1900不等。

K常量：

不难看出K值越大，单次评价的积分变化幅度越大。那么K值的设定应该遵循什么规则？

一般而言，分段越高，K值越小。如此设计，能够令玩家的积分在前期快速趋近其真实水平，同时避免少数的几场对局就改变顶尖玩家的排名。

所以K值的选择取决于，这个游戏需要以什么样的方式来统计选手的积分，并根据玩家、玩家数量之类的参数微调。

优缺点

从Elo的工作模式中我们可以得出以下几点：

1.Elo会给出玩家一场对局的获胜概率。Elo积分相差越大，积分高的一方获胜概率就越大；

2.每一场对局后，对阵双方都会进行一部分积分交换，胜者得分，败者失分；

3.如果两名玩家的积分相差很大，代表高分方获胜的概率极大，因此即便赢了也涨不了多少分，败方也掉不了多少分。但倘若被低分方爆出冷门，那高分方将失去大量分数。

Elo Rating System的缺点

任何算法系统都有优缺点，Elo也不例外。

初期的盲目性

Elo积分在达到合理（趋近真实）水平之前需要一个过程。比如一个2000分的玩家玩小号，遇到的对手大概都是1400分水平，这时候Elo积分是不能准确反映他的实力的。经过几局对战，这名玩家的积分会逐渐达到合理水平。这个过程就是Elo积分的收敛过程。

对时间不敏感

Elo积分不会随着时间变化，当一位玩家很长时间没有游戏的时候，他的水平可能会上下浮动，但他的Elo积分并不会随之改变。尤其对于顶尖玩家而言，这时候的积分排名未必能反映玩家间真实的实力排名。针对这个问题，Glicko积分系统则做出了改进。

推导过程和更一般公式

看到有文章说ELO是根据正态分布求积分，然后用最小二乘法推导出来的，由于原博客缺少了一些关键步骤，我也无法得出原作者“显而易见”的推导过程，原文章也没有给出400这个数值的推导由来，有“显而易见，众所周知”之嫌疑。故不做详述。但根据已知论文，其描述的推导过程大方向应该是没问题的。

更一般的积分公式

对于更一般的情况，比如腾讯的体系是4颗星星一个月亮，4个月亮一太阳，每一级都和在线时间有个关系，当等级越高的时候升级越慢。

但是这种等级算法不应该是一条直线，其应该满足以下规律： 1.随着等级的提高，升级越来越慢，不然就会出现几百级这种情况，容易让玩家疲倦和失去探索乐趣； 2.积分算法在外人来说，不容易猜到； 3.算法有一定复杂度，但又不是很复杂。

其基本原则就是找一个收敛较慢的函数。

举个例子来说，对数函数y = log(a)x，其中a为底数。当a>1的时候，函数的曲线是一条单调递增的凸曲线，它的增长是越来越缓慢的。

这样的话，只要你的分数计算函数是类似这样的凸函数就可以了。考虑到希望函数本身不易被猜中，可以把多个满足这样条件的函数直接加起来合成一个新函数。

补充：这样的函数一阶导数总为正数，二阶导数总为负数。如果想不到好的函数，可以自己积分。

除了使用log，arctan这类曲线进行表示，也可以用多项式，分段函数进行拟合。比如我现在有一组数据分别如下

对此进行一次四参数拟合，得出方程如下：

拟合方程式：Y = (A – D) / [1 + (X/C)B] + D

参数：

A = 24.7720740473647

B = -0.278796299488484

C = 41979.1135432759

D = -1.31553879280325