Show HN: ソコバンAIソルバー

ソコバン ソコバン（倉庫番）は1980年代のパズルで、全ての箱をゴールに押し込むことが目的です。このバリアントでは、倉庫番自身もゴールで終了する必要があります。 盤面: リセット 元に戻す AIで解く AI速度: 遅い 普通 速い 次へ → 移動数: 0 最適解: – ▲ ◀ ▶ ▼ 倉庫番（あなた） 箱 ゴール ゴール上の箱 壁 遊び方とルール 倉庫はグリッド状になっています。各ステップで、倉庫番は上下左右に1マス移動します。倉庫番は壁や箱の中に入ることはできません。箱のすぐ先のマス（押す方向）が空きフロアまたはゴールである場合、箱を1つ押すことができます。1回のステップで動く箱は1つだけで、スペースを空けるために箱をゴールから再び押し出すことも可能です。 操作: 矢印キーまたはW A S D、または画面上のパッド。 元に戻す: ステップを戻します。 リセット: 盤面を初期状態に戻します。 ゴール: パズルは、全ての移動可能な要素、つまり全ての箱と倉庫番がゴールの上に配置されたときにクリアとなります。そのため、各盤面には箱の数よりも1つ多いゴールがあります。最後のゴールは倉庫番用です。 目的: この状態に到達するまでの移動回数を最小限にすることです。いくつかの盤面では、最適な移動回数が知られており、上記に表示されています。AI（許容的なヒューリスティックを使用）は、網羅的に探索できる盤面に対して最適な解を返します。 AIソルバーの仕組み ソコバンはA*探索問題ですが、1回の倉庫番の移動ごとに探索する単純なバージョンは、混雑した盤面では爆発的に計算量が増大します。ここで実行されているのは、私が書いたネイティブC++の最適ソルバーのプレーンJavaScriptポートです。これは単なる解ではなく、証明可能な最小移動回数の解を返します。 移動最適化マクロプッシュ A* 各探索エッジは、箱全体のプッシュであり、コストは（プッシュ地点までの倉庫番の最短経路）+ 1として計算されます。これにより、総コストは倉庫番の実際の最小移動回数となり、探索は個々の歩行ステップをスキップします。 コンパクトなビットマスク状態 箱は盤面の到達可能な「ライブ」セルに32ビット整数としてパックされ、倉庫番はさらに1つの数値にパックされるため、状態全体は〜1 KBのオブジェクトではなく、単一の約8バイトのキーとなります。数百万の状態が数十MBに収まります。 ダイアルバケットキュー + 開番地ハッシュ A*のフロンティアはコストでキー付けされたバケットキューであり、訪問済みセット（解の親リンク付き）はフラットな型付き配列ハッシュに格納されます。割り当てフリーでキャッシュフレンドリーです。 デッドロックプルーニング 静的なデッドスクエアテーブル（ゴールからの逆到達可能性）とフリーズチェックにより、証明可能な解決不可能な位置を破棄します。これは、壁を考慮したプッシュ距離の下限によってガイドされ、A*を許容的（したがって最適）に保ちます。 盤面1〜14は、ミリ秒単位で証明された最適解までライブで解決されます（上記の「最適解」として表示されている移動回数は、このソルバーが返す値と正確に一致します）。 盤面15. 8箱の迷路。 例外です。その最適探索は約4900万の状態を探索し、1 GB以上を必要とするため、ブラウザタブ内で実行するには長すぎます。そのため、その最適解（184移動）は、この正確なアルゴリズムのネイティブC++ビルド（並列A*探索、24コアで約5秒）によってオフラインで計算され、リプレイによって検証されました。そして、ページは単にその事前計算された解を再生します。そのため、盤面15の解はここで探索されるのではなく、ハードコードされています。 私のソコバンソルバーから構築されました。ソコバンについて →