游戏开发论坛

 找回密码
 立即注册
搜索
查看: 186523|回复: 68

[原创] ELO算法教程

  [复制链接]

16

主题

364

帖子

1223

积分

金牌会员

我的QQ:521117903

Rank: 6Rank: 6

积分
1223
QQ
发表于 2013-10-28 22:29:49 | 显示全部楼层 |阅读模式
本帖最后由 pinkrg 于 2013-10-29 19:13 编辑

ELO是什么?能吃么?
是指由匈牙利裔美国物理学家阿帕德·埃洛创建的一个衡量各类对弈活动水平的评价方法,是当今对弈水平评估的公认的权威方法。被广泛用于国际象棋、围棋、足球、篮球等运动。
埃洛排名系统是基于统计学的一个评估棋手水平的方法。美国国际象棋协会在1960年首先使用这种计分方法。由于它比先前的方法更公平客观,这种方法很快流行开来。1970年国际棋联正式开始使用这个系统。
换言之,就是一个叫ELO学霸,做了一个算法取名叫ELO,大家玩LOL和DOTA的时候匹配就是通过这个算法做的。

ELO不是孙悟空。
As we all know,一个LOL玩家,或者象棋大师,在职业身涯中会因为各种情况导致自身的实力波动,且主观难以控制。比如说,二狗在打LOL的时候突然腹泻,导致无法操作,最后满盘皆输。再比如说,某象棋大师老来得子,春风得意马蹄疾,气势如龙,以摧枯拉朽之势虐爆各种强敌。
我们认为,在某一个人的身上,其生涯实力总体在某一特定水平波动。虽然有可能会出现大波动,但通常情况下出现大波动的可能性较低。

说道这里,我们需要对ELO算法进行假设:
l 某个选手,在某一分段区间内的波动属于正常现象。
l 在某一分段区间内的选手,水平大致相同,胜出的期望也大致相同。

那么在样本量足够大的情况下,我们可以认为,出现异常情况(期望胜率大于50%时失败)是可以被允许的。

上图杀猫!
FIDE.png
这是国际棋联FIDE所用200为一分段的Rank区间。弄一个称号显得高大上,信达雅。


不是学霸不要紧,看到公式不要怕!
*这一章的公式比较多,看起来很复杂,但是跟着楼主的思路慢慢走,你会发现其实很简单,千万别着急。

想必大家都知道,其实高手不一定总能赢比他弱一些的选手,就比如LOL钻石1的选手不一定每次都能赢钻石5的选手,因此ELO先是采用了统计学的正态分布函数来表示一名选手在比赛时的波动表现。在这个奇妙的函数中,隐藏着另一个叫做“正态概率密度”函数,虽说长得有点难看,各位就将就一下:
111.png

但是经过多次的模拟和分析,学霸ELO发现其实选手在比赛中的表现更接近于逻辑斯谛分布,因此有了下面这个看上去好看一点的推导公式:
A对B的期望胜率:
反之,得到B对A的期望胜率:
最终,我们得到这样一个最简化公式:(后面和有一个附加值公式,我们先分析这个)
222.png
Sa表示队伍A的比赛结果,胜利S值为1,平局S值为0.5,失败S值为0
Ra(A’s RankScore):表示队伍A当前的Rank分
Rb(B’s RankScore):表示队伍B当前的Rank分
D=Ra-Rb:就是A和B的Rank分差
Ea:表示A在这场比赛中的期望胜率
Eb:表示B在这场比赛中的期望胜率
则有Ea+Eb=1,上式中P(D)=Ea

出题的时间到了,各位同志们注意看!
狗蛋LOL2000分,铁锤LOL1950分,父子局SOLO,那么狗蛋成为爸爸的概率多大?
由上式推得,狗蛋Ra=2000,铁锤Rb=1950,那么D=Ra-Rb=50,那么:
QQ截图20131028211834.png

也就是说,狗蛋能成为爸爸的概率是57.1%,同时狗蛋也会有42.9%的概率成为儿子。
继续大图杀猫:
下图是对D所有取值的胜率期望表

QQ截图20131028212950.png

守关Boss就在眼前,各位同学,切勿掉以轻心!
如果在多次比赛中,实际上我们真正要通过P(D)计算的是另一个变量,暂且将其称之为W(win),不过由于P(D)实际上是计算的期望胜率,因此必须让W带上e变成我们需要的We(预期胜率和)
多场比赛后,一般为
QQ截图20131028214603.png
我们为什么不用W?因为W是实际得分率,下面会用到。
W作为实际得分率,有且只有三个取值
胜利:100%=1
打平:50%=0.5
失败:0%=0
此时还不够,因为我们必须要为不同分段的选手们引入一个常数K,这个常数的作用暂时不表,留作课后习题。
天空一阵巨响,公式闪亮登场
QQ截图20131028214333.png

Rn:赛事后的新Rank分
Ro:赛事前的原Rank分

出题时间又到了,同志们别开小差!
狗蛋和自己的小伙伴们参加了街道举办的小学生杯LOL锦标赛,他们的队伍Rank分是2000分,比赛中遇到了土蛋(2150分),野蛋(1870分)和铁蛋(1920分)队。最终,狗蛋队凭借超人的意志力和娴熟的操作,战胜了野蛋和铁蛋队,但是遗憾地输给了土蛋队。那么经过这次举世瞩目的比赛,狗蛋队最终的得分是多少呢?(此处,赋值K=20)
通过读题我们发现,W=0+1+1=2(负1胜2)
那么最核心的一步就是计算We了:
1.png
2.png
3.png
然后我们再带入公式:
Rn=2000+20×(2-1.589)≈2008
狗蛋队最终得分是2008分。

有关ELO算法的讲解到此结束了,在课后,我会留几道题目给大家。再此之前呢,我还要把最后一点东西讲完,希望大家不要厌烦。
为了防止某一个玩家连胜,或者连败,为游戏和用户体验带来消极的影响,我们会在Rank分中加入一个临时常数Ri,该常数在匹配时会使玩家匹配到更低或者更高的分段,并且在Rank分差D=Ra-Rb-Ri中体现。这个常数的引入有什么好处就一并留作课后思考吧。

1. K取1和100时会出现什么样的情况?
2. K的取值大小会对Rank分造成什么影响?
3. K的取值大小在游戏中实际对玩家造成了什么影响?
4.我们应该如何为K赋值?

本文不允许任何形式的转载。
国际棋联.jpg
QQ截图20131028212950.png
EB.jpg
EA.jpg

98

主题

784

帖子

4493

积分

版主

Rank: 7Rank: 7Rank: 7

积分
4493
发表于 2013-10-29 09:54:16 | 显示全部楼层
pinkrg 发表于 2013-10-29 07:29
。。。我看了一下你给的链接,相似度很是相当低的,理论基础基本一样,一个2007年的帖子和一个2013年的帖 ...

我倒是觉得那贴说的简明扼要,看你的发帖你也不了解他为什么成为这样,就像1+1=2,你也不知道为什么,但是你就是认定了1+1=2的,已经被公认为科学了,所以运用就好了,不然不来搞游戏了,而是去搞数学了。
我倒是觉得你这帖的整个分析不如直接把这个nga的连接发出来来的实惠,毕竟你没有在elo的基础上做出什么突破,说到头还是个运用,这个运用既没有代码支持,也没有实际的逻辑运用范例支持,我不知道价值在哪儿,至少07年的那贴还有个范例就是WoW本身,我相信玩过WoW的策划还是在多数的。
有些理论知识你根本不必去深究他为什么是这样的,如果他工作完好,那就在这个基础上探索新的用法就好了,WoW的K定为32没出什么大问题,我觉得我如果要做一个竞技平台的话,就套用这个32好了,前人都验证没问题了,而且这并不是一个游戏的核心所在,连0.00001%都占不到。而开发这样的平台显然是不适合国内现在的环境的,至少对我们的团队来说没法挤入这样的市场,相信99%的团队都是一样的情况,所以这个理论其实毫无意义。
我觉得一个策划的能力并不是在炫耀他知道多少基础,而是在于他的逻辑能归纳出多少新的机制,这些机制可能是前所未有的,也可能是很多人已经在用了但大多是偏方,并且这些机制可以沿用与之后所有游戏的开发,比如Buff机制。而谦虚的策划则应该这个已经在多个项目中成功运作的基础上继而研究,完善并突破这套机制用在更多的游戏中,并且发布出来,好让别人继续要救并突破,这就是成长。程序界的成长和积累几十年来都是这么来的,而游戏策划相关的,新人还不如10年前,大多新人即不谦虚也很无知,更谈不上去研究一个别人的机制并且去进化了。
而对于整个项目来说,我雇佣一个策划,不是让他在这种东西上浪费时间的,我认为从一个项目的角度来说,这种可以用别人已经稳固的东西就用,我们没有足够的金钱和时间去创造数学原理,我们要把时间用在积累更好的用户体验,包括操作感,游戏整体感觉,游戏UI等产品相关的地方。
elo机制是不会错的,所以我们运用,如果我们的用法(对于K的定义)有问题,那就沿用别人证明没问题的用法,这个就好像AStar,最简单的估价也是最常见的、最有效的、最确保准确率的一定是曼哈顿算法。一个项目没必要去为这个浪费时间,我们毕竟不是国家扶持着让你3年做个手游的团队,我们是2个月产一个项目的团队。

点评

顶一下这个精彩回复  发表于 2018-9-9 19:39

16

主题

364

帖子

1223

积分

金牌会员

我的QQ:521117903

Rank: 6Rank: 6

积分
1223
QQ
 楼主| 发表于 2013-10-31 18:54:01 | 显示全部楼层
独孤逍遥 发表于 2013-10-31 17:00
学习了!

客气了。

2

主题

135

帖子

634

积分

高级会员

Rank: 4

积分
634
发表于 2013-10-29 00:26:24 | 显示全部楼层
有个问题:以前版本的WOW竞技场也是用的ELO算法(我记得K值好像是32),但赛季结算时冠军的积分可以高达2800+甚至3000。而国际象棋能达到2600分以上的人凤毛麟角。是因为WOW竞技场的比赛场次远远多于国际象棋么?

98

主题

784

帖子

4493

积分

版主

Rank: 7Rank: 7Rank: 7

积分
4493
发表于 2013-10-29 07:08:07 | 显示全部楼层
本帖最后由 猴与花果山 于 2013-10-29 07:16 编辑

我的天,看了下日期是最近的,吓了一跳,还以为谁挖坟了,NGA上这个帖子可是08年那会WOW开JJC时候就有了的……http://bbs.ngacn.cc/read.php?tid=1284872
NGA的原帖,2007年的……比我记忆的还早,所以惊讶的以为这是坟贴

98

主题

784

帖子

4493

积分

版主

Rank: 7Rank: 7Rank: 7

积分
4493
发表于 2013-10-29 07:13:57 | 显示全部楼层
Qzzz 发表于 2013-10-29 00:26
有个问题:以前版本的WOW竞技场也是用的ELO算法(我记得K值好像是32),但赛季结算时冠军的积分可以高达280 ...

WoW的确是因为场次多,虽然我们没打到过2800+,但基本每个赛季都能到2600+在TF\MF\国服都是,那时候我们周末基本上2天至少要打100场,由于很多时候会出现肾斗士状况,所以没能打更多。2450开始偶尔会遇到赢了只有1分的队伍,一般都是获胜8分左右,输了24分左右。
ELO算法其实对于游戏而言,BLZ用的很好了,确切的说Tom Cadwell用的很好,所以LoL还是沿袭这套,所以如果你真要做排位等,也可以直接沿用就好了,甚至可以不知道这个原理,只要知道一个计算公式就OK。

16

主题

364

帖子

1223

积分

金牌会员

我的QQ:521117903

Rank: 6Rank: 6

积分
1223
QQ
 楼主| 发表于 2013-10-29 07:29:57 | 显示全部楼层
猴与花果山 发表于 2013-10-29 07:08
我的天,看了下日期是最近的,吓了一跳,还以为谁挖坟了,NGA上这个帖子可是08年那会WOW开JJC时候就有了的 ...

。。。我看了一下你给的链接,相似度很是相当低的,理论基础基本一样,一个2007年的帖子和一个2013年的帖子去解释1960年的理论,我觉得还是我做的比较好,猴子你觉得呢?

16

主题

364

帖子

1223

积分

金牌会员

我的QQ:521117903

Rank: 6Rank: 6

积分
1223
QQ
 楼主| 发表于 2013-10-29 07:39:15 | 显示全部楼层
Qzzz 发表于 2013-10-29 00:26
有个问题:以前版本的WOW竞技场也是用的ELO算法(我记得K值好像是32),但赛季结算时冠军的积分可以高达280 ...

这就是为什么最后我留了K值得课后题。K值处于一个浮动状态,当大于2400分之后,K值会缩小,一般2400分以后,我们会将K值缩小到8左右。

国际棋联中得到过2800分以上的人屈指可数的最主要的原因还是场次。一年大不了几场比赛,非JJC一天就要打几十场,冲五字角斗士的时候和刷子拼了个不眠夜,分数的确容易更高。

16

主题

364

帖子

1223

积分

金牌会员

我的QQ:521117903

Rank: 6Rank: 6

积分
1223
QQ
 楼主| 发表于 2013-10-29 07:42:04 | 显示全部楼层
猴与花果山 发表于 2013-10-29 07:13
WoW的确是因为场次多,虽然我们没打到过2800+,但基本每个赛季都能到2600+在TF\MF\国服都是,那时候我们 ...
ELO算法其实对于游戏而言,BLZ用的很好了,确切的说Tom Cadwell用的很好,所以LoL还是沿袭这套,所以如果你真要做排位等,也可以直接沿用就好了,甚至可以不知道这个原理,只要知道一个计算公式就OK。


这样的理论倒是让我觉得猴子你蛮有意思的。不知道一个理论是如何来的,只要知道公式就行了,你的数学老师成功了。不知道ELO,你怎么拿他和Trueskill比较?还是说继续像你说的,只要别人说好,我们用就是了,看wow不是用的挺好么?呵呵。

0

主题

80

帖子

890

积分

高级会员

Rank: 4

积分
890
发表于 2013-10-29 09:38:38 | 显示全部楼层
不明觉历  倒是可以直接拿来用的 虽然不知道最初的那个公式怎么推导来的 请问LZ  有个公式里面的X那是什么

0

主题

8

帖子

102

积分

注册会员

Rank: 2

积分
102
发表于 2013-10-29 09:58:40 | 显示全部楼层
老孙来也 发表于 2013-10-29 09:38
不明觉历  倒是可以直接拿来用的 虽然不知道最初的那个公式怎么推导来的 请问LZ  有个公式里面的X那是什么 ...

貌似没用的样子...
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2024-10-5 11:24

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表