基于蒙特卡罗模拟和Z检验的“2048”游戏并行优化算法

Monte Carlo Simulation and Z-test Based Parallel Algorithm for the Game of 2048

针对一款单人手机游戏"2048",结合其具有很强不确定性的特点,设计一种基于蒙特卡罗模拟和Z检验的并行游戏搜索算法.算法总共分为四部分:首先通过少量的模拟实验,对各个可选节点进行初步评估;然后,使用Z检验确定缺乏搜索潜力的节点,对其进行剪枝;之后,对剩下的节点进行较多次数的模拟实验;最后,综合两组模拟实验的结果,对可选节点进行最终评估,并选择最优节点.算法核心部分能够实现并行计算,所以使用C++语言开发了并行计算机博弈系统.大量实验结果表明,本文设计的优化算法能够快速、有效地求解"2048"游戏,达到资深玩家的水平.

For a single-player cell phone game 2048,a Monte Carlo Simulation and Z-test based parallel game search algorithm is proposed according to the strong uncertainty of the game. The algorithm consists of four parts. In the first part,a small number of simulation experiments are conducted to preliminarily assess the feasible nodes. In the second part,Z-test is applied to determine and prune the nodes that are lack of search potential. In the third part,a large number of simulation experiments are conducted from the remaining node. In the last part,all the data of the simulation experiments are integrated to evaluate the remaining nodes and the best node is selected. The main parts of the algorithm are parallelizable,so a parallel computer game system of game 2048 using C ＋ ＋ language was developed. Experimental results showthat the proposed optimization algorithm can effectively solve the game of 2048,and reach the senior level.