编辑：这是一个天真的算法，模拟人类有意识的思维过程，与搜索所有可能性的人工智能相比，它的结果非常微弱，因为它只向前看一块砖。它是在答复时间表的早期提交的。

我改进了算法，打败了游戏！它可能会因为临近结束时的简单厄运而失败（你被迫向下移动，这是你永远不应该做的，并且在你最高的位置会出现一个瓦片。只需保持最上面的一行填满，这样向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动的部分可以玩。这是您的目标：

这是我默认选择的模型。

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   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 score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

关于缺失步骤的几点提示。在这里：

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

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

实现这一目标的链条变成了：

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O代表禁区。。。

因此，它将向右，然后再向右，然后（向右或向右，取决于4创建的位置），然后继续完成链，直到它得到：

因此，现在模型和链又回到了：

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

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

这里的模型和链是：

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

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

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   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;
            else
                move_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实现。自述节选：

该算法是迭代加深深度优先alpha beta搜索。求值函数试图保持行和列的单调性（要么减少，要么增加），同时最小化网格上的平铺数量。

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

我是其他人在本主题中提到的AI程序的作者。您可以查看人工智能的运行情况或读取源代码。

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

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

单调性

该启发式方法试图确保平铺的值都沿着左/右和上/下方向增加或减少。仅此启发式方法就抓住了许多其他人提到的直觉，即较高价值的瓦片应该聚集在角落中。它通常会防止价值较小的瓦片成为孤立的，并保持棋盘非常有序，较小的瓦片层叠并填充到较大的瓦片中。

这是一个完全单调的网格截图。我通过运行带有eval函数集的算法来实现这一点，从而忽略其他启发式，只考虑单调性。

平滑度

仅上述启发式方法就倾向于创建相邻瓦片值降低的结构，但当然，为了合并，相邻瓦片需要具有相同的值。因此，平滑启发式算法仅测量相邻平铺之间的值差，试图将此计数最小化。

《黑客新闻》的一位评论者用图论的方式对这一想法进行了有趣的形式化。

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

自由平铺

最后，由于游戏板太拥挤，选项可能会很快用完，所以免费瓷砖太少会受到惩罚。

就这样！在优化这些标准的同时搜索游戏空间会产生非常好的性能。使用像这样的通用方法而不是显式编码的移动策略的一个优点是，该算法通常可以找到有趣和意外的解决方案。如果你看着它跑，它通常会做出令人惊讶但有效的动作，比如突然切换它所建的墙或角落。

编辑：

这里展示了这种方法的威力。我取消了平铺值的上限（因此它在达到2048之后保持不变），这是八次试验后的最佳结果。

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

该算法对于赢得游戏来说不是最佳的，但就性能和所需代码量而言，它是相当最佳的：

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

我使用expectimax优化开发了2048 AI，而不是@ovolve算法使用的最小值搜索。AI简单地对所有可能的移动执行最大化，然后对所有可能瓦片产生进行期望（由瓦片的概率加权，即，4个瓦片为10%，2个瓦片为90%）。据我所知，不可能删减expectimax优化（除了删除极不可能的分支），因此所使用的算法是经过仔细优化的暴力搜索。

表演

AI在其默认配置（最大搜索深度为8）中执行移动需要10毫秒到200毫秒，具体取决于板位置的复杂性。在测试中，AI在整个游戏过程中实现了每秒5-10次的平均移动速度。如果搜索深度被限制在6次移动，AI可以轻松地每秒执行20次以上的移动，这使得观看更加有趣。

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

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

所有跑步的最低得分为124024分；最高得分为794076分。平均得分为387222。AI从未未能获得2048个区块（因此它从未在100场游戏中输掉过一次游戏）；事实上，它在每次运行中至少实现一次8192平铺！

以下是最佳跑步记录的截图：

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

实施

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

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

评分也使用表格查找来完成。这些表包含对所有可能的行/列计算的启发式得分，一个板的最终得分只是每行和每列的表值之和。

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

expectimax搜索本身被编码为递归搜索，它在“期望”步骤（测试所有可能的平铺生成位置和值，并根据每个可能性的概率加权其优化分数）和“最大化”步骤（检测所有可能的移动并选择具有最佳分数的移动）之间交替。当树搜索看到之前看到的位置（使用换位表）、达到预定义的深度限制或达到极不可能达到的板状态时（例如，通过从起始位置开始一行获得6“4”块而达到），树搜索终止。典型的搜索深度为4-8次移动。

启发式

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

最初，我使用了两种非常简单的启发式方法，即为开放正方形和边缘值较大的正方形授予“奖金”。这些启发式算法表现得很好，经常达到16384，但从未达到32768。

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

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

这些变化的影响极其显著。该算法在大约13%的时间内实现了16384个瓦片，在90%的时间内完成了它，并且该算法在1/3的时间内开始实现32768个瓦片（而旧的启发式算法从未产生过32768个）。

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

人工智能在超过三分之一的游戏中获得32768分，这是一个巨大的里程碑；我会很惊讶地听到是否有人类玩家在官方游戏中达到了32768（即不使用保存状态或撤销等工具）。我认为65536瓷砖触手可及！

你可以自己尝试人工智能。该代码位于https://github.com/nneonneo/2048-ai.

我在这里复制我博客上的一篇文章的内容

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

算法

启发式评分算法

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

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

两种可能的董事会组织方式如下图所示：

为了以单调递减的顺序执行瓷砖的排序，得分si计算为板上线性化值的和乘以公共比率r＜1的几何序列的值。

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

决策规则

实现的决策规则不太聪明，Python代码如下：

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for 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 = m
                bestScore = score
    return (bestMove,bestScore);

minmax或Expectimimax的实现肯定会改进算法。显然更多复杂的决策规则会降低算法的速度，并且需要一些时间来实现。我将在不久的将来尝试一个最小值实现。（敬请关注）

基准

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

在T2的情况下，十次测试中有四次生成平均分数为42000的4096分图块

Code

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

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

我的游戏实现与实际游戏略有不同，因为新的平铺始终是“2”（而不是90%2和10%4）。而且，新的平铺不是随机的，而是始终是左上角第一个可用的平铺。该变体也称为Det 2048。

因此，此解算器是确定性的。

我使用了一种支持空瓷砖的穷举算法。它在深度1-4时表现得很快，但在深度5时，每次移动大约1秒就会变得很慢。

下面是实现求解算法的代码。网格表示为16长度的整数数组。得分是通过计算空方块的数量来完成的。

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue 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）形成对比，在这些AI中，游戏玩法基本上是由代表人类对游戏理解的评分函数控制的暴力。

AI算法

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

每次移动仅运行100次（即内存游戏），AI可实现2048次平铺80%的次数和4096次平铺50%的次数。使用10000次运行可获得2048个平铺100%，4096个平铺70%，8192个平铺约1%。

在行动中看到它

最佳成绩如下：

关于这个算法的一个有趣的事实是，尽管随机游戏毫无疑问非常糟糕，但选择最佳（或最不糟糕）的招式会带来非常好的游戏效果：一个典型的人工智能游戏可以达到70000点，并持续3000步，但任何给定位置的记忆中随机游戏在死亡前都会在大约40次额外的招式中平均增加340点。（您可以通过运行AI并打开调试控制台自行查看。）

这张图说明了这一点：蓝线显示了每次移动后的棋盘得分。红线显示了该位置的算法的最佳随机运行结束游戏分数。本质上，红色值是将蓝色值向上拉向它们，因为它们是算法的最佳猜测。有趣的是，在每一点上，红线都比蓝线略高一点，但蓝线仍在不断增加。

我觉得很奇怪的是，算法不需要实际预测好的游戏玩法，就可以选择产生它的动作。

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

实施和链接

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

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

后果

令人惊讶的是，增加跑步次数并不能显著改善比赛。这一策略似乎有一个限制，即4096个区块和所有较小的区块在80000点左右，非常接近8192个区块。将跑步次数从100次增加到100000次会增加达到这一分数限制（从5%增加到40%）但无法突破的几率。

在关键位置临时增加到1000000次的10000次跑步打破了这一障碍，达到129892分的最高得分和8192分的次数不到1%。

改进

在实现这个算法后，我尝试了许多改进，包括使用最小或最大分数，或最小、最大和平均值的组合。我还尝试了使用深度：我没有尝试每次移动K次，而是尝试了给定长度的每次移动列表（例如“向上、向上、向左”）的K次移动，并选择最佳得分移动列表的第一个移动。

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

然而，这些想法都没有比简单的第一个想法显示出任何真正的优势。我将这些想法的代码注释在C++代码中。

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

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

2048个变体和克隆

为了好玩，我还将AI实现为书签，与游戏的控件挂钩。这使得AI可以与原始游戏及其许多变体一起工作。

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

我的尝试与上面的其他解决方案一样使用expectimax，但没有比特板。Nneonneo的解决方案可以检查1000万次移动，大约深度为4，剩余6个平铺，可能移动4次（2*6*4）4。在我的情况下，这个深度需要很长时间来探索，我根据剩余的空闲平铺数调整expectimax搜索的深度：

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上的代码：

变量n＝4，M=新矩阵变换（n）；var ai=｛weights:[1，1]，深度：1｝；//默认情况下，depth=1，但我们会根据空闲平铺的数量对每个预测进行调整var蛇=[[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（函数（a）｛return a.map（Math.exp）｝）初始化（ai）函数运行（ai）{变量p；而（（p=预测（ai））！=空）{移动（p，ai）；}//console.log（ai.grid，maxValue（ai.ggrid））ai.maxValue=最大值（ai.grid）控制台日志（ai）}函数初始化（ai）{ai.grid=[]；对于（变量i=0；i<n；i++）{ai网格[i]=[]对于（变量j=0；j<n；j++）{ai.grid[i][j]=0；}}兰特（ai网格）兰特（ai网格）ai.steps=0；}函数move（p，ai）{//0:向上，1:向右，2:向下，3:向左var newgrid=mv（p，ai.grid）；if（！equal（newgrid，ai.grid））{//console.log（stats（newgrid，ai.grid））ai.grid=新网格；尝试{兰特（ai网格）ai.步骤++；}捕获（e）{控制台日志（“无房间”，e）}}}函数预测（ai）{var free=freeCells（ai.grid）；ai.depth=自由>7？1：（自由>4？2：3）；var-root={path:[]，prob:1，grid:ai.grid，childs:[]}；var x=expandMove（根，ai）//console.log（“叶数”，x）//console.log（“叶数2”，countLeaves（根））if（！root.childres.length）返回nullvar values=root.childres.map（expectimax）；var mx=最大值；return root.childrens[mx[1]].path[0]}函数countLeaves（节点）{变量x=0；if（！node.childres.length）返回1；for（node.childs的var n）x+=叶数（n）；返回x；}函数预期值（节点）{if（！node.childres.length）{返回node.score}其他{var values=node.childres.map（expectimax）；如果（node.prob）{//我们处于最大节点return Math.max.apply（空，值）}否则｛//我们处于随机节点var平均值=0；对于（var i=0；i<values.length；i++）avg+=节点.子项[i].prob*值[i]返回平均值/（values.length/2）}}}函数expandRandom（节点，ai）{变量x=0；对于（var i=0；i<node.grid.length；i++）对于（var j=0；j<node.grid.length；j++）if（！node.grid[i][j]）{var grid2=M.copy（node.grid），grid4=M.copy（node.grid）；网格2[i][j]=2；网格4[i][j]=4；var child2=｛grid:grid2，prob:.9，path：node.path，childs:[]｝；var child4=｛grid:grid4，prob:.1，path：node.path，childs:[]｝node.childres.push（child2）node.childres.push（child4）x+=expandMove（child2，ai）x+=expandMove（child4，ai）}返回x；}函数expandMove（node，ai）｛//node＝｛grid，path，score｝var isLeaf=真，x=0；如果（节点路径长度小于ai深度）{for（变量移动[0，1，2，3]）{var grid=mv（移动，node.grid）；if（！equal（grid，node.grid））{isLeaf=false；var child=｛grid:grid，path:node.path.contat（[move]），childs:[]｝node.childres.push（child）x+=expandRandom（子级，ai）}}}if（isLeaf）node.score=dot（ai.weights，stats（node.grid））return是Leaf？1:x；}var单元格=[]var table=document.querySelector（“table”）；对于（变量i=0；i<n；i++）{var tr=document.createElement（“tr”）；单元格[i]=[]；对于（变量j=0；j<n；j++）{cells[i][j]=document.createElement（“td”）；tr.appendChild（单元格[i][j]）}table.appendChild（tr）；}函数更新UI（ai）{cells.forEach（函数（a，i）{a.forEach（函数（el，j）{el.innerHTML=ai.grid[i][j]| |“”})});}更新UI（ai）；updateHint（预测（ai））；函数runAI（）{var p=预测（ai）；如果（p！=null&&ai.running）{移动（p，ai）；更新UI（ai）；updateHint（p）；requestAnimationFrame（runAI）；}}runai.onclick=函数（）{if（！ai.running）{this.innerHTML=“停止AI”；ai.running=真；runAI（）；}其他{this.innerHTML=“运行AI”；ai.running=false；updateHint（预测（ai））；}}函数updateHint（dir）{hintvalue.innerHTML=['↑', '→', '↓', '←'][目录]| |“”；}document.addEventListener（“keydown”，函数（事件）{if（！event.target.matches（'.r*'））返回；event.prpreventDefault（）；//避免滚动if（地图中的event.which）{移动（map[event.with]，ai）console.log（stats（ai.grid））更新UI（ai）；updateHint（预测（ai））；}})变量映射={38:0，//以上39:1，//右40:2，//向下37:3，//左};init.onclick=函数（）{初始化（ai）；更新UI（ai）；updateHint（预测（ai））；}函数统计信息（网格，previousGrid）{var free=freeCells（网格）；var c=dot2（网格，蛇）；返回[c，free*free]；}函数dist2（a，b）{//2D距离的平方返回Math.pow（a[0]-b[0]，2）+Math.pow（a[1]-b[1]，2）}功能点（a，b）{变量r=0；对于（var i=0；i<a.length；i++）r+=a[i]*b[i]；返回r}函数dot2（a，b）{变量r=0；对于（var i=0；i<a.length；i++）对于（变量j=0；j<a[0].length；j++）r+=a[i][j]*b[i][j]返回r；}函数积（a）{return a.reduce（函数（v，x）{返回v*x}, 1)}函数maxValue（网格）{return Math.max.apply（null，grid.map（函数（a）{return Math.max.apply（null，a）}));}无功能单元格（网格）{返回grid.reduce（函数（v，a）{返回v+a.reduce（函数（t，x）{返回t+（x==0）}, 0)}, 0)}函数max（arr）{//返回max的[value，index]var m=[-无限，空]；对于（变量i=0；i<arr.length；i++）{如果（arr[i]>m[0]）m=[arr[i]，i]；}返回m}函数min（arr）{//返回min的[value，index]var m=[无限，空]；对于（变量i=0；i<arr.length；i++）{如果（arr[i]<m[0]）m=[arr[i]，i]；}返回m}函数maxScore（节点）{变量最小值={分数：-无限，路径：[]};for（节点的var节点）{如果（node.score>min.score）min=节点；}

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

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

例如：

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

按照上面显示的顺序读取正方形，直到下一个正方形值大于当前值。这就带来了试图将另一个具有相同值的平铺合并到此方形中的问题。

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

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

较大的平铺：增加较小的周围平铺的值。

等

整个方法可能比这更复杂，但并不复杂。这可能是一种机械的感觉，缺乏分数、体重、神经和对可能性的深入探索。可能性之树甚至需要足够大，完全需要分支。

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

控制器使用expectimax搜索，该搜索具有通过时间差学习（强化学习技术）的变体从零开始学习的状态评估函数（没有人类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修剪的minimax实现，搜索树深度截止值为3和5。我试图解决4x4网格的相同问题，作为edX课程ColumbiaX:CSMM101x人工智能（AI）的项目作业。

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

单调性可用的可用空间

在我的情况下，电脑玩家是完全随机的，但我仍然假设了对抗性设置，并将AI玩家代理实现为最大玩家。

我有4x4网格来玩游戏。

观察结果：

如果我给第一个启发式函数或第二个启发式函数分配了太多权重，那么AI玩家获得的分数都很低。我对启发式函数进行了许多可能的权重分配，并采用了凸组合，但很少有AI玩家能够得分2048。大多数时候，它要么停在1024或512。

我也尝试过拐角启发式，但出于某种原因，它会使结果更糟，凭直觉为什么？

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

我认为使用Expectimax而不是minimax会更好，但我仍然希望只使用minimax来解决这个问题，并获得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代理探索的游戏树，假设计算机是对手，只需一步：