关于比赛评分和排名的算法分析

Kaggle 积分

Kaggle 是一个数据建模和数据分析竞赛平台。企业和研究者可在其上发布数据,统计学者和数据挖掘专家可在其上进行竞赛以产生最好的模型。用户以团队形式参加 Kaggle 的比赛,团队可以仅包含自己一人,根据在每场比赛中的排名不断获取积分,用做 Kaggle 网站中的最终排名。

早期 Kaggle 对于每场比赛的积分按如下方式计算:

[\frac{100000}{N_{teammates}}][Rank^{-0.75}][log_{10}(N_{teams})][\frac{2years = time}{2 years}]

在 2015 年对新的排名系统做了调整,新的比赛积分计算公式调整为:
[\frac{100000}{N_{teammates}}][Rank^{-0.75}][log_{10}(1 + log_{10}(N_{teams}))][e^{-t/500}]

其中,N_{teammates} 为团队成员的数量,Rank 为比赛排名,N_{teams} 为参赛的团队数量,t
为从比赛结束之日起过去的时间。

第一部分可以视为基础分,团队成员越少,所获得的基础分越多。从调整的文档来看,Kaggle 认为团队合作每个人的贡献程度会大于 1 / N_{teammates} ,为了鼓励大家团队合作,Kaggle 减少了对团队人数的基础分惩罚力度。

第二部分则是根据用户在比赛中的排名得到一个小于等于 1 的系数。下图显示了不同的指数以及 1 / Rank 之间的区别:

从图中可以看出,通过调节指数的大小可以控制系数随排名下降而下降的速度。整体来说,Kaggle 更加重视前几名,对于 10 名开外的选手,系数均小于 0.2 ,且差异不大。

第三部分可以理解为通过参赛的队伍数量来衡量比赛的受欢迎程度(或是在众多参赛队伍中脱颖而出的难易程度)。以 100 和 1000 支参赛队伍对比为例,根据之前的计算公式,这一部分为:

log_{10}(100) = 2
log_{10}(1000) = 3

但随着 Kaggle 本身比赛流行度越来越高,官方认为赢得一场 1000 人的比赛并不需要比赢得一场 100 人的比赛需要多 50% 的技能,因此通过调整后的算法,这个比例调整至大约为 25% 。

log_{10}(log_{10}(100) + 1) \approx 0.47
log_{10}(log_{10}(1000) + 1) \approx 0.6

第四部份为时间衰减项,调整为新的计算公式后可以消除原来通过设置 2 年时限导致的积分断崖。如果任何一对个体都没有采取任何进一步的行动,那么排名不应该在任何一对个体之间发生变化。换句话说,如果整个 Kaggle 用户群停止参加比赛,他们的相对排名应该随着时间的推移保持不变。选择 1/500 的原因是可以将旧的 2 年断崖延长到更长的时间范围,并且永远不会变为 0。

Elo 评分系统

Elo 评分系统(Elo Rating System)是由匈牙利裔美国物理学家 Arpad Elo 创建的一个衡量各类对弈活动水平的评价方法,是当今对弈水平评估公认的权威标准,且被广泛用于国际象棋、围棋、足球、篮球等运动。网络游戏的竞技对战系统也常采用此评分系统。

Elo 评分系统是基于统计学的一个评估棋手水平的方法。Elo 模型原先采用正态分布,但实践显明棋手的表现并非正态分布,所以现在的评分计分系统通常使用的是逻辑分布。

假设棋手 A 和 B 的当前评分分别为 R_AR_B ,则按照逻辑分布,A 对 B 的胜率期望值为:

E_A = \frac{1}{1 + 10_{(R_B - R_A) / 400}}

类似的有 B 对 A 的胜率期望值为:

E_B = \frac{1}{1 + 10_{(R_A - R_B) / 400}}

假如一位棋手在比赛中的真实得分 S_A (胜 1 分,和 0.5 分,负 0 分)和他的胜率期望值 E_A 不同,则他的评分要作相应的调整:

R^{'}_A = R_A + K(S_A - E_A)

公式中 R_AR^{'}_A 分别为棋手调整前后的评分。 K 值是一个极限值,代表理论上最多可以赢一个玩家的得分和失分,K/2 就是相同等级的玩家其中一方胜利后所得的分数。国际象棋大师赛中,K = 16 ;在大部分的游戏规则中, K = 32。通常水平越高的比赛中其 K 值越小,这样做是为了避免少数的几场比赛就能改变高端顶尖玩家的排名。E_AE_B 中的 400 是让多数玩家积分保持标准正态分布的值,在 K 相同的情况下,分母位置的值越大,积分变化值越小。

Glicko 评分系统

Glicko 评分系统(Glicko Rating System)及 Glicko-2 评分系统(Glicko-2 Rating System)是评估选手在比赛中(如国际象棋及围棋)的技术能力方法之一。

此方法由马克·格利克曼发明,原为国际象棋评分系统打造,后作为评分评分系统的改进版本广泛应用。

Elo 评分系统的问题在于无法确定选手评分的可信度,而 Glicko 评分系统正是针对此进行改进。假设两名评分均为 1700 的选手 A 和 B 在进行一场对战后 A 获得胜利,在美国国际象棋联赛的 Elo 评分系统下,A 选手评分将增长 16,对应的 B 选手评分将下降 16。但是假如 A 选手是已经很久没玩,但 B 选手每周都会玩,那么在上述情况下 A 选手的 1700 评分并不能十分可信地用于评定其实力,而 B 选手的 1700 评分则更为可信。

Glicko 算法的主要贡献是“评分可靠性”(Ratings Reliability),即评分偏差(Ratings Deviation)。若选手没有评分,则其评分通常被设为 1500,评分偏差为 350。新的评分偏差(RD)可使用旧的评分偏差((RD_0)计算:

(RD) = min(\sqrt{RD^{2}_0 + c^2t} , 350)

其中,t 为自上次比赛至现在的时间长度(评分期),常数 c 根据选手在特定时间段内的技术不确定性计算而来,计算方法可以通过数据分析,或是估算选手的评分偏差将在什么时候达到未评分选手的评分偏差得来。若一名选手的评分偏差将在 100 个评分期间内达到 350 的不确定度,则评分偏差为 50 的玩家的常数 c 可通过解 350 = \sqrt{50^2 + 100c^2},则有 c = \sqrt{(350^2 - 50^2) / 100 }\approx34.6
在经过 m 场比赛后,选手的新评分可通过下列等式计算:

r = r_0 + \frac{q}{\frac{1}{RD^2} + \frac{1}{d^2}}\sum^m_{i=1}g(RD_i)(S_i - E(s | r_0, r_i ,RD_i))

其中:
g(RD_i) = \frac{1}{\sqrt{1 + \frac{3q^2(RD^2_i)}{n^2}}}
E(s | r , r_i , RD_i) = \frac{1}{1+10(\frac{g(RD_i)(r_0-r_i)}{-400})}
q = \frac{ln(10)}{400} = 0.00575646273
d^2 = \frac{1}{q^2\sum{^m_{i=1}(g(RD_i))^2E(s | r_0,r_i,RD_i)(1 - E(s | r_0 , r_i , RD_i))}}

r_i表示选手个人评分,s_i 表示每场比赛后的结果。胜利为 1,平局为 1/2,失败为 0。

原先用于计算评分偏差的函数应增大标准差值,进而反应模型中一定非观察时间内,玩家的技术不确定性的增长。随后,评分偏差将在几场游戏后更新:

RD^{'} = \sqrt{(\frac{1}{RD^2} + \frac{1}{d^2})^{-1}}

Glicko-2 评分系统

Glicko-2 算法与原始 Glicko 算法类似,增加了一个评分波动率 \sigma ,它根据玩家表现的不稳定程度来衡量玩家评分的预期波动程度。例如:当一名球员的表现保持稳定时,他们的评分波动性会很低,如果他们在这段稳定期之后取得了异常强劲的成绩,那么他们的评分波动性就会增加。

Glicko-2 算法的简要步骤如下:

1.计算辅助量

在一个评分周期内,当前评分为 μ 和评分偏差为 \phi 的玩家与 m 个评分为 \mu_1 , \cdots , \mu_m 和评分偏差为 \phi_1 , \cdots , \phi_m 的玩家比赛,获得的分数为 s_1,\cdots,s_m ,我们首先需要计算辅助量 v\Delta :

v =[\sum^m_{j=1}g(\phi_j)^2E(\mu , \mu_j , \phi_j)\{s_j - E(\mu , \mu_j,\phi_j)\}]
\Delta = v\sum^m_{j=1}g(\phi_j)\{s_j - E(\mu , \mu_j,\phi_j)\}

其中:
g(\phi) = \frac{1}{\sqrt{1+3\phi^2 / \pi^2}} , E(\mu , \mu_j,\phi_j) = \frac{1}{1+exp\{-g(\phi_j)(\mu - \mu_j)\}}

2. 确定新的评分波动率

选择一个小的常数 \tau 来限制时间的波动性,例如:\tau = 0.2 (较小的 \tau 值可以防止剧烈的评分变化),对于:

f(x) = \frac{1}{2} \frac{e^x(\Delta^2 - \phi^2 - v^2 - e^x)}{(\phi^2 + v + e^x)} - \frac{x - ln(\sigma^2)}{\tau ^2}

我们需要找到满足 f(A) = 0 的值 A。解决此问题的一种有效方法是使用 Illinois 算法,一旦这个迭代过程完成,我们将新的评级波动率 \sigma^{'} 设置为:\sigma^{'} = e^{\frac{A}{2}}

3. 确定新的评分偏差和评分

之后得到新的评分偏差:

\mu^{'} = \mu + \phi^{r2}\sum^m_{j=1}g(\phi_j)\{s_j - E(\mu , \mu_j,\phi_j)\}

需要注意这里的评分和评分偏差与原始 Glicko 算法的比例不同,需要进行转换才能正确比较两者。

TrueSkill 评分系统

TrueSkill 评分系统是基于贝叶斯推断的评分系统,由微软研究院开发以代替传统 Elo 评分系统,并成功应用于 Xbox Live 自动匹配系统。
TrueSkill 评分系统是 Glicko 评分系统的衍伸,主要用于多人游戏中。TrueSkill 评分系统考虑到了个别玩家水平的不确定性,综合考虑了各玩家的胜率和可能的水平涨落。当各玩家进行了更多的游戏后,即使个别玩家的胜率不变,系统也会因为对个别玩家的水平更加了解而改变对玩家的评分。
在电子竞技游戏中,特别是当有多名选手参加比赛的时候需要平衡队伍间的水平,让游戏比赛更加有意思。这样的一个参赛选手能力平衡系统通常包含以下三个模块:

  1. 一个包含跟踪所有玩家比赛结果,记录玩家能力的模块。
  2. 一个对比赛成员进行配对的模块。
  3. 一个公布比赛中各成员能力的模块。
能力计算和更新

TrueSkill 评分系统是针对玩家能力进行设计的,以克服现有排名系统的局限性,确保比赛双方的公平性,可以在联赛中作为排名系统使用。TrueSkill 评分系统假设玩家的水平可以用一个正态分布来表示,而正态分布可以用两个参数:平均值和方差来完全描述。设 Rank 值为 R ,代表玩家水平的正态分布的两个参数平均值和方差分别为 \mu\sigma,则系统对玩家的评分即 Rank 值为 R = \mu - k \times \sigma 其中,k 值越大则系统的评分越保守。

上图来自 TrueSkill 网站,钟型曲线为某个玩家水平的可能分布,绿色区域是排名系统的信念,即玩家的技能在 15 到 20 级之间。

下表格给出了 8 个新手在参与一个 8 人游戏后 mu\sigma 的变化。

第 4 名 Darren 和第 5 名 Eve,他们的 \sigma 是最小的,换句话说系统认为他们能力的可能起伏是最小的。这是因为通过这场游戏我们对他们了解得最多:他们赢了3 和 4 个人,也输给了 4 和 3 个人。而对于第 1 名 Alice,我们只知道她赢了 7 个人。

定量分析可以先考虑最简单的两人游戏情况:

\mu_{winner} \leftarrow \mu_{winner} + \frac{\sigma^2_{winner}}{c} \times v (\frac{\mu_{winner} - \mu_{loser}}{c} , \frac{\epsilon}{c})

\mu_{loser} \leftarrow \mu_{loser} - \frac{\sigma^2_{loser}}{c} \times (\frac{\mu_{winner} - \mu_{loser}}{c}, \frac{\epsilon}{c})

\sigma^2_{winner} \leftarrow \sigma^2_{uninner} \times [1 - \frac{\sigma^2_{winner} }{c} \times w (\frac{\mu_{winner} - \mu_{loser}}{c}, \frac{\epsilon}{c})]

\sigma^2{loser} \leftarrow \sigma^2{loser} \times [ 1- \frac{\sigma^2_{loser} }{c} \times w (\frac{\mu_{winner} - \mu_{loser}}{c} , \frac{\epsilon}{c})]

c^2 = 2\beta^2 + \sigma^2_{winner} + \sigma^2{loser}

其中,系数 \beta^2 代表的是所有玩家的平均方差,vw 是两个函数,比较复杂,\epsilon 是平局参数。简而言之,个别玩家赢了 \mu 就增加,输了 \mu 减小;但不论输赢,\sigma 都是在减小,所以有可能出现输了涨分的情况。

对手匹配

势均力敌的对手能带来最精彩的比赛,所以当自动匹配对手时,系统会尽可能地为个别玩家安排可能水平最为接近的对手。TrueSkill 评分系统采用了一个值域为 (0 , 1) 的函数来描述两个人是否势均力敌:结果越接近 0 代表差距越大,越接近 1 代表水平越接近。

假设有两个玩家 A 和 B,他们的参数为 (\mu_A,\sigma_A)(\mu_B,\sigma_B),则函数对这两个玩家的返回值为:
e ^- \frac{(\mu_A-\mu_B)^2}{2c^2}\sqrt{\frac{2\beta^2}{c^2}}

c 的值由如下公式给出:

c^2 = 2\beta^2 + \mu^2_A + \mu^2_B

如果两人有较大几率被匹配在一起,仅是平均值接近还不行,还需要方差也比较接近才可以。

在 Xbox Live 上,系统为每个玩家赋予的初值是 \mu = 25\sigma = \frac{25}{3}k = 3。所以玩家的起始 Rank 值为:

R = 25 - 3 \frac{25}{3} = 0

相较 Elo 评价系统,TrueSkill 评价系统的优势在于:

  1. 适用于复杂的组队形式,更具一般性。
  2. 有更完善的建模体系,容易扩展。
  3. 继承了贝叶斯建模的优点,如模型选择等。
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容