algorithm - 游戏2048的最优算法是什么？

Question

我最近偶然发现了游戏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 的最高分略高于 20,000 分，这比我目前的分数大得多。有没有比上面更好的算法？

Answer 1

我使用 expectimax 优化而不是 @ovolve 算法使用的极小极大搜索开发了一个 2048 AI。 AI 只是对所有可能的移动执行最大化，然后是对所有可能的瓷砖产生的期望(由瓷砖的概率加权，即 4 为 10%，2 为 90%)。据我所知，不可能修剪 expectimax 优化(除了删除极不可能的分支)，因此所使用的算法是经过仔细优化的蛮力搜索。

表现

默认配置下的 AI(最大搜索深度为 8)需要 10 毫秒到 200 毫秒的时间来执行移动，具体取决于棋盘位置的复杂性。在测试中，AI 在整个游戏过程中实现了每秒 5-10 次移动的平均移动速率。如果搜索深度限制在 6 次移动，AI 可以轻松地每秒执行 20 次以上的移动，这使得 interesting watching .

为了评估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 位整数(其中瓦片是 nybbles，即 4 位块)。在 64 位机器上，这使得整个电路板可以在单个机器寄存器中传递。

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

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

这种棋盘表示，连同用于移动和得分的表格查找方法，允许人工智能在短时间内搜索大量游戏状态(在我 2011 年中期笔记本电脑的一个核心上每秒搜索超过 10,000,000 个游戏状态)。

expectimax 搜索本身被编码为递归搜索，它在“期望”步骤(测试所有可能的瓷砖生成位置和值，并通过每种可能性的概率对它们的优化分数进行加权)和“最大化”步骤(测试所有可能的移动)之间交替并选择得分最高的那个)。树搜索在看到先前看到的位置(使用 transposition table )、达到预定义的深度限制或达到极不可能的棋盘状态时终止(例如，通过获得 6“4”从起始位置开始排成一行)。典型的搜索深度是 4-8 步。

启发式

使用几种启发式方法将优化算法引导至有利位置。启发式的精确选择对算法的性能有巨大的影响。各种试探法被加权并组合成一个位置分数，它决定了给定的棋盘位置有多“好”。优化搜索的目标是最大化所有可能的棋盘位置的平均分数。游戏中显示的实际分数不用于计算棋盘分数，因为它的权重太大，不利于合并瓷砖(当延迟合并可能会产生很大的好处时)。

最初，我使用了两个非常简单的启发式方法，为开放的正方形和在边缘具有大值的人提供“奖励”。这些启发式算法的表现非常好，经常达到 16384，但从未达到 32768。

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

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

这些变化的影响是极其显着的。算法从大约 13% 的时间实现 16384 块到超过 90% 的时间，并且算法开始在 1/3 的时间内实现 32768(而旧的启发式算法从未产生过 32768 块) .

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

人工智能在超过三分之一的游戏中达到 32768 块是一个巨大的里程碑；听说是否有人类玩家在官方游戏中达到了 32768(即不使用 savestates 或 undo 等工具)，我会感到惊讶。我觉得65536瓷砖触手可及!

你可以自己试试人工智能。该代码可在 https://github.com/nneonneo/2048-ai 获得.