2016-03-11
日前睦袖，圍棋人機(jī)大戰(zhàn)激戰(zhàn)正酣，代表人工智能出戰(zhàn)的阿爾法狗（AlphaGo）已經(jīng)2：0領(lǐng)先韓國(guó)世界冠軍李世石，展示出雄厚實(shí)力验靡。

AlphaGo使用蒙特卡洛樹搜索（Monte Carlo tree search），借助值網(wǎng)絡(luò)（value network）與策略網(wǎng)絡(luò)（policy network）這兩種深度神經(jīng)網(wǎng)絡(luò)症脂，通過(guò)值網(wǎng)絡(luò)來(lái)評(píng)估大量選點(diǎn)谚赎，并通過(guò)策略網(wǎng)絡(luò)選擇落點(diǎn)淫僻。

什么是 MCTS？

全稱 Monte Carlo Tree Search壶唤，是一種人工智能問(wèn)題中做出最優(yōu)決策的方法雳灵，一般是在組合博弈中的行動(dòng)（move）規(guī)劃形式。它結(jié)合了隨機(jī)模擬的一般性和樹搜索的準(zhǔn)確性闸盔。

MCTS 受到快速關(guān)注主要是由計(jì)算機(jī)圍棋程序的成功以及其潛在的在眾多難題上的應(yīng)用所致悯辙。超越博弈游戲本身，MCTS 理論上可以被用在以 {狀態(tài) state迎吵，行動(dòng) action} 對(duì)定義和用模擬進(jìn)行預(yù)測(cè)輸出結(jié)果的任何領(lǐng)域躲撰。

基本算法

基本的 MCTS 算法非常簡(jiǎn)單：根據(jù)模擬的輸出結(jié)果，按照節(jié)點(diǎn)構(gòu)造搜索樹击费。其過(guò)程可以分為下面的若干步：

搜索樹的構(gòu)建過(guò)程
選擇 Selection：從根節(jié)點(diǎn) R 開始拢蛋，遞歸選擇最優(yōu)的子節(jié)點(diǎn)（后面會(huì)解釋）直到達(dá)到葉子節(jié)點(diǎn) L。

擴(kuò)展 Expansion：如果 L 不是一個(gè)終止節(jié)點(diǎn)（也就是荡灾，不會(huì)導(dǎo)致博弈游戲終止）那么就創(chuàng)建一個(gè)或者更多的字子節(jié)點(diǎn)瓤狐，選擇其中一個(gè) C。

模擬 Simulation：從 C 開始運(yùn)行一個(gè)模擬的輸出批幌，直到博弈游戲結(jié)束础锐。

反向傳播 Backpropagation：用模擬的結(jié)果輸出更新當(dāng)前行動(dòng)序列。

參看Tutorial 了解關(guān)于這個(gè)過(guò)程更多的信息荧缘。

每個(gè)節(jié)點(diǎn)并需包含兩個(gè)重要的信息：一個(gè)是根據(jù)模擬結(jié)果估計(jì)的值和該節(jié)點(diǎn)已經(jīng)被訪問(wèn)的次數(shù)皆警。

按照最為簡(jiǎn)單和最節(jié)約內(nèi)存的實(shí)現(xiàn)，MCTS 將在每個(gè)迭代過(guò)程中增加一個(gè)子節(jié)點(diǎn)截粗。不過(guò)信姓，要注意其實(shí)根據(jù)不同的應(yīng)用這里也可以在每個(gè)迭代過(guò)程中增加超過(guò)一個(gè)子節(jié)點(diǎn)。

節(jié)點(diǎn)選擇

Bandits 和 UCB
在樹向下遍歷時(shí)的節(jié)點(diǎn)選擇通過(guò)選擇最大化某個(gè)量來(lái)實(shí)現(xiàn)绸罗，這其實(shí)類似于 Multiarmed bandit problem意推，其中的參與者必須選擇一個(gè) slot machine（bandit）來(lái)最大化每一輪的估計(jì)的收益。我們可以使用 Upper Confidence Bounds（UCB）公式常常被用來(lái)計(jì)算這個(gè)：

Exploitation 和 Exploration
UCB 公式對(duì)已知收益的 exploitation 和鼓勵(lì)接觸那些相對(duì)未曾訪問(wèn)的節(jié)點(diǎn)的 exploration 進(jìn)行平衡腻窒。收益估計(jì)基于隨機(jī)模擬，所以節(jié)點(diǎn)必須被訪問(wèn)若干次來(lái)缺包估計(jì)變得更加可信磅崭；MCTS 估計(jì)會(huì)在搜索的開始不大可靠儿子，而最終會(huì)在給定充分的時(shí)間后收斂到更加可靠的估計(jì)上，在無(wú)限時(shí)間下能夠達(dá)到最優(yōu)估計(jì)砸喻。

MCTS 和 UCT
Kocsis 和 Szepervari 在 2006 年首先構(gòu)建了一個(gè)完備的 MCTS 算法柔逼，通過(guò)擴(kuò)展 UCB 到 minimax 樹搜索蒋譬，并將其命名為 Upper Confidence Bounds for Trees（UCT）方法。這其實(shí)是用在當(dāng)前眾多 MCTS 實(shí)現(xiàn)中的算法版本卒落。

UCT 可以被描述為 MCTS 的一個(gè)特例：UCT = MCTS + UCB羡铲。

優(yōu)點(diǎn)

MCTS 提供了比傳統(tǒng)樹搜索更好的方法。

Aheuristic
MCTS 不要求任何關(guān)于給定的領(lǐng)域策略或者具體實(shí)踐知識(shí)來(lái)做出合理的決策儡毕。這個(gè)算法可以在沒有任何關(guān)于博弈游戲除基本規(guī)則外的知識(shí)的情況下進(jìn)行有效工作也切；這意味著一個(gè)簡(jiǎn)單的 MCTS 實(shí)現(xiàn)可以重用在很多的博弈游戲中，只需要進(jìn)行微小的調(diào)整腰湾，所以這也使得 MCTS 是對(duì)于一般的博弈游戲的很好的方法雷恃。

Asymmetric
MCTS 執(zhí)行一種非對(duì)稱的樹的適應(yīng)搜索空間拓?fù)浣Y(jié)構(gòu)的增長(zhǎng)。這個(gè)算法會(huì)更頻繁地訪問(wèn)更加有趣的節(jié)點(diǎn)费坊，并聚焦其搜索時(shí)間在更加相關(guān)的樹的部分倒槐。

非對(duì)稱的增長(zhǎng)
這使得 MCTS 更加適合那些有著更大的分支因子的博弈游戲，比如說(shuō) 19X19 的圍棋附井。這么大的組合空間會(huì)給標(biāo)準(zhǔn)的基于深度或者寬度的搜索方法帶來(lái)問(wèn)題讨越，所以 MCTS 的適應(yīng)性說(shuō)明它（最終）可以找到那些更加優(yōu)化的行動(dòng)，并將搜索的工作聚焦在這些部分永毅。

任何時(shí)間
算法可以在任何時(shí)間終止把跨，并返回當(dāng)前最有的估計(jì)。當(dāng)前構(gòu)造出來(lái)的搜索樹可以被丟棄或者供后續(xù)重用沼死。

簡(jiǎn)潔
算法實(shí)現(xiàn)非常方便（參見 Code:http://mcts.ai/code/index.html）

缺點(diǎn)

MCTS 有很少的缺點(diǎn)着逐，不過(guò)這些缺點(diǎn)也可能是非常關(guān)鍵的影響因素。

行為能力
MCTS 算法意蛀，根據(jù)其基本形式耸别，在某些甚至不是很大的博弈游戲中在可承受的時(shí)間內(nèi)也不能夠找到最好的行動(dòng)方式。這基本上是由于組合步的空間的全部大小所致县钥，關(guān)鍵節(jié)點(diǎn)并不能夠訪問(wèn)足夠多的次數(shù)來(lái)給出合理的估計(jì)秀姐。

速度
MCTS 搜索可能需要足夠多的迭代才能收斂到一個(gè)很好的解上，這也是更加一般的難以優(yōu)化的應(yīng)用上的問(wèn)題若贮。例如囊扳，最佳的圍棋程序可能需要百萬(wàn)次的交戰(zhàn)和領(lǐng)域最佳和強(qiáng)化才能得到專家級(jí)的行動(dòng)方案，而最有的 GGP 實(shí)現(xiàn)對(duì)更加復(fù)雜的博弈游戲可能也就只要每秒鐘數(shù)十次（領(lǐng)域無(wú)關(guān)的）交戰(zhàn)兜看。對(duì)可承受的行動(dòng)時(shí)間，這樣的 GGP 可能很少有時(shí)間訪問(wèn)到每個(gè)合理的行動(dòng)狭瞎，所以這樣的情形也不大可能出現(xiàn)表現(xiàn)非常好的搜索细移。

幸運(yùn)的是，算法的性能可以通過(guò)一些技術(shù)顯著提升熊锭。

提升

很多種 MCTS 強(qiáng)化的技術(shù)已經(jīng)出現(xiàn)了弧轧。這些基本上可以歸納為領(lǐng)域知識(shí)或者領(lǐng)域獨(dú)立兩大類雪侥。

領(lǐng)域知識(shí)
特定博弈游戲的領(lǐng)域知識(shí)可以用在樹上來(lái)過(guò)濾掉不合理的行動(dòng)或者在模擬過(guò)程中產(chǎn)生重要的對(duì)局（更接近人類對(duì)手的表現(xiàn)）。這意味著交戰(zhàn)結(jié)果將會(huì)更加的現(xiàn)實(shí)而不是隨機(jī)的模擬精绎，所以節(jié)點(diǎn)只需要少量的迭代就能給出一個(gè)現(xiàn)實(shí)的收益值速缨。

領(lǐng)域知識(shí)可以產(chǎn)生巨大的性能提升，但在速度和一般性上也會(huì)有一定的損失代乃。

領(lǐng)域獨(dú)立
領(lǐng)域獨(dú)立強(qiáng)化能夠應(yīng)用到所有的問(wèn)題領(lǐng)域中旬牲。這些一般用在樹種（如 AMAF），還有一些用在模擬（如 在交戰(zhàn)時(shí)傾向于勝利的行動(dòng)）搁吓。領(lǐng)域獨(dú)立強(qiáng)化并不和特定的領(lǐng)域綁定原茅，具有一般性，這也是當(dāng)前研究的重心所在堕仔。

背景和歷史

1928：John von Neumann 的 minimax 定理給出了關(guān)于對(duì)手樹搜索的方法擂橘，這形成了計(jì)算機(jī)科學(xué)和人工智能的從誕生至今的決策制定基礎(chǔ)。
1940s：Monte Carlo 方法形成摩骨，作為一種通過(guò)隨機(jī)采樣解決不太適合樹搜索解決的弱良定義問(wèn)題的方法通贞。
2006：Rémi Coulomb 和其他研究者組合了上面兩種想法給出了一個(gè)新的圍棋程序中行動(dòng)規(guī)劃的觀點(diǎn)——MCTS。Kocsis 和 Szepesvári 將此觀點(diǎn)形式化進(jìn) UCT 算法恼五。

研究興趣

從 MCTS 誕生后幾年內(nèi)昌罩，就有超過(guò) 150 篇與 MCTS 相關(guān)的研究論文發(fā)布，平均下來(lái)是每?jī)芍芤黄碌奈恼禄礁浴＿@些文章中包含了大概 50 個(gè)推薦的變體峡迷、強(qiáng)化和優(yōu)化，這和傳統(tǒng)樹搜索自其 1928 年誕生開始的加強(qiáng)的數(shù)量也差不太多你虹。

這個(gè)新的研究領(lǐng)域當(dāng)前是 AI 中非常熱的研究話題绘搞，有很多的開放的研究問(wèn)題有待發(fā)掘和解決。

MCTS: 最新成果

Imperial College London held the first international MCTS workshop in August 2010 on the theme of MCTS: State of the Art. Speakers included:
O. Teytaud, "State of the Art: What is MCTS, where is it now, and where is it going?” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:london2010.pdfM. Müller, “Challenges in Monte Carlo Tree Search,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:london2010-mcts-challenges.pdfR. Hayward, “MoHex: Computer Hex world champion,” 2010 [Online]. Available: http://www.aigamesnetwork.org/_media/main:events:mohextalk.pdfH. Finnsson and Y. Bj?rnsson, “CadiaPlayer: MCTS in General Game Playing,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:cadiaplayer_lic_slides_print.pdfA. Rimmel, “Havannah, Monte Carlo Enhancements and Linear Transforms,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:presmctsworkshop_rimmel.pdf

英文原文:http://mcts.ai/about/index.html
來(lái)源：簡(jiǎn)書
原文：http://www.reibang.com/p/d011baff6b64