Sokoban AI 求解器：在 JavaScript 中實現最佳路徑搜尋

Menachem Kornreich 發展了一款 Sokoban AI 求解器，能以高效率的 JavaScript 版本 C++ 求解器，找出可證明的最優解——也就是最少的搬運工移動次數。此工具展示了「傳統 AI」搜尋技術在瀏覽器環境中高效解決複雜格子謎題的應用。

求解器的技術實現

該求解器基於 A* 搜尋演算法，但透過多種優化策略避免了 naïve 實作常見的狀態空間爆炸問題：

宏推 A* 搜尋

與將每個搬運工的步驟視為搜尋邊不同，求解器採用宏推方法。搜尋圖中的每條邊代表一次完整的箱子推進。邊的代價計算方式為搬運工到推進位置的最短步行距離，再加上一次推進的代價。這使得搜尋能跳過單一步行步驟，同時仍能計算出搬運工移動次數的真正最小值。

狀態壓縮與記憶體管理

為在有限記憶體中容納數百萬個狀態，求解器使用緊湊的位元遮罩狀態：

箱子位置： 箱子被壓縮至 32 位元整數中，存放於棋盤上可達的「活躍」格子。
搬運工位置： 搬運工的位置以獨立的數字儲存。
狀態表示： 此方法將狀態從約 1 KB 的物件縮減為單一約 8 位元的索引，使數百萬個狀態可容納於數十 MB 的記憶體中。

用於效能的資料結構

求解器使用 Dial 桶佇列作為 A* 前沿，並使用開放定址雜湊表作為已訪問集合。透過使用平坦的 typed-arrays，實作完全無記憶體配置且快取友善，這在 JavaScript 中對效能至關重要。

死結剪枝

為維持可接受性並確保最優性，求解器採用兩種剪枝技術：

死格表： 透過從目標反向可達性生成的靜態表格，識別出箱子無法移動至目標的格子。
凍結檢查： 一種機制，根據考慮牆壁的推進距離下界，捨棄可證明無解的位置。

性能與限制

雖然第 1 到第 14 關可在毫秒內即時求解，但第 15 關（一個 8 箱迷宮）的複雜度顯著高於其他關卡。此特定關卡的最優搜尋探索了約 4900 萬個狀態，並需要超過 1 GB 的記憶體。由於這會超出瀏覽器分頁的記憶體限制，第 15 關的解是透過在 C++ 中使用 24 個核心的平行 A* 搜尋離線計算，並以預先計算的解進行播放。

社群討論與洞見

Hacker News 上的社群成員將此專案視為回歸「傳統 AI」（搜尋與專家系統）而非現代基於 LLM 的 AI。有些使用者指出，求解器所處理的 Sokoban 是一種特定變體，其中搬運工也必須在結束時位於目標格上，這為勝利條件增加了額外約束。

其他技術性批評與建議也出現在社群回饋中：

我很好奇：狀態是否過度壓縮了？若儲存 (箱子, [搬運工在不推箱子情況下可到達的所有位置]) 而非 (箱子, 代表性的搬運工位置)，是否能加快速度？這樣可以減少搬運工繞行的重複計算？

我很好奇：還有沒有其他簡單的剪枝技術可以加入？例如，從當代先進的 Sokoban 求解器（如這個）中學到的經驗？

使用者也指出，求解器允許使用者從任意棋盤狀態觸發 AI 求解，這使得可以透過將箱子移動至對抗性位置，來探索「惡化」謎題的可能。