MCTS (Monte Carlo Tree Search) 演算法
MCTS（Monte Carlo Tree Search，蒙地卡羅樹搜尋）是一種利用取樣結果進行決策的演算法，自從 MCTS 問世以來，AI 棋力明顯的提升，許多傳統方法正逐漸被取代。2016 與類神經網路結合後，AI 實力更進一步，在圍棋等複雜度極高的遊戲中超越人類的頂尖。
MCTS 四階段
一次 MCTS 模擬包含四個階段：selection、expansion、rollout、backpropagation。
- Selection：選擇要進行展開下一層的葉節點。
- Expansion：展開下一層。
- Rollout (playout, simulation)：估這個節點的 value。
- Backpropagation：向上更新。
（圖片來源：By Rmoss92 - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=88889583）
Selection
從根節點開始向下層選擇要移至的位置，直到葉節點為止。
選擇哪個節點是一個探索與利用的問題，是要選擇之前表現不錯的節點？還是探索很少走過的節點？
一般可以試試用 UCT 公式選（UCT 也有不少變體）。（論文：Kocsis, Levente & Szepesvári, Csaba. (2006). Bandit Based Monte-Carlo Planning. Machine Learning: ECML. 2006. 282-293. 10.1007/11871842_29.）
維基裡 UCT 的描述如下：（跟論文原文的式子有點不同但基本一樣）
左邊 w/n 是利用（利用過往經驗）項，右邊是探索項（總模擬次數 N 越大，或自己被模擬次數 n 越小，探索比重越大）。
一開始 n 為 0，探索比重無限大。除以零可能導致程式崩壞，實作細節可以自行微調，例如手動給無限大或是從 1 開始等等。
Expansion
長出下一層合法步。
Rollout (playout, simulation）
Rollout 在有的地方可能會以 playout 或 simulation 的名稱出現。用 simulation （模擬）稱呼的話要注意不要和一次 MCTS 模擬的「模擬」搞混，前者表達的是一輪 MCTS 模擬的 rollout 階段，後者表達的是一輪完整的 MCTS 的模擬，包含 selection、expansion、rollout、backpropagation。
一般 rollout 的方式為：雙方輪流隨機地下直到把這盤棋下完，結束後得到的結果即是這個節點好壞的估值，類似 evaluation value。乍聽可能會覺得這樣得到的估值牢靠嗎？別擔心，別忘了 Monte Carlo 方法的精神：隨機取樣，只要以這個節點為根節點的子樹的總模擬次數夠大，可以趨進真正的值。
Backpropagation
向上更新回去。在雙人對局的 MCTS 裡，向上一層更新勝負要記得倒過來一次，因為上一層是你的對手的 move。
在到達一定的模擬次數/時間或其他結束條件後，我們通常會選擇根節點第一層 child nodes 裡面造訪次數最多的 node，作為實際下一步要下的 action。
Reference
https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
Kocsis, Levente & Szepesvári, Csaba. (2006). Bandit Based Monte-Carlo Planning. Machine Learning: ECML. 2006. 282-293. 10.1007/11871842_29.