Solvable Sokoban Without a Solver via Diffusion

コンピュータサイエンスの世界には、解法を検証することは容易だが、解を見つけ出すには、総当たりでは宇宙の年齢よりも長い時間を要するほど膨大な可能性の迷宮をナビゲートしなければならない、極めて複雑な問題のクラスが存在します。これらは単に難しいパズルではありません。答えへの道筋が単に長いだけでなく、指数関数的に長い、つまり、一歩進むごとに新たな可能性の宇宙が開かれると同時に、他の可能性が閉ざされてしまうような問題です。その最も有名な例の一つが、「倉庫番（Sokoban）」と呼ばれるゲームです。これはグリッド上でプレイされ、一人のキャラクターが特定のターゲット・マスに箱を押していくゲームです。落とし穴は、キャラクターは押すことはできても引くことはできないという点であり、一度箱が隅に挟まってしまうと、しばしば永遠に動かせなくなってしまいます。一つの箱の位置がボード全体の到達可能性を完全に変えてしまう可能性があるため、このゲームを小さな独立したタスクに分解することはできません。これを解くには、最初の一手を打つ前に、あらゆる相互作用を考慮した包括的な計画が必要となります。数十年にわたり、この種の新しい、有効なパズルを生成する能力は課題となってきました。なぜなら、解ける迷路を作成することは、それを解くことと同じくらい困難であり、迷路が機能するかどうかを確認するには、通常、あらゆる可能な動きをシミュレートするために強力なコンピュータを必要とするからです。

最近の研究では、コンピュータに解き方を教えることなく、これらの複雑なパズルを生成する驚くべき方法が見出されました。研究者たちは、周囲の文字に基づいて欠けている単語を推測してクロスワードパズルを完成させる人間のように、ソコバンンのグリッドの欠けている部分を埋めるように、ある種の人工知能モデルを訓練しました。モデルには何千もの実際のパズルが示され、壁、床、箱のパターンを学習するように求められましたが、どのパズルが解けるかについては教えられず、動作するゲームを作成するための報酬も与えられませんでした。モデルは単に、目に見えるタイルに基づいて、隠された場所にどのタイルが入るべきかを予測することを学んだだけでした。その結果は驚くべきものでした。モデルがゼロから新しいパズルを生成したとき、その77.4パーセントが解けるものでした。これは、モデルが解けることを保証するように明示的に訓練されたわけではなく、単に空白を埋めるように訓練されただけであるため、極めて注目すべき成果です。研究者たちは、解けるパズルを作成する能力は、モデルが学習した別個のスキルではなく、ゲームの局所的なパターンを学習することによる自然な副産物であることを発見しました。

このアプローチの成功は、モデルがどのようにグリッドを捉えているかに依存しています。テキストを書くような、シーケンスを生成する従来のコンピュータプログラムは、最初の単語、次の単語、その次の単語というように固定された順序で決定を下します。この線形的なアプローチは、グリッドの最初の方で行った決定が、最後の方の可能性を制約してしまうことがあり、プログラムが後から修正できない衝突を生じさせるため、倉庫番には向きません。しかし、この研究で使用されたモデルは、固定された順序に従いません。モデルは、すべてのセルが隠された完全に空のグリッドから始まり、ランダムな順序で一つずつセルを明らかにしていきます。各ステップにおいて、モデルは現在のボード全体（ここにある壁、あそこにある箱、そしてあちこちにある空きスペース）を見渡し、次に隠された場所に何が属すべきかを決定します。これにより、モデルは一方の隅に壁を置き、反対の隅にゴールを置いた上で、それらをつなぐ通路を考え出し、新しいピースを明らかにするたびにボード全体の理解を調整することができます。この柔軟性は、ボードの離れた部分同士の非局所的な相互作用から難しさが生まれるという、人間のプレイヤーがゲームについて考える方法を反映しています。

この手法がどの程度うまく機能したかをテストするため、研究者たちは5万個の新しいパズルを生成し、標準的なソルバーでそれぞれをチェックしました。その結果、パズルのほぼ4分の3が即座に解けることがわかりました。さらに示唆に富んでいたのは、解けないパズルに何が起きていたかです。解けないケースの94.5パーセントにおいて、内部の壁を一つ取り除くだけでパズルを修正することができました。これは、モデルがランダムに推測していたのではなく、ほとんど正しく、わずかな浅いエラーによって解決が妨げられているだけの構造を作り出していたことを示唆しています。また、研究者たちは、モデルが訓練中に見たパズルを単に記憶しているだけではないことを確認するために、生成されたパズルを元のデータセットと比較しました。その結果、生成されたパズルは、未見の実際のパズルと同様に、訓練データとは異なっていることがわかりました。モデルは、特定の事例のリストを単に覚えたのではなく、ゲームの根底にある構造を学習していたのです。

研究ではまた、研究者がモデルの確信度を調整したときに、モデルの挙動がどのように変化するかについても調査しました。モデルの選択をより断定的（決定的）にすることで、壁の密度が通常よりも少し高いパズルを作るという代償を払いつつも、解ける割合を99パーセント近くまで高めることができました。しかし、デフォルトの設定では、元の訓練セットに見られる壁の密度と完璧に一致するパズルが生成されました。この構造とランダム性のバランスが鍵となります。モデルは、パズルが有効であるためには、壁と箱が非常に特定の方法で適合しなければならないことを学び、空白を正しく埋めることを学ぶことで、図らずも解けるためのルールを学習したのです。研究者たちは、個々のタイルの予測能力が向上しなくなった後も、解けるというグローバルな特性に関するモデルの性能が向上し続けたことを指摘しました。これは、二つの目標が別個のものであることを示しています。つまり、モデルは単一のタイルを埋めることは得意でも、一つの完全なパズルを作成することは得意ではない場合があり得ますが、このケースでは、局所的な詳細をマスターすることがグローバルな解決策を解き出すのに十分であったということです。

この発見の意義は、より良いパズルを作ること以上に広がっています。それは、複雑なグローバルな特性が、単純なローカルな学習目的から創発し得ることを示しています。モデルにはパズルが解けるようにという指示は一度も与えられませんでしたが、それでもモデルはそれを作成することを学びました。これは、データの構造自体に解決策の論理が含まれており、システムのすべての部分間の関係を理解できるモデルは、それを解く能力を継承できることを示唆しています。研究者たちは、モデルが生成を導くための隠れたソルバーを使用していないことを確認しました。プロセスのすべてのステップは、グリッドの可視部分に基づいたモデル自身の予測によって駆動されていました。モデルが解法の経路を見ることなく、解ける迷路を生成できたという事実は、システムのパターンを深く理解することで、その最も困難な特性を再現できるという、学習の力を証明しています。

結局のところ、この研究は、問題を生成することと解くことの間の障壁は、これまで考えられていたほど高いものではないことを示しています。モデルに単にパターンを完成させるよう訓練することで、研究者たちは有効で複雑な課題を作り出す能力を解き放ったのです。モデルは、プレイする価値のあるゲームを作るためにグランドマスターである必要はなく、ただタイルのルールを理解していればよかったのです。このアプローチは、人工知能の考え方に新しい視点を提供します。つまり、もし複雑な世界における局所的な関係を理解するようにシステムを教えれば、その世界におけるグローバルな課題に対処する方法を明示的に教えられなくても、自然にナビゲートすることを学べる可能性があるということです。生成されたパズルは完璧ではありませんでしたが、小さな調整だけで機能するほどに近いものであり、モデルがゲームの本質を把握していたことを証明していました。