无需求解器的可解推箱子（Sokoban）生成：基于扩散模型的方法
文章背景与核心概要
推箱子（Sokoban）问题的可解性判定是一个经典的 PSPACE 完全问题，其特征在于解路径冗长复杂，且对布局的微小改动极其敏感。传统的生成方法往往依赖于复杂的求解器或奖励机制，计算成本高昂。
本文提出了一种基于 Transformer 的离散扩散模型，能够在不依赖求解器、奖励函数或显式可解性标签的情况下，生成可解的推箱子谜题，成功率高达 77.4%。该模型仅通过瓦片补全（填充掩码单元格）进行训练，从而隐式地学习到了谜题可解性所需的非局部结构约束。
关键研究发现
推箱子面临的挑战
推箱子对于计算模型而言极其困难，原因如下： * 复杂性： 它是 PSPACE 完全问题；不存在用于验证解的简短证明。 * 脆弱性： 哪怕放置错一个墙壁，都可能导致整个谜题变得不可解。 * 非局部依赖： 难度源于全局交互，即网格某一部分的决策会限制整个棋盘的可能性。
The Challenge of Sokoban
Sokoban is notoriously difficult for computational models because: * Complexity: It is PSPACE-complete; there is no short certificate to verify a solution. * Fragility: A single misplaced wall can render an entire puzzle unsolvable. * Non-local Dependencies: The difficulty arises from global interactions where a decision in one part of the grid constrains possibilities across the entire board.
扩散模型方法
作者利用了掩码扩散模型（Masked Diffusion Model），与传统的自回归模型相比，它具有显著优势： * 灵活生成： 与受限于固定序列（\(p(c_k \mid c_1 \dots c_{k-1})\)）的自回归模型不同，掩码扩散模型学习的是在任意单元格子集上的条件生成。 * 结构对齐： 由于模型可以以任意顺序揭示单元格，它更适合捕捉推箱子谜题中固有的非局部依赖关系。
The Diffusion Approach
The author utilizes a masked diffusion model, which offers a distinct advantage over traditional autoregressive models: * Flexible Generation: Unlike autoregressive models that are locked into a fixed sequence (\(p(c_k \mid c_1 \dots c_{k-1})\)), masked diffusion learns to condition generation on any subset of cells. * Structural Alignment: Because the model can reveal cells in any order, it is better suited to capture the non-local dependencies inherent in Sokoban puzzles.
性能表现
- 可解率： 该模型在生成可解谜题方面达到了 77.4% 的成功率。
- 鲁棒性： 在剩余 22.6% 的失败案例中，94.5% 的谜题只需移除一堵墙即可变为可解，这表明模型生成的布局始终“接近”有效解。
- 训练方法： 该流水线改编自 MD4 架构（Shi et al., 2024），并使用 DeepMind 的 Boxoban 数据集进行训练。
Performance
- Solvability Rate: The model achieves a 77.4% success rate in generating solvable puzzles.
- Robustness: Of the remaining 22.6% of failures, 94.5% can be rendered solvable by simply removing a single wall, suggesting the model is consistently "near" a valid solution.
- Training Methodology: The pipeline is adapted from the MD4 architecture (Shi et al., 2024) and trained using the DeepMind Boxoban dataset.
获取与资源
注：训练好的模型及谜题生成说明已公开。
Note: The trained model and instructions for generating puzzles are publicly available.