蒙特卡洛樹搜索 MCTS 入門

引言

??你如果是第一次聽到蒙特卡洛，可能會認為這是一個人名，那么你就大錯特錯，蒙特卡洛不是一個人名，而是一個地方，還一個賭場名！！！但是這不是我們的重點，

??我們今天的主題就是入門蒙特卡洛樹搜索，這個演算法我個人覺得非常神奇也非常有意思，因為前幾年 AlphaGo 就是借助蒙塔卡洛樹搜索以及基于深度學習的的策略價值網路擊敗了人類冠軍，贏得了勝利，而今天我們的主角就是蒙特卡洛樹搜索它究竟是怎么實作的？它的原理？以及會舉出一個例子來告訴大家整個演算法的作業流程，

一、什么是 MCTS？

??蒙特卡洛樹搜索是一類樹搜索演算法的統稱，簡稱 MCTS（ Monte Carlo Tree Search），它是一種用于某些決策程序的啟發式搜索演算法，且在搜索空間巨大的游戲中會比較有效，那什么叫做搜索空間巨大呢？比如說，在上世紀90年代，IBM公司推出深藍這個 AI，擊敗了當時國際象棋的世界冠軍，而這個 AI 也比較簡單粗暴，把整個國際象棋的搜索空間全部窮舉出來，把整個游戲樹全部列舉出來，那么不管對手下什么，它都知道下一步怎么下可以把他下贏，而對于圍棋這種游戲，圍棋棋盤是 19*19 的，也就是說有 361 個落子的位置，那么如果我們想把所有圍棋的棋局的可能列舉出來，一般來說就是 361！，這個數量是比宇宙的原子數量還要多的，就算是世界上最強的超級計算機也無法把所有的可能性窮舉出來，那么我們就需要用到類似于蒙特卡洛樹搜索這樣的稍微智能一點，更可行的辦法去對圍棋這個游戲可以進行棋盤式的搜索，然后進行決策，最后下贏人類選手，

??從全域來看，蒙塔卡洛樹搜索的主要目標是：給定一個游戲狀態來選擇最佳的下一步，

??MCTS 受到關注主要是由計算機圍棋程式的成功以及潛在的眾多難題上的應用所致，超越博弈游戲本身，MCTS 理論上可以被用在以（狀態 state，行動 action）對定義和用模擬進行預測輸出結果的任何領域，

??常見應用包括 Alpha Go，象棋或圍棋 AI 程式等等，

二、演算法程序

演算法程序一般有四步：

• 選擇（Selection）：選擇能夠最大化 UCB 值的結點
  
• 擴展（Node Expansion）：創建一個或多個子結點
• 仿真（Simulation）：在某一結點用隨機策略進行游戲，又稱 playout 或 rollout
• 反向傳播（Backpropagation）：使用隨機搜索的結果來更新整個搜索樹

??在完成了反向傳播這一步，我們就會持續迭代，回到選擇這一步，然后再進行擴展仿真，然后再反向傳播，再回到選擇擴展仿真，不斷地迭代下去，直到演算法結束并且給出最終決策，

??下面，我將用一個流程圖簡單展示一下上面四個步驟：

當然你可能看上面的流程圖會有點迷，不要慌，下面我用一個中文流程圖展示一下整個演算法的流程，

??整個演算法程序是這樣的，一開始，我們會找到根節點 S0，代表目前的游戲的一個狀態，那么接下來判斷它是否是葉節點，如果它不是葉節點，是一個中間節點的話，我們就計算出該結點下面的所有子結點的 UCB 值并且找到 UCB 值最大的子結點，然后將這個 UCB 最大值的子結點當作當前節點進行下一步迭代，繼續判斷當前結點是否是葉節點，若它還不是葉節點，我們就在這個結點下面計算它的所有子節點的 UCB 值并找出最大的結點當作當前結點繼續進行迭代，直到找出一個結點是葉節點，我們就判斷該節點的 n（探索的次數） 是否為 0，如果它的探索次數為 0，那么就代表該結點是沒有被探索過的，那么我們就進行 ROLLOUT，如果不是 0，我們就列舉出當前結點所有的動作，并添加到樹中，這一步相當于是 Node Expansion，然后我們將第一個新結點作為當前結點，然后進行 ROLLOUT，

下面我將對演算法的四個步驟做進一步的論述，

1. 選擇（selection）

下面我對選擇中 UCB 公式中的各項做一個解釋，

• Vi：該結點下的平均 Value 大小，比如說，好的一步它的 Value 更大一些，差的一步相對來說要小一些
• c ：常數，通常可以取 2，相當于是加號兩邊式子的一個權重
• N：總探索次數，就是對所有的結點一共 explore 了多少次
• ni：當前結點的探索次數

2. 擴展（Node Expansion）

下面通過一個例子來說明，

??比如我們從根節點出發，它不是葉子節點，之后計算它的兩個子節點的 UCB 值，比如說結點 3 的 UCB 值更大，但是它之前已經被訪問過了，根據我們之前的流程圖，該節點不會直接進行 ROLLOUT，而是列舉出當前節點所有可能的動作并添加到樹中，那么我們列舉出了結點 3 可能有兩個動作，所以形成了圖(2)，然后接下來我們再看我們要采取哪種動作，這就是 Node Expansion，

3. 仿真（Rollout）

??接著上面一步，根據我們的流程圖，會將第一個新結點（結點 4）作為當前結點，會對它進行一個 Rollout，

??那么這個 rollout 怎么做呢？它會進行一個隨機檢測，下面我用一段偽代碼來表示 rollout 程序：

def Rollout(S_i): # S_i：當前狀態
	loop forever: # 無限回圈
		if S_i a terimal state: # 如果當前狀態是個終止狀態，比如說你贏了或者他贏了
			return value(S_i)   # 回傳對 S_i 這個狀態的價值，比如說你贏了，這個價值可能就會相對比較高
		
		# 假設還沒到終止狀態
		A_i = random(available_action(S_i)) # 隨機選取當前狀態下能夠采取的一個動作
		S_i = simulate(A_i, S_i)   # 通過當前狀態 S_i 與隨機選取的動作 A_i 來計算出下一步的狀態并賦值給 S_i

??下面我再用圖示進行說明，

??來看下面這張圖，假設我們從黃色節點 1 進行 Rollout，它隨機決策到結點 2，然后再隨即決策到結點 3，然后在隨機決策一直到最后紅色結點 7，該節點的狀態是 terminal state，然后得到一個 value，然后再將 value 回傳給黃色節點 1，

??這一步其實也是蒙克卡羅樹搜索的非常重要的一關，因為這一步很像是在用隨機的方法去逼近整體的一個分布，你想，如果黃色節點 1 代表的是更好的一個動作的話，那么贏的概率就會更大一點，經過很多次的仿真，都會得到一個比較大的概率值，如果它是一個不好的策略，那么經過很多次的仿真，大概率是不會得到一個很好的概率，

4. 反向傳播（Backpropagation）

??在完成了 Selection，Expansion 和 Rollout 之后，我們再進行 Backpropagation，它是做什么的呢？

??在 Rollout 中我們計算出了 value 之后，我們需要回傳這個 value，那么對于它所有的父節點（下圖黑線上的所有的結點），它們的探索次數全部 +1，它們的 value 也會進行一個累加，然后我們整個演算法會 repeate 很多次，直到蒙特卡洛樹能夠給出當前狀態下最好的一個解答，就是我到底應該怎么走，

??那么四個步驟到此就結束了，但是之前提到過這個演算法會一直進行迭代，那么這個演算法到底什么時候結束？

演算法何時終結？

??一般的方法比如說游戲內棋手的限制時間，比如說，像圍棋，國際象棋，在比賽當中每個棋手的時間都是有限制的，但是如果你用電腦肯定就有無限的時間，你可以將其全部窮舉出來，但是這樣是沒有意義的，所以我覺得一個 AI 能夠在規定時間內，尤其是時間越少越好，能夠在更少的時間內做出更好的決策說明這個機器才更加的智能，如果給你無限的時間來做出一個決策，你可以暴力窮舉出所有的可能性，其實就說明這個 AI 沒有那么智能，所以一般來說我們會在規定時間范圍內終結演算法的迭代，然后給出最優的一個解答，下一步應該怎么走，然后再讓對面去下棋，對面下完之后，你再進行一個搜索在規定時間內給出一個最優的，

??還有一種就是固定迭代的次數，比如說，第一個 AI 迭代了 5000 次得到了一個比較好的結果，另一個 AI 用了 50 次就迭代出了一個比較好的結果，那么就基本認定第二個 AI 相對來說是比較智能的，所以我們也可以給出一個固定的迭代次數，比如說你算到 5000 次迭代就讓蒙特卡洛樹搜索停下來給出一個決策，

??至于怎么給出一個決策呢？很簡單，在迭代完成后，選擇 value 更大的結點即可完成決策，

舉例說明

??下面舉出一個例子來詳細說明蒙特卡洛樹搜索的程序，

??首先我們有一個根節點，S_0，它有兩個屬性值 T_0（價值），N_0（迭代的次數），

??那么我們首先先判斷 S_0 是否是葉節點，它確實是一個葉節點，我們需要對它進行一個 Node Expansion，我們發現有兩種策略可以采取分別為 S_1 和 S_2，

??在這里，我們可以直接選擇 S_1 作為當前節點，也可以通過 UCB 公式計算一下 S_1 和 S_2 的 UCB 值，并選取其中 UCB 值較大的節點作為當前節點，下面我們在列出 UCB 的公式：

??可以發現 S_1 和 S_2 的 ni 都是 0，那么對于 S_1 和 S_2 來說，它們的 UCB 值都是無窮大，所以選擇誰都是一樣的，那么我就根據我上面畫的流程圖，選擇第一個新結點作為當前節點，即 S_1，

??然后我們發現 S_1 的 n_1（探索次數）為 0，即它沒有被探索過，根據之前的流程圖就應該進行 Rollout，

??結果我們發現 value = 20，在 Rollout 完成之后，我們對 S_1 進行 Backpropagation，將 S_1 的 T_1 更新為 20，n_1 更新為 1，然后再反向傳播到它的父節點 S_0，并更新S_0 的 T_0 為 20，N_0 為 1，那么就完成了第一輪迭代，

??每一次迭代，都需要從根節點開始，所以到了第二輪迭代，我們同樣首先判斷 S_0 是否是葉節點，S_0 不是葉節點，然后我們使用 UCB 對它進行一個 Selection，選擇下一個節點，S_1 的迭代次數為 1，而 S_2 的迭代次數還是 0，所以 S_2 的 UCB 還是無窮大，所以下一個節點選擇 S_2，然后判斷 S_2 是否是葉節點，它是葉節點，并且還未被探索過，那么直接對 S_2 進行 Rollout，然后我們得到 value = 10，然后進行 Backprppagation，更新 S_2 的 T_2 為 10， n_2 為 1，然后更新 S_2 的父節點 S_0，將 S_0 的 T_0 更新為 30（20+10），N_0 為 2（1+1），那么就完成了第二次迭代，

??接下來，我們繼續迭代，我們還是從 S_0 開始，它不是葉節點，然后計算 S_1 和 S_2 的 UCB 值，

??因為 S_1 的 UCB 大于 S_2，所以我們選擇 S_1，S_1 是一個葉節點，并且它的探測次數不為 0，那么我們就列舉出當前節點所有可能的動作，并添加到樹中，即 Node Expansion，那么假設 S_1 也有兩個動作 S_3 和 S_4，

??因為 S_3 和 S_4 它們的探索次數都為 0，所以 UCB 都為無窮大，所以我們還是選擇第一個新結點 S_3 作為當前節點，然后對 S_3 進行 Rollout，最終我們得到的 value = 0，然后對它進行一個反向傳播，更新 S_3 的 T_3 為 0，n_3 為 1，更新 S_1 的 n_1 為 2，T_1 不變，更新 S_0 的 N_0 為 3，T_0 不變，這就是我們的第三次迭代，

??然后我們進入第四次迭代，還是從 S_0 開始，它不是葉節點，然后根據 UCB 公式計算我們選擇 S_1 還是 S_2，此時我們需要注意的是，在 UCB 公式中，Vi 是 value 的平均值，所以在 S_1 中，S_1 已經被探索了 2 次，所以 S_1 的平均 value 為 10（20/2=10），那么 S_1 和 S_2 的 UCB 計算如下：

??所以我們下一個節點選取 S_2，S_2 為葉節點，而且已經被探索過了，所以需要列舉出所有的動作并添加到樹中，還是假設 S_2 有 2 個動作 S_5 和 S_6，然后我們選擇 S_5 對其進行 Rollout，得到 value = 15，然后依次更新 S_5，S_2, S_6 相應的 T 和 n，然后又完成了一次迭代，

??假如我們現在就停止迭代，那么我們看一下我們究竟應該選 S_1 還是 S_2，很明顯，S_2 的 T_2 （value）會更大一些，所以說我們通常會選擇 S_2，也就是做第二個動作，是目前這個樹當中最優的解，

??那么，關于 UCB 公式還有幾個需要注意的點，如果說 Vi 越大，那么 UCB 相應的也是越大的，而 UCB 越大代表越有可能選擇這條路徑，Vi 越大代表這個節點平均的價值會更高，我們就更愿意去搜索它，但是如果說只有 Vi 可不可以呢？比如將 UCB 公式變成這樣：

??當然不行，如果這樣的話那些沒有被探索過的節點就永遠不會被探索，這就是為什么會有右邊這一項，特別是當 ni 等于 0 的時候，UCB 會等于無窮大，那么就一定會去探索這個沒有被探索過的節點，那么隨著 N 的一些變化，相應的 UCB 也會跟著變化，總之，這個 UCB 公式既保證了探索了的分支可以再次被探索，又保證了我們盡量去探索那些價值更大的那些路徑然后讓我們能夠更好的完成整個游戲，

??以上就是我對蒙特卡洛樹搜索的初步理解，如有錯誤，還請指正~~