针对目前流行的2048游戏，有人实现了一个可以高概率（高于90%）赢得游戏的AI程序，笔者简单介绍一下AI算法关于stackoverflow框架和实现思路。不过这个回答主要集中在启发式函数的选择上，并没有详细解释AI使用的核心算法。本文将主要分为两部分。第一部分介绍了其中使用的基本算法，即Minimax和Alpha-beta剪枝；第二部分分析了作者的具体实现。2048的基本算法本质上可以抽象为一个信息对称的双人博弈模型（玩家向四个方向之一移动，然后计算机在某个空白处填入2或4）。这里的“信息对称”是指在任何时刻，双方对格局的信息完全相同，走棋策略只取决于对下一个格局的推理。作者使用的核心算法是游戏模型中常用的带有Alpha-beta剪枝的Minimax。该算法也常用于国际象棋等信息对称的博弈AI中。Minimax首先介绍了没有剪枝的Minimax。首先，本文将通过一个简单的例子来说明Minimax算法的思想和决策方法。问题现在考虑这样一个游戏：有A、B、C三个盘子，每个盘子里放着三张钞票。A放1,20,50；B投入5、10、100；C放1、5、20。单位是“元”。有两个人，A和B，他们都可以自由地检查三个盘子和放在上面的钞票。游戏分为三个步骤：A从三个盘子中选择一个。B从A选的盘子里拿出两张钞票递给A，A从B给的两张钞票中选一张拿走。其中，A的目标是尽可能拿到面额大的钞票，B的目标是让A最终拿到的钞票面额尽可能小。接下来用Minimax算法来解决这个问题。基本思路一般解决类游戏问题的自然思路是将模式组织成一棵树，树的每个节点代表一个模式，父子关系是指父模式一步之后可以到达子模式.Minimax也不例外，它通过搜索以当前模式为根的模式树来决定下一步的选择。所有模式树搜索算法的核心是对每个模式值的评估。Minimax算法基于以下简单的思想来确定形态的价值：Minimax是一种悲观算法，即假设对手的每一步都会将我们引向目前理论价值最小的形态方向，即对手具有完美的决策能力。所以我们的策略应该是在我们最坏的情况下选择对方能做到的最好的，也就是让对方在完美决策下对我造成的损失最小。Minimax并没有找到理论最优解，因为理论最优解往往取决于对手是否足够愚蠢。在Minimax中，我们可以完全控制主动权。如果对手的每一步决策都是完美的，那么我们就可以达到预期的最小损失模式。如果对方没有做出完美的决定，我方可能会达到比预期的最悲观情景更好的结局。总之，我们这边就是在最坏的情况下选择最好的。上面的表述有些抽象，下面看具体的例子。解题下图是上述例题的模式树：注意，由于例题模式的数量很少，我们可以给出一个完整的模式树。在这种情况下我可以找到Minimax算法的全局最优解。在实际情况下，模式树非常大，即使是计算机也无法给出一棵完整的树，所以我们往往只能搜索到一定深度，此时只能找到局部最优解。我们从A的角度考虑。其中，方形节点表示轮到我方（A），三角形表示轮到对方（B）。经过三轮比赛（我方-对手-我方），进入决赛。黄色的叶子代表所有可能的结局。从甲方的角度来看，既然最终的收益可以用纸币的面值来衡量，那么我们自然可以用甲方在结局中获得的纸币的面值来代表最终版图的价值。接下来，考虑倒数第二层节点。在这些节点上，轮到我们去选择，所以我们应该引入一个可选的最大值模式，这样每个节点的值就是它的子节点的最大值：这些轮到我们的节点称为最大节点，而max节点的值是其子节点的最大值。倒数第三层轮到对手来选择，假设对手会想尽办法把情况引入到我们的值最小的模式中，所以这些节点的值取决于子节点的最小值。这些轮到另一边的节点称为最小节点。最后，根节点是最大节点，所以这个值取决于叶子节点的最大值。完整赋值的最终模式树如下：总结一下Minimax算法的步骤：首先确定最大搜索深度D，D可能到达终点，也可能是中间模式。在最大深度为D的模式树的叶子节点上，使用预定义的价值评估函数评估叶子节点的价值。从下往上给非叶子节点赋值。其中，max节点取子节点的最大值，min节点取子节点的最小值。每次轮到我们（一定是在模式树中的某个max节点），选择其值等于这个max节点值的子节点路径。在上面的例子中，根节点的值为20，也就是说如果对手每一步都做出了完美的决定，我们根据上面的算法最终可以得到20元，这是我们在Minimax算法下的最佳决定。模式转换路径如下图红色路径所示：对于实际问题中的Minimax，这里有几点需要再次强调：实际问题一般无法构造完整的模式树，因此需要确定一个最大深度D，并且每次D层最多从当前模式向下计算。由于以上原因，Minimax一般寻找局部最优解而不是全局最优解。搜索深度越大，越有可能找到更好的解，但计算时间会呈指数增长。也正是因为不可能一次构造出完整的模式树，所以在实际问题中，Minimax一般是边玩游戏边计算局部模式树，而不是只计算一次，但计算出来的中间结果可以缓存起来。#p#Alpha-beta剪枝简单的Minimax算法在计算复杂度方面存在很大问题。由于要搜索的节点数随最大深度呈指数级增长，而算法的效果往往与深度有关，这极大地限制了算法的效果。Alpha-beta剪枝是对Minimax的补充和改进。使用Alpha-beta剪枝后，我们不需要构造和搜索最大深度D内的所有节点。在构造过程中，如果发现当前模式无法找到更好的解，我们将停在这个模式和下面.搜索，即剪枝。Alpha-beta基于这样一个简单的想法：永远记住当前已知的最佳选择。如果无法从当前模式中找到比已知最优解更好的解，则停止该模式的分支。搜索（剪枝），回到父节点继续搜索。Alpha-beta算法可以看作是Minimax的变体。基本方法是从根节点开始，以深度优先的方式构建模式树。在构造每个节点时，会读取该节点的alpha和beta这两个值，其中alpha表示搜索当前节点时已知的最佳选择的下界，beta表示最坏结果的上界从这个节点。由于我们假设对手会把局面引向最坏的结局之一，当beta小于alpha时，意味着无论从这里开始的最终结局是什么，其上限值也都低于已知的最优解，也就是说，往下找不到更好的解，所以会被剪枝。下面也结合上面的例子介绍Alpha-beta剪枝算法的工作原理。我们从根节点开始，详细说明使用Alpha-beta的每一步：根节点的alpha和beta分别初始化为-∞和+∞。深度优先搜索第一个子节点，而不是叶节点，所以alpha和beta是从父节点继承的，分别为-∞和+∞。搜索第三层的第一个孩子，如上。搜索第四层，到达叶子节点，使用评价函数得到这个节点的评价值为1，这个叶子节点的父节点是max节点，所以它的alpha值更新为1，表示较低的这个节点的值的bound为1，再看另一个子节点，值为20，大于当前的alpha值，所以更新alpha值为20，此时最左边节点的所有子树在第三层已经搜索完毕，作为max节点，更新其真实值为当前alpha值：20。由于其父节点（第二层最左边的节点）为min节点，更新其父节点beta值到20，表示这个节点的值最多为20。在第二层及其子树中搜索最左边节点的第二个子节点。按照上面的逻辑，值为50（注意第二层最左边节点的beta值必须传给子节点）。由于50大于20，因此不会更新最小节点的beta值。搜索第二层最左边节点的第三个子节点。读完第一个叶子节点，发现第三个孩子的alpha=beta，意味着这个节点下不会有更好的解，所以剪枝。继续搜索B分支。查找B分支的第一个孩子后，发现B分支的alpha为20，beta为10。这意味着B分支节点的最大值不会超过10，而我们已经取20在A分支。此时满足alpha大于等于beta的剪枝条件，所以剪枝B。并将B分支的节点值设置为10，注意这个10不一定是这个节点的真实值，只是在线而已。B节点的真实值可能是5、1，或者任何小于10的值。不过已经无所谓了，反正我们知道这个分支不会比A分支好，所以可以放弃了。我在C分支查找的时候遇到了和B分支一样的情况。所以说说C分支剪枝。至此，搜索全部结束，我们也得到了这一步的策略：应该走A分支。可以看出，相比于普通Minimax搜索的18个叶子节点，这里只搜索了9个叶子节点。使用Alpha-beta剪枝可以同时增加Minimax的搜索深度，因此可以获得更好的结果。而Alpha-beta的解与普通Minimax的解是一致的。#p#针对2048游戏的实现我们来看看ov3y同学为2048实现的AI，程序的github在这里，主要程序在ai.js中。上面在建模中提到，Minimax和Alpha-beta都是针对信息对称的round-robin博弈问题。在这里，作者将游戏抽象为：我们这边：玩家。每次可以选择上、下、左、右四种棋策略中的一种（有的花样会少于四个，因为有的方向是不允许走的）。下棋后，按照既定逻辑移动合并方块，完成图案转换。对手：电脑。在当前任意空白处放置一个块，块的值可以是2或4。放置新块后，布局过渡完成。胜利条件：某块的值为“2048”。失败条件：格子满了，四个方向都不能移动（都不能触发合并）。这样，2048博弈就被建模为一个信息对称的两人博弈问题。模式评估是算法的核心，如何评估当前模式的价值是重中之重。在2048中，除了决赛之外，中间模式没有明显的价值评估指标，因此需要一些启发式指标来评估模式。那些得分高的“好”配置是容易导致胜利的配置，而得分低的“坏”配置是容易导致失败的配置。作者采用了以下几种启发式指标。单调性单调性是指块从左到右、从上到下跟随递增或递减。一般来说，图案越单调越好。这里有一个很好的单调模式的例子：平滑度平滑度是每个正方形的值与其直接邻居之间的差异，差异越小越平滑。比如4next2比128next2更平滑，一般认为图案越平滑越好。下面是一个极端平滑的例子：空格的数量很容易理解，因为一般来说，空格越少，对玩家来说就越糟糕。所以我们认为有更多空间的模式更好。隔离空间的数量评估空间被分隔的程度。空间越分散，格局越差。具体来说，2048-AI在评估模式时对这些启发式指标采用了加权策略。具体代码如下：//staticevaluationfunctionAI.prototype.eval=function(){varemptyCells=this.grid.availableCells().length;varsmoothWeight=0.1,//monoWeight=0.0,//islandWeight=0.0,mono2Weight=1.0,emptyWeight=2.7,maxWeight=1.0;returnthis.grid.smoothness()*smoothWeight//+this.grid.monotonicity()*monoWeight//-this.grid.islands()*islandWeight+this.grid.monotonicity2()*mono2Weight+Math.log(emptyCells)*emptyWeight+this.grid.maxValue()*maxWeight;};有兴趣的同学可以调整重量看看有什么效果。对于对手选择的剪枝，在本程序中，除了Alpha-beta剪枝外，在最小节点处使用了另一种剪枝，即只考虑对手采取最差步骤的那一步（而实际2048电脑选择是随机的），而不是搜索对手所有可能的走法。这是因为对方所有可能的选择都是“空格数×2”，如果全部搜索，搜索深度将受到严重限制。相关剪枝代码如下：//trya2and4ineachcellandmeasurehowannoyingitis//withmetricsfromevalvarcandidates=[];varcells=this.grid.availableCells();varscores={2:[],4:[]};for(varvalueinscores){for(variincells){scores[value].push(null);varcell=细胞[i]；vartile=newTile(cell,parseInt(value,10));this.grid.insertTile(tile);scores[value][i]=-this.grid.smoothness()+this.grid.islands();这个.grid.removeTile（单元格）；}}//nowjustpickoutthemostannoyingmovesvarmaxScore=Math.max(Math.max.apply(null,scores[2]),Math.max.apply(null,scores[4]));for(varvalueinscores){//2and4for(vari=0;i
