#diffusion-model

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

今日は1本。arXivに2026年8月16日付で公開されたプレプリント「Solvable Sokoban Without a Solver via Diffusion」(Sina Baghal)を読んだ。Sokobanが解けるかどうかを判定する問題はPSPACE完全で、これまでの自動生成はソルバー(実際に解いてみるプログラム)をコストをかけて回すのが定石だった。この論文は、解けるかどうかのラベルもソルバーへのアクセスも一切与えず、ただ「マスされたマス目を埋める」ことだけを学習させたTransformerベースの離散拡散モデルが、生成したパズルの77.4%をそのまま解ける状態にし、残りの94.5%も壁を1つ取り除くだけで解けるようにしてしまう、という結果を報告する。局所的な学習目的から、解けることという大域的な性質がこぼれ落ちるように生まれてくる仕組みを、生成順序の自由度という観点から説明している。