刘昊辰 (2025-10-27 14:21):
#paper Strongly Solving 2048 4×3. 本文由日本东京大学研究者提出,成功强解了 2048 游戏的 4×3 变体(2048₄ₓ₃),核心关键技术是基于 ”年龄(age)”(定义为棋盘上所有方块数字之和)对状态空间进行划分 —— 状态与后续动作后的过渡态(afterstate)年龄保持不变,过渡态到新状态时年龄因新增方块(2 或 4)增加 2 或 4,据此可分阶段枚举状态并控制内存占用;同时采用Elias-Fano 编码实现状态的紧凑存储,将约 4.4TiB 的原始存储需求压缩至 1.4TiB(最优玩法专用存储仅需 300GiB)。研究结果显示,最常见初始状态(两个 2 方块,年龄 4)的最优策略期望得分为50724.26,可到达状态数与过渡态数分别为1.15×10¹²和7.40×10¹¹,且验证了 “生成大数字方块(如 2048)时难度显著提升” 等玩家直觉。下载地址:https://arxiv.org/pdf/2510.04580
arXiv, 2025-10-06T08:31:59Z. DOI: 10.48550/arXiv.2510.04580
Strongly Solving 2048 4x3
翻译
Abstract:
2048 is a stochastic single-player game involving 16 cells on a 4 by 4 grid,where a player chooses a direction among up, down, left, and right to obtain ascore by merging two tiles with the same number located in neighboring cellsalong the chosen direction. This paper presents that a variant 2048-4x3 12cells on a 4 by 3 board, one row smaller than the original, has been stronglysolved. In this variant, the expected score achieved by an optimal strategy isabout $50724.26$ for the most common initial states: ones with two tiles ofnumber 2. The numbers of reachable states and afterstates are identified to be$1,152,817,492,752$ and $739,648,886,170$, respectively. The key technique isto partition state space by the sum of tile numbers on a board, which we callthe age of a state. An age is invariant between a state and its successiveafterstate after any valid action and is increased two or four by stochasticresponse from the environment. Therefore, we can partition state space by agesand enumerate all (after)states of an age depending only on states with therecent ages. Similarly, we can identify (after)state values by going along withages in decreasing order.
翻译
回到顶部