关于算法:积分等级那些事

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

场景形容：奥运会集体排行榜。
如张三打了 1 场较量，1 场胜利，那么胜率即为 100%，
李四打了 100 场较量，80 场胜利，那么胜率即为 80%，
王五打了 10000 场较量，7000 场胜利，那么胜率即为 70%，

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

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

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

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

Elo Rating System 是由匈牙利裔美国物理学家 Arpad Elo 创立的一个掂量各类对弈流动程度的评估办法，是当今对弈程度评估的公认的权威办法。被宽泛用于国际象棋、围棋、足球、篮球等静止。网络游戏英雄联盟、魔兽世界内的竞技对战零碎也采纳此分级制度。

ELO 算法中文网络曾经有很多文章介绍其利用和原理了，这里仅对已有材料的一个总结，而后加上一些本人的了解。

那么它到底是如何实现对象的评估和排名的呢？以游戏中的竞技玩法积分排名为例阐明。

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

1. 依据积分差计算单方获胜概率；
2. 得出游戏后的积分变动。

计算公式

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 这类曲线进行示意，也能够用多项式，分段函数进行拟合。比方我当初有一组数据别离如下

#X 轴示意积分
10
50
100
300
700
1600
3000
5000
8500
15000
30000
#y 轴示意对应等级
1
2
3
4
5
6
7
8
9
10
11

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

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

参数：

A = 24.7720740473647

B = -0.278796299488484

C = 41979.1135432759

D = -1.31553879280325

相关系数 R2：0.998424922803427

当然，因为游戏中（不仅限游戏）等级皆是整数，没有小数，所以个别采纳的都是点对点拟合，不会波及到这么简单的公式。

回到最后的那个问题，显然 Glicko 算法能更好地解决这个问题。如果谋求用风扇吹空肥皂盒的成果（用最简略的形式解决固定的问题），那就是多引入几个参数建模即可。

参考：

1.《A simple approximation to the Elo chess ratings formula》
2. 艰深讲义：匹配系统核心“ELO”积分揭秘 https://zhuanlan.zhihu.com/p/…
3.https://en.wikipedia.org/wiki…