遊戲人工智慧 讀書筆記（十）利用AI玩遊戲

來自專欄第九藝術魅影

作者： Vino Wan @ Tencent Game AI Research Center (TGAIRC)

本文內容包含（但不限於）以下章節：

本書英文版： Artificial Intelligence and Games - A Springer Textbook4

利用AI玩遊戲

為何使用AI來玩遊戲

選擇AI來玩遊戲之前，我們需要明確兩個問題：

1. AI的目標是為了獲勝，還是為了提高遊戲體驗？

在棋牌類遊戲或者FPS類遊戲中，提供一個高性能的AI能增加遊戲的挑戰性；而在另一些遊戲中，比如模擬人生和MineCraft等，這些遊戲並沒有一個明確的獲勝條件，玩家在這些遊戲中主要目標也不是獲勝，而是為了諸如消磨時間、放鬆心情或者是交友的目標，那麼在這些遊戲中就需要一個能夠優化遊戲體驗的AI。

1. AI的目標是為了模擬人類角色（Player Character，後面簡稱為PC）還是為了模擬非人類角色（Non Player Character，後面簡稱為NPC）？

有一些遊戲希望AI能夠模擬人類角色（PC），比如在CS中有一些角色可以由AI來控制，而這些遊戲使用AI的目的可能是人數不夠，需要AI來補充人數，也可能是為了故意輸給玩家，而又不讓玩家感知角色是AI控制的。而在另一些遊戲中，比如很多角色扮演類遊戲（Role-Playing Game）中就存在大量的NPC，這些NPC需要AI來使得遊戲更加流暢的運行，提高遊戲的體驗。

所以對AI的需求可以劃分為如下圖所示的4個類別：

遊戲設計和AI設計的考量

遊戲本身的特徵以及AI演算法的特徵決定了如何在遊戲中選擇合適的AI。

按照Characteristics of Games中遊戲劃分的方法，遊戲可以按照可觀察性（observability）、隨機性（stochasticity）以及時間粒度（time granularity）這三個維度劃分成如下圖所示的類別：

而這些遊戲特徵又會影響對AI演算法的選擇。比如在具有隨機性的遊戲中就不能使用MCTS演算法，即使是增強學習也需要對模型做一些調整；而完美信息和非完美信息的建模方法也有很大的不同，比如在非完美信息情況下，就需要通過ISMCTS（Information Set Monte Carlo Tree Search）的方案來做樹搜索；有些遊戲對實時性要求不高，就可以使用基於規劃的方法，比如樹搜索等，而對實時性要求高的遊戲就必須儘快的返回評估結果，所以也就無法使用基於規劃的方法。

AI演算法本身的一些特性也會影響對AI演算法的選擇。比如演算法的輸入是結構化的特徵還是原始的視覺輸入，顯然原始的視覺輸入對演算法更加具有挑戰；再比如遊戲的模擬成本高不高，如果不高的話就可以使用tree-search的方法（例如MCTS），如果模擬成本很高，那就只能使用一些online的方法（例如A3C和DQN等）；

AI如何玩遊戲

利用AI玩遊戲主要有4種方法：

• 基於規劃的方法（Planning-Based Approaches）
• 基於增強學習的方法
• 基於監督學習的方法
• 混合方法

基於規劃的方法

基於規劃的方法一般都是通過探索未來的狀態空間來決定當前的動作，這種方法一般都需要有一個模擬器來計算未來的狀態。基於規劃的方法又可以分為：

• 經典的樹搜索方法：包括在遊戲中用於尋路的A*演算法和在對抗遊戲（比如棋牌）中使用的minmax演算法
• 隨機樹搜索方法：最常見的隨機樹搜索方法就是MCTS以及在非完美信息情況下使用的ISMCTS
• 進化規劃（Evolutionary Planning）方法：利用進化演算法來優化AI的動作序列以達到最大化效能函數（utility function）的目的。相比樹搜索的方法，這種方法更加適合用於動作空間比較大的場景。
• 基於符號表示的規劃方法：有些遊戲可以使用一階符號邏輯來表示事件、狀態和動作之間的轉換，然後就可以基於這寫符號邏輯表示來對遊戲進行規劃。

增強學習

增強學習的方法把遊戲建模稱為蒙特卡洛決策過程（Monte Carlo Decision Process）。增強學習方法需要較長的訓練時間，但在預測時的時間很短，這些特點正好和基於規劃的方法相反。以下主要討論兩類增強學習方法：

• 經典的增強學習方法以及深度增強學習方法：

最初經典的增強學習演算法在一些簡單的棋牌類遊戲取得了很好的效果，但是對於更加複雜的一些遊戲，經典的增強學習演算法難以遍歷所有的狀態-動作組合，這時就需要通過近似函數模型（function approximator）來壓縮狀態表示，而神經網路（Neural Network）就是一個非常好的近似函數模型。由於Reward的稀疏性，Agent可能很長時間都無法收到新的reward值，這就會導致近似函數模型在不同狀態下始終只有一個輸出值，這樣的話模型就會退化，這就是所謂的「災難性遺忘」（catastrophic forgetting）

• 基於進化演算法的增強學習方法：

基於進化演算法的增強學習演算法一般通過遺傳演算法或者進化演算法來進化神經網路的權重和拓撲結構，這種方法在一些簡單的遊戲取得了不錯的成績，但是由於維度詛咒（curse of dimensionality）的原因，這種隨機搜索的方法只能處理輸入維度較少（一般來說不多於50維）的場景。

監督學習

一般的監督學習方法就是通過使用人類的軌跡，利用近似函數模型（function approximator）學習這些樣本，學習到模型之後就可以用來預測某一個狀態的輸出目標。但是如下圖所示，人類的樣本覆蓋的分布範圍只佔整個分布的很小一部分，為了填補這些空白，可以有很多方法，比如最簡單的DAgger（Dataset Aggregation），核心思想就是當出現新的狀態，就由人類專家來給出目標值。

混合方法

在很多遊戲中也常常會把之前討論的三種方法結合起來一起使用，比如有一種動態腳本的方法，結合了基於腳本的規則和增強學習方法，能夠基於當前的狀態動態的選擇執行的腳本，這種方法被應用到很多格鬥類遊戲和即時戰略類遊戲中。

AI怎麼玩遊戲？

接下來我們將按照遊戲的類別來討論AI是如何玩遊戲的

棋類遊戲

由於棋類遊戲具有狀態表示簡單並且具有完美信息，所以早起的AI研究有很多都是針對棋類遊戲的。棋類遊戲主要研究方向是對抗性規劃（adversarial planning），即在博弈中如何選擇最佳的動作。由於棋類遊戲通常具有離散化的狀態和動作，所以非常適合使用樹搜索的方法。對於一些簡單的棋類遊戲可以直接使用minmax樹搜索結合剪枝來進行樹搜索，而對於一些比較複雜的棋類遊戲，比如最近去的突破的圍棋，就需要通過MCTS（Monte Carlo Tree Search）來進行樹搜索。

牌類遊戲

與棋類遊戲不同，大部分的牌類遊戲都是非完美信息的，所以牌類遊戲主要的研究方向就是在非完美信息條件下的對抗性規劃，即在包含隱藏信息的條件下選擇最佳的動作。通常這類問題都是通過反事實遺憾最小化（Counterfactual Regret Minimization）來實現的，這個演算法通過計算每次實際採取動作的收益和最佳動作收益之差，即遺憾（regret），然後迭代的最小化這個遺憾值，最終收斂到一個最優的策略。這個演算法在一些比較簡單的牌類遊戲中取得了較好的效果，但是對於德州撲克這種比較複雜的牌類遊戲，還是需要在原有的基礎上做一些優化，比如DeepStack就是在原有的CRF演算法的基礎上借鑒了AlphaGo的思想，增加了樹搜索以及狀態評估模型。

經典的競技類遊戲

經典的競技類遊戲平台，比如Atari 2600，包含了多個種類的遊戲，也同時對AI提出了不同的能力要求。比如一些體育類的遊戲主要考驗的是反應的能力，而超級馬里奧這樣的遊戲又主要考驗對遊戲中的事件以及軌跡的提前判斷能力，還有像吃豆人這種考驗在迷宮中導航的能力，甚至有祖瑪的復仇這種考驗長期的規劃以及記憶隱藏的狀態能力。

大部分的經典競技類遊戲目前已經很好的得到了結果，比如2015年DeepMind提出的DQN方法以及它後續的一系列變種已經在很多Atari遊戲上取得了和人類水平相當甚至是超過人類水平的能力，但是也有一些這些方法表現的就非常差，比如吃豆人遊戲，在缺乏向前搜索的情況下，經典的增強學習方法表現都不好，只有在具備Planning能力的AI才能取得平均人類的水平，不過最近Microsoft提出了一種混合reward的架構，通過把複雜的reward函數分解為不同的部分，然後由不同的agent分別學習，最後把各個Agent的Q函數聚合稱為一個最終的結果。

目前，經典的競技類遊戲有很多測試床：

• 超級馬里奧：主要包括設計AI能力更高、AI表現更像人以及生成遊戲關卡
• ALE平台：主要包括Atari的很多遊戲，DeepMind的很多研究都是基於ALE平台
• 通用遊戲AI（General Video Game AI）：主要目標是設計一個AI能夠完成多種遊戲

策略遊戲

策略類遊戲一般可以分為「回合制」以及「實時」的，「文明」就是典型的回合制遊戲，而「星際爭霸」就是典型的實時策略遊戲。策略類遊戲的主要挑戰就是需要同時對多個遊戲單元（比如騎士、坦克等）作出規劃（planning），導致動作空間巨大。與此同時，策略類遊戲的每一個動作的影響都很長遠，導致遊戲的規劃深度非常的長。這兩個特點導致策略類遊戲planning的複雜度遠遠超過棋牌類遊戲，並且對於即時戰略類遊戲（Real-Time Strategy）需要能夠實時的planning，並選擇最合適的動作。所以為了能夠處理這麼複雜的搜索場景，必須對問題作出簡化。

星際爭霸是一個典型的即時戰略類遊戲（Real-Time Strategy），並且在玩家中非常流行，目前也有多個星際爭霸的研究環境，包括基於星際1的BWAPI以及TorchCraft和基於星際2的SC2LE。並且還有多個星際爭霸的AI機器人比賽，比如IEEE CIG和AIIDE。

由於星際爭霸非常複雜，一般來說，會把這個問題分為三個層次：戰略、戰術以及微操，如下圖所示。大部分研究都只能解決其中的一個部分，目前為止還沒有一個AI能夠達到人類的平均水平。

在微觀層面，需要解決每個遊戲單元具體執行的動作。目前的研究還大多數集中在兩隻隊伍面對面對戰的場景，而建築物建造、科技研究以及戰爭迷霧這些都沒有涉及。早期研究有一些非機器學習方法，比如勢能場和模糊邏輯，應用在這個場景並取得了一定的成功，後來出現了很多基於增強學習的方法，比如為每一個遊戲單元學習一個單獨的Q函數，還有一些利用forward model的基於planning的方法，也取得一定的成功。總體來說，目前大多數的研究還只能解決比較簡單的場景，尚未有突破性的進展。

在宏觀層面，需要根據對手的動作來動態的選擇策略。目前大部分的AI機器人都沒有實現多個策略，更不用說動態的選擇策略了。因為星際爭霸是非完美信息遊戲，要判斷對手的策略只能基於有限的可觀察數據，要做到這一點是非常困難的。

賽車遊戲

賽車遊戲一般需要玩家駕駛賽車在儘可能短的時間內跑完賽道，有些簡單的遊戲只需要控制賽車的方向，而一些複雜的遊戲還需要玩家考慮換擋、離合以及氮氣等等。在不考慮其他玩家的情況下，簡單的動作只需要短期規劃即可，而複雜的動作則需要考慮長遠一些，而在考慮其他玩家的情況下，還需要考慮玩家之間的對抗策略。

當前賽車遊戲的研究環境主要是TORCS，並且每年都有舉辦一次比賽Simulated Car Racing Championship，目前AI已經可以達到人類高手水平。從參賽的AI機器人採用的技術來看，賽車遊戲AI的主要方法包括：

• 非機器學習類方法：比如將賽道分成很多段，然後在人類賽道軌跡中需要和當前段最相近的，最後按照這個最相近的段中人類執行的動作來運行
• 機器學習類方法：
• 增強學習方法：將賽車比賽建模成為MDP問題，根據比賽時間賦予Reward，然後根據當前狀態（可以是結構化輸入也可以是純圖片輸入）判斷最優的動作
• 進化演算法：根據領域知識為賽車建立模型，並使用進化演算法調優模型參數。

第一人稱射擊遊戲

第一人稱射擊遊戲（後面簡稱為FPS遊戲）是一個快節奏的遊戲，強調人或者AI的反應能力，並且需要具備在複雜的3D環境下的導航和需要目標的能力，在多人場景下，還需要具備團隊協作能力，這些都對AI提出了很多挑戰。

目前FPS遊戲主要有兩個AI機器人比賽：

• 2K BotPrize：基於Unreal Tournament 2004的AI機器人比賽，比賽的主要目標是讓AI更加像人，並讓其他玩家感覺不到是AI在和他們玩遊戲。2014年獲勝的團隊主要是採用進化演算法來優化多目標函數的反覆。
• VizDoom：基於DOOM的AI機器人比賽，比賽分為三個場景：採集加血包、迷宮導航以及deathmatch比賽模式，比賽的主要目標是提高AI的表現能力，目前大多數研究方法都是基於Deep Reinforcement Learning，但也有基於進化演算法的研究工作。

其他遊戲

還有其他一些非典型的遊戲AI，比如嚴肅遊戲（Serious Games）中的AI，主要目的是為了科學、工程、數學或者是心理類的互動，具體應用的技術也和遊戲的內容和方向有關。還有一種文本冒險類遊戲（text-based adventure games）需要通過自然語言處理技術來理解用戶的輸入，並且根據遊戲內容生成輸出，這樣就可以和用戶產生互動。還有一些諸如因果類遊戲（Casual Games），比如憤怒的小鳥和植物大戰殭屍等，和格鬥類遊戲以及沙箱類遊戲最近都引起了比較多的關注，也有一些專門針對這些遊戲的研究，但主要方法和思路和之前的遊戲都差不多，在此就不在贅述。