「一つの鍵と、一つの扉」を守れるか——ダンジョン生成が苦手なこと、色を積むだけのパズルがNP困難になる理由

はじめに

今日のTsumikiまとめ。今日は2本。

1本は、迷路やダンジョンを自動生成する側の研究。もう1本は、パズルの難しさそのものを数学で証明する側の研究。作る側と、難しさを裏付ける側、対になる二つの視点を追ってみる。

迷路やダンジョンの自動生成に進化計算を組み合わせると、何が変わるのか?——Evolutionary Wave Function Collapse(IEEE CoG 2026)

答えは、「その場その場の関係だけで決まる性質」は伸ばせるが、「盤面全体にまたがる整合性」は相変わらず苦手、というものだ。IEEE CoG 2026(2026年9月1〜4日、マドリード。Procedural Content Generationセッション、9月2日発表)で発表された論文「Evolutionary Wave Function Collapse」は、迷路やダンジョンのタイル生成によく使われる定番手法Wave Function Collapse(WFC)に、進化計算を組み合わせる方法を提案している。著者はDipika Rajesh(カリフォルニア大学サンタクルーズ校)、Ahmed Khalifa(マルタ大学)、Julian Togelius(ニューヨーク大学)の3人。arXivに2026年7月付けで公開されている論文(2607.02082)を読んだ。

WFCは、見本となる小さな盤面やタイルの並びから「どのタイルが隣に来てよいか」という局所的な制約だけを学習し、そこから大きな出力を組み立てる生成手法だ。計算が軽く仕組みも単純なので、迷路やダンジョンのタイル生成でよく使われてきた。ただし弱点もある。見本から学んだ局所ルールの積み重ねだけでは、「盤面全体で鍵と扉をちょうど1組だけ配置する」といった、盤面全体を見渡さないと判定できない制約を保証できない。

この論文が試すのは、WFCが生成した盤面そのものを直接いじるのではなく、WFCに渡す「小さな見本」の方を進化計算で改良するという発想だ。見本を遺伝子型、WFCがそこから作る盤面を表現型とみなし、盤面の出来をスコア化しては見本を少しずつ書き換えていく。評価対象は二つ——迷路のつながりやすさ(コネクティビティ)と、ゼルダ風ダンジョンの部屋配置。

結果は対称的だった。迷路のつながりやすさのように、盤面のどこを見てもその場の関係だけで判定できる性質については、進化計算による改良がはっきり効いた。一方、ダンジョンで「鍵と扉をちょうど1組だけ置く」といった、盤面全体を見渡さないと判定できない制約は、見本を進化させるだけでは依然として崩れやすく、局所パターンに基づく生成手法の限界がそのまま姿を現したという。

持ち帰り文としてはこうなる——WFCのような局所パターン学習の生成手法を安全に頼れるのは、"つながっていればよい"式の局所的に成立する性質までで、"鍵は一つだけ"のような大域的な整合性を要求した瞬間、進化計算を足しても綱渡りになる。当サイトのカタログでは『TUNIC』のように、ゼルダ的な探索そのものをパズルにした作品があるが、こうした「手作りだからこそ、鍵と扉の対応が最後まで狂わない」ダンジョンの価値は、この論文が示す機械生成の限界の裏返しとして読める。『TUNIC』(TUNIC Team, 2022)Steamストアページより

色付きのブロックを積んで、同じ色同士をくっつけて消すだけのパズルが、なぜ数学的に「難しい」と証明されるのか?——Hexasortの計算量理論(TU Wien)

答えは、盤面をどれだけ単純な形に削っても、色をたった1種類に絞っても、このゲームが解けるかどうかを判定する問題は依然としてNP困難であり続けるからだ。オーストリア・ウィーン工科大学(TU Wien)アルゴリズムと計算量理論グループのLinus Klockerは、スマートフォン向けパズル『Hexasort』の解答可能性を扱った論文をarXivに公開している(2603.01244、2026年3月)。

論文の書き出しはこうだ。「広く遊ばれているパズル・マッチ系ゲームの多くは、計算量理論のレンズを通して分析されてきた。代表例はSudoku、Candy Crush、Flood-Itだ。これらのゲームに共通するのは、その一般化版の決定問題がNP困難だという点であり、これはしばしば、プレイヤーにとっての『抜け出せない難しさ』や『やめられない魅力』の源だと考えられている」。Hexasortは、グラフの頂点(実際のゲームでは六角形の盤面のマス)に色付きのスタックを一つずつ置いていき、隣り合う同色のスタックが自動で合体、一定の高さに達すると消える、というルールのゲームだ。盤面を空にする「Empty」版と、置き場所を切らさず最後まで置き切る「Fitting」版の2つの目標がある。

Klockerが示したのは、色を1種類だけに絞り、盤面の形をどんどん制限していっても——木構造で、しかも高さや各頂点のつながる数(次数)に上限を付けた場合でも——Hexasortが解けるかどうかを判定する問題はNP困難であり続けるということだ。証明には「3-Partition問題」と呼ばれる、数の集合を合計が等しくなるよう3個ずつのグループに分ける古典的な難問からの帰着が使われており、扱う数値の大きさを多項式の範囲に抑えても難しさが消えない「強いNP困難性」まで示している。

一方で論文は「どこからなら簡単になるか」も地図として描いている。色の種類数としきい値の高さをパラメータとして固定すれば、動的計画法で多項式時間で解ける場合があることを、具体的なアルゴリズムとともに提示した。当サイトの機構語彙にある倉庫番系ブロック押しも、同じように計算量理論の側から「なぜ難しく感じるのか」を調べられてきた機構であり、Hexasortの結果はその系譜に並ぶ一例と言える。

持ち帰り文としてはこうだ——「同色同士がくっついて消える」というたった一つの単純なルールでも、盤面の形を木構造まで削り込み、色を1種類にまで絞っても、解けるかどうかの判定はNP困難であり続ける。単純なルールの組み合わせから抜け出せない難しさが生まれること自体が、こうしたパズルが「やめられない」と感じられる仕組みの一つの説明になっている、と論文は述べている。

今日の気になった一文

"A common theme among these widely played games is that their generalized decision versions are NP-hard, which is often thought of as a source of their inherent difficulty and addictive appeal to human players."(これらの広く遊ばれているゲームに共通するのは、その一般化版の決定問題がNP困難であるという点だ。これは、プレイヤーにとっての『抜け出せない難しさ』や『やめられない魅力』の源だと、しばしば考えられている。)

—— Linus Klocker「Hexasort – The Complexity of Stacking Colors on Graphs」より。数学の証明が、そのまま「なぜこのパズルはやめられないのか」への一つの答えになっている一文として印象に残った。

おわりに

私はパズルを解くのが得意ではないが、今日の2本を並べて読むと、「作る側の限界」と「難しさの正体」が同じ場所を指しているように見えて、デザイナー志望として素直に面白かった。局所的なルールを積み重ねるだけでは守れない全体の整合性があり、逆に局所的なルールを積み重ねるだけで、抜け出せない難しさが生まれてしまう。どちらも一人の設計者の手加減では御しきれない話で、だからこそ人が丁寧に組んだ盤面には価値があるのだと思う。明日もよろしくお願いします。

参考リンク

本日扱った記事:

・Evolutionary Wave Function Collapse(Dipika Rajesh, Ahmed Khalifa, Julian Togelius / arXiv 2026年7月・IEEE CoG 2026 Procedural Content Generation セッションで発表)

・IEEE CoG 2026 Conference Schedule(開催: 2026年9月1〜4日、マドリード)

・Hexasort – The Complexity of Stacking Colors on Graphs(Linus Klocker, TU Wien / arXiv 2026年3月)