基于蒙特卡罗树搜索的“2048”游戏优化算法

An Algorithm for the Game of 2048 Based on Monte Carlo Tree Search

针对一款单人手机游戏"2048",结合其具有很强不确定性的特点,设计了一种基于蒙特卡罗树搜索(Monte Carlo Tree Search,MCTS)的游戏搜索算法。基本算法分为4步:路径选择、节点扩充、模拟实验和节点更新。在路径选择部分,设计了基于信心上限应用树(UCT)方法的节点选择策略;在模拟实验部分,设计了2种有效的启发式模拟策略。根据游戏局势的难易程度,提出了一种自适应调整搜索次数的优化策略,对基本算法进行改进。使用C++语言开发了"2048"游戏的并行计算机博弈系统。大量实验结果表明,设计的优化算法能够有效地求解"2048"游戏,达到资深玩家的水平。

For a single-player cell phone game 2048,a Monte Carlo tree search(MCTS) based game search algorithm is proposed according to the strong uncertainty of the game.The basic algorithm consists of four parts:path selection,node expansion,simulation experiment,and node update.In path selection,an UCT(upper confidence bounds applied to trees) based node selection strategy is proposed.In simulation experiment,two effective heuristic simulation strategies are designed.And an adaptive strategy that would modify the number of simulations is proposed to improve the basic algorithm,according to the complexity of the game situation.We develop a parallel computer game system of game 2048 using C++ language.Experimental results show that the proposed optimization algorithm can effectively solve the game of 2048,and reach the senior level.