万维百科粤语版

蒙地卡羅樹搜尋

跳去導覽 跳去搵嘢
一盤圍棋;圍棋嘅可能步數有成超過 10100 個咁多-「將啲可能性冚唪唥睇勻嗮」嘅做法喺實際應用上行唔通。

蒙地卡羅樹搜尋粵拼mung4 dei6 kaa1 lo4 syu6 sau2 cam4英文Monte Carlo tree search,簡稱「MCTS」)係一種搜尋演算法,用嚟幫個決策者-例如一個人工智能(AI)-由一個有極高複雜性(complexity)嘅決策情境下搵出最好嘅選擇[1][2]

舉個例說明,家陣教一個人工智能程式捉棋,但現實世界嘅好多時都複雜得好交關,例如係圍棋噉,圍棋係一種好複雜嘅遊戲,圍棋棋盤有成 10170 個可能形勢;而事實表明咗,就算用先進嘅電腦行,都要嘥極大量嘅時間先至能夠睇勻嗮所有嘅可能性,唔能夠令人工智能程式响夠短嘅時間內俾到答案,所以喺實際應用上,靠「將啲可能性冚唪唥考慮嗮,再揀最好嗰個選擇」嘅演算法行唔通[3]

於是廿一世紀初嘅遊戲人工智能領域就有咗 MCTS 嘅諗頭。簡單噉講,MCTS 涉及由手上嘅可能性嗰度,有技巧噉揀一細部份嘅出嚟集中睇;用 MCTS 嘅程式會有一啲特定方法決定「邊啲可能性最值得睇」,然後就集中考慮呢啲可能性,令到部電腦能夠喺相對短嘅時間內俾到個輸出出嚟睇[3]。MCTS 嘅諗頭喺 2010 年代後半橛經已達致咗一定嘅成功-2016年打低九段圍棋棋手李世石而出名嘅人工智能程式 AlphaGo 就用咗 MCTS [4]

以下嘅內容假設咗讀者經已具備基本嘅概率論機械學習知識。

背景

睇埋:遊戲人工智能同埋普遍玩遊戲

要解決嘅問題

內文:決策決策樹、 同 複雜性

蒙地卡羅樹搜尋係一種用嚟應付複雜決策問題嘅技術。想像一樖決策樹(decision tree)。決策樹係一種用嚟表示決策嘅圖:一樖決策樹(下圖)會有若干個節點(node),每個節點(黑色框框)代表一個決策點,會有若干個箭咀指去下一排節點(下一步),每個箭咀表示「如果揀咗呢個選項,就去呢個決策點」。即係話下圖嗰樖決策樹表示:

  • 個決策者家陣想決定好唔好去玩(PLAY),
  • 喺開頭個節點,去玩(play)嘅價值有 9 分,唔好去玩(don't play)嘅價值有 5 分,
  • 然後睇天氣(OUTLOOK),如果晴天(sunny),噉去玩嘅價值變成 2 分,唔好去玩嘅價值變成 3 分,
  • 然後個決策者會睇濕度(HUMIDITY)

... 如此類推[1]

Decision tree model.png

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

一盤國際象棋開局嗰陣嘅樣

蒙地卡羅方法

用蒙地卡羅方法估計 數值嘅圖解;圖上高嘅字顯示計出嚟個 數值同 之間嘅關係- 愈大,計到出嚟嘅 就愈近真嘅圓周率。
內文:蒙地卡羅方法

蒙地卡羅方法(Monte Carlo method)係蒙地卡羅樹搜尋嘅一個重要基礎。蒙地卡羅方法係用隨機性嘅做法嚟應付決定性系統(deterministic system)嘅演算法,源於 1940 年代:如果話一個系統係「決定性」嘅,意思係指個系統冇隨機性喺裏面,但就算一個系統係決定性,個系統依然有可能會係複雜到難以用決定性嘅方法解決[7]。蒙地卡羅方法最基本嘅流程如下[8]

  1. 定義個系統嘅輸入嘅可能數值(定義域;domain);
  2. 用一個表示輸入數值、受定義域限制嘅概率分佈(probability distribution)隨機噉產生一個輸入;
  3. 對個輸入做決定性嘅運算
  4. 將步驟 2 同 3 重複 咁多次,得到 個輸出,再結合數據(aggregate data)-例如計嗰 個輸出嘅平均值

舉個簡單例子說明,蒙地卡羅方法可以用嚟估計圓周率)嘅數值(睇附圖)[8]

  1. 畫一個正方形,再喺個正方形入面畫個 90° 嘅扇形,任何嘅輸入坐標 都實會喺個正方形裏面(定義域);
  2. 用一個均勻分佈(uniform distribution)產生一個輸入坐標數值,「均勻分佈」意思係指每個坐標可能數值出現嘅機會率都完全一樣(睇埋隨機數生成);
  3. 喺產生咗出嚟輸入坐標數值嘅位置嗰度畫一點(做運算);
  4. 將步驟 2 同 3 重複 咁多次,然後數吓有幾多點點係喺個扇形裏面(同原點距離細過 1)嘅,設呢個數值做 ,如果 嘅數值大到接近無限大嘅話,以下呢樣嘢會成立:

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

原理

呢個伯努利分佈描述緊一個節點:「呢一個節點有 咁大機會率引致贏(1),有 咁大機會率引致輸(0)。想像個程式 foreach 節點都整到個噉嘅分佈。

蒙地卡羅樹搜尋嘅重點在於一樣嘢[4]

諗吓『自己可以採取嘅行動』當中邊一個係最有可能幫自己贏嘅,建基於由可能嘅答案嗰度做隨機抽樣(random sampling)。

玩到尾

想像玩到尾(playout / roll-out)呢個概念。喺最基本上,家陣個人工智能程式做以下嘅步驟:

  • 由可能嘅選擇(樖決策樹嘅下一排節點)當中隨機揀(select)一個出嚟;
  • 將呢柞節點「玩到尾」-以某啲方式估計呢個節點最後結果會係乜(輸定贏),簡單例子有由過往數據嗰度估一個概率分佈表示呢個節點引致「輸」同引致「贏」嘅機會率

噉就算係一次玩到尾。喺最簡單嗰種情況下,個演算法可以每次自己要做決定(例:到自己行)嗰陣,都

  1. 完全隨機噉(隨機抽樣)select 若干個節點,
  2. foreach 節點都做玩到尾嘅過程,
  3. 最後再按「邊一個節點最大機會令自己贏」做基準決定要行邊一步。

進階啲嘅演算法仲會有更複雜嘅方法做 select,而 select 當中嘅技巧就係蒙地卡羅樹搜尋最重要嘅一環之一[9]

優缺點

進階

簡史

睇埋

文獻

參攷

  1. 1.0 1.1 Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Perez; Spyridon Samothrakis; Simon Colton (March 2012). "A Survey of Monte Carlo Tree Search Methods". IEEE Transactions on Computational Intelligence and AI in Games. 4 (1): 1–43.
  2. Monte Carlo Tree Search. Towards Data Science.
  3. 3.0 3.1 Silver, David; Huang, Aja; Maddison, Chris J.; ... et al. (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature. 529 (7587): 484–489.
  4. 4.0 4.1 Liu, Michael (10 October 2017). "General Game-Playing With Monte Carlo Tree Search". Medium.
  5. Bontrager, P., Khalifa, A., Mendes, A., & Togelius, J. (2016, September). Matching games and algorithms for general video game playing. In Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference.
  6. Kleinsmith, A., & Gillies, M. (2013). Customizing by doing for responsive video game characters. International Journal of Human-Computer Studies, 71(7-8), 775-784.
  7. 7.0 7.1 Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. (2014). "Why the Monte Carlo method is so important today". WIREs Comput Stat. 6 (6): 386–392.
  8. 8.0 8.1 Kalos, Malvin H.; Whitlock, Paula A. (2008). Monte Carlo Methods. Wiley-VCH.
  9. Brügmann, Bernd (1993). Monte Carlo Go (PDF). Technical report, Department of Physics, Syracuse University.


本页面最后更新于2021-04-06 00:18,点击更新本页查看原网页

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器