HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Show HN: Sokoban AI Solver (mkornreich.me)

64 pointsby enjoyyourlife37 コメント

要約

この記事は、JavaScriptで実装されたソコバン(倉庫番)のAIソルバーについて説明しています。ゲームのルール、AIがA*探索とマクロプッシュ、ビットマスク状態を用いて効率的に解を見つけるアプローチ、そして複雑な盤面への対応方法が解説されています。特に、移動回数を最小限に抑えるための最適化手法が強調されています。

全文翻訳

Sokoban

倉庫番(Sokoban)は1980年代のパズルで、全ての箱をゴールに押し込むことが目的です。このバリアントでは、倉庫番自身もゴールに到達する必要があります。

盤面:

AI速度:

手数: 0 最適手数: –

倉庫番(あなた) 箱 ゴール 箱がゴール上にある 壁

遊び方とルール

倉庫はグリッド状になっています。倉庫番は1ステップごとに上下左右のいずれかのマスに1マス移動します。倉庫番は壁や箱には入ることができません。箱のすぐ後ろのマス(押す方向)が空き床またはゴールである場合に限り、箱を1つだけ押すことができます。1ステップで動く箱は1つだけで、スペースを確保するために箱をゴールから外へ押すことも可能です。

  • 操作: 矢印キーまたは W A S D、あるいは画面上のパッドを使用します。ステップを元に戻すことができます。盤面をリセットすることも可能です。
  • ゴール: パズルは、全ての移動可能な要素、すなわち全ての箱と倉庫番がゴール上に配置されたときにクリアとなります。そのため、各盤面には箱の数より1つ多いゴールが用意されており、最後のゴールは倉庫番用です。
  • 目標: 可能な限り少ない手数でその状態に到達することです。いくつかの盤面については、最適手数も表示されています。AI(許容ヒューリスティックを使用)は、網羅的に探索できる盤面に対して最適解を返します。

AIソルバーの仕組み

倉庫番はA探索問題ですが、1回の倉庫番の移動ごとに探索する単純なバージョンでは、混雑した盤面で爆発的に状態数が増加します。ここで実行されているのは、私が書いたネイティブC++の最適ソルバーのプレーンJavaScriptポートです。これは、単なる解法ではなく、証明可能な最小手数*の解法を返します。

  • Move-optimal macro-push A
    y.
    各探索エッジは、箱を押すための(倉庫番がプッシュスポットまで最短で歩く距離)+ 1 をコストとする箱プッシュ全体であり、合計は倉庫番の移動手数の真の最小値となります。探索は個々の歩行ステップをスキップします。
  • Compact bitmask states. 箱は、盤面の到達可能な「ライブ」セル上に32ビット整数としてパックされ、倉庫番はさらに1つの数値で表されます。そのため、状態全体は、約1KBのオブジェクトではなく、約8バイトの単一キーとなります。数百万の状態が数十MBに収まります。
  • Dial bucket queue + open-addressed hash. A*のフロンティアはコストでキー付けされたバケットキューであり、訪問済みセット(解の親リンクを含む)はフラットな型付き配列ハッシュに格納されます。アロケーションフリーでキャッシュフレンドリーです。
  • Deadlock pruning. 静的なデッドスクエアテーブル(ゴールからの逆到達可能性)とフリーズチェックにより、証明可能な解決不可能な位置を破棄します。これは、A*を許容可能(したがって最適)に保つ壁を考慮したプッシュ距離の下界によって導かれます。

盤面1~14は、ミリ秒単位で証明された最適解までライブで解決されます(上記の「最適手数」として表示されている手数はこのソルバーが返す値と正確に一致します)。盤面15、すなわち8箱のマウスは例外です。その最適探索は約4900万の状態を探索し、1GB以上を必要とするため、ブラウザタブ内で実行するには時間がかかりすぎます。そのため、その最適解(184手数)は、このアルゴリズムのネイティブC++ビルド(並列A探索、24コアで約5秒)によってオフライン*で計算され、リプレイによって検証されました。ページは単にその事前計算された解法を再生するだけです。そのため、盤面15の解はここで探索されるのではなく、ハードコードされています。

私のSokobanソルバーから構築されました。倉庫番について →