Solvable Sokoban Without a Solver via Diffusion

在计算机科学领域，存在一类极其复杂的难题，其特点是验证一个解很容易，但寻找解却需要穿越一个如此庞大的可能性迷宫，以至于通过暴力破解法可能需要比宇宙的年龄还要长的时间。这些不仅仅是困难的谜题；这些问题意味着通往答案的路径不仅漫长，而且是指数级增长的，也就是说，你迈出的每一步都可能开启一个全新的可能世界，同时又关闭了其他的可能性。其中最著名的例子之一是一款名为《推箱子》（Sokoban）的游戏，玩家在一个网格上操作一个角色，必须将箱子推到特定的目标方块上。难点在于，角色只能推不能拉，而且一旦箱子被卡在角落里，往往就会永远卡在那里。由于一个箱子的位置可以完全改变整个棋盘的可达性，因此这款游戏无法被分解为小的、独立的任务。解决它需要一个整体性的计划，在采取任何行动之前，就必须考虑到所有的相互作用。几十年来，生成这类新且有效的谜题一直是一个挑战，因为创建一个可解的迷宫与解决它一样难，而且检查一个迷宫是否有效通常需要一台强大的计算机来模拟每一个可能的移动。

最近的一项研究发现了一种令人惊讶的方法，可以在从未教过计算机如何解决问题的情况下生成这些复杂的谜题。研究人员训练了一种类型的人工智能模型来填补索科班（Sokoban）网格中缺失的部分，就像人类根据周围的字母来猜测缺失单词的填字游戏一样。该模型展示了数千个真实的谜题，并被要求学习墙壁、地板和箱子的模式，但从未被告知哪些谜题是可解的，也没有因为创造了一个可运行的游戏而获得任何奖励。它只是学习了如何根据已可见的方块来预测隐藏位置应该是什么方块。结果令人震惊：当模型从头开始生成新的谜题时，其中 77.4% 是可解的。这是一个非凡的结果，因为模型从未被明确训练以确保可解性；它仅仅是被训练去填补空白。研究人员发现，创造一个可解谜题的能力并不是模型学习到的独立技能，而是学习局部模式的一个自然产物。

这种方法的成功取决于模型如何思考网格。传统的生成序列的计算机程序（例如编写文本的程序）按固定顺序工作，先决定第一个词，然后是第二个，接着是第三个。这种线性方法在处理《推箱子》时会遇到困难，因为在网格开头做出的决定可能会限制结尾处可能发生的情况，从而产生程序在后期无法修复的冲突。然而，本研究中使用的模型并不遵循固定顺序。它从一个每个单元格都是隐藏状态的完全空白网格开始，并按随机顺序逐一揭示它们。在每一步中，它都会观察当前整个棋盘的状态——这里的墙壁、那里的箱子以及其他地方的空位——并决定下一个隐藏位置应该属于什么。这使得模型可以先在角落放一面墙，在对角线位置放一个目标，然后构建连接它们的走廊，并在揭示每一个新部件时调整对整个棋盘的理解。这种灵活性反映了人类玩家思考游戏的方式，即难度来自于棋盘远处部分之间的非局部相互作用。

为了测试这种方法的有效性，研究人员生成了 50,000 个新谜题，并使用标准的求解器对每一个进行了检查。他们发现，近四分之三的谜题可以直接求解。更具启发性的是那些失败的谜题所发生的情况：在 94.5% 的不可解案例中，只需移除一个内部墙壁即可修复谜题。这表明模型并非在进行随机猜测；它正在创建几乎完全正确的结构，只是存在一些微小的、浅层的错误阻碍了解决方案。研究人员还检查了模型是否只是在记忆训练期间见过的谜题。他们将生成的谜题与原始数据集进行了比较，发现生成的谜题与真实、未见的谜题一样，与训练数据具有显著差异。模型学习到了游戏的底层结构，而不只是记录了一系列特定的例子。

研究还探讨了当研究人员调整模型的置信度时，其行为会发生怎样的变化。通过让模型在选择时更加果断，他们可以将可解率提高到接近 99%，尽管这以创造出比平时拥有更多墙壁的谜题为代价。然而，默认设置产生的谜题在墙壁密度上与原始训练集完美匹配。这种结构与随机性之间的平衡是关键所在。模型学到了：为了使一个谜题有效，墙壁和箱子必须以非常特定的方式组合在一起，通过学习如何正确地填补空白，它在无意中也学会了可解性的规则。研究人员注意到，在模型预测单个方块的能力停止提升后，其在全局属性（即可解性）上的表现仍在持续改进。这表明这两个目标是截然不同的：一个模型可以擅长填充单个方块，但不一定擅长创造整个谜题，但在本案例中，掌握局部细节足以解锁全局解决方案。

这一发现的影响超出了仅仅制作更好谜题的范畴。它证明了复杂的全局属性可以从简单的局部训练目标中涌现出来。模型从未被告知谜题必须是可解的，但它却学会了创造它们。这表明，数据本身的结构包含了解决方案的逻辑，并且一个能够理解系统中所有部分之间关系的模型，可以继承解决该系统的能力。研究人员确认，模型并没有使用隐藏的求解器来引导其生成过程。过程中的每一步都是由模型基于可见部分的自身预测所驱动的。模型能够在从未见过解路径的情况下生成一个可解的迷宫，这证明了深入理解系统模式以重现其最难属性的力量。

最终，这项工作表明，生成一个问题与解决一个问题之间的障碍并不像之前认为的那样高。通过训练一个模型仅仅去完成一个模式，研究人员解锁了创造有效且复杂挑战的能力。模型不需要成为游戏的宗师才能创造出一个值得玩的挑战；它只需要理解方块的规则。这种方法为我们思考人工智能提供了一种新途径，即如果我们教会一个系统去理解复杂世界中的局部关系，它可能会自然而然地学会应对该世界的全局挑战，而无需被明确教授如何去做。生成的谜题并不完美，但已经足够接近，以至于微小的调整就能使其奏效，这证明了模型已经抓住了游戏的本质。