到目前为止，我们已经为两名玩家之间、以其中一方获胜告终的一局游戏构建了一个概率模型。为处理 Xbox Live 所需的各种各样的游戏，我们需要扩展我们的模型以应对若干额外的复杂性。具体而言，真实游戏可能以平局结束、可能涉及超过两名玩家、并且可能在多支队伍之间进行。现在我们将展示如何扩展最初的模型以考虑这些复杂性。这种灵活性很好地说明了基于模型的机器学习方法的强大之处。

具体来说，我们需要扩展我们的模型，使它能够：

  • 在结果为平局时更新技能；
  • 对团队游戏，更新各个团队成员的技能；
  • 适用于超过两名玩家的游戏。

基于模型的方法允许以透明的方式并入这些扩展，从而产生一个能够处理上述所有复杂性、同时仍保持可理解、可维护的解决方案。

如果一局游戏可能以平局结束怎么办？

在我们当前的模型中，在某一局游戏中表现值较高的玩家就是那局的赢家。对于也可能以平局结束的游戏，我们可以引入平局边界（draw margin）这一概念来修改这个假设：只有当一名玩家的表现超过另一名玩家至少一个平局边界的值时，他才是赢家。数学上这可以表达为

$$ \begin{array}{lll} \text{如果} & \text{Jperf} > \text{Fperf} + \text{drawMargin} & \text{Jill 获胜} \\ \text{否则若} & \text{Fperf} > \text{Jperf} + \text{drawMargin} & \text{Fred 获胜} \\ \text{否则} & & \text{游戏平局。} \end{array} $$

这在图 3.32 中作了图示。

图 3.32

图 3.32：表现空间中各区域的图示，标明 Jill 获胜、Fred 获胜、以及游戏以平局结束分别对应的区域。

因此我们把假设 3.3 修改为：

  • 表现值较高的玩家赢得游戏，除非他的表现与对手表现之差小于平局边界，此时游戏为平局。

平局边界的值代表我们模型中的一个新参数，而我们可能并不知道其恰当取值。当我们引入一种新类型的游戏、或修改现有游戏的规则、以致尚未看到任何游戏结果时，尤其如此。为解决这个问题，我们干脆把平局边界当作一个新的随机变量 drawMargin，其值将从数据中学习得到。因为 drawMargin 是一个连续变量，我们把它选为一个高斯。这可以表达为一个因子图，如图 3.33 所示。

图 3.33

图 3.33：包含平局可能性的两名玩家之间一局游戏的 TrueSkill 模型。

变量 Jwins 被 outcome 取代，后者是一个离散变量，取 JillWins、Draw 或 FredWins 之一。WinLoseDraw 因子只是一个函数：当 Jperf、drawMargin 和 Fperf 三个值与 outcome 的取值一致时其值为 1，否则为 0。有了这个更新后的因子，我们需要对从因子节点发出的消息做相应的修改。这里不会详细讨论这些，感兴趣的读者可以参考 Herbrich 等人 [2007] 以及 Moser [2010] 的一篇出色的博客文章。

为简化后续对其他模型扩展的讨论，我们在本章余下的因子图中将忽略平局这一修改，尽管所有后续模型在需要时都可以类似地修改以纳入平局。

如果一局游戏中有超过两名玩家怎么办？

多名玩家

超过两名玩家的游戏需要一个更复杂的模型

假设我们现在一局游戏中有超过两名玩家，例如《光环》中的“大乱斗”（Free for All）游戏，其中八名玩家同时彼此对战。这样一局游戏的结果是所涉玩家之间的一个排序。以我们基于模型的方法，纳入这样的改动只需做一个合适的假设、构建相应的因子图，然后再次运行期望传播。我们新的假设 3.3 可以表述为

  • 游戏结果中玩家的顺序与他们在该局游戏中表现值的排序相同。

如果游戏中有 $N$ 名玩家，那么这个假设可以在一个因子图中用 $N-1$ 个 GreaterThan 因子来刻画玩家排序。图 3.34 就三名玩家的情形作了图示。

图 3.34

图 3.34：涉及三名玩家的一局游戏的因子图。图中还展示了对该图应用期望传播时出现的一些消息。

注意，我们本可以为每一对可能的玩家引入一个单独的“大于”因子。对于 $N$ 名玩家共有 $N(N-1)/2$ 个这样的因子。然而这些额外的因子只包含冗余信息，会导致一个不必要地复杂的图。$N$ 名玩家的排序可以用 $N-1$ 个大于因子来表达，只要选择它们去连接排序序列中相邻的玩家对即可。实际上，因为我们知道游戏的结果，我们可以选择一个相对简单的图来刻画它。

推断深入探讨

在这个可选小节中，我们展示为什么即便对一个树结构的图，使用期望传播也可能需要迭代求解。如果你想专注于建模，尽可跳过本小节。

扩展到超过两名玩家引入了一个与我们期望传播算法相关的有趣效应。我们在第 2.2 节中看到，如果我们的因子图具有树结构，那么置信传播在扫过全图一遍后（每条连接的每个方向各传一条消息）就给出精确的边缘分布。类似地，如果我们现在把期望传播应用于图 3.10 的两名玩家图，同样只需每个方向各扫一遍。这是因为期望传播近似所用的“上下文”消息是固定的。然而，当我们有超过两名玩家时，情况变得更复杂。图 3.34 的图具有树结构、没有环，因此精确的置信传播只需扫一遍。然而，考虑用期望传播来计算输出消息 (A)。这需要入向消息 (D) 来为近似提供“上下文”。然而消息 (D) 依赖于消息 (C)，后者本身又是用消息 (B) 作上下文、通过期望传播计算的，而消息 (B) 反过来又依赖于消息 (A)。因此期望传播要求我们迭代这些消息，直到达到某个合适的收敛准则（即消息的变化落到某个阈值以下）。因此我们修改消息传递调度：首先把消息从技能节点向下传到表现节点（和之前一样），然后在表现节点之间来回做多次传递直到收敛，最后再把消息向上传到技能节点。

回到图 3.29 和图 3.30，我们看到当较弱的玩家（Fred）赢得游戏时，分布在先验与后验之间的偏移更大。现在我们重复该实验，只是加入第三名玩家（Steve），他的先验技能分布为 Gaussian(140, 40²)，而 Jill 保持为 Gaussian(120, 40²)、Fred 保持为 Gaussian(100, 5²) 与之前相同。我们把多玩家 TrueSkill 模型应用于一局结果为 Jill 第 1、Fred 第 2、Steve 第 3 的游戏。

图 3.35

图 3.35：对 Jill（蓝色）、Fred（红色）与 Steve（绿色）之间一局三人游戏应用 TrueSkill 模型、且 Jill 获胜、Fred 第二、Steve 垫底情形的结果。先验分布以虚线曲线表示，相应的后验分布以实线曲线表示。

结果显示于图 3.35。首先，注意到由于 Steve 本被期望是最强的玩家、实际却垫了底，他的后验均值显著向下移动（移到另外两名玩家之下）。其次，注意到 Jill 和 Fred 均值的变化方向与图 3.29 中相同，但比之前更明显。这同样是因为整个游戏结果更令人意外。

现在让我们考虑一个不同的结果，把 Fred 和 Jill 对调，即 Fred 第 1、Jill 第 2，而 Steve 仍是第 3。图 3.36 展示了三个技能分布的（相同的）先验与在这个新结果下新的后验。

图 3.36

图 3.36：与图 3.35 相同，但为 Fred 获胜、随后是 Jill、Steve 垫底的情形。

因为 Fred 的技能不确定性很低，给定游戏结果后他的曲线几乎没有变化。Fred 获胜这一事实强有力地证明他的技能高于 Jill 或 Steve。结果 Jill 和 Steve 的技能曲线都移到了 Fred 的左侧。因为 Jill 击败了 Steve，她的曲线移动得比他少，所以现在 Steve 的均值最低，而之前它是最高的。更有趣的是，如果我们把图 3.36 中 Steve 的后验技能曲线与图 3.35 中的相比，会发现在这个结果下它甚至更靠左，尽管 Steve 在两种情形下都垫了底。这是因为我们现在必须把 Jill 的技能安置在 Steve 与 Fred 之间，而在第一个结果中，Steve 的技能只需移到 Fred 的左侧即可。所以在这局多玩家游戏中，其他玩家的相对排序会影响我们对 Steve 技能的估计！

如果游戏由队伍进行怎么办？

Xbox Live 上许多游戏可以由玩家队伍进行。例如在《光环》中，另一种类型的游戏在各由八名玩家组成的两支队伍之间进行。游戏的结果只说明哪支队伍是赢家、哪支是输家。我们的挑战是利用这一信息来修正每一个个体玩家的技能分布。这是一个信用分配问题（credit assignment problem）的例子，其中当只给出整支队伍的结果时，我们必须弄清胜利的功劳（或失败的责任）应如何归属到各个玩家身上。解法与前两种情形相似：我们对个体玩家技能如何组合以影响游戏结果做一个假设，构建一个编码该假设的概率模型，然后运行推断来更新技能分布。无需发明新的算法或设计新的启发式方法。

队伍

一支队伍的表现取决于各个玩家的技能。

下面是我们在建模团队游戏时可以使用的一个合适假设，它将替换假设 3.3：

  • 一支队伍的表现是其成员表现之和，表现值最高的队伍赢得游戏。

我们现在可以构建一个对应于该假设的因子图。例如，考虑两支队伍之间的一局游戏，每支队伍各有两名玩家。相应的因子图如图 3.37 所示。

图 3.37

图 3.37：两支队伍的 TrueSkill 模型的因子图。第一支队伍由玩家 1 和 2 组成，第二支队伍由玩家 3 和 4 组成。

一支队伍的表现由组成该队伍的玩家的表现决定。我们上面的假设是队伍表现由各个玩家表现之和给出。这对于像《光环》这样的协作型团队游戏或许是合适的。然而，在其他类型的游戏中，其他假设可能更合适。例如，在一场只有最快的玩家决定队伍结果的赛跑中，我们可能会做另一种假设：

  • 一支队伍的表现等于其任一成员的最高表现，表现值最高的队伍赢得游戏。

在本节中，我们讨论了对核心 TrueSkill 模型的各种修改，即纳入平局、扩展到多名玩家、以及扩展到团队游戏。这些修改可以按需组合，例如通过构建合适的因子图、然后运行期望传播，来允许一局包含平局的多队伍游戏。这不仅凸显了基于模型的机器学习方法的灵活性，也凸显了并入修改的便捷性。只要模型构建者能够描述数据生成的过程，通常就很容易表述出相应的模型。相比之下，当一个解决方案仅表达为一个算法时，我们可能很难看清应如何修改该算法以适应问题规范的变化。在下一节，我们将通过对模型再做一处修改——放宽玩家技能固定不变这一假设——来结束我们对在线游戏配对问题的讨论。

本页引入概念回顾

信用分配问题（credit assignment problem）：把一份奖励分配给一组实体（例如若干人）的问题，这些实体都对结果有所贡献。

自我评估 3.4

以下练习将帮助你巩固本节所学的概念。做题时，回顾正文或下面的概念小结可能会有所帮助。

  1. 为一个同时允许平局、两人队伍与多支队伍的模型勾画一个因子图。你需要把图 3.33、图 3.34 和图 3.37 的因子图组合起来。你的草图可以相当粗略——例如，你应给因子命名（如“Gaussian”），但无需为因子参数提供任何数字。
  2. 把你在上一次自我评估中的 Infer.NET 模型扩展为三名玩家，并复现图 3.35 和图 3.36 的结果。
  3. 【项目点子】网上有各种各样的体育赛事结果数据可用。找一组合适的数据，构建一个恰当的模型来推断所涉队伍或玩家的技能。按推断出的技能对队伍或玩家排名，并判断你是否认为该模型推断出了一个好的排名。如果不是，诊断原因，并探索对你模型的修改以解决该问题。

参考文献

[Herbrich et al., 2007] Herbrich, R., Minka, T., and Graepel, T. (2007). TrueSkill(TM): A Bayesian Skill Rating System. In Advances in Neural Information Processing Systems 20, pages 569–576. MIT Press.

[Moser, 2010] Moser, J. (2010). The Math behind TrueSkill.

下一节：允许技能变化