從FPS到RTS，一文概述游戲人工智能中的深度學習算法
本文綜述了用于打電子游戲的深度學習算法，分析了不同類型的電子游戲對深度學習系統的要求，同時也列舉了一些開放性挑戰。
論文鏈接：https://arxiv.org/pdf/1708.07902.pdf
摘要：在本論文中，我們綜述了近期深度學習在不同類型的電子游戲中的應用進展，如第一人稱射擊游戲(FPS)、街機游戲或即時戰略游戲(RTS)。我們分析了不同的游戲對深度學習系統的獨特要求，以及將這些機器學習方法應用到電子游戲中的重要開放性挑戰，如在通用游戲中，如何處理大型決策空間和稀疏獎勵。
1. 引言
本文中，我們關注基于深度學習的游戲 AI 中廣泛存在的問題以及使用的環境，如 Atari/ALE、《毀滅戰士》(Doom)、《我的世界》(Minecraft)、《星際爭霸》(StarCraft)和賽車游戲。另外，我們綜述了現有的研究，指出亟待解決的重要挑戰。我們對能夠玩好電子游戲(非棋類游戲，如圍棋等)的方法很感興趣。本文分析了多種游戲，指出這些游戲給人類和機器玩家帶來的挑戰。必須說明，本文并未涉及所有 AI 在游戲中的應用，而是專注于深度學習方法在電子游戲中的應用。深度學習并非唯一應用于游戲中的 AI 方法，其他有效方法還有蒙特卡洛樹搜索 [12] 和進化計算 [85], [66]。
2. 深度學習概述
本節我們概述了應用于電子游戲中的深度學習方法，及多種方法結合起來的混合方法。
A. 監督學習
在人工神經網絡(ANN)的監督訓練中，智能體通過樣本進行學習 [56], [86]。智能體需要做出決策(已知正確答案)，之后，使用誤差函數確定智能體提供的答案和真正答案之間的區別;這將作為損失用于更新模型。在大數據集上進行訓練后，智能體應該學習通用模型，使之在未見過的輸入上依然表現良好。
這些神經網絡的架構大致可分為兩個主要范疇：前饋網絡和循環神經網絡(RNN)。
B. 無監督學習
無監督學習的目標不是學習數據和標簽之間的映射，而是在數據中發現模式。這些算法可以學習數據集的特征分布，用于集中相似的數據、將數據壓縮成必要特征，或者創建具備原始數據特征的新的合成數據。
深度學習中有多種不同的技術允許使用無監督學習。其中最重要的是自編碼器技術，這種神經網絡嘗試輸出自我輸入的復制版本。
C. 強化學習方法
在用于游戲的強化學習中，智能體通過與環境互動來學習打游戲。其目標在于學習策略，即每一步需要用什么操作才能達到想要的狀態。這種情況通常出現在電子游戲中，玩家每一步可以采取的操作數量有限，動作的順序決定玩家玩的如何。
D. 進化方法
另一個訓練神經網絡的方法基于進化算法。該方法通常指神經進化(neuroevolution，NE)，可以優化網絡權重和拓撲。與基于梯度下降的訓練方法相比，NE 方法的優勢在于不要求網絡可微分，且可用于監督學習和強化學習問題。
E. 混合方法
近期，研究者開始研究適用于玩電子游戲的混合方法，即將深度學習方法和其他機器學習方法結合起來。
這些混合方法旨在結合兩種方法的優點：深度學習方法能夠直接從高維原始像素值中學習，進化方法不需要依賴可微分架構，且在稀疏獎勵的游戲中表現良好。
在棋類游戲中有重大意義的混合方法是 AlphaGo [97]，該方法依賴深度神經網絡和樹搜索方法，打敗了圍棋領域的世界冠軍。
3. 游戲類型和研究平臺
本節概述流行的游戲類型和研究平臺(與深度學習相關)。我們簡略地概述了這些游戲的特點和算法在玩游戲時遇到的挑戰。
A. 街機游戲
經典的街機游戲是上世紀 70 年代晚期 80 年代早期流行的游戲類型，在過去十年中這種游戲常常作為 AI 的測試基準。
街機游戲的代表性平臺是 Atari 2600、Nintendo NES、Commodore 64 和 ZX Spectrum。大多數經典街機游戲的特點是在二維空間中的移動、圖文邏輯(graphical logic)的大量使用、連續時間進度(continuous-time progression)，以及連續空間或離散空間移動。這類游戲的挑戰因游戲而異，不過大部分此類游戲都需要快速反應和抓住時機。很多游戲需要優先處理多個同時發生的事件，這要求預測游戲中其他實體的行為或軌跡。另一個普遍要求是穿過迷宮或其他復雜環境，比如吃豆人(Pac-Man，1980 年出現的游戲)和鉆石小子(Boulder Dash，1984 年出現的游戲)。
最著名的用于深度學習方法的游戲平臺是街機模式學習環境(Arcade Learning Environment，ALE)[6]。ALE 由 Atari 2600 模擬機 Stella 打造，包含 50 個 Atari 2600 游戲。該框架抽取游戲得分、160×210 的屏幕像素和可用于游戲智能體的輸入的 RAM 內容。該平臺是第一批深度強化學習論文(使用原始像素作為輸入)探索的主要環境。
另一個經典的街機游戲平臺是 Retro Learning Environment(RLE)，目前該平臺包含 7 個發布到超級任天堂(SNES)的游戲 [9]。這些游戲中很多都有 3D 圖畫，控制器允許超過 720 種組合操作，這使得 SNES 游戲比 Atari 2600 游戲更加復雜和生動，但這個環境目前沒有 ALE 那么流行。
圖 1. 作為深度學習研究平臺的幾款游戲的截圖。
B. 競速游戲
競速游戲中，玩家控制某種車或某個人物在最短的時間內到達目的地，或者在給定時間內沿軌道行駛最遠的距離。通常情況下，該游戲使用第一人稱視角或玩家控制車輛的后方有利的位置作為視角。
競速游戲中的一個普遍挑戰是智能體需要利用微調后的持續輸入來控制車輛的位置，調整加速或剎車，以盡快走完軌道。這至少需要短期規劃、一次或兩次轉彎。如果游戲中還需要管理其他資源，如能源、破壞或提速，則還需要長期規劃。如果軌道上出現其他車輛，還需要加入對抗規劃，以管理或阻止超車。
帶 3D 圖像的視覺強化學習經常使用的環境是開源賽車模擬器 TORCS [121]。
C. 第一人稱射擊游戲(FPS)
近期，第一人稱射擊游戲(FPS)設置成為適合視覺強化學習智能體的先進游戲環境。與 ALE 基準中的經典街機游戲相比，FPS 具備 3D 圖像，狀態部分可觀測，因此是更加生動的研究環境。通常的游戲視角是玩家控制的人物的視角，但 FPS 范疇內的多款游戲采用了過肩視角。這種設計造成的挑戰是快速感知和快速反應，尤其是看到敵人并快速瞄準時。但是也存在其他認知挑戰，包括在復雜的三維環境中定向和移動，預測多個敵人的動作和位置;某些游戲模式還需要團隊合作。如果游戲中使用了視覺輸入，那么從像素中抽取相關信息也是一個挑戰。
ViZDoom 是一個 FPS 平臺，該框架允許智能體使用屏幕緩沖作為輸入來玩經典的第一人稱射擊游戲 Doom[50]。DeepMind Lab 是一個基于《雷神之錘》(Quake III)Arena 引擎的三維導航和解謎任務平臺 [2]。
D. 開放世界游戲
開放世界游戲，如 Minecraft、Grand Theft Auto V，這類游戲的特點是非線性，有一個很大的游戲世界供玩家探索，沒有既定目標或清晰的內在次序，玩家在既定時間內有很大的操作自由。智能體的關鍵挑戰是探索游戲世界，設定真實、有意義的目標。鑒于這是一項非常復雜的挑戰，大部分研究使用這些開放環境探索強化學習方法，這些方法可以重用和遷移學得的知識到新的任務中。Project Malmo 是一個根據開放世界游戲 Minecraft 構建的平臺，可用于定義多種復雜問題 [43]。
E. 即時戰略游戲
這類游戲中玩家控制多個人物或單元，游戲目標是在競賽或戰爭中獲勝。即時戰略游戲的關鍵挑戰是制定和執行涉及多個單元的復雜計劃。這個挑戰通常比經典棋類游戲如象棋中的規劃挑戰更難，因為多個單元會隨時移動，有效的分支因子通常非常大。另外一個挑戰是預測一個或多個敵人的移動，敵人本身就有多個單元。即時戰略游戲(RTS)在戰略游戲本就很多的挑戰之上又增加了時間優先次序(time prioritization)的挑戰。
星際爭霸游戲系列無疑是即時戰略游戲中研究最多的游戲。《星際爭霸·母巢之戰》的 API(BWAPI)使軟件可以在游戲運行中與星際爭霸交流，如抽取狀態特征、執行操作。BWAPI 曾廣泛應用于游戲 AI 研究，但是目前只有少數使用了深度學習。近期根據 BWAPI 構建的庫 TorchCraft 將科學計算框架 Torch 和 StarCraft 聯系起來，使用機器學習方法研究該游戲 [106]。DeepMind 和暴雪(星際爭霸的開發者)已經開發了機器學習 API，以支持機器學習在星際爭霸 2 中的研究 [114]。該 API 包含多個小挑戰，盡管它支持 1v1 游戲設置。有兩個抽象出來的 RTS 游戲引擎值得一提：RTS [77] 和 ELF [109]，后者實現了 RTS 游戲中的多個特征。
F. OpenAI Gym & Universe
OpenAI Gym 是一個對比強化學習算法和單獨接口的大型平臺，該接口包含一系列不同的環境，包括 ALE、MuJoCo、Malmo、ViZ-Doom 等等 [11]。OpenAI Universe 是 OpenAI Gym 的擴展，目前可以接入一千多個 Flash 游戲，并且計劃接入更多現代電子游戲。
4. 玩游戲的深度學習方法
A. 街機游戲
街機模式學習環境(ALE)已經成為深度強化學習算法直接從原始像素中學習控制策略的主要試驗平臺。本節概述 ALE 中的主要進展。
深度 Q 網絡(DQN)是第一個在 Atari 游戲中展示人類專業玩家控制水平的學習算法 [70]。該算法在七種 Atari 2600 游戲中進行測試，表現優于之前的方法，如具備特征構建 [3] 和神經卷積 [34] 的 Sarsa 算法，并在三種游戲上表現優于人類專業水平。
深度循環 Q 學習(DRQN)在輸出前使用循環層擴展 DQN 架構，這對狀態部分可觀測的游戲效果很好。
Q 學習算法存在一個問題，即它通常高估動作值。基于雙 Q 學習 [31] 的雙 DQN 通過學習兩個價值網絡降低觀測到的過高估計值，兩個價值網絡在更新時互為目標網絡 [113]。
Dueling DQN 使用的網絡在卷積層后可以分成兩個流，分別估計狀態值 V π (s) 和動作優勢(action-advantage)Aπ (s, a)，使 Qπ (s, a) = V π (s) + Aπ (s, a) [116]。Dueling DQN 優于雙 DQN，且能夠連接優先經驗回放。
本節還描述了 Advantage Actor-Critic (A3C) 算法、使用漸進神經網絡的 A3C 算法 [88]、非監督強化和輔助學習(UNsupervised REinforcement and Auxiliary Learning，UNREAL)算法、進化策略(Evolution Strategies，ES)等算法。
B. Montezuma's Revenge(略)
C. 競速游戲
Chen et al 認為基于視覺的自動駕駛通常存在兩種范式 [15]：(1)直接學習將圖像映射到動作的端到端系統(行為反射);(2)分析傳感器數據，制定明智決策的系統(介導感知)。
策略梯度方法，如 actor-critic [17] 和確定性策略梯度(Deterministic Policy Gradient，DPG)[98]，可以在高維、持續的動作空間中學習策略。深度確定性策略梯度是一種實現回放記憶和獨立目標網絡的策略梯度方法，二者都極大提升了 DQN。深度確定性策略梯度方法曾用于利用圖像訓練 TORCS 的端到端 CNN 網絡 [64]。
前面提到的 A3C 方法也被應用于競速游戲 TORCS，僅使用像素作為輸入 [69]。
D. 第一人稱射擊游戲
使用同步定位與地圖構建(Simultaneous Localization and Mapping，SLAM)從屏幕和深度緩沖區獲取位置推斷和物體映射，這二者也能改善 DQN 在《毀滅戰士》游戲中的效果 [8]。
死亡競賽的冠軍使用了直接未來預測(Direct Future Prediction，DFP)方法，該方法的效果優于 DQN 和 A3C [18]。DFP 使用的架構有三個流：一個用于屏幕像素，一個用于描述智能體當前狀態的低維評估，一個用于描述智能體的目標，即優先評估的線性結合。
3D 環境中的導航是 FPS 游戲所需的一個重要技巧，并且已經被廣泛研究。CNN+LSTM 網絡使用 A3C 訓練，A3C 用預測像素深度和環閉合的額外輸出擴展而成，顯示出顯著改善 [68]。
內在好奇心單元(Intrinsic Curiosity Module，ICM)包括多個神經網絡，在每個時間步內基于智能體無法預測動作結果來計算內在獎勵。
E. 開放世界游戲
分層深度強化學習網絡(Hierarchical Deep Reinforcement Learning Network，H-DRLN)架構實現終身學習框架，該框架能夠在游戲《我的世界》的簡單任務中遷移知識，比如導航、道具收集和布局任務 [108]。H-DRLN 使用一個變種策略振蕩 [87] 來保留學得的知識，并將其封裝進整個網絡。
F. 即時戰略游戲
即時戰略(RTS)游戲的環境更加復雜，玩家必須在部分可觀測的地圖中實時同步控制多個智能體。
即時戰略主要有以下幾種方法：
- 獨立 Q 學習(IQL)將多智能體強化學習問題簡化，智能體學習一種策略，可以獨立控制單元，而將其他智能體當作環境的一部分 [107]。
- 多智能體雙向協調網絡(BiCNet)基于雙向 RNN 實現一種向量化的 actor-critic 框架，其中一個向度適用于每一個智能體，其輸出為一系列操作 [82]。
- Counterfactual multi-agent(COMA)策略梯度是一種 actor-critic 方法，該方法具備一個中心化的 critic 和多個去中心化的 actor，用 critic 網絡計算出的反事實基線(counterfactual baseline)來解決多智能體信度分配的問題 [21]。
G. Physics Games(略)
H. 基于文本的游戲
這類游戲中的狀態和操作都以文本的形式呈現，是一種特殊的電子游戲類型。研究者專門設計了一種叫作 LSTM-DQN [74] 的網絡架構來玩這類游戲。使用 LSTM 網絡可以把文本從世界狀態轉換成向量表征，評估所有可能的狀態動作對(state-action pair)的 Q 值。
5. 游戲中的深度學習概覽(略)
6. 開放性挑戰
深度學習，特別是深度強化學習方法，在電子游戲中取得了卓越的成果，但是仍然存在大量重要的開放性挑戰。本節我們將對此進行概述。
A. 通用電子游戲
圖 3. 本文討論的深度學習技術的影響力圖
圖 3中每一個節點代表一個算法，顏色代表游戲基準，與中心的距離代表原始論文在 arXiv 上的發表時間，箭頭表示技術之間的關系，每一個節點指向所有使用或修改過該技術的節點。本論文未討論的影響力則不在圖中出現。
B. 稀疏獎勵的游戲
C. 多智能體學習
D. 計算資源
E. 深度學習方法在游戲產業中的應用情況
F. 游戲開發交互工具
G. 創造新型電子游戲
H. 終身適應性
I. 與人類相似的玩游戲方式
J. 性能水平可調整的智能體
K. 游戲的學習模型
L. 處理大型決策空間
7. 結論
本論文對應用到電子游戲中的深度學習方法進行了綜述，涉及到的電子游戲類型包括：街機游戲、競速游戲、第一人稱射擊游戲、開放世界游戲、即時戰略游戲、物理游戲和基于文本的游戲。涉及到的多數工作研究端到端無模型深度強化學習，其中卷積神經網絡能夠通過游戲互動從原始像素中直接學習玩游戲。一些研究還展示了使用監督學習從游戲日志中學習，讓智能體自己在游戲環境中展開互動的模型。對于一些簡單的游戲，如很多街機游戲，本文談及的很多方法的表現已經超過人類水平，而復雜度更高的游戲還面臨很多開放性挑戰。
【本文是51CTO專欄機構“機器之心”的原創譯文，微信公眾號“機器之心( id: almosthuman2014)”】
