2048游戏的最佳算法是？来看看AI版作者的回答_最新动态_新闻资讯_程序员俱乐部

　　英文原文：What is the optimal algorithm for the game 2048?

　　问题 by nitish712

　　我最近偶然发现一款叫2048 的游戏。你需要通过上下左右方向键来移动合并值相同的方块(Title)。每一次移动之后，一个值为 2 或者 4 的新方块会随机出现在某个空位置。如果所有位置都塞满方块，并且没有值相同的方块可以合并的时候，游戏结束。游戏的目标是合并出一个值为 2048 的方块。

　　我需要遵循一套定义良好的策略来实现这个目标。所以我想到写个程序来实现。我当前的算法如下：

while(!game_over)
{
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with large number of merges
}

　　我所做的是，在任何时刻，我都尝试合并值为 2 或者 4 的方块，也就是我会尝试让值为 2 和 4 的方块越少越好。如果我尝试那么做，其它的方块会自动的合并，看起来像是个好策略。

　　但是当我真正使用这套算法的时候，我大概只能得到 4000 分，游戏就结束了。游戏的最高分应该是 20000 多点，远超我当前的分数。有比上面策略更好的算法吗？

　　最佳回答 by ovolve

　　我是 AI 程序的作者，前面也有人提到 AI 程序。你可以看 AI 版游戏，或者直接阅读源代码。

　　当前，这套运行在我笔记本浏览器的 javascript 程序能够达到 90% 左右的胜率，每次移动的思考时间是 100 毫秒。尽管不是最完美，但做得还不赖。

　　既然这个游戏是一个离散状态空间，信息完备的回合制游戏，类似于象棋和国际跳棋，那么我就使用了针对这些游戏的证明过的行之有效的方法。一套叫 minimax search 的算法，结合了 alpha-beta pruning。既然已经有很多信息解释了这套算法，那么我就仅谈谈我在 static evaluation function 中使用到的两个重要概念。这将会把一些人在这里表达的直觉形式化。

　　单调性(Monotonicity)

　　这个概念保证方块的值沿着上下左右方向的，要么增加，要么减少。这个概念单独地解释了一个大家提到的直觉，值较大的方块应该聚集到某一个角落。这将有助于阻止值小的方块被孤立起来，也将让面板保持良好的组织结构，使得值小的方块渐进层叠式的并逐步合并为值大的方块。

　　下图是一个有完美单调性格子的截屏。我通过运行 eval 函数被设置为忽略其它概念的算法获得，仅仅考虑单调性。

　　平滑性(Smoothness)

　　上面的概念倾向于构造值递减的结构，但如要合并，相邻的方格值必须相同。因此，平滑性衡量相邻方格值的差，并尝试减少差。

　　Hacker News 上的一个评论者用图论给出了一个平滑性的有趣解释。来源于 2048 的一个优秀分支。

　　下图是个有完美单平滑性的截屏。

　　空闲方块(Free Tiles)

　　最后，有一个针对空闲格子过少的惩罚。毕竟面板过于拥挤的时候，选择受限且很快会被用完。

　　就是这样。扫描游戏格子，同时优化以上标准，这会产生相当好的表现。与明确硬编码的移动策略相比，这种使用通用性的方法有一个优点，这种算法可以找到有趣且难以预料的解决方案。如果你观察它运行，它经常会做出一些惊奇但有效的移动，比如突然转向一个相反的墙或者角落。

　　修改

　　这是该方法强大能力的一个展示。我拿掉了方格值大小的限制（到 2048 之后还可以继续运行，下图是 8 次尝试中最好一次的截屏，是的，那可是一个 4096 外加一个 2048），那意味着在同一个面板上它完成了 3 次困难的 2048 方块。

　　翻译： 伯乐在线 - kimylrong

　　译文链接： http://blog.jobbole.com/63888/