文档介绍：MathorCup竞赛优秀论文
11
44
评委一评分，签名及备注
队号：
10302
评委三评分，签名及备注
评委二评分，签名及备注
选题：
A:2048
评委四。在图1-a中，节点A的值应是节点B和节点C的值中之较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的诸子节点的值中之极小者，此极小值一定小于等于节点D的值，因此亦一定小于节点B的值，这表明，继续搜索节点C的其他诸子节点E, F,…已没有意义，它们不能做任何贡献，于是把以节点C为根的子树全部剪去。这种优化称为Alpha剪枝。在图1-b是与极大值冗余对偶的现象，称为极小值冗余。节点A的值应是节点B和节点C的值中之较小者。现在已知节点B的值小于节点D的值。由于节点C的值应是它的诸子节点的值中之极大者，此极大值一定大于等于节点D的值，因此也大于节点B的值，这表明，继续搜索节点C的其他诸子节点已没有意义，并可以把以节点C为根的子树全部剪去，这种优化称为Beta剪枝。
而Alpha-beta算法是在众多路线里尽可能选择最好的线路。要想通过检查搜索树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜索是很重要的。下面通过比较来进一步了解Random-Max-Trees算法与Alpha-beta剪枝算法的关系。
11
3
对于一个Min节点，若能估计出其倒推值的上确界Beta，并且这个Beta值不大于Min的父节点(Max节点)的估计倒推值的下确界Alpha，即AlphaBeta，则就不必再扩展该Min节点的其余子节点了，因为这些节点的估值对Min父节点的倒推值已无任何影响了，这一过程称为Alpha剪枝。
对于一个Max节点，若能估计出其倒推值的下确界Alpha，并且这个Alpha值不小于Max的父节点(Min节点)的估计倒推值的上确界Beta，即AlphaBeta，则就不必再扩展该Max节点的其余子节点了，因为这些节点的估值对Max父节点的倒推值已无任何影响了。这一过程称为Beta剪枝。
一个Max节点的Alpha值等于其后继节点当前最大的最终倒推值，一个Min节点的Beta值等于其后继节点当前最小的最终倒推值

图1-a 图1-b
采用Alpha-beta剪枝，可以在相同时间内加大Random-Max-Trees的搜索深度，因此可以获得更好的效果。
问题一模型的建立与求解
本论文对2048游戏进行抽象化表述：
我方：（即游戏玩家）每次可以选择上、下、左、右四个行棋策略中的一种（某些格局会少于四种，因为有些方向不可走）。行棋后方块按照既定逻辑移动及合并，格局转换完成。
对方：（计算机）在当前任意空格子里放置一个方块，方块的数值可以是“2”或“4”。放置新方块后，格局转换完成。
胜利条件：出现某个方块的数值为“2048”。
失败条件：格子全满，且无法向四个方向中任何一个方向移动（均不能触发合并）。
这样分析，于是2048游戏就可化成建立一个模型解决信息对称的双人对弈问题。
评价当前格局的价值
在2048中，除了终局外，中间格局并无非常明显的价值评价指标，因此需要
用一些启发式的指标来评价格局。那些分数高的“好”格局是容易引向胜利的格局，而分低的“坏”格局是容易引向失败的格局。
11
3
本文采用了如下几个启发式指标，如下：

孤立空格数字
平滑性
单调性
空格数
对方选择的剪枝

解释：
(1)单调性
单调性指方块从左到右、从上到下均遵从递增或递减。一般来说，越单调的格局越好。
（2）平滑性
是指每个方块与其直接相邻方块数值的差，其中差越小越平滑。例如2旁边是4就比2旁边是128平滑。一般认为越平滑的格局越好。
（3）空格数
这个很好理解，因为一般来说，空格子越少对玩家越不利。所以我们认为空格越多的格局越好。
（4）孤立空格数
这个指标评价空格被分开的程度，空格越分散则格局越差。
（5）对方选择的剪枝
在这个程序中，除了采用Alpha-beta剪枝外，在Min节点还采用了另一种剪枝，即只