小游戏2048最佳算法怎么实现？思路全解析！
共 3094字，需浏览 7分钟
·
2020-11-23 23:40
点击上方蓝色“程序猿DD”，选择“设为星标”
回复“资源”获取独家整理的学习资料！
作者 | 刘一手
1.简介
很多人都玩过2048，我就比较老套，因为我一向看不上这类单机游戏。但是就在某一天泡脚的无聊时光，拿了媳妇儿的手机，左看看右点点，莫名打开了2048。嗯... 这真是一款打发无聊时光的 "good game"。通过滑动来使得每行或每列相邻并且相同的数字相加而得到一个最大的数字，最后的数字越大，得分越高！于是，我在想，是否能像魔方一样，有一定的套路来帮助我们决定每一步该往哪个方向滑动最佳，以便获得最好的成绩呢？
2.如何玩2048
2048是在4×4方格中玩的游戏。方格的每个位置都可能是空的，也可能是一个带有数字的方块。
开始游戏时，方格上会在随机位置产生两个方块，数字为“ 2”或“ 4”。每个方块都有10％的几率是“ 4”，否则为“2”。
通过将所有方块向某个方向（上，下，左或右）移动来进行游戏。这样做时，彼此相邻且一起移动的具有相同值的所有方块将合并成一个新的方块，该方块的值等于前两个方块的和：
游戏面板
进行滑动后，将在随机位置产生一个新的方块。新方块有 90% 的几率为 ”2“, 10% 的几率是 ”4“。
然后，继续进行游戏，直到方格中不再有能移动的方块为止。
按理来说，这游戏的目标是达到一个值为“ 2048”的方块就结束了。但是，we never stop，我们可以继续进行游戏，来争取更大的胜利。理论上，方块最大值为 “ 131072” 。
3.问题说明
想要解决这个游戏，是个灰常因缺斯汀的问题。因为我们不仅要正确预测每个新方块产生的位置，而且还要正确地预测它是“ 2”还是“ 4”。这是随机事件，理论上每一次都预测正确是不可能的。
因此，不可能有一种算法每次都能轻松而正确解决难题。我们能尽可能做到的玩好这个概率游戏，确定每个步骤的最佳操作。
不管什么时候，我们只能采取四种行为，然后面临的挑战是确定这四项举措中哪一项将取得最佳的长期效果。
我们的算法基于 [Expectimax] 算法，它本身是 [Minimax] 算法的一种变体，但是树的路由会根据它们发生的可能性进行加权。
从本质上讲，我们将游戏视为两人游戏：
玩家一（人类玩家）可以向四个方向的某个方向移动方块。 玩家二（计算机玩家）可以将方块放置在方格的任一空白位置。
基于此，我们可以根据每个动作发生的概率对每个动作生成结果树。然后，这可以为我们提供确定哪种人员举动可能给出最佳结果所需的详细信息。
3.1. 游戏流程图
游戏玩法的一般流程：
我们可以在“添加随机方块”过程中看到游戏的随机性——既要找到随机的正方形来添加方块，又要为方块选择一个随机值。
**然后，我们面临的挑战是在“确定下一步行动”步骤中确定要做什么。**这是我们玩游戏的算法。
总体上看似看似简单：
我们需要做的是模拟每一种可能，确定哪个滑动给出最佳结果，然后使用它。
因此，我们现在将算法简化为模拟任何给定的移动并为结果生成分数。
这是一个分为两部分的过程。第一步是看是否可以移动，如果不能移动，则以“ 0”的分数提前中止。如果可以移动，那么我们将继续进行真正的算法，在该算法中确定移动的效果如何：
3.2 确定下一步行动
到目前为止，算法的主要部分是模拟滑动，然而关键的问题是：如何为每个可能的移动进行评分。这下就是 Expectimax 算法发挥作用的时候了！
我将模拟两个玩家的所有可能动作，并进行几个步骤，然后看看其中哪个能带来最佳结果。
对于人类玩家而言，只有“上”，“下”，“左”和“右”的这四个动作。对于计算机则是，将“ 2”或“ 4” 方块随机放置在空白的位置：
该算法是递归的，每个递归步骤只有在距离真实游戏中的实际移动有一定深度时才会停止。这样导致流程图会循环返回自身，但实际上我们将这么做：
1.如果处于极限深度则停止，为当前模拟的方格计算分数。 2.计算机模拟所有可能的移动：模拟任何可能的人类玩家移动，返回人的移动，并计算出的分数。 3.对模拟移动计算出的分数相加，然后对该移动发生的可能性进行加权。
完成此操作后，我们将所有计算出的分数相加，这就是我们要从当前游戏板上进行的移动的最终分数。因为我们执行了四次操作（从当前游戏界面开始，每个可能的动作都获得一个），所以我们最终得到了四个分数，其中得分最高的就是应该做出的动作。
3.3. 计分
此时，剩下要做的就是计算方格的分数。但还需要考虑，如何从这个位置继续得分。
通过添加几个因素以及适当的权重，可以实现很多方法。例如：
空方块数 可能合并的次数——即，两个相邻位置中相同数字的次数 每个方块上的最大值 所有方块的总和 方格的单一性——确定方格的结构好坏，使得方块的值在一个方向上增加。
4.伪代码
现在我们知道了算法的工作原理，接下来探索一些详细描述算法的伪代码。
我对游戏的实际玩法并不感冒，只对确定移动的算法有点兴趣，所以从这里开始：
算法1-2
现在到了这样的步骤：从第一个方块开始，模拟每一个可能的动作，并返回得分最好的那一个。因此我们需要为新模拟的方格生成分数。
因为使用的是递归算法，所以我增加了一个深度限制，用来停止，否则可能会无止境运行下去。
算法3
算法4
这又是一个递归，模拟了每个人移动一定数量的步骤，并确定哪些移动可以拿到最佳的结果。
剩下的唯一事情就是为移动后得到的每个方格，计算出最终分数。当然，这也没有十全十美的算法，不同的因素会造成不同的结果。
算法5
5.性能优化
到目前为止，我们已经有了一种算法来尝试解决游戏问题，但是它效率不高。由于过程的特性，总是会有一定程度的重复。
我们已经在上面的算法中做了一些优化，不处理对游戏没有任何影响的移动。但是，我们还有其他方法可以减少工作量，例如跟踪移动的累积概率，以及在移动的概率太低时停止。
我们还可以动态确定深度次数的限制。上面的伪代码的硬编码限制为3，但我们可以在计算开始时根据方格的形状动态计算该限制。
此外，由于可以多次重新访问同一方格的位置，因此我们可以记住这些位置并缓存这些位置的分数，而不必每次都重新计算它们。潜在地，我们可以提前生成每个方块可能的位置，但是最多有2048个方块，281,474,976,710,656个可能的位置，因此这可能不可行。
但是，我们可以做的最重要的优化是调整生成方格分数的算法。计分的因素和权重与我们的算法发挥得如何直接相关。
6.结论
2048是一款非常有趣的游戏，可以尝试破解。虽然没有完美的方法，但是我们可以用一些启发式的方法，来探索游戏的最佳路径。
这类原则同样适用其他类型的两人游戏（例如国际象棋），在这种游戏中，无法准确预测别人会做什么。
思考一下，棋牌类游戏电脑托管代打的策略是什么呢？在评论区留下你的答案吧！
【往期推荐】
2020-11-22
2020-11-21
2020-11-21
2020-11-20
2020-11-19
扫一扫，关注我
一起学习，一起进步
每周赠书，福利不断
﹀
﹀
﹀
深度内容
推荐加入
1