我最近偶然发现了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分，这比我目前的分数要大得多。有比上述更好的算法吗？
当前回答
我用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
其他回答
许多其他答案使用人工智能，对可能的未来、启发式、学习等进行计算成本高昂的搜索。这些令人印象深刻，可能是正确的前进方向，但我想提出另一个想法。
模拟游戏中优秀玩家使用的策略。
例如：
13 14 15 16
12 11 10 9
5 6 7 8
4 3 2 1
按照上面显示的顺序读取正方形，直到下一个正方形值大于当前值。这就带来了试图将另一个具有相同值的平铺合并到此方形中的问题。
为了解决这个问题，他们有两种移动方式，没有留下或更糟，检查这两种可能性可能会立即发现更多问题，这形成了一个依赖关系列表，每个问题都需要先解决另一个问题。我认为我在决定下一步行动时，特别是在被卡住的时候，会有一条链条，或者在某些情况下，是内部的依赖树。
瓷砖需要与邻居合并，但太小：将另一个邻居与此邻居合并。
较大的平铺：增加较小的周围平铺的值。
等
整个方法可能比这更复杂，但并不复杂。这可能是一种机械的感觉，缺乏分数、体重、神经和对可能性的深入探索。可能性之树甚至需要足够大，完全需要分支。
我是一个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平铺。
算法
while(!game_over)
{
for each possible move:
evaluate next state
choose the maximum evaluation
}
评价
Evaluation =
128 (Constant)
+ (Number of Spaces x 128)
+ Sum of faces adjacent to a space { (1/face) x 4096 }
+ Sum of other faces { log(face) x 4 }
+ (Number of possible next moves x 256)
+ (Number of aligned values x 2)
评估详细信息
128 (Constant)
这是一个常数，用作基线和其他用途，如测试。
+ (Number of Spaces x 128)
更多的空间使状态更灵活，我们乘以128（这是中值），因为填充了128个面的网格是最佳的不可能状态。
+ Sum of faces adjacent to a space { (1/face) x 4096 }
这里，我们评估有可能合并的面，通过向后评估它们，平铺2的值为2048，而平铺2048的值为2。
+ Sum of other faces { log(face) x 4 }
在这里，我们仍然需要检查堆叠的值，但以一种较小的方式，这不会中断灵活性参数，因此我们得到了[4,44]中的{x的和}。
+ (Number of possible next moves x 256)
如果一个国家对可能的转变有更大的自由度，它就会更灵活。
+ (Number of aligned values x 2)
这是对在该状态内合并的可能性的简化检查，而无需进行前瞻。
注意：常数可以调整。。
我是其他人在本主题中提到的AI程序的作者。您可以查看人工智能的运行情况或读取源代码。
目前，该程序在我的笔记本电脑上的浏览器中运行javascript时，每次移动大约需要100毫秒的思考时间，获得了大约90%的胜率，因此，尽管它还不完美（还！），但它的表现相当不错。
由于游戏是一个离散的状态空间，完美的信息，基于回合的游戏，如国际象棋和跳棋，我使用了已经被证明适用于这些游戏的相同方法，即带有alpha beta修剪的极小极大搜索。由于已经有很多关于该算法的信息，我将只讨论我在静态评估函数中使用的两种主要启发式方法，它们将其他人在这里表达的许多直觉形式化。
单调性
该启发式方法试图确保平铺的值都沿着左/右和上/下方向增加或减少。仅此启发式方法就抓住了许多其他人提到的直觉，即较高价值的瓦片应该聚集在角落中。它通常会防止价值较小的瓦片成为孤立的，并保持棋盘非常有序，较小的瓦片层叠并填充到较大的瓦片中。
这是一个完全单调的网格截图。我通过运行带有eval函数集的算法来实现这一点，从而忽略其他启发式，只考虑单调性。
平滑度
仅上述启发式方法就倾向于创建相邻瓦片值降低的结构，但当然，为了合并，相邻瓦片需要具有相同的值。因此，平滑启发式算法仅测量相邻平铺之间的值差，试图将此计数最小化。
《黑客新闻》的一位评论者用图论的方式对这一想法进行了有趣的形式化。
这是一张完美平滑的网格截图。
自由平铺
最后，由于游戏板太拥挤，选项可能会很快用完，所以免费瓷砖太少会受到惩罚。
就这样！在优化这些标准的同时搜索游戏空间会产生非常好的性能。使用像这样的通用方法而不是显式编码的移动策略的一个优点是，该算法通常可以找到有趣和意外的解决方案。如果你看着它跑，它通常会做出令人惊讶但有效的动作，比如突然切换它所建的墙或角落。
编辑：
这里展示了这种方法的威力。我取消了平铺值的上限（因此它在达到2048之后保持不变），这是八次试验后的最佳结果。
是的，这是4096和2048。=）这意味着它在同一块板上三次实现了令人难以捉摸的2048瓷砖。
我想我找到了一个非常有效的算法，因为我经常得分超过10000分，我个人最好的成绩是16000分左右。我的解决方案并不是要把最大的数字放在角落里，而是要把它放在最前排。
请参见以下代码：
while( !game_over ) {
move_direction=up;
if( !move_is_possible(up) ) {
if( move_is_possible(right) && move_is_possible(left) ){
if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) )
move_direction = left;
else
move_direction = right;
} else if ( move_is_possible(left) ){
move_direction = left;
} else if ( move_is_possible(right) ){
move_direction = right;
} else {
move_direction = down;
}
}
do_move(move_direction);
}
