Baghal: 解き方を一度も試さないAIが、解ける倉庫番を77.4%描いた — Fukai が読む

要点 — 解答プログラムを一度も呼ばずに、解ける盤面が出てきた

倉庫番(Sokoban。荷物を押して指定の位置に運ぶパズル)の盤面を機械に作らせるとき、いちばん面倒なのは「その盤面が本当に解けるのか」の確認だ。ふつうは1問作るたびに解答プログラムを走らせ、解けなければ捨てる。この原稿がやったのは、その確認を生成中に一度もしないことだった。

学習させたのは穴埋めだけである。10×10 の盤面のマスをランダムに隠し、隠れたマスに何が入るかを当てさせる。解答プログラムも、報酬も、「解ける/解けない」の正解ラベルも与えていない。それでも、出てきた盤面の 77.4% が解けた。

解けなかった残りも、94.5% は内側の壁を1マス消すだけで解けるようになる。合わせて実質 98.7%。著者はこれを「探索が要る大域的な性質が、局所的な学習目標から出てくる」と書いている。作る側にとっては、検算の置き場所が変わるという話だ。

誰が書いた、どんな原稿か

著者は Sina Baghal。単著である。arXiv の書誌ページには所属機関が記されていないので、ここでは名前だけを書いておく。

公開先は arXiv、識別子は arXiv:2608.15958、投稿は 2026年8月16日。主分類は cs.AI(人工知能)、副分類に cs.GT(ゲーム理論)と cs.LG(機械学習)が付いている。会議名もジャーナル名も記載がない。つまりこれは preprint(査読前の公開原稿)であり、peer-reviewed な論文ではない。出てきた数字は、その前提で読むことになる。まだ広く議論されている段階でもない。

私がこれを今日選んだのは、パズルを作る現場でいちばん静かに高くつくのが「検算」だからだ。盤面を描くこと自体は速い。だが描いた盤面が解けるかどうかを確かめるのは、パズルの種類によっては描くより何十倍も重い。そこに手を入れる話は、実装に近い。

しかも規模が小さい。パラメータは約490万、学習は GPU 1枚で回っている。研究所の計算資源がないと再現できない類の話ではない、という点も選んだ理由だ。

なぜ「解けるかどうか」が生成の壁になるのか

倉庫番が解けるかどうかの判定は PSPACE完全であることが知られている(Culberson, 1997)。原稿はその中身をこう説明している。解の手順は指数的に長くなりうるし、「これで解ける」と短く示せる証拠(certificate。第三者が短時間で検証できる証明書)が存在しない。

だから自動生成は、たいてい「作る → 解かせてみる → だめなら捨てる」の繰り返しになる。捨てる割合が高いほど、解答プログラムを回す時間が生成コストの本体になっていく。ここを削れると、パイプライン全体の性格が変わる。

学習データは DeepMind の Boxoban(Guez ら, 2019)、45万問である。すべて 10×10 のマス目で、タイルは7種類(壁、床、プレイヤー、箱、ゴール、ゴール上の箱、ゴール上のプレイヤー)。盤面はそのまま100マス分の並びとして扱える。

難しさの物差しとして、原稿は push-based solver(プレイヤーの歩数ではなく「押し」で枝分かれさせる解答プログラム)が解を見つけるまでに展開した状態の数を使っている。人間の体感難易度との関係については、Jarušek と Pelánek の研究で分解にもとづく指標が ρ=0.82、確率的探索モデルが r=0.76 という相関を出したことに触れている。

穴埋めだけを教える、という方法

使っているのは masked diffusion(マスク拡散)と呼ばれる生成のやり方だ。拡散モデルというと画像にノイズを混ぜていく話を思い浮かべるが、ここで混ぜるのはノイズではない。マスを [MASK] という「隠した」記号に置き換える。どれだけ濁らせるかではなく、どれだけ隠すかを段階で制御する。手順は MD4(Shi ら, 2024)という定式化に従っている。

学習は単純だ。45万問の盤面から1問取り、各マスを一定確率で独立に隠し、隠れたマスの正解タイルを当てさせる。隠す割合は直線的なスケジュールで決まり、段階の総数は100。盤面が100マスなので、1段階あたり平均1マスという対応になる。

ここで効いてくるのが「左から順ではない」という点だ。文章を書くモデルのように左上から順に埋めていくやり方だと、条件にできるのは常に「それより前」のマスだけになる。マスク拡散は、残りのどのマスの組み合わせを条件にしても答えられるように訓練される。倉庫番は盤面の端の壁ひとつが反対側の詰みを決める種類のパズルだから、この「どこからでも条件にできる」性質が効く、というのが著者の見立てである。

モデル自体は小さい。双方向 Transformer エンコーダで約490万パラメータ、内部の次元 256、6層、8ヘッド。各マスの埋め込みに行番号・列番号・段階の情報を足しているだけで、凝った仕掛けはない。学習は45万問を1,000周、バッチ1,536で292,000ステップ、RTX 5070 Ti 1枚の混合精度で回している。

細かいが効いている工夫がひとつある。損失の重みだ。ほとんど埋まった盤面(隠れているのが数マスだけ)は、そのままだと1問あたりの勾配が極端に重くなる。そこで重みに上限(原稿では10)を置いている。著者自身が書いているとおり、この上限は「解けるかどうかが決まる終盤の局面から、モデルがどれだけ学ぶか」を決めてしまうつまみでもある。

生成は逆向きだ。全マスが隠れた状態から始め、100段階かけて1マスずつ確定していく。確定する場所は毎回ランダムに選ぶ。確信度の高い順に確定すると壁ばかり先に置かれ、壁の平均枚数が 69.5 から 81.5 に膨らんでしまうからだ。一度置いたマスは後から書き換えない。(図解)生成の流れ。全マス隠した状態から、ランダムな順に1マスずつ確定し、100段階で盤面が出来上がる。この間、解答プログラムは一度も動かない。

77.4%、そして壁1枚で 98.7%

主結果は、生成した盤面の 77.4% が解けたことだ。何と比べて高いのかは気になるところだが、比較対象として別方式の生成器を並べた表は、私が読んだ範囲では原稿に見当たらなかった。ここは数字をそのまま受け取るしかない。

解けなかった盤面のうち 94.5% は、内側の壁を1マス消すだけで解けるようになった。これを足すと実質 98.7% になる。壁2マスまでの修復を数えると、本当に壊れているのは生成物全体の約 0.40% だけだという。つまり失敗のほとんどは、構造が破綻しているのではなく、通路が1箇所ふさがっているだけだった。

面白いのは、その「犯人の壁」をモデル自身が疑っていたらしいことだ。原因になった壁が確定されたときの確率の中央値は 0.45、同じ盤面の他の内側の壁は 0.93。数字の出どころは、5万問を生成したうちの不正解 11,288 問である。(図解)壁を1マス消すだけで、解ける割合は 77.4% から実質 98.7% へ。原因になった壁は、確定時の確率が中央値 0.45 と低かった。

「本物らしさ」も測っている。盤面を 3×3 の窓 64 個に分けてタイルの並びの分布を取り、45万問の学習データとの隔たり(Jensen-Shannon divergence)を見る方法だ。生成した盤面と、学習に使っていない本物の盤面は、どちらもサンプル数の -0.59 乗で隔たりが縮んでいく。著者の言い方を借りれば、本物の曲線が「床」であり、生成の曲線はその上に乗っている。

温度(生成のばらつきを絞るつまみ)を 1.0 から 0.6 に下げると、解ける割合は 3.8 ポイント上がる。ただし壁の平均枚数が 69.5 から 73.2 に増える。学習データの平均は 68.6 なので、絞るほど盤面が本物から離れていく。同時に、解答プログラムが必要とする手間の中央値は 36% 減る。要するに「解きやすく、壁が多く、本物らしくない」方向に寄るということだ。

もうひとつ、学習を止める場所の話がある。検証損失は早い段階で平らになるのに、解ける割合は最後まで伸び続けた。原稿は「損失が平らになった時点で止めた実行は、解ける割合をおよそ25ポイント捨てていたことになる」と書いている。生成器を自作する人には、ここがいちばん実務的な指摘かもしれない。

パズルを作る人は、ここから何を持ち帰れるか

第一に、検証をやめるのではなく減らすという読み方だ。もし自分が倉庫番系のレベル生成を回しているなら、100問生成して77問がそのまま通る前提で、解答プログラムの予算を組み直せる。全問に解答プログラムをかける設計から、「落ちたものだけ深く調べる」設計に変えられる。

第二に、「壁を1マス消す」を修復手として実装する。落ちた盤面をすぐ捨てるのではなく、内側の壁を1マスずつ外して再判定する後処理を挟む。この原稿の条件では、それだけで失敗の 94.5% が救われた。捨てる前にもう一手ある、という発想は他のジャンルにも移せる。

第三に、モデルの確信度を「怪しいマス」の検知に使う。確定したときの確率が低いマスを記録しておき、疑わしい順に修復や検査を試す。原因になった壁の中央値 0.45 に対し、他の壁は 0.93。この差があるなら、全マスを総当たりする必要はない。

第四に、温度を難易度のつまみとして扱う。0.6 に絞れば解きやすい盤面が増えるが、壁が増えて見た目が単調になる。チュートリアル用には絞り、中盤以降は 1.0 に戻す、といった使い分けができる。ただし見た目の変化を必ず目で確認すること。数字上は良くても、プレイヤーには「同じような面ばかり」と映る危険がある。

第五に、学習の止め時を損失で決めない。自作の生成器でも、検証損失ではなく「使える盤面の割合」を定期的に測り、それが伸びなくなるまで回す。この原稿では、その差がおよそ25ポイントあった。

第六に、規模の話。約490万パラメータ、GPU 1枚という条件は、個人開発やハイパーカジュアルの現場でも現実的だ。もし自分が小さなチームで面の量産を考えているなら、巨大なモデルを借りてくる前に、手元のデータで穴埋めだけを学ばせる選択肢を検討する価値がある。

何が分かっていないか

まず設計上はっきりしている制約から。対象は Boxoban の 10×10、箱4個という形式に限られる。盤面の大きさが変わったとき、あるいは倉庫番以外のルールに移したときに同じことが起きるかは、この原稿からは分からない。生成は100段階の固定手順で、途中で置いたマスをやり直す仕組みもない。

著者自身が明示しているのが、損失の重みの上限の話だ。上限を置くことで、ほとんど埋まった終盤の局面から学ぶ量が抑えられる。そして解けるかどうかを決めるのは、まさにその終盤に置かれる数マスである。著者はこの上限を「モデルが、自分は一度も教わっていない大域的な性質について、どれだけ学ぶかを決める」ものだと書いている。77.4% という数字は、このつまみの位置とセットで見る必要がある。

丸写しの検査も用意されている。生成した各盤面について、45万問の学習データの中で最も近いものとのハミング距離(100マスのうち何マスが違うか。0 なら完全な複製)を測り、比較の前にプレイヤーの位置は正規化する、という設計だ。検査の設計はこのとおり読めたが、その結果の数値までは私は原文で確認できていないので、ここでは数字を書かない。

ここから先は、Fukai がここで指摘する点である。ひとつめ。「解ける」は「面白い」ではない。原稿は生成した盤面を学習データの難易度四分位に当てはめて示しているが、人間のプレイヤーに遊ばせた評価は含まれていない。解答プログラムの探索量と人の体感の相関については先行研究(ρ=0.82 など)が引かれているだけで、この生成器の出力そのものが人に対して検証されたわけではない。

ふたつめ。比較対象が弱い。左から順に埋める方式など、他のやり方でどの程度の解ける割合が出るのかを並べた実験は、私が読んだ範囲では見当たらなかった。77.4% が方式の勝利なのか、Boxoban という素材の性質なのかは、この原稿だけでは切り分けにくい。

みっつめ。これは preprint であり、査読を通っていない。単著で、追試もまだない。ここに書かれた数字は「この条件下でこう観察された」という報告として読むのが正しく、「拡散モデルは解ける盤面を作れる」という一般則として持ち出すのは早い。

Fukai の読み

私はこの研究を、「作る力」の競争ではなく検算をどこに置くかの設計という流れの中に置きたい。生成AIをレベル制作に使う話の多くは、より複雑なものを作れるかを競っている。この原稿が示したのはむしろ逆で、作る側は何も賢くなっていないのに、確かめる側の仕事が減った。穴埋めという地味な課題を、マスの確定順を固定しない形で解かせた結果、盤面の離れた場所どうしの辻褄が副産物として合ってしまった、と読める。設計批評の語彙で言えば、これはルールの自動化ではなく整合性チェックの自動化に近い。だとすれば、次に問われるのは精度ではなく、「確かめずに出してよい基準を、作り手はどこに引くのか」という運用の問題になると私は考えている。

次に何を読むと地図が見える

手で組む面と機械が生む面の役割分担については、当サイトの手で組む面、機械が生む面 — パズルレベル自動生成の設計論が地図になる。生成した面の「詰み」をどう見せるかという話は読める失敗 — パズルの『詰み』をどう可視化するかのほうが詳しい。押して運ぶパズルの手触りを確かめたい人は、A Good Snowman Is Hard To Build や Patrick's Parabox から入るといい。

原典まわりでは、生成の骨格である MD4(Shi ら, 2024)と、データセットの Boxoban(Guez ら, 2019)、そして倉庫番の計算量を確定させた Culberson(1997)の3本を押さえておくと、この原稿が何を借りて何を足したのかが見える。順番としては Culberson → Boxoban → MD4 → 本稿が読みやすい。

参考文献

本記事で参照した論文と関連資料:

・Solvable Sokoban Without a Solver via Diffusion (Sina Baghal, 2026, arXiv preprint / 査読前)

・関連研究: Simplified and Generalized Masked Diffusion for Discrete Data (Shi ら, 2024, NeurIPS 2024)(本稿が従う MD4 の定式化)

・データセット: Boxoban Levels (Guez et al., DeepMind, 2019)(本稿の学習データ 45万問)

・背景: Joseph Culberson, "Sokoban is PSPACE-complete" (1997)(倉庫番の可解性判定が PSPACE完全であることを示した古典)