如何才能讓玩家匹配更“周到”？
帶不動隊友、仙人局、被虐到懷疑人生、心儀位置被搶、隊友不合作甚至掛機、職業組合不平衡……糟糕的體驗往往讓新手難以上手，老手憤而棄坑。因為體驗差導致玩家流失，對遊戲的口碑和長久發展造成了難以估量的負面影響。
玩家匹配演算法對玩家遊戲體驗一直至關重要，如何透過AI演算法高效地構建一個能有效兼顧平衡性和娛樂性、保障玩家遊戲體驗的匹配系統一直是遊戲演算法團隊的重點研發課題。在 GDC 2021 核心會議中，伏羲的匹配團隊圍繞“應用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和遊戲相關國際頂會上有多篇發表，本次將代表伏羲匹配團隊介紹匹配演算法研究和應用成果。
遊戲葡萄招聘產業記者/內容編輯，
點選「閱讀原文」可瞭解詳情
上海人才戰｜成都人才戰｜白夜極光
摩爾莊園發行｜二次元美術內卷｜防沉迷困局
二次元抽卡｜中國做不出賽馬娘｜自研困局