蒙地卡羅樹搜尋

係一種搜尋演算法，用嚟幫個決策者－例如一個人工智能－喺一個有極高複雜性嘅決策情境下搵出最啱嘅選擇。

以教一個人工智能程式捉棋爲例：現實世界入面啲棋類遊戲好多時都複雜得好交關；譬如係圍棋噉，圍棋個棋盤有成 10170 個可能形勢；事實表明，就算用好先進嘅電腦嚟推算形勢，都要嘥極大量嘅時間先至能夠睇勻嗮所有嘅可能性，令到人工智能程式响短嘅時間內俾唔到答案。所以喺實際應用上，靠窮舉式嘅演算法就唔扂。

於是廿一世紀初嘅遊戲人工智能領域當中就有咗 MCTS 嘅諗法。簡單噉講，MCTS 旨在由手上嘅可能性嗰度，有技巧噉揀一細部份可能性出嚟集中睇。用 MCTS 嘅程式會有一啲特定嘅方法嚟決定「邊啲可能性最值得睇」，然之後就集中考慮呢啲可能性，令到部電腦能夠喺相對短嘅時間內俾到個輸出出嚟睇。MCTS 呢個諗法喺 2010 年代後半橛經已成功咁嚌－例如人工智能程式 AlphaGo 就用咗 MCTS，並且喺 2016 年因為打低九段圍棋棋手李世石而出咗名。

背景

問題 

蒙地卡羅樹搜尋係一種用嚟應付複雜決策問題嘅技術。想像一樖決策樹。決策樹係一種用嚟表示決策嘅圖：一樖決策樹會有若干個節點，每個節點代表一個決策點，會有若干個箭咀指去下一排節點，每個箭咀表示「如果揀咗呢個選項，就去呢個決策點」。即係話下圖嗰樖決策樹表示：
個決策者家陣想決定好唔好去玩，
喺開頭個節點，去玩嘅價值有 9 分，唔好去玩嘅價值有 5 分，
然後睇天氣，如果晴天，噉去玩嘅價值變成 2 分，唔好去玩嘅價值變成 3 分，
然後個決策者會睇濕度
... 如此類推。

以下係井字過三關樖決策樹嘅其中一橛：

決策樹喺教人工智能玩遊戲嘅研究上相當受重視：一隻遊戲可以想像成一樖決策樹，喺任何一個時間點會喺某個特定嘅狀態，而玩家嘅決策會決定遊戲狀態跟住會變成點；原則上，教人工智能玩遊戲可以想像成「用搜尋演算法嚟由一樖決策樹嗰度搵出最好嘅選擇」。問題係，現實遊戲嘅決策樹通常都複雜得好交關，例如：國際象棋喺兩個棋手都行咗第一步之後，個棋盤會有 400 個可能嘅形勢，喺兩個棋手都行咗第二步之後，個棋盤會有 197,742 個可能嘅形勢，而喺兩個都行咗第三步之後，呢個數字會超過 100 萬；圍棋就仲複雜，有成 10170 個可能形勢咁多。因為呢啲遊戲嘅複雜性，窮舉搜尋喺實際應用上根本行唔通－做唔到「喺夠短嘅時間之內計到個答案出嚟」。

啟發 

蒙地卡羅方法係蒙地卡羅樹搜尋嘅一個重要基礎。蒙地卡羅方法係用隨機性嘅做法嚟應付決定性系統嘅演算法，源於 1940 年代：如果話一個系統係「決定性」嘅，意思係指個系統冇隨機性喺裏面，但就算一個系統係決定性，個系統依然有可能會係複雜到難以用決定性嘅方法解決。蒙地卡羅方法最基本嘅流程如下：
定義個系統嘅輸入嘅可能數值；
用一個表示輸入數值、受定義域限制嘅概率分佈隨機噉產生一個輸入；
對個輸入做決定性嘅運算；
將步驟 2 同 3 重複  咁多次，得到  個輸出，再結合數據－例如計嗰  個輸出嘅平均值。
舉個簡單例子說明，蒙地卡羅方法可以用嚟估計圓周率嘅數值：
畫一個正方形，再喺個正方形入面畫個 90° 嘅扇形，任何嘅輸入坐標  都實會喺個正方形裏面；
用一個均勻分佈產生一個輸入坐標數值，「均勻分佈」意思係指每個坐標可能數值出現嘅機會率都完全一樣；
喺產生咗出嚟輸入坐標數值嘅位置嗰度畫一點；
將步驟 2 同 3 重複  咁多次，然後數吓有幾多點點係喺個扇形裏面嘅，設呢個數值做 ，如果  嘅數值大到接近無限大嘅話，以下呢樣嘢會成立：

蒙地卡羅方法帶出咗一個諗頭：無論個系統係咪決定性嘅都好，用帶有隨機性嘅方法都有可能俾得到有返咁上下準嘅答案－「有返咁上下準」意思係指，得出嘅答案同真實嘅答案差距唔係咁大，未至於大到能夠對解決問題嘅效率造成明顯嘅負面影響。即係話，响應付國際象棋呢啲決定性嘅遊戲嘅決策樹嗰陣，都有可能可以用帶有隨機性嘅演算法嚟解。

原理

玩到尾 

想像玩到尾呢個概念。喺最基本上，家陣個人工智能程式做以下嘅步驟：
由可能嘅選擇當中隨機揀一個出嚟；
將呢柞節點「玩到尾」－以某啲方式估計呢個節點最後結果會係乜，簡單例子有
由過往數據嗰度估一個概率分佈表示呢個節點引致「輸」同引致「贏」嘅機會率；又或者
假設自己同對手會用某啲策略，模擬吓喺嗰個情況下邊個贏；
再唔係可以學 AlphaGo 噉，靠人工神經網絡由「行咗呢步」嗰度預測「自己會贏定輸」；
噉就算係一次玩到尾。喺最簡單嗰種情況下，個演算法可以每次自己要做決定嗰陣，都
完全隨機噉select 若干個節點，
foreach 節點都做玩到尾嘅過程，
最後再按「邊一個節點最大機會令自己贏」做基準決定要行邊一步。
進階啲嘅演算法仲會有更複雜嘅方法做 select 同 roll，而 select 同 roll 當中嘅技巧就係蒙地卡羅樹搜尋最重要嘅一環之一。

四大步驟 
喺最基本上，用蒙地卡羅樹搜尋嚟搵出「應該行邊步」嘅過程有若干個回合，每個回合有四個步驟：
選擇：設  呢個節點做起點，並且由下一排節點嗰度揀一個，揀  排，設  做最後去到嗰個節點；選擇嘅過程會涉及所謂嘅利用同探索之間嘅取捨－利用係指揀最「好」嗰啲選擇，而探索就係指睇一啲冇咁「好」嗰啲選擇。
擴張：除非  會令遊戲結束，由  嘅下一排節點當中揀一個，設呢個節點做 ；
模擬：由  嗰度做一次玩到尾嘅過程；
反向傳播：用玩到尾嘅結果改變自己對  同  之間嗰條路線嘅判斷；例：如果模擬步驟發現  最後會大機會令到自己贏，就將  同  之間嗰條路線或者節點  加若干分數，而一個節點愈高分，個程式就愈大可能會揀行嗰步。亦都可以最小最大化等嘅決策法則。
順帶一提，有進階嘅做法會係教個 AI「喺唔同時候採取唔同嘅決策法則」或者「行完一輪之後攞走某啲諗過、但發覺冇用嘅節點」。
以下係呢個基本演算法嘅圖解。幅圖表示緊一樖玩國際象棋嘅決策樹，每個圓圈係一個節點，白色圓圈表示白棋嗰方嘅選擇，而灰色圓圈表示黑棋嗰方嘅選擇，白色同黑色輪流行；每個節點掕住嘅份數表示嗰個節點有幾大機會會令嗰一方贏：

利用定探索 

喺蒙地卡羅樹搜尋嘅第一步當中，其中一個最大嘅問題係「要點樣平衡利用同探索」：一方面，响短期內令自己利益最大化嘅做法係利用－集中淨係揀一啲根據過往經驗係大機會贏嘅選擇；另一方面，蒙地卡羅樹搜尋必然就係涉及由數唔嗮咁多嘅選擇當中揀一啲出嚟嘅，所以喺任何一個時間點都實會有大量嘅可能性係個程式未睇嘅－去睇呢啲可能性有一定嘅機會搵到能夠進一步提升贏面嘅選擇；所以蒙地卡羅樹搜尋嘅研究者就喺度諗－

設  做有得揀嘅節點嘅集合，家陣個程式變成想令以下呢條式得出嘅數值有咁大得咁大：
；，當中
 係節點  睇咗幾多次。
 係節點  嘅模擬當中「贏」發生咗幾多次。
反映節點  根據過往經驗有幾大機會贏。
 係依家身處嗰個節點睇咗幾多次。
 係自然對數。
反映節點  有幾少可睇， 數值愈細  就會愈大。
 係所謂嘅探索參數，係一個數值可以用實驗嚟調節嘅參數。
用日常用語講即係話：喺呢條式之下，得分最高嘅節點－個程式最有可能會睇嘅節點－傾向會係「根據過往經驗有大機會贏」或者「過往最少睇」嘅節點。

輕度定重度 

蒙地卡羅樹搜尋改良版會分辨所謂嘅輕度玩到尾同埋重度玩到尾：
「輕度玩到尾」指玩到尾嘅過程完全係隨機嘅－喺模擬「呢個節點會引致乜嘢結果」嗰陣，個程式齋靠每步隨機是但噉行；
「重度玩到尾」指玩到尾嘅過程會用到常用嘅啟發法－即係用一啲已知嘅常用解難步驟嚟行。喺呢方面，個程式嘅設計者好可能會靠參考由專業玩嗰隻遊戲嘅人所提供嘅專家知識：喺專業捉棋或者玩第啲遊戲嘅人之間，好多時都會有啲所謂嘅行內啟發法，即係「噉行法傾向會贏」嘅簡單法則，而研究者可以試吓教一個人工智能程式喺做重度玩到尾嗰時用呢啲法則嚟模擬「呢個節點會引致乜嘢結果」。例如喺圍棋入面，一條簡單嘅啟發法係「用自己啲棋將對手圍住」，而因為呢條啟發法相對簡單，做起玩到尾模擬嗰陣部電腦就唔使用咁多運算資源。
喺 2010 年代初，用重度玩到尾嘅蒙地卡羅樹搜尋經已有初步嘅成功，喺一啲人工智能玩遊戲比賽當中打贏。

RAVE 
蒙地卡羅樹搜尋改良版好多時仲會用埋所謂嘅快速行動價值估計做法：一般嘅蒙地卡羅樹搜尋要花一段時間嚟做模擬，先至會得出每個節點嘅價值；而喺呢一點之前，個蒙地卡羅樹搜尋演算法嘅行動會係隨機嘅咁滯。想像有樖決策樹，當中有個節點 ， 有一個子節點 ，個程式儲起咗  嘅價值，而  呢個數值包含咗兩樣嘢：
 喺打前嘅玩到尾當中贏咗幾多次，而且仲包埋
所有起自  終於  嘅「玩到尾贏出次數」。
RAVE 呢種做法係考慮到一點：喺好多遊戲當中，是但搵某一個「遊戲狀態改變」，個改變通常都係可以透過多條圖徑達致嘅；所以如果做咗一個節點嘅玩到尾，估計到佢個價值，噉呢個結果理應唔淨只可以反映個節點本身嘅價值，仲會反映相連節點嘅價值。用咗 RAVE，個程式能夠快啲知道每個節點嘅價值，所以可以加快「估計啲節點嘅價值」嘅過程。

以下圖為例，想像以下呢樖井字過三關決策樹，每個節點表示「邊方霸咗邊個格仔」。如果個程式係用 RAVE，而起始點係最開始嗰點，做咗  嘅玩到尾模擬之後，啲紅線掂嘅節點嘅價值冚唪唥都會受到更新。

响實際應用上，可以想像成將  嗰條式改吓，變成類似以下噉嘅樣，照舊係要個程式揀條式個數值最大嘅節點：
；，當中
 係指包含咗節點  喺入面嘅玩到尾嘅數量。
 係指包含咗節點  喺入面嘅玩到尾總共贏咗幾多次。
 反映總共做咗幾多次模擬；
 係一個函數， 數值細  會接近 1，而  數值大  會接近 0。

起源 
蒙地卡羅樹搜尋嘅技術起源於 2000 年代中：喺 2006 年，有法國嘅人工智能研究者受到蒙地卡羅方法啟發，將蒙地卡羅方法應用嚟搜尋遊戲嘅決策樹－輸入可能值：目前狀態去得嘅節點；隨機產生輸入：是但攞一個節點嚟睇；計輸出：「個節點會輸定贏」... 重複若干次－並且用「蒙地卡羅樹搜尋」呢個詞嚟形容佢個演算法做緊嘅嘢。佢嗰個做法話咁快就引起咗當時學界嘅注意，吸引第啲研究者仿傚同埋嘗試改善佢嗰個演算法，而呢啲程式仲取得咗初步嘅成功，喺簡化版嘅圍棋當中打低咗業餘嘅棋手。

蒙地卡羅樹搜尋係喺 2010 年代開始進入全盛嘅：喺 2015 年 10 月，由 Google DeepMind 開發嘅捉圍棋程式 AlphaGo 成為咗第一個成功噉响「個人類棋手冇讓賽」嘅情況下打低專業人類棋手嘅人工智能程式，而及後 AlphaGo 仲同韓國嘅九段圍棋棋手李世石比賽，捉咗 5 局，並且以 4 比 1 大獲全勝，令到 AlphaGo 相關嘅技術－包括蒙地卡羅樹搜尋－一舉成名。自此之後，蒙地卡羅樹搜尋嘅技術受到人工智能界嘅關注，仲俾人廣泛噉攞嚟教人工智能玩各種圍棋以外嘅圖板遊戲，甚至乎係即時制嘅視像遊戲同埋帶有隨機性嘅檯上遊戲。

出名程式 
AlphaGo：用到蒙地卡羅樹搜尋、強化學習同深度學習，玩嘅係圍棋。
AlphaGo Zero：AlphaGo 嘅進化版，出名在唔使用到任何人類捉棋數據，而且仲打低咗之前嘅 AlphaGo 程式。
AlphaZero：廣義化嘅 AlphaGo，都係用蒙地卡羅樹搜尋、強化學習同深度學習，但除咗圍棋之外仲識捉國際象棋同日本將棋。
Leela Chess Zero：一隻自由開源軟件，用 AlphaZero 嘅方法捉國際象棋。

樹狀數據
搜尋演算法
Alpha-beta 剪枝
圍棋
電腦模擬
複雜系統
博弈論
決策論
最佳化

文獻 

Althöfer, Ingo (2012). "On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness". Advances in Computer Games. Lecture Notes in Computer Science. 7168. pp. 258–269.
Bouzy, B., & Tutorial, C. (2007, April). Old-fashioned computer go vs monte-carlo go (PDF). In IEEE Symposium on Computational Intelligence in Games (CIG).
Cameron Browne; Edward Powley; Daniel Whitehouse; ... et al. (March 2012). "A Survey of Monte Carlo Tree Search Methods" (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 4 (1): 1–43.
Chang, Hyeong Soo; Fu, Michael; Hu, Jiaqiao; Marcus, Steven I. (2016). "Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement". OR/MS Today. 45 (5): 24–29.
Chaslot, G. M. J., Winands, M. H., Herik, H. J. V. D. ... et al. (2008). Progressive strategies for Monte-Carlo tree search (PDF). New Mathematics and Natural Computation, 4(03), 343-357.
Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik (2008). "Parallel Monte-Carlo Tree Search" (PDF). Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 60–71.
Markus Enzenberger; Martin Müller (2010). "A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm". In Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers. Springer. pp. 14–20.
Richard J. Lorentz (2008). "Amazons Discover Monte-Carlo". Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 13–24.
Silver, David; Huang, Aja; Maddison, Chris J.; ... et al. (28 January 2016). "Mastering the game of Go with deep neural networks and tree search (PDF)". Nature. 529 (7587): 484–489.
Subramanian, K., Scholz, J., Isbell, C. L., & Thomaz, A. L. (2016). Efficient exploration in monte carlo tree search using human action abstractions (PDF). In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS (Vol. 16).
Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). Modification of UCT with Patterns in Monte-Carlo Go (PDF). Technical report, INRIA.

參攷

拎 

"Lee Sedol defeats AlphaGo in masterful comeback - Game 4". Go Game Guru.
MoGo, maître du jeu de Go ?.

演算法
機械學習