遊戲人工智慧 讀書筆記 （四） AI演算法簡介——Ad-Hoc 行為編程

來自專欄第九藝術魅影9 人贊了文章

作者： fled

本文內容包含以下章節：

Chapter 2 AI Methods

Chapter 2.1 General Notes

Chapter 2.2 Ad-Hoc Behavior Authoring

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

這個章節主要討論了在遊戲中經常用到的一些基礎的人工智慧演算法。這些演算法大部分都出現在一些人工智慧和機器學習的入門書籍中。在講解演算法在遊戲中的應用的時候，會以吃豆人（Ms Pac-Man)作為樣例，講解怎麼用行為樹演算法，樹搜索演算法，監督學習演算法，無監督學習演算法，強化學習演算法和進化演算法來構建一個玩遊戲的AI。

一. AI演算法的基本要素

這些AI演算法雖然形態各有不同，但是本質上都是基於兩個基本的要素來做文章。一個是演算法的表示(Representation), 另外一個是效用(Utility)。

首先是怎麼把學到的玩遊戲的知識用某種數據結構來表示出來。這個數據結構也是和要用的演算法強相關的。比如如果用文法演化演算法(Grammatical Evolution），最後學到的就是一些文法（Grammars）；如果用概率模型或者有限狀態機，最後知識就表示成一個圖(Graphs)；而行為樹和決策樹還有遺傳演算法會學到一顆樹(Trees)，神經網路自然是聯結主義的(Connectionism）, 遺傳演算法和演化策略會帶來一些基因編碼(Genetic Representation), 而TD-learning 和 Q-learning則學到了一下狀態轉移的表格(Tabular)。

當然，尋找一個最優的演算法表示通常是很難的，並且世界上沒有免費的午餐，演算法之間總是各有利弊的。不過一般來說，我們希望選擇的演算法的表示儘可能的簡單，和佔用更小的空間。而我們需要有一些先驗知識來找到一個較好的演算法表示。

另外一方面，我們會用效用（Utility)這個來自博弈論的術語來指導演算法的訓練。不嚴格的來說，可以把它看做一個函數，輸入是當前狀態和演算法可能的動作(Action)，輸出是演算法做出某個動作所能夠獲得的好處。理論上來說，如果我們能得到一個完備的Utility Function, 我們的演算法每次都可以找到最優的路徑。但實際上，我們只能夠得到一個估計值，或者更確切的，在沒有先驗知識的情況下，我們只能通過記住我們探索過的狀態和路徑及其獲得的回報來估算一個效用值來表示某個走法的好壞(Measure of Goodness)。如果遊戲本身的狀態空間比較小，我們可以通過遍歷所有的可能情況來得到一個準備的Utility Function。而通常我們面對的問題都有著極大的搜索空間，因此我們希望能夠儘可能的探索到更多的路徑，然後在探索到的數據上進行採樣來得到一個估計的Utility。

Utility 在不同的演算法上的叫法會有所不同，在含義上也有細微的差別。例如在一些樹搜索演算法上，我們會用啟發式的規則(Heuristic)來指導演算法的收斂。而在遺傳演算法上，它又被叫做適應度函數(Fitting Function)。在優化演算法上，我們更常用的詞語是Loss, Error, Cost； 而在強化學習，Reward是一個更常用的單詞，

這樣，我們訓練AI的過程就是尋找一套Representation最好的參數，可以最大化Utility。因此，能夠學到一個好用的模型，取決於Utility Function是否設計的合理，和我們的目標是否完全一致。對於監督學習來說，Utility等價於其Label；對於強化學習來說，Utility來自於環境的反饋。而無監督學習的Utility則來自於數據本身的結構和共性。

二. 基於有限狀態機的AI實現

實現一個NPC，最簡單的方法當時就是寫一些規則，但這樣子顯然比較low，不過在很多場景下其實也能滿足需要了。如果我們把規則（If, else 語句）抽象，就變成了有限狀態機(Finite State Machine, FSM) 或者 行為樹(Behavior Trees, BT)。

FSM直到21世紀的前十年都還是廣泛的應用到各種遊戲之中。我們可以把FSM理解為一個圖(Graphs), 遊戲中的狀態是圖的一個節點（Nodes), 可以相互轉化的狀態之間有連線(Edges),連線之間定義了狀態轉移(Transitions)的條件，而在每個狀態中，定義了一系列的動作(Actions),當AI處於該狀態時，就執行具體的動作，如向左或向右或者更複雜的組合動作。

例如上面的一個基於FSM的吃豆人AI，首先定義了狀態和狀態轉移的條件。當在尋找豆子的狀態的時候，可以給AI編程具體在每個狀態的行為。比如在尋找豆子的狀態，一開始隨機遊走，如果看到豆子就去吃掉它，如果看到Ghost，就進入到躲避Ghost的狀態。下面是一個簡單的3種狀態下動作的偽代碼：

def seek_pellet: while 1: if ghost_in_sight: return evade_ghost_state if power_pill_eaten: return chase_ghost_state if pellet_in_sight: go_and_eat_pellet() #using pathfinding algorithm find best action else: move_randomly()def evade_ghost: while 1: if not ghost_in_sight: return seek_pellet_state if power_pill_eaten: return chase_ghost_state leave_the_ghost() # using tree search to find best actiondef chase_ghost: while 1: if power_pill_expired: return seek_pellet_state find_the_ghost() # using tree search to find best action

三. 基於行為樹的AI實現

可以看到FSM的AI的模式是非常固定的，玩家很容易發現其中的pattern，這個通過模糊邏輯(Fuzzy Logic)和增加概率可以得到一定緩解。另外，對於一些要完成比較難的任務的NPC,需要為其設計很多不同的狀態和狀態轉移方式，整個過程是非常複雜和難以調試的。因此人們定義了行為樹（BT),通過模塊化(Modularity)的設計，可以把複雜的行為拆解成簡單的任務，從而減輕整個系統的複雜度和提高可維護性。因此，自光暈2(Halo 2)之後，BT就取代了FSM，成為遊戲工業界最常用的NPC演算法。

行為樹是把FSM的圖轉變成為一顆樹結構。因此行為樹是有一個Root節點，然後往下有一些中間節點，最後是葉子節點。我們從根節點遍歷行為樹，每一個子節點被執行的時候都按預設的時間間隔回傳三種信息給到父節點：

1. Run: 表示這個節點還在繼續執行
2. Success:表示這個節點已經成功執行了
3. Failure: 表示這個節點執行失敗了

而行為樹的節點有3種類型：

1. Sequence: (如上圖的藍色方塊）表示該父節點會順序執行它的子節點，並且知道它的所有子節點都成功執行了，它才會回傳Success給更上層的節點。
2. Selector:(如上圖的紅色方塊）表示該父節點會從其子節點中選擇其中一個執行，只要有一個子節點執行成功，該父節點就會返回Success。除非所有子節點都執行失敗，該父節點才會返回失敗。父節點選擇子節點的順序有兩種方式：a. Probability：按概率選取子節點執行的順序；b. Priority: 該預設的順序選取子節點。
3. Decorator:(如上圖紫色的方塊）相當於節點執行增加一些條件，比如限定執行的時間，或者失敗重新執行的次數。如圖中是限定了一個條件，只有在看到Ghost的時候，吃豆子(Eat Next Pellet)這個節點才會返回Fail 狀態。

可以看到，行為樹的結構可以比較方便的把複雜的行為分解成層次的簡單結構，方便維護。例如我可以在吃豆子（Eat Next Pellet)這個Node上設定新的很複雜的演算法，但不會影響整個樹的其他節點。同時測試起來也比較方便，我們可以針對行為樹的某個子樹來進行測試，而不影響整個大的框架。

當然，行為樹和FSM也有同樣的問題，就是NPC的行為的可預見性還是比較大的，整個行為的模式還是受限於整體的行為樹框架。雖然可以通過一些概率的方式來增加一些隨機性，但整體來看還是有很多局限性的。

在行為樹裡面，選擇不同子樹的方式還是稍顯簡單，通過一定的規則，或者預設的概率來選擇不同的子節點（子樹）來執行。因此人們在上面添加了基於效用的方式(Utility-based)。簡單說來，我們定義一個Utility Function: u = F(S,a)。 根據當前遊戲的環境狀態S, 得到某一個行為a的效用值u。這個Utility Function是可以通過規則設定，也可以通過一些複雜的學習方法來得到。比如我們可以用一個神經網路去預測在當前狀態下，做哪個動作更好。比如在吃豆人遊戲中，可能我們就不需要來寫一些規則來判斷該做什麼動作（比如看到Ghost就停止吃豆子的子樹執行），而可以用更動態的方式來控制（比如Ghost在多遠的地方，往哪個方向走，豆子和Ghost和NPC的位置關係怎麼樣）是否停止吃豆子的子樹執行。當然更General的說，其實後續的強化學習，監督學習也好，都是在學一個Utility Function來控制NPC的動作。本質上，Utility-based AI是一種構建NPC的思想，可以應用到不同的AI方法上。