「从未教过它可解,却诞生了可解的谜题」——不靠求解器生成 Sokoban 的扩散模型

引言

今天的 Tsumiki 摘要。今天只有一篇,取的是 2026 年 8 月 16 日发布在 arXiv 上的预印本《Solvable Sokoban Without a Solver via Diffusion》。作者是 Sina Baghal。通读了论文的摘要与正文后加以概括。需要明确说明:这是一篇尚未经过同行评审的预印本。

不把「可解」纳入目标函数,却诞生了可解的谜题——掩码扩散模型与 Sokoban 生成

在自动生成像 Sokoban 这样的谜题时,最棘手的问题是如何保证盘面「真的可解」。判断一个盘面是否可解,这个问题本身已知是 PSPACE 完全的(Culberson, 1997)。解法步骤可能呈指数级增长,也不存在那种一眼就能确认「这样就能解开」的简短证明(证据)。而且可解这一性质极其脆弱——哪怕只是一面墙放错了位置,整个盘面就会悄无声息地变得无解。正因如此,以往的谜题自动生成往往依赖于在生成过程中或生成之后,实际运行求解器来验证,这是一种代价高昂的做法。

这篇论文展示的方法是:让一个基于 Transformer 的双向编码器(参数量约 490 万,维度 256、6 层、8 个注意力头)构成的离散扩散模型,在完全不给予求解器访问权限、不给予奖励、也不给予「是否可解」标签的情况下,只学习「填补被掩码(遮盖)的格子」这一项任务。训练遵循 MD4(Shi et al., 2024)的表述方式,只在被掩码的位置施加交叉熵损失。数据使用了 DeepMind 公开的 Boxoban 数据集(Guez et al., 2019)中的 45 万个谜题,训练了 1000 个 epoch(约 29.2 万步),仅用一块 GPU(RTX 5070 Ti)便完成。这里也一并说明:这并非一项堆砌了特殊计算资源的研究。

结果显示,生成谜题中的 77.4% 直接就是可解状态。而在无法直接解开的剩余部分(约 22.6%)之中,94.5% 只需去掉一面墙就能变得可解,需要修正两面及以上墙壁的仅占全体的约 0.40%。将生成盘面视为 3×3 图块模式的分布,与真实的 Boxoban 验证集数据进行比较的 Jensen-Shannon 散度分析显示,即便样本数从 250 变到 50,000,差异也都控制在 4% 以内——这也证实了生成物完整复制了真实盘面的统计特征(如墙壁密度等)。有趣的是,在训练过程中,「填补掩码」这一任务本身的验证损失很早就收敛了,而「可解」的概率却在此之后一直持续提升,直到训练结束。作者将此视为「每格填补的重构损失」与「整个盘面可解这一全局性质」以不同速度被学习的证据,同时也报告称训练损失与验证损失始终并行(=并非单纯的记忆)。

作者将这一结果表述为「局部的训练目标之中,诞生了全局性且搜索代价高昂的性质」。也就是说,一个只被教会填补格子的模型,却擅自继承了它从未被教过的「可解性」。作者认为,关键在于生成顺序。普通的自回归模型只能按照「依据已放置的序列来放置下一格」这种固定顺序生成。而掩码扩散模型则可以按任意顺序、在盘面的任意位置——依据其他所有已放置的格子——填补被随机遮盖的格子。作者解释道,Sokoban 的难度恰恰来自「盘面某处的决定,会约束完全另一处的成败」这种非局部的相互作用。事实上,作者还做了一项额外的对比实验:将生成顺序改为「优先填补有把握(容易确定)的格子」,结果墙壁数量膨胀到 81.5,远离训练数据的平均值(68.6);而随机顺序下则为 69.5,接近平均值。也就是说,作者亲自证实了「不固定顺序」这一设计选择,并非碰巧奏效,而是正确复现分布所必需的。

坦白说,这篇论文并未与其他生成方法(基于 GAN 的方法、在生成循环中嵌入求解器的方法等)做定量比较。即便如此,这项发现对试图自动生成仓库番式推箱子这类品类的人来说仍具有启发意义。Puzzlebyrinth 曾介绍过的 《A Monster's Expedition》这类作品,同样带有「盘面某一手会封死或打开完全另一处可能性」这种相同的非局部难度。94.5% 的失败仅需「去掉一面墙」就能修复,这一事实也表明:即便不在生成过程中嵌入求解器,也存在「先生成、再轻量修复」这种成本低廉的设计路径。

今天在意的一句话

"a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on."

(中文译:「局部的训练目标之中,诞生了全局性且搜索代价高昂的性质——只被教会填补被掩码格子的模型,擅自继承了它从未被教过的『可解性』」——Sina Baghal,《Solvable Sokoban Without a Solver via Diffusion》)

参考链接

今天涉及的论文:

・Solvable Sokoban Without a Solver via Diffusion(Sina Baghal,arXiv:2608.15958,2026 年 8 月 16 日公开的预印本。英文)

结语

从未把「可解」纳入目标函数,结果却诞生了可解的谜题——读到这段话,我想起了自己看实况卡关时的样子。我并不是被教会了解法才解开的,而是盯着盘面某处看着看着,「大概是这样动吧」这种感觉才后知后觉地冒出来。明知模型内部发生的事情应该完全不同,却还是忍不住觉得手感相似,这一点很有意思。「大多数只需去掉一面墙就能修好」这种说法,也让我觉得莫名地带点人味,挺喜欢的。明天,我还会去世界的某个角落寻找新的设计议论。