乐趣区

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

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

场景形容:奥运会集体排行榜。
如张三打了 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…

退出移动版