我最近偶然发现了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的最高分数略高于20000分，这比我目前的分数要大得多。有比上述更好的算法吗？
当前回答
我是其他人在本主题中提到的AI程序的作者。您可以查看人工智能的运行情况或读取源代码。
目前，该程序在我的笔记本电脑上的浏览器中运行javascript时，每次移动大约需要100毫秒的思考时间，获得了大约90%的胜率，因此，尽管它还不完美（还！），但它的表现相当不错。
由于游戏是一个离散的状态空间，完美的信息，基于回合的游戏，如国际象棋和跳棋，我使用了已经被证明适用于这些游戏的相同方法，即带有alpha beta修剪的极小极大搜索。由于已经有很多关于该算法的信息，我将只讨论我在静态评估函数中使用的两种主要启发式方法，它们将其他人在这里表达的许多直觉形式化。
单调性
该启发式方法试图确保平铺的值都沿着左/右和上/下方向增加或减少。仅此启发式方法就抓住了许多其他人提到的直觉，即较高价值的瓦片应该聚集在角落中。它通常会防止价值较小的瓦片成为孤立的，并保持棋盘非常有序，较小的瓦片层叠并填充到较大的瓦片中。
这是一个完全单调的网格截图。我通过运行带有eval函数集的算法来实现这一点，从而忽略其他启发式，只考虑单调性。
平滑度
仅上述启发式方法就倾向于创建相邻瓦片值降低的结构，但当然，为了合并，相邻瓦片需要具有相同的值。因此，平滑启发式算法仅测量相邻平铺之间的值差，试图将此计数最小化。
《黑客新闻》的一位评论者用图论的方式对这一想法进行了有趣的形式化。
这是一张完美平滑的网格截图。
自由平铺
最后，由于游戏板太拥挤，选项可能会很快用完，所以免费瓷砖太少会受到惩罚。
就这样！在优化这些标准的同时搜索游戏空间会产生非常好的性能。使用像这样的通用方法而不是显式编码的移动策略的一个优点是，该算法通常可以找到有趣和意外的解决方案。如果你看着它跑，它通常会做出令人惊讶但有效的动作，比如突然切换它所建的墙或角落。
编辑：
这里展示了这种方法的威力。我取消了平铺值的上限（因此它在达到2048之后保持不变），这是八次试验后的最佳结果。
是的，这是4096和2048。=）这意味着它在同一块板上三次实现了令人难以捉摸的2048瓷砖。
其他回答
我在这里复制我博客上的一篇文章的内容
我提出的解决方案非常简单，易于实施。虽然，它已经达到131040分。给出了算法性能的几个基准。
算法
启发式评分算法
我的算法所基于的假设相当简单：如果你想获得更高的分数，那么棋盘必须尽可能保持整洁。特别地，最优设置由瓦片值的线性和单调递减顺序给出。这种直觉也会给你一个平铺值的上限：其中n是板上平铺的数量。
（如果需要时随机生成4个图块而不是2个图块，则有可能达到131072图块）
两种可能的董事会组织方式如下图所示：
为了以单调递减的顺序执行瓷砖的排序，得分si计算为板上线性化值的和乘以公共比率r＜1的几何序列的值。
可以同时评估多个线性路径，最终得分将是任何路径的最大得分。
决策规则
实现的决策规则不太聪明，Python代码如下：
@staticmethod
def nextMove(board,recursion_depth=3):
m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
return m
@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
bestScore = -1.
bestMove = 0
for m in range(1,5):
if(board.validMove(m)):
newBoard = copy.deepcopy(board)
newBoard.move(m,add_tile=True)
score = AI.evaluate(newBoard)
if depth != 0:
my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
score += my_s*pow(base,maxDepth-depth+1)
if(score > bestScore):
bestMove = m
bestScore = score
return (bestMove,bestScore);
minmax或Expectimimax的实现肯定会改进算法。显然更多复杂的决策规则会降低算法的速度，并且需要一些时间来实现。我将在不久的将来尝试一个最小值实现。（敬请关注）
基准
T1-121测试-8个不同路径-r=0.125T2-122测试-8个不同路径-r=0.25T3-132测试-8个不同路径-r=0.5T4-211测试-2条不同路径-r=0.125T5-274测试-2条不同路径-r=0.25T6-211测试-2条不同路径-r=0.5
在T2的情况下，十次测试中有四次生成平均分数为42000的4096分图块
Code
该代码可以在GiHub上的以下链接找到：https://github.com/Nicola17/term2048-AI它基于term2048，用Python编写。我将尽快用C++实现一个更高效的版本。
我是一个2048控制器的作者，它的得分比本主题中提到的任何其他程序都要高。github上提供了控制器的有效实现。在单独的回购中，还有用于训练控制器状态评估功能的代码。本文描述了训练方法。
控制器使用expectimax搜索，该搜索具有通过时间差学习（强化学习技术）的变体从零开始学习的状态评估函数（没有人类2048专业知识）。状态值函数使用n元组网络，它基本上是板上观察到的模式的加权线性函数。总共涉及超过10亿重量。
表演
1次移动/秒：609104（平均100局）
10次移动/秒：589355（平均300场）
3局（约1500步/秒）：511759（平均1000局）
10次移动/秒的平铺统计如下：
2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%
（最后一行表示在板上同时具有给定的瓷砖）。
对于3层：
2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%
然而，我从未观察到它获得65536平铺。
许多其他答案使用人工智能，对可能的未来、启发式、学习等进行计算成本高昂的搜索。这些令人印象深刻，可能是正确的前进方向，但我想提出另一个想法。
模拟游戏中优秀玩家使用的策略。
例如：
13 14 15 16
12 11 10 9
5 6 7 8
4 3 2 1
按照上面显示的顺序读取正方形，直到下一个正方形值大于当前值。这就带来了试图将另一个具有相同值的平铺合并到此方形中的问题。
为了解决这个问题，他们有两种移动方式，没有留下或更糟，检查这两种可能性可能会立即发现更多问题，这形成了一个依赖关系列表，每个问题都需要先解决另一个问题。我认为我在决定下一步行动时，特别是在被卡住的时候，会有一条链条，或者在某些情况下，是内部的依赖树。
瓷砖需要与邻居合并，但太小：将另一个邻居与此邻居合并。
较大的平铺：增加较小的周围平铺的值。
等
整个方法可能比这更复杂，但并不复杂。这可能是一种机械的感觉，缺乏分数、体重、神经和对可能性的深入探索。可能性之树甚至需要足够大，完全需要分支。
我使用expectimax优化开发了2048 AI，而不是@ovolve算法使用的最小值搜索。AI简单地对所有可能的移动执行最大化，然后对所有可能瓦片产生进行期望（由瓦片的概率加权，即，4个瓦片为10%，2个瓦片为90%）。据我所知，不可能删减expectimax优化（除了删除极不可能的分支），因此所使用的算法是经过仔细优化的暴力搜索。
表演
AI在其默认配置（最大搜索深度为8）中执行移动需要10毫秒到200毫秒，具体取决于板位置的复杂性。在测试中，AI在整个游戏过程中实现了每秒5-10次的平均移动速度。如果搜索深度被限制在6次移动，AI可以轻松地每秒执行20次以上的移动，这使得观看更加有趣。
为了评估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]）。
评分也使用表格查找来完成。这些表包含对所有可能的行/列计算的启发式得分，一个板的最终得分只是每行和每列的表值之和。
这种棋盘表示，以及移动和得分的表格查找方法，允许AI在短时间内搜索大量游戏状态（在我2011年中期笔记本电脑的一个核心上，每秒超过10000000个游戏状态）。
expectimax搜索本身被编码为递归搜索，它在“期望”步骤（测试所有可能的平铺生成位置和值，并根据每个可能性的概率加权其优化分数）和“最大化”步骤（检测所有可能的移动并选择具有最佳分数的移动）之间交替。当树搜索看到之前看到的位置（使用换位表）、达到预定义的深度限制或达到极不可能达到的板状态时（例如，通过从起始位置开始一行获得6“4”块而达到），树搜索终止。典型的搜索深度为4-8次移动。
启发式
使用几种启发式方法将优化算法引向有利位置。启发式算法的精确选择对算法的性能有着巨大的影响。各种启发式算法被加权并组合成一个位置得分，这决定了给定的董事会位置有多“好”。然后，优化搜索将旨在最大化所有可能董事会位置的平均得分。如游戏所示，实际得分不用于计算棋盘得分，因为它的权重太大，有利于合并瓦片（当延迟合并可能产生很大的好处时）。
最初，我使用了两种非常简单的启发式方法，即为开放正方形和边缘值较大的正方形授予“奖金”。这些启发式算法表现得很好，经常达到16384，但从未达到32768。
Petr Morávek（@xivicurk）使用了我的AI，并添加了两种新的启发式方法。第一个启发式是对非单调行和列的惩罚，这些行和列随着排名的增加而增加，从而确保小数字的非单调行不会强烈影响分数，但大数字的非非单调行会严重影响分数。第二个启发式算法除了计算开放空间之外，还计算了潜在合并（相邻的相等值）的数量。这两种启发式方法用于将算法推向单调板（更容易合并），以及大量合并的板位置（鼓励其在可能的情况下对齐合并以获得更大的效果）。
此外，Petr还使用“元优化”策略（使用称为CMA-ES的算法）优化了启发式权重，其中权重本身被调整以获得可能的最高平均分数。
这些变化的影响极其显著。该算法在大约13%的时间内实现了16384个瓦片，在90%的时间内完成了它，并且该算法在1/3的时间内开始实现32768个瓦片（而旧的启发式算法从未产生过32768个）。
我相信启发式方法还有改进的空间。这个算法肯定还不是“最佳”的，但我觉得它已经接近了。
人工智能在超过三分之一的游戏中获得32768分，这是一个巨大的里程碑；我会很惊讶地听到是否有人类玩家在官方游戏中达到了32768（即不使用保存状态或撤销等工具）。我认为65536瓷砖触手可及！
你可以自己尝试人工智能。该代码位于https://github.com/nneonneo/2048-ai.
该算法对于赢得游戏来说不是最佳的，但就性能和所需代码量而言，它是相当最佳的：
if(can move neither right, up or down)
direction = left
else
{
do
{
direction = random from (right, down, up)
}
while(can not move in "direction")
}
