|
本文授权转载自微信号：鬼之一手，作者：可爱的小鬼鬼 著名的棋手排名榜，Goratings，采用的是WHR（Whole-History Rating)算法。在介绍具体的算法之前，我们首先介绍知道一些基础知识。 我们想对棋手的水平进行排序，那么按照什么刻画出棋手的水平？胜率是一个非常重要且合理的指标。我们有理由相信，两个棋手之间，相对胜率更高的棋手，理应有更高的水平。现在我们用一个实数来刻画出棋手的实力（水平），那么自然，数字越大，代表着棋手的实力越强，相对的，与其他棋手的胜率也会变得更高。Bradley-Terry模型就是用来比较两者水平和计算胜率的一个工具。假设现在有两个棋手A和B，实力分别为a和b，那么：P(A战胜B）=a/（a+b)。需要注意的是，这个模型是静态的，也就是没有考虑时间因素。在动态Bradley-Terry模型，一个棋手的实力是随着时间t发生改变的，因此上面的实力a和实力b也要对应成一个关于时间t的函数a(t)和b(t)。 我们思考一下这个Bradley-Terry模型。假设有多个棋手，A，B，C……。B对A的胜率为80%，C对B的胜率为80%……以此类推。按照模型，B的实力应是A的4倍，C的实力是B的4倍，随着棋手增多，后面棋手的实力呈指数增长。这对于计算上十分不方便，看起来也很不自然。因此我们通常会对其取对数，这样的话棋手随着胜率的变化增长的速度就由指数增长变为了线性增长，既便于计算也更符合人类习惯。而我们常用的Elo等级分和上面提到的实力，在忽略尺度的情况下也呈这种指数与对数的关系。假设一个棋手的实力是γ，Elo等级分为R，那么两者的换算关系为：γ=10^(R/400)。根据棋手的Elo等级分，我们就可以估计出棋手之间的相对胜率。 我们现在可以用Elo等级分或者实力来计算胜率。但是棋手的实力不是我们天然就知道的，需要依靠棋手间的相互胜率进行计算。贝叶斯推断的核心是贝叶斯公式，该公式刻画了先验概率和后验概率之间的关系：  （贝叶斯公式） 这里的γ就是上文提到的实力。G代表对局结果。p(G|γ）可以用前面的模型进行计算，关键的问题在于公式左侧。我们给棋手定等级分排序的目的就是估计棋手之间的胜率，因此我们定的等级分以及计算出来的胜率越和比赛结果相吻合，等级分就越合理。因此我们需要做的就是找到令p(γ|G）最大的γ，而这是一个经典的优化问题。而p(G)是一个可以通过比赛结果观察到的常数，p(γ）是实力的先验分布。 在动态Bradley-Terry模型中，先验含有两个层面。一个是所有棋手的实力的先验概率分布。另一个随着时间变化实力发生的改变，而这在动态Bradley-Terry模型是维纳过程（也称作布朗运动过程）。  （维纳过程的定义） 维纳过程具有马尔可夫性（无记忆性）。举一个不精确的例子，我现在想知道棋手A当前的实力，而我已知他昨天的实力。那么棋手A在一周前，两周前，一年前的实力就都不需要再去考虑了。 现在我们具体来说明一些Goratings的算法。由于时间是连续的，我们首先要做的就是将其离散化，而这个很容易做到，因为我们不需要知道每一分每一秒棋手的水平，只需要知道每场对局时的水平。之后要计算每个棋手的实力。上文提到这是一个优化问题，而这个用牛顿法做即可。目标函数是p(γ|G）（简称p），优化变量是r（由每一个棋手的实力构成的向量），那么牛顿法的公式即是：  对于这个公式还有两点需要提及。一个是目标函数p非常接近于高斯分布，因此logp与二次函数非常类似，这保证了牛顿迭代法可以在一次迭代中就取得非常良好的效果。第二点是维纳过程的马尔可夫性保证了Hessian矩阵是一个三对角矩阵，进而牛顿法中Hessian矩阵求逆是线性时间复杂度的：这保证了计算时间可以在合理的范围之内。 上面是一个全局优化。如果在这基础之上再有新的对局添加进来呢？如果重新全部计算，那未免也太复杂了。因此每当有新的对局添加，首先保持原有的实力不变，之后牛顿法只对这个对局相关的棋手采用（而不是所有棋手）。这会降低一些精准性，但是保证了算法可以实时计算。至于牛顿法的迭代次数，就看计算需要了。最后，将每个棋手的实力计算之后，其实力的不确定度也可以估计出来，但由于这个不体现在等级分上，因此就不多说了。 最后关于Goratings这个排行榜多说两句。一个是AlphaGo输给李世石之后才进入排名（当时排在世界第4）。事实上这个排行榜排名时棋手必须要输过棋，不然胜率100%,等级分岂不是要无穷大了。另外就是有些人认为这个榜就是野鸡榜，他们大约有几种理由： (1)XXX(某棋手）连世界冠军都没拿过，居然能排名这么高！野鸡榜果然野鸡！ 排行榜不是按照世界冠军的个数去排名的，而是按照历史各次对局成绩估算出的相对胜率，据此进行排名。 (2)柯洁/朴廷桓/XXX赢（或者输）1盘棋怎么等级分变化的这么多？野鸡榜果然野鸡！ 赢（输）1盘棋看对的是谁，二来要看胜率变化有多大影响，等级分变化不同再正常不过了。 (3) XX那么厉害（弱），凭什么野鸡榜排这么靠后（前）？野鸡榜果然野鸡！
(4) XX怎么可能比巅峰时期的李昌镐（或者其他过去的现象级棋手）的等级分高/还要厉害？野鸡榜果然野鸡！ 客观的来说，随着时间的发展人类棋手的整体实力在不断上涨，这很正常。现在看起来不是顶级的棋手，放在过去几十年前那也是降维打击。 最后，我们来欣赏一个目前等级分第一选手的等级分变化（没错，本人就是申吹）。  参考文献 [1] Coulom, Rémi. Whole-history rating: A Bayesian rating system for players of time-varying strength[M]// Computers and Games. Springer Berlin Heidelberg, 2008. |
|
|
