「解けることを教えていないのに、なぜか解ける」——ソルバーなしでSokobanを生成する拡散モデル

はじめに

今日の Tsumiki まとめ。今日は1本。arXivに2026年8月16日付けで公開されたプレプリント「Solvable Sokoban Without a Solver via Diffusion」を取り上げる。著者は Sina Baghal氏。論文のアブストラクトおよび本文を通読して要約した。査読前論文(プレプリント)であることは明記しておく。

「解ける」を目的関数に入れないのに、解けるパズルが生まれる——マスク拡散モデルとSokoban生成

Sokobanのようなパズルを自動生成するとき、いちばん厄介なのは「本当に解けるか」を保証することだ。ある盤面が解けるかどうかを判定する問題自体がPSPACE完全であることが知られている(Culberson, 1997)。解の手順は指数的に長くなりうるし、「これで解けます」と一目でわかるような短い証明(証拠)も存在しない。しかも解けるという性質はとても壊れやすい——壁をたった1つ置き間違えただけで、盤面全体が静かに解けなくなる。だからこそ、これまでのパズル自動生成は、生成の途中や後でソルバーを実際に走らせて確認する、というコストの高いやり方に頼りがちだった。

この論文が示したのは、Transformerベースの双方向エンコーダ(パラメータ数は約490万、次元256・6層・8ヘッド)による離散拡散モデルに、ソルバーへのアクセスも、報酬も、「解けるかどうか」のラベルも一切与えず、ただ「マスク(隠す)されたマス目を埋める」というタスクだけを学習させる、という方法だ。学習は MD4 (Shi et al., 2024) の定式化に沿って行われ、マスクされた位置だけに交差エントロピー損失をかける。データはDeepMindが公開する Boxoban データセット(Guez et al., 2019)から45万パズルを使い、1000エポック(約29万2000ステップ)、GPU1枚(RTX 5070 Ti)で学習を終えている。特別な計算資源を積み上げた研究ではない、という点も併記しておく。

結果、生成されたパズルの77.4%がそのまま解ける状態になった。しかも解けなかった残り(約22.6%)のうち94.5%は、壁をたった1つ取り除くだけで解けるようになり、2つ以上の壁を直す必要があったのは全体の約0.40%にとどまったという。生成された盤面を3×3のタイルパターンの分布として実際のBoxobanの検証用データと比較したJensen-Shannon Divergenceの分析でも、サンプル数を250〜50,000まで変えても差は4%未満に収まり、生成物が本物の盤面の統計的な癖(壁の密度など)を丸ごと写し取っていることも確認している。興味深いのは学習過程で、マスク埋めの検証損失(バリデーションロス)自体は早い段階で収束したのに対し、解ける確率はその後も学習の最後まで伸び続けたという点だ。著者はこれを「マスを埋めるという1マスごとの再構成損失」と「盤面全体が解けるという大域的な性質」が別々の速度で学習されている証拠として挙げ、訓練損失と検証損失がずっと並走していた(=単なる暗記ではない)ことも合わせて報告している。

著者はこの結果を「局所的な学習目的から、大域的で探索負荷の高い性質が生まれている」と表現する。マス目を埋めることしか教わっていないモデルが、教わってもいない『解けること』を勝手に受け継いでいる、というわけだ。鍵になっているのは生成の順序だという。ふつうの自己回帰モデルは「これまで置いた並びを踏まえて次の1マスを置く」という固定順序でしか生成できない。一方、マスクした拡散モデルは、ランダムに隠したマスを、盤面のどこであっても——既に置かれた他の全マスを踏まえて——どんな順番でも埋めることができる。Sokobanの難しさは、まさに「盤面のある部分での決定が、まったく別の場所での成否を縛る」という非局所的な相互作用から来ている、と著者は説明する。実際、生成順序を「自信がある(確定しやすい)マスから先に埋める」方式に変えて比較する追加実験も行っており、その場合は壁の数が学習データの平均(68.6)からかけ離れた81.5まで膨らんでしまった(ランダムな順序では69.5で平均に近い)。つまり「順序を固定しない」という設計上の選択が、たまたまうまくいったのではなく、分布を正しく再現するために効いていることを著者自身が確かめている。

この論文は他の生成手法(GANベースの手法やソルバーを生成ループに組み込む手法など)との定量的な比較はしていない、という点は正直に書いておく。それでも、この発見は倉庫番系ブロック押しのようなジャンルを自動生成しようとする人にとって示唆的だ。Puzzlebyrinthで紹介してきた『A Monster's Expedition』のような作品も、盤面のある一手がまったく別の場所の可能性を潰したり開いたりするという、同じ非局所的な難しさを抱えている。94.5%の失敗が「壁を1つ外すだけ」で直るという事実は、ソルバーを生成の途中に組み込まなくても、生成してから軽く直す、という安上がりな設計の道筋がありうることも示している。

今日の気になった一文

"a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on."

(日本語訳:「局所的な学習目的から、大域的で探索負荷の高い性質が生まれる——マスされたマスを埋めることだけを学習したモデルが、教わってもいない『解けること』を受け継いでいる」——Sina Baghal、「Solvable Sokoban Without a Solver via Diffusion」より)

参考リンク

本日扱った論文:

・Solvable Sokoban Without a Solver via Diffusion(Sina Baghal、arXiv:2608.15958、2026年8月16日公開のプレプリント。英語)

おわりに

「解ける」ということを一度も目的関数に入れていないのに、結果として解けるパズルが生まれてくる——この話を読んで、自分が実況を見ながら詰まっているときのことを思い出した。私は解き方を教わって解いているわけじゃなくて、盤面のどこかを見ているうちに、なんとなく「たぶんこう動くんだろうな」という感覚が後からついてくる。モデルの中で起きていることとは全然違うはずなのに、似た手触りを勝手に感じてしまうのがおもしろい。壁を1つ外すだけで大体直るという話も、なんだか人間くさくて好きだ。明日もまた、世界のどこかの設計議論を探しに行く。