Integrating Learning and Planning

Monte-Carlo Search（續(xù)）

下面我們結(jié)合實(shí)例（下圍棋）和示意圖，來實(shí)際了解MCTS的運(yùn)作過程。

第一次迭代：五角形表示的狀態(tài)是個(gè)體第一次訪問的狀態(tài)，也是第一次被錄入搜索樹的狀態(tài)。我們構(gòu)建搜索樹：將當(dāng)前狀態(tài)錄入搜索樹中。使用基于蒙特卡羅樹搜索的策略（兩個(gè)階段），由于當(dāng)前搜索樹中只有當(dāng)前狀態(tài)，全程使用的應(yīng)該是一個(gè)搜索第二階段的默認(rèn)隨機(jī)策略，基于該策略產(chǎn)生一個(gè)直到終止?fàn)顟B(tài)的完整Episode。圖中那些菱形表示中間狀態(tài)和方格表示的終止?fàn)顟B(tài)，在此次迭代過程中并不錄入搜索樹。終止?fàn)顟B(tài)方框內(nèi)的數(shù)字1表示（黑方）在博弈中取得了勝利。此時(shí)我們就可以更新搜索樹種五角形的狀態(tài)價(jià)值，以分?jǐn)?shù)1/1表示從當(dāng)前五角形狀態(tài)開始模擬了一個(gè)Episode，其中獲勝了1個(gè)Episode。

第二次迭代：當(dāng)前狀態(tài)仍然是樹內(nèi)的圓形圖標(biāo)指示的狀態(tài)，從該狀態(tài)開始決定下一步動(dòng)作。根據(jù)目前已經(jīng)訪問過的狀態(tài)構(gòu)建搜索樹，依據(jù)模擬策略產(chǎn)生一個(gè)行為模擬進(jìn)入白色五角形表示的狀態(tài)，并將該狀態(tài)錄入搜索樹，隨后繼續(xù)該次模擬的對(duì)弈直到Episode結(jié)束，結(jié)果顯示黑方失敗，因此我們可以更新新加入搜索樹的五角形節(jié)點(diǎn)的價(jià)值為0/1，而搜索樹種的圓形節(jié)點(diǎn)代表的當(dāng)前狀態(tài)其價(jià)值估計(jì)為1/2，表示進(jìn)行了2次模擬對(duì)弈，贏得了1次，輸了1次。

經(jīng)過前兩次的迭代，當(dāng)位于當(dāng)前狀態(tài)（黑色圓形節(jié)點(diǎn)）時(shí)，當(dāng)前策略會(huì)認(rèn)為選擇某行為進(jìn)入上圖中白色五角形節(jié)點(diǎn)狀態(tài)對(duì)黑方不利，策略將得到更新：當(dāng)前狀態(tài)時(shí)會(huì)個(gè)體會(huì)嘗試選擇其它行為。

第三次迭代：假設(shè)選擇了一個(gè)行為進(jìn)入白色五角形節(jié)點(diǎn)狀態(tài)，將該節(jié)點(diǎn)錄入搜索樹，模擬一次完整的Episode，結(jié)果顯示黑方獲勝，此時(shí)更新新錄入節(jié)點(diǎn)的狀態(tài)價(jià)值為1/1，同時(shí)更新其上級(jí)節(jié)點(diǎn)的狀態(tài)價(jià)值，這里需要更新當(dāng)前狀態(tài)的節(jié)點(diǎn)價(jià)值為2/3，表明在當(dāng)前狀態(tài)下已經(jīng)模擬了3次對(duì)弈，黑方獲勝2次。

隨著迭代次數(shù)的增加，在搜索樹里錄入的節(jié)點(diǎn)開始增多，樹內(nèi)每一個(gè)節(jié)點(diǎn)代表的狀態(tài)其價(jià)值數(shù)據(jù)也越來越豐富。在搜索樹內(nèi)依據(jù)$?$-greedy策略會(huì)使得當(dāng)個(gè)體出于當(dāng)前狀態(tài)（圓形節(jié)點(diǎn)）時(shí)更容易做出到達(dá)圖中五角形節(jié)點(diǎn)代表的狀態(tài)的行為。

第四次迭代：當(dāng)個(gè)體位于當(dāng)前（圓形節(jié)點(diǎn)）狀態(tài)時(shí)，樹內(nèi)策略使其更容易進(jìn)入左側(cè)的藍(lán)色圓形節(jié)點(diǎn)代表的狀態(tài)，此時(shí)錄入一個(gè)新的節(jié)點(diǎn)（五角形節(jié)點(diǎn)），模擬完Episode提示黑方失敗，更新該節(jié)點(diǎn)以及其父節(jié)點(diǎn)的狀態(tài)價(jià)值。

第五次迭代：更新后的策略使得個(gè)體在當(dāng)前狀態(tài)時(shí)仍然有較大幾率進(jìn)入其左側(cè)圓形節(jié)點(diǎn)表示的狀態(tài)，在該節(jié)點(diǎn)，個(gè)體避免了進(jìn)入剛才失敗的那次節(jié)點(diǎn)，錄入了一個(gè)新節(jié)點(diǎn)，基于模擬策略完成一個(gè)完整Episode，黑方獲得了勝利，同樣的更新搜索樹內(nèi)相關(guān)節(jié)點(diǎn)代表的狀態(tài)價(jià)值。

如此反復(fù)，隨著迭代次數(shù)的增加，當(dāng)個(gè)體處于當(dāng)前狀態(tài)時(shí)，其搜索樹將越來越深，那些能夠引導(dǎo)個(gè)體獲勝的搜索樹內(nèi)的節(jié)點(diǎn)將會(huì)被充分的探索，其節(jié)點(diǎn)代表的狀態(tài)價(jià)值也越來越有說服力；同時(shí)個(gè)體也忽略了那些結(jié)果不好的一些節(jié)點(diǎn)（上圖中當(dāng)前狀態(tài)右下方價(jià)值估計(jì)為0/1的節(jié)點(diǎn)）。需要注意的是，仍然要對(duì)這部分節(jié)點(diǎn)進(jìn)行一定程度的探索，以確保這些節(jié)點(diǎn)不會(huì)被完全忽視。

MCTS的優(yōu)點(diǎn)：

• 蒙特卡羅樹搜索是具有高度選擇性的（Highly selective)、導(dǎo)致越好結(jié)果的行為越被優(yōu)先選擇（best-first）的一種搜索方法。

• 它可以動(dòng)態(tài)的評(píng)估各狀態(tài)的價(jià)值，這種動(dòng)態(tài)更新價(jià)值的方法與動(dòng)態(tài)規(guī)劃不同，后者聚焦于整個(gè)狀態(tài)空間，而蒙特卡羅樹搜索是立足于當(dāng)前狀態(tài)，動(dòng)態(tài)更新與該狀態(tài)相關(guān)的狀態(tài)價(jià)值。

• 使用采樣避免了維度災(zāi)難；同樣由于它僅依靠采樣，因此適用于那些“黑盒”模型（black-box models）。

• MCTS是可以高效計(jì)算的、不受時(shí)間限制以及可以并行處理的。

參考：

https://mp.weixin.qq.com/s/4qeHfU9GS4aDWOHsu4Dw2g

記憶增強(qiáng)蒙特卡洛樹搜索細(xì)節(jié)解讀

https://zhuanlan.zhihu.com/p/30458774

如何學(xué)習(xí)蒙特卡羅樹搜索（MCTS）

https://zhuanlan.zhihu.com/p/26335999

蒙特卡洛樹搜索MCTS入門

https://zhuanlan.zhihu.com/p/25345778

蒙特卡洛樹搜索（MCTS）基礎(chǔ)

Game Tree

上面圍棋示例中的搜索樹，在博弈論中，也叫做博弈樹（Game Tree）。

Minimax

極小化極大算法（Minimax）是零和游戲常見的策略。通俗的說法就是：選擇對(duì)自己最有利，而對(duì)對(duì)手最不利的動(dòng)作。

Alpha Beta pruning algorithm

在博弈過程中，我們不僅要思考自己的最優(yōu)走法，還要思考對(duì)手的最優(yōu)走法。而且這個(gè)過程是可以遞歸下去的，直到終局為止。

這樣就會(huì)形成一整套如下所示的策略序列（以圍棋為例，黑棋先下）：

黑最優(yōu)->白最優(yōu)->黑最優(yōu)->白最優(yōu)->…

然后輪到白棋下子：

黑最優(yōu)->白最優(yōu)->黑最優(yōu)->白最優(yōu)->...

這里的紅色字體表示的是已經(jīng)發(fā)生的事件。

可以看的出來，在零和游戲中，我們只需要考慮一方的Game Tree就行了，另一方的Game Tree只是一個(gè)鏡像而已。這樣的話，搜索空間直接就只有原來的一半了。

能不能進(jìn)一步裁剪呢？這里介紹一下Alpha Beta pruning algorithm。

詳細(xì)的步驟參見：

http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html

Minimax with Alpha Beta Pruning

這里只提一下要點(diǎn)：

• $\alpha$是指the maximum lower bound of possible solutions；$\beta$是指the minimum upper bound of possible solutions。

• 我方下棋會(huì)尋找使我方獲得最大值的策略，因此叫做MAX結(jié)點(diǎn)；敵方下棋顯然會(huì)尋找能使我方收益最小的策略，因此叫做MIN結(jié)點(diǎn)。從Game Tree的角度來看，就是：一層MAX結(jié)點(diǎn)->一層MIN結(jié)點(diǎn)->一層MAX結(jié)點(diǎn)->一層MIN結(jié)點(diǎn)->…

• 初始狀態(tài)：根節(jié)點(diǎn)：$\alpha =?\infty ,\beta =\infty$，葉子結(jié)點(diǎn)：包含value值。

• 深度優(yōu)先遍歷Game Tree，利用MAX結(jié)點(diǎn)的值，更新父結(jié)點(diǎn)的$\beta$值，利用MIN結(jié)點(diǎn)的值，更新父結(jié)點(diǎn)的$\alpha$值。

• 一旦出現(xiàn)$\alpha >\beta$的情況，則說明遇到了異常分支，直接剪去該分支即可。

參考

https://zhuanlan.zhihu.com/p/55750669

博弈樹與α-β剪枝

https://segmentfault.com/a/1190000013527949

Minimax和Alpha-beta剪枝算法簡(jiǎn)介，以及以此實(shí)現(xiàn)的井字棋游戲（Tic-tac-toe）

https://materiaalit.github.io/intro-to-ai-17/part2/

Games

MCTS和MC的區(qū)別

上圖是一局圍棋的Game Tree的局部。最下面的葉子結(jié)點(diǎn)給出了黑棋贏棋的百分比。現(xiàn)在的問題是，黑棋該如何走呢？（假設(shè)根節(jié)點(diǎn)為當(dāng)前狀態(tài)）

如果是用蒙特卡洛方法，趨近的會(huì)是其下所有勝率的平均值。例如經(jīng)過蒙特卡洛模擬，會(huì)發(fā)現(xiàn)b1后續(xù)的勝率是49% = (50+48)/2，而b2后續(xù)的勝率是55% = (62+45+58)/3。

于是蒙特卡洛方法說應(yīng)該走b2，因?yàn)?5%比49%的勝率高。但這是錯(cuò)誤的。因?yàn)槿绻灼鍓蚵斆?#xff0c;會(huì)在黑棋走b1的時(shí)候回應(yīng)以w2（盡量降低黑棋的勝率），在黑棋走b2的時(shí)候回應(yīng)以w4（盡量降低黑棋的勝率）。

如果用蒙特卡洛方法做上一百萬次模擬，b1和b2的勝率仍然會(huì)固定在49%和55%，不會(huì)進(jìn)步，永遠(yuǎn)錯(cuò)誤。所以它的結(jié)果存在偏差（Bias），當(dāng)然，也有方差（Variance）。

而蒙特卡洛樹搜索在一段時(shí)間模擬后，b1和b2的勝率就會(huì)向48%和45%收斂，從而給出正確的答案。所以它的結(jié)果不存在偏差（Bias），只存在方差（Variance）。但是，對(duì)于復(fù)雜的局面，它仍然有可能長(zhǎng)期陷入陷阱，直到很久之后才開始收斂到正確答案。

Dyna-2

如果我們把基于模擬的前向搜索應(yīng)用到Dyna算法中來，就變成了Dyna-2算法。

使用該算法的個(gè)體維護(hù)了兩套特征權(quán)重：

• 一套反映了個(gè)體的長(zhǎng)期記憶，該記憶是從真實(shí)經(jīng)歷中使用TD學(xué)習(xí)得到，它反映了個(gè)體對(duì)于某一特定強(qiáng)化學(xué)習(xí)問題的普遍性的知識(shí)、經(jīng)驗(yàn)；

• 另一套反映了個(gè)體的短期記憶，該記憶從基于模擬經(jīng)歷中使用TD搜索得到，它反映了個(gè)體對(duì)于某一特定強(qiáng)化學(xué)習(xí)在特定條件（比如某一Episode、某一狀態(tài)下）下的特定的、局部適用的知識(shí)、經(jīng)驗(yàn)。

總結(jié)

以上是生活随笔為你收集整理的机器学习（三十七）——Integrating Learning and Planning（3）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。