蒙特卡洛树搜索在游戏“2048”中的运行机制分析
发布时间：2021-03-04 18:11
对蒙特卡洛树搜索（Monte Carlo Tree Search,MCTS）算法在游戏"2048"中的运行机制进行了分析研究。在MCTS过程中,利用上限置信区间（Upper Confidence Bound Apply to Tree,UCT）算法计算当前局面所有可移动4个方向节点的UCT值,选择使节点价值最大的方向作为下一次的移动方向,再经过扩展、模拟阶段,直到达到游戏限制范围后进行反向传播,以当前路径的局面评估值对其父节点、祖父节点直至根节点的节点价值进行更新,以此得到最佳移动方向,进而得到最优选择策略。
【文章来源】：计算机与网络. 2020,46(02)
【文章页数】：4 页
【部分图文】：
MCTS算法流程图
在游戏“2048”中使用MCTS算法的过程是以当前局面为节点，在上下左右任一方向的移动及UCT值计算过程分别执行100次[15]，进行移动模拟操作，结束后记录每一次移动得分，并对每一个方向最终结果取平均值，并将4个值做大小比较，选取最大值对应的方向作为最佳移动方向。这里循环100次的选择主要从计算的角度考虑，若次数太少，得到的UCT值可能分布较稀疏，不能得到搜索过程的全局表现；若次数过大，则计算与搜索过程的复杂度均会增加，加大系统资源开销。算法流程如图2所示。在游戏“2048”中，上下左右选择任一方向进行移动，每一次移动操作后更新当前局面评估值直至操作满100次，得到当前最优方向，该方向即为当前情况下的最优节点。UCT算法在游戏中的优势在于能够平衡探测和利用之间的关系，因为在实际情况中由于操作的随机性，往往会存在节点价值最高而实际收益不高的情况。
从当前节点开始模拟接下来可能出现的结果，一直循环多次，直到游戏结束。游戏中，不同的方向不仅会导致棋子个数的不同，更重要的是要考虑到棋子及其周围棋子所代表的数字，如果移动后棋子周围的棋子数值远大于该棋子，则这种移动并非最优策略。因此在实际操作中，应尽可能的减少方块的个数，尽量把棋子往合并数目越多的那一个方向移动，同理也就增加了局面评估值[16]。游戏“2048”的蒙特卡洛树拓展过程模拟如图3所示。(4）反向传播
【参考文献】：
期刊论文
[1]一种2048游戏自动“玩游戏”算法的实现[J]. 许子明. 科技风. 2018(16)
[2]双人博弈问题中的蒙特卡洛树搜索算法的改进[J]. 季辉,丁泽军. 计算机科学. 2018(01)
[3]一种新的博弈树迭代向前剪枝搜索[J]. 孙若莹,宫义山,赵刚. 沈阳工业大学学报. 2017(03)
[4]基于蒙特卡罗树搜索的“2048”游戏优化算法[J]. 刘子正,卢超,张瑞友. 控制工程. 2016(04)
[5]局部UCT算法在围棋死活题上的性能测试[J]. 邓超,吴霖,陈磊,袁梅宇. 信息技术. 2013(03)
[6]UCT算法在计算机围棋中的应用与改进[J]. 周明明,高航,赵国安. 数据采集与处理. 2012(S2)
硕士论文
[1]基于静态评估的计算机围棋UCT算法改进研究[D]. 张玉琪.南昌航空大学 2015
[2]计算机博弈在<2048>游戏的研究与应用[D]. 何璇.湖南师范大学 2015
[3]基于Cocos2d-x引擎的手机游戏2048及其AI的设计与实现[D]. 胡辰坤.华中科技大学 2015
[4]基于蒙特卡洛树搜索的计算机围棋博弈研究[D]. 于永波.大连海事大学 2015
[5]基于Alpha-Beta搜索算法的计算机博弈的研究与实现[D]. 刘雅靖.大连交通大学 2012
[6]Monte-carlo方法在计算机围棋中的应用[D]. 刘宇.电子科技大学 2012
本文编号：3063664
【文章来源】：计算机与网络. 2020,46(02)
【文章页数】：4 页
【部分图文】：
MCTS算法流程图
在游戏“2048”中使用MCTS算法的过程是以当前局面为节点，在上下左右任一方向的移动及UCT值计算过程分别执行100次[15]，进行移动模拟操作，结束后记录每一次移动得分，并对每一个方向最终结果取平均值，并将4个值做大小比较，选取最大值对应的方向作为最佳移动方向。这里循环100次的选择主要从计算的角度考虑，若次数太少，得到的UCT值可能分布较稀疏，不能得到搜索过程的全局表现；若次数过大，则计算与搜索过程的复杂度均会增加，加大系统资源开销。算法流程如图2所示。在游戏“2048”中，上下左右选择任一方向进行移动，每一次移动操作后更新当前局面评估值直至操作满100次，得到当前最优方向，该方向即为当前情况下的最优节点。UCT算法在游戏中的优势在于能够平衡探测和利用之间的关系，因为在实际情况中由于操作的随机性，往往会存在节点价值最高而实际收益不高的情况。
从当前节点开始模拟接下来可能出现的结果，一直循环多次，直到游戏结束。游戏中，不同的方向不仅会导致棋子个数的不同，更重要的是要考虑到棋子及其周围棋子所代表的数字，如果移动后棋子周围的棋子数值远大于该棋子，则这种移动并非最优策略。因此在实际操作中，应尽可能的减少方块的个数，尽量把棋子往合并数目越多的那一个方向移动，同理也就增加了局面评估值[16]。游戏“2048”的蒙特卡洛树拓展过程模拟如图3所示。(4）反向传播
【参考文献】：
期刊论文
[1]一种2048游戏自动“玩游戏”算法的实现[J]. 许子明. 科技风. 2018(16)
[2]双人博弈问题中的蒙特卡洛树搜索算法的改进[J]. 季辉,丁泽军. 计算机科学. 2018(01)
[3]一种新的博弈树迭代向前剪枝搜索[J]. 孙若莹,宫义山,赵刚. 沈阳工业大学学报. 2017(03)
[4]基于蒙特卡罗树搜索的“2048”游戏优化算法[J]. 刘子正,卢超,张瑞友. 控制工程. 2016(04)
[5]局部UCT算法在围棋死活题上的性能测试[J]. 邓超,吴霖,陈磊,袁梅宇. 信息技术. 2013(03)
[6]UCT算法在计算机围棋中的应用与改进[J]. 周明明,高航,赵国安. 数据采集与处理. 2012(S2)
硕士论文
[1]基于静态评估的计算机围棋UCT算法改进研究[D]. 张玉琪.南昌航空大学 2015
[2]计算机博弈在<2048>游戏的研究与应用[D]. 何璇.湖南师范大学 2015
[3]基于Cocos2d-x引擎的手机游戏2048及其AI的设计与实现[D]. 胡辰坤.华中科技大学 2015
[4]基于蒙特卡洛树搜索的计算机围棋博弈研究[D]. 于永波.大连海事大学 2015
[5]基于Alpha-Beta搜索算法的计算机博弈的研究与实现[D]. 刘雅靖.大连交通大学 2012
[6]Monte-carlo方法在计算机围棋中的应用[D]. 刘宇.电子科技大学 2012
本文编号：3063664
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3063664.html
