目前流行的排名系统,主要有Elo, Glicko和 TureSkill 。
Elo Rating System
Elo Rating System中最有名的应该就是由匈牙利人Arpad Elo发明的国际象棋排名算法,MOBA类游戏中lol初期就是采用此算法计算玩家的评分。社交网络中“we are rating girls”后也曾出现过ELO的公式
Elo认定所有选手的表现是有起伏的,也就是有状态之分,但每个选手整体的表现应该是围绕某个水平上下波动,这个水平我们可以量化成一个基准分。因此ELO的假设就是某个个体根据水平反应出的不同表现会成正态分布,个体水平由基准分代表。
因此得出一个玩家获胜的概率P(D) = 1/2 + Integration(标准正态分布函数)(0,D),其近似于1/(1+10^(-D/400))
Elo算法的表达式则为:
假设R(A),R(B) 代表选手A, B 的基准分。E(A)代表A选手在比赛胜利的期望值。
那么E(A) = 1/(1+10^(R(B)-R(A))/400)
我们假设k为浮动系数,S(A)为A在该场比赛的得分,则在一场比赛后R(A') = R(A) + k(S(A)-E(A)).
S(A)= 1, 0, 0.5分别为A获胜,落败,和平局。不鼓励平局的话,可以将平局系数调低,如0.3
关于k值的优化
1.对k可以使用不同分段不同系数来保证高分段的低变化,而中低端局变化相应大一些。
2.还有一种是基于比分给k加上一个margin factor,来加大碾压的分数区别。这样不会影响到S和A,也就不会影响到算法的稳定性。其中一种方法是K = K_A ^ (v*u)。
Glicko
Mark Glickman对elo进行了一系列提升,发明了Glicko算法,该算法主要加入了rating deviation,即RD。竞技游戏中CS:GO是使用此算法。
RD代表了一个玩家评分的准确性,同时等于它的标准差。例如,一个评分1500,而RD是50的玩家分段在1400-1600的可能性有95%。两倍RD值加减基准分即是该选手能力的范围。 而每局比赛后基准分的变化也是取决与RD的大小。所以当一个选手RD很低时(代表该选手的评分已经很准确了),则胜负对他基准分的改变会很小。而当一个选手RD很高时(比如该选手的水平还捉摸不透)。RD值在越来越多游戏之后会逐渐减少,若一定时间没比赛,RD又会随时间增加。
关于Glicko主要分3步,先通过旧RD算出这次比赛使用的RD,再算出新的基准分,由于比赛数增加,再更新一次RD.
具体的算法可以参考维基百科,里面有所有系数的推导和相应的方程。
Glicko-2 算法
这个提出了rating period 的概念,并加入了volatility的参数,来纠正错误的玩家。
True Skill
由于Glicko和Elo最好的应用场景都是1v1的玩家或者战队,但对于多人游戏的支持并没有很好。因此受到了很多玩家的抱怨,微软研究院推出了一个基于Glicko的新的评分系统,不过目前并没有广泛应用。而且Elo/ Glicko的目的是用于更直观的表现一个选手的实力水平,而True Skill被开发的目的则是为了帮助各个游戏的玩家更快找到相应的匹配,所以这两种目的虽然大同小异,在实际实现的取舍上会有些不同。