什么是2048年游戏的最佳算法？
我最近偶然发现了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的任意位置来执行移动，具体取决于电路板位置的复杂程度。 在测试中，AI在整个游戏过程中的平均移动速度为每秒5-10次。 如果搜索深度限制为6次移动，AI可以很容易地每秒执行20次以上的移动，这使得一些有趣的观看。
为了评估AI的分数表现，我跑了100次AI（通过遥控器连接到浏览器游戏）。 对于每个瓦片，这里是至少一次获得该瓦片的游戏比例：
2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%
全部最低分数为124024; 最高得分是794076.中位得分是387222.人工智能从未获得2048瓦（所以它从未在100场比赛中失败过一次）。 实际上，它在每次运行中至少实现了8192个瓦片！
以下是最佳运行的截图：
这场比赛在96分钟内完成了27830次移动，平均每秒移动4.8次。
履行
我的方法将整个板（16项）编码为一个64位整数（其中tile是nybbles，即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（即不使用类似于投资或撤销的工具）。 我认为65536瓦片是可及的！
你可以尝试自己的AI。 该代码可在https://github.com/nneonneo/2048-ai获得。
我是其他人在此主题中提到的AI程序的作者。 您可以查看正在使用的AI或读取源代码。
目前，该程序在我的笔记本电脑中的浏览器中获得了约90％的赢率，运行时间大约为100毫秒，所以虽然不够完美（但！），它表现相当不错。
由于游戏是一个离散的状态空间，完美的信息，像国际象棋和跳棋这样的基于回合的游戏，我使用了已经被证明可以在这些游戏上运行的相同方法，即使用alpha-beta修剪进行minimax搜索。 由于已经有很多关于该算法的信息，所以我将仅讨论我在静态评估函数中使用的两种主要启发式，并将其他人在这里表达的许多直觉形式化。
单调性
这种启发式方法试图确保瓷砖的值沿着左/右和上/下方向都增加或减小。 单独的这种启发式捕捉许多其他人提到的直觉，认为更高价值的瓷砖应该聚集在一个角落。 它通常会防止价值较小的瓷砖变得孤立，并保持电路板非常有组织，而较小的瓷砖层叠并填充到较大的瓷砖中。
这是一个完美单调网格的屏幕截图。 我通过运行eval函数设置忽略其他启发式并仅考虑单调性的算法来获得此结果。
顺利
单独的上述启发式倾向于创建相邻的瓷砖价值下降的结构，但当然为了合并，相邻的瓷砖需要具有相同的价值。 因此，平滑启发式只是测量相邻区块之间的值差异，试图将此计数最小化。
“黑客新闻”的一位评论者用图论的方式对这个想法进行了有趣的形式化。
这是一个完美平滑的网格截图，由这个优秀的模仿分岔提供。
免费瓷砖
最后，免费磁贴太少会导致惩罚，因为当游戏板变得太狭窄时，选项可能会很快耗尽。
就是这样！ 在优化这些标准的同时搜索游戏空间可获得非常好的性能。 使用这种通用方法而不是明确编码的移动策略的一个优点是该算法通常可以找到有趣且意想不到的解决方案。 如果你看它运行，它通常会令人惊讶但有效的举动，例如突然切换它正在建立的墙或角落。
编辑：
这是这种方法的强大功能的演示。 我打开瓦片值（因此在达到2048之后保持不变），这是八次试验后的最佳结果。
是的，这是4096和2048一样。=）这意味着它在同一块电路板上实现了难以捉摸的2048瓦。
编辑：这是一个天真的算法，建模人类有意识的思维过程，并得到非常薄弱的结果相比，人工智能，搜索所有可能性，因为它只看起来前面一块。 它在响应时间表早期提交。
我已经完善了算法并打败了游戏！ 它可能会失败，因为接近尾声的简单运气不好（你不得不向下移动，这是你永远不应该做的，并且一个贴片会出现在你最高位置的位置）。试着保持顶行被填满，所以向左移动不会打破模式），但基本上你最终有一个固定的部分和移动部分玩。 这是你的目标：
这是我默认选择的模型。
1024 512 256 128
8 16 32 64
4 2 x x
x x x x
所选的角落是任意的，你基本上从不按下一个键（禁止的移动），如果你这样做，你再次按相反的方法并尝试修复它。 对于未来的贴图，模型总是期望下一个随机贴图是2，并且出现在当前模型的反面（而第一行是不完整的，在右下角，一旦第一行完成，左下角角）。
算法如下。 大约80％的胜利（看起来总是有可能用更多的“专业”AI技术获胜，但我不确定这一点。）
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