Sokoban AI Solver: Optimal Pathfinding in JavaScript

Menachem Kornreich氏は、ネイティブC++ソルバーの高パフォーマンスなJavaScript移植版を使用し、証明可能な最適解（キャラクターの移動回数の絶対的な最小値）を見つけるSokoban AIソルバーを開発しました。このツールは、ブラウザ環境内で複雑なグリッドベースのパズルを効率的に解くための「古典的AI」探索技術の応用を示しています。

Technical Implementation of the Solver

このソルバーはA*探索アルゴリズムに基づいていますが、いくつかの最適化戦略を採用することで、素朴な実装に典型的な状態空間の爆発を回避しています：

Macro-Push A* Search

個々のキャラクターの歩行ステップを探索エッジとして扱う代わりに、ソルバーはmacro-pushアプローチを使用します。探索グラフの各エッジは、1回の完全な箱のプッシュを表します。エッジのコストは、プッシュ位置までのキャラクターの最短歩行距離に、プッシュ自体のコスト1を加えたものとして計算されます。これにより、探索は個々の歩行ステップをスキップしつつ、キャラクターの移動回数の真の最小値を計算することが可能になります。

State Compression and Memory Management

数百万の状態を限られたメモリフットプリントに収めるため、ソルバーはコンパクトなビットマスク状態を使用します：

Box Positions: 箱の配置は、盤面の到達可能な「ライブ」セルにわたって32ビット整数にパックされます。
Keeper Position: キャラクターの配置は、別の数値として保存されます。
State Representation: これにより、状態を約1 KBのオブジェクトから単一の約8バイトのキーに削減し、数百万の状態を数十メガバイトに収めることができます。

Data Structures for Performance

パフォーマンス向上のため、ソルバーはA*のフロンティア用にdial bucket queueを使用し、訪問済みセット用にopen-addressed hashを使用します。フラットなtyped-arraysを使用することで、実装はアロケーションフリーかつキャッシュフレンドリーであり、これはJavaScriptにおけるパフォーマンスにとって極めて重要です。

Deadlock Pruning

許容性を維持し最適性を確保するため、ソルバーは2つの枝刈り技術を採用しています：

Dead-square table: ゴールから逆到達可能性を用いて生成される静的テーブルにより、箱がゴールに移動できないマスを特定します。
Freeze check: 壁を考慮したプッシュ距離の下限に基づき、証明可能な解決不能な配置を破棄するメカニズムです。

Performance and Constraints

ボード1から14まではミリ秒単位でリアルタイムに解かれますが、15番目のボード（8個の箱がある迷路）の複雑さは顕著な外れ値です。この特定のボードの最適探索は、約4900万の状態を探索し、1 GB以上のメモリを必要とします。これはブラウザのタブの制限を超えるため、ボード15の解はC++で24コアを使用した並列A*探索を用いてオフラインで計算され、事前計算された解として再生されます。

Community Discussion and Insights

Hacker Newsのコミュニティメンバーは、このプロジェクトを、現代のLLMベースのAIに対する「古典的AI」（探索とエキスパートシステム）への回帰として議論しました。一部のユーザーは、ソルバーのアプローチが、キャラクターがゴールに到達しなければならないという追加の制約条件を持つSokobanパズルの特定のバリエーションであると指摘しました。

その他の技術的な批判や提案も、コミュニティのフィードバックに含まれていました：

I wonder: maybe the state is overly compressed? Could it speed things up to store (boxes, [every position the keeper can reach without pushing]) rather than (boxes, representative keeper position), so we can reduce recomputation of the keeper walking around?

I wonder: are there any other simple pruning techniques that you could incorporate? Any learnings from state-of--the-art Sokoban solvers, like this one?

ユーザーはまた、ソルバーが任意のボード状態からAIによる解決を開始できることに注目しました。これにより、解決策を要求する前に箱を不利な位置に移動させてパズルを「悪化させる」ことで、パズルを探索することが可能になります。