Halina & Guzdial: レベルを「時間のケーキ」として生成する — Fukai が読む

一段落要約

ゲームのレベル(面)は、多くの自動生成手法の中では「静止画」のように扱われてきた。だがゲームの本質は時間とともに動くことにある。プレイヤーが動き、箱が押され、状態が刻々と変わる。この論文で Emily Halina と Matthew Guzdial(カナダ・アルバータ大学)は、レベルを「時間の各瞬間の盤面をスライスとして積み重ねたもの」として表す新しい表現、名づけて「ケーキ(cake)表現」を提案する。積み重なったスライスがケーキに見えるからだ。

この表現の上で動く生成手法 PRP(Playtrace Reconstructive Partitioning、プレイの軌跡を使ってレベルを組み立て直す方法)を使うと、レベルとその解答を同時に作り出せる。倉庫番(Sokoban)で六つの既存手法と比べたところ、遊べること(playability)を100%保ちながら、多様性も高い水準で両立した。しかも「このレベルは解けるか」を外部でチェックする仕組みも、報酬関数も一切使わずに、である。動きの情報を表現そのものに埋め込んだのが効いている、と私は読んだ。

はじめに

今日紹介するのは、Emily Halina と Matthew Guzdial による「Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning」だ。二人はアルバータ大学の計算科学科と Amii(Alberta Machine Intelligence Institute)に所属している。この論文は arXiv に 2026年7月13日に投稿された preprint(arXiv:2607.12097)であると同時に、査読を通った国際会議 FDG 2026(Foundations of Digital Games、8月にコペンハーゲンで開催)の採択論文でもある(DOI が付いている)。つまり査読前の草稿ではなく、正式に発表される論文だ。

Guzdial はゲームの手続き的生成(PCG、Procedural Content Generation。コンテンツを人手ではなくアルゴリズムで自動生成すること)の分野で長く研究してきた人で、この論文はどちらかというと「新しい道具立ての土台」を据えるタイプの仕事にあたる。派手な生成デモよりも、レベルを何としてコンピュータに持たせるかという表現の問い直しが主眼にある。

私がこれを今日選んだのは、Puzzlebyrinth のように倉庫番系のパズルを作る側にとって直に使える話だからだ。手元にある数枚の面から、遊べることが保証された新しい面を大量に、しかも高速に作れる——その仕組みの中身を、論文を開かなくても掴めるように解説したい。

背景

これまでのレベル表現には、タイル(格子状のマス目)、グラフ、画像、メモリなど様々な形があった。だが著者たちの整理では、これらはどれもレベルを静的なもの、つまり止まった一枚の状態として扱ってしまう。ところがゲームは動く。外から動きの情報を補わない限り、生成した面が本当に遊べるか(クリアできるか)を保証できない、というのが出発点の問題意識だ。

動きの情報を足す工夫は過去にもあった。例えばスーパーマリオの有名なデータ集(VGLC)では、プレイヤーの通り道を別のトークン(記号)として盤面に重ねる。だがこれは二次元の表現なので、プレイヤーが同じマスを何度も往復すると本当の経路を表せない。ほかにも、人手で書いた制約や、解答を探すソルバーを報酬に組み込む(強化学習系の)やり方があるが、いずれも動きの情報を表現の外側で近似しているにすぎない。

この「外付け」のやり方は、新しいゲーム領域ごとに設計情報を人手で書き直す手間を生む。もし静的な表現と動的なゲームプレイの食い違いそのものを埋められれば、レベル生成にも自動プレイにも使い回しが効き、設計者が自分のゲームにこうした仕組みを持ち込みやすくなる——そこにこの研究の狙いがある。

アプローチ / 方法

まず中心となるケーキ表現から。著者はレベルを、時間の各ステップでの盤面(n×m マスの状態)を k ステップ分だけ積み重ねた立体として定義する。この一枚一枚の「スライス」がその瞬間の全状態を記録し、積み重ねが時間の流れそのものになる。前提の一つはマルコフ性(各時点の状態だけを見れば次の状態が決まる、という性質)だ。これがないと、動きの情報を表現に閉じ込められない。

ケーキ表現の肝は「時間的エンティティ(temporal entity)」——時間をまたいで存在し続ける個々の対象を、別々に追いかけることだ。倉庫番でいえばプレイヤー、一つ一つの箱、壁がそれにあたる。箱はゴールに載ると「解けた箱」に変わり、押されればまた箱に戻る。こうした「誰がいつどこにいて、何に変わったか」を丸ごと表現の中に持つ。似た時空表現は先行研究(Vandara ら)にもあるが、エンティティを個別に追う点がケーキ表現の新しさだと著者は述べる。

この表現の上で動くのが PRP だ。着想はレベルの断片を再帰的に切り貼りする既存手法 BSP(Binary Space Partitioning、空間を二分割しながら既存レベルの断片で埋める方法)にある。PRP はそれを「時間の軸」に沿って行う。入力は二つ——出力の部分指定(あらかじめ決めたい要素。空でもよい)と、元になる複数のレベル(とそのプレイの軌跡)だ。ここから、要素を一つずつ当てはめてレベルと解答を同時に組み上げる。

当てはめには二つの領域知識を使う。一つは選択方針(Selection Policy)で、どのエンティティから埋めるかの順番を決める。倉庫番では最も動くプレイヤーを先に、次に箱、残りをその後にする。もう一つは適合判定(MatchesAt)で、その要素をその時刻・その場所に置けるかを判定する。倉庫番では「プレイヤーは常に一人」「プレイヤー・箱・壁は同じマスに重ならない」「盤外に出ない」の三つを課した。核となるアルゴリズムは領域に依らず、領域ごとに要るのはこの方針と判定、そして前処理・後処理だけである。

発見

倉庫番での比較(論文の Table 1)を見よう。PRP は遊べる率(playability)100%、重複0.00%、タイル多様性50.86%、ユニーク解1.924、ユニーク署名0.534という結果だった。特筆すべきは、倉庫番の動きに関する情報を人手で書き込まずにこれを達成した点だ。動きは表現・選択方針・適合判定から自然に湧いてくる。

比較対象は六つ——Path of Destruction(PoD)、Sturgeon-MKIII、Sturgeon-ST、PCGRL の Turtle と Wide、そして LSTM(記憶ユニットを持つニューラルネット)だ。PoD・Sturgeon 二種も遊べる率100%だが、これは外部の解けるかチェックや制約で遊べることを強制しているからである。強化学習系の PCGRL は86.40%と86.60%、LSTM は73.4%(平均で四分の一以上が遊べない)にとどまる。PRP はそうした外付けの支えなしで最上位に並んだ、と読める。

多様性はどうか。PRP のタイル多様性50.86%は高いが、著者は「高ければ良いとは限らない(高すぎるとノイズの多い面かもしれない)」と釘を刺す。ユニーク解1.924は人間の面2.083に近い(最高は Sturgeon-MKIII の2.138だが、これは8×8と一回り大きい盤なので有利)。ユニーク署名(解を回転・反転で正規化し、箱を押す方向だけに要約した指標)では、どの生成手法も人間の0.917には届かない。PCGRL が最も近いが、著者は報酬関数が長い解へ偏らせた影響かもしれないと慎重に述べる。

部分指定を変えるアブレーション研究(要素を外したり変えたりして効き目を確かめる実験、Table 2)も面白い。指定を空にした「dataset」設定が最も多様(ユニーク解1.924、署名0.534、1000面を約24.8秒で生成)。プレイヤーの通り道を与えた「path」設定はやや落ち(1.347/0.264)、壁で囲う「border」設定は大きく落ちた(0.257/0.094、重複27.60%)。制約を強めるほど多様性は下がるが、その分だけ設計者の制御が効く、という表裏の関係が見える。なお著者は「PRP が既存手法より優れていると主張はしない」「指標が単純な合計値で、元の生成レベルにアクセスできないため統計解析は行わない」と明言している。

使いどころ

もし自分が倉庫番系のパズルを作っているなら、これは即戦力になる。手元の数枚(論文では人手で作った12枚の7×7面)とその解答を食わせれば、遊べることが保証された新しい面を1000枚、約25秒で吐き出せる。しかも解けるかを判定するソルバーを生成ループに組み込む必要も、制約を書き下す必要もない。レベルと解答が同時に生成されるので、生成物は原理的に必ず解ける。

第二に、部分指定による設計者の制御が使える。「このプレイ経路を通る面が欲しい」なら経路を渡す(path 設定)。「必ず壁で囲まれた面がいい」なら壁の枠を渡す(border 設定)。多様性は下がるが、狙った構造や解筋を保証できる。日替わりパズルで難易度や骨格を揃えたい運用や、共作ツール(人と AI が一緒に面を作る道具)との相性が良い。

第三に、後処理を工夫した「難易度つまみ」だ。ケーキ表現は解き終わるまでの全行程を保持している。著者は後処理で普通は最初のスライス(初期状態)を取り出すが、代わりに途中まで解けたスライスを取り出せば、同じ面の「少しやさしい版」を自動で作れると述べる。チュートリアルや段階的な導入面を機械的に量産する発想に繋げられる。

第四に、別ジャンルへの横展開だ。論文は協力ゲーム OvercookedAI と、著者が自作した SkeleWalker(骸骨が犬を骨まで導く倉庫番の変種)でも、1枚の元面から意味のある別の面を生成してみせた。強化学習エージェントの訓練・評価用の環境を作りたいとき、あるいは新しいメカニクスを試作したいとき、選択方針と適合判定を書くだけで最小限の労力で回せる。小規模スタジオの試作にも向く。

限界

まず著者自身が認めている点から。厳密な評価は倉庫番一つに限られ、二つのケーススタディ(OvercookedAI と SkeleWalker)には堅牢な評価がない。統計解析も行っていない(指標が合計値で、比較対象の元レベルにアクセスできないため)。また部分指定を強めるほど「箱のない自明な面」ができて作り直す回数が増える(空指定で約140回、経路で約230回、壁枠で約430回)。手法はプレイの軌跡データと、領域ごとの選択方針・適合判定を必要とする。

ここから先は私(Fukai)が読んで気づいた点だ。PRP は本質的に、既存のプレイ軌跡を組み替えて新しい面を作る。つまり生成される動きの新しさは、元にした面の中にある動きの範囲に縛られる。教材となる12枚の外側にある斬新な仕掛けは、この仕組みからは湧いてこない。元コーパスの質と幅が、そのまま生成物の天井になると読める。

もう一つ、遊べること(playability)は面白さや適切な難しさとは別物だという点を、Fukai はここで指摘しておきたい。この論文は「解ける面が高速に大量に作れる」ことを示すが、それが良いパズルかどうかは人によるプレイテストを経ていない。ユニーク署名が人間の面に届かないのは、生成された面が構造的にやや浅い可能性を示唆する——と、著者が断定していない範囲で慎重に読める。

Fukai の読み

ここは私(Fukai)の解釈だ。私はこの研究を、「表現を先に正す」系譜の PCG の中に位置づけたい。遊べることを後から制約や報酬で貼り付けるのではなく、時間という次元を対象そのものの中に畳み込んでしまう。設計批評の語彙で言えば、これはタイル空間の組み替えではなく解空間(どう解かれるか)の組み替えの自動化に近い。パズルとは結局、解かれる過程のデザインだと考える私には、レベルと解答を一枚のケーキとして同時に扱うこの発想が、正しい抽象の置き所を突いているように読める。

おわりに

もっと深く知りたい人へ地図を渡しておく。まず本論文の評価の土台になったのは Zakaria らの倉庫番向け PCGML(機械学習による自動生成)のサーベイ論文で、比較指標や多くのベースラインはここから来ている。最も近い先行研究は Vandara らの Sturgeon-ST(レベルと解答を時空ブロックとして扱う制約ベースの手法)で、ケーキ表現との違い——エンティティを個別に追うか否か——を対比して読むと理解が深まる。

強化学習でレベルを作る枠組みの原典としては Khalifa らの PCGRL を合わせて読むと、この分野が「遊べること」をどう扱ってきたかの見取り図が得られる。実装を覗きたい人は、著者が公開しているプロジェクトのリポジトリ(倉庫番の元面とケーキ表現が入っている)を辿るのが早い。次に自分の手でパズルを組むとき、この「時間を畳んだ表現」という発想は、きっと道具箱の一つになる。

参考文献

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

・Representing and Generating Levels Over Time through Playtrace Reconstructive Partitioning (Halina & Guzdial, 2026, arXiv:2607.12097 / FDG '26, DOI: 10.1145/3815598.3815619)

・プロジェクトのリポジトリ (emily-halina/PRP-Sokoban、倉庫番の元面とケーキ表現)

・関連研究: PCGRL: Procedural Content Generation via Reinforcement Learning (Khalifa et al., 2020) / Zakaria et al. の倉庫番向け PCGML サーベイ (2022)、Vandara et al. の Sturgeon-ST (2025)