如果讓人工智慧來打王者榮耀，應該選擇什麼樣的英雄？近日，匹茨堡大學和騰訊 AI Lab 提交的論文給了我們答案：狄仁傑。在該研究中，人們嘗試了 AlphaGo Zero 中出現的蒙特卡洛樹搜索（MCTS）等技術，並取得了不錯的效果。
對於研究者而言，遊戲是完美的 AI 訓練環境，教會人工智慧打各種電子遊戲一直是很多人努力的目標。在開發 AlphaGo 並在圍棋上戰勝人類頂尖選手之後，DeepMind 正與暴雪合作開展星際爭霸 2 的人工智慧研究。去年 8 月，OpenAI 的人工智慧也曾在 Dota 2 上用人工智慧打敗了職業玩家。那麼手機上流行的多人在線戰術競技遊戲（MOBA 遊戲）《王者榮耀》呢？騰訊 AI Lab 自去年起一直在向外界透露正在進行這樣的研究。最近，匹茨堡大學、騰訊 AI Lab 等機構提交到 ICML 2018 大會的一篇論文揭開了王者榮耀 AI 研究的面紗。
本文中，我們將通過論文簡要介紹該研究背後的技術，以及人工智慧在王者榮耀中目前的能力。
2006 年 Remi Coulom 首次介紹了蒙特卡洛樹搜索（MCTS），2012 年 Browne 等人在論文中對其進行了詳細介紹。近年來 MCTS 因其在遊戲 AI 領域的成功引起了廣泛關注，在 AlphaGo 出現時關注度到達頂峰（Silver et al., 2016）。假設給出初始狀態（或決策樹的根節點），那麼 MCTS 致力於迭代地構建與給定馬爾可夫決策過程（MDP）相關的決策樹，以便注意力被集中在狀態空間的「重要」區域。MCTS 背後的概念是如果給出大概的狀態或動作值估計，則只需要在具備高估計值的狀態和動作方向擴展決策樹。為此，MCTS 在樹到達一定深度時，利用子節點鑑別器（策略函數（Chaslot et al., 2006）rollout、價值函數評估（Campbell et al., 2002; Enzenberger, 2004），或二者的混合（Silver et al., 2016））的指引，生成對下遊值的估計。然後將來自子節點的信息反向傳播回樹。
MCTS 的性能嚴重依賴策略／值逼近結果的質量（Gelly & Silver, 2007），同時 MCTS 在圍棋領域的成功表明它改善了用於子節點鑑別的給定策略，事實上，這可以被看作是策略改進算子（Silver et al., 2017）。匹茨堡大學、騰訊 AI Lab 等機構的研究者們新發表的論文研究了一種基於反饋的新型框架，其中 MCTS 利用根節點生成的觀測結果更新其子節點鑑別器。
MCTS 通常被視為一種在線規劃器，決策樹以當前狀態作為根節點開始構建（Chaslot et al., 2006; 2008; Hingston & Masek, 2007; Matrepierre et al., 2008; Cazenave, 2009; Mehat & Cazenave, 2010; Gelly & Silver, 2011; Gelly et al., 2012; Silver et al., 2016）。MCTS 的標準目標是僅為根節點推薦動作。在採取動作之後，系統向前移動，然後從下一個狀態中創建一棵新的樹（舊樹的數據可能會部分保存或完全丟棄）。因此 MCTS 是一個「局部」的步驟（因為它僅返回給定狀態的動作），與構建「全局」策略的價值函數逼近或策略函數逼近方法存在本質區別。在實時決策應用中，構建足夠的「運行中」（on-the-fly）局部逼近比在決策的短期時間內使用預訓練全局策略更難。對於西洋棋或圍棋等遊戲而言，使用 MCTS 的在線規劃可能是合適的，但是在需要快速決策的遊戲中（如 Atari 或 MOBA 視頻遊戲），樹搜索方法就太慢了（Guo et al., 2014）。本論文提出的算法可以離策略的方式在強化學習訓練階段中使用。訓練完成後，與子節點鑑別有關聯的策略可以實現，以進行快速、實時的決策，而無需樹搜索。
主要貢獻
MCTS 的這些特性推動了研究者們提出一種新方法，在訓練步驟中利用 MCTS 的局部特性，來迭代地構建適應所有狀態的全局策略。思路是在原始 infinite-horizon MDP 的多批小型 finite-horizon 版本上應用 MCTS。大致如下：（1）初始化隨機價值函數和策略函數；（2）開始（可能是並行處理）處理一批 MCTS 實例（限制在搜索深度內，從採樣狀態集合中初始化而得），同時將價值函數和策略函數整合為子節點鑑別器；（3）使用最近的 MCTS 根節點觀測結果更新價值函數和策略函數；（4）從第（2）步開始重複步驟。該方法利用 MCTS 策略優於單獨的子節點鑑別器策略（Silver et al., 2016），同時改進子節點鑑別器也會改善 MCTS 的質量（Gelly & Silver, 2007）。
研究者稱，新論文的主要貢獻如下：
提出了一個基於批量 MCTS 的強化學習方法，其在連續狀態、有限動作 MDP 上運行，且利用了子節點鑑別器可以通過之前的樹搜索結果進行更新來生成更強大的樹搜索。函數逼近器用於追蹤策略和價值函數逼近，後者用於減少樹搜索 rollout 的長度（通常，策略的 rollout 變成了複雜環境中的計算瓶頸）。提供對該方法的完整樣本複雜度分析，表明足夠大的樣本規模和充分的樹搜索可以使估計策略的性能接近最優，除了一些不可避免的逼近誤差。根據作者的認知，基於批量 MCTS 的強化學習方法還沒有理論分析。基於反饋的樹搜索算法的深度神經網絡實現在近期流行的 MOBA 遊戲《王者榮耀》上進行了測試。結果表明 AI 智能體在 1v1 遊戲模式中很有競爭力。
圖 1. 基於反饋的樹搜索算法。
圖 2. 反饋循環圖示。
案例分析：《王者榮耀》MOBA 遊戲 AI
研究者在全新的、有挑戰性的環境：《王者榮耀》遊戲中實現了基於反饋的樹搜索算法。該實現是第一次為該遊戲 1v1 模式設計 AI 的嘗試。
遊戲介紹
在《王者榮耀》中，玩家被分為對立的兩隊，每一隊有一個基地，分別在遊戲地圖的相反角落（與其他 MOBA 遊戲類似，如英雄聯盟和 Dota 2）。每條線上有防禦塔來防禦，它可以攻擊在一定範圍內的敵人。每支隊伍的目標是推塔並最終摧毀對方的水晶。本論文僅考慮 1v1 模式，該模式中每個玩家控制一個「英雄」，還有一些稍微弱一點的遊戲控制的「小兵」。小兵負責守衛通往水晶的路，並自動攻擊範圍內的敵人（其攻擊力較弱）。圖 4 顯示了兩個英雄和他們的小兵，左上角是地圖，藍色和紅色標記表示塔和水晶。
圖 4.《王者榮耀》1v1 遊戲模式截圖。
實驗設置
系統的狀態變量是一個 41 維的向量，包含直接從遊戲引擎獲取的信息，包括英雄位置、英雄健康度（血量）、小兵健康度、英雄技能狀態和不同結構的相對位置。有 22 個動作，包括移動、攻擊、治療術（heal）和特殊的技能動作，包括（扇形）非指向技能。獎勵函數的目標是模仿獎勵形態（reward shaping），使用信號組合（包括健康、技能、傷害和靠近水晶的程度）。研究者訓練了五個《王者榮耀》智能體，使用的英雄是狄仁傑：
FBTS 智能體使用基於反饋的樹搜索算法進行訓練，一共迭代 7 次，每次進行 50 局遊戲。搜索深度 d = 7，rollout 長度 h = 5。每次調用 MCTS 運行 400 次迭代。第二個智能體因為沒有 rollout 被標註為「NR」。它使用和 FBTS 智能體相同的參數，除了未使用 rollout。總體來看，它在批量設置上與 AlphaGo Zero 算法有些相似。DPI 智能體使用 Lazaric et al., 2016 的直接策略迭代技術，進行 K = 10 次迭代。沒有價值函數和樹搜索（因為計算限制，不使用樹搜索就可能進行更多次迭代）。AVI 智能體實現近似價值迭代（De Farias & Van Roy, 2000; Van Roy, 2006; Munos, 2007; Munos & Szepesvari , 2008），K = 10 次迭代。該算法可被認為是 DQN 的批量版本。最後是 SL 智能體，它通過在大約 100,000 個人類玩遊戲數據的狀態／動作對數據集上進行監督學習來訓練。值得注意的是，此處使用的策略架構與之前的智能體一致。
事實上，策略和價值函數近似在所有智能體中都是一樣的，二者分別使用具備五個和兩個隱藏層的全連接神經網絡和 SELU（scaled exponential linear unit）激活函數（Klambauer et al., 2017）。初始策略 π0 採取隨機動作：移動（w.p. 0.5）、直接攻擊（w.p. 0.2）或特殊技能（w.p. 0.3）。除了將移動方向挪向獎勵方向之外，π0 不使用其他啟發式信息。MCTS 是 UCT 算法的變體，更適合處理並行模擬：研究者不使用 UCB 分數的 argmax，而是根據對 UCB 得分應用 softmax 函數所獲得的分布進行動作採樣。
與理論不同，在算法的實際實現中，回歸使用 cosine proximity loss，而分類使用負對數似然損失。由於在該遊戲環境中我們無法「倒帶」或「快進」至任意狀態，因此採樣分布 ρ0 由第一次採取的隨機動作（隨機的步數）來實現併到達初始狀態，然後遵循策略 πk 直到遊戲結束。為了減少價值逼近中的相關性，研究者丟棄了在這些軌跡中遇到的 2/3 的狀態。對於 ρ1，研究者遵循 MCTS 策略，偶爾帶入噪聲（以隨機動作和隨機轉向默認策略的方式）來減少相關性。在 rollout 中，研究者使用遊戲內部 AI 作為英雄狄仁傑的對手。
結果
由於該遊戲幾乎是確定性的，因此研究者的主要測試方法是對比智能體對抗內部 AI 對手的有效性。研究者還添加了遊戲內建 AI 的狄仁傑作為「完整性檢查」基線智能體。為了選擇測試對手，研究者使用內建 AI 狄仁傑對抗其他內建 AI（即其他英雄）並選擇六個內建 AI 狄仁傑能夠打敗的射手類英雄。研究者的智能體每一個都包含內建狄仁傑 AI，使用智能體對抗測試對手。圖 5 顯示了每個智能體打敗測試對手的時間長度（單位為幀）（如果對手贏了，則顯示為 20,000 幀）。在與這些共同對手的戰鬥中，FBTS 顯著優於 DPI、AVI、SL 和遊戲內建 AI。但是，FBTS 僅稍微超出 NR 的表現（這並不令人驚訝，因為 NR 是另外一個也使用 MCTS 的智能體）。研究者的第二組結果幫助可視化了 FBTS 和四個基線的對決（全部都是 FBTS 獲勝）：圖 6 顯示了 FBTS 智能體及其對手的金幣比例，橫軸為時間。王者榮耀遊戲中英雄對敵人造成傷害或者戰勝敵人時，都會得到金幣，因此金幣比例大於 1.0（高出紅色區域）表示 FBTS 的良好性能。如圖所示，每個遊戲結束時 FBTS 的金幣比例都在 [1.25, 1.75] 區間內。
圖 5. 幾種智能體戰勝其他射手英雄所用時間（以幀為單位，即幀的數量），數字越小越好。其中 FBTS 為新研究提出的智能體。
圖 6. 遊戲內行為。
論文：Feedback-Based Tree Search for Reinforcement Learning
摘要：蒙特卡洛樹搜索（MCTS）已在多個人工智慧領域取得了成功，受此啟發我們提出了一種基於模型的強化學習技術，可以在原始 infinite-horizon 馬爾可夫決策過程的多批小型 finite-horizon 版本上迭代使用 MCTS。我們使用估計值函數和估計策略函數指定 finite-horizon 問題的終止條件或 MCTS 所生成決策樹的子節點鑑別器。MCTS 步驟生成的推薦結果作為反饋，通過分類和回歸來為下一次迭代細化子節點鑑別器。我們為基於樹搜索的強化學習算法提供第一個樣本複雜度界限。此外，我們還證明該技術的深度神經網絡實現可以創建一個適合《王者榮耀》遊戲的有競爭力的 AI 智能體。