这篇文章介绍了一个名为“推箱子 AI 求解器”的开源 Web 项目，它将经典的 1980 年代推箱子益智游戏与现代人工智能搜索算法相结合。该项目的核心在于其 AI 求解器，它不仅仅是解决问题，还能计算出数学意义上的“最优解”（即最少步数）。该求解器采用“移动最优宏推动 A* 算法”，将搜索边缘定义为一次完整的推箱操作（包含保管员走到推动点的最短路径距离 + 1），从而跳过繁琐的行走步数搜索。为了在浏览器内存限制下高效运行，作者进行了深度的底层优化：使用紧凑的位掩码将棋盘状态压缩为 32 位整数，采用无需分配的拨号桶队列和开放寻址哈希表，并结合死锁剪枝技术来剔除不可解状态。对于大多数关卡，该纯 JavaScript 实现能在毫秒内实时求解；对于极其复杂的第 15 关，则展示了通过 C++ 并行计算得出的预计算结果。这是一个展示浏览器端计算能力和经典搜索算法优化的优秀案例。
事件分析
该项目展示了经典搜索算法在现代 Web 环境下的极致优化技巧。Sokoban 问题是计算复杂度极高的 PSPACE-complete 难题，常规算法极易在浏览器中崩溃。作者通过位掩码状态压缩和特定的代价函数设计，成功将复杂的 A* 搜索移植到 JavaScript 中，打破了传统认为浏览器不适合处理重度算法计算的刻板印象。特别是“宏推动”策略与“死锁剪枝”的结合，极大减少了搜索空间的开销。此外，对于超大状态空间的关卡，作者采用离线 C++ 并行计算与在线回放结合的混合架构，这种“预计算+轻量前端”的思路为在 Web 端处理复杂逻辑提供了极具价值的工程范例。
核心观点：极致的内存优化与经典 A* 算法结合，证明了浏览器前端具备处理复杂搜索问题的潜力。
原文链接：Hacker News
