🤖 AI

Strongly Solving 2048 4x3

本文提出了随机游戏2048的4×3变体的强解，通过采用基于年龄的划分技术来管理其超过1.15万亿个可达状态的庞大状态空间，确定了约50,724.26的最优期望得分。

原作者： Tomoyuki Kaneko, Shuhei Yamashita

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Tomoyuki Kaneko, Shuhei Yamashita

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，将流行的益智游戏2048视为一个巨大而混乱的厨房，你正试图将食材（图块）组合起来，制作出越来越大的菜肴。在标准版本中，你拥有一个 4x4 的网格（16 个位置）。而在本文中，作者决定将这个厨房缩小为一个4x3 的网格（12 个位置），使其成为一个更加紧凑、拥挤的挑战。

以下是他们做了什么、如何做的以及发现了什么的简单分解，使用了日常类比。

1. 巨大的挑战：一本大得无法读完的图书馆

作者想要“强力求解”这个游戏的缩小版本。在游戏术语中，这意味着他们不仅仅想知道开局的最佳走法；他们想要知道游戏可能达到的每一个可能局面的完美走法。

将游戏的所有可能局面想象成一座图书馆。

原始的 3x3 版本（Mini2048）就像一个小书架，大约有 48,000 本书。很容易读完。
这个新的 4x3 版本则是一座拥有超过 1.15 万亿本书（状态）的巨型图书馆，以及近 7400 亿本“中间”书（后状态）。

试图一本接一本地读完这座图书馆里的每一本书，将耗费永恒的时间，并需要一台内存超过世界现有总量的计算机。作者需要一个魔法技巧来整理这座图书馆，以便他们能在普通个人电脑上仅用几天时间就完成求解。

2. 魔法技巧：游戏的“年龄”

他们成功的关键在于一个被称为**“年龄”**的概念。

想象每次你玩游戏时，你都在给一个秤增加重量。

当你开始时，你有两个图块（比如两个 2）。“年龄”是棋盘上所有数字的总和（2 + 2 = 4）。
当你滑动图块并将它们合并时，数字会翻倍，但年龄保持不变。（将两个 2 合并成一个 4 不会改变总和）。
年龄发生变化的唯一时刻是当计算机随机掉落一个新图块（2 或 4）时。这会给年龄增加 2 或 4。

类比：
将游戏想象成一座多层建筑，而不是迷宫。

建筑的每一层代表一个特定的年龄（例如，第 4 层、第 6 层、第 8 层……）。
你可以在同一层自由移动（滑动和合并图块），而无需上下楼。
只有当计算机掉落一个新图块时，你才会移动到下一层。

因为游戏总是随着年龄向前推进（你永远不会回到更低的总和），作者可以按楼层处理这座图书馆。他们不需要一次性在脑海中容纳整座图书馆。他们只需要在内存中保留当前楼层、下一层以及再下一层的数据。一旦他们计算完第 100 层的最佳走法，就可以丢弃第 98 层的数据，以便为第 102 层腾出空间。

3. 压缩：把鲸鱼塞进背包

即使有了这种按楼层处理的技巧，数据仍然非常庞大。如果他们试图在纸上写下每一个游戏状态，将占用约4.4 TB的硬盘空间（大约相当于一个大型数据中心的规模）。

为了解决这个问题，他们使用了一种称为Elias-Fano 编码的巧妙数据压缩技术。

类比： 想象你有一份 10 亿人的名单，但他们都穿着红衬衫。与其在每个名字旁边都写上“红衬衫”（这会浪费空间），不如写一个特殊代码，说明“这份名单里的每个人都穿着红衬衫”。
他们找到了一种方法，将所有可能游戏状态的“身份证”压缩到约1.4 TB。如果只关心最佳走法（忽略原始数据），他们甚至可以将其进一步缩小到约300 GB（相当于一台高端笔记本电脑硬盘的大小）。

4. 结果：他们学到了什么

通过求解游戏，他们计算出了一个从不犯错的玩家所能获得的完美预期得分。

得分： 如果你从最常见的开局（两个 2）开始并完美操作，你可以预期获得约50,724 分。
“运气不佳”因素： 他们发现，从一个 4 图块开始而不是两个 2，实际上会让你处于轻微劣势（大约低 4 分）。这就像背着沉重的背包开始赛跑；你必须更努力地工作才能赶上。
"2048"瓶颈： 他们的结果图显示，每当年龄达到 2048 的倍数时，就会出现“低谷”（性能下降）。这证实了许多玩家的感觉：要制作出 2048 图块变得极其困难，因为你在 12 格的小棋盘上空间不足。你需要完美的排列，才能将所有较小的数字（2、4、8……直到 1024）容纳进去，然后才能将它们合并。

总结

作者解决了一个看似因可能性数量巨大而过于复杂、无法完全求解的游戏。他们意识到，游戏会自然地按照“数字总和”（年龄）进行组织。通过将游戏视为一系列楼层而非巨大的 tangled 网络，并利用超高效的归档系统（压缩），他们绘制出了每一个可能走法的完美策略。

他们证明，使用一台普通计算机和几天的工作，就可以数学上掌握一款通常依赖运气和直觉的游戏。

技术摘要：在 4×3 棋盘上强解 2048

问题定义

本文针对一种随机单人游戏变体——4×3 棋盘上的 2048（记为 2048 $^{4\times3}$ ）——的“强解”问题。与标准的 4×4 版本不同，该变体使用包含 12 个单元格的网格。该游戏被建模为马尔可夫决策过程（MDP），其中智能体选择动作（上、下、左、右）以合并相邻且数值相等的方块。在有效动作执行后，棋盘状态确定性地过渡到“后状态”（即方块滑动并合并）。随后，环境以随机方式在一个空单元格中生成一个新方块（90% 概率生成 2，10% 概率生成 4），从而过渡到下一个状态。

目标是计算最优策略 $\pi^*$ 和最优价值函数 $v^*(s)$ ，代表从任意可达状态 $s$ 出发的期望累积奖励。主要挑战在于状态空间的大小：4×3 变体包含约 $1.15 \times 10^9$ 个可达状态和 $7.4 \times 10^8$ 个后状态。这一规模大约是此前已解决的 3×3 变体（Mini2048）的 $10^4$ 倍，使得在标准硬件上通过直接枚举和存储变得不可行。

方法论

作者提出了一种基于按“年龄”划分状态空间和紧凑数据表示的解决方案。

1. 基于年龄的划分

核心创新在于将状态的年龄定义为棋盘上所有方块数值之和（ $age(s) = \sum c_i$ ）。

不变性：在有效动作执行后，状态与其直接后状态之间的年龄保持不变（因为合并方块保留了数值总和，而滑动不改变数值）。
递进：在随机过渡（生成新方块）期间，年龄增加 2 或 4。
算法含义：这一特性允许将状态空间按年龄划分为不相交的子集。
- 前向传递（枚举）：年龄为 $n$ 的有效状态可以仅从年龄为 $n-2$ 和 $n-4$ 的后状态生成。算法按递增年龄迭代，仅在内存中维护三个集合（当前年龄、年龄 +2、年龄 +4），以枚举所有可达状态和后状态。
- 后向传递（价值计算）：通过从最大年龄向后迭代至初始年龄来计算最优价值。状态的价值是其可达后状态的最大价值；后状态的价值是其可达下一状态的期望价值（按生成概率加权）。

2. 紧凑表示

为了处理存储需求（原始 48 位 ID 估计需要约 4.4 TiB），作者采用Elias-Fano 编码来存储唯一状态 ID 的集合。

结构：排序后的唯一 ID 被分为高位（ $h_i$ ）和低位（ $l_i$ ）。低位存储在连续的位向量中，而高位则使用秩操作编码在稀疏位向量 $H$ 中。
优化：
- 对称性归约：ID 被归一化为水平、垂直和 180 度旋转对称性中的最小值。
- 基数适配：编码基数根据特定年龄的最大方块值进行调整。
- 单元格丢弃：在编码过程中丢弃一个单元格的信息，因为总和（年龄）约束了总量，允许后续完全重建。
效率：这将所有后状态 ID 的存储从约 4.4 TiB 减少到约 1.4 TiB，同时保持了高效的查找能力。针对最优玩法，一种专门的表示法（使用 BuRR 算法）将需求降低到 300 GiB 以下。

主要结果

状态空间统计：可达状态总数为 1,152,817,492,752，后状态数量为 739,648,886,170。
最优期望得分：对于最常见的初始状态（两个数值为 2 的方块），在最优策略下的期望得分约为 50,724.26。
- 包含一个 4 方块的初始状态（年龄 6）产生的期望得分略低（约 50,720.62）。
- 包含两个 4 方块的初始状态（年龄 8）产生的得分最低（约 50,708.99），表明以更高数值的方块开局存在微小的劣势。
状态分布：每个年龄的状态数量通常是可以管理的（每个年龄少于 $3 \times 10^6$ 个），使得算法能够将多个年龄层保留在内存中。
终止状态：状态数量分布中的“低谷”出现在 2048 的倍数年龄处，反映了在有限的棋盘空间内形成大方块的难度。某些年龄（例如 8190、12286）没有有效的后状态，因为形成这些总和所需的方块数量超过了可用的 12 个单元格。
动作敏感性：最优动作与次优动作之间的价值差异在年龄 2048 和 4096 附近达到峰值，表明在形成大方块后立即做出的早期决策至关重要。

意义与主张

本文声称已强解了 2048 $^{4\times3}$ 变体，这是一项此前因状态空间过大而被认为无法解决的任务。这项工作的意义在于：

可扩展性：证明了通过利用游戏特定的结构特性（年龄）而非蛮力方法，可以在几天内在个人计算机上解决拥有超过 $10^9$ 个状态的游戏。
方法论贡献：引入“年龄”划分技术，使得能够枚举和计算随机 MDP 的价值（其中状态价值取决于期望），有效地绕过了在随机环境中无效的 $\alpha\beta$ 剪枝需求。
数据可用性：作者提供了最优价值函数和状态空间的紧凑表示，作为未来强化学习研究和游戏分析的基准。
存储效率：成功应用 Elias-Fano 编码将庞大的游戏状态集压缩至约 1.4 TiB，使得拥有中等计算资源（例如 4 TiB SSD）的研究人员能够访问该数据集。

作者指出，虽然主要目标是解决该游戏，但生成的数据集和“年龄”概念可作为随机游戏和强化学习评估进一步研究的基础。