AlphaGo背后的力量：蒙特卡洛树搜索入门指南
我們都知道 DeepMind 的圍棋程序 AlphaGo，以及它超越人類的強大能力，也經常會聽到「蒙特卡洛樹搜索」這個概念。事實上，蒙特卡洛樹搜索是在完美信息博弈場景中進行決策的一種通用技術，除游戲之外，它還在很多現實世界的應用中有著廣闊前景。本文中，我們會以 AlphaGo 為例子，對這一方法進行詳細介紹。
長久以來，學術世界一直認為計算機在圍棋這個復雜游戲上達到超越人類的水平是幾乎無法實現的。它被視為人工智能的「圣杯」——一個我們原本希望在未來十年挑戰的遙遠里程碑。在國際象棋上，「深藍」曾在 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/??
機器之心編譯
文章版權歸原作者所有，轉載僅供學習使用，不用于任何商業用途，如有侵權請留言聯系刪除，感謝合作。
總結
以上是生活随笔為你收集整理的AlphaGo背后的力量：蒙特卡洛树搜索入门指南的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何用Python画一个中国地图？
- 下一篇： 如何简单形象又有趣地讲解神经网络是什么？