至此，我们似乎已经为本章开头提出的问题找到了一个全面的解决方案。我们有了一个关于多支玩家队伍之间游戏（含平局）的概率模型，其中更简单的情形（两名玩家、个人而非队伍、无平局的游戏）作为特例出现。然而，当这个系统面向真实的 beta 测试者部署时，人们发现它的配对并不总是令人满意。特别是，某些玩家的技能值似乎“卡”在了较低的取值上，即使这些玩家已经打了很多游戏并有了很大进步，从而导致糟糕的配对。

网球

技能随练习而提高。

为理解其中的原因，我们注意到，我们模型中编码的假设并不允许玩家技能随时间变化。特别是，假设 3.1 说“每名玩家有一个技能值”——换句话说，每名玩家有单个技能值，完全没有提到这个技能值可以变化。既然玩家的技能确实会随时间变化，这个假设在真实数据中就会被违背。例如，随着玩家在某一特定类型游戏中积累经验，我们可能预期他的技能会提高。反过来，一名有经验的玩家若很少玩、荒疏了，其技能也可能退化。

你也许会认为，我们的在线学习过程会随时间更新玩家的技能分布，因而会允许技能变化。这是关于在线学习的一个常见误解，但它并不成立。我们当前的模型假设玩家的技能是一个固定但未知的量。在线学习所表示的并不是对一个演变技能值的建模，而是对这个未知的、跨时间固定的技能的不确定性的更新。如果一名玩家在某个技能水平上打了很长时间，那么我们关于其技能的分布就会变得非常窄。如果这名玩家随后突然进步了——也许是因为得到某种指导——当前的模型将很难追踪该玩家新的技能水平，因为在那个很窄的技能分布下它会显得极不可能。

复现该问题

为处理玩家技能会变化的情形，我们需要修改模型。但首先，我们需要复现这个问题，以便稍后检查我们是否已修复它。为此我们可以创建一个合成数据集。在这个数据集中，我们合成涉及一个百人玩家池的游戏结果。第一名玩家 Elliot 的初始技能固定为 110，且这个技能值按图 3.38 中红线所示的方式分阶段提高。

图 3.38

图 3.38：红色曲线展示了从一个百人玩家池中抽取的合成数据集里某玩家 Elliot 的技能值。所有其他玩家有固定技能（未展示）。蓝线展示了在我们（假设 Elliot 技能固定的）模型下 Elliot 推断出的高斯技能分布的均值。蓝色阴影区域展示了该分布均值上下一个标准差的范围。

其余 99 名玩家有固定的技能值，从一个均值为 125、标准差为 10 的高斯中抽取。对每一局游戏，随机选出两名玩家，通过向他们的技能值加入标准差为 5 的高斯噪声来评估他们在这局游戏中的表现。这正好对应于在图 3.6 的模型上运行祖先采样（就像我们在第 2.5 节中创建合成数据集时所做的那样）。

给定这个合成数据集，我们随后可以用图 3.10 的模型运行在线学习，其中游戏结果已知而技能未知。图 3.38 展示了在这个模型下 Elliot 推断出的技能分布。我们看到，我们的模型无法解释 Elliot 技能的变化：估计的技能均值与真实技能的轨迹不匹配，而且估计的方差太窄，容纳不下不断提升的技能值。由于方差很小，对技能均值的更新也很小，因此技能均值的演变太慢。这并不奇怪，因为模型的一个关键假设——即每名玩家的技能恒定不变——是不正确的。

为解决这个问题，我们需要改变模型中那个不正确的假设。我们不再假设固定的技能，而是要允许技能在每局游戏之间发生通常较小的变化。因此我们可以把假设 3.1 替换为：

  • 每名玩家有一个技能值，由一个连续变量表示，其值由该玩家上一局游戏中的技能值加上某个服从零均值钟形分布的技能变化量给出。

之前一名玩家只有单个技能变量，现在则为每一局游戏各有一个单独的技能变量。我们假设某名玩家在某一具体游戏中的技能值，由其上一局游戏的技能值加上某个从零均值分布中抽取的变化量给出。同样，我们通过把这个分布选为零均值高斯来使该假设在数学上精确。如果我们用 $\text{skill}^{\rm (old)}$ 表示玩家在其上一局游戏中的技能、用 $\text{skill}^{\rm (new)}$ 表示其在当前游戏中的技能，那么我们假设

$$\text{skill}^{\rm (new)} = \text{skill}^{\rm (old)} + \text{skillChange}$$

其中

$$p(\text{skillChange}) = \text{Gaussian}(0, \text{ChangeVariance}).$$

由这两个方程可以推出 [Bishop, 2006]

$$p\left( \text{skill}^{\rm (new)} \right) = \text{Gaussian}\left( \text{skill}^{\rm (old)}, \text{ChangeVariance} \right).$$

这使我们能够以因子图的形式表达我们新的假设。例如，在两名玩家彼此连续打两局游戏的情形中，因子图如图 3.39 所示。

图 3.39

图 3.39：两名玩家连续两局游戏的因子图，其中技能值被允许从一局到下一局发生变化。

玩家 1 在第二局游戏中技能的先验分布（记为 $\text{skill1}_{(2)}$）由一个高斯分布给出，其均值不再是固定的，而是由该玩家上一局游戏中的技能（记为 $\text{skill1}_{(1)}$）给出。图中所示的 ChangeVariance 为 0.16，它编码了我们的信念：技能从一局到下一局的变化应当很小。

在这个模型中进行在线推断可以如下进行。我们用图 3.10 所示形式的图对第一局游戏运行期望传播，得到每名玩家的后验高斯技能分布。然后我们让消息穿过连接两局游戏的高斯因子传递，如图 3.39 中蓝色所示。进入这些因子的入向消息就是来自第一局游戏的技能分布。由于对高斯因子所计算的卷积，随后发往新技能变量的输出消息是这些技能分布被展宽后的版本。这些展宽后的分布随后被用作这局新游戏的先验技能分布。因为我们在新游戏中展宽了先验，我们本质上是在说，我们对该玩家技能的不确定性稍高了一些。这反过来意味着新的游戏结果将导致更大的技能变化，因此我们会更擅长追踪技能的变化。看起来也许很奇怪：我们竟然能通过增加技能变量中的不确定性来改善系统的行为，但这之所以成立，是因为我们已经把模型修改得更贴近现实。在距上一局游戏以来的这段时间里，玩家的技能可能确实已经变了，而我们现在正确地建模了这种可能性。

我们现在可以在合成数据集上测试这个修改后的模型。结果由图 3.40 中的绿色曲线展示。

图 3.40

图 3.40：这展示了与图 3.38 相同的信息，另外以绿色加入了在一个允许技能值随时间演变的模型下 Elliot 推断技能的分布。

我们看到，当我们在模型中允许技能变化时，Elliot 变化的技能被追踪得好多了——我们解决了追踪时变技能的问题！这个模型已被应用于国际象棋的历史，以推算不同历史象棋棋手之间的相对强弱，尽管他们相隔数十年之久！你可以在 Dangauthier 等人 [2007] 中读到关于这项工作的全部内容。

最终模型

既然我们已经让模型能够应对变化的技能，它就满足了 Xbox Live 团队的所有需求。把所有扩展组合起来，下面是构建进我们模型的完整假设集：

  • 每名玩家有一个技能值，由一个连续变量表示，其值由该玩家上一局游戏中的技能值加上某个服从零均值钟形分布的技能变化量给出。
  • 每名玩家在每一局游戏中有一个表现值，它在各局游戏之间相互独立，其平均值等于该玩家的技能。表现的变动（对所有玩家都相同）围绕均值对称分布，且更可能接近均值而非远离均值。
  • 一支队伍的表现由该队伍内各玩家表现之和给出。
  • 游戏结果中队伍的顺序与他们在该局游戏中表现值的排序相同，除非两支队伍之间表现差异的大小低于某个阈值，此时这些队伍打成平局。

图 3.41：编码进我们最终模型的四个假设。

Xbox 手柄

这个模型涵盖了出现的各种不同游戏类型，包括队伍与多名玩家，它允许平局，并且追踪玩家技能随时间的演变。因此，当 Xbox 360 于 2005 年 11 月发布时，它采用了这个 TrueSkill 模型作为其在线技能评分系统。自那以后，TrueSkill 推断出的技能分布已被用于在数百款不同的 Xbox 游戏中执行实时配对。

模型的作用是推断技能，而如何用这些技能来执行配对的决策则是一个单独的问题。通常，这通过挑选那些游戏结果最不确定的玩家来完成。注意，这也往往会产生那些在学习玩家技能方面结果最具信息量的对局。配对过程还必须考虑到在相当短的时间内为玩家提供对手的需要，因此在玩家等待一局游戏组建所需的时间与其对手匹配程度之间存在一种天然的权衡。把配对问题分解为技能推断与配对决策这两个阶段，其强大之处之一在于：对配对准则的更改易于实现，且不需要对更复杂的建模与推断代码做任何改动。正如引言中所讨论的，能够把玩家与能力相近的其他玩家匹配起来、并且快速准确地做到这一点，是这个非常成功的服务的一个关键特性。

TrueSkill 产生的推断技能还被用于第二个不同的目的，即构建排行榜，展示玩家在某一特定类型游戏中的排名。为此，我们需要基于推断出的高斯技能分布为每名玩家定义一个单一的技能值。一种可能是使用分布的均值，但这没有考虑不确定性，可能导致某名玩家在排行榜上人为地偏高（或偏低）。相反，为某名玩家显示的技能值取为其分布的均值减去三倍其分布的标准差。这是一个保守的选择，意味着他的实际技能以很高的概率不低于其显示技能。因此，一名玩家既可以通过提高其分布的均值（靠战胜其他玩家）、也可以通过降低其技能中的不确定性（靠打大量游戏）来在排行榜上取得进步。

TrueSkill 模型有许多可以扩展的方式，以提升其对游戏过程特定方面建模的能力。2018 年，若干这样的改进被纳入 TrueSkill 2 模型 [Minka et al., 2018]，其做法是引入特别适合《战争机器》和《光环》等在线射击游戏的额外假设。例如，增强的模型利用了每名玩家的击杀数，而不仅仅是他们的最终排名。它还建模了一个人在不同游戏模式下技能的相关性。其他改进则用于处理诸如玩家中途退出游戏之类的情形，这类情形先前会导致不准确的技能估计。

我们已经看到 TrueSkill 如何持续地自适应，以追踪各个玩家的技能水平。在下一章中，我们将看到另一个自适应于个体用户的模型的例子，但是在一个非常不同的应用背景下：帮助整理你杂乱的电子邮件收件箱。

参考文献

[Bishop, 2006] Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

[Dangauthier et al., 2007] Dangauthier, P., Herbrich, R., Minka, T., and Graepel, T. (2007). Trueskill through time: Revisiting the history of chess. In Platt, J. C., Koller, D., Singer, Y., and Roweis, S. T., editors, NIPS. Curran Associates, Inc.

[Minka et al., 2018] Minka, T., Cleven, R., and Zaykov, Y. (2018). TrueSkill 2: An improved Bayesian skill rating system. Technical Report MSR-TR-2018-8, Microsoft.

下一章：清理你的收件箱