我最近偶然发现了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分,这比我目前的分数要大得多。有比上述更好的算法吗?


当前回答

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

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

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

单调性

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

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

平滑度

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

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

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

自由平铺

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

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

编辑:

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

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

其他回答

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

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

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

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

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

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

单调性

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

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

平滑度

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

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

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

自由平铺

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

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

编辑:

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

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

算法

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(如本线程中的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的领域独立性。一些变体非常独特,例如六边形克隆。

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