蒙特卡羅樹搜索之初學者指南

蒙特卡羅樹搜索之初學者指南

來自專欄 我是程序員

摘要： 一直以來，學術界普遍認為在圍棋遊戲中機器是遠不能和人類相比的，它被認為是未來十年內人工智慧需要實現的目標之一。令人驚訝的是，在2016年3月由谷歌發明的Alpha Go以4-1擊敗了韓國的世界冠軍。

介紹

蒙特卡羅樹搜索由RémiCoulom於2006年作為Crazy Stone的一個組成部分引入，令人印象深刻的是其出色的引擎的能力，同時也是Alpha Go / Zero的核心組件。蒙特卡羅樹搜索主要目的是：給出一個狀態來選擇最佳的下一步。我們回顧AlphaGo / Zero，試圖解釋在Alpha Go中使用了哪些蒙特卡羅樹搜索變體。

兩人有限零和順序遊戲

在該環境下，蒙特卡羅樹搜索內運行的是一個遊戲，其本身是一個很抽象、很廣義的術語，因此在這裡我們專註於單一遊戲類型：二人有限零和順序博弈。把它分解成以下幾個部分：

1.遊戲意味著需要處理互動的情況，一些參與者（一個或多個）。

2.「有限」一詞表明，在任何時間點，參與者之間存在有限的交互方式。

3.兩人博弈意味著兩個參與者參與了我們的遊戲。

4.連續的，因為參與者交替地移動他們的動作。

5.最後，零和遊戲意味著雙方都有相反的目標，換句話說：在遊戲的任何終端狀態，所有玩家的收益總和等於零。

圍棋、象棋或井字棋都是兩人有限零和順序遊戲。事實上，有兩個人參與，總是有限的動作，並且兩個參與者的目標是完全相反的（所有遊戲的結果總和為零）。

如何表示遊戲？

形式上，遊戲由一些基本的數學實體表示。在博弈理論書中，你可以找到以下定義：

定義1.一個廣泛的表單遊戲由一個元組定義：

從計算機程序員的角度來看，一個正式的定義可能有點混亂。幸運的是，我們可以使用一個眾所周知的數據結構來簡化表示為：一個遊戲樹。

遊戲樹是一個樹，其中每一個節點代表遊戲的某些狀態。從節點到其子節點（如果存在）的轉換是一個移動。節點的子節點的數目稱為分支因子，樹的根節點代表遊戲的初始狀態。如果遊戲樹的終端節點沒有子節點，遊戲就不能繼續了。讓我們試著描述（部分）看到的井字遊戲樹：

1.在頂部，你可以看到樹的根部，代表井字遊戲的初始狀態，空白紙板（標記為綠色）。

2.從一個節點到另一個節點的任何轉換都表示一個移動。

3.井字遊戲的分支因素各不相同- 它取決於樹的深度。

4.遊戲結束於終端節點（標記為紅色）。

遊戲樹是一個遞歸數據結構，所以在選擇最佳移動後，最終會在子節點中實現，而子節點實際上是其子樹的根節點。因此，你可以把一個遊戲看作是一個「最佳的下一步」序列的代表，每次都有一個遊戲樹（不同的根節點）。通常在實踐中，你不必記住通往當前狀態的路徑，因為它不是當前遊戲狀態中的關注點。

什麼是最佳的下一步？

我們的最終目標是在給定遊戲狀態和遊戲樹暗示的情況下找到最佳的下一步行動。我們假設在國際象棋中，你知道你的對手是一個業餘愛好者，你可以選擇簡單的策略來欺騙他並迅速獲勝。但是，針對強大對手的時候採用相同策略會對你產生不利影響。如果你根本不了解你的對手，那麼有一個非常激進的策略叫做minimax，假設你的對手很厲害，那麼這個策略可以得到最大化效果。在A和B之間的兩人有限零和序貫博弈時，minimax

演算法可以用下面的遞歸公式來描述：

簡單地說，假設你的對手試圖最大限度地限制你，而你利用minimax演算法將會產生最大的回報，這也是minimax演算法的由來。我們需要的只是擴展整個遊戲樹，並根據遞歸公式給出的規則來反向傳播。

minimax演算法的最大弱點是擴展整個遊戲樹的必要性，對於具有高度分支因素的遊戲（如圍棋或象棋），它會產生巨大的遊戲樹並導致失敗。

有沒有補救辦法呢？

接下來我介紹兩種方法，一種方法是將我們的遊戲樹擴展到一定的閾值深度D。但是，我們不能保證閾值樹級別D中的任何節點都是終端。因此，我們需要一個函數來評估一個非終端遊戲狀態。這對人類來說是很自然的：通過看國際象棋或圍棋，即使遊戲仍在繼續，你也能預測贏家。例如：

克服遊戲樹大小問題的另一種方法是通過alpha-beta修剪演算法修剪遊戲樹。Alpha-beta修剪演算法以minimax方式遍歷遊戲樹，避免某些樹枝的擴展。結果最多與minimax相同，但alpha-beta修剪演算法通過減少搜索空間來保證改進。

蒙特卡羅樹搜索- 基本概念

蒙特卡羅樹搜索的主要概念是搜索。搜索是一組沿著遊戲樹的遍歷，單次遍歷是從根節點（當前遊戲狀態）到未完全展開的節點的路徑。未完全展開的節點意味著至少有一個子節點未被訪問，而沒有被探索。遇到未完全展開的節點時，其子節點不會選擇成為一個根節點。然後將模擬結果反向傳播到當前遊戲樹節點以統計數據。一旦搜索（受時間或計算能力限制）終止，則根據收集的統計信息選擇移動。

讓我們試著接著上面簡單描述的關鍵問題，以便慢慢理解所有的部分：

1.什麼是擴展或不完全擴展的遊戲樹節點？

2.在搜索過程中，下一個（子）節點如何選擇？

3.什麼是模擬？

4.什麼是反向傳播？

5.在擴展的遊戲樹節點中傳播和更新哪些統計數據？

6.最後的移動如何選擇？

模擬

我們首先關注模擬，因為它不會嚴重依賴其他術語的定義。模擬是一種單一的遊戲行為，是一系列從當前節點開始，並終止於可計算遊戲結果的終端節點的動作序列。模擬是通過在該節點處開始以某種方式隨機遊戲來計算的遊戲樹節點評估近似值。在模擬過程中如何選擇動作？在模擬過程中，選擇一個稱為「轉出策略」的函數：

它消耗一個遊戲狀態併產生下一個移動/動作。在實踐中，它被設計成能夠快速地模擬，默認的轉出策略函數是一個統一的隨機函數。

最簡單形式的模擬只是隨機的一系列動作，從給定的遊戲狀態開始並終止。模擬對於我們所談論的遊戲來說總是會產生一個評估，勝利、失敗或平局，通常任何結果都是模擬的合法結果。

擴展或不完全擴展的遊戲樹節點

給定一個根節點加上遊戲規則，我們可以遍歷它，而不需要將整個樹存儲在內存中。在最初的形式中，它根本沒有擴展並且處於遊戲樹的根部，其餘節點未被訪問。一旦我們考慮到一個動作，就會想像這個動作會產生什麼樣的結果。

蒙特卡羅樹搜索遊戲樹也有同樣的區別。節點被視為訪問或未訪問，對於要訪問的節點意味著如果一個節點的所有子節點都被訪問，則節點被認為是完全擴展的，否則它沒有完全擴展，但是可能會進一步擴展。

在實踐中，一旦搜索開始，所有的根節點都未被訪問。如果其中一個被選中，第一個模擬立即開始。請注意，在模擬過程中，由轉出策略函數選擇的節點不被考慮訪問。它們是未經許可的，只有模擬開始的節點被標記為已訪問過。

反向傳播

一旦完成了一個葉節點的模擬，其結果已準備好傳播回當前的遊戲樹根節點，然後模擬開始的節點被標記為已訪問。

反向傳播是從葉節點（模擬開始）到根節點的遍歷。模擬結果被傳送到根節點，並且對於反向傳播路徑上的每個節點更新某些統計信息。反向傳播保證每個節點的統計數據反映在其所有後代中開始的模擬結果（因為模擬結果被傳送到遊戲樹根節點）。

遊戲樹遍歷

在搜索的一開始，由於我們還沒有開始任何模擬，所以首先選擇未訪問的節點。單個模擬從根節點開始遍歷到葉節點，結果又反向傳播到根節點，然後根節點被認為完全展開。

當前的節點標記為藍色，並且已完全展開，它必須存儲其節點統計信息：總體模擬結果和總訪問次數。這同樣適用於其子節點。

終止蒙特卡羅樹搜索

我們現在知道成功實施蒙特卡羅樹搜索所需的所有條件，但我們什麼時候才能真正結束蒙特卡羅樹搜索程序？答案是：它取決於上下文。如果你構建了一個遊戲引擎，那麼你的「思考時間」可能是有限的，再加上計算機的計算能力也有限制。一旦蒙特卡羅樹搜索程序完成，最好的移動通常是訪問次數N最多的移動，因為它的估計價值最高（經常被探索）。

在使用蒙特卡羅樹搜索選擇你的移動後，你所選擇的節點將成為你的對手移動的遊戲狀態。一旦他選擇了他的移動，你將再次開始蒙特卡羅樹搜索程序。之前蒙特卡羅樹搜索產生的一些統計數據可能仍然存在於你正在考慮的新分支中。這帶來了重新使用統計數據而不是從頭開始構建新樹的想法，事實上這也是Alpha Go / Alpha Zero的創建者所做的。

以上為譯文。

譯文鏈接

文章原標題《Monte Carlo Tree Search – beginners guide》

譯者：黃小凡，審校：袁虎。

文章為簡譯，更為詳細的內容，請查看原文。

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎

推薦閱讀：