带不动队友、神仙局、被虐到疑惑人生、心仪位置被抢、队友不合作甚至挂机、职业组合不平衡……糟糕的体验每每让新手难以上手，老手愤而弃坑。由于体验差导致玩家流失落，对游戏的口碑和长久发展造成了无法计算的负面影响。
玩家匹配算法对玩家游戏体验一贯至关主要，如何通过AI算法高效地构建一个能有效兼顾平衡性和娱乐性、保障玩家游戏体验的匹配系统一贯是游戏算法团队的重点研发课题。在GDC2021 核心会议中，伏羲的匹配团队环绕“运用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创建一个新的匹配做事的预估开拓时长，以及系统每个组件的设置、更新间隔、演习迭代、测试和支配阶段的信息。
主讲人：巩琳霞（Linxia），2017年加入网易伏羲，紧张卖力用户建模干系研究和运用落地事情，紧张研发方向有玩家匹配、外挂检测、用户留存，在KDD、CIKM、GDC等AI和游戏干系国际顶会上有多篇揭橥，本次将代表伏羲匹配团队先容匹配算法研究和运用成果。
游戏葡萄招聘家当/内容编辑，
点击「阅读原文」可理解详情