發(fā)布時(shí)間：2021-03-04 18:11

　　對蒙特卡洛樹搜索（Monte Carlo Tree Search,MCTS）算法在游戲"2048"中的運(yùn)行機(jī)制進(jìn)行了分析研究。在MCTS過程中,利用上限置信區(qū)間（Upper Confidence Bound Apply to Tree,UCT）算法計(jì)算當(dāng)前局面所有可移動(dòng)4個(gè)方向節(jié)點(diǎn)的UCT值,選擇使節(jié)點(diǎn)價(jià)值最大的方向作為下一次的移動(dòng)方向,再經(jīng)過擴(kuò)展、模擬階段,直到達(dá)到游戲限制范圍后進(jìn)行反向傳播,以當(dāng)前路徑的局面評估值對其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)直至根節(jié)點(diǎn)的節(jié)點(diǎn)價(jià)值進(jìn)行更新,以此得到最佳移動(dòng)方向,進(jìn)而得到最優(yōu)選擇策略。 

【文章來源】：計(jì)算機(jī)與網(wǎng)絡(luò). 2020,46(02)

【文章頁數(shù)】：4 頁

【部分圖文】：

MCTS算法流程圖

在游戲“2048”中使用MCTS算法的過程是以當(dāng)前局面為節(jié)點(diǎn)，在上下左右任一方向的移動(dòng)及UCT值計(jì)算過程分別執(zhí)行100次[15]，進(jìn)行移動(dòng)模擬操作，結(jié)束后記錄每一次移動(dòng)得分，并對每一個(gè)方向最終結(jié)果取平均值，并將4個(gè)值做大小比較，選取最大值對應(yīng)的方向作為最佳移動(dòng)方向。這里循環(huán)100次的選擇主要從計(jì)算的角度考慮，若次數(shù)太少，得到的UCT值可能分布較稀疏，不能得到搜索過程的全局表現(xiàn)；若次數(shù)過大，則計(jì)算與搜索過程的復(fù)雜度均會(huì)增加，加大系統(tǒng)資源開銷。算法流程如圖2所示。在游戲“2048”中，上下左右選擇任一方向進(jìn)行移動(dòng)，每一次移動(dòng)操作后更新當(dāng)前局面評估值直至操作滿100次，得到當(dāng)前最優(yōu)方向，該方向即為當(dāng)前情況下的最優(yōu)節(jié)點(diǎn)。UCT算法在游戲中的優(yōu)勢在于能夠平衡探測和利用之間的關(guān)系，因?yàn)樵趯?shí)際情況中由于操作的隨機(jī)性，往往會(huì)存在節(jié)點(diǎn)價(jià)值最高而實(shí)際收益不高的情況。

從當(dāng)前節(jié)點(diǎn)開始模擬接下來可能出現(xiàn)的結(jié)果，一直循環(huán)多次，直到游戲結(jié)束。游戲中，不同的方向不僅會(huì)導(dǎo)致棋子個(gè)數(shù)的不同，更重要的是要考慮到棋子及其周圍棋子所代表的數(shù)字，如果移動(dòng)后棋子周圍的棋子數(shù)值遠(yuǎn)大于該棋子，則這種移動(dòng)并非最優(yōu)策略。因此在實(shí)際操作中，應(yīng)盡可能的減少方塊的個(gè)數(shù)，盡量把棋子往合并數(shù)目越多的那一個(gè)方向移動(dòng)，同理也就增加了局面評估值[16]。游戲“2048”的蒙特卡洛樹拓展過程模擬如圖3所示。(4）反向傳播

【參考文獻(xiàn)】：
期刊論文
[1]一種2048游戲自動(dòng)“玩游戲”算法的實(shí)現(xiàn)[J]. 許子明.  科技風(fēng). 2018(16)
[2]雙人博弈問題中的蒙特卡洛樹搜索算法的改進(jìn)[J]. 季輝,丁澤軍.  計(jì)算機(jī)科學(xué). 2018(01)
[3]一種新的博弈樹迭代向前剪枝搜索[J]. 孫若瑩,宮義山,趙剛.  沈陽工業(yè)大學(xué)學(xué)報(bào). 2017(03)
[4]基于蒙特卡羅樹搜索的“2048”游戲優(yōu)化算法[J]. 劉子正,盧超,張瑞友.  控制工程. 2016(04)
[5]局部UCT算法在圍棋死活題上的性能測試[J]. 鄧超,吳霖,陳磊,袁梅宇.  信息技術(shù). 2013(03)
[6]UCT算法在計(jì)算機(jī)圍棋中的應(yīng)用與改進(jìn)[J]. 周明明,高航,趙國安.  數(shù)據(jù)采集與處理. 2012(S2)

碩士論文
[1]基于靜態(tài)評估的計(jì)算機(jī)圍棋UCT算法改進(jìn)研究[D]. 張玉琪.南昌航空大學(xué) 2015
[2]計(jì)算機(jī)博弈在<2048>游戲的研究與應(yīng)用[D]. 何璇.湖南師范大學(xué) 2015
[3]基于Cocos2d-x引擎的手機(jī)游戲2048及其AI的設(shè)計(jì)與實(shí)現(xiàn)[D]. 胡辰坤.華中科技大學(xué) 2015
[4]基于蒙特卡洛樹搜索的計(jì)算機(jī)圍棋博弈研究[D]. 于永波.大連海事大學(xué) 2015
[5]基于Alpha-Beta搜索算法的計(jì)算機(jī)博弈的研究與實(shí)現(xiàn)[D]. 劉雅靖.大連交通大學(xué) 2012
[6]Monte-carlo方法在計(jì)算機(jī)圍棋中的應(yīng)用[D]. 劉宇.電子科技大學(xué) 2012



本文編號：3063664