AlphaGo背後的力量：蒙特卡洛樹搜索入門指南

我們都知道 DeepMind 的圍棋程序 AlphaGo，以及它超越人類的強大能力，也經常會聽到「蒙特卡洛樹搜索」這個概念。事實上，蒙特卡洛樹搜索是在完美信息博弈場景中進行決策的一種通用技術，除遊戲之外，它還在很多現實世界的應用中有著廣闊前景。本文中，我們會以 AlphaGo 為例子，對這一方法進行詳細介紹。文章選自int8 Blog，機器之心編譯。

長久以來，學術世界一直認為計算機在圍棋這個複雜遊戲上達到超越人類的水平是幾乎無法實現的。它被視為人工智慧的「聖杯」——一個我們原本希望在未來十年挑戰的遙遠里程碑。在國際象棋上，「深藍」曾在 20 多年前實現了自己的目標，而其後數年，沒有一個圍棋引擎能夠打敗人類頂尖棋手。圍棋及其引發的「數字混沌」是如此令人著迷，以至於人們一度將其想像為人類「對抗」計算機的最後壁壘。

然而正如我們所知，2016 年 DeepMind 推出的人工智慧圍棋程序 AlphaGo 結束了這一局面，它在當年 3 月份的系列比賽中以 4：1 的比分擊敗了來自韓國的前世界冠軍李世石。AlphaGo 證明了世人對於虛擬和現實世界的懷疑是錯誤的。而在短短一年之後，新一代圍棋程序 AlphaGo Zero 在測試中就能夠以 100：0 的成績擊敗舊程序，這無疑宣告了人類在圍棋上和計算機的差距已經越來越遠。

作為今天最被人們所熟知的人工智慧系統（沒有之一），AlphaGo/Zero 是一個多種計算方法的集合體，人類工程學的傑作，其核心組件包含：

• 蒙特卡洛樹搜索——內含用於樹遍歷的 PUCT 函數的某些變體
• 殘差卷積神經網路——其中的策略和價值網路被用於評估棋局，以進行下一步落子位置的先驗概率估算。
• 強化學習——通過自我對弈進行神經網路訓練

在本文中，我們只著重於介紹蒙特卡洛樹搜索（MCTS/Monte Carlo Tree Search）。這個演算法很容易理解，而且也在遊戲人工智慧領域外有很多應用。

目錄

1 介紹

1.1 有限兩人零和回合制遊戲

1.2 如何表徵一個遊戲

1.3 什麼是最有潛力的下一步？簡要介紹極小極大（minimax）演算法和 alpha-beta 修剪演算法

2 蒙特卡洛樹搜索——基本概念

2.1 模擬——AlphaGo 和 AlphaZero

2.2 博弈樹的展開節點、完全展開節點和訪問節點

2.3 反向傳播：將模擬結果傳播回去

2.4 關於節點的統計學

2.5 博弈樹遍歷

2.6 樹的置信上限

2.7 終止蒙特卡洛樹搜索

3 總結

介紹

蒙特卡洛樹搜索是由前里爾第三大學助理教授 Rémi Coulom 在圍棋程序 Crazy Stone 中首先引入的方法——後者是第一個在圍棋上達到職業五段水平的計算機程序。

從最直觀的角度來看，蒙特卡洛樹搜索有一個主要目的：給出一個「遊戲狀態」並選擇「勝率最高的下一步」。在本文中，我會試圖解釋蒙特卡洛樹搜索的大多數細節，其中我們也會不時回顧 AlphaGo/Zero，並試圖解釋那些在 DeepMind AI 程序系列中使用的 MCTS 變體。

有限兩人零和回合制遊戲

蒙特卡洛樹搜索運行的框架/環境是「遊戲」，其本身是一個非常抽象的廣義術語，所以在這裡我們只針對於一種遊戲類型：有限兩人零和回合制遊戲——這聽起來或許有點複雜，不過其實很簡單，讓我們來分析一下：

• 「遊戲」意味著處理「互動情況」。互動意味著有玩家會參與進來（一個或多個）
• 「有限」表示在任何時間點上，玩家之間都有有限的互動
• 「兩人」有限遊戲，顧名思義
• 「回合制」表示玩家按照一定順序進行遊戲——輪流出招
• 最後「零和遊戲」——這意味著遊戲雙方有著相反的目標，換句話說：在遊戲的任何終結狀態下，所有玩家獲得的總和等於零。有時這樣的遊戲也被稱為嚴格競爭博弈

我們可以輕易驗證圍棋、國際象棋或井字棋是有限兩人零和回合制遊戲。的確，它們都是兩個玩家，遊戲可選的下一步也是有限的，且遊戲是嚴格競爭的——兩名玩家會進行對抗（遊戲的所有輸出之和為零）。

Notes：請注意，為了簡化本教程，我們只專註於可能場景的某系子集，蒙特卡洛樹搜索是一個應用廣泛的工具，適用於兩人有限零和遊戲以外。更為全面的概述請參閱：http://mcts.ai/pubs/mcts-survey-master.pdf

如何表徵一個博弈

形式上，一個博弈由一系列的基本數學實體表徵。在一本 PhD 級別的博弈論書中你可以找到這樣的定義：

定義 1. 一個博弈的擴展式可以用一個多元組來定義：

從計算機編程的角度來看形式化的定義可能難以理解，但幸運的是，我們可以使用一種著名的數據結構以簡單的形式來表徵一個博弈：博弈樹。

博弈樹是一種樹結構，其中每一個節點表徵博弈的確定狀態。從一個節點向其子節點的轉換被稱為一個行動（move）。節點的子節點數目被稱為分支因子（branching factor）。樹的根節點表徵博弈的初始狀態。我們還區分了博弈樹的端節點（terminal nodes），即沒有子節點的節點，表示博弈無法再繼續進行。端節點的狀態可以被評估，並總結博弈的結果。

在上圖的井字棋博弈樹（部分展示）的例子中：

• 在頂部，你可以看到樹的根節點，其表徵了井字棋博弈的初始狀態，即空白棋盤（標記為綠色）；
• 任何從一個節點向另一個節點的轉換被稱為一個行動；
• 井字棋的分支因子是變化的，它依賴於樹的深度；
• 從一個根節點到一個端節點的樹遍歷表徵了單個博弈過程。

博弈樹是一種遞歸的數據結構，因此當你選擇了一個最佳行動併到達一個子節點的時候，這個子節點其實就是其子樹的根節點。因此，你可以在每一次（以不同的根節點開始），將博弈看成由博弈樹表徵的「尋找最有潛力的下一步行動」問題的序列。在實踐中很常見的是，你不需要記住到達當前狀態的路徑，因為它在當前的博弈狀態中並不重要。

什麼是最有潛力的下一步行動？簡要介紹極小極大（minimax）策略和 alpha-beta 剪枝演算法

再次提醒，我們的最終目標是在給定博弈狀態的前提下，利用博弈樹尋找最有潛力的下一步行動。但這究竟是什麼意思呢？

這個問題並沒有直接的答案。首先你不能提前知道對手的策略，對手可能是個高手，也可能是個菜鳥。假定在國際象棋中，你知道對手是個業餘愛好者（數學家會說，你的對手使用的是混合策略），你可以使用簡單的策略來嘗試欺騙對手並快速獲得勝利。但很明顯，同樣的策略在面對強大的對手時將適得其反。

如果你完全不了解對手，那麼你可以使用一種非常保守的策略即極小極大演算法，在假定你的對手執行最佳行動的前提下，最大化你的收益，也可以說在各種獲得最小收益的策略中選擇有最大收益的策略。這種方法以放棄最優策略為代價，從而最小化了風險，因此它是一種非常保守的方法。在 A 和 B 的兩人有限零和序列博弈中（其中 A 嘗試最大化其收益，而 B 嘗試最小化 A 的收益），極小極大演算法可以用以下的遞歸形式來描述：

其中：

• v_A 和 v_B 分別是玩家 A 和玩家 B 的效用函數（效用=收益）；
• move 是一個函數，它在給定當前狀態 s_i 和在該狀態的動作 a_i 下，生成下一個博弈狀態（當前節點的子節點之一）；
• eval 是一個評估最終博弈狀態（在端節點處）的函數；
• s hat 是任意的最終博弈狀態（即一個端節點）；
• 右下方式子的負號表示該博弈是一個零和博弈。

簡單來說，給定狀態 s，並假定對手嘗試最小化你的收益，你希望找到能最大化收益的動作 a_i。這正是該演算法被稱為極小極大的原因。我們需要做的就是展開整個博弈樹，並反向傳播由遞歸形式的規則得到的值。

上圖中的博弈樹展示了極小極大演算法中的最佳行動選擇過程。白皇后希望博弈的結果儘可能的黑暗（冷色，獎勵值=像素強度），而黑皇后希望博弈的結果儘可能的明亮（暖色）。每一個層級的選擇都是極小極大判斷的最優結果。我們可以從底部的終端節點開始，其中的選擇是很明顯的。黑皇后將總是選擇最明亮的顏色，然後白皇后將尋找最大的獎勵並選擇到達最暗顏色的路徑，等等。這正是基礎的極小極大演算法的執行過程。

極小極大演算法的最大弱點是它需要展開整個博弈樹。對於有高分支因子的博弈（例如圍棋或國際象棋），該演算法將導致巨大的博弈樹，使得計算無法進行。

那麼有什麼解救的辦法嗎？其中一個方法是僅在確定的閾值深度 d 內展開博弈樹，但是我們無法保證在閾值深度 d 處的任何節點是否端節點。因此我們一個函數來評估非終端博弈狀態。這對於人類來說很自然：即使博弈仍在進行，你也可能通過觀察圍棋或國際象棋的棋盤預測勝者。例如，對以下棋局可以很容易知道結束棋局的走法。

另一種克服博弈樹規模過大問題的方法是通過 alpha-beta 剪枝演算法來修剪博弈樹。alpha-beta 剪枝是提升版的極小極大演算法，它以極小極大演算法的形式遍歷博弈樹，並避免某些樹分支的展開，其得到的結果在最好的情況下等於極小極大演算法的結果。alpha-beta 剪枝通過壓縮搜索空間提高搜索效率。

極小極大演算法和 alpha-beta 修剪演算法已經是相當成熟的解決方案，目前已被用於多個成功的博弈引擎例如 Stockfish——AlphaZero 的主要對手之一。

蒙特卡洛樹搜索的基本概念

在蒙特卡洛樹搜索演算法中，最優行動會通過一種新穎的方式計算出來。顧名思義，蒙特卡洛樹搜索會多次模擬博弈，並嘗試根據模擬結果預測最優的移動方案。

蒙特卡洛樹搜索的主要概念是搜索，即沿著博弈樹向下的一組遍歷過程。單次遍歷的路徑會從根節點（當前博弈狀態）延伸到沒有完全展開的節點，未完全展開的節點表示其子節點至少有一個未訪問到。遇到未完全展開的節點時，它的一個未訪問子節點將會作為單次模擬的根節點，隨後模擬的結果將會反向傳播回當前樹的根節點並更新博弈樹的節點統計數據。一旦搜索受限於時間或計算力而終止，下一步行動將基於收集到的統計數據進行決策。

下面有一些關於上述蒙特卡洛樹搜索過程的關鍵問題，它們有助於我們的理解：

• 什麼是展開或未完全展開的博弈樹？
• 在搜索過程中，向下遍歷是什麼意思？如何選擇訪問的下一個子節點？
• 什麼是模擬？
• 什麼是反向傳播？
• 反向傳播回的統計數據是什麼，在展開博弈樹結點更新的是什麼?
• 最後的行動策略到底是如何選擇的？

下面，我們將依次解決這些問題，因而能對蒙特卡洛樹搜索有一個清晰的理解。

模擬

首先我們會關注於模擬，它並不會過多依賴於其它術語的定義。模擬即單次博弈策略，它是一系列從當前節點（表示博弈狀態）開始，並在計算出博弈結果後結束於端節點。模擬是一個在隨機博弈初始點開始評估近似計算的博弈樹節點。那在模擬中如何選擇行動呢？

在模擬中，行動可以通過 rollout 策略函數選擇：

該函數將輸入一個博弈狀態，併產生下一次行動的選擇。在實踐中，該函數會設計為允許很多次模擬快速進行，一般默認的 rollout 策略函數可以是服從均勻分布的隨機採樣。

Alpha Go 和 Alpha Zero 中的模擬

在 Alpha Go Lee 葉 S_L 的評估中，它會採用以下兩個分量的加權和：

• 帶有自定義快速 rollout 策略的標準 rollout 評估 z_L，它是一個帶有人工特徵的淺層 softmax 神經網路。
• 稱之為價值網路的 13 層卷積網路 v_0 從 Alpha Go 自我對抗中抽取 30mln 不同位置進行訓練，並最後預測評估位置。

Deepmind 的工程師在 Alpha Zero 中更進一步，他們根本不會執行模擬，他們會使用 19 層 CNN 殘差網路直接評估當前節點。

最簡單的模擬形式只是在給定博弈狀態下的隨機行動序列。模擬總會產生一個評估，對於博弈來說，該評估就是勝利、失敗或平局等結果，但通常任何值都可以是模擬的合理結果。

在蒙特卡洛樹搜索模擬中，我們始終會從一個前面沒訪問的節點開始，因此下面會介紹關於訪問節點的意義。

博弈樹的展開節點、完全展開節點和訪問節點

現在我們需要思考人類是如何考慮圍棋或象棋等博弈的。給定一個根節點並加上博弈的規則，那麼博弈樹的其餘部分就已經隱含表示出來了。我們可以遍歷它而不需要將整棵樹儲存在內存中。在最初的根節點中，它是完全未展開的，我們處於博弈的初始狀態，其餘所有節點都沒有被訪問。一旦我們需要執行一個行動，我們就會思考採用該行動後會產生怎樣的結果，因此訪問一個節點後，需要分析該節點位置與帶來的效用。

蒙特卡洛樹搜索也是採用相同的特性構建博弈樹。所有節點可以分為訪問或未訪問，那麼一個節點的訪問到底指的是什麼？一般而言，如果模擬將該節點作為初始節點，這就意味著它至少評估了一次，那麼它就可以視為已訪問節點。如果某節點的所有子節點都是已訪問節點，那麼它就可視為完全展開的節點，相對而言也就存在未完全展開的節點。

在實踐中，搜索開始時，根節點的所有子節點都未被訪問。然後一個節點被選中，第一個模擬（評估）就開始了。

請注意：模擬過程中 rollout 策略函數選擇的節點並未被訪問。它們仍然是未被訪問狀態，即使 rollout 經過它們，只有模擬開始的那個節點是被訪問的狀態。

反向傳播：將模擬結果傳播回去

當初次訪問節點的模擬結束後，其結果會反向傳播至當前博弈樹的根節點。模擬開始的節點被標註為已訪問。

反向傳播是從子節點（模擬開始的地方）遍歷回根節點。模擬結果被傳輸至根節點，反向傳播路徑上的每個節點的統計數據都被計算／更新。反向傳播保證每個節點的數據都會反映開始於其所有子節點的模擬結果（因為模擬結果被傳輸回博弈樹的根節點）。

節點的統計數據

反向傳播模擬結果的目的是更新反向傳播路徑（包括模擬起始的節點）上所有節點 v 的總模擬獎勵 Q(v) 以及總訪問次數 N(v)。

• Q(v) 即總模擬獎勵是節點 v 的一項屬性，在最簡單的形式中是通過考慮的節點得到的模擬結果的總和。
• N(v) 即總訪問次數是節點 v 的另一項屬性，表示節點 v 位於反向傳播路徑上的次數（即它對總模擬獎勵做出了多少次貢獻）。

每個被訪問節點都會保存這兩個值，一旦完成了確定次數的模擬之後，被訪問的節點就保存了它們被利用/探索（expolited/explored）的信息。

換句話說，當你查看任意節點的統計數據時，這兩個值將反映該節點的潛在價值（總模擬獎勵）和它被探索的程度（總訪問次數）。高獎勵的節點是很好的可利用候選，而那些訪問次數少的節點也可能是有價值的（因為它們尚未得到很好的探索）。

我們還缺少一塊拼圖。如何從一個根節點到達一個未訪問節點，來啟動一次模擬呢？

博弈樹遍歷

在搜索最開始的時候，由於我們還沒有進行任何模擬，所以先選擇未被訪問的節點。在每個未被訪問的節點上進行單次模擬，結果被反向傳播至根節點，然後根節點即被認為經過了完全展開。

但是接下來怎麼做呢？現在我們如何從完全展開的節點導向未被訪問的節點呢？我們必須遍歷被訪問節點的層，目前沒有很好的繼續進行的方式。

為了在路徑中找到下一個節點，以通過完全展開的節點 v 開始下一次模擬，我們需要考慮 v 所有子節點 v_1, v_2, …, v_k 的信息，以及節點 v 本身的信息。現在我們來思考一下可用信息有哪些：

當前節點（藍色）是完全展開的，因此它必須經過訪問，以存儲節點數據：它及其子節點的總模擬獎勵和總訪問次數。這些值是為了最後一部分：樹的置信上限（UCT）做準備。

樹的置信上限

UCT 是一個函數，使我們在被訪問節點中選擇下一個要遍歷的節點，這也是蒙特卡洛樹搜索的核心函數：

UCT 最大的節點就是蒙特卡洛樹搜索遍歷過程中選擇的節點。讓我們來看看 UCT 函數如何運行：

首先，該函數為節點 v 的子節點 v_i 而定義，它包括兩個組件：第一個組件是

，又叫做 exploitation 組件，可以理解為贏／輸率，總模擬獎勵（simulation reward）除以總訪問次數，即節點 v_i 的勝率評估結果。我們當然更想遍歷具備高贏率的節點。

為什麼不僅僅使用 exploitation 組件呢？因為我們會在搜索開始時很快結束對取得單次獲勝的節點的貪婪探索。

簡單示例：

假設我們僅使用 exploitation UCT 組件開始蒙特卡洛樹搜索。從根節點開始，我們對所有子節點進行一次模擬，然後下一步僅訪問那些模擬結果至少有一次是贏的節點。第一次模擬結果不幸失敗的節點會立刻被捨棄。

因此我們還要有第二個 UCT 組件 exploration。exploration 組件支持未被探索的節點，這些節點相對來說更少被訪問（N(v_i) 較低）。我們來看一下 UCT 函數 exploration 組件的形狀：隨著節點訪問量的增加而遞減，給訪問量少的節點提供更高的被選中幾率，以指引 exploration 探索。

最終，UCT 公式中的參數 c 控制蒙特卡洛樹搜索中 expolitation 和 exploration 組件之間的權衡。

UCT 函數中的一個重要標誌是：在競爭性遊戲中，其 exploitaion 組件 Q_i 的計算通常與在節點 i 處行動的玩家有關，這意味著在遍歷博弈樹時，玩家視角根據被遍歷的節點而變化：對於任意連續節點，玩家視角都是相反的。

終止蒙特卡洛樹搜索

現在我們了解了實現蒙特卡洛樹搜索所需要的所有因素，但還有一些問題需要回答。首先，我們什麼時候可以終止 MCTS？答案是：看情況。如果你構建一個遊戲引擎，那麼你的「思考時間」有限，計算能力也有限。因此最安全的選擇是只要資源允許，就可以一直運行 MCTS。

一旦 MCTS 過程結束，最好的一步通常是具備最高訪問量 N(v_i) 的一步，因為它的獎勵值評估結果最好（評估的值必須很高，因為它被探索的頻率也最高）。

在使用蒙特卡洛樹搜索走了一步之後，你的選擇節點就變成了對手下一步的起始遊戲狀態。一旦他走了一步，你就可以執行蒙特卡洛樹搜索，從表示對手選擇遊戲狀態的節點開始。之前的 MCTS round 數據可能仍然在你現在考慮的新分支以內。這就可以重新使用數據而不是從頭構建新的樹，事實上這就是 Alpha Go / Alpha Zero 創造者所做的。

總結

現在，我們來回顧一下蒙特卡洛樹搜索的簡單定義，並將其封裝進偽代碼：

你可以看到它縮減至非常少的函數，這些函數對任何遊戲都有效，不只是圍棋或象棋。你可以在這裡找到蒙特卡洛樹搜索用於井字棋（Tic-Tac-Toe）的實現示例：https://github.com/int8/monte-carlo-tree-search。

希望本文對大家有所幫助。

原文鏈接：https://int8.io/monte-carlo-tree-search-beginners-guide/