機器之心報導
編輯：Panda
搶射手？搶中單位？「絕悟」在打王者榮耀時是如何選英雄的？
騰訊 AI Lab 開發的 AI 智能體「絕悟」已讓王者峽谷不再只是人類召喚師的競技場，而且這個 AI 戰隊在上月底進化成了「完全體」。在一局完整的比賽中，英雄選擇階段是至關重要的（比如五射手或五法師陣容會有官方勸退）。
近日，騰訊 AI Lab 和上海交通大學發布的一篇論文介紹了絕悟的英雄選擇策略：JueWuDraft。別的不敢說，有一點可以肯定：人工智慧不會亂搶英雄。
玩 MOBA 遊戲，選英雄很關鍵，因為這決定了雙方隊伍的陣容，會直接影響戰績、勝負等最終結果。之前最佳的選英雄方法通常沒有考慮以下因素：1）英雄池擴大時選英雄的效率，2）MOBA 遊戲 5v5 的多輪競賽機制，即兩支隊伍比賽 N 局，獲勝次數更多的隊伍獲勝（best-of-N），而在這一系列比賽中，每個英雄只能被選擇一次。
騰訊 AI Lab 和上海交通大學合作的這篇論文將陣容選擇過程描述成了一個多輪組合博弈過程，並提出了一種全新的陣容選擇算法 JueWuDraft，該算法基於神經網絡和蒙特卡洛樹搜索。具體來說，作者設計了一種長期的價值估計機制，可以更好地應對 best-of-N 比賽的選英雄情況。研究者在大熱 MOBA 手遊《王者榮耀》中檢驗了該方法，結果表明：相較於其它當前前沿的方法，JueWuDraft 的實用性和有效性都更勝一籌。
「選英雄」的重要性
自 AlphaGo 和 AlphaZero 在棋盤類遊戲上擊敗了人類職業玩家以來，遊戲人工智慧（Game AI）一直備受關注。另外，我們也見證了 AI 智能體在其它遊戲類型上的成功，包括 Atari 系列遊戲和奪旗遊戲等第一人稱射擊遊戲（FPS）、《任天堂明星大亂鬥》等視頻遊戲、撲克等紙牌遊戲。儘管如此，相比於複雜的實時策略遊戲（RTS），這些遊戲要簡單得多，因為 RTS 遊戲更能體現真實世界的本質。因此，近來的研究者更加關注 RTS 遊戲，比如《Dota 2》、《星際爭霸》和《王者榮耀》。
RTS 遊戲有一個子類別是多人在線戰術競技遊戲（MOBA），這是當今最受歡迎的一類電子競技遊戲。MOBA 遊戲的遊戲機制涉及到多智能體競爭和協作、不完美信息、複雜動作控制、巨大的狀態 - 動作空間。也因此，MOBA 遊戲被視為 AI 研究的首選測試平臺。MOBA 的標準遊戲模式是 5v5，即兩支各包含 5 位玩家的隊伍互相對抗。最終目標是摧毀對方隊伍的基地 / 水晶 / 堡壘。每位玩家都會控制單個遊戲角色，通常稱為「英雄」，並與其他隊友協作攻擊對方的英雄、小兵、炮塔和中立生物，同時保護己方的單位。
一局 MOBA 遊戲通常包含兩個階段：1）匹配階段，在此期間，兩支隊伍的 10 位玩家從英雄池挑選英雄，這個過程也被稱為「英雄選擇」或「選英雄」；2）比賽階段，兩支隊伍開始戰鬥，直至遊戲結束。下圖是《王者榮耀》英雄陣容選擇階段的遊戲截圖。在挑選英雄時，兩支隊伍會輪流選擇，直到每位玩家都各自選擇一個英雄。最終選出的英雄陣容會直接影響之後的遊戲策略和最終比賽結果。因此，為了構建能完整地玩 MOBA 遊戲的 AI 系統，選英雄階段非常重要而且也是必需的。
圖 1：《王者榮耀》選英雄界面截圖
為了確定兩支隊伍的勝敗，常用的評估規則是 best-of-N，其中 N 可為奇數 1、3、5，意思是執行 N 局比賽，直到某個隊伍贏得 (N+1)/2 局，比如三局兩勝或五局三勝。
在 MOBA 遊戲中，每個英雄都有獨特的技能和能力。每支隊伍 5 個英雄的技能和能力綜合起來即為該團隊的整體實力。另外，英雄彼此之間還存在複雜的壓制和互補關係。舉個例子，在《Dota 2》中，敵法師的技能能削減敵方英雄的魔法值，因此它「天克」美杜莎，因為美杜莎的持續作戰能力嚴重依賴魔法量。再舉另一個例子，在《王者榮耀》中，明世隱能提升所有己方英雄的普攻傷害，使其為射手英雄后羿提供強力輔助。因此，為了贏得比賽，玩家選英雄時需要謹慎考慮如何增強隊友英雄的能力或補充其弱點，以及如何克制對方英雄。
在《王者榮耀》和《Dota 2》等 MOBA 遊戲中，選英雄階段可選英雄的數量可能超過 100 個。比如，最新版的《王者榮耀》已有 102 個英雄。因此，可能的英雄陣容數量可達 5.37×10^（），即從包含 102 個英雄的英雄池中選出 10 個英雄，然後從這 10 個中選出 5 個）。由於英雄之間存在複雜的關係，陣容也有非常多的可能性，選擇配合隊友和克制敵方的英雄對人類玩家來說也頗具挑戰性。
在 MOBA 英雄選擇方面，當前最佳方法來自 OpenAI Five 和 DraftArtist。OpenAI Five 是一個玩《Dota 2》的 AI 程序，它使用 Minimax 算法來選擇英雄，因為它僅支持 17 個英雄。但是，Minimax 會構建一個完整的搜索樹，這個搜索樹由每位玩家交替的可能選擇構成，這使其在計算上難以擴展用於大型英雄池，比如 100 個英雄。DraftArtist 使用了蒙特卡洛樹搜索（MCTS），即通過模擬陣容完成前可能的後續選取過程來估計每次選取的價值。但是，它只考慮單次競賽，即 best-of-1（一局定勝負），這可能導致陣容選擇結果不是最優。此外，MCTS 模擬採用隨機 roll-out（推演）來獲得獎勵，這種方法的效率很低。
騰訊 AI Lab 和上海交通大學的這篇論文將 MOBA 遊戲選英雄的過程描述成了一個雙玩家使用完美信息的零和博弈問題。每個玩家的目標都是最大化己方隊伍相對於敵方隊伍的勝率（敵我隊伍各有五個英雄）；另一個條件是英雄池中每個英雄都只能被同一個隊伍選擇一次。
為了解決這個問題，該論文提出了組合使用蒙特卡洛樹搜索（MCTS）和神經網絡的方法。具體來說是將 MCTS 與策略和價值網絡組合起來，其中價值網絡的作用是直接預測當前狀態的價值來獲得獎勵，而不是執行效率低下的隨機 roll-out。在西洋棋和圍棋等棋盤遊戲中，競賽的勝者由最終的狀態決定，而選英雄過程卻不一樣，其終點並非一局 MOBA 比賽的終點。因此，我們不能直接獲取比賽結果。為了解決這個問題，作者構建了一個神經預測器，用以預測特定陣容的勝率。這個最終狀態的勝率可用作預測 MCTS 的反向傳播和訓練價值網絡的獎勵。
此外，根據 best-of-N 規則，為當前一局比賽選擇的英雄會影響後續幾局的選擇。針對這個特點，作者提出將選英雄過程描述為一個多輪組合博弈過程，並設計了一套長期價值機制。這樣得到的選英雄策略能更長遠地考慮當前對局和後續對局。
總體而言，該研究的貢獻如下：
為 MOAB 遊戲提出了一種名為 JueWuDraft 的選英雄方法，該方法利用了神經網絡和蒙特卡洛樹搜索。具體來說是將 MCTS 與策略和價值網絡組合到了一起，其中價值網絡是用於評估當前狀態的價值，策略網絡則是為下個英雄選擇執行動作採樣。
將 best-of-N 選英雄問題描述成了一個多輪組合博弈問題，其中每一局遊戲都有一個對最終陣容的預測勝率。為了適應這樣的 best-of-N 選英雄問題，作者設計了一套長期價值機制。這使得對當前狀態的價值估計會考慮到後續對局。
作者在單局和多局遊戲上執行廣泛的實驗驗證，結果表明：相較於其它當前最佳方法，JueWuDraft 能取得更優的表現。
相關工作
在 MOBA 遊戲選英雄問題上，之前的方法主要分為以下四類：
1. 根據該遊戲過去的英雄出場率進行選擇
2. 根據該遊戲之前的英雄勝率進行選擇
3. Minimax 算法
4. 蒙特卡洛樹搜索
絕悟用這個方法選英雄
問題描述
如前所述，在 MOBA 遊戲中，選英雄過程是非常重要的，尤其是在複雜的遊戲比賽中。在正式的 MOBA 比賽中，在確定獲勝者方面，常用的策略是 best-of-N 多局格式，其中 N 是一個奇數，通常是 best-of-3 或 best-of-5，即三局兩勝制或五局三勝制。舉個例子，王者榮耀職業聯賽（KPL）的比賽形式總是包含多局比賽。其中兩支戰隊會進行多局比賽，直到某支戰隊贏得其中 (N+1)/2 局比賽。此外，在多局比賽中，KPL 不允許玩家選擇己方戰隊之前幾局已經選擇過的英雄。這意味著，為了贏得多局比賽的最終勝利，在選擇英雄時，既要考慮當前一局比賽，還需要考慮後續幾局比賽。
基於這些考慮，除了單獨考慮每一局的英雄選擇，這篇論文還將全場比賽 G 定義成了一個雙玩家零和完美信息博弈問題，其中具有重複的子結構。一場比賽考慮的元素包括玩家數、選擇順序、遊戲狀態等，詳情請見原論文。另需說明該論文未考慮英雄禁選的情況。
使用神經網絡和樹搜索學習在 MOBA 遊戲中選英雄
整體訓練框架圖 2 展示了 JueWuDraft 的整體訓練框架。為了提升訓練效率，作者將該框架分散到了多個 CPU 和 GPU 伺服器上進行處理。整體而言，該框架包含 4 個模塊：數據採樣器、樣本池、神經網絡訓練器和模型池。
圖 2：整體訓練框架
搭配深度神經網絡的並行 MCTS：該框架使用的搜索算法是多項式置信度上限樹。為了提升數據採用的速度和充分利用計算資源，對樹的搜索是並行執行的。總體而言，PUCT 搜索樹是按四個步驟迭代式構建的：選擇、評估、擴展和反向傳播。圖 3 展示了該過程。
圖 3：用於英雄選擇過程的 MCTS 每次模擬都分四步：選擇、評估、擴展和向後傳播。搜索完成後，返回概率 π（其正比於對每個節點的訪問次數 C(s)）。
策略和價值網絡的訓練深度神經網絡在評估未曾見過的狀態的價值方面具有很強的泛化能力，因此也是 JueWuDraft 的重要組成部分，它既可以提供當前價值的穩定參考，也能提供主要動作。另外，這個神經網絡還能節省搜索和構建樹的時間；相對而言，傳統 MCTS 算法會採樣到遊戲結束，因此會在 rollout 上花很多時間。因此，訓練網絡的方式很關鍵。這篇論文提出的網絡能在單一框架內輸出價值和預言（oracle）策略。
長期價值傳播正如前面介紹的，在多局比賽中，早期比賽對局的每次英雄選擇都會影響後期對局的選擇。另外，將所有相關對局的結果匯總起來預測當前步驟的價值也是很直觀的做法。長期價值傳播的情況有兩種：
MCTS 中的反向傳播步驟價值網絡的目標（target）標籤圖 4 展示了一場三對局比賽的示例，其中說明了價值網絡中上述兩種價值傳播方式。
圖 4：價值傳播
網絡結構和狀態重構：為了以更高效的方式訓練策略和價值網絡，需要對狀態進行重構。如圖 5 所示，重構的狀態向量主要包含三部分。一是當前英雄選擇部分，即當前局的英雄選擇，這對當前局的勝率有主要影響。該向量的中間部分是歷史的英雄選擇信息。最後一部分是關係信息（比如當前對局由哪方先選）。
圖 5：狀態向量的配置
如圖 6(b) 所示，策略和價值網絡使用了一個簡單的 3 層全連接神經網絡。其以圖 5 所示的狀態向量為輸入，輸出則是兩個頭（head）：一個帶 softmax 函數的全連接層（策略頭，其輸出每個動作的概率）；一個帶 tanh 函數的全連接層（價值頭，輸出當前狀態的價值）。
圖 6：網絡架構：(a) 是勝率預測器，(b) 是策略和價值網絡
勝率預測器
在選擇英雄階段，只能得到陣容信息，勝負信息是未知的。作者採用了勝率預測器來預測陣容的勝率並將其作為獎勵函數。
訓練這個勝率預測器所使用的比賽數據集包含陣容和勝負信息。每個英雄都各有一個範圍在 [0, N_classes1] 之間的索引。輸入特徵由全部 10 個已選擇英雄的索引表示。
圖 6(a) 給出了勝率預測器的網絡架構，這是一個簡單的 3 層神經網絡，其輸出層連接著一個 sigmoid 激活函數。
實驗
在實驗中，JueWuDraft 總體而言優於其它策略，該算法的有效性和高效性也得到了體現。
具體來說，JueWuDraft 與這三種策略進行了比較：
DraftArtist，使用了單純的 MCTS，沒有策略和價值網絡。該策略不會考慮後續對局的情況。最高勝率（HWR）策略，基於統計數據選擇剩餘英雄池中勝率最高的英雄。隨機策略（RD），在剩餘英雄池中隨機挑選一個英雄。
表 1：在 AI 數據集的單局比賽中（各行玩家對抗各列玩家），每一對策略中各行玩家的預測勝率。
表 4：在人類數據集的單局比賽中，每一對策略中各行玩家的預測勝率。
下面說明一個具體的模擬案例，其中上場玩家是 JueWuDraft 與 HWR，如圖 10 所示。JueWuDraft 在三局比賽中的預測勝率分別為 56.3%、71.8%、65.1%。其中第二局和第三局中 JueWuDraft 的勝率比第一局更高。具體來說，在第一局中，JueWuDraft 先手選擇了成吉思汗而不是平均勝率最高的劉備，儘管首先選擇劉備可能會在第一局得到更高的勝率。這說明 JueWuDraft 的貪心策略沒有 HWR 那麼高，而是會長線考慮，兼顧後面的對局。
圖 10：JueWuDraft 對抗 HWR 的一次具體模擬結果，其中 JueWuDraft 先手選擇。
研究局限和展望未來
該研究還存在兩方面的局限，有待進一步探索和延伸。
第一，該研究還沒考慮英雄禁選過程，這也非常重要，通常與選英雄過程合稱「Ban/Pick」。第二，訓練數據集是從強化學習訓練比賽或人類比賽收集的，儘管這套 AI 系統的目標是擊敗人類玩家，但訓練出的智能體與人類玩家的勝率差距還很明顯。而這裡設計的勝率預測器還沒有充分考慮這一差距。研究者希望能在這兩方面為 JueWuDraft 帶來進一步突破。
論文連結：https://arxiv.org/abs/2012.10171