我最近偶然发现了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分。据我所知，最高分略高于20000分，这比我目前的分数高得多。是否有比上述更好的算法？
回答：
我开发了一个使用期望最大化优化的2048 AI，而不是@ovolve算法使用的极小极大搜索。AI简单地对所有可能的移动进行最大化，然后对所有可能的瓷砖生成进行期望计算（根据瓷砖的概率加权，即4的概率为10%，2的概率为90%）。据我所知，除了去除极不可能的分支外，无法修剪期望最大化优化，因此使用的算法是一种经过精心优化的暴力搜索。
性能
AI在默认配置下（最大搜索深度为8）执行一次移动需要10毫秒到200毫秒不等，具体取决于棋盘位置的复杂性。在测试中，AI在整个游戏过程中平均每秒执行5到10次移动。如果将搜索深度限制为6次移动，AI可以轻松每秒执行20次以上的移动，这使得观看变得有趣。
为了评估AI的得分表现，我运行了AI 100次（通过远程控制连接到浏览器游戏）。对于每个瓷砖，以下是至少达到该瓷砖的游戏比例：
2048: 100%4096: 100%8192: 100%16384: 94%32768: 36%所有运行中的最低得分为124024；最高得分为794076。中位数得分为387222。AI从未未能获得2048瓷砖（因此在100场游戏中从未输过一次）；事实上，它在每次运行中至少获得了一次8192瓷砖！
这是最佳运行的截图：
这场游戏进行了27830次移动，历时96分钟，平均每秒4.8次移动。
实现
我的方法将整个棋盘（16个条目）编码为一个64位整数（其中瓷砖是4位块，即nybbles）。在64位机器上，这使得整个棋盘可以在单个机器寄存器中传递。
使用位移操作来提取单个行和列。单行或单列是一个16位量，因此大小为65536的表可以编码对单行或单列进行操作的变换。例如，移动是通过4次查找预计算的“移动效果表”来实现的，该表描述了每个移动如何影响单行或单列（例如，“向右移动”表包含条目“1122 -> 0023”，描述了行[2,2,4,4]在向右移动时变为行[0,0,4,8]）。
评分也是使用表查找完成的。表中包含对所有可能的行/列计算的启发式分数，棋盘的最终分数只是各行和各列的表值之和。
这种棋盘表示法，连同用于移动和评分的表查找方法，使AI能够在短时间内搜索大量游戏状态（在我2011年中期的笔记本电脑上，每秒搜索超过1000万个游戏状态）。
期望最大化搜索本身被编码为一个递归搜索，它在“期望”步骤（测试所有可能的瓷砖生成位置和值，并根据每种可能性的概率对其优化分数进行加权）和“最大化”步骤（测试所有可能的移动并选择得分最高的一个）之间交替进行。树搜索在看到之前见过的位置时（使用转置表）、达到预定义的深度限制时，或达到极不可能的棋盘状态时（例如，从起始位置连续获得6个“4”瓷砖）终止。典型的搜索深度为4到8次移动。
启发式
使用了几种启发式方法来引导优化算法朝向有利的位置。启发式的具体选择对算法的性能有巨大影响。各种启发式方法被加权并组合成一个位置分数，用于确定给定棋盘位置的“好坏”。优化搜索然后旨在最大化所有可能棋盘位置的平均分数。实际分数，如游戏所示的，不用于计算棋盘分数，因为它过于偏向于合并瓷砖（当延迟合并可能产生很大好处时）。
最初，我使用了两个非常简单的启发式方法，为开放的方块和边缘上的大值提供“奖励”。这些启发式方法表现得相当好，经常达到16384，但从未达到32768。
Petr Morávek (@xificurk) 拿走了我的AI，并添加了两个新的启发式方法。第一个启发式方法是对非单调行和列进行惩罚，随着等级的增加而增加，确保小数字的非单调行不会强烈影响分数，但大数字的非单调行会大大损害分数。第二个启发式方法除了开放空间外，还计算了潜在合并的数量（相邻的相等值）。这两个启发式方法有助于将算法推向单调的棋盘（更容易合并），并推向具有大量合并的棋盘位置（鼓励它在可能的情况下对齐合并以获得更大效果）。
此外，Petr还使用了一种“元优化”策略（使用一种称为CMA-ES的算法）来优化启发式权重，其中权重本身被调整以获得尽可能高的平均分数。
这些变化的效果极其显著。算法从大约13%的时间达到16384瓷砖，提高到超过90%的时间，并且算法开始超过三分之一的时间达到32768（而旧的启发式方法从未一次产生32768瓷砖）。
我相信在启发式方法上仍有改进的空间。这个算法肯定还不是“最优”的，但我觉得它已经相当接近了。
AI在超过三分之一的游戏中达到32768瓷砖是一个巨大的里程碑；如果有任何人类玩家在官方游戏中（即不使用存档或撤销等工具）达到32768，我会感到惊讶。我认为65536瓷砖是可以实现的！
你可以自己尝试这个AI。代码可在https://github.com/nneonneo/2048-ai获取。
