蒙地卡羅樹搜尋
From Wikipedia, the free encyclopedia
蒙地卡羅樹搜尋(英文:Monte Carlo tree search,簡稱 MCTS)係一種搜尋演算法,用嚟幫一位決策者(例如一個 AI 程式)喺有極高複雜度嘅決策情境下搵出「最啱」嘅選擇[1][2]。
例如依家教一個人工智能程式捉棋:現實世界嘅棋類遊戲好多時都複雜得好交關;譬如係圍棋噉,圍棋個棋盤有成 10170 個可能形勢咁多;事實表明,就算用好先進嘅電腦嚟推算形勢,都要嘥極大量嘅時間先至能夠睇勻晒所有嘅可能性,人工智能程式做唔到「响夠短嘅時間內俾答案」。所以喺實際應用上,靠窮舉式(指考慮晒一切可能性再揀個最好嘅選擇)行事嘅演算法就唔掂[3]。
於是,廿一世紀初嘅遊戲人工智能領域就有咗 MCTS 嘅諗法。簡單噉講,MCTS 旨在要由手上嘅可能性當中,有技巧噉揀一細部份嘅出嚟集中睇。行 MCTS 嘅程式會有一啲特定嘅方法決定「邊啲可能性最值得睇」,然之後佢哋就會集中分析呢啲可能性,噉就令到部電腦能夠喺相對短嘅時間內俾到個輸出[3]。喺 2010 年代後半橛 MCTS 呢個諗法經已成功咁嚌,例如人工智能程式 AlphaGo 就用咗 MCTS,並且喺 2016 年打低九段圍棋棋手李世石而出咗名[4][5]。