3×3 棋盘上的 2048 游戏博弈分析
文章背景与核心概要
本文探讨了将经典益智游戏《2048》缩小到 3×3 棋盘上的穷举博弈论分析。作者 Simon Tatham 最初出于在等待代码编译等碎片时间内寻找更快速游玩体验的需求，自己编写了一个 3×3 版本的 2048，并利用动态规划和带记忆的递归对所有可能的棋盘状态进行了全面分析。
文章的核心发现包括：由于 3×3 的状态空间较小，完美博弈可以被精确计算；通过对平局和概率的推演，完美玩家有极高概率达成 256（约 99.6%）和 512（约 73.7%）方块，但达到 1024 极其罕见（约 1.1%），而达到 2048 在数学上则是绝对不可能的。此外，分析揭示了从 4×4 的“边缘策略”向 3×3 的“2×2 角落方块策略”的转变，并进一步建模了对抗恶意掉落生成器（“撒旦”）时的极限边界。
目录
引言
几年前，益智游戏《2048》非常流行。我觉得它很有趣，但稍微有些太长了。我想要一个节奏更快的同款游戏，这样在等待其他事情（比如漫长的代码编译）完成的间隙，我能更轻松地快速玩上一局。
最显而易见的答案就是在比平常 4×4 更小的网格上玩。标准的实现并没有提供这个选项，但游戏规则很简单，所以我自己写了一个版本。
但是，改变网格大小肯定意味着改变目标数字。在一个 3×3 的棋盘上，玩家能够拼出的合理方块大小应该是多少？
我本来可以通过自己或与朋友进行大量的实测来得出这个问题的答案。但我有一个不同的想法：3×3 版本的《2048》足够小，你可以合理地遍历所有可能的棋盘状态。因此，我可以分析这个游戏，找出完美玩家能达到什么水平，并以此为基础来选择目标。
于是我照做了。事实上，我是在 2018 年完成的，直到现在才把它写成文章。抱歉！
Javascript 的使用
通常我在像这样的博客文章中会避免使用任何 Javascript，因为我很理解那些希望关闭它以避免安全隐患和网页侵入性行为的读者。在这篇文章中，我破例了一次，因为我想展示用于游玩游戏的内联小程序，而且我也想不出有什么合理的非 JS 方式来完整重放一把完美游玩的游戏。
因此，恐怕如果你在没有启用 Javascript 的情况下阅读这篇文章，就会错过一些最有趣的部分。对此我很抱歉！
分析游戏
我有两个理由认为 3×3 的《2048》会是一个易于穷举分析的游戏。
首先，状态空间小到可以驾驭。假设你想知道完美玩家成功制造出某个特定方块值 \(2^k\) 的概率。在这种情况下，在你的 3×3 棋盘上，你期望每个格子要么是空的，要么包含一个具有 \(2, 4, 8, \dots, 2^k\) 这 \(k\) 个值之一的方块。因此，一个格子可能处于 \(k + 1\) 种状态，总共有 9 个格子，从而产生大小为 \((k + 1)^9\) 的总状态空间。
即使你雄心勃勃地想要达到最初的目标数字 \(2048 = 2^{11}\)，这也只会产生 \(12^9\) 种可能的游戏状态，略多于 \(2^{32}\)。现代计算机为这么多种状态中的每一种进行计算没有任何难度。甚至不需要花费很长时间——只需几秒钟或几分钟，甚至不需要几小时。
其次，《2048》是单调的：在每一步移动中，棋盘上所有方块的总和严格增加。这意味着没有任何游戏可以回到以前的位置。因此，游戏不可能永远持续下去，也不需要通过求解复杂的联立方程组来确定位置的值。
问题陈述
在描述程序如何解决这个问题之前，我们应该准确阐述这个问题的实际内容。
这种工作中的基本思想是将每一个棋盘位置关联一个值（value）。在这里，由于我对“玩家成功制造特定目标方块的概率是多少？”这个问题感兴趣，因此让这个值成为该概率是合乎逻辑的。
事实上，在《2048》中，我们与每个位置关联了两个概率： * 如果轮到玩家移动，玩家制造出目标方块的概率是多少？ * 如果玩家刚移动完，轮到计算机随机掉落方块，玩家制造出目标方块的概率是多少？
在我的分析代码中，我分别将它们称为 pvalue（玩家值）和 cvalue（计算机值）。计算这些值的规则是： * 在包含目标方块的位置中，pvalue 为 1。 * 否则，在无法进行任何移动的位置，pvalue 为 0。 * 否则，pvalue 的确定方法是：考虑所有可能的移动，找到每种移动导向的位置的 cvalue，并取其最大值。 * 位置的 cvalue 的确定方法是：考虑所有可能的随机掉落，找到每种掉落导向的位置的 pvalue，并对它们进行加权平均，权重为每次掉落的概率（值为 2 的概率为 \(9/10\)，值为 4 的概率为 \(1/10\)）。
在这里，玩家最大化该值，而计算机则在其所有可能的移动中取（适当加权的）平均值^meanimax。
最后，我们真正关心的问题是整盘游戏的价值：总体而言，完美玩家制造出指定目标方块的几率是多少？为了回答这个问题，我们必须计算所有可能起始位置的平均 pvalue。
Algorithm
解决这个问题本质上有两种方法，它们都具有“绝不重复计算某个位置的值”的属性： * 动态规划（Dynamic programming）： 按照方块总和的相反顺序简单迭代所有棋盘位置，计算 pvalues 和 cvalues。 * 记忆化递归（Memoised recursion）： 编写返回给定棋盘位置 pvalue 或 cvalue 的函数，将计算出的每个值存储在缓存中。
在这种情况下，递归是可以接受的。一场《2048》游戏只持续几百步，不足以溢出常规 Linux 应用程序的栈。我也懒得同时缓存 pvalue 和 cvalue；只缓存 pvalues 可以避免内存耗尽（RAM overflow）。
其他注意事项
我可以做但没有去做的潜在优化是通过对称性进行约简（通过挑选其 8 种旋转和翻转中字典序最小的那一个，将每个棋盘位置归一化为规范方向）。然而，简单版本的代码已经足够快了。
浮点数被用于表示概率。但浮点数并非完全精确，这引入了下文将讨论的潜在舍入误差问题。
分析结果
我在 2018 年编写了这个程序并运行了它。在完美博弈下的核心结果是： * 你可以制造出 256 方块，概率约为 \(\approx 99.6\%\)。 * 你可以制造出 512 方块，概率约为 \(\approx 73.7\%\)。 * 你可以制造出 1024 方块，概率约为 \(\approx 1.1\%\)。 * 你制造出 2048 方块的概率为零。
不可能达成的目标
制造 2048 方块的概率为零，表明这是字面意义上的不可能。证明过程相当简单： 1. 要制造出一个 2048 方块，你的棋盘上必须同时存在两个 1024 方块。 2. 棋盘上第一次出现两个 1024 时，它必然是一次移动的结果，该移动通过合并两个 512 生成了至少一个 1024（这意味着在此之前至少有三个 \(\ge 512\) 的方块）。 3. 依此类推倒退回去，你可以推断出棋盘上存在至少 5 个 \(\ge 128\) 的方块、至少 6 个 \(\ge 64\) 的方块、至少 7 个 \(\ge 32\) 的方块、至少 8 个 \(\ge 16\) 的方块，最后所有九个方块的值都至少为 8。 4. 但棋盘上的其中一个方块总是最近随机掉落的方块，它不是 2 就是 4。因此你根本不可能让所有九个方块都 \(\ge 8\)。
因此，在 3×3 棋盘上制造 2048 在物理上是不可能的，这使得“3×3 《2048》”这个名字在技术上有些名不符实[^ads]。
极高的难度
要制造一个 1024 方块，你需要穿过一个所有九个方块至少为 4 的状态。十有八九，关键的掉落会是一个 2 而不是 4，导致你在并非自身过失的情况下输掉游戏。
Rounding errors
2018 年我使用单精度 32 位浮点数运行此计算时，它报告制造 128 方块的概率为 1（100%）。然而，使用 64 位 double 精度重复计算表明，该概率实际上约为 \(0.9999998\) (\(99.99998\%\))。
翻转指标来计算失败概率而不是成功概率，使我们能够在浮点数最精确的地方（接近零的地方）使用它们： * 未能制造出 128 方块的概率：\(\approx 1.94 \times 10^{-7}\) * 未能制造出 64 方块的概率：\(\approx 7.01 \times 10^{-18}\) * 未能制造出 32 方块的概率：零。
优秀的玩法是什么样的？
通过在分析过程中将理想的移动列表与获胜概率一起保存，我们可以建立一个完美的博弈查找表。将它接入互动游戏实现中，就能让我们观看自动完美对局。
正如我们所见，即使是完美的玩家，也只期望在大约百分之一的游戏中成功制造出 1024 方块：
(嵌入在原文章中的可玩小程序或回放查看器)
从完美玩家身上学到的主要战略见解是：使用基于棋盘一个角落的策略，而不是某个边缘。
- 旧的边缘策略（底行）： 将高价值方块按递增顺序保持在底行。缺点：你永远不能向上移动，否则会毁掉棋盘。
- 新的角落策略： 将高价值方块保持在某个角落的 2×2 块中（例如右下角）。只要左侧/上方的方块被堵住，你就可以沿着顶行和左列来回滑动，充分利用所有四个方向。
前两行的疯狂活动生成了一个 16 方块，它向下合并到底行。
角落策略：顶行和左列的活动在中心格子中生成了一个 16 方块，向外和向下合并。
追求不止一个目标
当人类游玩时，他们可能开始时瞄准 256 方块，然后再继续冲刺 512。如果在 256 策略结束后接管分层的最优策略，性能会下降多少？
事实证明，你大约会损失 1% 的胜率：专门的 512 策略在 73.7% 的情况下成功，而链式策略则下降到 72.6%。相反，从一开始就使用 1024 策略对较小目标的影响微乎其微（\(10^{-7}\) 或更小）。
与“撒旦”对弈
如果我们把 cvalue 的计算从均值（mean）改为最小值（minimum），我们就把《2048》变成了一场真正的零和确定性双人博弈，对手是一个对抗性的掉落生成器（“撒旦”）。
使用单位值（single-bit values）进行此项分析，以绝对的数学确定性证实了：无法制造出 32 方块的概率字面意义上为零。然而，“撒旦”可以成功阻止你制造出任何 64 方块。
结论
这个项目最初是为了在 3×3 棋盘上寻找一个公平的目标数字，但它带来了对博弈论分析、浮点精度陷阱的更深见解，并极大地改善了我个人的游戏风格。
仍有未解的问题：尽管存在微小的浮点不准确性，这些策略真的完全最优吗？高价值角落策略能扩展到 4×4 棋盘吗？最重要的是——这真的减少了我花在玩《2048》上的时间吗？可能并没有，因为门槛降低意味着我更频繁地开启快速局了！
脚注
[^ads]: 我曾经看到过一个克隆网站，它确实允许你把游戏缩减到 3×3，并且保留 2048 作为目标方块。也许他们没有意识到这是不可能的。但该网站也充斥着广告，所以另一种理论是，他们故意给你设定一个不可能完成的任务，好让你的眼球在页面上多停留一会儿！
[^score]: 你也可以想象用一个比“尝试制造 512”更具量化优化目标的方式来重新进行分析。你的目标可以是最大化所有方块的期望总和，或者原始游戏计算出的期望得分。这类目标最终也会转化为对某些更原始目标的加权组合进行最大化。 [^bits]: 事实上，在这种情况下，提取 pvalues 表比提取最佳移动表成本更低，因为这样数据文件更小。单比特的 pvalue 比掉落描述更小。通过这种方法，并且在已知最多只会出现 32 的方块的前提下，策略数据文件只需要 \(6^9\) 位长（约合 \(\approx 1.2\text{ MB}\)）。