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

我最近偶然发现了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个平铺。如果我这样做，所有其他平铺都会自动合并，策略似乎很好。

但是，当我实际使用这个算法时，在游戏结束之前，我只得到了大约4000分。AFAIK的最高分数略高于20000分，这比我目前的分数要大得多。有比上述更好的算法吗？

当前回答

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

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

这是我默认选择的模型。

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

2014-03-12 16:05:34

其他回答

这不是对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代理探索的游戏树，假设计算机是对手，只需一步：

2017-03-06 21:37:45

我是一个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平铺。

2015-12-21 10:49:45

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

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

2014-03-14 21:53:56