排名算法简介

Posted by c cm on September 1, 2014

想要知道一个player的水平如何,最简单的方式就是看他的排名。比如FIFA World RankingsWTA Rankings等等。这些竞赛排名通常会与胜负率、比赛的重要程度、参与比赛的场数有直接关系,往往不能反应player的“真实”水平。

ELO

ELO最初是象棋使用,社交网络中“we are rating girls”后也曾出现过ELO的公式。

社交网络elo公式

何解?假设妹子A和妹子B的貌美如花程度分别为Ra(Rating a)和Rb,初始情况下设Ra = Rb = 1500。在经过一轮打分后,将咳咳妹子分数的一部分拿出来奖励给漂亮妹子。分数的update公式为:

= 更新后分数

= 更新前分数

= 分数变动的最大值

= 实际打分结果(1 if win, 0 if lose, 0.5 if draw)

= 期望打分结果(就是图片中的公式啦)

举个栗子

那么 ,

计算容易得到,400分的差值代表91%的胜率,200分的差值代表76%的胜率。

如果A赢,则

如果B赢,则

可以看到,,在A赢得91%概率的情况下,B输的代价并不大,而A输的代价则大得多。这些都是由公式根据AB两者分数差值大小决定的。

ELO中的最大主观因素在于K值的选取。在象棋中,一般认为master表现水平稳定,K值应该较小(16),而新手表现波动较大,K值应该更大(32)。当然,如果对不同人取不同K的话,的关系就不一定成立了。

Glicko

Glicko对ELO做出的最大改进是引入了分数的波动,即Rating Deviation(RD)。

STEP1 计算RD

如果第一次play,初始化为

否则

其中
t = 玩家从上次比赛到现在间隔的时间
c = 用来控制玩家uncertainty的一个常数,
距离上次比赛的时间越长,选手的变动越大,最小不小于350。

STEP2 计算


其中

是一个随RD递减的函数

,当对手时,与ELO的Ei等同

越小,越大,越不确定(越靠近0.5),越大,越小。

举个栗子


首先假设



如果A赢,那么

如果B赢,那么

Stephenson

挖坑

TrueSkill

挖坑