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

2023-02-21 本文已影响0人 ___n

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_A$ 和 $R_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_A$ 和 $R^{'}_A$ 分别为棋手调整前后的评分。 $K$ 值是一个极限值，代表理论上最多可以赢一个玩家的得分和失分， $K/2$ 就是相同等级的玩家其中一方胜利后所得的分数。国际象棋大师赛中， $K = 16$ ；在大部分的游戏规则中， $K = 32$ 。通常水平越高的比赛中其 $K$ 值越小，这样做是为了避免少数的几场比赛就能改变高端顶尖玩家的排名。 $E_A$ 和 $E_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 评分系统考虑到了个别玩家水平的不确定性，综合考虑了各玩家的胜率和可能的水平涨落。当各玩家进行了更多的游戏后，即使个别玩家的胜率不变，系统也会因为对个别玩家的水平更加了解而改变对玩家的评分。
在电子竞技游戏中，特别是当有多名选手参加比赛的时候需要平衡队伍间的水平，让游戏比赛更加有意思。这样的一个参赛选手能力平衡系统通常包含以下三个模块：

一个包含跟踪所有玩家比赛结果，记录玩家能力的模块。
一个对比赛成员进行配对的模块。
一个公布比赛中各成员能力的模块。

能力计算和更新

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})]$