Sokoban: 寻找推箱子最优解的AI求解器
Show HN: Sokoban AI Solver
这是一款基于A*算法的Sokoban（推箱子）AI求解器，由Menachem Kornreich开发。它不仅是简单的游戏辅助，更是能在毫秒级内计算出数学上证明的最少步数解法的强大工具。项目将原生C++最优求解器移植为纯JavaScript，利用紧凑的位掩码状态和Dial bucket队列技术，在浏览器中高效处理数百万状态。前14关实时求解，第15关则回放了离线计算的最优解。无论是想挑战极限步数，还是研究算法实现，这都是一个极佳的开源项目。
它返回的是经过数学证明的最少步数解，而不仅仅是一个可行解。
HN 评论区
42- TimTheTinker
看到“AI”这个词被用在经典意义上，我真是乐见其成。老派 AI 充满了迷人的发展成果：专家系统、A* 搜索、基于 S-表达式生成任意解的遗传算法，以及 SAT 算法，这些曾经都被认为终将演化为通用人工智能（AGI）。
我怀疑下一个重大的 AI 突破，至少部分将源于用老派 AI 方法来约束大语言模型（LLM）的决策。Frank Coyle 大约一个月前就提出了用本体论（ontologies）来约束 LLM 输出的想法：https://www.youtube.com/watch?v=Sir59K8ZDPU
更进一步，我好奇是否能让智能体维护一份动态更新的假设与已知事实清单（附带置信度/置信区间），主动或被动地测试它们，在观测结果与之矛盾时更新它们，并据此行动——这不应仅仅是某种涌现行为，而应是一种嵌入在 Transformer 架构中的、可证明正确的（基于老派 AI 的）算法。
- tintor
这个推箱子求解器只能处理微小且简单的关卡，落后于现有的多个最先进（SOTA）推箱子求解器。
http://www.sokobano.de/wiki/index.php?title=Solver_Statistic...
- epiccoleman
我有点惊讶自己居然开始享受这个游戏了，毕竟我对推箱子类游戏一直挺反感的。（也许是因为宝可梦游戏里那些滑块的创伤吧，哈哈）。我想我大概正在克服这种心理（也许是因为《Baba Is You》带来的美好回忆）。
总之，这里有趣的一点是，你可以从任何棋盘状态触发 AI 求解。特别是在第 12 关，我很感兴趣地发现，我原本认为行不通的初始推法（为了逃出起始的“箱子”），结果反而是最优解。当然，看着求解器去攻克我当初解决谜题时的初始条件（并且步数还比我少），也很有意思。
也许玩“最优化”（pessimizing）这个谜题会很有趣——比如，你怎么移动方块，才能创造一个对点击“用 AI 求解”按钮来说最恶劣的局面？（当然，你绕着棋盘走的初始步数不算在内，否则你来回走就能得到最“差”的解了，谢了 Mel。）
编辑：第 14 关感觉有点怪。超级简单，为什么排到第 14 关？也许有什么我没看出来的棘手之处，也许是竞技场形状让 A* 算法变难了？
另外，第 15 关很有趣，也印证了我注意到的一个主题：通常谜题的初始几步似乎非常固定，而 AI 能比我少用步数的地方，往往在于某种巧妙的“堆叠”箱子到目标点的方法。写出来看，这似乎挺显而易见的。
总之，感谢分享……
- GPerson
“这里运行的是我写的一个原生 C++ 最优求解器的纯 JavaScript 移植版。”
这听起来像是 10 年前的老派 AI 吧？
- npinsker
直觉上，我觉得如果利用 WASM 并加速求解器，最终的关卡也许也能在浏览器里跑起来。
我好奇：也许状态压缩得太厉害了？如果存储（箱子，[看守者在不推箱子的情况下能到达的所有位置]）而不是（箱子，看守者的代表性位置），会不会更快？这样就能减少看守者四处走动时的重复计算。
我好奇：也许 A* 是适得其反的，因为明显的启发式函数存在陷阱？BFS 会不会更好？
我好奇：搜索过程实际上并没有“跳过”行走状态，只是把它们隐藏在每个队列元素的处理过程中，所以把它们显式加入队列会不会反而更快？
我好奇：还有没有其他简单的剪枝技术可以加入？有没有从最先进推箱子求解器（比如这个？）中学到的经验？-- https://ieee-cog.org/2020/papers/paper_44.pdf
很多有趣的问题……可惜这个网页是 AI 写的，所以完全没有讨论这些权衡取舍、未来方向或被否决的想法，取而代之的是关于“可证明最优解”的无意义自夸，以及诸如“桶队列是无分配的”之类的愚蠢说法。