网易伏羲GDC分享：匹配 在网易游戏中的智能匹配算法实践_游戏陀螺

带不动队友、仙人局、被虐到怀疑人生、心仪位置被抢、队友不合作甚至挂机、职业组合不平衡….糟糕的体验往往让新手难以上手，老手愤而弃坑。因为体验差导致玩家流失，对游戏的口碑和长久发展造成了难以估量的负面影响。

玩家匹配算法对玩家游戏体验一直至关重要，如何通过AI算法高效地构建一个能有效兼顾平衡性和娱乐性、保障玩家游戏体验的匹配系统一直是游戏算法团队的重点研发课题。在GDC2021 核心会议中，伏羲的匹配团队围绕“应用AI算法对游戏的匹配算法进行优化实践”进行算法、工程实践经验方面的具体介绍。

网易伏羲实验室在人工智能领域积极探索，推出了游戏行业人工智能解决方案，横跨AI反外挂、AI竞技机器人、AI 对战匹配以及 AI 剧情动画制作四大AI能力，实现了AI 技术在游戏行业的新突破。本次分享的内容就是源于AI对战匹配系统在游戏中的运用经验。

主讲人：巩琳霞（Linxia），2017年加入网易伏羲，主要负责用户建模相关研究和应用落地工作，主要研发方向有玩家匹配、外挂检测、用户留存，在KDD、CIKM、GDC等AI和游戏相关国际顶会上有多篇发表，本次将代表伏羲匹配团队介绍匹配算法研究和应用成果。

玩家匹配是匹配系统将等待队列中的玩家分配到不同比赛当中的过程。匹配系统可以通过多种方式设计和实现，一种最基础也是最常见的匹配系统实现方式如下：

游戏研发人员提取设置一些匹配规则，然后在在线匹配时，匹配系统从队列的最前面（一般是等待最久的玩家）开始进行检索，将玩家的属性与预设规则进行比较，如果一个玩家组合满足预设规则，他们将会被放入一场比赛当中。这些规则通常由游戏策划确定，并会以某种方式硬编码/通过特定算法按时间进行调整。但是这样的匹配系统通常只能保证每一场游戏中的玩家体验下限，而为了提高玩家体验的上限，我们还需要考虑很多因素：如玩家战斗峰哥的兼容性，位置偏好、玩家韧性等等。

那么我们应该如何在匹配系统当中加入这些因素的考量，使我们的匹配系统更加“周到”呢？我们首先可以想到的一个方式，就是在预设规则当中添加更多的限制。例如，我们可以添加一个规则来检查这场比赛是否会是一场公平的比赛，这可以通过预测每个阵营的获胜概率来实现。此外，我们可以添加另一个规则来检查它是否会是一场快乐的游戏，例如玩家在这场比赛中、比赛之后是否获得足够的玩家体验。

当然，玩家体验的建模可以隐式地考虑游戏的平衡性，但在这里我们明确地对游戏平衡性进行建模和限定接收范围，因为我们认为我们的玩法必须有一个明确的公平界限。

我们从一场比赛的多个阵营的获胜概率角度出发，对游戏匹配的平衡性进行评估。为了准确地评估两个或多个组的实力并预测每个组的获胜概率，我们尝试将获胜模式总结为四类。

首先是游戏能力，这可以看作是一个玩家对这款游戏的掌握程度的总结。通常系统会为每个玩家评估一个整体能力评分，用于定位他们在人群中的绝对实力。ELO、Glicko、TrueSkill等几种经典算法在游戏中被广泛使用。

二是英雄机制设计。在大多数游戏中，英雄被设计成具有不同的技能和属性，有些与其他英雄可以形成互相配合，这些配合英雄的组合有时会触发额外的能力。同时有些英雄被设计的非常强，但总有一个或几个英雄可以很好地抑制它。我们通过结算数据可以提取英雄之间的协同和克制关系图，然后通过Graph Embedding算法可以很好地学习代表这两种关系的英雄表征（KDD2020 Optmatch: Optimized matchmaking via modeling the high-order interactions on the arena）。

三是一个队伍中的英雄构成，这里指的是团队的组成方式，例如一个队伍中有多少战士/医生/弓箭手。在许多游戏中，医生通常对一个队伍很重要，但是对一个固定大小的团队来说，医生太多则挤占了其它输出职业的名额，又会削弱战斗力而导致失败。那么有多少医生和其他角色适合一个团队呢？

我们在这里使用SHAP模型可解释的方法进行分析，我们首先构建获胜预测模型，然后解释每个角色的重要性。这里的例子里我们有一个20v20的游戏，从SHAP值我们可以看出两队之间职业5的差异对获胜结果影响最大。而我们进一步看这个职业5的单特征数据，当发现双方职业5的人数差小于2时，影响并不大，而当人数差变大时，对游戏平衡性的影响就出现了。这启发了我们在匹配规则中添加一条规则，即两个阵营的职业5人数差不应超过 2。

这种方法可以非常有效地为不同游戏构建规则引擎。

最后一种是人际关系效果，即玩家之间的合作/对抗效果。类似地，玩家之间也有相互协调/不协调甚至克制的关系。我们在这里是通过设计如下的预测模型的结构来对这样的效果进行刻画的。

在通过算法预测对预设规则进行完善之后，匹配系统可以判断几个是否适合组成一场比赛，但很多情况下，一个玩家A可以同时满足与B、C进行比赛的条件，也可以满足与D、E进行比赛的条件，即可行的匹配结果有许多中，那么此时一个更优的匹配系统可以更好地最大化全体玩家的游戏体验总和。以下是一个匹配系统算法的对比示例，可以看到相比左边的先进先出（FCFS）匹配系统，右边的全局优化的匹配算法可以更好地输出让全体玩家更加满意的匹配方案。

在我们进一步讨论匹配系统的设计之前，我们先对匹配系统的优化目标进行定义。我们以如下公式对玩家在一场未来比赛中的体验进行量化的评估：

然后我们以所有匹配成功的玩家体验之和作为量化指标，对一个匹配算法进行评估。

在对匹配算法进行设计时，我们首先采用一些数学表达式来对匹配问题进行定义：

以一个两阵营玩法（记为campA和campB）的匹配为例，玩家匹配可以看作是一个指派问题。匹配模型对每个玩家 i 使用 x_ij 的决策变量，如果玩家 i 被分配到团队 j，则 x_ij 为 1，否则为 0。

我们将一种匹配结果表示为Ф_i，那么匹配算法的目标就是找到使玩家总体验最大化的匹配结果Ф。

那么如何找到这个最优匹配结果Ф呢？对于1v1竞技玩法，这个问题可以看作是在图中找到匹配（在图论中，无向图中的匹配，即独立边集是一组没有公共顶点的边）。

• 最大匹配（也称为最大基数匹配）是包含尽可能多的边的匹配，这可以用于目标为匹配尽可能多的玩家的匹配系统。
• 最大权重匹配问题是在加权图中找到权重总和最大化的匹配问题。 （最大基数匹配中的最大权重匹配），这可以用于构建最大化总效用的匹配系统。
• 完美匹配是匹配图的所有顶点的匹配，这可以看作是一种匹配每个人的匹配算法。

此外，还有有很多研究和方案可以从图中找到各种不同的匹配，我们可以通过采用它们轻松地构建一个最优化的匹配系统。

而对于多v多玩法，组合的情况随着N和队列中等待玩家数的增长呈指数增长：

那么此时我们可以考虑用一种启发式的算法，如先分房间再分队伍：

或者利用强化学习框架学习挑选模型，对玩家进行综合排序和按匹配顺序输出：

匹配服务的平台化建设

通常一个游戏中会涉及到多个匹配服务，而且各个接入我们匹配系统的游戏也希望能通过平台对匹配服务进行统一的运维和管理（以及资源利用的优化），因此我们采用微服务架构，模块功能解耦，搭建了通用的玩家匹配系统，提供适配多种玩法的、满足多优化目标情况下的最优玩家对阵组合策略，在兼顾游戏性、娱乐性的同时实现对战平衡。

一个匹配服务的流程为：

• 首先，玩家在游戏数据集中注册并存储他们的基本信息；当玩家点击按钮开始匹配时，他们的请求被发送到匹配服务平台的相关接口；
• 匹配服务器获取相应的数据并为那些等待的玩家分配组，匹配服务平台会将匹配结果推送给游戏服务器；
• 之后，游戏服务器根据匹配服务器的分配为排队的玩家开始比赛。
• 同事，匹配服务平台会持续收集游戏日志以增强玩家和竞技场的刻画准确度，用于更好地学习对战模式。

下图为匹配系统功能展示：匹配算法负责准确分析玩家的游戏能力，保证游戏质量，控制恶意游戏行为，并在必要时分配机器人玩家。此外，系统还提供综合分析和监控图表，供后期操作使用。

我们在此也提供了基于匹配SaaS创建一个新的匹配服务的预估开发时长，以及系统每个组件的设置、更新间隔、训练迭代、测试和部署阶段的信息。

以上就是本次分享的核心内容，我们也希望可以通过分享我们的实践经验，给更多的游戏研发厂商带来启发，为游戏玩家带来更好的体验。如果想要了解更多的伏羲产品，欢迎移步伏羲主页https://fuxi.163.com/。