2048游戏通关算法 - 新闻 - SegmentFault
基本的算法是，如果2^k是最大的数字，那么我们努力将2^(k-1)放在它的旁边，然后再把2^(k-2)放在2^(k-1)的旁边，以此类推。
为了达成这一点，我们努力将最大的数字放在角落，然后将第二大的数字放在它旁边，以此类推。将最大的数字放在角落，这样就可以留出足够的空间来组合出更大的数字。
最终我们期望形成这样的图形：
这是适用于人类的算法，如果是机器呢？可以使用更强力、复杂的算法。
ovolve编写了一个针对2048的AI程序，可以自动帮你通关。
在机器的眼里，2048是一个回合制的游戏，是一个离散的状态空间，和象棋之类的游戏一样。因此完全可以使用成熟的极小化极大 + α-β剪枝算法。为了提升搜索的效率，考虑了两个因素：
- 单调性
- 平滑性
单调性指尽量使各个方向上的数字保持单调（递增或递减），这样可以防止小数字被分割开来。
为了便于合并，相邻的块（tile）差距要尽可能地小，这通过衡量平滑性来判断。
我们可以从图论的角度来解释平滑性。我们可以把游戏的状态看成是G(V, E)，其中V代表活动的块的集合，而E代表连接相邻块的边角，边角的差距通过函数c(v1, v2)来衡量。因为推进游戏要求相邻块数值相同，也就是说c(v1, v2)返回0。因此我们需要尽可能地减少相邻块的差距，或者说，确保移动导致各处相邻块c(v1, v2)之和最小。
通过这样的算法，我们能得到大约90%的胜率，同时也有不错的性能。（没人愿意等上半天才看到AI动一步……
Read full article from 2048游戏通关算法 - 新闻 - SegmentFault
No comments:
Post a Comment