Soksolv 推出号称世界最强的推箱子求解器,在标准测试集上解出更多关卡
来源标题:Introducing the World's Strongest Sokoban Solver
Soksolv 在两大标准推箱子基准测试集上解出的关卡数超过所有已发表的求解器,其中 24 关是首次由自动化程序解出。它解出其他求解器能解的关卡时,总耗时约为对方的 1/3.3。作者未手写代码,在 Claude Code 中借助约 430 个子代理完成开发,API 等效成本约 3500 美元,另消耗 15000 vCPU 小时用于研究和验证。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
Soksolv 在两个标准基准套件上解出的关卡数都超过任何已发表的 Sokoban 求解器,其中包括 24 个全球首次由自动化程序解出的关卡。在其他求解器能解出的关卡上,它也更快(总时间约为后者的 3.3 倍)。
+10 领先 Festival(10 分钟时) Open Test Suite · 10,045 个关卡的解出百分比 50%70%80%90%95%98%99%1 秒10 秒1 分钟10 分钟+20 领先 Festival(10 分钟时) soksolv Festival Sokolution Takaken YASS BoxSearch Festival:在同一硬件上实测。其他:已发表结果。纵轴为剩余未解关卡的对数刻度。
与这个时代的常见做法一样,我没有手写一行代码。我在 Claude Code 中使用了一个长时间的 Opus 5.5 会话,以及约 430 个子代理(混合使用 Sonnet 5.5、Opus 5.5 和 Fable 5.2),API 等效成本约 3,500 美元(我用的是 100 美元套餐,外加一次重置)。
这个为期 14 天的 Claude 会话是在我的 MacBook 上运行的,其中约 50% 的工作是我在路上通过 /remote-control 向 iPhone 口述完成的。在算力方面,我用了 15,000 vCPU 小时(AMD EPYC)来做研究和验证运行,以及(非常)漫长的基准测试运行。
Sokoban 于 1982 年首次在日本发行,是一款把箱子推到目标点上的解谜游戏。它在 1997 年被证明是 PSPACE 完全的,而小棋盘也隐藏着巨大的搜索空间。人类可解的关卡通常需要数百到数千步。
Sokoban 关卡可以看作一个移动的循环图。分支因子约为 16(但在巨大棋盘上可高达约 176!),任何形式的暴力搜索在几步之后都变得不可行。
作为玩家,尤其是作为求解器作者,Sokoban 关卡在设计上就让人感觉充满对抗性。任何显而易见的启发式都会被游戏规则或关卡作者立刻惩罚。
当我写第一个 Sokoban 求解器时(大约 4 年前),我试图把自认为在玩这个游戏时的思路编码进去。不用想得太深,我们可以把它描述为“把箱子送到目标点”。好,那怎么在程序里计算这个?也许是把每个箱子到目标点的距离求和?
以此为指引,我们可以探索可能的移动图,看看会发生什么。
啊,优先把箱子放在目标点上,我们直接走进了陷阱。游戏陷入死锁、无法解开,而我们只有一条规则的求解器会一直跑到时间尽头也没有解。
我们需要一整套策略,才能比新手玩家表现得更好。
我在工作中使用前沿代理已经有一段时间了,我很享受(并从中获益良多)我称之为“创造性目标设定”的做法。也就是你定义目标、路径的某些部分、你认为可接受的风险,以及对方法的一些偏好。
我的经验是,代理非常擅长爬山,而求解器程序就是最纯粹的山。有两件事要衡量:解出的关卡数,以及这些解法的某种总时间。
在这个项目开始时,我启动了一个 Claude Code 会话,并定义了一个爬山计划。一个不可变的现任求解器版本(第一版只是暴力搜索)、每次实验一个假设、一个冻结的验证器(这样代理就无法作弊),以及独立的晋级套件。
随着我不断取得进展,我扩大了对求解器进行评测的关卡池,直到我采用了 Sokoban 求解器社区常用的两个基准:Large Test Suite 和 Open Test Suite,其中包含越来越复杂的 Sokoban 关卡。两个套件之间有一些重复关卡,去重后共 9,758 个关卡,平均每个关卡有 16 个箱子,约需 830 步(约 160 次推动)才能解开。
我知道我不想在现有求解器之上构建,原因有两个。第一,我做这个项目是因为我喜欢这类东西,而在现有程序上打小补丁的旅程没那么有趣。从零开始参与其中、亲历整个故事要有趣得多。
第二个原因,直到项目后期我才意识到:如果你在现有解决方案之上构建,就会在并不了解那些设计决策的情况下被牢牢绑定在某些设计决策上,从而不可能做出超过一个数量级的改进。
所以我为代理设定了一些初始基本规则。不用机器学习(对我来说审计难度大得多),不阅读竞争对手求解器的代码(否则有复制低效设计的风险),不为解关卡而硬编码(那是作弊)。
在项目开始时,我担心代理会作弊。我相信我们都还记得早期几代 LLM 会直接注释掉测试来达成给定目标!
但我完全没有发现代理作弊的迹象。我最好的猜测是,我把代理的动机引导向了实验和学习,而不是纯粹的数字游戏。
我还设定了另外两条基本规则:求解器必须用 Go 编写(我觉得读起来有趣),以及 15 GB 内存上限,以便能装进 8 核/16 GB 的机器。为了公平起见,我还想使用与 Festival(领先的竞争求解器)相同的核心数。
在迭代周期中,每个解法都会用冻结的验证器在原始关卡上逐步重放。
验证器放在它自己的包里,代理不允许编辑它。在推广新的剪枝规则时,我也有类似的检查。我有 2,632 个已知解法会通过它重放,如果某个剪枝切掉了任何一个已知解法,它就会被判失败(这最终在两个不健全的剪枝规则落地之前抓住了它们)。
前面我说过,解关卡就像探索一个图,对吧?你可能把每个节点算作一次工人移动或一次箱子推动。但走路是免费的!只有推动才会改变谜题。所以我们在推动上搜索,并把“工人能到达哪里”视为一次洪水填充。
一个“位置”:箱子所在的格子,以及工人所在的区域(而不是确切的格子)。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。