2048小游戏最佳算法C语言,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获得。