2048游戏的最佳算法是什么？

Question

我最近偶然发现了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点，这比我目前的分数还大。是否有比以上更好的算法？

Answer 1

我是该线程中其他人提到的AI程序的作者。您可以查看AI 行动或阅读源。

目前，考虑到每次移动大约100毫秒的思考时间，该程序在我的笔记本电脑上的浏览器中的javascript中运行时，可以实现约90％的获胜率，因此虽然效果不理想（但！），但它的表现还不错。

由于该游戏是离散的状态空间，完美的信息，基于回合的游戏（如国际象棋和西洋跳棋），因此我使用了已被证明可用于这些游戏的相同方法，即带有alpha-beta修剪的minimax 搜索。由于已经有很多关于该算法的信息，因此，我将仅讨论在静态评估函数中使用的两种主要启发式方法，这些启发式方法将其他人在这里表达的许多直觉形式化。

单调性

这种试探法试图确保图块的值都沿着左/右和上/下方向都增加或减少。仅凭这种启发式方法就可以捕捉许多其他人提到的直觉，即更高价值的瓷砖应聚集成一角。它通常会阻止越来越孤立的小有价值的瓷砖和将保持板非常有组织，有更小的砖级联并填充到大砖。

这里有一个完美的单调格的屏幕截图。我通过运行设置了eval函数的算法来忽略其他启发式算法，而仅考虑单调性，从而获得了此结果。

完美单调的2048板

光滑度

仅上述启发式方法趋向于创建其中相邻区块的值减小的结构，但是当然为了合并，相邻区块需要具有相同的值。因此，平滑度启发式方法只是测量相邻图块之间的值差，以尽量减少此计数。

关于Hacker News的评论者从图论的角度对该想法进行了有趣的形式化。

这是一个完美平滑的网格的屏幕截图，这要归功于出色的模仿叉。

完美光滑的2048板

免费瓷砖

最后，免费磁贴太少会受到惩罚，因为当游戏板太狭窄时，选项会很快用完。

就是这样！在优化这些条件的同时搜索游戏空间会产生非常好的性能。使用这样的通用方法而不是显式编码的移动策略的一个优点是该算法通常可以找到有趣且出乎意料的解决方案。如果您观察它的运行，它通常会做出令人惊讶但有效的举动，例如突然切换它要面对的墙或角。

编辑：

这是这种方法的强大功能的演示。我取消了图块值的上限（因此在达到2048后继续保持不变），这是八次试验后的最佳结果。

4096

是的，这是4096和2048的乘积。=）这意味着它在同一块板上完成了3倍难以捉摸的2048瓦片。