协慌网

我最近偶然发现了2048游戏。您可以通过在四个方向中的任何一个方向上移动它们来合并相似的图块，以制作 “更大” 的图块每次移动后，新的图块会出现在随机空位置，值为2或4 。当所有框都被填充并且没有可以合并图块的移动时，或者您创建值为2048的图块时，游戏将终止。

一，我需要遵循明确的战略来实现目标。所以，我想为它编写一个程序。

我目前的算法：

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

我正在做的是在任何时候，我将尝试将值与值2和4合并，也就是说，尽量减少2和4 tile。如果我这样尝试，所有其他瓷砖自动合并，策略似乎很好。

但是，当我实际使用这个算法时，我只能在游戏结束前获得大约 4000 点。 AFAIK 的最高分数略高于 20,000 分，远高于我目前的分数。是否有比上述更好的算法？

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

目前，该程序在我的笔记本电脑上的浏览器中使用 javascript 运行大约 90％的赢率，每次移动大约有 100 毫秒的思考时间，所以虽然不完美（但是！）它表现相当不错。

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

单调性

该启发式尝试确保瓦片的值沿左 / 右和上 / 下方向都增加或减少。这种启发式捕获了许多其他人提到的直觉，即更高价值的瓷砖应该聚集在一个角落里。它通常会阻止较小的有价值的瓷砖变得孤立，并使电路板非常有条理，较小的瓷砖层叠并填充到较大的瓷砖中。

这是一个完美单调网格的屏幕截图。我通过运行算法并使用 eval 函数设置忽略其他启发式算法并且仅考虑单调性来获得此结果。

顺利

上述启发式单独倾向于创建其中相邻瓦片的值减小的结构，但是当然为了合并，相邻瓦片需要是相同的值。因此，平滑度启发式测量仅测量相邻图块之间的值差异，尝试最小化此计数。

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

这是一个非常流畅的网格的截图，由这个优秀的模仿叉子提供 。

免费瓷砖

最后，由于游戏牌太过狭窄，选项很快就会耗尽，因此免费牌位太少会受到惩罚。

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

编辑：

以下是这种方法的强大功能。我打开了瓷砖值（所以它在达到 2048 后继续运行），这是八次试验后的最佳结果。

是的，这是 2048 年的 4096. =）这意味着它在同一块板上实现了三次难以捉摸的 2048 瓦片。

我使用expectimax优化开发了 2048 AI，而不是 @ ovolve 算法使用的 minimax 搜索。 AI 简单地对所有可能的移动执行最大化，然后对所有可能的瓦片生成进行预期（通过瓦片的概率加权，即 4 的 10％和 2 的 90％）。据我所知，不可能修剪 expectimax 优化（除了删除非常不可能的分支），因此使用的算法是经过仔细优化的强力搜索。

性能

默认配置中的 AI（最大搜索深度为 8）需要 10ms 到 200ms 才能执行移动，具体取决于电路板位置的复杂程度。在测试中，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 位整数（其中 tile 是 nybbles，即 4 位块）。在 64 位计算机上，这使得整个电路板可以在一个机器寄存器中传递。

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

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

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

expectimax 搜索本身被编码为递归搜索，其在 “期望” 步骤（测试所有可能的瓦片生成位置和值，并通过每种可能性的概率加权其优化得分）和 “最大化” 步骤（测试所有可能的移动）之间交替。并选择得分最高的那个）。树搜索在看到先前看到的位置（使用转置表 ），达到预定义的深度限制时，或者当它达到极不可能的板状态时（例如，通过获得 6“4” 瓦片达到）终止从起始位置开始连续）。典型的搜索深度为 4-8 个移动。

启发式

使用几种启发法将优化算法指向有利位置。启发式的精确选择对算法的性能有很大影响。各种启发式方法被加权并组合成位置分数，该分数确定给定的板位置的 “好” 程度。然后，优化搜索将旨在最大化所有可能的董事会职位的平均分数。如游戏所示，实际得分不用于计算董事会得分，因为它的权重太大而有利于合并磁贴（当延迟合并可能产生很大的好处时）。

最初，我使用了两个非常简单的启发式方法，为空心方块和边缘上的大值赋予 “奖励”。这些启发式表现相当不错，经常达到 16384 但从未达到 32768。

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

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

这些变化的影响非常显着。该算法从大约 13％的时间实现 16384 瓦片到 90％以上的时间实现它，并且算法在 1/3 的时间内开始达到 32768（而旧的启发式方法从未生成 32768 瓦片） 。

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

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

你可以亲自试试 AI。该代码可在https://github.com/nneonneo/2048-ai 获得 。

编辑：这是一个天真的算法，对人类有意识的思维过程进行建模，并且与搜索所有可能性的人工智能相比得到非常微弱的结果，因为它只能看到前面的一个区块。它是在响应时间表的早期提交的。

我已经改进了算法并击败了游戏！它可能会因为接近末尾的简单坏运而失败（你被迫向下移动，你永远不应该这样做，而且你的最高点应该出现在你的最高位置。只是尽量保持顶行填充，所以向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动部分来玩。这是你的目标：

这是我默认选择的模型。

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

选择的角落是任意的，你基本上从不按一个键（禁止移动），如果你这样做，你再次按相反的方法并尝试修复它。对于将来的图块，模型总是希望下一个随机图块为 2 并显示在当前模型的另一侧（第一行不完整，右下角，第一行完成后，左下角）角）。

这是算法。大约 80％的胜利（似乎总是可以通过更多 “专业”AI 技术获胜，但我不确定这一点。）

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)
  }

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

由于更接近预期模型的运气，该模型已经改变。 AI 试图实现的模型是

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