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

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

Chapter 2 AI Methods

Chapter 2.1 General Notes

本書(shū)英文版： Artificial Intelligence and Games - A Springer Textbook

_

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

吃豆人

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Failure: 表示這個(gè)節(jié)點(diǎn)執(zhí)行失敗了

而行為樹(shù)的節(jié)點(diǎn)有3種類型：

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

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

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

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

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

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

更多推薦

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

游戲人工智能 讀書(shū)筆記 （二） 游戲人工智能簡(jiǎn)史

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

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

點(diǎn)擊：https://wetest.qq.com/cloud/deepcompatibilitytesting 了解更多詳情。

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