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

我最近偶然发现了2048游戏。您可以通过在四个方向上任意移动相似的图块来合并它们,以制作 “更大” 的图块。每次移动后,新的图块将出现在随机的空白位置,值为24 。当所有盒子都装满并且没有可以合并磁贴的移动,或者您创建的值为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
}

我正在做的是在任何时候,我将尝试合并值24的图块,也就是说,我尝试将24图块尽可能地减少。如果以这种方式尝试,所有其他磁贴将自动合并,并且该策略看起来不错。

但是,当我实际使用该算法时,在游戏终止之前我只能得到 4000 点。最高分数 AFAIK 略高于 20,000 点,这比我目前的分数还大。是否有比以上更好的算法?

答案

我是该线程中其他人提到的 AI 程序的作者。您可以查看 AI 行动或阅读

目前,考虑到每次移动大约 100 毫秒的思考时间,该程序在我的笔记本电脑上的浏览器中的 javascript 中运行时,可以实现约 90%的获胜率,因此虽然效果不理想(但!),但它的表现还不错。

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

单调性

这种试探法试图确保图块的值都沿着左 / 右和上 / 下方向都增加或减少。仅凭这种启发式方法就可以捕捉许多其他人提到的直觉,即更高价值的瓷砖应聚集成一角。通常,它将防止较小价值的瓷砖变得孤立,并使板块井井有条,较小的瓷砖会层叠并填充到较大的瓷砖中。

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

完美单调的2048板

光滑度

仅上述启发式方法趋向于创建其中相邻区块的值减小的结构,但是当然为了合并,相邻区块需要具有相同的值。因此,平滑度启发式方法只是测量相邻图块之间的值差,以尽量减少此计数。

关于 Hacker News 的评论者从图论的角度对该想法进行了有趣的形式化

这是一个完美平滑的网格的屏幕截图, 这要归功于出色的模仿叉

完美光滑的2048板

免费瓷砖

最后,免费磁贴太少会受到惩罚,因为当游戏板太狭窄时,选项会很快用完。

就是这样!在优化这些条件的同时搜索游戏空间会产生非常好的性能。使用这样的通用方法而不是显式编码的移动策略的一个优点是该算法通常可以找到有趣且出乎意料的解决方案。如果您观察它的运行,它通常会做出令人惊讶但有效的举动,例如突然切换它要面对的墙或角。

编辑:

这是这种方法的强大功能的演示。我取消了图块值的上限(因此在达到 2048 后继续保持不变),这是八次试验后的最佳结果。

4096

是的,这是 4096 和 2048 的乘积。=)这意味着它在同一块板上完成了 3 倍难以捉摸的 2048 瓦片。

我使用Expectimax优化开发了 2048 AI,而不是@ovolve算法使用的minimax搜索。 AI 会简单地对所有可能的移动执行最大化,然后对所有可能的图块生成进行期望(通过图块的概率加权,即 4 的概率为 10%,2 的概率为 90%)。据我所知,不可能修剪 Expectimax 优化(除去删除极不可能的分支),因此使用的算法是经过仔细优化的蛮力搜索。

性能

AI 的默认配置(最大搜索深度为 8)从 10ms 到 200ms 的任何时间执行移动,具体取决于电路板位置的复杂程度。在测试中,人工智能在整个游戏过程中的平均移动速率为每秒 5-10 次移动。如果将搜索深度限制为 6 个动作,则 AI 可以轻松地每秒执行 20 个以上的动作,这使观看变得有趣

为了评估 AI 的得分表现,我运行了 AI 100 次(通过遥控器连接到浏览器游戏)。对于每个图块,以下是该图块至少获得一次的游戏比例:

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

最低分数为 124024; AI 的最高得分是 794076。中位数是 387222。AI 从未失败过获得 2048 个图块(因此,即使每 100 场游戏中有一次它也不会输掉游戏);实际上,它在每次运行中至少获得了8192 个磁贴!

这是最佳运行的屏幕截图:

32768瓷砖,得分794076

该游戏在 96 分钟内进行了 27830 次移动,或平均每秒 4.8 次移动。

实作

我的方法将整个电路板(16 个条目)编码为单个 64 位整数(其中,图块为四位,即 4 位块)。在 64 位计算机上,这使整个电路板可以在单个计算机寄存器中传递。

位移操作用于提取单独的行和列。单个行或列是 16 位数量,因此大小为 65536 的表可以编码对单个行或列进行操作的转换。例如,将移动作为 4 个查询实现到预先计算的 “移动效果表” 中,该表描述了每个移动如何影响单个行或一列(例如,“向右移动” 表包含条目 “1122-> 0023”,该条目描述了当向右移动时,行 [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 或 undo 等工具),我会感到惊讶。我认为 65536 磁贴触手可及!

您可以自己尝试 AI。该代码可从https://github.com/nneonneo/2048-ai 获得

我对此游戏的 AI 构想产生了兴趣,其中包含硬编码的智能 (即,没有启发式,计分功能等)。 AI 应该仅“知道”游戏规则,并“确定”游戏玩法。这与大多数 AI(如该线程中的 AI)形成鲜明对比,在这些 AI 中,游戏玩法本质上是由代表人类对游戏理解的计分功能控制的。

人工智能算法

我发现了一个简单但出乎意料的好玩算法:要确定给定棋盘的下一招,人工智能会使用随机举动在内存中玩游戏,直到游戏结束。在跟踪最终比赛分数的同时,完成了几次。然后计算每个开始动作的平均终点得分。选择平均终点得分最高的起点作为下一步。

每步仅进行 100 次运行(即在记忆游戏中),AI 可以达到 80%的 2048 瓦片和 50%的 4096 瓦片。使用 10000 次运行可获得 2048 个图块的 2048 个图块,4096 个图块的 70%和 8192 个图块的约 1%。

实际观看

最佳成绩如下所示:

最好成绩

关于此算法的一个有趣的事实是,尽管毫无疑问,随机游戏非常糟糕,但选择最佳(或最差)的举动却可以带来非常好的游戏玩法:典型的 AI 游戏可以达到 70000 点,最后可以移动 3000 次,但是在死之前,来自任何给定位置的内存中随机播放游戏平均会在大约 40 个额外动作中平均产生 340 个额外点。 (您可以通过运行 AI 并打开调试控制台来亲自查看。)

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

得分图

我感到非常惊讶的是,该算法实际上不需要预测良好的游戏玩法来选择产生它的动作。

稍后搜索,我发现该算法可能被归类为 “ 纯蒙特卡洛树搜索”算法。

实施和链接

首先,我创建了一个 JavaScript 版本, 在这里可以看到它的实际效果 。该版本可以在适当的时间内运行 100 多次。打开控制台以获取更多信息。 ( 来源

后来,为了玩得更多,我使用了 @nneonneo 高度优化的基础结构,并使用 C ++ 实现了我的版本。如果您有足够的耐心,此版本最多可允许单次运行 100000 次,甚至 100 万次。提供了建筑说明。它在控制台中运行,还具有播放网络版本的遥控器。 ( 来源

结果

令人惊讶的是,增加运行次数并不能大大改善游戏玩法。对于 4096 磁贴和所有较小的磁贴,此策略似乎在 80000 点附近存在限制,非常接近实现 8192 磁贴。将跑步次数从 100 增加到 100000,增加了达到此分数限制(从 5%到 40%)但没有突破的几率

跑步 10000 次,在关键位置附近暂时增加到 1000000 次,成功突破该障碍的时间不到 1%,实现了最高分 129892 和 8192 磁贴。

改进措施

实施此算法后,我尝试了许多改进,包括使用最小或最大分数,或最小,最大和平均值的组合。我使用深度也试过:不是每移动试图ķ运行,我想每一个给定长度的移动列表 (“向上,向上,左” 为例),并选择最好的得分移动列表的第一个举动 K 移到。

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

但是,与简单的第一个想法相比,这些想法都没有显示出任何真正的优势。我将这些想法留在代码中,以在 C ++ 代码中注释掉。

我确实添加了 “深度搜索” 机制,当任何运行成功地意外到达下一个最高磁贴时,运行次数会暂时增加到 1000000。这提供了时间上的改进。

我很想听听是否有人还有其他可以维持 AI 领域独立性的改进想法。

2048 个变体和克隆

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

由于 AI 的域独立性质,这是可能的。一些变体非常不同,例如六角形克隆。

编辑:这是一种幼稚的算法,可对人类意识的思维过程进行建模,与 AI 相比,它搜索所有可能性的结果非常微弱,因为 AI 只能向前看一个图块。它在响应时间表的早期提交。

我优化了算法并击败了游戏!它可能由于运气不佳而失败(您将被迫向下移动,这是您永远不应该做的,并且您应该在最高位置出现一个图块。只是尝试使第一行保持填充状态,所以向左移动不会打破模式),但基本上您最终会拥有一个固定的零件和一个可移动的零件。这是您的目标:

准备完成

这是我默认选择的模型。

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

缺少步骤的一些提示。这里: 型号变更

由于更接近预期模型,所以模型已更改。 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

我在此处复制博客文章的内容


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

得分了

算法

启发式评分算法

我的算法所基于的假设非常简单:如果您想获得更高的分数,则必须尽可能保持董事会整洁。特别地,最佳设置是由瓦片值的线性和单调递减顺序给出的。这种直觉还将为您提供图块值的上限: s其中 n 是板上的瓦片数。

(如果在需要时随机生成 4 区块而不是 2 区块,则有可能到达 131072 磁贴)

下图显示了两种组织董事会的可能方式:

在此处输入图片说明

为了以单调递减的顺序执行瓦片的排序,将分数 si 计算为板上线性化值的总和乘以公共比率 r <1 的几何序列的值。

s

s

可以一次评估几个线性路径,最终分数将是任何路径的最大分数。

决策规则

实现的决策规则不是很聪明,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 或 Expectiminimax 的实现肯定会改进算法。显然,更复杂的决策规则会使算法变慢,并且需要一些时间才能实现。我将在不久的将来尝试 minimax 实现。 (敬请关注)

基准测试

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

在此处输入图片说明在此处输入图片说明在此处输入图片说明在此处输入图片说明

在 T2 的情况下,十分之四的测试会生成 4096 个图块,平均得分为s 42000

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

我的尝试像上面的其他解决方案一样使用 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]]

我是 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%

(最后一行表示在板上同时具有给定的图块)。

对于三层:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

但是,我从未观察到它能获得 65536 瓦。

我认为我找到了一种效果很好的算法,因为我经常达到 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);
}

已经有一个 AI 实现这个游戏在这里 。自述摘录:

该算法是迭代加深深度优先的 alpha-beta 搜索。评估功能尝试使行和列保持单调(全部减少或增加),同时最小化网格上的图块数量。

Hacker News 上也有关于此算法的讨论,您可能会发现它很有用。

算法

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 }

在这里,我们仍然需要检查堆叠的值,但是以一种不影响灵活性参数的较小方式,因此我们得到 {x in [4,44]} 的总和。

+ (Number of possible next moves x 256)

如果一个国家有更多可能的过渡自由,那么它会更加灵活。

+ (Number of aligned values x 2)

这是对在该状态内进行合并的可能性的简化检查,而无需事先进行检查。

注意:可以调整常量。