显示 HN：推箱子 AI 求解器

Sokoban Sokoban（“仓库管理员”）是一款 20 世纪 80 年代的益智游戏：将每个盒子推向目标。在这种情况下，守门员还必须射门得分。棋盘：重置 撤消 用 AI 解决 AI 速度：慢 正常 快 接下来 → 移动：0 最佳： – ▲ ◀ ▶ ▼ 守门员（你） 框 球门 球门墙上的框 如何玩和规则 仓库是一个网格。每走一步，守门员就向上、向下、向左或向右移动一个格子。守门员不能走进墙壁或盒子。如果盒子外面的方块（沿推动方向）是空地板或球门，它可以推动单个盒子。每一步只有一个盒子移动，并且可以再次将盒子推出球门以腾出空间。控件：箭头键或 W A S D 或屏幕键盘。撤消后退一步。重置可恢复主板。目标：当每个可移动实体出现时，拼图就获胜。每个盒子和守门员。正坐在一个目标上。这就是为什么每个棋盘上的球门比它的盒子多一个：最后一个球门是守门员的。目标：以尽可能少的动作达到该状态。对于多个棋盘，最佳移动计数是已知的并如上所示。人工智能（具有可接受的启发式）在它可以彻底搜索的板上返回最佳解决方案。 AI 解算器如何工作推箱子是一个 A* 搜索问题，但一次探索一个守门员步骤的简单版本在拥挤的棋盘上会爆炸。这里运行的是我编写的原生 C++ 最优解算器的纯 JavaScript 端口。它返回可证明的最少移动解决方案，而不仅仅是某个解决方案：移动最优宏推 A*。每个搜索边都是整个盒子的推动，成本为（守门员到推动点的最短步行）+ 1，因此总数是真正的守门员移动的最小数量，而搜索会跳过各个步行步骤。紧凑位掩码状态。这些盒子被打包成一个 32 位整数，覆盖板的可到达的“活动”单元，而 keeper 被打包成一个又一个数字，因此整个状态是一个约 8 字节的密钥，而不是约 1 KB 的对象。数百万个状态可容纳数十 MB。拨号桶队列+开放寻址哈希。 A* 边界是一个以成本为键的存储桶队列，访问集（带有解决方案的父链接）位于平面类型数组哈希中。免分配且缓存友好。死锁修剪。静态死方表（从目标的反向可达性）加上冻结检查丢弃可证明无法解决的位置，由墙感知推距离下限引导，保持 A* 可接受（因此是最佳的）。棋盘 1-14 在几毫秒内实时求解，达到经过验证的最佳值（上面显示为“最佳”的移动计数正是该求解器返回的值）。第 15 块板。8 个盒子的迷宫。例外的是：它的最佳搜索探索约 4900 万个状态，需要 >1 GB，这在浏览器选项卡中运行需要太长时间。因此，它的最佳值（184 次移动）是通过该精确算法的本机 C++ 构建（并行 A* 搜索，跨 24 个核心约 5 秒）离线计算的，并通过重播进行验证，并且页面只是播放该预先计算的解决方案。这就是为什么 board 15 的答案是硬编码的而不是在这里搜索的。由我的 Sokoban 解算器构建。关于推箱子 →