共计 2665 个字符，预计需要花费 7 分钟才能阅读完成。
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. 伪代码
当初咱们晓得了算法的工作原理，接下来摸索一些详细描述算法的伪代码。
我对游戏的理论玩法并不感冒，只对确定挪动的算法有点趣味，所以从这里开始：
当初到了这样的步骤：从第一个方块开始，模仿每一个可能的动作，并返回得分最好的那一个。因而咱们须要为新模仿的方格生成分数。
因为应用的是递归算法，所以我减少了一个深度限度，用来进行，否则可能会无止境运行上来。
这又是一个递归，模仿了每个人挪动肯定数量的步骤，并确定哪些挪动能够拿到最佳的后果。
剩下的惟一事件就是为挪动后失去的每个方格，计算出最终分数。当然，这也没有美中不足的算法，不同的因素会造成不同的后果。
5. 性能优化
到目前为止，咱们曾经有了一种算法来尝试解决游戏问题，然而它效率不高。因为过程的个性，总是会有肯定水平的反复。
咱们曾经在下面的算法中做了一些优化，不解决对游戏没有任何影响的挪动。然而，咱们还有其余办法能够缩小工作量，例如跟踪挪动的累积概率，以及在挪动的概率太低时进行。
咱们还能够动静确定深度次数的限度。下面的伪代码的硬编码限度为 3，但咱们能够在计算开始时依据方格的形态动静计算该限度。
此外，因为能够屡次从新拜访同一方格的地位，因而咱们能够记住这些地位并缓存这些地位的分数，而不用每次都从新计算它们。潜在地，咱们能够提前生成每个方块可能的地位，然而最多有 2048 个方块，281,474,976,710,656 个可能的地位，因而这可能不可行。
然而，咱们能够做的最重要的优化是调整生成方格分数的算法。计分的因素和权重与咱们的算法施展得如何间接相干。
六，论断
2048 是一款十分乏味的游戏，能够尝试破解。尽管没有完满的办法，然而咱们能够用一些启发式的办法，来摸索游戏的最佳门路。
这类准则同样实用其余类型的两人游戏（例如国际象棋），在这种游戏中，无奈精确预测他人会做什么。
思考一下，棋牌类游戏电脑托管代打的策略是什么呢？在评论区留下你的答案吧！
如果你感觉文章还不错，记得关注公众号：锅外的大佬
刘一手的博客