2048游戏是一单人游戏。游戏中的操作对象是网格中的带数字的“瓦片”方块。单次游戏中，玩家可以使用方向键使所有方块向目标方向移动并对齐，如果两个带有相同数字的方块在移动方向上碰撞，则它们会合并为一个方块，且新方块所带的数字变为两者之和。每次移动后，会有一个数值为2或4的新方块出现在空白位置。玩家的最终目标是努力合并出更大的数字，一般的2048游戏中合出2048即可，该游戏也正因此得名。

该游戏自2014年初由开发者Cirulli开发并发布，因其简单操作方式和具有挑战性，十分受国内外玩家的欢迎。对于其中高分策略的研究十分有意义，随着游戏的火爆，对于该游戏策略的研究和实现也越来越多。通过近段时间在学术论文方向和相关开源项目中的了解和学习，我大致了解到以下三个实现方向。

(1) 基于简单估值函数。常见的是简单的对四个可选方向移动后的得分进行评价，由于得分越高的步骤意味着更大、更多的数字合并，故对于要求不高的简单ai而言已经够用了。但显然这种简单的估值是不具备足够稳定性的。比如在某个局势A下，虽然不同的决策方向很有可能存在相同的得分，但是在接下来的局面子树中，相差的结果可能是天壤之别。简而言之，简单的通过合并得分作为估值函数的策略是不稳定的。

(2) 基于强化学习。值得一提的是，有人通过一种变种的时序差分强化学习技术实现了一个表现不错的ai，相比较于其他的方案可谓是十分抢眼^[1]。使用强化学习技术，在不需要人的指导，而只靠自己的试错经历学习演变，就实现了一个高效的策略^[2]。但就结果看来与基于博弈树的剪枝优化搜索算法的成功概率不相上下。考虑到前期巨量的训练学习开支，我认为可以在本研究结束后再做后续学习。

(3) 基于博弈树（game tree）的搜索。在博弈论中，博弈树是一个有向图，其树节点表示对弈的局面，其有向边表示选择的行动，对于任意一个非叶节点所表示的局面，不同的边所表示的不同的走法会将局面变化为子节点所表示的局面^[3]。理论上，通过对博弈树的生成和搜索，能达到对局势走向的把握，而且通过一系列的优化算法，能实现十分高效的决策ai。

这三个方向中我觉得第三种能高效且准确的实现，比较适合我的研究，所以我做了进一步研究。

博弈论是研究理性决策者之间对抗策略的数学模型^[4]，在人工智能领域十分重要。在常见的棋类游戏中应用博弈论指导，可以将比赛抽象为有限状态零和完全信息两人博弈模型。如果在2048游戏中，把随机置放新方块的工作看作另一位玩家的行为，游戏结果离散为达到目标与否，即可抽象为该博弈模型。且在两方零和博弈中任意局面下，总有一方存在必胜策略。因为如果我们并不能找到这样的一个必胜策略，就意味着我们不论如何行动，对手总有办法阻止我们的胜利，而且由于游戏是零和的，即意味着对手有必胜策略。

对于此类两方零和博弈，常见的可用Minimax算法和Alpha-Beta剪枝改进算法去处理。

极小化极大值算法（Minimax）^[5][6]。该算法在寻找必胜策略的理论特性上是十分完美的。构建决策树并深度优先搜索遍历决策树，通过自下而上的评价传递选择，可以找出当前格局下的更好情况的下确界，在对方的完美决策下我方尽可能地少损失。虽然看起来有些消极，不过考虑到理论最优解是看对手够不够愚蠢，Minimax算法其实是保守谨慎的。但是Minimax算法在实际应用中有很明显的缺陷。若要完美决策所需遍历的博弈树节点数一般是天文数字，所以一般的都结合估值函数以缩小搜索深度。

Alpha-Beta剪枝算法。在Minimax的基础上，该算法通过剪枝来减少分支因子以实现性能大幅提升^[7]。去掉明显劣势的走法分支树的访问（如从当前节点搜索下去后续走法存在比之前走法还差的局面时剪枝），在更少的搜索开支情况下得到完全相同于Minimax的结果。而且相比较于通过采样估计（即蒙特卡洛模拟），这种较为激进的减少分支因子的手段而言，在决策树分支因子不多（Alt;=4,Blt;=15）的2048游戏中，Alpha-Beta剪枝算法显然更加合适，则更具备应用价值。