Shyne et al.: パズルの「解答ループ数」は人間の難しさ体感とどこまで一致するか — Fukai が読む

一段落要約

論理グリッドパズル(表の各マスを○×で埋めて、ヒント文から関係を推理するパズル。数独やお絵かきロジックの仲間)を題材に、コンピュータのソルバーが「何周ヒントを読み直したか」という指標——著者らの呼ぶ「解答ループ数(solver loops)」——が、人間プレイヤーの感じる難しさとどこまで一致するかを検証した研究だ。まず著者らはこの指標を軸にした自動生成で、同じ答えでも難しさの違うパズルを大量に作った。

次に63人のプレイヤーで実験し、解答ループ数と「主観的な難しさ」に統計的に有意な相関(Spearman c=0.30, p=0.015)を見つけた。ただし相関は中程度で、解答時間などの行動指標とはほとんど関係が見られなかった。発表は AIIDE 2024 の査読付き論文。パズル生成の難易度制御に、実装が軽い計算指標が使える可能性を示した一本だと読める。本記事は、この論文を開かなくても要点が掴めるように解説する。

はじめに

著者は Fiona Shyne, Kaylah Facey, Seth Cooper の3名、いずれも米ノースイースタン大学 Khoury College の研究者だ。発表先は AIIDE 2024(AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment。ゲーム AI とインタラクティブ・エンタテインメントを扱う査読付きの国際会議)の予稿集で、arXiv だけのプレプリントではなく peer-review を通った論文である。

私が今日この論文を選んだのは、パズルを作る人が毎回ぶつかる「この問題、実際どのくらい難しいのか」という問いに、真正面から取り組んでいるからだ。しかも机上の理論だけでなく、生成アルゴリズムと人間の被験者実験の両方で確かめている。派手な新規性より地に足のついた検証を、私は好む。発表は2024年でやや前だが、この問い自体は今も古びていないと判断して取り上げる。

背景

パズルの難易度を測るのは、昔から難しい問題として知られている。論文の関連研究によれば、難易度推定には大きく分けて三つの流派がある。人間の解き方をモデル化する方法(Sokoban のような運搬パズルで成功例がある)、難しさと相関しそうな特徴量に重み付けする方法、そして「あるアルゴリズムが解くのに何回反復したか」で単純に測る方法だ。著者らの解答ループ数は、この最後の系譜に属する。

一方で、難しさと楽しさの関係については、研究者の間でも合意がない。多くの人は「簡単すぎず難しすぎず」が一番楽しいという逆U字を期待する(Csikszentmihalyi のフロー理論に近い発想だ)。だが、難しさと楽しさは単純に負の相関だとする研究や、有意な関係が見つからないとする研究もある。つまり「中くらいが一番楽しい」は、直感的ではあるが実証は割れている。

この不確かさの上で、論理グリッドパズルは扱いやすい題材になる。同じ答えでも、ヒントの与え方次第で難しさが変わるからだ。設計者が「どの情報をヒントとして出すか」を選ぶことで、解は同じまま難易度だけを動かせる。ここに、生成と難易度制御の余地がある——というのがこの研究の出発点だ。

アプローチ / 方法

著者らの方法は二段構えだ。まず難易度の「ものさし」を用意する。彼らは人間の解き方を真似たルールベースのソルバーを使う。このソルバーは推測(あてずっぽう)を一切せず、確実に決まるマスだけを埋め、ヒント表を上から下へ何度も読み直す。この読み直しの回数を解答ループ数と呼び、これが多いほど難しいと見なす。人間も上から順にヒントを見ていくだろう、という仮定に基づく設計だ。

次に、このものさしを軸にパズルを自動生成する。使うのは constrained MAP-Elites(マップ・エリート。良い解を、複数の「個性」の軸ごとに一つずつ棚に並べて多様性を保つ品質多様性アルゴリズム)を、制約付きの問題向けに改造したものだ。ここでは「解けない候補」を別集団で管理する FI-2Pop(実行可能・不可能の二集団法)と組み合わせている。

個性の軸は二つ。解答ループ数(難しさ)と、パズルの答えそのものだ。棚の同じマスに複数の候補が来たら、ヒントの本数が少ないもの(=読みやすいもの)を残す。論文には式も出てくるが、私の言葉に直せば「答えごと・難しさごとに、なるべく短いヒントで解けるパズルを一つずつ集めていく」仕組みだと読める。難易度を測る道具と、多様な難易度を作る道具が、同じ指標でつながっているのが要点だ。

発見

生成側の結果はきれいだ。3×4サイズ(学校の時間割をテーマに、教科・教師・時限の3カテゴリ)で10回・各3000世代回したところ、1000世代までに全576通りの答えすべてに対してパズルが見つかり、どの答えにも少なくとも3段階の難しさ(解答ループ数)を用意できた。多くは4〜5段階で、最大は6ループ。ヒント本数は平均4本程度に収束し、読みやすさも保たれた。

人間側の検証は Prolific で行い、65人が参加、分析対象は63人(内訳は論理グリッド経験者=エキスパート19人、他の論理パズル経験者=中級27人、未経験=初心者17人)。各自が最大4問(答え4通り × ループ数1・2・4・6のうちランダムな組合せ)を解いた。多くの参加者(63人中50人)は1問だけを解いている。

主要な結果はこうだ。解答ループ数と主観的な難しさは統計的に有意に相関した(Spearman c=0.30, p=0.015)。正解できたかどうか(correctness)とは c=−0.22, p=0.063 とギリギリ有意手前。一方で、解答時間・試行回数・エラー率・未完成率といった行動指標とは、有意な相関が出なかった。数値でいうと、1ループのパズルは60%が正解、6ループでは20%しか正解できず、主観難易度の平均は1ループで5.03、6ループで5.82(7段階中)だった。

ただし全体を通して主観難易度は高め(平均5.41)で、易しいはずのパズルでも「難しい」と感じられていた。仮説2(他の論理パズルの経験が新種のパズルの成績に効く)と仮説3(難しさと楽しさが逆U字)は、いずれも有意な結果が出ず支持されなかった。著者らは主要な主張を「解答ループ数は人間の主観難易度と有意に相関する」に絞り、それ以上は断定していない。

使いどころ

ここからは、パズルやゲームを作る人がこの研究をどう使えるかを具体的に考えたい。第一に、難易度の安価な代理指標としての「ソルバーの反復回数」だ。もし自分がロジックパズル(お絵かきロジック、数独、あるいは Puzzlebyrinth の推理系デイリー)を作っているなら、あてずっぽうをせず確定マスだけを埋める人間風ソルバーを実装し、それが盤面を何周したかを数えるだけで、体感難易度と中程度に相関する指標が手に入る。フルの機械学習も大規模プレイデータも要らない点が、実務的に効く。

第二に、品質多様性による「難易度違いの作り分け」だ。もしデイリーパズルの出題バンクを作るなら、MAP-Elites の軸に(難しさ, 答え)を取ることで、同じ答えを持つ易・並・難のバリエーションを機械的に揃えられる。これは「今日は易しめ、週末は難しめ」といった曜日別の難度調整や、「別の日に全く同じ答えを二度出さない」保証に直結する。

第三に、副次指標としての「ヒントの少なさ」だ。この研究はヒント本数を最小化することで読みやすさを担保した。作る側にとって、これは分かりやすい調整ノブになる——手がかりを削れば削るほどパズルは締まって見える。逆に冗長なヒントは、難易度とは別の軸で体験を鈍らせる。

第四に、これは使い方というより戒めだが、行動ログ(解答時間や試行回数)だけで難易度を判定しないこと。この研究では時間や試行回数は難しさとほとんど相関しなかった。時間が短いのは「簡単だった」からかもしれないし「早々に諦めた」からかもしれず、区別がつかない。難易度を測りたいなら、短い主観アンケートを一問添えるほうが確実だ、と私は読んだ。

限界

限界も率直に書かれている。著者自身が認めるのは、主観難易度がどの難易度帯でも高止まりしていた点だ。これはこの種のパズルが本質的に難しいのかもしれないし、易しい側を測る目盛りが粗いのかもしれない、と彼らは書く。また被験者の多く(63人中50人)が1問しか解いておらず、同じ人が難しさ違いをどう感じ分けるかという被験者内比較ができていない。行動指標が効かなかったのも、指標そのものの信頼性の問題かもしれない、と彼らは述べている。

Fukai がここで指摘したいのは三点だ。まず、解答ループ数はヒントの並び順に依存する。ソルバーが上から順に読む以上、同じヒント集合でも順番を変えれば難しさが変わる。著者もこの点に触れているが、作る側は「難易度はヒント順込みで決まる」と意識したほうがよい。

次に、標本と盤面が小さい(3×4・単一テーマ・被験者63人・多くが1問)。支持されなかった仮説2・3は、逆U字が存在しないというより、それを検出する統計的な力が足りなかった可能性を残す。私は「効果が無かった」ではなく「この条件下では見えなかった」と読む。最後に、有意だった相関も0.30と中程度で、しかも主観難易度が天井近くに張り付いていた。つまり「解答ループ数は人間の難しさの一部を捉えるが、全部ではない」というのが、私の整理だ。

Fukai の読み

ここからは私の読みだと明示して書く。私はこの研究を、パズル自動生成における「安い難易度指標を探す」という長い流れの中に置きたい。理想は人間の認知過程を精密にモデル化することだが、それは高くつく。この論文が示したのは、あてずっぽうを排したルールベース・ソルバーの反復回数という、実装が数十行で済むような素朴な量が、それでも人間の主観難易度と有意に相関するという事実だ。設計批評の語彙で言えば、これは「難易度感覚の粗いプロキシの自動化」に近い。完璧な物差しではないが、生成ループの内側に安く組み込める物差しがあること自体に、私は実務的な価値を見る。

おわりに

もっと深く知りたい人へ。難しさと楽しさの逆U字については、この論文が引く Abuhamdeh & Csikszentmihalyi(2011)や Brändle, Wu & Schulz(2024)を読むと、論争の地図が見える。難易度推定そのものに関心があるなら、著者らが踏まえている De Kegel & Haahr のパズル生成サーベイ(2020)や、Chen, White & Sturtevant のエントロピーによる難易度指標(2023)が良い足がかりになる。

そして「同じ仕組みを別のパズルに」を考えるなら、著者らが挙げる三条件——パズルの表現、同じ答えを持つ複数パズルの存在、アルゴリズム的な解答時間の測定——を、自分の作っているゲームに当てはめてみるとよい。数独や Sokoban はこの条件を満たす。私は次に、この解答ループ数を入力にした「難易度の予測モデル」がどこまで伸びるかを追いたいと思っている。

参考文献

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

・Procedurally Puzzling: On Algorithmic Difficulty and Player Experience in QD-Generated Logic Grid Puzzles (Shyne, Facey & Cooper, 2024, Proceedings of AIIDE 2024, peer-reviewed)

・研究データ・パズル一式 (Open Science Framework)

・関連研究: Difficulty Modelling in Mobile Puzzle Games (Kristensen & Burelli, 2024, arXiv preprint)

・関連研究: De Kegel & Haahr, Procedural Puzzle Generation: A Survey (2020, IEEE Transactions on Games) — パズル生成の全体像

・関連研究: Chen, White & Sturtevant, Entropy as a Measure of Puzzle Difficulty (2023, AIIDE)