我最近偶然发现了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

其他回答

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

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

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

单调性

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

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

平滑度

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

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

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

自由平铺

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

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

编辑:

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

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

这里已经有了这款游戏的AI实现。自述节选:

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

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

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

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

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

例如:

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

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

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


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

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


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

我用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