机器学习驱动的最优匹配系统

演讲：Josh Menke（343 Industries / Halo）
研究：Tom Minka（Microsoft Research）
协作：Ryan Cleven（The Coalition / Gears of War）
来源：GDC 2020 演讲，根据视频字幕翻译整理

开场

大家好，我是 Josh Menke，欢迎来到这场关于”机器学习驱动的最优匹配系统”的演讲。

到目前为止，我从事匹配（matchmaking）方面的工作已经超过 16 年了。我本身是有机器学习背景的，但坦白说，我之前从来没有把这两件事真正结合起来。我用机器学习来计算玩家的技能值（skill），但那只是一个被送进匹配系统的数字而已——我从来没有真正用机器学习去做匹配本身。

而这次我也并不是这套方法的发明者，我更像是它的使用者、它的客户。真正做完全部研究、把这套漂亮方法拿出来的人，是微软研究院（Microsoft Research）的研究员 Tom Minka。我目前在 343 Industries 负责 Halo 的相关工作，是这份工作的客户之一；另一位客户是当时在 The Coalition 工作室负责 Gears of War 的 Ryan Cleven。我们俩都对”用机器学习去改进匹配”这件事很感兴趣。

我可以说，在我做匹配的这 16 年里，这大概是我见过的、关于”如何做匹配”的最大一次跨越。希望大家会喜欢——我个人觉得它非常棒——下面我们开始正题。

我们要讨论的是哪种匹配？

先说清楚我们要谈的是哪种匹配。匹配指的是竞技多人游戏里，玩家寻找其他玩家一起对战、一起游玩的过程。它的工作方式大致是这样的：一群想要参加比赛的玩家会向匹配系统提交请求——他们可能分布在世界各地，并不在一起，但都想找一场比赛。他们会把一些信息发给匹配系统，比如自己的技能、所在位置以及其他有用的字段（细节我们后面再说）。匹配系统再用这些信息把玩家分到具体的比赛里，并组成相互对抗的队伍。

今天我们要谈的就是这种类型的匹配，以及如何去改进它。

什么是机器学习？

既然要用机器学习，我们也给它一个简单的定义：机器学习是一种用数据来自我调参的算法，而不是靠人手工去调。

那这两件事怎么结合呢？传统的匹配算法是靠人去手动调参的，我们要做的，就是改用机器学习，让匹配算法基于数据自动地调出参数。

当下的”主流”匹配是怎么做的？

今天最常见的匹配系统大致是这样的：玩家提交进来，匹配系统”期望”能凑出一场最好的比赛，找不到就等，等到最后只能”将就”一个不那么理想的结果。

以技能匹配为例，匹配系统看到一个玩家，最希望给他找一个技能相近的对手。如果一时找不到，它就等下去，最后只能接受一场不平衡的对局。差不多过去很多年，自动匹配就是这样做的。

我们用一个例子直观感受一下。随着时间推进，玩家陆续进入队列：玩家 1 来了，说”我想打一场”，系统让他等，因为没人能跟他匹配；玩家 2 来了，系统看了看，觉得”这俩匹配得不算好，再等等说不定能有更合适的”；玩家 3 来了，”还是不算理想，但玩家 1 已经等很久了，凑合一下吧”，于是把 1 和 3 组合成一场比赛；这时玩家 4 来了——糟糕，4 才是 1 的”完美对手”。但比赛已经开了，4 只能去和 2 凑一场，将就着打。

注意我说的”完美对手”这件事——如果匹配系统能预知未来，它本该等到玩家 4 出现再开局，给玩家 1 一场更好的比赛。也就是说，如果匹配系统知道未来会发生什么，匹配问题就可以退化为一个已知输入下的组合优化问题。 这正是这次分享的核心思路：用机器学习去预测未来会来什么样的玩家，再用优化方法在已知未来的基础上撮合出最优的比赛。

传统匹配是怎么搭出来的：规则系统

在介绍那套更花哨的方法之前，我们先看看今天主流的匹配是怎么实现的，以此作为起点来看机器学习能从哪里切进去。

搭一套传统的匹配系统时，我们通常会先给匹配器写一套规则，让它依规则去组比赛。常见的规则比如：

• 比赛的形态：例如告诉匹配器我们要 8 个人、分成两队各 4 人。
• 延迟的扩张规则：一开始严格要求玩家到服务器的 ping 不超过 50ms，但随着等待时间变长，这个上限会逐步放宽到比如 200ms。
• 技能差距的扩张规则：和延迟类似，刚开始限制得很死，随着等待时间放宽。
• 一些必须严格匹配的”账务”字段：比如版本号要一致，要同一款游戏，能连上同一台服务器，playlist 必须一致（Halo 用 playlist 来区分玩家想玩什么模式，只有都想玩同一个模式的玩家才能凑到一起）。

举个例子，我们用 JSON 写一条扩张规则大概长这样：起始时只允许 0.2 的技能差距，但允许它在一段时间内逐步扩张到某个上限。细节不重要，重要的是要注意——一条规则本质上就是一组数。 后面会反复用到这一点：当你要优化的对象是一组数时，有很多非常成熟的数值优化方法可用。

匹配器拿着这套规则，每来一个请求就比对一下。请求本身大致长这样：玩家提交时间（系统需要知道他等了多久）、玩家 ID（用于区分谁是谁）、技能值、所在位置（可能是一张到各数据中心的延迟表，也可能直接告诉系统”我喜欢 East US”）、想玩的 playlist ID、版本号等等。匹配器拿到 Bob 和 Alice 的请求后，挨条规则去判断——比如”技能差距是否小于 10？Alice 是 32，Bob 是 27，差 5，OK”；如果所有规则都通过，这两个玩家（或两支队伍）就可以匹成一场比赛。

这种做法的两个本质问题

第一个问题是：这些规则是全球统一应用的。 所有玩家在世界各处都受同一套门槛限制。但如果我在英国，要和美国玩家打，我心里更希望技能差距能更小一些来弥补跨区损失；而如果我本地匹配能拿到极低延迟，我也许愿意为此放宽一点公平性。一套全球规则没办法区分这些情形。

第二个问题是：这些规则是静态的。 无论是高峰还是凌晨低谷，门槛都一样。这意味着在低峰时段，玩家会先按”严格规则”等很久，等系统逐步把门槛放宽——但其实那些”更好的匹配”在低峰时段根本不会出现，你只是白白让玩家多等了。

这里其实就有一条非常实用的可外带回去的建议：让你的匹配器具备实时统计能力，能看见此刻人口和请求量的变化，根据流量动态地调整起始门槛。低峰时段直接从”放宽后”的门槛开始，不要再让玩家干等了——光这一条改进，已经能给玩家带来明显的等待时间收益。

用”可预测性”来衡量匹配的不公平

为了把后面的现象讲清楚，先引入一个指标——可预测性（predictability）。它衡量”实力更强的那队赢的比例”，因此可以理解成一种”不公平度”：

• 50% 表示这场比赛在两队之间不可预测，相当于势均力敌的公平比赛；
• 90% 表示”较强一方”十场赢九场，明显不公平。

我接下来都会用 predictability 来表达匹配公平性，要回答的问题就是：”较弱的那队还有没有赢的机会？”

静态规则导致的几条不良曲线

我们做了一些现网观测：

• 请求量：一天之内有非常大的波动，波峰和波谷之间的落差很大；
• 等待时间：高峰时段平均等待约 20 秒，但到低峰会涨到 60–80 秒；
• 公平性：高峰时较强队伍的胜率约 70%，到了低峰会逼近 100%；
• 延迟：高峰时玩家平均”过剩延迟”约 10–12ms，低峰会涨到接近 100ms。

更值得一看的是另一张图——它展示了等待时间和可预测性之间的权衡。横轴是等待时间，纵轴是可预测性，理想状态是左下角（既不让玩家等太久，又能保证公平）。在静态规则下，你其实是先固定一个可预测性目标，然后被动接受由此产生的等待时间。

但从曲线上你会发现：在某个”拐点”附近，再多等就只换回非常微小的公平性提升——比如本来等 134 秒能拿到 52% 的预测度（弱队 48% 胜率，已经很不错了），要把这个数再压到 51%，等待时间得翻一倍以上。这显然不划算。而且这条曲线本身一天之内是会变的：低峰时段你应该愿意更早接受将就，因为多等几乎换不回任何质量提升。 静态规则永远捕捉不到这种动态特性。

总结一下当前主流匹配的问题

主流匹配会忽略以下几件事：

• 请求到达的实时速率：现在的人比平时更多还是更少？
• 当下的技能分布：现在这个时间点有没有高水平玩家在线？
• 区域分布：全球流量可能在低位，但欧洲这片区域可能正高峰，玩家的偏好应该不同。

结果就是两种”将就”二选一：要么让玩家等很久，让规则慢慢扩张到能匹上为止；要么强行接受我们明知道质量很差的比赛。最糟糕的情况是两件事同时发生——玩家既等了很久，又被塞进一场糟糕的比赛。这是真正需要我们解决的痛点。

TrueMatch：一种更优的做法

要谈”最优”，先要给”最优”一个定义。我们引入一个效用函数（utility function），把”最优”具体化为一个可优化的数。同时我们用上：

• 实时统计：玩家到达率与技能分布（都按区域来分）；
• 机器学习预测：用模型预测未来一段时间会来什么样的玩家；
• 优化器：在预测到的未来上做组合优化，最大化效用函数。

效用函数里我们关心的几个指标包括：

• 等待时间：玩家不希望永远等下去；
• 技能差距：用前面说的 predictability 来表达；
• 强弱玩家的胜率是否对等（equal-run win rate）：是不是无论强弱都有合理的胜率；
• 延迟：到服务器的 ping 有多重要。

这套方法我们称之为 TrueMatch：实时地按你定义的效用函数自适应地优化匹配。

TrueMatch 与传统匹配的高层对比

• 自动调参 vs 手动调参：传统系统需要人手定期去调，而 TrueMatch 会全天 24 小时实时调，不再依赖”等玩家抱怨—再去调”的循环。
• 按区域和技能段定制 vs 全局一套规则：每对区域、每个技能段都有自己的一套规则。
• 可以做个性化的预测：能给每个玩家一个根据他所在区域和技能段定制的、靠谱的等待时间预测。
• 可监控、可告警：因为系统始终在做预测，一旦真实结果和预测出现持续偏差，就可以自动发出告警，提示有某种异常正在发生。传统匹配往往要等玩家来抱怨才会发现问题。

目前 TrueMatch 已经在 Gears of War 5 上线，Halo 5 也切到了它，未来甚至有可能做成第三方可用的标准服务。

效用函数：把”最优”量化

我们把它称作统一目标函数（unified objective function）。每一场比赛都有等待时间、技能差距、玩家延迟，对整段人口我们还能算胜率分布——把这些维度按权重相加，就得到一个数，用来描述”这一场（或某段时间、某个区域）的匹配质量到底如何”。

为了方便设计师使用，我们有一个小技巧：把等待时间的权重锁定为 1。 这样其它指标的权重就直接表示成”为了换得 1 单位的该指标改善，你愿意多等几秒”。比如把延迟的权重 w3 设成 10，意思就是”为了少 1ms 延迟，我愿意让玩家多等 10 秒”。这种”以时间为锚”的表达方式让设计师可以直接在等待时间和其它指标之间做权衡——“多等 1 秒 vs 公平度多 1%”，非常直观。

效用函数还有几个延展用法：

• 不一定只用一个全局函数，可以给每个游戏甚至每个玩家配一份效用函数，描述他们各自重视什么；
• 它是评估匹配改动的好工具——只要明确知道你看重什么，任何变更都可以通过效用函数评估是否真的让结果更好。

如果你的匹配器里已经有一些既定的门槛和差距值，要把它反推成效用函数里的权重并不困难（细节展开太长，这里就不细讲了）。

TrueMatch 的运行循环

宏观上看，TrueMatch 走的是这样一个循环：

1. 按类型计数请求：每隔一个固定的时间间隔，TrueMatch 统计每个区域、每个技能段各来了多少玩家，让系统对”现在的人口长什么样”有个清晰的概念，进而能预测”接下来会来什么人”。
2. 优化器选择规则：基于上述预测，挑出一组规则，使在预期人口下产出的比赛效用最高。
3. 按规则去匹配，玩家开打。
4. 测量结果：回收每张匹配单的真实等待时间、真实延迟、真实公平性等。
5. 自我更新：根据真实结果，TrueMatch 把”人口计数 → 实际匹配结果”之间的映射更新得更准。
6. 回到第 1 步，再次计数，进入下一轮。

一个典型的循环周期约为 15 分钟。在这个节奏下，系统一边动态调整匹配规则，一边持续校准自己”预测匹配效果”的能力。

TrueMatch 的组件细节

1. 人口跟踪器（Population Tracker）

玩家的匹配请求先进入人口跟踪器。它统计当前各类型玩家的数量，输出一个人口模型——可以理解为对当前请求流的一个紧凑摘要：现在大致是什么样的玩家在排队。

实现方式可以很简单：用一个循环缓冲区保存最近的 1000 条请求，然后实时算这 1000 条里的统计量。更紧凑一点的做法是直接维护直方图——按技能桶、按区域桶累计计数，这样即便人口有几百万级，也能压缩成一个非常小的结构。我们实际用的是后者。

最终给到下游的，是一个”按 (技能桶, 区域桶) 索引的请求速率表”。例如：”巴西区、技能 0.3–0.4 的玩家，当前请求率是 0.01 次/秒”。

2. 指标预测器（Metric Predictor）

指标预测器的工作是：输入”当前人口模型 + 当前规则”，预测如果按这些规则做匹配会发生什么——比如各区各技能段玩家的等待时间、ping、公平性等等。机器学习就主要发生在这里。

它会把预测结果交给优化器，优化器据此判断”这套规则的效用够不够好”。如果不够好，优化器在还没有开始真实匹配之前，就可以基于预测的效用先调整规则，反复几轮，直到拿到一组更优的规则再下发执行。

随后真实匹配跑起来，预测器会拿到真实结果反馈，用机器学习手段更新自己内部的模型，让”人口 + 规则 → 指标”这条映射变得越来越准。每个指标（等待时间、公平性、延迟……）都有自己的一套带可学习参数的公式，这些参数会随实际反馈不断调优。

等待时间公式举例

我们看其中一个公式——等待时间的预测。

最初版本是一个静态近似：基于”对玩家 T 来说，有多少潜在玩家可以和他匹配”这一信息，反推他要等多久。

但我们的比赛通常不是 1v1，可能是 4v4，也可能更多。为了不必手工去逐一推导每种规模、每种动态特征下的修正项，我们的做法是：给这条公式加两个可学习参数——一个缩放因子 C、一个平移因子 B，让它们直接从数据里学。

直观上理解：

• C 会随每场比赛需要的玩家数变化：1v1 时 C=1，规模更大时 C 会按”需要再等一个玩家、再等一个玩家”的方式合理放大；
• B 主要吸收”匹配器为了凑齐工单而引入的缓冲时间”——大多数传统匹配器都会留一段缓冲来攒工单，B 把这段缓冲从数据里学出来。

这只是众多公式之一的示例。每一个指标都有结构类似的、可自学习的小模型，让 TrueMatch 在一天的不同时段都能更准地预测”规则调整后会怎样”。

3. 优化器（Optimizer）

回头再看规则的形态——它实质上是一组”属性 + 数”，比如”技能差距 ≤ X”。我们的匹配器不会让优化器去发明新的规则形态，规则的”骨架”是固定的；优化器要做的，只是去搜索那一组数。

由于本质上是在一个数值向量上做优化，可用的现成方法非常多：梯度下降、分支定界等等。配上来自指标预测器的”效用函数”，整个流程就是：调一组数 → 问预测器这组数对应的效用 → 继续调 → 收敛，得到一组（你相信是）最优的规则。

优化”规则的形态”本身：百分位映射

举一个最经典的规则起点：“任意两个玩家的技能差距 ≤ 某个数 X”。绝大多数现在还在用的匹配系统，差不多就是这种规则。

那么，这是不是一个好的规则形态？ 当我们把”等待时间 vs 可预测性”画成那条曲线，会发现：规则的形态本身决定了这条曲线长什么样。 同一时间点上，能不能找到一条更好的曲线？

微软研究院（自然）问了这个问题。他们的策略是：先把规则改写成一种等价但更适合搜索的形式。具体来说，他们证明了——“技能差距 < 某个数”这种规则，可以重写成”某个关于技能的函数之差 < 1”。也就是说，真正的匹配器规则永远是 |a − b| < 1，你不需要改它；你要改的是塞进 a、b 的那个函数。

如果想让”技能差距不超过 0.5”，只要让函数 F 取 2 × skill，再放进 |a − b| < 1，就等价了。这本身就是一个值得带回去的工程改进：你完全不需要去改匹配器内部的规则比较，只需要改变你喂给它的”技能值”是怎么算出来的。 这让你可以非常方便地在线调匹配的”松紧度”。

接着，他们用这种参数化形式去搜索所有可能的规则曲线，找到了最优解。但他们最终在实践里没有直接用那个”最优解”——因为还有一个几乎一样好、但用起来简单很多的形态，那就是我们最终采用的方案。

我们最终用的：基于百分位的匹配

它的做法是：

1. 把玩家技能先映射成百分位——这名玩家在整体玩家分布中的第几百分位？比如他是第 97 百分位、第 80 百分位？
2. 给这个百分位乘上一个缩放因子——这个缩放因子是 TrueMatch 真正去优化的那个参数。

这个缩放因子的实际含义是”你愿意在多宽的百分位区间里去匹配”。比方说，你不再说”这名玩家可以和技能在 1.5 到 2.5 之间的玩家匹配”，而是说”这名玩家可以和位于第 80–82 百分位的玩家匹配”。

这样做最大的好处是：任何玩家都看到一段同样宽度的百分位，意味着每个人能匹的潜在玩家数量是一样的，因此所有玩家的等待时间就是恒定的。

举个例子。假设我们允许的”差距”恒为 1，把缩放因子取为 10：

• 三个玩家 A、B、C，原始技能分别是 0.5、1.0、1.5。
• 把它们映射到百分位（按标准正态分布大致估计）：A 在第 69 百分位、B 在第 84 百分位、C 在第 93 百分位。
• 缩放因子是 10，A 和 B 的百分位差 0.15 × 10 = 1.5，超过 1，A 不能匹 B；B 和 C 的百分位差 0.09 × 10 = 0.9，没超过 1，B 可以匹 C。

注意这与”原始技能差距”做法的本质区别：A 在分布稠密的中段，会被要求更挑剔；B、尤其是 C 在分布尾部，被允许更宽的原始技能差距，因为他们四周本来就稀疏。但他们看到的”可匹对手数量”是一样的，所以等待时间还是一致。

这种规则形态究竟好多少？

我们做了仿真：

• 黄色曲线：用原始”技能差距 ≤ X”那种传统规则能达到的最优等待—公平曲线；
• 蓝色曲线：用上面这种”映射到百分位 + 缩放”的规则能达到的曲线。

蓝色明显更靠近左下角——也就是说，对于同样的等待时间，我们能拿到更好的公平性；对于同样的公平性，我们能让玩家等得更短。

所以 TrueMatch 是”双重最优”：我们不仅在固定的曲线上找到最优点，还在所有可能的曲线里找到了一条最好的曲线。

如果你今天还没办法把完整的 TrueMatch 落地，那么这里有一个非常值得带回去的小改进：别在原始技能差距上做匹配，改成在百分位差距上做。 即使只是允许玩家在自己百分位的 ±1% 或 ±2% 内匹配，再根据当下流量动态调一调这个百分比，效果就已经会好很多。

总结一下我们最终的规则：

• 比较的是技能百分位而不是技能本身；
• 所有玩家看到的”候选池”大小相同；
• 这个”百分位宽度”会随着当下流量动态缩放——高峰时段可以收紧到 1% 以内，低峰时段放宽到 10% 左右。

跨区域的处理

那不同区域之间怎么办？我们的做法是为每一对区域单独维护一组优化好的规则。也就是说，把”美区玩家 vs 欧区玩家”作为一类，专门有一条规则在管它该用多大的”差距”，再交给 TrueMatch 去优化。

下面这个小例子很直观。一位欧区玩家正在排队：

• 传统做法：她先按欧区严格匹配，等了 5 分钟还没匹到（鱼池太浅），系统宣告超时；她只好手动允许跨区到美区匹配——美区延迟更差，她不情愿，但只能将就。问题是，她已经被白白浪费了 5 分钟才确认这件事。
• TrueMatch 做法：她不需要先在一个池子里等够再去另一个池子，而是同时在两个池子里下网。她在欧区下的是”大网”——可以接受更宽的技能差距，以便尽量多地吃到欧区玩家；在美区下的是”小网”——更不容易钓到美区玩家。两张网的大小直接体现了她”宁愿等欧区”的偏好。一旦两张网加起来够 7 条鱼（凑齐一场），匹配就成立。结果是：她还是看到了和其他玩家一样大的整体候选池，但搜索过程更符合她的偏好，等待时间也更合理。

实证：Halo 5 6 人 Free-for-All

我们拿一个真实播放列表来验证——Halo 5 的 6 人混战（Free-for-All，6 个玩家全部互相对抗）。挑这个 playlist 的原因是它的请求率波动非常大：低谷可能只有高峰的十分之一。它不是最热门的 playlist 之一，反而恰好提供了一个”高波动”的实验环境。

整体效用对比

为了让对比有参照，我们做了一个 Oracle（预言者）基线：它仍然使用传统的静态规则，但允许它”预知未来”，从而能为整一天选出全局最优的那一套静态参数。

• 黄线（TrueMatch）：整天的效用值相对平稳，即使在低峰也只略受影响；
• 蓝线（Oracle）：尽管知道未来，仍然在低峰段无法维持同样高的效用。

公平性（predictability）

低峰时段，TrueMatch 主动放宽了允许的技能差距（也就是 predictability 上升、比赛更不公平），目的是把”自己被要求满足的那个效用目标”撑住。Oracle 由于本质是静态规则，没多大调整空间，整体上预测度维持得更平稳——也就是说低峰时段它的比赛更公平一些。

等待时间

但代价立刻在等待时间上显现：

• TrueMatch 把全天等待时间都压在 5 分钟以内；
• Oracle 即使已经是”全知最优静态规则”，低峰时段的等待时间也会冲过 10 分钟、甚至 15 分钟，仅仅为了换回 10% 左右的公平性提升。

按我们效用函数的设计意图，这种取舍并不划算。

结论

• 在正常人口时段，TrueMatch 与 Oracle 的效用基本一致；
• 在低峰时段，相对于 Oracle，TrueMatch 把”距离最优静态规则的 gap”直接减半；
• 这让等待时间相对静态最优规则减少了 72%——即使那是”预知未来”挑出来的最优静态规则；
• 代价是 13% 的公平性。换句话说，我们用 多等 600 秒（10 分钟） 的代价换回 13% 公平性，这种交换从设计意图上看并不合算。

也就是说：TrueMatch 的行为完全符合我们效用函数所表达的设计意图。

几条主要收益

TrueMatch 带来的几条主要收益：

1. 效用函数直接让设计师能在”等待时间”上为各项指标定价：愿意为 1ms 更好的延迟多等多久？愿意为 1%/3%/5% 公平度多等多久？这些都可以直接通过效用函数说清楚。
2. 真正可信的个性化预计等待时间：因为指标预测器对每个区域、每个技能段都能给出预测，所以可以告诉每个玩家一个个性化的、靠谱的”你大概要等多久”。在我做匹配的这些年里，这一直是一种”圣杯”——既能管理玩家预期，又是真的准。
3. 实时统计 + 实时反馈：实时调出最优规则，也实时改善”规则 → 效果”这条映射的精度。这是人工不可能全天候做到的，机器学习正好补上了这一块。

即使无法完整落地 TrueMatch，也可以带走的小改进

如果你今天没法立刻把完整 TrueMatch 上线，至少可以考虑下面这套”轻量版”：

1. 持续维护一份对当前人口的简单模型：每小时若干次刷新一次，把不同时段下技能分布的若干分位点存起来，对人口规模有个估计就行。
2. 建立技能 → 百分位的映射：玩家技能 5.2 对应的是第 87 百分位（举例）。
3. 把匹配条件从”原始技能差距”换成”百分位差距”。
4. 用实时统计动态调整百分位窗口宽度：高峰收紧，低峰放宽。

只做这些，已经能让你的玩家在低峰时段不至于”先等很久再被塞进一场质量差的比赛”。如果完整的 TrueMatch 一时落不下来，至少把这一小段先用上。

结束语

以上就是今天的全部分享。我自己在 Halo 5 上使用 TrueMatch，体验非常好，它解决了我这些年在匹配上遇到的很多痛点。希望这篇文章对大家也有用，感谢各位。