论文部分内容阅读
摘 要：2048游戏曾经风靡一时，游戏简单但富有挑战性。这篇文章主要讲述了2048游戏的AI实现，在不进行人为干预的情况下取得游戏胜利。文章详细讨论了该游戏的评估函数和多步分析，并在最终对该算法进行了一些深入性的分析。
关键词：2048游戏；AI；算法；局部最优
一、算法要求
2048游戏规则极其简单，给定一个44的矩阵，玩家控制矩阵中数字的整体移动方向，电脑则会随机在一个空格中生成2或者4，在移动过程中，相同的数字相撞会合并成两数之和，如果有数字超过2048则为游戏胜利，而如果矩阵被填满，并且矩阵中的最大值没有达到2048时，则游戏失败。
我们此次需要完成的是2048游戏的AI，即只通过算法进行方向移动，在不经过任何人为干预的情况下获取游戏胜利。算法优劣的评判标准有三个：一是游戏胜率评估，即超过2048的概率要尽可能大；二是最高分评估，即游戏中所获取的最大值要尽可能大；三是等待时间，即每步之间等待时间不能过长。
二、算法概要
此次主要研究的是2048的AI实现，该AI算法主要分为两个部分。
第一部分是评估函数，确定局部最优情况，最终确定的评估函数算法有两种：一是局部进行评分的算法，在此称为局部最优得分算法；一是尽量贴近最优情况阵型的算法，称为局部最优矩阵算法。
第二部分是完成对多步结果的评估，然后根据多步之后的情况选择当前最优选项作为行动方向。
三、评估函数
（一）局部最优得分算法
对上下左右四个方向产生的结果进行评估，评估方式为建立多个子算法加权得分，而得分最高的方向即为当前行动的最佳方向，下一步向该方向移动，为局部最优策略。由于不同子算法之间评判标准的不同，可能出现相互干扰，甚至相互对立的情况，同时不同时期受到的影响也可能不同，所以我们需要通过调整数字权重以及子算法权重完成优化，找到较好的评判标准，提高胜率。
可参考的评估子算法：可以检测边角值，进行加权求和，数值越大说明大数在边角，更易合并取得更高的分数；检测所有数值的周围数值的情况，差距越小时两者更易进行合并；检测矩阵中最大值，最大值直接反映游戏情况；检测空格数，空格数越多，就有更大机会成功。
（二）局部最优矩阵算法
与局部最优得分算法不同，局部最优矩阵算法是将地图矩阵看着一个整体，寻找到适合的阵型，而不是按具体评分标准进行判断。目前找到的已知的几种最佳合并阵型，将其作为地图的初始权重矩阵，对数字也设置权重，将两者在对应位置的乘积之和作为评判标准，如果在此方向合并后结果评判最优，下一步则向该方向移动。
我们找到来三种比较优秀的阵型进行测试：一是较为常见的蛇形S阵型，这是人类的常见高分策略，也是最易得到的矩阵情况，矩阵优先级为[1，2，3，4，8，7，6，5，9，10，11，12，16，15，14，13]；二是SPD阵型，这种阵型是根据高分算法总结得到的电脑合并矩阵，使矩阵偏向于向某一角进行合并，矩阵优先级为[16，15，12，4，14，13，11，3，10，9，8，2，7，6，5，1]；三是ZSL阵型，与SPD矩阵略有不同，但仍保留向单一角落合并的倾向，矩陣的优先级为[16，15，14，4，13，12，11，3，10，9，8，2，7，6，5，1]。
当前算法在三种优先级权重阵型对应加权作用下，会自然表现出选择最适合当前局面的阵型进行游戏的行为。当然由于在游戏中没有固定方向，所以必须考虑权重矩阵对称和旋转的情况。
四、多步评估
事实上，仅仅靠着优秀的评估函数，游戏AI就可以初步完成，最终获取一定的游戏胜率。但由于游戏过程中会随机生成2和4，局部最优往往不是全局最优，所以我们无法保证随机生成的数字会不会使当前情况变糟。
如果将2048游戏看成两个人的博弈，玩家会选择向某一方向移动来使游戏获取更高的分数，而作为玩家对手的电脑则会选择随机生成一个数字来影响我的选择。我们无法判断对手的好坏，所以玩家在当前情况下冒着极大风险选择的获取最高分数的方向，可能没有影响，但也可能因为对手的妙手而万劫不复，所以游戏获胜的最佳策略是将对手看的极其聪明，即假设电脑每一步生成的数字都是最坏的情况来保证目前选择不会变得更糟糕，而玩家选择的策略不应利益最大，而是以不会出现意外为主。
通过以上分析，我们得到以下思路：利用四叉树来分析多步之后的情况，四叉树的每一枝代表当前游戏的一个方向，每一层代表一步操作，同时需要修剪风险高于利益，使得当前情况变得糟糕的枝干，简化计算的同时保持较高的胜率，而当前最佳移动方向即是在完成枝干修剪后分数最大的枝干代表的方向。
算法的具体实现可参考的有Minimax算法和Alpha-beta剪枝。Minimax算法是一种悲观算法，即每步都假设对方选择最优的情况下，己方进行选择；而Alpha-beta剪枝则可以简化计算量，大体思路为我们不需要构建完整的树，其中当前格局无法找到最好情况下，我们应该返回父节点，而舍弃当前节点。两者的结合可以完成2048游戏的多步分析，使胜率达到较高水平。
五、分析与总结
（一）局部最优得分算法
在此次游戏的局部评分算法的研究中，简单的评分子算法比较容易实现，如查找最大值之类算法花费时间并不算太多，各个独立算法实现较为简单。问题主要出在权重配比的方面，多个子算法之间相互干扰，并且不同时期的比重也会有所不同，所以调节较为困难。
（二）局部最优矩阵算法
与局部最优得分算法相比，只看整体的局部最优矩阵算法在权重调整方面更显优势，但却更缺乏灵活性，只向特定的阵型倾斜代表着必然忽略不少优秀的情况，导致在中途的适应性比不上局部最优得分算法，较为死板，但胜在调试简单，计算相对偏少，评估表现较为优秀，配合上多步评估可以取得十分不错的结果。
（三）多步评估
如果只需要实现简单的AI，那么使用局部最优的策略就可以完成，但要进一步提升胜率，就必须考虑通过四叉树来预判多步之后的情况。不过因为游戏中是随机在空格中生成数字，所以简单的四叉树的遍历效果会大打折扣，故需要考虑风险与收益的情况，从而剪去高风险的枝叶。整个过程是依次递进，总体思路较为清晰，实现不算困难。
关键词：2048游戏；AI；算法；局部最优
一、算法要求
2048游戏规则极其简单，给定一个44的矩阵，玩家控制矩阵中数字的整体移动方向，电脑则会随机在一个空格中生成2或者4，在移动过程中，相同的数字相撞会合并成两数之和，如果有数字超过2048则为游戏胜利，而如果矩阵被填满，并且矩阵中的最大值没有达到2048时，则游戏失败。
我们此次需要完成的是2048游戏的AI，即只通过算法进行方向移动，在不经过任何人为干预的情况下获取游戏胜利。算法优劣的评判标准有三个：一是游戏胜率评估，即超过2048的概率要尽可能大；二是最高分评估，即游戏中所获取的最大值要尽可能大；三是等待时间，即每步之间等待时间不能过长。
二、算法概要
此次主要研究的是2048的AI实现，该AI算法主要分为两个部分。
第一部分是评估函数，确定局部最优情况，最终确定的评估函数算法有两种：一是局部进行评分的算法，在此称为局部最优得分算法；一是尽量贴近最优情况阵型的算法，称为局部最优矩阵算法。
第二部分是完成对多步结果的评估，然后根据多步之后的情况选择当前最优选项作为行动方向。
三、评估函数
（一）局部最优得分算法
对上下左右四个方向产生的结果进行评估，评估方式为建立多个子算法加权得分，而得分最高的方向即为当前行动的最佳方向，下一步向该方向移动，为局部最优策略。由于不同子算法之间评判标准的不同，可能出现相互干扰，甚至相互对立的情况，同时不同时期受到的影响也可能不同，所以我们需要通过调整数字权重以及子算法权重完成优化，找到较好的评判标准，提高胜率。
可参考的评估子算法：可以检测边角值，进行加权求和，数值越大说明大数在边角，更易合并取得更高的分数；检测所有数值的周围数值的情况，差距越小时两者更易进行合并；检测矩阵中最大值，最大值直接反映游戏情况；检测空格数，空格数越多，就有更大机会成功。
（二）局部最优矩阵算法
与局部最优得分算法不同，局部最优矩阵算法是将地图矩阵看着一个整体，寻找到适合的阵型，而不是按具体评分标准进行判断。目前找到的已知的几种最佳合并阵型，将其作为地图的初始权重矩阵，对数字也设置权重，将两者在对应位置的乘积之和作为评判标准，如果在此方向合并后结果评判最优，下一步则向该方向移动。
我们找到来三种比较优秀的阵型进行测试：一是较为常见的蛇形S阵型，这是人类的常见高分策略，也是最易得到的矩阵情况，矩阵优先级为[1，2，3，4，8，7，6，5，9，10，11，12，16，15，14，13]；二是SPD阵型，这种阵型是根据高分算法总结得到的电脑合并矩阵，使矩阵偏向于向某一角进行合并，矩阵优先级为[16，15，12，4，14，13，11，3，10，9，8，2，7，6，5，1]；三是ZSL阵型，与SPD矩阵略有不同，但仍保留向单一角落合并的倾向，矩陣的优先级为[16，15，14，4，13，12，11，3，10，9，8，2，7，6，5，1]。
当前算法在三种优先级权重阵型对应加权作用下，会自然表现出选择最适合当前局面的阵型进行游戏的行为。当然由于在游戏中没有固定方向，所以必须考虑权重矩阵对称和旋转的情况。
四、多步评估
事实上，仅仅靠着优秀的评估函数，游戏AI就可以初步完成，最终获取一定的游戏胜率。但由于游戏过程中会随机生成2和4，局部最优往往不是全局最优，所以我们无法保证随机生成的数字会不会使当前情况变糟。
如果将2048游戏看成两个人的博弈，玩家会选择向某一方向移动来使游戏获取更高的分数，而作为玩家对手的电脑则会选择随机生成一个数字来影响我的选择。我们无法判断对手的好坏，所以玩家在当前情况下冒着极大风险选择的获取最高分数的方向，可能没有影响，但也可能因为对手的妙手而万劫不复，所以游戏获胜的最佳策略是将对手看的极其聪明，即假设电脑每一步生成的数字都是最坏的情况来保证目前选择不会变得更糟糕，而玩家选择的策略不应利益最大，而是以不会出现意外为主。
通过以上分析，我们得到以下思路：利用四叉树来分析多步之后的情况，四叉树的每一枝代表当前游戏的一个方向，每一层代表一步操作，同时需要修剪风险高于利益，使得当前情况变得糟糕的枝干，简化计算的同时保持较高的胜率，而当前最佳移动方向即是在完成枝干修剪后分数最大的枝干代表的方向。
算法的具体实现可参考的有Minimax算法和Alpha-beta剪枝。Minimax算法是一种悲观算法，即每步都假设对方选择最优的情况下，己方进行选择；而Alpha-beta剪枝则可以简化计算量，大体思路为我们不需要构建完整的树，其中当前格局无法找到最好情况下，我们应该返回父节点，而舍弃当前节点。两者的结合可以完成2048游戏的多步分析，使胜率达到较高水平。
五、分析与总结
（一）局部最优得分算法
在此次游戏的局部评分算法的研究中，简单的评分子算法比较容易实现，如查找最大值之类算法花费时间并不算太多，各个独立算法实现较为简单。问题主要出在权重配比的方面，多个子算法之间相互干扰，并且不同时期的比重也会有所不同，所以调节较为困难。
（二）局部最优矩阵算法
与局部最优得分算法相比，只看整体的局部最优矩阵算法在权重调整方面更显优势，但却更缺乏灵活性，只向特定的阵型倾斜代表着必然忽略不少优秀的情况，导致在中途的适应性比不上局部最优得分算法，较为死板，但胜在调试简单，计算相对偏少，评估表现较为优秀，配合上多步评估可以取得十分不错的结果。
（三）多步评估
如果只需要实现简单的AI，那么使用局部最优的策略就可以完成，但要进一步提升胜率，就必须考虑通过四叉树来预判多步之后的情况。不过因为游戏中是随机在空格中生成数字，所以简单的四叉树的遍历效果会大打折扣，故需要考虑风险与收益的情况，从而剪去高风险的枝叶。整个过程是依次递进，总体思路较为清晰，实现不算困难。