2048游戏的最佳算法是什么？

编辑：这是一个天真的算法，模拟了人类有意识的思维过程，与搜索所有可能性的人工智能相比，得到的结果非常弱，因为它只看前面一个瓦片。它是在响应时间线的早期提交的。

我改进了算法并击败了游戏！它可能会失败，原因是接近尾声时运气不好（你被迫向下移动，这是你永远不应该做的，一个瓦片出现在你最高的地方。尽量保持最上面的行被填满，所以向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动的部分可以玩。这是你的目标：

这是我默认选择的模型。

1024 512 256 1288   16  32  644   2   x   xx   x   x   x

选择的角落是任意的，你基本上从不按下一个键（禁止移动），如果你这样做，你再次按下相反的键并尝试修复它。对于未来的瓷砖，模型总是期望下一个随机瓷砖是2，并出现在当前模型的对面（而第一行是不完整的，在右下角，一旦第一行完成，在左下角）。

算法是这样的。大约80%的人获胜（似乎用更“专业”的人工智能技术总是有可能获胜，不过我不确定。）

initiateModel();
while(!game_over){checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point
for each 3 possible move:evaluateResult()execute move with best scoreif no move is available, execute forbidden move and undo, recalculateModel()}
evaluateResult() {calculatesBestCurrentModel()calculates distance to chosen modelstores result}
calculateBestCurrentModel() {(according to the current highest tile acheived and their distribution)}

关于缺失步骤的一些提示。这里：

由于更接近预期模型的运气，模型发生了变化。AI试图实现的模型是

 512 256 128  xX   X   x   xX   X   x   xx   x   x   x

到达那里的链条变成了：

 512 256  64  O8   16  32  O4   x   x   xx   x   x   x

O代表禁区…

所以它会按右，然后再按右，然后（右或上取决于4的创建位置）然后继续完成链，直到它得到：

所以现在模型和链又回到了：

 512 256 128  644   8  16   32X   X   x   xx   x   x   x

第二个指针，它运气不好，它的主要位置已经被拿走了。它很可能会失败，但它仍然可以实现它：

这里的模型和链是：

  O 1024 512 256O   O   O  1288  16   32  644   x   x   x

当它设法达到128时，它会再次获得整行：

  O 1024 512 256x   x  128 128x   x   x   xx   x   x   x

我想我找到了一个很有效的算法，因为我经常达到10000以上的分数，我个人最好的是16000左右。我的解决方案不是把最大的数字放在角落里，而是把它放在最前面。

请参阅下面的代码：

while( !game_over ) {move_direction=up;if( !move_is_possible(up) ) {if( move_is_possible(right) && move_is_possible(left) ){if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) )move_direction = left;elsemove_direction = right;} else if ( move_is_possible(left) ){move_direction = left;} else if ( move_is_possible(right) ){move_direction = right;} else {move_direction = down;}}do_move(move_direction);}

算法

while(!game_over){for each possible move:evaluate next state
choose the maximum evaluation}

评价

Evaluation =128 (Constant)+ (Number of Spaces x 128)+ Sum of faces adjacent to a space { (1/face) x 4096 }+ Sum of other faces { log(face) x 4 }+ (Number of possible next moves x 256)+ (Number of aligned values x 2)

评估详情

128 (Constant)

这是一个常量，用作基线和其他用途，如测试。

+ (Number of Spaces x 128)

更多的空间使状态更灵活，我们乘以128（这是中位数），因为充满128个面的网格是最佳的不可能状态。

+ Sum of faces adjacent to a space { (1/face) x 4096 }

在这里，我们评估有可能合并的面，通过向后评估它们，图块2的值变为2048，而图块2048的值为2。

+ Sum of other faces { log(face) x 4 }

在这里，我们仍然需要检查堆叠值，但以较小的方式不会中断灵活性参数，因此我们在[4,44]}中有{x的总和。

+ (Number of possible next moves x 256)

如果一个状态有更多的可能转换的自由，它就会更灵活。

+ (Number of aligned values x 2)

这是对在该状态内合并的可能性的简化检查，而无需进行展望。

注意：常量可以调整…

这个游戏这里已经有一个AI实现。README摘录：

该算法是迭代深化深度优先alpha-beta搜索。评估函数试图保持行和列单调（全部减少或增加），同时最小化网格上的瓦片数量。

还有一个关于黑客新闻的讨论，你可能会发现这个算法很有用。

我是其他人在这篇文章中提到的AI程序的作者。您可以在行动中查看AI或阅读来源。

目前，该程序在我的笔记本电脑上的浏览器中以javascript运行的胜率约为90%，每次移动的思考时间约为100毫秒，因此虽然不完美（还！）它的表现相当不错。

由于游戏是一个离散的状态空间，完美的信息，回合制游戏，如国际象棋和跳棋，我使用了已被证明适用于这些游戏的相同方法，即极大极小值搜索和α-β修剪。由于已经有很多关于该算法的信息，我将只谈谈我在静态评价函数中使用的两个主要启发式方法，它们将其他人在这里表达的许多直觉形式化。

单调性

这种启发式方法试图确保瓷砖的值沿着左/右和上/下方向增加或减少。仅此启发式方法就抓住了许多其他人提到的直觉，即高价值的瓷砖应该聚集在角落里。它通常会防止较小价值的瓷砖被孤立，并将保持董事会非常有条理，较小的瓷砖层叠并填充到较大的瓷砖中。

这是一个完美单调网格的屏幕截图，我是通过运行一个算法来获得它的，这个算法使用了val函数集来忽略其他的启发式方法，只考虑单调性。

平滑度

单独使用上述启发式往往会创建相邻图块价值递减的结构，但当然为了合并，相邻图块需要相同的值。因此，平滑启发式只是测量相邻图块之间的值差异，试图最小化这个计数。

Hacker News上的一位评论者从图形理论的角度给出了这个想法。

这是一个完美平滑网格的截图。

免费瓷砖

最后，免费图块太少会受到惩罚，因为当游戏板过于狭窄时，选项会很快用完。

就是这样！在优化这些标准的同时搜索游戏空间会产生非常好的性能。使用这样的广义方法而不是明确编码的移动策略的一个优点是，算法通常可以找到有趣和意想不到的解决方案。如果你观察它运行，它通常会做出令人惊讶但有效的移动，比如突然切换它正在建造的墙或角落。

编辑：

这里展示了这种方法的威力。我取消了瓦片值的上限（所以在达到2048之后它继续运行），这是八次试验后的最佳结果。

是的，这是一个4096和一个2048。=）这意味着它在同一块板上实现了三次难以捉摸的2048瓷砖。

这个算法对于赢得游戏来说并不是最佳的，但在性能和所需的代码量方面是相当最佳的：

  if(can move neither right, up or down)direction = leftelse{do{direction = random from (right, down, up)}while(can not move in "direction")}

我开发了一个2048 AI，使用了期望最大值优化，而不是@ovolve的算法使用的极小极大搜索。AI简单地对所有可能的移动执行最大化，然后是对所有可能的瓦片生成的期望（通过瓦片的概率加权，即4的10%和2的90%）。据我所知，由于不可能修剪期望最大优化（除了删除极不可能的分支），因此使用的算法是精心优化的蛮力搜索。

性能

默认配置下的AI（最大搜索深度为8）执行一步动作需要10毫秒到200毫秒不等，具体取决于棋盘位置的复杂程度。在测试中，AI在整场比赛中的平均移动速度为每秒5-10步。如果搜索深度限制为6步，则AI每秒可以轻松执行20+步，这使得一些有趣的观看。

为了评估AI的得分表现，我运行了AI 100次（通过遥控器连接到浏览器游戏）。对于每个图块，以下是至少实现一次该图块的游戏比例：

2048: 100%4096: 100%8192: 100%16384: 94%32768: 36%

所有运行的最低分数为124024；获得的最高分为794076。中位数分数为387222。AI从未未能获得2048块瓷砖（因此它在100场比赛中从未输过一次比赛）；事实上，它在每次运行中都至少获得了一次0块瓷砖！

以下是最佳运行的截图：

这场比赛在96分钟内进行了27830次移动，平均每秒4.8次移动。

实施

我的方法将整个电路板（16个条目）编码为单个64位整数（其中瓦片是nybble，即4位块）。在64位机器上，这使整个电路板能够在单个机器寄存器中传递。

位移位操作用于提取单个行和列。单个行或列是16位的数量，因此大小为65536的表可以编码对单个行或列进行操作的转换。例如，移动被实现为对预计算的“移动效果表”的4次查找，该表描述了每次移动如何影响单个行或列（例如，“向右移动”表包含条目“1122->0023”，描述了当向右移动时行[2,2,4,4]如何成为行[0,0,4,8]）。

评分也是使用表查找完成的。表包含在所有可能的行/列上计算的启发式分数，板的结果分数只是每行和每列的表值的总和。

这种棋盘表示，以及用于移动和评分的表格查找方法，允许AI在短时间内搜索大量游戏状态（在我2011年年中的笔记本电脑的一个核心上，每秒超过10,000,000个游戏状态）。

树搜索本身被编码为递归搜索，它在“期望”步骤（测试所有可能的瓦片生成位置和值，并根据每种可能性的概率加权它们的优化分数）和“最大化”步骤（测试所有可能的移动并选择分数最好的移动）之间交替进行。当它看到以前见过的位置（使用换位表）、当它到达预定义的深度限制或当它到达一个极不可能的棋盘状态（例如，通过从起始位置连续获得6个“4”瓦片来达到它）时，树搜索会终止。典型的搜索深度是4-8步。

启发式

几种启发式方法被用来将优化算法引导到有利的位置。启发式方法的精确选择对算法的性能有巨大的影响。各种启发式方法被加权并组合成位置分数，这决定了给定棋盘位置的“好”程度。然后，优化搜索将旨在最大化所有可能棋盘位置的平均分数。如游戏所示，实际分数没有用于计算棋盘分数，因为它太重，有利于合并棋盘（当延迟合并可能产生很大的好处时）。

最初，我使用了两个非常简单的启发式方法，为开放的方块和边缘有大值的方块授予“奖金”。这些启发式方法执行得很好，经常达到16384，但从未达到32768。

Petr Morávek（@xizurk）接受了我的AI并添加了两个新的启发式方法。第一个启发式方法是对非单调行和列的惩罚，这些行和列随着排名的增加而增加，以确保小数字的非单调行不会强烈影响分数，但大数的非单调行会大大损害分数。第二个启发式计算除了开放空间之外的潜在合并（相邻相等值）的数量。这两个启发式方法有助于将算法推向单调板（更容易合并），以及具有大量合并的板位置（鼓励它在可能的情况下对齐合并以获得更大的效果）。

此外，Petr还使用“元优化”策略（使用称为CMA-ES的算法）优化了启发式权重，其中权重本身被调整以获得可能的最高平均分数。

这些变化的影响非常显著。算法从大约13%的时间实现16384个瓦片到超过90%的时间实现，算法开始在1/3的时间内实现32768个瓦片（而旧的启发式算法从未产生过32768个瓦片）。

我相信启发式算法还有改进的空间。这个算法肯定还不是“最佳”的，但我觉得它已经非常接近了。

人工智能在超过三分之一的游戏中获得了32768个瓦片，这是一个巨大的里程碑；如果有任何人类玩家在官方游戏中获得32768个瓦片，我会感到惊讶（也就是说，没有使用像保存或撤消这样的工具）。我认为65536瓦片是触手可及的！

您可以自己尝试AI。代码可在https://github.com/nneonneo/2048-ai处获得。

我在这里复制了发布在我的博客的内容

我提出的解决方案非常简单，易于实现。虽然，它已经达到了131040的分数。给出了算法性能的几个基准。

算法

启发式评分算法

我的算法所基于的假设相当简单：如果你想获得更高的分数，棋盘必须尽可能保持整洁。特别是，最佳设置由平铺值的线性和单调递减顺序给出。这种直觉也会给你一个瓦片值的上限：其中n是板上瓦片的数量。

（如果需要时随机生成4瓦而不是2瓦，则有可能到达131072瓦）

组织电路板的两种可能方法如下图所示：

为了强制按单调递减顺序排列瓦片，分数si计算为板上线性化值的总和乘以公共比率r<1的几何序列的值。

可以同时评估多个线性路径，最终得分将是任何路径的最大得分。

判定规则

实现的决策规则不是很聪明，Python中的代码在这里给出：

@staticmethoddef nextMove(board,recursion_depth=3):m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)return m
@staticmethoddef nextMoveRecur(board,depth,maxDepth,base=0.9):bestScore = -1.bestMove = 0for m in range(1,5):if(board.validMove(m)):newBoard = copy.deepcopy(board)newBoard.move(m,add_tile=True)
score = AI.evaluate(newBoard)if depth != 0:my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)score += my_s*pow(base,maxDepth-depth+1)
if(score > bestScore):bestMove = mbestScore = scorereturn (bestMove,bestScore);

minmax或EXPECTIMINAX的实现肯定会改进算法复杂的决策规则会拖慢算法速度，实现起来需要一些时间。

基准

• T1-121测试-8种不同的路径-r=0.125
• T2-122测试-8种不同的路径-r=0.25
• T3-132个测试-8个不同的路径-r=0.5
• T4-211测试-2种不同的路径-r=0.125
• T5-274测试-2种不同的路径-r=0.25
• T6-211测试-2种不同的路径-r=0.5

在T2的情况下，十分之四的测试生成4096瓦片，平均得分为42000

代码

代码可以在GiHub上的以下链接中找到：https://github.com/Nicola17/term2048-AI它基于term2048，用Python编写。我会尽快在C++实现一个更高效的版本。

我用Haskell编写了一个2048求解器，主要是因为我现在正在学习这门语言。

我对游戏的实现与实际游戏略有不同，因为新瓦片总是'2'（而不是90%2和10%4）。并且新瓦片不是随机的，而是总是左上角第一个可用的瓦片。这个变体也称为Det2048。

因此，这个求解器是确定性的。

我使用了一个穷举算法，支持空图块。它在深度1-4时执行得非常快，但在深度5时，它变得相当慢，每次移动大约1秒。

下面是实现求解算法的代码。网格表示为16长度的整数数组。只需计算空方块的数量即可完成评分。

bestMove :: Int -> [Int] -> IntbestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]
gridValue :: Int -> [Int] -> IntgridValue _ [] = -1gridValue 0 grid = length $ filter (==0) grid  -- <= SCORINGgridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

我认为它的简单性非常成功。从空网格开始并在深度5求解时得到的结果是：

Move 4006[2,64,16,4][16,4096,128,512][2048,64,1024,16][2,4,16,2]
Game Over

源代码可以在这里找到：https://github.com/popovitsj/2048-haskell

我开始对这个游戏的AI包含没有硬编码的情报（即没有启发式、评分函数等）的想法感兴趣。人工智能应该“知道”只负责游戏规则，“找出”负责游戏玩法。这与大多数人工智能（如本文中的那些）形成鲜明对比，其中游戏玩法本质上是由代表人类对游戏理解的评分函数指导的蛮力。

ai算法

我发现了一个简单但令人惊讶的好游戏算法：为了确定给定棋盘的下一步棋，人工智能使用随机移动在内存中玩游戏，直到游戏结束。这是在跟踪结束游戏分数的同时进行几次。然后计算平均结束分数每开始移动。平均结束分数最高的起始棋被选为下一步。

每次移动仅运行100次（即在内存游戏中），AI达到2048瓦片的次数为80%，达到4096瓦片的次数为50%。使用10000次运行获得100%的2048瓦片，70%的4096瓦片，大约1%的8192瓦片。

看到它在行动

取得的最佳成绩显示在这里：

关于这个算法的一个有趣的事实是，虽然随机游戏不出所料地相当糟糕，但选择最好（或最不糟糕）的走法会带来非常好的游戏体验：一个典型的AI游戏可以达到70000点并持续3000步，然而任何给定位置的内存随机游戏在死亡前在大约40个额外走法中平均产生340个额外点。（你可以通过运行AI并打开调试控制台亲自看到这一点。）

下图说明了这一点：蓝线显示了每次移动后的棋盘得分。红线显示了算法从该位置的最好随机运行结束游戏得分。本质上，红色值是在向上“拉”蓝色值，因为它们是算法的最佳猜测。有趣的是，红线在每一点都只比蓝线高出一点点，然而蓝线继续增加越来越多。

我觉得非常令人惊讶的是，该算法并不需要真正预见良好的游戏玩法才能选择产生它的动作。

后来搜索我发现这个算法可能被归类为纯蒙特卡洛树搜索算法。

实施和链接

首先，我创建了一个可以在这里看到的行动的JavaScript版本。这个版本可以在适当的时间内运行100次运行。打开控制台以获取更多信息。（来源）

后来，为了玩更多的游戏，我使用了@nneonneo高度优化的基础设施，并在C++实现了我的版本。这个版本允许每次移动多达100000次运行，如果你有耐心，甚至可以达到1000000次。提供了构建说明。它在控制台中运行，也有一个遥控器来播放网络版本。（来源）

搜索结果

令人惊讶的是，增加运行次数并不能显著改善游戏玩法。这个策略似乎有一个限制，在4096瓦片和所有较小的瓦片的80000点左右，非常接近达到8192瓦片。将运行次数从100增加到100000会增加达到这个分数限制的赔率（从5%增加到40%），但不会突破它。

在关键位置附近运行10000次并临时增加到1000000次，设法打破这一障碍的次数不到1%，达到129892的最大分数和8192瓦片。

改进

在实现此算法后，我尝试了许多改进，包括使用min或max分数，或min，max和avg的组合。我还尝试使用深度：而不是尝试每次移动K次，我尝试了给定长度的每次移动列表的K次移动（例如“向上，向上，向左”）并选择最佳得分移动列表的第一步。

后来我实现了一个得分树，它考虑了在给定的移动列表之后能够进行移动的条件概率。

然而，这些想法中没有一个比第一个简单的想法显示出任何真正的优势。

我确实添加了一个“深度搜索”机制，当任何运行意外地到达下一个最高的图块时，该机制将运行次数暂时增加到1000000。这提供了时间改进。

我很想知道是否有人有其他改进想法来保持AI的领域独立性。

2048变种和克隆

只是为了好玩，我也将AI实现为书签，连接到游戏的控件。这允许AI与原始游戏和它的许多变体一起工作。

这是可能的，因为AI的域独立性质。一些变体非常不同，例如六边形克隆。

我的尝试像上面的其他解决方案一样使用了预期最大值，但没有位板。Nneonneo的解决方案可以检查1000万次移动，大约是4个深度，还剩下6个瓦片，4个移动可能（2*6*4）⁴。在我的情况下，这个深度需要太长的时间来探索，我根据剩下的空闲瓦片数量调整预期最大搜索的深度：

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

板的分数是用自由瓦片数量的平方和2D网格的点积的加权和计算的：

[[10,8,7,6.5],[.5,.7,1,3],[-.5,-1.5,-1.8,-2],[-3.8,-3.7,-3.5,-3]]

它迫使瓷砖从左上方以蛇的形式向下组织瓷砖。

下面或上面的代码github：

var n = 4,M = new MatrixTransform(n);
var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles
var snake= [[10,8,7,6.5],[.5,.7,1,3],[-.5,-1.5,-1.8,-2],[-3.8,-3.7,-3.5,-3]]snake=snake.map(function(a){return a.map(Math.exp)})
initialize(ai)
function run(ai) {var p;while ((p = predict(ai)) != null) {move(p, ai);}//console.log(ai.grid , maxValue(ai.grid))ai.maxValue = maxValue(ai.grid)console.log(ai)}
function initialize(ai) {ai.grid = [];for (var i = 0; i < n; i++) {ai.grid[i] = []for (var j = 0; j < n; j++) {ai.grid[i][j] = 0;}}rand(ai.grid)rand(ai.grid)ai.steps = 0;}
function move(p, ai) { //0:up, 1:right, 2:down, 3:leftvar newgrid = mv(p, ai.grid);if (!equal(newgrid, ai.grid)) {//console.log(stats(newgrid, ai.grid))ai.grid = newgrid;try {rand(ai.grid)ai.steps++;} catch (e) {console.log('no room', e)}}}
function predict(ai) {var free = freeCells(ai.grid);ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);var root = {path: [],prob: 1,grid: ai.grid,children: []};var x = expandMove(root, ai)//console.log("number of leaves", x)//console.log("number of leaves2", countLeaves(root))if (!root.children.length) return nullvar values = root.children.map(expectimax);var mx = max(values);return root.children[mx[1]].path[0]
}
function countLeaves(node) {var x = 0;if (!node.children.length) return 1;for (var n of node.children)x += countLeaves(n);return x;}
function expectimax(node) {if (!node.children.length) {return node.score} else {var values = node.children.map(expectimax);if (node.prob) { //we are at a max nodereturn Math.max.apply(null, values)} else { // we are at a random nodevar avg = 0;for (var i = 0; i < values.length; i++)avg += node.children[i].prob * values[i]return avg / (values.length / 2)}}}
function expandRandom(node, ai) {var x = 0;for (var i = 0; i < node.grid.length; i++)for (var j = 0; j < node.grid.length; j++)if (!node.grid[i][j]) {var grid2 = M.copy(node.grid),grid4 = M.copy(node.grid);grid2[i][j] = 2;grid4[i][j] = 4;var child2 = {grid: grid2,prob: .9,path: node.path,children: []};var child4 = {grid: grid4,prob: .1,path: node.path,children: []}node.children.push(child2)node.children.push(child4)x += expandMove(child2, ai)x += expandMove(child4, ai)}return x;}
function expandMove(node, ai) { // node={grid,path,score}var isLeaf = true,x = 0;if (node.path.length < ai.depth) {for (var move of[0, 1, 2, 3]) {var grid = mv(move, node.grid);if (!equal(grid, node.grid)) {isLeaf = false;var child = {grid: grid,path: node.path.concat([move]),children: []}node.children.push(child)x += expandRandom(child, ai)}}}if (isLeaf) node.score = dot(ai.weights, stats(node.grid))return isLeaf ? 1 : x;}


var cells = []var table = document.querySelector("table");for (var i = 0; i < n; i++) {var tr = document.createElement("tr");cells[i] = [];for (var j = 0; j < n; j++) {cells[i][j] = document.createElement("td");tr.appendChild(cells[i][j])}table.appendChild(tr);}
function updateUI(ai) {cells.forEach(function(a, i) {a.forEach(function(el, j) {el.innerHTML = ai.grid[i][j] || ''})});}

updateUI(ai);updateHint(predict(ai));
function runAI() {var p = predict(ai);if (p != null && ai.running) {move(p, ai);updateUI(ai);updateHint(p);requestAnimationFrame(runAI);}}runai.onclick = function() {if (!ai.running) {this.innerHTML = 'stop AI';ai.running = true;runAI();} else {this.innerHTML = 'run AI';ai.running = false;updateHint(predict(ai));}}

function updateHint(dir) {hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';}
document.addEventListener("keydown", function(event) {if (!event.target.matches('.r *')) return;event.preventDefault(); // avoid scrollingif (event.which in map) {move(map[event.which], ai)console.log(stats(ai.grid))updateUI(ai);updateHint(predict(ai));}})var map = {38: 0, // Up39: 1, // Right40: 2, // Down37: 3, // Left};init.onclick = function() {initialize(ai);updateUI(ai);updateHint(predict(ai));}

function stats(grid, previousGrid) {
var free = freeCells(grid);
var c = dot2(grid, snake);
return [c, free * free];}
function dist2(a, b) { //squared 2D distancereturn Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)}
function dot(a, b) {var r = 0;for (var i = 0; i < a.length; i++)r += a[i] * b[i];return r}
function dot2(a, b) {var r = 0;for (var i = 0; i < a.length; i++)for (var j = 0; j < a[0].length; j++)r += a[i][j] * b[i][j]return r;}
function product(a) {return a.reduce(function(v, x) {return v * x}, 1)}
function maxValue(grid) {return Math.max.apply(null, grid.map(function(a) {return Math.max.apply(null, a)}));}
function freeCells(grid) {return grid.reduce(function(v, a) {return v + a.reduce(function(t, x) {return t + (x == 0)}, 0)}, 0)}
function max(arr) { // return [value, index] of the maxvar m = [-Infinity, null];for (var i = 0; i < arr.length; i++) {if (arr[i] > m[0]) m = [arr[i], i];}return m}
function min(arr) { // return [value, index] of the minvar m = [Infinity, null];for (var i = 0; i < arr.length; i++) {if (arr[i] < m[0]) m = [arr[i], i];}return m}
function maxScore(nodes) {var min = {score: -Infinity,path: []};for (var node of nodes) {if (node.score > min.score) min = node;}return min;}

function mv(k, grid) {var tgrid = M.itransform(k, grid);for (var i = 0; i < tgrid.length; i++) {var a = tgrid[i];for (var j = 0, jj = 0; j < a.length; j++)if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]for (; jj < a.length; jj++)a[jj] = 0;}return M.transform(k, tgrid);}
function rand(grid) {var r = Math.floor(Math.random() * freeCells(grid)),_r = 0;for (var i = 0; i < grid.length; i++) {for (var j = 0; j < grid.length; j++) {if (!grid[i][j]) {if (_r == r) {grid[i][j] = Math.random() < .9 ? 2 : 4}_r++;}}}}
function equal(grid1, grid2) {for (var i = 0; i < grid1.length; i++)for (var j = 0; j < grid1.length; j++)if (grid1[i][j] != grid2[i][j]) return false;return true;}
function conv44valid(a, b) {var r = 0;for (var i = 0; i < 4; i++)for (var j = 0; j < 4; j++)r += a[i][j] * b[3 - i][3 - j]return r}
function MatrixTransform(n) {var g = [],ig = [];for (var i = 0; i < n; i++) {g[i] = [];ig[i] = [];for (var j = 0; j < n; j++) {g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations}}this.transform = function(k, grid) {return this.transformer(k, grid, g)}this.itransform = function(k, grid) { // inverse transformreturn this.transformer(k, grid, ig)}this.transformer = function(k, grid, mat) {var newgrid = [];for (var i = 0; i < grid.length; i++) {newgrid[i] = [];for (var j = 0; j < grid.length; j++)newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];}return newgrid;}this.copy = function(grid) {return this.transform(3, grid)}}

body {font-family: Arial;}table, th, td {border: 1px solid black;margin: 0 auto;border-collapse: collapse;}td {width: 35px;height: 35px;text-align: center;}button {margin: 2px;padding: 3px 15px;color: rgba(0,0,0,.9);}.r {display: flex;align-items: center;justify-content: center;margin: .2em;position: relative;}#hintvalue {font-size: 1.4em;padding: 2px 8px;display: inline-flex;justify-content: center;width: 30px;}

<table title="press arrow keys"></table><div class="r"><button id=init>init</button><button id=runai>run AI</button><span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span></div>

许多其他答案使用人工智能来计算昂贵的未来搜索、启发式、学习等。这些令人印象深刻，可能是正确的前进方向，但我想贡献另一个想法。

模拟游戏中优秀玩家使用的策略类型。

例如：

13 14 15 1612 11 10  95  6  7  84  3  2  1

按照上面显示的顺序读取方块，直到下一个方块值大于当前方块。这会出现尝试将相同值的另一个图块合并到这个方块中的问题。

为了解决这个问题，他们有两种移动方式，这些方式不会留下或更糟，检查这两种可能性可能会立即发现更多的问题，这形成了一个依赖列表，每个问题都需要先解决另一个问题。我想在决定下一步行动时，我有这个链条，或者在某些情况下，内部依赖树，特别是当卡住的时候。

瓷砖需要与邻居合并，但太小：将另一个邻居与这个合并。

更大的瓷砖：增加周围较小瓷砖的价值。

等…

整个方法可能会比这更复杂，但不会复杂得多。它可能是这种机械的感觉，缺乏分数、权重、神经元和对可能性的深入搜索。可能性树甚至需要足够大，根本不需要任何分支。

我是2048控制器的作者，该控制器的得分比本线程中提到的任何其他程序都要高。控制器的有效实现可在github上获得。在一个单独的回购中，还有用于训练控制器状态评估函数的代码。训练方法在论文中描述。

控制器使用期望最大搜索，通过时序差异学习（一种强化学习技术）的变体从头开始学习（无需人类2048专业知识）的状态评估函数。状态值函数使用n元组网络，它基本上是在板上观察到的模式的加权线性函数。它总共涉及超过10亿重量。

性能

1步/秒：609104（平均100场比赛）

10步/秒：589355（平均300场比赛）

3层（约1500次/秒）：511759（平均1000场比赛）

10步/秒的瓦片统计如下：

2048: 100%4096: 100%8192: 100%16384: 97%32768: 64%32768,16384,8192,4096: 10%

（最后一行表示在板上同时具有给定的图块）。

对于3层：

2048: 100%4096: 100%8192: 100%16384: 96%32768: 54%32768,16384,8192,4096: 8%

然而，我从未观察到它获得65536瓦。

这不是对OP问题的直接回答，这是我到目前为止尝试解决相同问题的更多东西（实验），并获得了一些结果，并有一些我想分享的观察结果，我很好奇我们是否可以从中获得一些进一步的见解。

我刚刚尝试了我的极小极大实现，使用alpha-beta修剪，搜索树深度截止值为3和5。我试图解决4x4网格的相同问题，作为edX课程Columbia biaX：CSMM.101x人工智能（AI）的项目分配。

我应用了几个启发式评估函数的凸组合（尝试了不同的启发式权重），主要来自直觉和上面讨论的：

1. 单调性
2. 可用的自由空间

在我的情况下，计算机播放器是完全随机的，但我仍然假设对抗性设置并将AI播放器代理实现为最大播放器。

我有4x4网格玩游戏。

意见：

如果我给第一个启发式函数或第二个启发式函数分配太多的权重，在这两种情况下，人工智能玩家得到的分数都很低。我对启发式函数分配了许多可能的权重，并采取了凸组合，但人工智能玩家很少能够得分2048。大多数时候，它要么停在1024要么512。

我也尝试过角落启发式，但由于某种原因，它使结果更糟，任何直觉为什么？

此外，我试图将搜索深度截止值从3增加到5（我不能再增加了，因为搜索空间超过了允许的时间，即使进行了修剪），并添加了一个启发式方法，查看相邻图块的值，如果它们是可合并的，则给出更多的点，但我仍然无法获得2048。

我认为使用EXCETIMAX而不是最小化会更好，但我仍然想只用最小化来解决这个问题，并获得高分，如2048或4096。我不确定我是否错过了什么。

下面的动画显示了AI代理与计算机玩家玩游戏的最后几个步骤：

任何见解都将非常有帮助，提前感谢。（这是我博客文章的链接：https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/和youtube视频：https://www.youtube.com/watch?v=VnVFilfZ0r4）

以下动画显示了游戏的最后几个步骤，AI玩家代理可以获得2048分，这次也添加了绝对值启发式：

下图显示了玩家AI代理假设计算机作为对手仅一步探索的博弈树：