这几天 AlphaGo 4:1 战胜了李世石，围棋积分网站 给了 AlphaGo 一个世界排名。在 3:1 的时候是世界第四，4:1 后上升到了世界第二。

   我很好奇这个网站是如何给棋手打分的，便顺着链接指引翻了下 wikipedia 读了几篇 paper 。

   下面是我的一些理解，由于我的数学基本功不太扎实，难免有错误，所以有兴趣的同学最好自己读论文 。

   首先，如何定义等级分这个东西？

   在一对一竞技类游戏中，假设规则是公平的，对战双方如果都能给出最优策略，那么胜负概率是完全均等的 50% 。如果我们假定冥冥之中存在一个绝对实力值，而实力高的人可以少犯错误，那么他就能以超过 50% 的概率战胜对手。

   简化胜负结果背后复杂的过程，我们把全体选手按绝对实力值排名，排名靠前的选手对排名靠后的选手，胜率都是大于 50% 的。

   由于实力强的人不一定对实力弱的人必胜，所以这个绝对实力值其实是一个概率相关数。胜率的高低可以看成是实力差异大小。根据若干比赛的结果，我们可以推算出代表实力值得后验概率。

   比如有两个选手的实力为 A 和 B ，则 A 胜过 B 的概率就为 A / (A+B) 。（不考虑平局的情况）

   有一组选手和足够的他们相互之间的比赛成绩的话，我们就可以根据 Bradley Terry 模型 推算出一组实力值，尽可能的符合他们之间的对战结果。

   如果直接采用这样的数值表示实力（等级分），存在一个问题：在人类的大多数游戏中，参赛人的实力差别会很大。拿围棋举例，我这样的臭棋篓子，可以轻松碾压一个围棋新手（胜率超过 99%）；而随便一个业余高段也可以轻松碾压我；而他在职业选手中他的胜率却可能掉的非常低；而顶尖职业高手对一般职业选手的胜率也能很高。

   这样，每个实力层次的数值都会远大于低一个层次的。结果就是顶尖选手的分值相比初学者就成了个天文数字。

   一个叫 Elo 的物理教授发明了 elo 等级分，它采用指数形式表示上面的实力值。每提升 200 个 elo 分，对之前的胜率可以达到 76% ；100 个 elo 分差，胜率 64% 。

   btw, 目前国际象棋的世界顶尖选手是 2800+ 分，围棋顶尖选手在 goratings 网站上有 3600+ 分，我个人理解是围棋可能高低手的实力差距更大。另外，在很多采用 elo 系统的电子竞技系统中，顶尖高手也在 3000 分+ 以上。

   elo 是个好东西，它把选手的实力以一个非常直观的数字展现出来，在网络游戏中应用更为广泛。系统可以直接使用相近的 elo 分来匹配对手了。不过，elo 在中文维基以及上面的链接文章中的介绍并不准确。中文介绍中强调了 elo 的计算方法，但那仅仅是诸多方法中的一种（可能是实践中采用较多的一种）。而 elo 只是在数学上定义了分值得含义：相差 200 分则胜率达到 76% 。通过比赛结果去反推 elo ，让 elo 更符合结果的胜负比率，怎样的方法更准确，更高效（满足大量玩家大量比赛情况下的实时计算）一直是个难题。

   让我们回头来看静态 Bradley Terry 模型，它可能更适合 AI 间的较量，通过短期大量比赛成绩，能够很准确的推算出实际的实力。 而在人类比赛中不太适用。因为人的水平是不稳定的，会随比赛次数增加和提升，也会因为身体因素下降。如果导入一长段时间的赛绩，采用静态分析就变得很不靠谱。

   对于人类，等级分跟接近一个针对时间 t 的一个函数，而不是一个固定值。对于利用不断发生的比赛来评估不同时间点上系统中每个选手的等级分，有很多方法。

   目前用的比较多的是使用一个增量评分系统。也就是给每个新人一个基础分。当他们参加比赛后，每次赢一盘就从败者那里取得一些分，elo 系统就有了自我修正的能力。

   同时，如果是弱者战胜强者，这时弱方胜利者取得的分更多一些；反之则少获得一些。这个多少，是由一个公式的参数系数控制的。这个公式和比赛前双方的 elo 有关。

   这套方法实现简单，计算成本低，被广泛采用。但它有一个明显的缺陷：对每场比赛结果中蕴含的信息利用不足。

   假设有这样一种情况：张三和李四一直在相互打比赛，不相伯仲。他们的 elo 理所当然的一致，也非常符合实际情况（elo 只表示相对实力）。在这个过程中，他们两人的实力都提高了，但由于并没有和外界交流，所以无法从 elo 绝对值中体现出来。

   有一天，张三打败了一个外界高手，他的 elo 涨了上去（融入了更大的系统）。但是，李四的 elo 却保持不变。张三的那场比赛原本可以引入这个信息，但简单的增量评分系统却做不到这点。需要李四继续和张三比赛（拉低张三新获得的 elo ），或自己出去参赛（涨分）。

   为了解决上面的问题，我们可以对最近发生的一系列比赛放在一起做之前提到的全局静态分析，同时对之前已经发生的比赛结果做一次衰退处理，降低过去比赛的权重。

   这种方法可以解决增强评分系统的一些问题，它可以把每场比赛都放进系统中针对所有选手来考量。但这种方法也有瑕疵，最大的问题是，近期的比赛决定了新的一系列等级分的话，那些短期没有参赛的选手的 elo 估计就会偏差变大。（增量评分系统也有这个问题，但对暂时不参赛的选手的 elo 估计的偏差扩大的速度只是时间的平方根，要小的多）

   而采用历史衰退处理的评分系统中，长期不参赛的选手复出后，评分可能有非常大的跳跃，而近期比赛频繁的选手，可能连胜多次却迟迟不涨分。衰退周期需要根据选手的比赛频率来定，当不同选手的参赛频率差距很大时，就很难确定这个周期。

   动态 Bradley Terry 模型 就是为解决这一系列问题而提出的。它认为人的水平是随时间线性变化的，在极短时间内，人的水平变化不大，变化速度可快可慢，其可能的变化是呈正态分布的。

   我们根据上个时间周期选手的 elo 值，考虑这段时间他可能的水平变化区间，再依据最近的整体比赛结果，可以迭代出新一轮的 elo 。

   动态 Bradley Terry 模型的问题是计算量过大。WHR 的关键点在于提出了一个近似算法，可以增量更新比赛结果，用一个较小的时间代价迭代出新的一轮 elo 。在每场比赛结果后，对参赛选手用牛顿插值法直接估算出新的 elo ，而在有额外时间时，做多次迭代。

   除了论文中给出的数学公式，还有一个开源的  Ruby 实现 ，可能跟适合程序员理解。

   这个 ruby 实现中，还针对围棋做了一点改进，可以同时考虑让子棋。也就是盘外规则因素对评价系统的影响。他的做法是，根据让子数，对胜率的估算做一个修正。即，如果 A 让子胜了 B 就认为  A 战胜了一个比 B 实际  elo 分更高的对手。

   我认为这种修正同样可以用于有比分的对战系统，比如大比分战胜对手或是逼平一个比自己强很多的对手都可以根据结果做一些调整。

建议继续学习：

1. 如何使用1M的内存排序100万个8位数    (阅读：11004)
2. 快速排序（Quicksort）的Javascript实现    (阅读：10150)
3. 数学之美：StackOverflow问答排名算法    (阅读：9848)
4. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读：9091)
5. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读：6257)
6. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读：6055)
7. Hacker News 排名算法工作原理    (阅读：5483)
8. 用skip list实现实时排名?    (阅读：5393)
9. 数学之美：Reddit评论排名算法    (阅读：4583)
10. Java程序员必知的8大排序算法    (阅读：4539)