我最近偶然发现了游戏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点，这比我目前的分数还大。是否有比以上更好的算法？
请您参考如下方法:
我使用Expectimax优化开发了2048 AI，而不是@ovolve算法使用的minimax搜索。 AI会简单地对所有可能的移动进行最大化，然后对所有可能的瓦片生成进行预期（由瓦片的概率加权，即4的概率为10％，2的概率为90％）。据我所知，不可能修剪Expectimax优化（除去删除极不可能的分支），因此使用的算法是经过仔细优化的蛮力搜索。
性能
AI的默认配置（最大搜索深度为8）从10ms到200ms的任何时间执行一次移动，具体取决于电路板位置的复杂程度。在测试中，人工智能在整个游戏过程中的平均移动速率为每秒5-10次移动。如果将搜索深度限制为6个动作，则AI可以轻松地每秒执行20个以上的动作，这需要一定的interesting watching。
为了评估AI的得分表现，我运行了AI 100次（通过遥控器连接到浏览器游戏）。对于每个图块，以下是该图块至少获得一次的游戏比例：
2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%
最低分数为124024； AI的最高得分是794076。中位数是387222。AI从未失败过获得2048个图块（因此，即使每100场游戏中有一次它也不会输掉游戏）；实际上，它在每次运行中至少获得了8192个磁贴！
这是最佳运行的屏幕截图：
该游戏在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搜索本身被编码为递归搜索，它在“期望”步骤（测试所有可能的瓦片生成位置和值，并通过每种可能性的概率加权其优化得分）和“最大化”步骤（测试所有可能的移动）之间交替并选择得分最高的那个）。当树搜索看到先前看到的位置（使用 transposition table），达到预定义的深度限制或达到极不可能出现的板状态（例如，通过获得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获得。
