Zeytuncu: パズルの難しさは『使う数の個数』で決まる — Fukai が読む

一段落要約

数を組み合わせて目標の数を作る「ナンバーズ系」のパズル(英国のテレビ番組 Countdown の数字ラウンドや、フランスの『Le compte est bon』が有名)。この論文は、そうしたパズルの『難しさ』がどこから来るのかを、人のプレイ記録からではなく、パズルそのものの構造から説明しようとした。著者は四則演算で目標数に到達できるかを厳密に解く専用ソルバーを作り、約 347 万個の問題例を生成して、その難易度を『最小手数(目標に届くまでに必要な演算の最小回数)』で定義した。

中心的な発見は明快だ。最小解で実際に使われる入力数(手元の数のうち何個を使うか)という、たった一つの構造的な量だけで、この定義のもとでの難易度がぴたりと決まる、というものだ。表面的な統計(数の大きさや目標値)を使った機械学習では『易しい問題』を取りこぼすのに対し、この『使う数の個数』を加えると分類が完璧になる。著者はこれを『難易度の最小十分統計量(言い当てるのに必要十分で、これ以上削れない手がかり)』と呼ぶ。本記事は、この一本を論文を開かずに要点が掴めるように解説する。

はじめに

著者は Yunus E. Zeytuncu(ミシガン大学ディアボーン校)。この論文は arXiv に preprint(査読前の原稿)として公開されている(2026 年 3 月投稿)が、教育分野の AI を扱う国際会議 AIED 2026(Artificial Intelligence in Education、教育における人工知能)に採択済みと本文に明記されている。つまり査読を通った研究だ。ただし本記事で参照したのは arXiv の preprint 版である点は断っておく。

なぜ今日この論文を選んだか。私は毎朝 arXiv の新着を眺めているが、『難易度を測る』という話題はパズルを作る人にとって永遠のテーマでありながら、たいていはプレイヤーのクリア率や離脱率といった『結果のデータ』から後付けで推定される。この論文は逆に、問題そのものの中身から難易度を説明しようとしている。しかも対象が、誰でも一度は触れたことのある『数字を組み合わせて目標を作る』パズルだ。実装に近く、すぐ持ち帰れると感じたので選んだ。

背景

適応学習システム(学習者の習熟度に合わせて出す課題を変える仕組み)では、課題の難易度をどう決めるかが要になる。易しすぎる課題は学びが薄く、難しすぎる課題は意欲をくじく。これはパズルゲームの難易度設計とまったく同じ悩みだ。ちょうどよい歯ごたえを、どうやって事前に見積もるか。

ただ、これまでの多くの手法では、難易度は『正答率や解答時間といった成績データから推定するラベル』として扱われてきた。つまり人がたくさん遊んだ後でないと難易度が分からず、しかも『なぜその課題が難しいのか』は説明できないままだった。著者が問うのは、成績を見る前に、問題の構造そのものから難易度を定義できないか、という点である。これが分かれば、新作の問題でもプレイ前に難易度の見当がつく。

アプローチ / 方法

著者が扱うパズルは『4OPS』と名づけられている(four operations、四則演算の意)。手元にある複数の正の整数と、一つの目標数が与えられ、足す・引く・掛ける・割るの四則だけで目標を作れるかを問う。整数しか許さない制約がある。各数は一度しか使えない、途中の計算結果は常に正の整数、引き算で負になってはいけない、割り算は割り切れる場合だけ。そして手元の数を全部使う必要はない(一部だけ使ってよい)。著者はこの『一部だけ使ってよい』形式を採ることで、より細かい構造の違いを取り出せると述べている。

まず著者は、目標に到達できるかを厳密に解く専用ソルバーを作った。これは闇雲な総当たりではなく、動的計画法(一度計算した部分問題の答えを覚えておき、組み合わせて全体を解く手法)で、到達できる値とその『最小手数』を記録する。さらに『最小の手で目標を作る式』の中身、つまりどの数を実際に使ったかという『証拠(witness、最小解の構成そのもの)』まで復元する。ここが後の発見の鍵になる。

次にデータセットを作る。手元の数は六つ。1〜9 の一桁の数を五つ(重複可)と、25・50・75 のうち一つ。これはテレビ番組 Countdown の数字ラウンドとほぼ同じ構成だ。重複を除くと 3,861 通りの組があり、目標は 100〜999 の三桁すべて。掛け合わせると 3,474,900 個の問題例になる。各例にソルバーで正確なラベル(解けるか/最小手数/構造的特徴)を付けた。難易度は最小手数で区切り、易しい(0〜2 手)・中(3〜4 手)・難(5 手)・解けない、の四段階とした。

発見

まず全体像。約 87% の問題は解ける。難易度の分布は偏っていて、易しい問題(0〜2 手)は比較的まれで、中(3〜4 手)と難(5 手)が大半を占める。短い手数で目標に届く組み合わせは、実は珍しいということだ。

では表面的な特徴(手元の数や目標値から作る統計)だけを使った機械学習はどうか。解けるかどうかの予測では、ロジスティック回帰(単純な線形の分類手法)で約 90% の精度が出た。ところが難易度の分類は格段に難しく、勾配ブースティング(弱い予測器を少しずつ足して強くする手法)でも約 73% にとどまり、とくに『易しい問題』をことごとく取りこぼした。著者は、易しさは表面の統計では捉えられず、解の作られ方という細部に依存すると整理している。

そこで、最小解の『証拠』から構造的な特徴を取り出す。使った数の個数、使った演算の種類、途中の数の大きさ、最小解が何通りあるか、などだ。これらを加えると難易度分類は劇的に改善し、ソルバーが定義した難易度ラベルに対して完璧な精度に達したと著者は報告している。

そして決定打。アブレーション分析(設計のどの部分が効いているかを、要素を一つずつ外して確かめる実験)の結果、最小解で使う数の個数(著者は minimal input usage と呼ぶ)、ただ一つを加えるだけで、すべての難易度クラスを完璧に言い当てられた。他の特徴を足しても改善しない。著者はこれを『この定義のもとでの難易度の最小十分統計量』と呼ぶ。構造的に言えば、易しい問題は少ない数で解け、難しい問題はほとんど全部の数を組み合わせる必要がある、ということだ。

使いどころ

パズルを作る人にとっての一つ目の使い道は、難易度ラベルの自動付与だ。もし私がナンバーズ系のパズル(与えられた数で目標を作る形式)を量産しているなら、生成した各問題に対してソルバーを一度だけ走らせ、『最小解が何個の数を使うか』を記録しておく。これだけで、プレイヤーに遊んでもらう前に易しい・中・難のラベルが付く。クリア率データが貯まるのを待つ必要がない。

二つ目は、難易度の『並べ方』だ。著者は、使う数の個数が増える順に問題を並べれば、説明可能で筋の通った難易度進行になる、と述べている。チュートリアルから本編への橋渡しや、デイリーパズルを曜日ごとに少しずつ重くする設計に、そのまま使える指標だ。『なぜこの順なのか』を作り手自身が説明できるのが効いてくる。

三つ目は、生成側の制御だ。もし私がハイパーカジュアルのパズルで PCG(Procedural Content Generation、コンテンツの自動生成)を回しているなら、『2 個の数で解ける問題』を狙って易しい面を作り、『5 個全部必要な問題』を狙って歯ごたえのある面を作る、という逆引きができる。難易度を後から測るのではなく、最初から狙って出せるわけだ。

加えて、応用範囲はナンバーズ系に限らないと私は読む。『最小解が何要素を同時に組み合わせる必要があるか』という発想は、Sokoban-like(倉庫番のように箱を押して並べるパズル)で『正解手順が何個の独立した気づきを要するか』や、配線・経路パズルで『解が何本の経路を同時に成立させるか』といった構造量に翻訳できる。手数の長さではなく、同時に協調させる要素の数で難しさを測る、という見方だ。

限界

まず著者自身が認めている弱点。今回の難易度は『ソルバーが定義した最小手数』に基づくものであり、人間が実際に感じる難しさとの一致は今後の課題だと明記している。使う数の個数は構造的な必要量を捉えるが、計算の流暢さ・戦略の慣れ・気分といった、人の成績を左右する要因は説明しない。結果はこの整数四則パズルという枠組みの中での話に限られる、とも断っている。

Fukai がここで指摘するのは、『完璧な精度』『最小十分統計量』という強い言葉の受け止め方だ。難易度は最小手数で定義され、使う数の個数も同じ最小解(witness)から取り出された量である。つまり両者は同じ構造の別の見方に近く、片方からもう片方をほぼ言い当てられるのは、ある程度まで定義上の必然でもあると読める。これは欠陥ではないが、『人が感じる難しさを言い当てた』のではなく、『ソルバー上の難易度定義が、たった一つの構造量に集約できる』という話だと受け取るのが正確だろう。

もう一点。被引用数はまだほとんど付いておらず、新しい preprint であり広く議論されていない段階だ。データセットやコードの公開状況も本文だけからは詳細に確認できなかった(著者は元になったパズルを無料のモバイルアプリとして公開済みとは述べている)。ナンバーズ系という特定の形式に閉じている点も含め、他のパズルへ一般化する際は自分の題材で検証し直す必要がある。

Fukai の読み

ここからは私の解釈だ。私はこの研究を、『難易度を結果から測る』時代から『難易度を構造から設計する』時代への、小さいが象徴的な一歩として位置づけたい。設計批評の語彙で言えば、レベルデザインにおける『難しさ』を、プレイテストの統計から、解の構造そのものへ引き戻す試みだ。私たちは長らく、難しさを『プレイヤーがどれだけ詰まったか』で語ってきた。だがこの論文は、少なくともある種のパズルでは、難しさが『いくつの要素を同時に手の中で回す必要があるか』という認知的負荷(同時に保持・操作しなければならない情報の量)に還元できることを、計算で裏づけて見せた。これは私の読みだが、ワーキングメモリ(短時間だけ情報を保持しながら操作する記憶の働き)の負荷という古い心理学の概念を、パズルの構造側から定量化する橋になりうる、と受け取った。

おわりに

もっと深く知りたい人へ。難易度を『プレイヤーのデータから』推定する正攻法を見たいなら、モバイルパズルの難易度モデリングを扱った実証研究(Difficulty Modelling in Mobile Puzzle Games、2024)が対になる地図を見せてくれる。本論文が『構造から』攻めるのに対し、あちらは『結果から』攻める。両方を並べると、難易度という掴みづらい対象を二方向から挟み撃ちにする構図が見えてくる。

また、解の最小手数という考え方に興味が湧いたら、四則演算式の計算複雑性を扱った理論寄りの論文(括弧のあり/なしで到達できる数がどう変わるか、2021)も、この分野が踏まえている土台として目を通すとよい。本論文が『実装と教育応用』に寄っているぶん、理論側の地図と合わせると立体的に見えてくる。

参考文献

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

・4OPS: Structural Difficulty Modeling in Integer Arithmetic Puzzles (Yunus E. Zeytuncu, 2026, arXiv:2603.25356 preprint / AIED 2026 採択)

・関連研究: Difficulty Modelling in Mobile Puzzle Games (2024, arXiv:2401.17436)

・関連研究: The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses (2021, arXiv:2110.14045)