上一篇的 5/21 是在回答「看著一盤棋，要怎麼判斷形勢」。這個問題對圍棋程式非常關鍵：西洋棋程式用 Alpha-Beta 搜尋，搜到一定深度後就靠評估函數打分數；但圍棋的形勢太難用規則寫清楚，5/21 這類方法再怎麼調也不夠準，加上每一步有上百種下法，傳統搜尋在圍棋上一直做不起來。

蒙地卡羅樹搜尋（Monte Carlo Tree Search，MCTS）換了一個思路：看不出局面好壞，那就把棋下完很多次，統計勝率。終局要判斷誰贏很容易，數子就好。2006 年 Coulom^[1]和 Kocsis、Szepesvári^[2]先後提出這套方法之後，圍棋程式在幾年內從業餘入門進步到業餘高段；後來的 AlphaGo^[3]也是以 MCTS 為骨架，再把神經網路放進去。

互動演示

為了把整棵搜尋樹畫出來，下面用井字棋示範，演算法和圍棋版完全一樣，只是規模小到看得清楚。O 先手。

按「下一步」可以一次走一個階段，看一次模擬裡發生了什麼；看懂之後按「+100」或「+1000」快轉，觀察樹的形狀怎麼變。點樹上的節點，右下角會列出它每個子節點的 UCT 是怎麼算出來的。也可以自己在棋盤上下子，從任何局面開始搜尋。

演算法

MCTS 會從目前的局面（根節點）出發，重複做很多次「模擬」。每個節點記錄兩個數字：

• N：這個節點被走過幾次
• W：其中下這一手的一方贏了幾次（和局算 0.5）

所以 W ÷ N 就是這一手的勝率。每次模擬分成四個階段：

1. Selection（選擇）

從根往下走。如果一個節點的所有著手都已經在樹裡了，就用 UCT 公式挑一個子節點往下；直到走到一個還有著手沒展開的節點，或是終局為止。

2. Expansion（擴展）

在停下來的節點底下，挑一個還沒試過的著手，加進樹裡當新節點。每次模擬只加一個，所以樹是慢慢長大的。

3. Simulation（模擬）

從新節點開始，雙方隨機下到終局，得到一個勝負結果。這些隨機下的棋不會存進樹裡，只是用來「估一下這個局面大概怎樣」。這一步也常叫做 rollout 或 playout。

4. Backpropagation（回傳）

把結果沿著剛剛走過的路徑往回更新：每個節點的 N 加 1；如果下這一手的一方贏了，W 加 1，和局加 0.5。

模擬次數用完之後，選根節點底下造訪次數最多的那一手。用造訪次數而不是勝率，是因為勝率在 N 很小的時候不可靠：一手只試過一次、剛好贏了，勝率就是 100%。

UCT：要試好棋，還是試新棋？

Selection 階段的難處在於取捨：

• 一直試目前勝率最高的著手，可能錯過一開始運氣不好、其實更好的著手
• 每手都平均試，又會浪費大量時間在明顯的壞棋上

Kocsis 和 Szepesvári^[2]把這個問題對應到「多臂吃角子老虎機」（multi-armed bandit），借用 UCB1 公式^[4]，提出 UCT（Upper Confidence bounds applied to Trees）。在每個節點，選讓下式最大的子節點：

UCT = W_i ÷ N_i + c × √(ln N ÷ N_i)

• 第一項（利用）：這手目前的勝率。
• 第二項（探索）：N 是父節點的造訪次數，N_i 是這個子節點的。被試得越少，這一項越大；父節點被走得越多，沒試過幾次的子節點也會慢慢被拉回來試。
• c：調整兩者比重的常數，理論上常用 √2。

這個公式的保證是：模擬次數趨近無限時，選出來的著手會收斂到最佳解，而且浪費在壞棋上的次數只會以對數速度增長。

可以觀察的幾件事

• 搶勝還是擋？（預設局面）：O 下 C3 直接贏，X 也在 C1 等著連線。快轉 100 次，C3 會被試得遠比其他著手多：每次走到 C3 都是立刻獲勝，勝率是 100%，UCT 一直排在最前面。
• 樹是不對稱的：快轉 1000 次之後看搜尋樹，好的著手越長越寬、越長越深，差的著手只有薄薄一條。這正是 MCTS 跟固定寬度搜尋最大的差別，計算資源會自己集中到值得看的地方。
• 調整 c：把 c 調成 0 再重設搜尋、快轉，搜尋會很早就「認定」某一手，其他著手幾乎不再被試；把 c 調到 3，樹會變得比較平均。可以在「必須擋」這個局面試試看：c = √2 時每次都會找到 B1，c = 0 時大約每四次就有一次選錯。
• 隨機模擬的偏差：在空棋盤上快轉 1000 次，O 的勝率會明顯高於 50%，但井字棋雙方都下對的話其實是和局。這是因為隨機下的對手很弱，先手佔便宜。模擬次數夠多時，樹裡的統計會慢慢修正這個偏差，但它提醒我們：rollout 的品質決定了 MCTS 的上限。

換成圍棋會怎樣？

演算法本身不用改，只是規模完全不同：

• 分支數：19×19 開局有 361 種下法，井字棋只有 9 種。
• 模擬長度：一次隨機對局要下兩三百手才結束。
• 隨機對局的品質：隨機亂下的圍棋幾乎沒有意義，會到處自填眼位、送死。所以實際的程式會加規則，例如不准填自己的眼，或用棋形資料庫（pattern）讓 rollout 下得「像樣一點」^[1]。

AlphaGo 的改進正好落在這幾個痛點上：用策略網路告訴 Selection 哪些著手值得先試（等於縮小分支數），用價值網路直接估計局面勝率，取代或輔助隨機 rollout（等於不用每次都下完）^[3]。到了 AlphaGo Zero 和 KataGo，rollout 已經完全拿掉了，但 Selection、Expansion、Backpropagation 的骨架還是一樣。

參考資料

1. Rémi Coulom (2006). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search." Computers and Games (CG 2006), LNCS 4630, 72–83.
2. Levente Kocsis and Csaba Szepesvári (2006). "Bandit based Monte-Carlo Planning." Machine Learning: ECML 2006, LNCS 4212, 282–293.
3. David Silver et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484–489.
4. Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235–256.
5. Cameron B. Browne et al. (2012). "A Survey of Monte Carlo Tree Search Methods." IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.