算法猜想

在[上一篇文章]中，我们得出的几个基本的结论就是：

  • 水平评估模型为高斯模型
  • 分数结算算法原本为1V1所用的，通过与每名对手计算一次来拓展为多人混战算法

那么很容易猜到酒馆战棋用的算法是ELO+加权平均。 计算公式如下：

\[Result_i \in {1,2,...,8}\]

\[ Result_{i,j}= \begin{cases} \ \ \ 1\ \ \ Result_i<Result_j,\\ -1\ \ \ Result_i>Result_j. \end{cases} \]

\[Expect_{i,j} = \frac{1}{1+10^{\frac{Score_i-Score_j}{-\alpha}}}\]

\[\Delta Score_{i,j}=\eta*(Result_{i,j}-Expect_{i,j})\]

\[Final_i=\frac{\sum_j^{n-1}(\Delta Score_{i,j})}{n-1}+\beta\]

公式说明： 第一个公式 \(Result_i\) 表示玩家 \(i\) 得到的最终排名 第二个公式 \(Result_{i,j}\) 表示玩家 \(i\) 与 \(j\) 对战的结果，只要i的排名高于j，结果记为1，反之则为-1 第三个公式表示由分数计算所得的胜率期望，该公式为标准的Elo速算公式，其中\(\alpha\)是膨胀率，对分数差与胜率之间的换算关系进行放缩 第四个公式表示\(i\)与\(j\)两个玩家间以1V1 Elo算法结算对局后的分数应得的分数变化值，其中\(\eta\)是学习率，表示每次对局后，分数变化的量度 第五个公式表示将每个玩家与其他玩家的Elo分进行计算，最终将所有的变化量取平均进行最终结算,\(\beta\)是上一篇文章中提到的分数补偿

算法验算&参数推导

空口无凭，我们用炉石中真实的分数来验证这个公式的正确性并推导出超参数\(\alpha\)与\(\eta\)的取值。

对此，我在5500分打了数局，发现每次吃鸡得分都是100\(\pm\) 5，由于5500分是一个不会掉分的卡点，我们大胆假设所有对手的分数都是在5500分。另外在上篇文章中设计师说明了期望得分为98，因此可知\(\beta=2\)(非固定，随账号变化)且：

\[\Delta Score=98/7=\eta*(1-0.5) => \eta=28\]

考虑到两个因素，一是算法的超参数一般是整数，二是国际象棋中常用的\(\eta=32\)。那么我猜测这个\(\eta\)的初始值在30~40左右，然后随着游戏进程的增加，每进行一定局数减少1。

\(\eta\)的变化率在小样本中测不出来，但是我可以以\(\eta\)当前值来代入对局验证公式是否正确。 以\(\eta=28，\beta=2\)来计算，当前我在第一名可得98+2=100分，第二名可得145+2=72分，第三名可得143+2=44分。

经过进一步的游戏内对局数据验证，果然，分毫不差，第二名与第三名的均值分别为72和44，算法成立。

数学进阶

也许有人会问这样一个问题，为什么不考虑每个人的具体名次，只看排名高低，这样求平均值得到的Elo算法还能用吗？

这就涉及到Elo背后的数学原理了。对于Elo算法，如果我们把玩家之间的水平高低看做一个未知的黑盒子，那么以高斯函数为模型，以单局1V1战斗为数据的这一套计算过程，就是一个机器学习模型的训练过程。 如果学过机器学习的朋友可能马上就能认出，这不就是SGD(Stochastic Gradient Descent)吗？ SGD的收敛性是可证明的，只要满足对应的条件。我们回想一下匹配系统为什么需要水平相近的玩家匹配到一起，因为分数越相近，他们的分数差越接近于该点的梯度。

那么再看多人取平均后的分数结算，这不就是Mini-batch Gradient Descent吗？那么其收敛性，就毋庸质疑了。