倉庫番の「最短手順」をブラウザだけで証明する──ネイティブC++探索をJSに移植したSokoban Solver

3行まとめ

1. 個人開発者が公開したブラウザ版倉庫番は、ネイティブC++で書かれたA*探索エンジンをJavaScriptに移植したもので、「解ける」だけでなく「証明された最少手数」を返すのが特徴。
2. 探索の高速化には、盤面状態を32ビット整数のビットマスクに詰める圧縮、コストをキーにしたバケットキューと型付き配列上のオープンアドレッシング・ハッシュ、デッドロック局面を先読みで枝刈りする手法が使われている。
3. 8箱の最重量ボード（board 15）だけは約4,900万状態・1GB超のメモリを要し、ブラウザでは現実的な時間で解けない。24コアの並列ネイティブC++版が事前に計算した184手の最適解を、サイト自体は「再生」しているだけだという点をREADMEで確認した。

「解ける」ではなく「これ以上短くならない」を返す

倉庫番は、キーパーが箱を押してすべてゴールマスに乗せるパズルだ。このサイトのバリアントでは、箱だけでなくキーパー自身も最終的にゴールマスの上にいる必要がある（そのため、盤面のゴール数は箱の数より1つ多い）。単に「解ける手順」を出すのではなく、「証明された最少手数の解」を返すのがこのソルバーの主眼で、サイト側の説明には「A*探索問題だが、キーパーの1歩ずつを愚直に探索するナイーブな実装は混雑した盤面で爆発する」と明記されている。

4つの高速化手法

サイトの技術解説セクションによれば、実装されている工夫は次の4つだ。

• 手数最適なマクロプッシュA*：探索の1辺（エッジ）を「箱を1回押す」という単位にまとめ、そのコストを「キーパーがその押し位置に歩いていく最短距離＋1」として計算する。合計は本当の最小キーパー移動手数になり、探索自体は個々の歩行ステップを飛ばして進む
• コンパクトなビットマスク状態：箱の配置を、盤面の到達可能な「生きた」マスの範囲で32ビット整数に詰め込み、キーパーの位置ももう1つの数値にする。1つの状態全体が約1KBのオブジェクトではなく約8バイトの鍵になり、数百万状態が数十MBに収まる
• ダイヤルバケットキュー＋オープンアドレッシング・ハッシュ：A*のフロンティアはコストをキーにしたバケットキューで管理し、訪問済み集合（解を復元するための親リンク込み）は型付き配列上のフラットなハッシュに置く。アロケーションなし・キャッシュフレンドリーな設計
• デッドロック枝刈り：ゴールからの逆到達可能性による静的なデッドマス表と、フリーズチェックが、証明可能に解けない局面を捨てる。これは壁を考慮した押し距離の下界と組み合わされ、A*の許容性（admissibility、つまり最適性の保証）を保ったまま行われる

サイトによれば、ボード1〜14はこの仕組みでミリ秒単位で証明された最適解に達する。

8箱の迷路だけは「事前計算の再生」

ボード15（8箱の迷路）だけは例外だとサイトは明記している。最適探索は約4,900万状態を探索し1GB超のメモリを要するため、ブラウザのタブ内で現実的な時間に終わらせるのは難しい。そのため、最適解（184手）はこのアルゴリズムのネイティブC++版によってオフラインで計算され（並列A*探索、24コアで約5秒）、リプレイで検証された上で、ページはその計算済みの解を単に再生しているだけだという。

この数字が正確かどうか、GitHubで公開されているソルバー本体（mkornreich/sokoban）のREADMEも実際に取得して照合した。README中には実行例として次の出力がそのまま掲載されており、サイトの説明と完全に一致していた。

$ ./solver p15 600 --solution
[p15] boxes=8 goals=9 live=32 h0=32 timeout=600s
  ...expanded 4221749, f=82 gen=10083381 best=-1 0s
RESULT p15 optimal=184 expanded=49090929 generated=76482528 seconds=5.3 threads=24

「探索した状態数4,909万」「最適解184手」「24スレッドで5.3秒」という、ブラウザ版デモページの説明文に出てくる数字が、実際のC++ソルバーの標準出力とそのまま一致している。デモページのプロダクト文だけでなく、その裏付けとなるコマンドライン出力までさかのぼって確認できた、という点は書いておきたい。

全15ボードの検証済み最適解

README生データには、組み込みの15ボード全ての検証済み最適手数が一覧で載っている。

README自身が「p15以外はすべて1秒を大きく下回って解ける。p15だけは12コアのデスクトップで約5秒・約1.2GBを要する」と明記しており、記事本文で示したデモページの主張と数字が一致している。

状態空間の設計:32ビット/128ビットの2段構え、メモリは事前に丸ごと確保

READMEのアルゴリズム解説（Algorithm章）によれば、1つの状態は「(箱のビットマスク, キーパーのマス)」というペアで表現される。生存可能マス（ゴールに到達できるマス、全ゴールからの逆方向BFSで事前計算）が32個以下のボードは32ビットのマスクを使い、状態キー全体を40ビットに詰め込んで1つの64ビットワード（キーと値を同じワードに同居させる）で扱う。33〜128個の生存可能マスを持つボードでは128ビットのマスクと、より広いハッシュに切り替わる仕組みで、探索全体がマスクの型でテンプレート化されているため、小さいボードは大きいボード用のコストを一切払わない設計だという。対応範囲の上限は、盤面の総マス数255以下（8ビットのキーパーインデックス）・生存可能マス128個以下・f = g + h < 6000で、これを超えるボードはUNSUPPORTEDまたはNONEという結果を返す。メモリは探索開始前に生存可能マス数に応じてまとめて確保され、24マス未満は32MiB、24〜32マス（p7・p15が該当）は1GiB、それ以上は見積もりベースで最大約800MiBを確保する。空きRAMがこれに満たないマシンでは、探索開始前に明確な「メモリ不足」エラーで中断される設計になっている。

並列化の実装も具体的だ。共有される探索状態は、状態を最良のg値とクローズ済みフラグへマッピングする「オープンアドレッシングの並行ハッシュ（線形プロービング、固定サイズ、リハッシュなし）」1つに集約されている。高速パスでは1スロットがキーと値を同じ64ビットワードに収めた単一のatomic演算で、CAS（Compare-And-Swap）だけで完結する「純粋にロックフリー」な設計だという。ワーカースレッドは(スレッド, fレベル)ごとのチャンクバッファに後続状態を貯め、各波の終わりにまとめてグローバルなバケットへ移す構成で、ホットループはこのハッシュ以外に共有キャッシュラインへの書き込みを行わない、とREADMEは説明している。解の復元（--solution指定時）は、探索中は親ポインタを一切保存せず、完了後のハッシュからg値の整合性だけを頼りに逆順にたどり直す設計だという。

solver.cpp本体を読んで確認したこと

READMEの説明が実装に反映されているかどうかを確かめるため、solver.cpp（677行、raw.githubusercontent.com経由で取得）を実際に読んだ。冒頭のコメントブロックには、この記事でここまで紹介してきた設計（マクロプッシュA*・ビットマスク状態・デッドロック枝刈り・ロックフリーの並行ハッシュ）がすべて列挙されており、対応する実装をコード側でも確認できた。

• メモリ確保：ハッシュテーブル用のメモリはmadvise(p, bytes, MADV_HUGEPAGE)（106行目）でヒュージページを明示的に要求している。コメントには「テーブルはランダムアクセスされるためTLBミスが支配的になる。2MBアラインメント＋MADV_HUGEPAGE＋次スロットのソフトウェアプリフェッチで対処する」とあり、実際に__builtin_prefetchを使ったプリフェッチ呼び出し（271行目・332行目・519行目など）が探索ループの随所に入っていた。
• ロックフリーの実装：訪問済み集合への書き込みはstd::atomicのcompare_exchange_weak/compare_exchange_strong（278・282・296・340・352・368行目）で行われており、ミューテックスは使われていない。コメント通り「多数のスレッドがロックなしで共有する」設計が実コードでも確認できた。
• ヒューリスティックの差分更新：探索の各ステップでヒューリスティック値hを全箱について再計算するのではなく、nf = ng + hpar - DMIN[bcell] + DMIN[t]（515行目）という1行で、押した箱1つ分の変化だけを差分計算している。コメントの「h(nmask) = f - g - DMIN[from] + DMIN[to]、箱ごとのループなし」という説明と実装が一致している。
• ビルドコマンド：ファイル冒頭にg++ -O3 -march=native -std=c++17 -pthread solver.cpp -o solverというビルドコマンドがそのまま書かれていた。
• ボードデータの格納方法：全15ボードは、0=床・1=壁・2=箱・3=キーパー・4=ゴール・5=箱+ゴール・6=キーパー+ゴールという数字グリッドの文字列として、ソースコード内に直接ハードコードされている（外部ファイル読み込みではない）。

これらは全てコメントに書かれている設計方針と実コードが一致していることを確認したもので、実際にこのバイナリをビルド・実行してボード1〜14の解答時間を計測したわけではない。

ブラウザ版が本当にミリ秒で解けるかは自分では計測していない

本記事はmkornreich.meのSokobanページと、そこからリンクされているGitHubリポジトリ（mkornreich/sokoban）のREADME・solver.cpp本体・GitHub APIのリポジトリメタデータをcurlで取得した内容にもとづく。GitHub APIで確認したリポジトリメタデータは、star数4・fork数0・open issues 0、created_atは2026-07-20T16:13:36Z、最終push（pushed_at）は2026-07-22T04:59:42Z、言語はC++、ライセンスは未設定（GitHub上でライセンスファイルが検出されていない）だった。ブラウザ版のJavaScriptソルバーを実際に自分のブラウザで動かし、ボード1〜14が本当にミリ秒単位で解けるかを計測したわけではない。またこの記事はソースコードを読んで設計と実装の一致を確認したのみで、solver.cppを自分の環境でビルド・実行して数字を再現したわけでもない。

最適解を証明するパズルソルバーという切り口は未紹介

Zenn・Qiitaともに実質的な言及はなかった（Zennはフォールバックのみ）。倉庫番の最適解探索アルゴリズム自体は競技プログラミングの文脈で日本語記事もあるが、この個人プロジェクトの固有名詞での紹介はまだない。

関連記事

• ゲームバランスをAIのbotに240回遊ばせて計測した──「深追いの崖」の位置が数字で見えるまで
• Claude Codeで初心者がゲームを作る手順──未経験から公開までの4ステップ