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

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

網(wǎng)上很少見(jiàn)到關(guān)于 MCTS 的詳細(xì)介紹，而且許多看似詳細(xì)的介紹實(shí)際有錯(cuò)誤，甚至許多人會(huì)混淆蒙特卡洛樹(shù)搜索和蒙特卡洛方法。這兩者有本質(zhì)區(qū)別。用做過(guò)渲染器的朋友會(huì)理解的話來(lái)說(shuō)：蒙特卡洛方法有偏差（Bias），而MCTS沒(méi)有偏差（Bias）。我們?cè)诤笪臅?huì)解釋。

一、極小極大（Minimax）搜索

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

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

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

于是蒙特卡洛方法說(shuō)應(yīng)該走b2，因?yàn)?5%比49%的勝率高。但這是錯(cuò)誤的。因?yàn)槿绻灼鍓蚵斆?，?huì)在黑棋走b1的時(shí)候回應(yīng)以w2（盡量降低黑棋的勝率），在黑棋走b2的時(shí)候回應(yīng)以w4（盡量降低黑棋的勝率）。

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

下圖是一個(gè)更多層的例子：

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

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

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

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

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

二、蒙特卡洛樹(shù)搜索

如果想把 Minimax 搜索運(yùn)用到圍棋上，立刻會(huì)遇到兩個(gè)大問(wèn)題：

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

• 很難評(píng)估勝率。除非把搜索樹(shù)走到終局，這意味著要走夠三百多步（因?yàn)閷?duì)于電腦來(lái)說(shuō)，甚至很難判斷何時(shí)才是雙方都同意的終局，所以只能傻傻地填子，一直到雙方都真的沒(méi)地方可以走為止）。簡(jiǎn)單地說(shuō)，搜索樹(shù)也需要特別深。

蒙特卡洛樹(shù)搜索的意義在于部分解決了上述兩個(gè)問(wèn)題：

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

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

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

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

我們將不斷重復(fù)一個(gè)過(guò)程（很多萬(wàn)次）：

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

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

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

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

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

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

因此，最簡(jiǎn)單有效的選擇公式是這樣的：

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

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

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

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

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

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

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

28 天自制你的 AlphaGo（一）

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

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

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

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