Sokoban AI Solver: Optimal Pathfinding in JavaScript

Menachem Kornreich 开发了一个 Sokoban AI 求解器，它使用原生 C++ 求解器的高性能 JavaScript 移植版，能够找到可证明的最优解——即搬运工移动次数的绝对最小值。该工具展示了如何将“经典 AI”搜索技术应用于浏览器环境中，从而高效地解决复杂的基于网格的谜题。

Technical Implementation of the Solver

该求解器基于 A* 搜索算法，但通过采用几种优化策略，避免了朴素实现中常见的状态空间爆炸问题：

Macro-Push A* Search

与其将每一个搬运工的单步移动视为搜索边，该求解器采用了 macro-push 方法。搜索图中的每一条边代表一次完整的推箱子动作。边的成本计算为：搬运工走到推箱位置的最短路径长度加上推箱动作本身的一次移动。这使得搜索过程可以跳过单个行走步数，同时仍能计算出搬运工移动次数的真实最小值。

State Compression and Memory Management

为了将数百万个状态放入有限的内存占用中，该求解器使用了紧凑的位掩码（bitmask）状态：

• Box Positions: Boxes 均被打包进一个 32 位整数中，分布在棋盘上可达的“活跃”单元格内。
• Keeper Position: 搬运工的位置被存储为一个单独的数字。
• State Representation: 这将一个状态从约 1 KB 的对象减少到了单个约 8 字节的键值，从而允许将数百万个状态放入几十兆字节的内存中。

Data Structures for Performance

该求解器在 A* 前沿队列中使用 dial bucket queue，并在已访问集合中使用 open-addressed hash。通过使用扁平化的 typed-arrays，该实现保持了无分配（allocation-free）且对缓存友好的特性，这对于 JavaScript 的性能至关重要。

Deadlock Pruning

为了保持可采纳性（admissibility）并确保最优性，该求解器采用了两种剪枝技术：

• Dead-square table: 通过从目标点进行反向可达性分析生成的静态表，用于识别箱子无法移动到目标的方格。
• Freeze check: 一种基于感知墙壁的推箱距离下限的机制，用于丢弃可证明无法解决的位置。

Performance and Constraints

虽然 1 到 14 号棋盘可以在毫秒级内实时求解，但第 15 号棋盘（一个包含 8 个箱子的迷宫）的复杂度是一个显著的离群值。针对该特定棋盘的最优搜索需要探索约 4900 万个状态，并需要超过 1 GB 的内存。由于这会超过浏览器标签页的限制，第 15 号棋盘的解法是通过在 C++ 中使用 24 核并行 A* 搜索离线计算的，并作为预计算解法进行回放。

Community Discussion and Insights

Hacker News 上的社区成员讨论了该项目，将其视为对“经典 AI”（搜索和专家系统）相对于现代基于 LLM 的 AI 的回归。一些用户指出，该求解器的方案是一种特定的 Sokoban 变体，其中搬运工也必须最终停留在目标点上，这为获胜条件增加了一个额外的约束。

其他技术批评和建议也包含在社区反馈中：

I wonder: maybe the state is overly compressed? Could it speed things up to store (boxes, [every position the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the keeper walking around?

I wonder: are there any other simple pruning techniques that you could incorporate? Any learnings from state-of-the-art Sokoban solvers, like this one?

用户还注意到，该求解器允许用户从任何任意的棋盘状态触发 AI 求解，这使得用户可以通过在请求解决方案之前将箱子移动到不利位置来“恶化”谜题，从而进行探索。