McConnell & Zhao: 遺伝的アルゴリズムで「ちょうどいい難しさ」のパズルをリアルタイム生成する — Fukai が読む

一段落要約

私が今日選んだのは、遺伝的アルゴリズムでパズルを「その場で」作り、プレイヤー一人ひとりに難しさを合わせる試みを report した論文だ。題材は Cosmic Express によく似た、一筆書きで荷物を運ぶ経路パズルである。著者らは、プレイヤーの解き方(かかった時間・やり直し・あと一歩で解けた回数など)を記録して次の難易度を決め、その難易度に合うパズルを遺伝的アルゴリズム(生物の進化をまねて良い解を少しずつ探す手法)で1問あたり約7秒で生成する仕組みを作った。

18人の小規模な実験では、時間だけを手がかりにする版が明確に見劣りし、複数の指標を使う版のほうが「難易度がちょうどいい」「進んでいる感覚がある」という評価で高かった。リアルタイム生成と適応的な難易度調整を素直につないだ、実装寄りの一本だ。この記事だけで、何をどう作り、何が分かったのかが掴めるように書く。

はじめに

論文は Matthew McConnell と Richard Zhao(カナダ・カルガリー大学コンピュータサイエンス学科)による「From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm」。本記事の出典は arXiv に2025年9月に公開されたプレプリント(arXiv:2509.23796)である。原稿には AAAI(人工知能の学会)の著作権表記と匿名査読者への謝辞があり、AAAI 系の発表に向けて準備・採択されたものと読めるが、私は確認できた範囲で arXiv 版を出典として扱う。

私がこれを選んだのは、Puzzlebyrinth で扱う題材ど真ん中だからだ。経路パズルの自動生成、難易度の数値化、プレイヤーモデリング(プレイの記録から「この人は今どれくらいの腕前か」を推定すること)、そして動的難易度調整(プレイ中に難しさを上げ下げする仕組み。DDA = Dynamic Difficulty Adjustment)。これらが一つの遊べるシステムに収まっていて、しかもアルゴリズムの擬似コードまで載っている。ゲームを作る人がそのまま参考にできる粒度なのが嬉しい。

1点だけ先に断っておく。これは被引用がまだほとんど無い新しめのプレプリントで、本実験も参加者18人のパイロット(予備的)スタディだ。だから「証明された」と言える結果は少ない。私は数値を原文通りに引きつつ、どこまでが言えてどこからが言えないかを最後にきちんと分ける。

背景

難易度を一人ひとりに合わせる、という発想自体は新しくない。ゲームでも教育でも「易しすぎれば退屈、難しすぎれば挫折、その間に没入(フロー)がある」という考え方が長く使われてきた。著者らも、個別指導が学習に極めて効果的だという古典的な知見(Bloom が1984年に示した、個別指導を受けた平均的な生徒が通常授業の平均より2標準偏差上にくるという話)を出発点に置いている。

では何が足りなかったか。著者らの整理では、既存の適応学習システムの多くは「オフライン」で動く。つまり後からデータを分析して次回に活かす形で、プレイの最中にその場で内容を作り替えるものは少ない。さらに、適応の手がかりとして最も広く使われてきたのが time-on-task(課題にかけた時間)だが、それ単独でどこまで有効かはあまり検証されてこなかった、という。

そこで本研究は、(1) リアルタイムにオンラインで難易度を調整するシステムを、非適応の基準と比べられる形で作り、(2) 時間という単一指標を切り出して、その有効性そのものを問う、という二点に踏み込む。生成の中心には PCG(Procedural Content Generation、コンテンツの自動生成)の代表的手法である遺伝的アルゴリズムを置いている。

アプローチ

まず遊びそのもの。著者らは Unity で APSG(Adaptive Problem-Solving Game)を作った。題材は Cosmic Express(Hazelden, Davis, Tyu, 2017)に倣った経路パズルだ。n×nのマス目の上で、スタートからゴールまで一本の(枝分かれのない)道を引く。道に沿って「コンテナ」が1マスずつ進み、荷物を一度に1つだけ運べる。指定の積み込み地点で荷物を拾い、指定の降ろし地点で降ろす。道は交差できず、順番を考えて引かないと解けない。難しさは主に、グリッドの大きさ・積み降ろし地点の数・特殊マスの配置で決まる。

そのパズルを毎回その場で作るのが遺伝的アルゴリズムだ。仕組みを言葉で言えばこうなる。まずパズル候補の集団を用意し、それぞれに「どれくらい狙った難易度に近いか」という点数(適応度=fitness)をつける。点数の高いものを親に選び、二つを掛け合わせ(交叉=crossover)、少しランダムに変異(mutation)させて子を作る。これを世代を重ねて繰り返すと、狙った難易度のパズルへ少しずつ寄っていく。著者らはこの骨格に Scirea(2020)の NSFI-2POP という構造を下敷きにしている。

交叉には工夫がある。パズルは文字の二次元マップ(# 空き、X 道、P 積込、D 降ろし、S 開始、E 終了 など)で表される。ランダムに選んだ列で二つの親を左右に切って入れ替えると、たいてい道が途切れる。そこを BFS(幅優先探索。近いマスから順に探して最短のつなぎ方を見つける方法)で埋め直し、積み降ろし地点は道を区切った各区間に距離ベースで置き直す。最後に解けるかどうかを必ず検証する。生成が壊れた解を吐かないよう、修復を組み込んでいるわけだ。

適応度は「どの難しさを狙うか」で動く。著者らは経路長(8〜50)、曲がり角(0〜20)、空きマス、積込数(1〜12)、直交する積込などの要素ごとに目標値を決め、難易度1〜10に応じて目標を補間する。点数は要素ごとに「目標にどれだけ近いか」を重み付きで足し合わせる(数式は使わないが、要は目標から外れるほど減点する形だ)。

では狙う難易度は誰が決めるのか。プレイヤーモデルだ。システムはプレイヤーの状態を見て「上げる/下げる/そのまま」を次のパズルに提案する。材料は、解くまでの時間・試行回数・バックトラック(引いた道の一部を消してやり直した回数)・リセット回数・あと一歩(特殊地点の取りこぼしが25%未満)で惜しかった回数。面白いのは、試行回数を「ハード制約」(必ず満たすべき安全弁。失敗が多い間は難易度を上げない)とし、残りを「ソフト制約」として重み付きで点数化し、上げ下げの度合いを滑らかに決める点だ。

実験で使ったパラメータは集団サイズ300、交叉率80%、世代数の上限10、最大グリッド10×10。この設定で、どの難易度のパズルもおよそ7秒で生成できたという。集団や世代やグリッドを増やせばもっと大型で複雑なパズルも作れるが、その分だけ生成時間が大きく延びる、と著者らは率直に書いている。

発見

実験は参加者18人。各人が APSG の3つの版を遊んだ。Standard(全部のプレイヤーモデル指標を使う版)、Increasing(成績に関係なく難易度を1ずつ上げる版)、Time-based(時間だけを指標に使う版)である。提示順は人によって入れ替え、慣れによる偏りを抑えている。全体としては好意的で、89%が「知的に刺激された」、94.5%が「問題解決の力を使った」、72.2%が「批判的思考を要した」と答えた(いずれも同意/強く同意)。

肝心の比較を、原文の数値で引く。「フラストレーションが減った」(1〜10、高いほど良い)は Standard 6.47、Increasing 6.94、Time-based 6.83で、分散分析(ANOVA。複数グループの平均差を調べる検定)では有意差なし(F(2,51)=0.072, p=0.93)。一方「難易度がちょうど良かった」は Standard 6.06、Increasing 5.67、Time-based 4.44で差があり(p=0.039)、Standard と Time-based の差は明確だった(p=0.004、効果量 Cohen's d=0.869。効果量とは差の大きさの目安)。

「難易度の変化を感じた」は Standard 8.17、Increasing 7.56、Time-based 6.89(有意差なし、p=0.149)。「進んでいる感覚があった」は Standard 8.56、Increasing 7.5、Time-based 6.0で、ここははっきり差が出た(p=0.005、Standard 対 Time-based は p<0.001、d=1.083)。ログのデータでも、Standard と Increasing は平均難易度がほぼ同じ(5.53 と 5.50)なのに対し、Time-based は3.87と低く、ベンチマークより平均25.67秒も速く解けてしまっていた。難易度を十分に上げ切れていなかった、という解釈だ。

まとめると、複数の指標を使う版が体感の指標で総じて高く、時間だけの版は「易しいまま留まりやすい」という弱さを見せた。著者らはこれを根拠に、Standard 型を今後の中核として磨く方向を示している。ただし Standard と Increasing の差の多くは統計的に有意でない点も、著者ら自身が明記している。

使いどころ

ゲームやパズルを作る人にとっての実用を、具体的に挙げてみる。まず、もし自分が Cosmic Express や倉庫番(Sokoban)系の経路パズルを作っているなら、この論文の適応度関数はそのまま難易度のつまみになる。経路長・曲がり角・空きマス・積込数・直交する積込といった「測れる量」に目標値を設定し、それに合わせて生成する。難しさを言葉でなく数で握れるので、レベル帯ごとの量産がやりやすくなる。

次に、もしハイパーカジュアルの PCG を組むなら、プレイヤーモデルの「時間だけに頼らない」という教訓が効く。本論文ではバックトラック・リセット・あと一歩の回数を併用しており、時間単独版の弱さも実測している。離脱しやすいカジュアル層ほど、複数の行動シグナルで詰まりを早く検知し、次の1問の難易度を微調整する価値がある。

三つ目に、もし生成パズルの「壊れ」に悩んでいるなら、交叉のあとに BFS で道を修復し、最後に必ず解けるか検証する設計はそのまま盗める。GA に限らず、合成して壊れた候補を捨てるのではなく直す、という発想は制約の強いパズル全般で有効だ。さらに四つ目として、著者らが将来の応用に挙げるように、これは論理パズルや算数ドリル、学習障害のある学習者向けの練習問題の難易度調整にも展開しうる。ゲームの外、教育の現場が射程に入る。

限界

まず著者ら自身が認めている弱点。参加者は18人と少なく、結果はパイロット段階のものだ。決定的に重要なのは、完全な非適応版(静的なベースライン)との比較が無いことで、これがないと「フラストレーションをどれだけ減らせたか」を厳密には言えないと著者らは書いている。時間指標も単独で切り出して評価しただけで、他の指標を一つずつ外して効くものを見極める ablation study(設計のどの部分が効いているかを、要素を一つずつ外して検証する実験)は今後の課題に回している。閾値もグループ単位で決めており、個人差は捨象されている。

ここから先は Fukai が読んで気づいた点だ。第一に、生成に約7秒という時間は、それが同期的に走るならテンポを切る恐れがある。本論文はそこを問題視していないが、商用パズルの「サクサク次へ」という気持ちよさとは緊張関係がある。第二に、Standard と Increasing の差の多くは有意でない(参加者18人では検出力が足りない)。だから「Standard が最良」は示唆であって証明ではない、と私は読む。

第三に、私がいちばん気になるのは、適応度が測っているのは経路長や曲がり角といった「難しさの代理指標」であって、人が感じる認知的な難しさそのものではない、という点だ。代理指標と体感はずれうる。実際この実験でも、解き手応えと客観難易度は必ずしも一直線に並んでいない。最後に、題材の Cosmic Express は商用ゲームであり、「に倣った」再現には権利面の配慮が要る——これは論文の主張とは別の、実装者向けの注意である。

Fukai の読み

ここだけは私の解釈だと断って書く。私はこの研究を、PCG の重心が「とにかく多様に作る」から「一人の目の前のプレイヤーに合わせて作る」へ移っていく流れの中に位置づけたい。設計批評の語彙で言えば、これはレベルデザイナーが暗黙にやってきた「相手を見て次の一手を出す」という調整の自動化に近い。面白いのは、その自動化が高度な機械学習ではなく、遺伝的アルゴリズムと手で書いた制約という、枯れて読みやすい道具で組まれていることだ。再現しやすさという点で、私はむしろこの素朴さを買いたいと読んだ。

おわりに

もっと深く知りたい人へ、地図になりそうな線を一本引いておく。本論文の遺伝的アルゴリズムは Scirea(2020)の「計算論的思考のための適応的パズル生成」を下敷きにしているので、生成側を掘るならまずそこへ。PCG 全般の見取り図がほしければ、Shaker・Togelius・Nelson の『Procedural Content Generation in Games』が定番だ。プレイヤーモデリングと DDA に関心があるなら、本論文の参考文献にある DDA レビュー(Lopes & Lopes, 2022)から関連研究の枝をたどると、この一本がどの位置に立っているかが見えてくる。次は私自身、代理指標と体感のずれを正面から測った研究を探して読んでみたい。

繰り返すが、これは18人のパイロットスタディに基づくプレイプレプリントで、まだ広く議論されてはいない段階だ。だからこそ、結論を急がず「何が言えて何が言えないか」を持ち帰るのに向いた一本だと思う。私は今朝もホットの濃いめのコーヒーを片手に、紙に刷ったこの PDF へ色ペンで線を引きながら読んだ。

参考文献

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

・From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm (McConnell & Zhao, 2025, arXiv preprint 2509.23796)

・同論文 HTML 版(本文・図・アルゴリズム擬似コードを確認)

・関連研究: Scirea, M. (2020) "Adaptive puzzle generation for computational thinking"(本論文の遺伝的アルゴリズム構造 NSFI-2POP の下敷き)

・関連研究: Shaker, Togelius & Nelson (2016) "Procedural Content Generation in Games"(PCG の定番文献)

・関連研究: Lopes & Lopes (2022) "A review of dynamic difficulty adjustment methods for serious games"(DDA のレビュー)

・題材ゲーム: Cosmic Express (Hazelden, Davis & Tyu, 2017)