雷鋒網(wǎng)按：本文作者彭博，Blink·稟臨科技聯(lián)合創(chuàng)始人。文章由雷鋒網(wǎng)整理自作者知乎專欄，獲授權(quán)發(fā)布，未經(jīng)允許禁止轉(zhuǎn)載。

蒙特卡洛樹搜索（MCTS）是所有現(xiàn)代圍棋程序的核心組件。在此之上可以加入各種小技巧（如 UCT，RAVE/AMAF，Progressive Bias，Virtual win & lose，Progressive Widening，LGR，Criticality 等等）和大改進(jìn)（如 AlphaGo 的策略網(wǎng)絡(luò)和價值網(wǎng)絡(luò)）。

網(wǎng)上很少見到關(guān)于 MCTS 的詳細(xì)介紹，而且許多看似詳細(xì)的介紹實際有錯誤，甚至許多人會混淆蒙特卡洛樹搜索和蒙特卡洛方法。這兩者有本質(zhì)區(qū)別。用做過渲染器的朋友會理解的話來說：蒙特卡洛方法有偏差（Bias），而MCTS沒有偏差（Bias）。我們在后文會解釋。

一、極小極大（Minimax）搜索

先看傳統(tǒng)的博弈游戲樹搜索，著名的極小極大（Minimax）搜索，學(xué)過算法的朋友會清楚。看下圖，假設(shè)現(xiàn)在輪到黑棋，黑棋有b1和b2兩手可選，白棋對于b1有w1和w2兩手可選，白棋對于b2有w3 w4 w5三手可選：

然后假設(shè)走完w1/w2/w3/w4/w5后，經(jīng)過局面評估，黑棋的未來勝率分別是 50%/48%/62%/45%/58%（等一下，這些勝率是怎么評估出來的？我們后文會說這個問題）。

請問，黑棋此時最佳的著法是b1還是b2？如果是用蒙特卡洛方法，趨近的會是其下所有勝率的平均值。例如經(jīng)過蒙特卡洛模擬，會發(fā)現(xiàn)b1后續(xù)的勝率是49% = (50+48)/2，而b2后續(xù)的勝率是55% = (62+45+58)/3。

于是蒙特卡洛方法說應(yīng)該走b2，因為55%比49%的勝率高。但這是錯誤的。因為如果白棋夠聰明，會在黑棋走b1的時候回應(yīng)以w2（盡量降低黑棋的勝率），在黑棋走b2的時候回應(yīng)以w4（盡量降低黑棋的勝率）。

所以走b1后黑棋的真實勝率是48%，走b2后黑棋的真實勝率是45%。黑棋的正解是b1。這就是 Minimax 搜索的核心思想：在搜索樹中，每次輪到黑棋走時，走對黑棋最有利的；輪到白棋走時，走對黑棋最不利的。由于圍棋是零和游戲，這就可以達(dá)到最優(yōu)解。這是一個由底往上的過程：先把搜索樹畫到我們可以承受的深度，然后逐層往上取最大值或最小值回溯，就可以看到雙方的正解（如果勝率評估是準(zhǔn)確的）。而實際編程的時候，是往下不斷生長節(jié)點，然后動態(tài)更新每個父節(jié)點的勝率值。

下圖是一個更多層的例子：

值得注意的是，在實際對局中，勝率評估會有不準(zhǔn)確的地方，這就會導(dǎo)致“地平線效應(yīng)”，即由于電腦思考的深度不夠，且勝率評估不夠準(zhǔn)確，因此沒有看見正解。

Minimax 搜索還有許多后續(xù)發(fā)展，如課本會說的 Alpha-beta 剪枝，以及更進(jìn)一步的 Null Window / NegaScout / MTD(f) 等等?？上н@些方法更適合象棋等棋類，對于圍棋的意義不大（除非已經(jīng)接近終局），請讀者思考原因。

蒙特卡洛樹搜索和蒙特卡洛方法的區(qū)別在于：

• 如果用蒙特卡洛方法做上一百萬次模擬，b1和b2的勝率仍然會固定在49%和55%，不會進(jìn)步，永遠(yuǎn)錯誤。所以它的結(jié)果存在偏差（Bias），當(dāng)然，也有方差（Variance）。
  

• 而蒙特卡洛樹搜索在一段時間模擬后，b1和b2的勝率就會向48%和45%收斂，從而給出正確的答案。所以它的結(jié)果不存在偏差（Bias），只存在方差（Variance）。但是，對于復(fù)雜的局面，它仍然有可能長期陷入陷阱，直到很久之后才開始收斂到正確答案。

二、蒙特卡洛樹搜索

如果想把 Minimax 搜索運用到圍棋上，立刻會遇到兩個大問題：

• 搜索樹太廣。棋盤太大了，每一方在每一步都有很多著法可選。

• 很難評估勝率。除非把搜索樹走到終局，這意味著要走夠三百多步（因為對于電腦來說，甚至很難判斷何時才是雙方都同意的終局，所以只能傻傻地填子，一直到雙方都真的沒地方可以走為止）。簡單地說，搜索樹也需要特別深。

蒙特卡洛樹搜索的意義在于部分解決了上述兩個問題：

• 它可以給出一個局面評估，雖然不準(zhǔn)，但比沒有強(qiáng)。這就部分解決了第二個問題。
  

• 根據(jù)它的設(shè)計，搜索樹會較好地自動集中到“更值得搜索的變化”（注意，也不一定準(zhǔn)）。如果發(fā)現(xiàn)一個不錯的著法，蒙特卡洛樹搜索會較快地把它看到很深，可以說它結(jié)合了廣度優(yōu)先搜索和深度優(yōu)先搜索，類似于啟發(fā)式搜索。這就部分解決了第一個問題。

最后，隨著搜索樹的自動生長，蒙特卡洛樹搜索可以保證在足夠長的時間后收斂到完美解（但可能需要極長的時間）。下面看具體過程（需要指出，下圖是網(wǎng)絡(luò)上常見的一個圖，但其實有錯誤）：

上圖中每個節(jié)點代表一個局面。而 A/B 代表這個節(jié)點被訪問 B 次，黑棋勝利了 A 次。例如一開始的根節(jié)點是 12/21，代表總共模擬了 21 次，黑棋勝利了 12 次。

我們將不斷重復(fù)一個過程（很多萬次）：

這個過程的第一步叫選擇（Selection）。從根節(jié)點往下走，每次都選一個“最值得看的子節(jié)點”（具體規(guī)則稍后說），直到來到一個“存在未擴(kuò)展的子節(jié)點”的節(jié)點，如圖中的 3/3 節(jié)點。什么叫做“存在未擴(kuò)展的子節(jié)點”，其實就是指這個局面存在未走過的后續(xù)著法。

第二步叫擴(kuò)展（Expansion），我們給這個節(jié)點加上一個 0/0 子節(jié)點，對應(yīng)之前所說的“未擴(kuò)展的子節(jié)點”，就是還沒有試過的一個著法。

第三步是模擬（Simluation）。從上面這個沒有試過的著法開始，用快速走子策略（Rollout policy）走到底，得到一個勝負(fù)結(jié)果。按照普遍的觀點，快速走子策略適合選擇一個棋力很弱但走子很快的策略。因為如果這個策略走得慢（比如用 AlphaGo 的策略網(wǎng)絡(luò)走棋），雖然棋力會更強(qiáng)，結(jié)果會更準(zhǔn)確，但由于耗時多了，在單位時間內(nèi)的模擬次數(shù)就少了，所以不一定會棋力更強(qiáng)，有可能會更弱。這也是為什么我們一般只模擬一次，因為如果模擬多次，雖然更準(zhǔn)確，但更慢。

第四步是回溯（Backpropagation）。把模擬的結(jié)果加到它的所有父節(jié)點上。例如第三步模擬的結(jié)果是 0/1（代表黑棋失?。?，那么就把這個節(jié)點的所有父節(jié)點加上 0/1。

三、重要細(xì)節(jié)

怎么選擇節(jié)點？和從前一樣：如果輪到黑棋走，就選對于黑棋有利的；如果輪到白棋走，就選對于黑棋最不利的。但不能太貪心，不能每次都只選擇“最有利的/最不利的”，因為這會意味著搜索樹的廣度不夠，容易忽略實際更好的選擇。

因此，最簡單有效的選擇公式是這樣的：

其中 x 是節(jié)點的當(dāng)前勝率估計（注意，如前所述，要考慮當(dāng)前是黑棋走還是白棋走?。?，N 是節(jié)點的訪問次數(shù)。C 是一個常數(shù)。C 越大就越偏向于廣度搜索，C 越小就越偏向于深度搜索。注意對于原始的 UCT 有一個理論最優(yōu)的 C 值，但由于我們的目標(biāo)并不是最小化“遺憾”，因此需要根據(jù)實際情況調(diào)參。

我們看例子說明這是什么意思，就看之前的圖吧。假設(shè)根節(jié)點是輪到黑棋走。那么我們首先需要在 7/10、5/8、0/3 之間選擇：

如果 C 比較小，我們將會選擇 7/10，接著就要在 2/4 和 5/6 間選擇。注意，由于現(xiàn)在是白棋走，需要把勝率估計倒過來：

那么我們下一步肯定應(yīng)該選 2/4。所以說之前的圖是錯誤的，因為制圖的人并沒有注意到要把勝率倒過來（有朋友會說是不是可以認(rèn)為它的白圈代表白棋的勝率，但這樣它的回溯過程就是錯的）。

最后，AlphaGo 的策略網(wǎng)絡(luò)，可以用于改進(jìn)上述的分?jǐn)?shù)公式，讓我們更準(zhǔn)確地選擇需擴(kuò)展的節(jié)點。而 AlphaGo 的價值網(wǎng)絡(luò)，可以與快速走子策略的模擬結(jié)果相結(jié)合，得到更準(zhǔn)確的局面評估結(jié)果。注意，如果想寫出高效的程序，這里還有很多細(xì)節(jié)，因為策略網(wǎng)絡(luò)和價值網(wǎng)絡(luò)的運行畢竟需要時間，我們不希望等到網(wǎng)絡(luò)給出結(jié)果再進(jìn)行下一步，在等的時候可以先做其它事情，例如 AlphaGo 還有一個所謂 Tree policy，是在策略網(wǎng)絡(luò)給出結(jié)果之前先用著。

相信大家現(xiàn)在就可以寫出正確的 MCTS 程序了（注意：最終應(yīng)該選擇訪問量最大的節(jié)點，而不是勝率最高的節(jié)點，簡單地說是因為訪問量最大的節(jié)點的結(jié)果更可靠）。如果要寫一個高效的程序，你會發(fā)現(xiàn)必須自己寫一個內(nèi)存池。關(guān)于 MCTS 還有很多話題可以說，這篇就到這里吧。

本系列已更新多篇，其它幾篇的傳送門：

28 天自制你的 AlphaGo（一）

28 天自制你的 AlphaGo（二）：訓(xùn)練策略網(wǎng)絡(luò)，真正與之對弈

28天自制你的AlphaGo（三）：對策略網(wǎng)絡(luò)的深入分析以及它的弱點所在

28天自制你的AlphaGo（四）：結(jié)合強(qiáng)化學(xué)習(xí)與深度學(xué)習(xí)的Policy Gradient（左右互搏自我進(jìn)化的基礎(chǔ)）

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。