摘要：原文鏈接本文內(nèi)容包含以下章節(jié)本書英文版這個章節(jié)主要討論了在游戲中經(jīng)常用到的一些基礎(chǔ)的人工智能算法。行為樹是把的圖轉(zhuǎn)變成為一顆樹結(jié)構(gòu)。根據(jù)當(dāng)前游戲的環(huán)境狀態(tài)得到某一個行為的效用值。

作者：蘇博覽
商業(yè)轉(zhuǎn)載請聯(lián)系騰訊WeTest獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
原文鏈接：https://wetest.qq.com/lab/view/427.html

Chapter 2 AI Methods

Chapter 2.1 General Notes

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

_

這個章節(jié)主要討論了在游戲中經(jīng)常用到的一些基礎(chǔ)的人工智能算法。這些算法大部分都出現(xiàn)在一些人工智能和機器學(xué)習(xí)的入門書籍中。在講解算法在游戲中的應(yīng)用的時候，會以吃豆人（Ms Pac-Man)作為樣例，講解怎么用行為樹算法，樹搜索算法，監(jiān)督學(xué)習(xí)算法，無監(jiān)督學(xué)習(xí)算法，強化學(xué)習(xí)算法和進化算法來構(gòu)建一個玩游戲的AI。

吃豆人

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

首先是怎么把學(xué)到的玩游戲的知識用某種數(shù)據(jù)結(jié)構(gòu)來表示出來。這個數(shù)據(jù)結(jié)構(gòu)也是和要用的算法強相關(guān)的。比如如果用文法演化算法(Grammatical Evolution），最后學(xué)到的就是一些文法（Grammars）；如果用概率模型或者有限狀態(tài)機，最后知識就表示成一個圖(Graphs)；而行為樹和決策樹還有遺傳算法會學(xué)到一顆樹(Trees)，神經(jīng)網(wǎng)絡(luò)自然是聯(lián)結(jié)主義的(Connectionism）, 遺傳算法和演化策略會帶來一些基因編碼(Genetic Representation), 而TD-learning 和 Q-learning則學(xué)到了一下狀態(tài)轉(zhuǎn)移的表格(Tabular)。

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

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

Utility 在不同的算法上的叫法會有所不同，在含義上也有細微的差別。例如在一些樹搜索算法上，我們會用啟發(fā)式的規(guī)則(Heuristic)來指導(dǎo)算法的收斂。而在遺傳算法上，它又被叫做適應(yīng)度函數(shù)(Fitting Function)。在優(yōu)化算法上，我們更常用的詞語是Loss, Error, Cost； 而在強化學(xué)習(xí)，Reward是一個更常用的單詞，這里最主要的原因是：做RL的人由于整天面對著逆天難的問題，所以喜歡用reward(相對于loss)來激勵自己。（大霧）

這樣，我們訓(xùn)練AI的過程就是尋找一套Representation最好的參數(shù)，可以最大化Utility。因此，能夠?qū)W到一個好用的模型，取決于Utility Function是否設(shè)計的合理，和我們的目標(biāo)是否完全一致。對于監(jiān)督學(xué)習(xí)來說，Utility等價于其Label；對于強化學(xué)習(xí)來說，Utility來自于環(huán)境的反饋。而無監(jiān)督學(xué)習(xí)的Utility則來自于數(shù)據(jù)本身的結(jié)構(gòu)和共性。

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

FSM直到21世紀(jì)的前十年都還是廣泛的應(yīng)用到各種游戲之中。我們可以把FSM理解為一個圖(Graphs), 游戲中的狀態(tài)是圖的一個節(jié)點（Nodes), 可以相互轉(zhuǎn)化的狀態(tài)之間有連線(Edges),連線之間定義了狀態(tài)轉(zhuǎn)移(Transitions)的條件，而在每個狀態(tài)中，定義了一系列的動作(Actions),當(dāng)AI處于該狀態(tài)時，就執(zhí)行具體的動作，如向左或向右或者更復(fù)雜的組合動作。

一個FSM的吃豆人AI, 定義了3個狀態(tài)：躲避Ghosts, 追逐Ghosts和尋找豆子以及狀態(tài)之間的轉(zhuǎn)移條件

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

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

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

行為樹是把FSM的圖轉(zhuǎn)變成為一顆樹結(jié)構(gòu)。因此行為樹是有一個Root節(jié)點，然后往下有一些中間節(jié)點，最后是葉子節(jié)點。我們從根節(jié)點遍歷行為樹，每一個子節(jié)點被執(zhí)行的時候都按預(yù)設(shè)的時間間隔回傳三種信息給到父節(jié)點：

Run: 表示這個節(jié)點還在繼續(xù)執(zhí)行

Success:表示這個節(jié)點已經(jīng)成功執(zhí)行了

Failure: 表示這個節(jié)點執(zhí)行失敗了

而行為樹的節(jié)點有3種類型：

Sequence: (如上圖的藍色方塊）表示該父節(jié)點會順序執(zhí)行它的子節(jié)點，并且知道它的所有子節(jié)點都成功執(zhí)行了，它才會回傳Success給更上層的節(jié)點。

Selector:(如上圖的紅色方塊）表示該父節(jié)點會從其子節(jié)點中選擇其中一個執(zhí)行，只要有一個子節(jié)點執(zhí)行成功，該父節(jié)點就會返回Success。除非所有子節(jié)點都執(zhí)行失敗，該父節(jié)點才會返回失敗。父節(jié)點選擇子節(jié)點的順序有兩種方式：a. Probability：按概率選取子節(jié)點執(zhí)行的順序；b. Priority: 該預(yù)設(shè)的順序選取子節(jié)點。

Decorator:(如上圖紫色的方塊）相當(dāng)于節(jié)點執(zhí)行增加一些條件，比如限定執(zhí)行的時間，或者失敗重新執(zhí)行的次數(shù)。如圖中是限定了一個條件，只有在看到Ghost的時候，吃豆子(Eat Next Pellet)這個節(jié)點才會返回Fail 狀態(tài)。

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

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

在行為樹里面，選擇不同子樹的方式還是稍顯簡單，通過一定的規(guī)則，或者預(yù)設(shè)的概率來選擇不同的子節(jié)點（子樹）來執(zhí)行。因此人們在上面添加了基于效用的方式(Utility-based)。簡單說來，我們定義一個Utility Function: u = F(S,a)。 根據(jù)當(dāng)前游戲的環(huán)境狀態(tài)S, 得到某一個行為a的效用值u。這個Utility Function是可以通過規(guī)則設(shè)定，也可以通過一些復(fù)雜的學(xué)習(xí)方法來得到。比如我們可以用一個神經(jīng)網(wǎng)絡(luò)去預(yù)測在當(dāng)前狀態(tài)下，做哪個動作更好。比如在吃豆人游戲中，可能我們就不需要來寫一些規(guī)則來判斷該做什么動作（比如看到Ghost就停止吃豆子的子樹執(zhí)行），而可以用更動態(tài)的方式來控制（比如Ghost在多遠的地方，往哪個方向走，豆子和Ghost和NPC的位置關(guān)系怎么樣）是否停止吃豆子的子樹執(zhí)行。當(dāng)然更General的說，其實后續(xù)的強化學(xué)習(xí)，監(jiān)督學(xué)習(xí)也好，都是在學(xué)一個Utility Function來控制NPC的動作。本質(zhì)上，Utility-based AI是一種構(gòu)建NPC的思想，可以應(yīng)用到不同的AI方法上。

更多推薦

游戲人工智能 讀書筆記 （一）前言與介紹

游戲人工智能 讀書筆記 （二） 游戲人工智能簡史

游戲人工智能 讀書筆記 （三） 游戲和人工智能的相互影響

_
“深度兼容測試”現(xiàn)已對外，騰訊專家為您定制自動化測試腳本，覆蓋應(yīng)用核心場景，對上百款主流機型進行適配兼容測試，提供詳細測試報告。

點擊：https://wetest.qq.com/cloud/deepcompatibilitytesting 了解更多詳情。

如果使用當(dāng)中有任何疑問，歡迎聯(lián)系騰訊WeTest企業(yè)QQ：2852350015