遊戲人工智慧 讀書筆記 （五） AI演算法簡介——樹搜索

來自專欄第九藝術魅影

作者： fled

本文內容包含以下章節：

Chapter 2 AI Methods

Chapter 2.3 Tree Search

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

在一定程度上，人工智慧都可以認為是"搜索問題"， 其本質上都是在一個高維的空間上，搜索到一條可行的路徑。只是在很多複雜的問題上，求解的空間過於龐大，而解的空間又特別狹窄，造成了無法遍歷所有的可能性，而很大概率上無法找到解的空間。

在遊戲業界常用的搜索演算法是基於"樹搜索"的, 其本質都是構建一顆搜索樹，其節點(Node)代表遊戲中的某一個狀態。節點之間的連線(Edge)代表遊戲中的狀態節點A通過某個動作轉移到狀態節點B。通常從一個節點有多個動作可以到達不同的子節點（狀態），因此用不同的方式去選擇搜索子節點的順序就可以區分出不同的搜索演算法：

盲目搜索（Un-informed Search): 其實稱為 Brute-force Search （暴力搜索）更加合理一些。就是完全不考慮AI的目標和效用，純粹的去以某種固定的方式去遍歷遊戲的狀態樹，以求找到一種合理的路徑。這裡最常用的兩種搜索就是 廣度優先（Breadth-first)和深度優先(Depth-first)。具體就不詳細展開了，應該是任何一本講數據結構的書上都會講到的。

顯然這樣的演算法效率是很低的，基本上是不實用的。但是其一些變體（iterative width search， Sentient Sketchbook) 還是能在遊戲的某些方面上應用的。更多的關於Uninformed Search的內容可以參考第四章的內容。

一種改進的演算法稱為 最佳優先搜索(Best-First Search)。在Best-First Search中，我們通過用AI的目標以某種方式來指導AI的搜索過程，讓AI儘可能的優先搜索那些更有可能到達我們目標的節點。這中間，在業界中被廣泛應用的是A*演算法。在基本的A*演算法中，從當前的節點 可以通過選擇不同的動作來進入不同的狀態： 。那麼選擇不同狀態的cost由當前狀態到下一狀態的距離 和下一狀態到目標的距離 決定。然後AI會選擇cost最低的一個動作來進入對應的新的狀態。在這上面，怎麼定義距離，以及怎麼組合這兩個距離都是可以作文章的地方。

很自然的，A*演算法可以用來做遊戲和其他領域的尋路演算法。因為在尋路(pathfinding)上，目標和當前狀態的距離很好定義，可以簡單的定義為當前點和終點的物理意義上的距離，因此可以很好的定義在當前狀態下的最好的下一個狀態。當然，為了提高在遊戲龐大的狀態空間中的尋路效率，也有很多A*演算法的改進，如grid-based pathfinding，在不少遊戲上都有公開的benchmarks (http://movingai.com/benchmarks): 星際爭霸(StarCraft),魔獸世界3: 混亂之治(Warcraft III Reign of Chaos)，龍騰世紀:起源（Dragon Age: Origins)。

此外，在某些特定遊戲中，只要我們能夠很好的定義遊戲中的狀態之間，以及最終的目標的距離，A*演算法也可以構建出非常不錯的NPC。比如像超級馬里奧(Super Mario Bros)這樣的橫版或者豎版過關遊戲，其當前狀態都是和Agent在當前關卡所處的坐標相關的，而最終的目標永遠是關卡最右端的結束點，因此可以在這個基礎上加入一些當前的障礙物，怪物等的信息，就能比較準確的估計出當前狀態的好壞。

而多人之間的對抗性的遊戲中，雙方的目標是零和的，因此一方的最優狀態並不是另一方的最優狀態。因此在這樣的博弈樹(Game Tree)上，尤其是兩人對弈的完美信息博弈遊戲中，極小化極大搜索(Minimax Search)應用的非常廣泛。

Minimax的主要思路是，在完整的一個Game Tree上，假定每個玩家都是理性和聰明的，都走其中最好的走法。那麼取其中一個玩家的視角，在他行動的時候，選取對其收益最大的Node,也即是在對手下一步行動所有最大收益的最小值，具體的可以由以下的遞歸偽代碼決定。在葉子結點的值(Value)是由終局的狀態決定的，如獲勝收益為1，失敗收益為-1。最終，每個狀態節點上都會有一個值。對於玩家來說，每次行動的時候都選取值最大的節點。

def minimax(node, acting_player) if node is terminal: #Leaf node return node.value if acting_player == opponent: #Mininum Node v = MAX_VALUE for child in node.childs: v = min(v, minimax(child,player)) if action_player == player: #Maximum Node v = MIN_VALUE for child in node.childs: v = max(v, minimax(child, opponent)) return v

但是對於複雜的遊戲來說，構建和搜索一顆完整的Game Tree是很困難的，因此對於大部分使用的Minimax演算法，都會增加一個參數Depth，來限制樹的搜索深度，當達到一定的搜索深度的時候，直接返回一個估計的該節點的Value,這個節點的Value估計可以用規則來實現，也可以用模型來預估。

另外一個提高搜索效率的方法是alpha-beta剪枝，從演算法原理上來說，當我們在博弈樹第L層（輪到玩家行動）的時候，我們需要搜索玩家可能的N個動作節點 的時候，如果我們在搜索前t個Node的時候，可以得到當前最大的Value值 ,那麼在搜索 的時候，因為該節點的Value值由其子節點的最小值決定，因此在我們搜索 的m個子節點 的時候，如果搜索到第k個子節點的時候，其子節點的Value 已經小於第L層當前最大的Value值 的時候，那麼就不用繼續搜索k+1個子節點之後的子樹了，因為我們知道 。同理可得在搜索對手的極值的時候，也可以用類似的方法來剪枝。只是最小值變成了最大值。

可以看到，即使加上一些剪枝和規則判斷的過程，Minimax搜索的過程效率還是不高的。並且Minimax搜索也不能應用到一些非完全信息博弈遊戲（如撲克，橋牌）和非確定性的遊戲（如大富翁，雙陸棋）上。到了2007年的時候，一種新的樹搜索方法被發明和應用到遊戲中：蒙特卡洛樹搜索 Monte Carlo Tree Search(MCTS) ，並取得了極大的成功。

和minimax搜索相比，雖然也同樣缺乏對於狀態的評估函數，但是MCTS通過對不同的子樹給予不同的搜索次數和深度來解決樹的分支過多的問題。其本質的思想是，在搜索樹的某個節點上，通過快速走子(Roll Out)的方式來快速走到終局，從而得到關於該節點的是否能獲勝的一點信息，然後基於此信息來修正當前的搜索策略，來決定是否要提高還是降低該節點的權重。這樣就規避了要定義一個比較好的State Evaluation的函數的問題，事實上，對於一般的MCTS來說，只有兩個信息是需要的：遊戲的規則（定義怎麼走子和合法動作） 和 終局狀態（定義遊戲結束的狀態）,其起始狀態是根節點，然後隨著演算法的運行，不斷的Expand新的節點。通常MCTS是由四個步驟組成的：

Selection: 在這一步中，MCTS從根節點出發，選取一個Score值最大的子節點，直到該子節點有Child Node都沒有在之前被訪問過。這個Score的定義可以有很多不同的方式，最經典的UCB公式： , 其中 是當前Node的所有子節點的平均Reward，這個reward是每次探索的時候都可以通過Back-propagation得到的, n 是該節點的父節點的訪問次數， 是該節點的訪問次數， 是一個固定的係數，控制MCTS探索的權重。可以看到，當 趨近於0的時候，整個MCTS就傾向於已經探索過的節點的收益(Exploitation); 反之，那些很少被訪問過的節點的Score會變得更高，也更傾向於探索(Exploration)。

Expansion: 當MCTS到達一個節點，其有沒有訪問過的子節點,MCTS就進入了Expansion狀態。在該步驟下，MCTS隨機選取一個新的子節點加入到已有的搜索樹中。

Simulation(Roll Out): 然後，MCTS在這個新的子節點下，使用現有的策略來快速的走到終局，得到一個終局的結果（輸或者贏或者一個值）。

Back-propagation: 最後，這個值會作為這些新加入節點的當前Reward, 這Reward同時會向上傳遞，添加到它的父節點，祖父節點，一直到根節點上。

可以看到，在Roll-Out的時候，通過隨機的從某個子節點往下走子，實際上在次數足夠多的情況下，是對該節點對應的狀態的好壞的一種無偏估計。因此對於像棋牌類遊戲這些有很明確的終局狀態的遊戲，都很適合用MCTS來做。但是對很多遊戲（類似吃豆人遊戲來說，很難說有一個比較明確的終局狀態，或者到達終局狀態的深度很深。因此，我們還是要限制樹的深度，然後類似Minimax樹一樣，用一個State Evaluation的Function來返回估計的當前節點會導致的終局情況。