介紹
MCTS（Monte Carlo Tree Search）中文叫蒙特卡洛樹搜索。前一段時間非常厲害的Alpha Zero 的核心就是蒙特卡洛樹搜索。
還有個小插曲，老溼在搜索“蒙特卡洛樹搜索”的時候看到有的文章翻譯不怎麼準確，還有的竟然把“蒙特卡洛樹搜索”和“蒙特卡洛方法”弄混的，差點被誤導了，因為剛開始我也不太熟悉這個兩個概念，但是文章越往下看，感覺不對，用蒙特卡洛方法算出來的概率就算模擬一萬次也不變，這根本就不智能，像個假算法。Alpha Zero大家都知道的，自己模擬自己對弈，模擬的次數越多，它就越厲害，所以根本就對不上。建議同學們最好是看英文原文，咱們在這就不介紹蒙特卡洛方法是什麼了，本篇的重點是蒙特卡洛樹搜索。
基本算法：
由四步構成：Selection，Expansion，Simulation，Backpropagation。翻譯成普通話就是：
選擇節點：從根節點開始按最優選擇往下走，直到不能再走的那個最優子節點M的時候就停住。
擴展節點：給M節點擴展一個子節點N
模擬執行：根據子節點N開始模擬對弈，直到勝利結束
反向傳播：用反向傳播把模擬的結果更新到真實的父節點上。
然後會重複執行這樣的組合操作，需要注意的是每個節點上會有兩個數據統計，第一個是成功次數，第二個是經過這個節點的次數，如：3/8 代表這個節點經過了8次，但是隻有3次贏得比賽，可以叫做勝率，敏感的同學會猜測：是不是比例越高選擇這個節點的概率就越大呢？。後面會回答這個猜測，但是在學習過程中有這樣的思考非常好，多質疑，找答案，驗證自己的想法，千萬不要一篇文章從頭看到尾然後能記住多少算多少，這樣不好。
節點選擇：
每一個過程中節點是根據UCB公式來選擇：
$$s=v_i + C\sqrt{\frac{ln N}{n_i}}$$
解釋一下公式：
$$v_i$$ 表示當前節點的勝率，也就是用 勝利的次數／總共經過的次數
-
N表示當前節點的父節點的總共經過次數
n是當前節點的經過次數
C是一個常數，可以調整，C越大，對訪問次數相對較少的子節點有利，C越小，對訪問次數相對較多的子節點有利，換一種說法就是C 越大就越偏向於廣度搜索，C 越小就越偏向於深度搜索。
看公式比較抽象，舉個例子說明一下，如下圖：（老溼也在尋找更好的畫圖工具，老鐵們也可以推薦好的）
從最上面的根節點開始看，7表示贏了7次，15表示總次數嘗試了15次，紅色的表示選中的節點，藍色表示放棄的節點。而且每個子節點上的兩個數據加起來一定等於父節點上的數據，比如底部的兩個子節點，1/2和2/2加起來就是3/4表示嘗試4次，勝利3次，正好是父節點的數據。
根據上面介紹的公式，再來看一下節點如何選擇，首先看二級節點 4/7和3/8結算後的結果：
$$s_1=\frac{4}{7} + C\sqrt{\frac{ln 15}{7}}$$ 約等於 0.57 + 0.62C
$$s_2=\frac{3}{8} + C\sqrt{\frac{ln 15}{8}}$$ 約等於 0.37 + 0.58C
可以證明上面提到的C常數：C越大偏向於廣度搜索，對訪問次數相對較少的子節點有利，C越小偏向於深度搜索，對訪問次數相對較多的子節點有利。
下面的子節點的選擇也是如此，需要注意的是，我們這裡注重的是深度，應該選擇訪問量最大的節點，而不是勝率最高的節點像1/1這樣概率為100%的就不合適，因為訪問量最大的節點的結果更可靠。
總結：
介紹了蒙特卡洛樹搜索基本算法 ( Selection ) 選擇節點，( Expansion ) 擴展節點，( Simulation ) 模擬執行，( Backpropagation ) 反向傳播，以及UCB公式$$s=v_i + C\sqrt{\frac{ln N}{n_i}}$$
閱讀更多 5分鐘機器學習 的文章
