推箱子AI求解器：毫秒级最优解的秘密

推箱子（Sokoban）是一款诞生于上世纪八十年代的经典益智游戏，玩家需要将所有箱子推到目标位置。而一个名为Sokoban AI Solver的项目，展示了如何用现代算法在浏览器中实时求解最优解，其性能表现令人瞩目。

该项目是经典A*搜索算法的深度实践，但并非朴素的逐格搜索。开发者指出，如果每次只探索箱子搬运工的一步移动，在拥挤的棋盘上搜索空间会迅速爆炸。为此，求解器采用了一种“宏推送”策略：将每次完整的箱子推动作为搜索图中的一条边，其代价是搬运工走到推箱位置的最短路径长度加一。这样既保证了总代价等于真实的搬运工移动步数，又跳过了大量的中间步行步骤，大幅缩小了搜索分支。

为了在浏览器中高效运行，项目在状态编码上做了极致优化。棋盘上所有可到达的“活格子”被压缩进一个32位整数，搬运工的位置再用另一个数字表示，整个状态仅需要一个约8字节的键值，而不是传统对象约1KB的内存开销。这使得数百万个状态可以轻松放入几十MB的存储中。配合键值代价的Dial桶队列和开放寻址哈希表，求解器实现了无分配且缓存友好的运行效率。

同样重要的是死锁剪枝。通过从目标点反向可达性构建静态死方格表，并附加冻结检查，求解器能够排除那些在逻辑上必然无法解决的箱位布局。同时，一种考虑墙体的推送距离下界保证了A*启发式函数的可采纳性，从而确保最终返回的是可证明的最少步数解。

在性能上，该求解器在第1至14关都能实时运行，并在极短时间内给出验证过的最优解。唯一的例外是第15关——一个包含8个箱子的复杂迷宫。这一关的最优搜索需要探索约4900万个状态，内存需求超过1GB，在浏览器标签页内运行时间过长。因此，其最优解（184步）是使用相同的算法离线计算的，由C++并行版本在24核上约5秒完成，并通过回放验证后硬编码在页面中。

这个项目不仅展示了一个经典的AI领域案例，更体现了算法工程中状态压缩、队列优化和剪枝策略的价值。它由原生C++求解器移植而来，用一个可交互的网页证明了复杂搜索问题也能在现代设备上获得即时反馈。