<mark id="oztn4"></mark>
0
雷鋒網按：本文作者彭博，Blink·稟臨科技聯合創始人。文章由雷鋒網整理自作者知乎專欄，獲授權發布，未經允許禁止轉載。
蒙特卡洛樹搜索（MCTS）是所有現代圍棋程序的核心組件。在此之上可以加入各種小技巧（如 UCT，RAVE/AMAF，Progressive Bias，Virtual win & lose，Progressive Widening，LGR，Criticality 等等）和大改進（如 AlphaGo 的策略網絡和價值網絡）。
網上很少見到關于 MCTS 的詳細介紹，而且許多看似詳細的介紹實際有錯誤，甚至許多人會混淆蒙特卡洛樹搜索和蒙特卡洛方法。這兩者有本質區別。用做過渲染器的朋友會理解的話來說：蒙特卡洛方法有偏差（Bias），而MCTS沒有偏差（Bias）。我們在后文會解釋。
一、極小極大（Minimax）搜索
先看傳統的博弈游戲樹搜索，著名的極小極大（Minimax）搜索，學過算法的朋友會清楚。看下圖，假設現在輪到黑棋，黑棋有b1和b2兩手可選，白棋對于b1有w1和w2兩手可選，白棋對于b2有w3 w4 w5三手可選：
然后假設走完w1/w2/w3/w4/w5后，經過局面評估，黑棋的未來勝率分別是 50%/48%/62%/45%/58%（等一下，這些勝率是怎么評估出來的？我們后文會說這個問題）。
請問，黑棋此時最佳的著法是b1還是b2？如果是用蒙特卡洛方法，趨近的會是其下所有勝率的平均值。例如經過蒙特卡洛模擬，會發現b1后續的勝率是49% = (50+48)/2，而b2后續的勝率是55% = (62+45+58)/3。
于是蒙特卡洛方法說應該走b2，因為55%比49%的勝率高。但這是錯誤的。因為如果白棋夠聰明，會在黑棋走b1的時候回應以w2（盡量降低黑棋的勝率），在黑棋走b2的時候回應以w4（盡量降低黑棋的勝率）。
所以走b1后黑棋的真實勝率是48%，走b2后黑棋的真實勝率是45%。黑棋的正解是b1。這就是 Minimax 搜索的核心思想：在搜索樹中，每次輪到黑棋走時，走對黑棋最有利的；輪到白棋走時，走對黑棋最不利的。由于圍棋是零和游戲，這就可以達到最優解。這是一個由底往上的過程：先把搜索樹畫到我們可以承受的深度，然后逐層往上取最大值或最小值回溯，就可以看到雙方的正解（如果勝率評估是準確的）。而實際編程的時候，是往下不斷生長節點，然后動態更新每個父節點的勝率值。
下圖是一個更多層的例子：
值得注意的是，在實際對局中，勝率評估會有不準確的地方，這就會導致“地平線效應”，即由于電腦思考的深度不夠，且勝率評估不夠準確，因此沒有看見正解。
Minimax 搜索還有許多后續發展，如課本會說的 Alpha-beta 剪枝，以及更進一步的 Null Window / NegaScout / MTD(f) 等等。可惜這些方法更適合象棋等棋類，對于圍棋的意義不大（除非已經接近終局），請讀者思考原因。
蒙特卡洛樹搜索和蒙特卡洛方法的區別在于：
如果用蒙特卡洛方法做上一百萬次模擬，b1和b2的勝率仍然會固定在49%和55%，不會進步，永遠錯誤。所以它的結果存在偏差（Bias），當然，也有方差（Variance）。
而蒙特卡洛樹搜索在一段時間模擬后，b1和b2的勝率就會向48%和45%收斂，從而給出正確的答案。所以它的結果不存在偏差（Bias），只存在方差（Variance）。但是，對于復雜的局面，它仍然有可能長期陷入陷阱，直到很久之后才開始收斂到正確答案。
二、蒙特卡洛樹搜索
如果想把 Minimax 搜索運用到圍棋上，立刻會遇到兩個大問題：
搜索樹太廣。棋盤太大了，每一方在每一步都有很多著法可選。
很難評估勝率。除非把搜索樹走到終局，這意味著要走夠三百多步（因為對于電腦來說，甚至很難判斷何時才是雙方都同意的終局，所以只能傻傻地填子，一直到雙方都真的沒地方可以走為止）。簡單地說，搜索樹也需要特別深。
蒙特卡洛樹搜索的意義在于部分解決了上述兩個問題：
它可以給出一個局面評估，雖然不準，但比沒有強。這就部分解決了第二個問題。
根據它的設計，搜索樹會較好地自動集中到“更值得搜索的變化”（注意，也不一定準）。如果發現一個不錯的著法，蒙特卡洛樹搜索會較快地把它看到很深，可以說它結合了廣度優先搜索和深度優先搜索，類似于啟發式搜索。這就部分解決了第一個問題。
最后，隨著搜索樹的自動生長，蒙特卡洛樹搜索可以保證在足夠長的時間后收斂到完美解（但可能需要極長的時間）。下面看具體過程（需要指出，下圖是網絡上常見的一個圖，但其實有錯誤）：
上圖中每個節點代表一個局面。而 A/B 代表這個節點被訪問 B 次，黑棋勝利了 A 次。例如一開始的根節點是 12/21，代表總共模擬了 21 次，黑棋勝利了 12 次。
我們將不斷重復一個過程（很多萬次）：
這個過程的第一步叫選擇（Selection）。從根節點往下走，每次都選一個“最值得看的子節點”（具體規則稍后說），直到來到一個“存在未擴展的子節點”的節點，如圖中的 3/3 節點。什么叫做“存在未擴展的子節點”，其實就是指這個局面存在未走過的后續著法。
第二步叫擴展（Expansion），我們給這個節點加上一個 0/0 子節點，對應之前所說的“未擴展的子節點”，就是還沒有試過的一個著法。
第三步是模擬（Simluation）。從上面這個沒有試過的著法開始，用快速走子策略（Rollout policy）走到底，得到一個勝負結果。按照普遍的觀點，快速走子策略適合選擇一個棋力很弱但走子很快的策略。因為如果這個策略走得慢（比如用 AlphaGo 的策略網絡走棋），雖然棋力會更強，結果會更準確，但由于耗時多了，在單位時間內的模擬次數就少了，所以不一定會棋力更強，有可能會更弱。這也是為什么我們一般只模擬一次，因為如果模擬多次，雖然更準確，但更慢。
第四步是回溯（Backpropagation）。把模擬的結果加到它的所有父節點上。例如第三步模擬的結果是 0/1（代表黑棋失敗），那么就把這個節點的所有父節點加上 0/1。
三、重要細節
怎么選擇節點？和從前一樣：如果輪到黑棋走，就選對于黑棋有利的；如果輪到白棋走，就選對于黑棋最不利的。但不能太貪心，不能每次都只選擇“最有利的/最不利的”，因為這會意味著搜索樹的廣度不夠，容易忽略實際更好的選擇。
因此，最簡單有效的選擇公式是這樣的：
其中 x 是節點的當前勝率估計（注意，如前所述，要考慮當前是黑棋走還是白棋走！），N 是節點的訪問次數。C 是一個常數。C 越大就越偏向于廣度搜索，C 越小就越偏向于深度搜索。注意對于原始的 UCT 有一個理論最優的 C 值，但由于我們的目標并不是最小化“遺憾”，因此需要根據實際情況調參。
我們看例子說明這是什么意思，就看之前的圖吧。假設根節點是輪到黑棋走。那么我們首先需要在 7/10、5/8、0/3 之間選擇：
如果 C 比較小，我們將會選擇 7/10，接著就要在 2/4 和 5/6 間選擇。注意，由于現在是白棋走，需要把勝率估計倒過來：
那么我們下一步肯定應該選 2/4。所以說之前的圖是錯誤的，因為制圖的人并沒有注意到要把勝率倒過來（有朋友會說是不是可以認為它的白圈代表白棋的勝率，但這樣它的回溯過程就是錯的）。
最后，AlphaGo 的策略網絡，可以用于改進上述的分數公式，讓我們更準確地選擇需擴展的節點。而 AlphaGo 的價值網絡，可以與快速走子策略的模擬結果相結合，得到更準確的局面評估結果。注意，如果想寫出高效的程序，這里還有很多細節，因為策略網絡和價值網絡的運行畢竟需要時間，我們不希望等到網絡給出結果再進行下一步，在等的時候可以先做其它事情，例如 AlphaGo 還有一個所謂 Tree policy，是在策略網絡給出結果之前先用著。
相信大家現在就可以寫出正確的 MCTS 程序了（注意：最終應該選擇訪問量最大的節點，而不是勝率最高的節點，簡單地說是因為訪問量最大的節點的結果更可靠）。如果要寫一個高效的程序，你會發現必須自己寫一個內存池。關于 MCTS 還有很多話題可以說，這篇就到這里吧。
本系列已更新多篇，其它幾篇的傳送門：
28 天自制你的 AlphaGo（二）：訓練策略網絡，真正與之對弈
28天自制你的AlphaGo（三）：對策略網絡的深入分析以及它的弱點所在
28天自制你的AlphaGo（四）：結合強化學習與深度學習的Policy Gradient（左右互搏自我進化的基礎）
