我最近偶然发现了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分，这比我目前的分数要大得多。有比上述更好的算法吗？
当前回答
我是一个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平铺。
其他回答
我对这款游戏的人工智能的想法产生了兴趣，它不包含硬编码的智能（即没有启发式、评分功能等）。人工智能应该只“知道”游戏规则，并“弄清楚”游戏玩法。这与大多数AI（如本线程中的AI）形成对比，在这些AI中，游戏玩法基本上是由代表人类对游戏理解的评分函数控制的暴力。
AI算法
我发现了一个简单但令人惊讶的好游戏算法：为了确定给定棋盘的下一步，AI使用随机移动在内存中玩游戏，直到游戏结束。这是在跟踪最终比赛分数的同时进行的几次。然后计算每次开始移动的平均结束得分。平均结束得分最高的起始动作被选为下一个动作。
每次移动仅运行100次（即内存游戏），AI可实现2048次平铺80%的次数和4096次平铺50%的次数。使用10000次运行可获得2048个平铺100%，4096个平铺70%，8192个平铺约1%。
在行动中看到它
最佳成绩如下：
关于这个算法的一个有趣的事实是，尽管随机游戏毫无疑问非常糟糕，但选择最佳（或最不糟糕）的招式会带来非常好的游戏效果：一个典型的人工智能游戏可以达到70000点，并持续3000步，但任何给定位置的记忆中随机游戏在死亡前都会在大约40次额外的招式中平均增加340点。（您可以通过运行AI并打开调试控制台自行查看。）
这张图说明了这一点：蓝线显示了每次移动后的棋盘得分。红线显示了该位置的算法的最佳随机运行结束游戏分数。本质上，红色值是将蓝色值向上拉向它们，因为它们是算法的最佳猜测。有趣的是，在每一点上，红线都比蓝线略高一点，但蓝线仍在不断增加。
我觉得很奇怪的是，算法不需要实际预测好的游戏玩法，就可以选择产生它的动作。
后来搜索发现，这个算法可能被归类为纯蒙特卡罗树搜索算法。
实施和链接
首先，我创建了一个JavaScript版本，可以在这里看到。这个版本可以在适当的时间内运行100次。打开控制台获取更多信息。（来源）
后来，为了玩更多，我使用了@nneonneo高度优化的基础设施，并用C++实现了我的版本。这个版本允许每次移动最多100000次，如果你有耐心的话，甚至可以达到1000000次。提供建筑说明。它在控制台中运行，也有一个遥控器来播放网络版本。（来源）
后果
令人惊讶的是，增加跑步次数并不能显著改善比赛。这一策略似乎有一个限制，即4096个区块和所有较小的区块在80000点左右，非常接近8192个区块。将跑步次数从100次增加到100000次会增加达到这一分数限制（从5%增加到40%）但无法突破的几率。
在关键位置临时增加到1000000次的10000次跑步打破了这一障碍，达到129892分的最高得分和8192分的次数不到1%。
改进
在实现这个算法后，我尝试了许多改进，包括使用最小或最大分数，或最小、最大和平均值的组合。我还尝试了使用深度：我没有尝试每次移动K次，而是尝试了给定长度的每次移动列表（例如“向上、向上、向左”）的K次移动，并选择最佳得分移动列表的第一个移动。
后来我实现了一个得分树，它考虑了在给定的移动列表之后能够进行移动的条件概率。
然而，这些想法都没有比简单的第一个想法显示出任何真正的优势。我将这些想法的代码注释在C++代码中。
我确实添加了一个“深度搜索”机制，当任何一次运行意外达到下一个最高的平铺时，该机制将运行次数临时增加到1000000次。这提供了时间上的改进。
我很想知道是否有人有其他改进想法来保持人工智能的领域独立性。
2048个变体和克隆
为了好玩，我还将AI实现为书签，与游戏的控件挂钩。这使得AI可以与原始游戏及其许多变体一起工作。
这是可能的，因为AI的领域独立性。一些变体非常独特，例如六边形克隆。
我是一个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平铺。
这不是对OP问题的直接回答，这是我迄今为止试图解决同一问题的更多东西（实验），并获得了一些结果和一些我想分享的观察结果，我很好奇我们能否从中获得一些进一步的见解。
我刚刚尝试了使用alpha beta修剪的minimax实现，搜索树深度截止值为3和5。我试图解决4x4网格的相同问题，作为edX课程ColumbiaX:CSMM101x人工智能（AI）的项目作业。
我应用了两个启发式评估函数的凸组合（尝试了不同的启发式权重），主要来自直觉和上面讨论的函数：
单调性可用的可用空间
在我的情况下，电脑玩家是完全随机的，但我仍然假设了对抗性设置，并将AI玩家代理实现为最大玩家。
我有4x4网格来玩游戏。
观察结果：
如果我给第一个启发式函数或第二个启发式函数分配了太多权重，那么AI玩家获得的分数都很低。我对启发式函数进行了许多可能的权重分配，并采用了凸组合，但很少有AI玩家能够得分2048。大多数时候，它要么停在1024或512。
我也尝试过拐角启发式，但出于某种原因，它会使结果更糟，凭直觉为什么？
此外，我尝试将搜索深度截止值从3增加到5（我不能再增加了，因为即使在修剪的情况下，搜索该空间也超过了允许的时间），并添加了一个启发式方法，它查看相邻平铺的值，如果它们可以合并，则会给出更多的点，但我仍然无法获得2048。
我认为使用Expectimax而不是minimax会更好，但我仍然希望只使用minimax来解决这个问题，并获得2048或4096等高分。我不确定我是否遗漏了什么。
以下动画显示了AI代理与计算机玩家玩游戏的最后几个步骤：
任何见解都将非常有用，提前感谢。（这是我博客文章的链接：https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/以及youtube视频：https://www.youtube.com/watch?v=VnVFilfZ0r4)
以下动画显示了游戏的最后几个步骤，其中AI玩家代理可以获得2048分，这一次还添加了绝对值启发式：
下图显示了玩家AI代理探索的游戏树，假设计算机是对手，只需一步：
我用Haskell编写了一个2048解算器，主要是因为我现在正在学习这种语言。
我的游戏实现与实际游戏略有不同，因为新的平铺始终是“2”（而不是90%2和10%4）。而且，新的平铺不是随机的，而是始终是左上角第一个可用的平铺。该变体也称为Det 2048。
因此，此解算器是确定性的。
我使用了一种支持空瓷砖的穷举算法。它在深度1-4时表现得很快，但在深度5时，每次移动大约1秒就会变得很慢。
下面是实现求解算法的代码。网格表示为16长度的整数数组。得分是通过计算空方块的数量来完成的。
bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]
gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]
我认为它很简单，很成功。当从空网格开始并在深度5处求解时，其结果为：
Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]
Game Over
源代码可在此处找到：https://github.com/popovitsj/2048-haskell
我在这里复制我博客上的一篇文章的内容
我提出的解决方案非常简单，易于实施。虽然，它已经达到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++实现一个更高效的版本。
