你應該了解的AI演算法，樹搜索和演化演算法

作者：蘇博覽  騰訊IEG高級研究員

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

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

在遊戲業界常用的搜索演算法是基於"樹搜索"的, 其本質都是構建一顆搜索樹，其節點(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*演算法中，從當前的節點 S可以通過選擇不同的動作來進入不同的狀態：

（

S

′1

,

S

′2

,...,

S

′n

)

.那麼選擇不同狀態的cost由當前狀態到下一狀態的距離

dis(S,

S

′i

)

和下一狀態到目標的距離

dis(

S

′i

,G)

決定。然後AI會選擇cost最低的一個動作來進入對應的新的狀態。在這上面，怎麼定義距離，以及怎麼組合這兩個距離都是可以作文章的地方。

A* Planner演算法贏得了2009年馬里奧AI大賽的冠軍，圖中的紅線表示可能的路線

很自然的，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)應用的非常廣泛。

一個簡單的Minmax樹的例子，紅色的是玩家行動節點，藍色是對手行動節點

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

defminimax(node,acting_player)ifnode is terminal:#Leaf nodereturnnode.valueifacting_player==opponent:#Mininum Node v=MAX_VALUEforchildinnode.childs:v=min(v,minimax(child,player))ifaction_player==player:#Maximum Node v=MIN_VALUEforchildinnode.childs:v=max(v,minimax(child,opponent))returnv

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

另外一個提高搜索效率的方法是alpha-beta剪枝，從演算法原理上來說，當我們在博弈樹第L層（輪到玩家行動）的時候，我們需要搜索玩家可能的N個動作節點

(Nod

e

1

,Nod

e

2

,...,Nod

e

n

)

的時候，如果我們在搜索前t個Node的時候，可以得到當前最大的Value值

α=max(V(Nod

e

1

),V(Nod

e

2

),...,V(Nod

e

n

))

,那麼在搜索

Nod

e

t+1

的時候，因為該節點的Value值由其子節點的最小值決定，因此在我們搜索

Nod

e

t+1

的m個子節點

(Chil

d

Nod

e

t+1

1

,Chil

d

Nod

e

t+1

2

,...,Chil

d

Nod

e

t+1

m

)

的時候，如果搜索到第k個子節點的時候，其子節點的Value 已經小於第L層當前最大的Value值

α

的時候，那麼就不用繼續搜索k+1個子節點之後的子樹了，因為我們知道

V(Nod

e

t+1

)=min(Chil

d

Nod

e

t+1

1

,...,Chil

d

Nod

e

t+1

m

)?V(Chil

d

Nod

e

t+1

k

)

。同理可得在搜索對手的極值的時候，也可以用類似的方法來剪枝。只是最小值變成了最大值。

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

MCTS的四個步驟

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

Selection:在這一步中，MCTS從根節點出發，選取一個Score值最大的子節點，直到該子節點有Child Node都沒有在之前被訪問過。這個Score的定義可以有很多不同的方式，最經典的UCB公式：

UCB1=

ˉX

j

+2

C

p

√

2ln(n)

n

j

, 其中

ˉX

j

是當前Node的所有子節點的平均Reward，這個reward是每次探索的時候都可以通過Back-propagation得到的, n 是該節點的父節點的訪問次數，

n

j

是該節點的訪問次數，

C

p

是一個固定的係數，控制MCTS探索的權重。可以看到，當

C

p

趨近於0的時候，整個MCTS就傾向於已經探索過的節點的收益(Exploitation); 反之，那些很少被訪問過的節點的Score會變得更高，也更傾向於探索(Exploration)。

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

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

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

一個MCTS 在 吃豆人上的應用（Maastricht MCTS Controller)

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

前面講到，樹搜索演算法是從初始狀態開始，基於合法的動作來生成一顆樹，樹的葉子節點是終止狀態，然後通過搜索，來找到一條最佳的從初始狀態到終止狀態的路徑。而優化演算法(optimization algorithm)則是基於任務來構造一個目標函數(Objective function），然後在整個解法空間中，來尋找一個可以最大化目標函數的效用（Utility)的策略(Strategy)。

一. Local Search: 爬山演算法和模擬退火

Local Search 是其中最簡單的一種優化演算法，顧名思義，假設一個solution是N維向量，那麼當前給定一個solutions（N維空間上的一個點）, 我們就在s附近的區間內尋找一個更好的解法s1 ,然後再從s1出發尋找下一個解法。Local Search在每一代都只保留一個解法，每次都從該解法出發去找尋下一個解法。這個方式其實有點像爬山的過程，因此又叫hill climber演算法。但是如下圖所示，這個演算法很可能會終止在一個local maximum裡面。

一維 Hill Climber演算法，從當前的狀態出發往更好的狀態轉移（通常是基於梯度的方向），但是到達了一個local maximumn或者半山腰的時候，會發現沒法繼續找到更好的狀態。

為了解決Local Maximum的問題，人們參考突變(mutation)的思想設計了隨機爬山演算法(Randomized Hill Climber), 從當前的狀態s開始，不再是基於梯度的方式，而是隨機的改變s的某些維度來得到一個新的狀態s′，看是否能到達一個更好的狀態，這樣，上圖中的狀態就有機會向左邊轉變，然後跑到global maximum去。這個演算法還是要求突變後的狀態要比原理的狀態好，因此也不能保證一定能找到最優解。

另外一種方法是模擬退火演算法（Simulated Annealing）， 和爬山演算法相比，它的搜索過程引入了隨機因素。這個退火也是來自於對材料退火的原理。

模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。材料中的原子原來會停留在使內能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內能比原先更低的位置。https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

我們如果把一個解法(solution)看作空間中的一個原子，那麼「加熱」的過程相當於隨機的改變當前的解法，然後得到一個新的解法。這個時候我們就基於Metropolis準則來判斷是否接受新解法：1. 如果新的解法比原來的解法好，我們會接受該解法；2. 如果新的解法比原來的解法差，我們還是有一定的概率來接受新的解法。這個概率是由兩個參數決定的: 1. 兩個解法的Fitting Function的差值（「能量差」） 和 2. 當前的「溫度」（也即是演算法的迭代次數）。 因此如果兩個解法的差距不大，接受新解法的概率越大；在演算法迭代開始的時候，接受新解法的概率也更大一些。參考熱力學定律，在溫度為

T

時，出現能量差為

ΔU

的降溫的概率為

exp(?ΔU

/

T)

, 這個也是我們是否接受新解法的概率。整個模擬退火的偽代碼如下：

defsimulated_anneling():s=s0 #initial solution T=T0 #initial temperaturewhileT>Tmin andE(s)>Emax:s_n=random_new_state(s)#getanewstatebased on sifE(s_n)>E(s):#getthe"energy"(fitness score)ofsolution s=s_nelse:dE=abs(E(s_n)-E(s))ifrandom(,1)

模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S（是演算法迭代的起點）無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以概率1收斂於全局最優解的全局優化演算法；模擬退火演算法具有並行性。https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

演化演算法的例子：1和2 crossover 生成3 和4， 3突變生成6， 4突變生成5

二. 遺傳演算法(Genetic Algorithm)

而如果我們初始化的時候，不是只初始化一個種子，而是同時保留多個不同的solutions,同時更新。每次優化的時候，也不是只保留一個新的解法，而是丟掉比較差的演算法，但保留多個不同的解法，我們就得到了演化演算法的基本思路。

遺傳演算法（Genetic Algorithm，簡稱GA）是一種最基本的演化演算法(Evolutionary Algorithm)，它是模擬達爾文生物進化理論的一種優化模型，是全局的隨機優化演算法（Randomized Global Optimization Algorithms)。遺傳演算法中從一個或多個初始策略開始（稱為初代）, 每一代成為一個種群, 種群中每個個體都是解空間上的一個可行解，通過模擬生物的進化過程，隨機的改變部分策略（突變）或者隨機的合併多個策略（雜交）來得的新的策略（下一代），從而在解空間內搜索最優解。遺傳演算法一般是通過Utility Function(或者在演化演算法中通常叫Fitness Function)來保留當前更好的策略，而去除一些較差的策略（天擇），有些演算法還會隨機的消滅掉部分的策略，而不管它是不是當前比較好的策略（來模擬自然界中的災變，比如毀滅恐龍的小行星 和 打個響指的滅霸）。

應該很快某個演算法框架的某個模塊就叫Thanos了~~

在有些時候，我們的解法是有一定的限制(constraint)的，因此隨機的crossover和mutation可能都會產生很多的不合法的解法。但是如果我們給演化的過程增加限制，去除很多的不合法解法的話，很可能我們的演化演算法沒法找到一個很好的solution，因為初期大部分的演化solution都被殺死了。因此人們提出了feasible-infeasible 2-population(FI-2pop)演算法來緩解這個問題。在演化的過程中，演算法維護兩個隊列，一個隊列里只包含可用的解法（feasible),另一個隊列則沒有限制(infeasible)，只要infeasible的隊列中產生了可用解法(feasible solution)，這個解法就會放入feasible的隊列中。通過這樣的方式，FI-2pop找到不同的feasible solution的概率增大了。

三. 進化策略(Evolution Strategy)

在傳統的遺傳演算法中，一般是使用二進位編碼（DNA）來編碼種群中的個體的，這樣最大的好處是做crossover 和 Mutation特別方便，mutation 就是某個位置上的0變成1 或者 1變成0， crossover就可以簡單的定義為異或，或者隨機選取父輩對應位置的編碼就可以了。

但是在很多場景中，個體的特性不是固定的，而是服從某種分布的。比如人的能力，就不是一個固定值，而是會在一定的範圍內波動。通過我們假設這個分布是高斯分布，這樣我們就可以用均值和方差來表示這個分布了，因此和GA相比，進化策略(ES)的演算法表示是兩組實數值的編碼(DNA)，一組代表該維的均值，另一組代表方差。這樣在進化的時候(crossover 和 mutation)也和GA稍有不同，crossover相當於合併兩個高斯分布，通常可以考慮合併高斯分布的均值；mutation則可以改變高斯分布的方差。這個改變的幅度也可以用一個權重來控制。基於不同的合併策略，我們可以得到不同的ES的變種。

四. 多目標演化演算法

另一方面，演化演算法很可能是多目標的(multiobjective)，演化演算法要找到一個帕累托最優（Pareto Optimality)的solution,這個解法要滿足「不可能再改善某些目標的境況，而不使任何其他的目標受損」。通常來說這個解法不是唯一的。在遊戲AI的設計中，我們經常會碰到這樣的問題，比如在設計策略遊戲的過程中，我們希望設計各方的兵種是各有特色的，同時各方的實力又比較平衡的，這方面的比較好的例子有《星際爭霸》。

通常這樣的多目標的優化問題很難用數學的方法來進行優化，但是演化演算法在這上面比較有優勢。 因為演化演算法每代都隨機的全局搜索，可以產生多個候選的解，構成近似問題的Pareto最優解集；同時在種群中，不同的個體可以滿足不同類型的目標函數和約束。常用的多目標演化演算法有GA, 蟻群演算法等，這裡就不詳細的闡述了。

星際爭霸最大的不平衡點

五. 神經進化演算法（Neuroevolution）

前面幾篇文章分別討論了不同類型的AI演算法。但是在實際應用中，我們經常會把不同的AI技術混在一起使用，以期獲得更好的效果。例如，我們可以用演化演算法(GA)來學習行為樹的參數，我們也可以像Deepmind那樣用神經網路來對MCTS做更有效的剪枝(Pruning)。我們通常稱這樣的演算法為混合演算法(Hybrid algorithm)。這裡把神經網路和演化演算法結合的混合演算法就叫做：Neuroevolution。

神經演化演算法（Neuroevolution）主要是用演化學習的思想來調整神經網路的結構和權重。通常我們是用梯度下降的方法來更新神經網路的結構，但是如果我們不能很好的用監督學習的方法來訓練神經網路的時候（例如訓練的神經網路的loss function沒法微分(differentiable)，或者我們沒有一個很好的標註的訓練樣本），這個時候我們就要考慮演化學習的框架了。這個在遊戲AI中經常能夠遇到，比如我們很難定義一個行為是不是好的（如王者榮耀中，一個英雄在某個場景中使用某個技能是好的還是壞的）。而在演化學習的框架下，我們只需要考慮一個對Solution（某個訓練好的神經網路）的度量（fitness function)。其中基於NEAT演算法(NeuroEvolution of Augmenting Topologies增強拓撲的神經網路進化), 人們開發了可以玩馬里奧的AI，具體的代碼實現可以看下面的鏈接。

Mar I/O : AI玩轉馬里奧

當然，演化學習需要在每一代都保留多個可用的模型，然後在隨機進行crossover 或者 mutation。可想而知，這是一件非常耗費計算能力的事情，所以目前為止能得到的網路規模也不大、完成的任務也不夠複雜。不過去年底的時候， Uber AI Lab一連發了5篇文章來證明Neuroevolution 也可以高效的訓練大規模的神經網路。這裡就不具體的描述其演算法啦，有興趣的可以到Uber 公開的Github去看它的源碼和論文。

本文來自《遊戲人工智慧》 讀書筆記，作者：蘇博覽

作者： fled

本文內容包含以下章節：

Chapter 2 AI Methods

Chapter 2.3 Tree Search

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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！