在Show HN页面上,这个推箱子(Sokoban)求解器演示挂着一句轻描淡写的说明:15号棋盘"计算需要太久",所以答案是提前算好、写死在页面里的。前14道题,AI都能在浏览器里几十毫秒给出证明最优的解法;轮到第15道——一个8箱迷宫——它却当场认输,老老实实播放一段"剧本"。
这不是bug,是作者自己写在文档里的坦白。但这句坦白背后,藏着推箱子这个1980年代小游戏被学界折腾了四十年都没彻底解决的核心难题。
一句坦白背后的事实
- 这个求解器是作者自己写的原生C++最优解算法的纯JS移植版,核心技术是宏观推箱A*:每次推箱当一步,代价算成"角色走到推箱点的最短路径+1",搜索能跳过角色走路的细节步骤,却仍保证最终答案是玩家总步数最少的真最优解
- 棋盘状态被压成一个32位整数加一个角色坐标,一整个状态只占几个字节,配合桶队列和哈希表,几百万个状态能塞进几十MB内存
- 死锁剪枝(死格表+冻结检测)提前排除推不动的死局,同时保证启发式不高估,不破坏A*的最优性证明
- 1到14号棋盘,这套流程在浏览器里跑,毫秒级出结果
- 15号棋盘不一样.C++原生版本用24线程搜了5.3秒,扩展了4909万个状态、生成了7648万个状态,吃了约1.2GB内存,才算出184步的最优解——这个结果被写死进网页,浏览器只负责回放
贵在哪:两条求解路线的四十年分野
Sokoban早在被证明是PSPACE-complete难题的年代就分出两条路子。一条叫push-optimal,只关心"推了多少次箱子",代表求解器Rolling Stone靠强力剪枝换速度,角色具体站在哪个格子不重要,可以把同一片可达区域的角色位置全部归并成一个状态,状态空间因此小得多。另一条叫move-optimal,关心"玩家总共走了多少步",代表求解器Festival,必须精确记住角色每一步站在哪,状态空间会明显膨胀。
这个网页demo选的是第二条路——它要给玩家一个"最少移动次数"的答案,不是"最少推箱次数"。这个选择本身没错,甚至更贴近真人玩家的直觉体验,但代价是状态空间会跟着棋盘复杂度指数级涨起来。15号棋盘之所以要4900万个状态才能算完,根子就在这里:不是这块棋盘特别难,是move-optimal这条路本来就比push-optimal贵得多。
- 结论.选move-optimal是为了给玩家"真正最少步数"的体验,但复杂棋盘的搜索成本会比push-optimal高出一整个量级。
硬编码不是作弊,是诚实的边界
网页把15号棋盘的答案写死,乍看像作弊,细想却是少见的诚实。很多demo遇到算不动的情况,会悄悄换一个近似算法,给个看起来对但没证明的答案,读者根本看不出区别。这个作者没这么做——他把"算不出来"这件事摆在明面上,连24核5.3秒的成本都写进文档,留下可复现的编译命令和输出格式。
知之为知之,不知为不知,是知也。
《论语》这句老话搬到这里刚好合适:一个算法demo立不立得住,不在于它能不能把每道题都秒杀,而在于它敢不敢承认哪道题算不出来,又拿得出数据证明自己没在糊弄人。
- 风险.换一套没有公开源码、没有可复现基准的demo,同样一句"提前算好答案"完全可以变成一次没人察觉的糊弄。判断一个算法demo可不可信,不看它秒解了多少题,看它敢不敢公开算不出来的那道题的真实代价。
浏览器还差多远
15号棋盘现在只能在原生C++里跑。换成WebAssembly,理论上能拿到接近原生的速度和更大的可用内存,但4900万状态、1.2GB内存这个量级,能不能塞进普通用户浏览器标签页的资源限制,目前还看不清。更现实的路径可能是换一个更紧的下界启发式,比如用二分图匹配代替简单的反向可达距离,把搜索空间提前砍掉一大块——但这又要重新证明新的启发式仍然admissible,一步都不能走捷径。
一个推箱子小游戏的demo页面,意外把move-optimal算法这四十年的暗账翻了出来:秒解的题从来不是难题,难的从来是要不要精确,以及精确到底值多少代价。