algorithm - 2048游戏的最佳算法是什么？(What is the optimal algorithm for the game 2048?)

Question

I have recently stumbled upon the game 2048 .

(我最近偶然发现了2048游戏。)

You merge similar tiles by moving them in any of the four directions to make "bigger" tiles.

(您可以通过在四个方向上任意移动相似的图块来合并它们，以制作“更大”的图块。)

After each move, a new tile appears at random empty position with a value of either 2 or 4 .

(每次移动后，新的图块将出现在随机的空白位置，值为2或4 。)

The game terminates when all the boxes are filled and there are no moves that can merge tiles, or you create a tile with a value of 2048 .

(当所有盒子都装满并且没有可以合并磁贴的移动，或者您创建的值为2048磁贴时，游戏终止。)

One, I need to follow a well-defined strategy to reach the goal.

(第一，我需要遵循明确定义的策略才能实现目标。)

So, I thought of writing a program for it.

(因此，我想到了为此编写程序。)

My current algorithm:

(我当前的算法：)

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
}

What I am doing is at any point, I will try to merge the tiles with values 2 and 4 , that is, I try to have 2 and 4 tiles, as minimum as possible.

(我正在做的是在任何时候，我将尝试合并值2和4的图块，也就是说，我尝试将2和4图块尽可能地减少。)

If I try it this way, all other tiles were automatically getting merged and the strategy seems good.

(如果以这种方式尝试，所有其他磁贴将自动合并，并且该策略看起来不错。)

But, when I actually use this algorithm, I only get around 4000 points before the game terminates.

(但是，当我实际使用该算法时，在游戏终止之前我只能得到4000点。)

Maximum points AFAIK is slightly more than 20,000 points which is way larger than my current score.

(最高分数AFAIK略高于20,000点，这比我目前的分数还大。)

Is there a better algorithm than the above?

(是否有比以上更好的算法？)

  ask by nitish712 translate from so

Answer 1

I'm the author of the AI program that others have mentioned in this thread.

(我是该线程中其他人提到的AI程序的作者。)

You can view the AI in action or read the source .

(您可以查看AI 行动或阅读源 。)

Currently, the program achieves about a 90% win rate running in javascript in the browser on my laptop given about 100 milliseconds of thinking time per move, so while not perfect (yet!) it performs pretty well.

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

Since the game is a discrete state space, perfect information, turn-based game like chess and checkers, I used the same methods that have been proven to work on those games, namely minimax search with alpha-beta pruning .

(由于该游戏是离散的状态空间，完美的信息，基于回合的游戏（如国际象棋和西洋跳棋），因此我使用了已被证明可用于这些游戏的相同方法，即带有alpha-beta修剪的 minimax 搜索 。)

Since there is already a lot of info on that algorithm out there, I'll just talk about the two main heuristics that I use in the static evaluation function and which formalize many of the intuitions that other people have expressed here.

(由于已经有很多关于该算法的信息，因此，我将仅讨论在静态评估函数中使用的两种主要启发式方法，这些启发式方法将其他人在这里表达的许多直觉形式化。)

Monotonicity (单调性)

This heuristic tries to ensure that the values of the tiles are all either increasing or decreasing along both the left/right and up/down directions.

(这种试探法试图确保图块的值都沿着左/右和上/下方向都增加或减少。)

This heuristic alone captures the intuition that many others have mentioned, that higher valued tiles should be clustered in a corner.

(仅凭这种启发式方法就可以捕捉许多其他人提到的直觉，即更高价值的瓷砖应聚集成一角。)

It will typically prevent smaller valued tiles from getting orphaned and will keep the board very organized, with smaller tiles cascading in and filling up into the larger tiles.

(通常，它将防止较小价值的瓷砖变得孤立，并使板块井井有条，较小的瓷砖会层叠并填充到较大的瓷砖中。)

Here's a screenshot of a perfectly monotonic grid.

(这是一个完美单调网格的屏幕截图。)

I obtained this by running the algorithm with the eval function set to disregard the other heuristics and only consider monotonicity.

(我通过运行设置了eval函数的算法来忽略其他启发式算法，而仅考虑单调性，从而获得了此结果。)

Smoothness (光滑度)

The above heuristic alone tends to create structures in which adjacent tiles are decreasing in value, but of course in order to merge, adjacent tiles need to be the same value.

(仅上述启发式方法趋向于创建其中相邻区块的值减小的结构，但是当然为了合并，相邻区块需要具有相同的值。)

Therefore, the smoothness heuristic just measures the value difference between neighboring tiles, trying to minimize this count.

(因此，平滑度启发式方法只是测量相邻图块之间的值差，以尽量减少此计数。)

A commenter on Hacker News gave an interesting formalization of this idea in terms of graph theory.

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

Here's a screenshot of a perfectly smooth grid, courtesy of this excellent parody fork .

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

Free Tiles (免费瓷砖)

And finally, there is a penalty for having too few free tiles, since options can quickly run out when the game board gets too cramped.

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

And that's it!

(就是这样！)

Searching through the game space while optimizing these criteria yields remarkably good performance.

(在优化这些条件的同时搜索游戏空间会产生非常好的性能。)

One advantage to using a generalized approach like this rather than an explicitly coded move strategy is that the algorithm can often find interesting and unexpected solutions.

(使用这样的通用方法而不是显式编码的移动策略的一个优点是该算法通常可以找到有趣且出乎意料的解决方案。)

If you watch it run, it will often make surprising but effective moves, like suddenly switching which wall or corner it's building up against.

(如果您观察它的运行，它通常会做出令人惊讶但有效的举动，例如突然切换它要面对的墙或角。)

Edit: (编辑：)

Here's a demonstration of the power of this approach.

(这是这种方法的强大功能的演示。)

I uncapped the tile values (so it kept going after reaching 2048) and here is the best result after eight trials.

(我取消了图块值的上限（因此在达到2048后继续保持不变），这是八次试验后的最佳结果。)

Yes, that's a 4096 alongside a 2048. =) That means it achieved the elusive 2048 tile three times on the same board.

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