蒙特卡洛樹搜索在游戲“2048”中的運行機制分析

趙丹娜 曾孟佳 黃旭

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

關鍵詞：MCTS；UCT；游戲“2048”

中圖分類號：TP18文獻標志碼：A文章編號：1008-1739（2020）02-64-4

0引言

人工智能（Artificial Intelligence，AI）是長期以來的熱點話題，而計算機博弈（機器博弈）是廣受關注的研究方向。其中最復雜的博弈項目之一———棋類，則是充分檢驗其真實發(fā)展水平的重要手段。在象棋領域，1997年“深藍”擊敗世界排名第一棋手，至此，標志著計算機博弈進入一個新的高度。而在難度更大的圍棋領域，計算機卻鮮有造詣。直到2006年蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）的提出，這一窘境才被打破[1]。之后，計算機博弈相關研究有了跨越性的發(fā)展。

MCTS是在完美信息博弈場景中進行決策的一種通用技術，不僅在圍棋博弈，更是在其他游戲博弈中得到廣泛應用[2-4]，其根據(jù)局面評估算法產(chǎn)生的結果進行不斷地調(diào)整優(yōu)化。2012年，一種基于MCTS并行化方法的提出，極大地提升了MCTS算法的性能[5]。在MCTS中，上限置信區(qū)間（Upper Confidence Bounds for Trees，UCT）算法是一個十分重要的算法，對節(jié)點的最大訪問次數(shù)加以限制。簡言之，MCTS是一種將蒙特卡洛模擬評估與UCT相結合的最優(yōu)優(yōu)化算法[6]?，F(xiàn)今，MCTS被廣泛應用于各類計算機圍棋博弈程序中。本文以“2048”游戲為例，對MCTS算法運行機制進行了簡要分析。

1游戲“2048”

1.1游戲玩法

游戲在4*4棋盤中進行，游戲開始時，計算機方在當前任意空方格里隨機給出2個2，在隨后的走棋過程中，玩家每走一步，計算機隨機在空的方格中給出一個2或4。游戲玩家每次可以選擇上、下、左、右4個行棋策略中的一種（某些格局會少于4種，因為有些方向不可走）走棋，行棋后方格中的數(shù)值按照既定邏輯移動及合并，格局完成轉換[7]。移動合并規(guī)則是移動方向上若有2個相鄰方格的數(shù)值相同則合并，數(shù)值更新為“原數(shù)值*2”。由于游戲玩家應對方式主觀性過大，故本文只針對計算機行子方式進行判斷分析。

游戲結束的判斷方法有2種。第1種：玩家通過對棋盤上數(shù)字的移動，使其累加得到“2048”，則游戲結果為“勝利”；第2種：玩家對棋盤上的數(shù)字進行任意移動，若游戲中出現(xiàn)無效操作，格子全滿，且無法向4個方向中任何一個方向移動（均不能觸發(fā)合并），則游戲結束，游戲結果以游戲全過程中所合并各方格累加和的最大值為游戲最終結果。由于此時的游戲結果沒有達到“2048”，因此本判斷方法不產(chǎn)生游戲勝利的結果。

1.2游戲難點

“2048”的游戲規(guī)則看似簡單，但在實際操作中，每次移動棋盤上均會隨機出現(xiàn)數(shù)字2或4，在給游戲玩家對下一步的動作增加了不確定性的同時，也增添了一定的游戲難度。

“2048”是由玩家與計算機進行對弈的一種信息對稱雙人博弈模型，即在游戲過程中對弈雙方獲取的格局信息完全一致，故移動策略的選擇對接下來的格局至關重要[8]。

游戲進行過程中，玩家盡可能避免移動數(shù)值較大的方塊，因為一旦移動會導致這個游戲局面多個方塊數(shù)值改變，特別是要避免出現(xiàn)數(shù)值較大的方格（如1 024或512）周圍被小數(shù)值方格（如2或4）包圍的局面。

2“2048”中MCTS算法的應用

2.1 MCTS

MCTS是在樹搜索的其中某個節(jié)點上，從當前位置逐步向下延伸搜索，遇到未完全展開的節(jié)點時，則進行單次模擬，即將該節(jié)點作為單次模擬的根節(jié)點，繼續(xù)向下延伸搜索，直到因時間或其他限制因素而停止，并將搜索結果反向傳播回當前根節(jié)點，更新其評估值及訪問次數(shù)，從而獲得該節(jié)點的優(yōu)劣信息做出決策。在實驗條件不變的情況下重復實驗，實驗次數(shù)越多，誤差越小，評估值將越準確[9]。MCTS其實是一種對模擬結果進行不斷反饋調(diào)整的啟發(fā)式搜索算法[10]，搜索流程如圖1所示。

MCTS算法能夠從模擬產(chǎn)生結果的優(yōu)劣去思考、學習如何提高下一次策略的質(zhì)量，并通過多次隨機模擬后得到的評估值來判斷每一個節(jié)點的優(yōu)劣，從而選擇最佳路徑。算法執(zhí)行過程一般分為路徑選擇、擴展、模擬和反向傳播4個階段。

2.2應用

（1）選擇

從根節(jié)點開始選擇最優(yōu)的子節(jié)點，直到達到葉子節(jié)點，即選擇最具搜索潛力的路徑，這里節(jié)點選擇算法采用UCT算法。置信區(qū)間表示的是一個統(tǒng)計上的計算值，是在所有可能的下一節(jié)點中選擇任一節(jié)點，隨機模擬至游戲結束，并將最終值作為返回值（節(jié)點價值），以此類推，然后在節(jié)點中選擇節(jié)點價值最高的節(jié)點作為下一次的選擇節(jié)點[11-13]。如果當前選擇的最優(yōu)子步驟在之后的模擬中多次失敗，則該值變小，從而使另一個同級的子步驟變得更優(yōu)，因此在選擇過程中會減少搜索的廣度，從而減少系統(tǒng)資源的浪費[14]。路徑選擇的實質(zhì)是節(jié)點的選擇，即根據(jù)節(jié)點價值在每一步選擇當前的最優(yōu)節(jié)點，搜索路徑上的所有最優(yōu)節(jié)點組成最優(yōu)路徑。使用UCT算法進行搜索樹樹內(nèi)選擇，其公式為：

假定值保持不變，根據(jù)式（1），訪問次數(shù)越小，式（1）的第2項值越小，則的值越大，認為當前節(jié)點是有價值的節(jié)點；相反，訪問次數(shù)越多，的值越小，則算法會偏向于去尋找訪問次數(shù)越小的節(jié)點。但在實際過程中的值會變。

在游戲“2048”中使用MCTS算法的過程是以當前局面為節(jié)點，在上下左右任一方向的移動及UCT值計算過程分別執(zhí)行100次[15]，進行移動模擬操作，結束后記錄每一次移動得分，并對每一個方向最終結果取平均值，并將4個值做大小比較，選取最大值對應的方向作為最佳移動方向。這里循環(huán)100次的選擇主要從計算的角度考慮，若次數(shù)太少，得到的UCT值可能分布較稀疏，不能得到搜索過程的全局表現(xiàn)；若次數(shù)過大，則計算與搜索過程的復雜度均會增加，加大系統(tǒng)資源開銷。算法流程如圖2所示。

在游戲“2048”中，上下左右選擇任一方向進行移動，每一次移動操作后更新當前局面評估值直至操作滿100次，得到當前最優(yōu)方向，該方向即為當前情況下的最優(yōu)節(jié)點。UCT算法在游戲中的優(yōu)勢在于能夠平衡探測和利用之間的關系，因為在實際情況中由于操作的隨機性，往往會存在節(jié)點價值最高而實際收益不高的情況。

（2）擴展

若當前節(jié)點為非完全展開節(jié)點，則將其作為根節(jié)點，繼續(xù)向下創(chuàng)建一個或者多個子節(jié)點（每次移動后的局面都看成是一個節(jié)點），選擇其中一個，即只有在當前獲得的統(tǒng)計結果不足以計算出下一個節(jié)點時，隨機選擇一個子節(jié)點。故在節(jié)點的擴展過程中，搜索樹會逐漸擴充。而在“2048”中，根據(jù)當前節(jié)點繼續(xù)在上下左右4個方向進行移動選擇。

（3）模擬

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

（4）反向傳播

在模擬過程結束即棋子在棋盤上無法移動時，將該搜索樹其中一個葉節(jié)點的評估值反向更新該節(jié)點的父節(jié)點及其祖先節(jié)點等的價值，即游戲在某一方向移動結束后，從末到首反向移動，更新各節(jié)點的訪問次數(shù)（移動某一方向的次數(shù)），從中得出節(jié)點的訪問次數(shù)和節(jié)點的評估值。

3應用分析

游戲“2048”走棋過程模擬如圖4所示。

從圖4所列舉的6種游戲過程狀態(tài)可以看出，在游戲中會盡量把數(shù)字大的方塊（棋子）固定在一邊，這樣是為了減少游戲中大數(shù)字方塊的移動，避免大量出現(xiàn)數(shù)字無法合并的情況。抽象模型如圖5所示。

游戲中，使用UCT算法對節(jié)點的4個方向依次進行選擇、擴展和模擬，在節(jié)點價值和實際收益間選擇最優(yōu)節(jié)點（最佳移動方向），對本次移動后進行下一步移動方向模擬，以此類推，直至局面無法再移動，此后，自葉節(jié)點（最后一次移動后的局面評估值）至根節(jié)點（此時設為0）進行反向傳播，從而找出最優(yōu)路徑，也就是游戲“2 048”中的每一次局面最佳移動方向。

當出現(xiàn)以下局面時，可以稱之為死局。發(fā)生死局時，玩家沒有別的選擇只能向上移動，由于只有唯一路徑可以選擇，因此玩家失敗的機率也會增加。死局示意圖如圖6所示。

4結束語

本文主要分析了MCTS在游戲“2048”中的運行機制。通過設置上下左右任一方向模擬隨機移動100次，對每一次取得的值累加后取平均，各得到4個方向的局面評估值，由此選擇當前最佳移動方向。仍存在的難點是由于游戲的每一步不僅要選擇最佳移動方向，還要考慮到數(shù)字的合并情況、數(shù)字之間倍數(shù)的聯(lián)系關系等，需要進行下一步的研究。

參考文獻

[1] COULOM R. Efficient Selectivity and Backup Operators in Monte-carlo Tree Search[C]//Proc of the 5th International Conference on Computers and Games，Turin，Italy，2007（4630）： 72-83.

[2]林云川.基于深度學習和蒙特卡洛樹搜索的圍棋博弈研究[D].哈爾濱：哈爾濱工業(yè)大學， 2017.

[3]劉雅靖.基于Alpha Beta搜索算法的計算機博弈的研究與實現(xiàn)[D].大連：大連交通大學， 2012.

[4]許子明.一種2048游戲自動“玩游戲”算法的實現(xiàn)[J].科技風，2018（16）：4.

[5]季輝，丁澤軍.雙人博弈問題中的蒙特卡洛樹搜索算法的改進[J].計算機科學，2018，45（1）：140-143.

[6] GRAF T，LORENZ U，PLATZNER M，et al.Parallel Monte-Carlo Tree Search for HPC systems[C]//Proc of the 17th International Conference on Parallel Processing， Bordeaux，F(xiàn)rance， 2011： 365-376.

[7]于永波.基于蒙特卡洛樹搜索的計算機圍棋博弈研究[D].大連：大連海事大學， 2015.

[8]何璇.計算機博弈在<2048>游戲的研究與應用[D].長沙：湖南師范大學，2015.

[9]劉宇.Monte carlo方法在計算機圍棋中的應用[D].成都：電子科技大學，2012.

[10] BRODERICK A，RYAN B H，PHILIP H. Monte Carlo Tree Search in Hex[J].ICGA Journal，2010，4（2）：251-257.

[11]鄧超，吳霖，陳磊，等.局部UCT算法在圍棋死活題上的性能測試[J].信息技術，2013，37（3）：23-27.

[12]張玉琪.基于靜態(tài)評估的計算機圍棋UCT算法改進研究[D].南昌：南昌航空大學，2015.

[13]孫若瑩，宮義山，趙剛.一種新的博弈樹迭代向前剪枝搜索[J].沈陽工業(yè)大學學報，2017，39（3）：305-310.

[14]周明明，高航，趙國安.UCT算法在計算機圍棋中的應用與改進[J].數(shù)據(jù)采集與處理，2012，27（S2）：330-335.

[15]胡辰坤.基于Cocos2d-x引擎的手機游戲2048及其AI的設計與實現(xiàn)[D].武漢：華中科技大學， 2015.

[16]劉子正，盧超，張瑞友.基于蒙特卡羅樹搜索的“2048”游戲優(yōu)化算法[J].控制工程，2016，23（4）：550-555.