基于竞技比赛的评分排序系统-Glicko

发表于 | 分类于 ， | | 阅读次数:

背景介绍

参考各类竞技比赛的评分排序系统，我们在具体公司业务上也可以进行相应评分排序，从而得到最能体现用户偏好的商品评分系统。

  • 目标
    • 从用户角度出发，给出平台商品的真实排序
  • 数据
    • 需要数据类型：A和B比赛的胜负数据，即（A,B,1）代表A击败B
    • 例如在有A和B同时曝光可选时，用户选择了A，则代表A击败B一次
  • 方法
    • Elo rating system
    • Glicko rating system

Elo rating system

Elo等级分制度（Elo rating system）是指由匈牙利裔美国物理学家 Arpad Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估的公认的权威方法。被广泛用于国际象棋、围棋、足球、篮球等运动。游戏界比较著名的应用有： WOW（魔兽世界）、DOTA、LOL。

计分方法

系统中有A和B两位选手，$R_A$ 和$R_B$分别代表A与B的当前等级分，之后A和B的进行一次竞技，结果记为$S_A$（如果A胜则$S_A=1$，负为0，平为0.5）。该次竞技后A的等级分更新如下：

$$ R_{A}^{‘} = R_A + K(S_A - E_A) $$

其中：

  • $E_A$，代表A相对于B的获胜概率（胜率期望值）
    • $E_A=\frac{1}{1+10^{(R_B-R_A)/400}}$
  • $K$ 为一个常数，代表理论上最多可以赢一个玩家的得分和失分
    • K/2就是相同rating的玩家其中一方胜利后所得的分数
    • 在大部分的游戏规则中，K=32； 国际象棋大师赛中，K=16
    • 竞技的选手水平越高K取值越小（避免少数比赛改变顶尖玩家排名）
  • Elo模型原先采用正态分布。但是实践显明棋手的表现并非呈正态分布，所以现在的等级分计分系统通常使用的是逻辑分布。
  • 公式中分母的400来由： 根据公式可以得出，当K值相同的情况下，越高的分母，越低的积分变化。总体来说400是一个平衡的、让多数玩家积分保持标准正态分布的值

实例说明

若当前A玩家积分为1500，B玩家积分为1600

  • 预估A玩家的胜负值： Ea = 1/(1+10^[（1600-1500）/400]）≈ 0.36
  • 预估B玩家的胜负值： Eb = 1-Ea = 1-0.36 = 0.64
  • 假设A玩家获胜，实际胜负值为Sa = 1
    • A玩家最终得分为 ：R’a = 1500 + 32*(1-0.36) = 1500+20.5 = 1520
    • A玩家赢20分，B玩家输20分。
  • 假设B玩家获胜，实际胜负值为Sa = 1
    • B队最终得分为 R’b = 1600 + 32*(1-0.64) = 1600 + 11.52 = 1612
    • B玩家赢12分，A玩家输12分。

Glicko rating system

Glicko是由Mark Glickman提出的方法，是对Elo评分系统的改进，加入了评分偏差项RD（ratings deviation）。

  • 考虑未进行对战的时间长度，时间越长则RD越大
  • 举例解释：一个很久未参与竞技比赛的选手A，其能力值很可能不再等于系统记录的$R_A$，如果A与能力值相同的B（$R_A=R_B$）比赛，而选手B是近期一直活跃在系统的玩家，则明显能力值更加可信。
    • 若A击败B，则A加分应该更多，B减分应该更少
    • 对于A：其能力不确定，击败了系统中相同等级的对手，说明很可能A的能力早已高于系统的记录，因此需要‘快速加分’
    • 对于B：被一个不太确定能力的人击败，说明A很可能本来就比B强，因此被击败不应该扣除太多积分，因此需要‘减少降分’

计分方法

对于选手A，1）记其能力评分（rating）为$r$；2）偏差(可理解为：标准差)为$RD$，为了方便计算，记方差为$v$ （$v=RD^2$）；3）第$j$次的比赛结果为$S_j$。则其进入系统后，随着比赛的增加，其得分相应计算如下：

注意：比赛以周期为单位更新选手评分，此处假设选手A在一个周期t+1内，参与了m次比赛

  • Step1：初始化评分
    • a) 无历史评分则，评分$r=1500$，方差$v=350^2$ （初始分可根据实际情况设置为其他数值）
    • b) 有历史评分则，评分 $r=r_{old}$，方差$v=min(v_{old}+c^2t,350^2) $
      • $c$，衡量时间因素的常量系数
      • $t$，本次比赛和上次比赛的时间间隔（几个时间周期）
  • Step2：更新评分$r_{new}$与方差$v_{new}$
    • 方差:
      $$ v_{new}=(\frac{1}{v}+d)^{-1} $$
    • 评分:
      $$ r_{new}=r+qv_{new}{\sum_{j=1}^{m}k_j(s_j-e_j)} $$
    • 其中：
      • 对比Elo的常量$K$,Glicko的系数是方差的函数：$k_j=\frac{1}{\sqrt{1+3q^2v_j/\pi^2}}$ （实际上要和Elo的$K$对等，还需要再乘$qv^*$）
      • 对比Elo的$E_A$,Glicko的获胜概率期望值加入$k_j$乘数，从而也和方差$v$有关：$e_j=\frac{1}{1+10^{-k_j(r-r_j)/400}}$
      • $q=ln(10)/400$
      • $d=q^2\sum_{j=1}^{m}k_j^2e_j(1-e_j)$

预测方法

现有选手A，其评分和方差为$(r_a,v_a)$，若A与$(r_b,v_b)$的选手B进行比赛，则可预测A的胜率为：
$$ e_{ab}=\frac{1}{1+10^{-k_{ab}(r_a-r_b)/400}} $$
其中，
$$ k_{ab}=\frac{1}{\sqrt{1+3q^2(v_a+v_b)/\pi^2}} $$

tips

  • 关于$RD$：随着选手的活跃，参赛次数的增加，偏差会越来越小，$RD$太小会导致选手即使提升了能力赢得比赛，也只能加极少的分数，一般应用中会设置$RD$的下限，例如 $ RD=max(30,RD)$
  • 置信区间：根据 quasi-Bayesian derivation of the Glicko system，一般可以认为95%的置信区间如下：
    $$(r-1.96RD,r+1.96RD)$$

工程实现

使用 Alec Stephenson 写的R包PlayerRatings

共有参数

  • data，数据，由四列组成：
    • 时间：第几个比赛周
    • 主场方方选手名称，比如说中国队和西班牙队这次在中国比赛，那么中国为主场方
    • 非主场方选手名称
    • 得分，胜=1，平=0.5，负=0
  • status，当前计分系统的状态数据框
    • 主要包括：选手名称（Player）、评分（Rating）、比赛总场次（Games）、胜场次（Win）、平场次（Draw）、负场次（Loss）、该队结束比赛后还剩的比赛周次（Lag）
    • 有‘RD’参数的系统，例如Glicko，还包括Deviation列
  • gamma，对主场方的偏置
    • 主要用于预测，例如在A的地区和B比赛，那么同等水平下会A的胜率应该更高
    • 建模函数中gamma默认为0，而预测函数(predict())中gamma默认为30

建模函数

  • elo()，实现Elo评分系统，主要参数：

    • data，status=NULL，gamma=0
    • init，初始分，默认init = 2200
    • kfac，K值,
      • 给定常数，默认kfac=27
      • 也可以设置不同规则下的K值，例如场次在30以上取26，否则取32（kfac=kgames）

  • glicko()，实现Glicko评分系统

    • data，status=NULL，gamma=0
    • init，初始分和标准差，默认init = c(2200,300)
    • cval，衡量时间因素的常量系数，默认cval = 15，（区别于Elo的重要参数）

  • steph()，实现作者基于 Glicko 改进的 Stephenson 评分系统

    • status = NULL, gamma = 0,
    • init，初始分和标准差，默认init = c(2200,300)
    • cval = 10, hval = 10, bval = 0, lambda = 2