Wang et al.: パズルのソルバーを一手ごとの先生にする — Fukai が読む

一段落要約

言語モデルに Sokoban(倉庫番)や Minesweeper(マインスイーパ)のようなパズルを何十手も解かせて学習させるとき、最後に「解けた/解けなかった」の一点だけを報酬にすると、途中のどの一手が効いたのかが伝わらない。この論文は、そのパズルを解くための専用ソルバー(探索アルゴリズム)を先生役として横に置き、一手ごとに「今の手でゴールまでの残り手数がいくつ減ったか」を計算して学習信号に混ぜる、という手法 CAST を提案する。

著者らは Sokoban・Minesweeper・Rush Hour(車をずらして脱出させるスライドパズル)の三種で、学習に使った難易度でも、学習していない一段上の難易度でも、比較した学習手法すべてを上回ったと報告している。三種平均の成功率は、素の 4B モデルの 16.6% から 62.1% へ、未学習難易度では 5.9% から 28.4% へ上がった(論文 Table 1)。

面白いのは副作用のほうだ。ソルバーへの問い合わせコストは学習1ステップの実時間の 100 万分の 73 程度しかなく(Figure 6)、しかも厳密なソルバーの代わりに学習させた評価ネットワークでもおおむね同じ効果が出た(Figure 5)。「正解の手」ではなく「残り手数という一つの数値」だけで先生役が務まる、という点が本論文の核だと読める。

はじめに

今日読んだのは arXiv:2607.25308、題は「CAST: Game Solvers as Turn-Level Teachers for LLM Agents」。著者は Yu Wang と Yi-Kai Zhang(この二人が同等貢献)を筆頭に、Wentao Shi、Ziang Ye、Yuchun Miao、Yueqing Sun、Qi Gu、Xunliang Cai、Lan-Zhe Guo、Han-Jia Ye、Fuli Feng の 11 名。所属は中国科学技術大学・南京大学・武漢大学・美団(Meituan)である。2026 年 7 月 28 日投稿、分類は cs.CL と cs.AI。

arXiv の書誌欄には会議名も journal-ref も付いていないので、これは preprint(査読前の投稿原稿)として扱う。投稿から一週間も経っていないので被引用数はまだ実質ゼロで、広く議論されていない段階の論文である。実装は GitHub(Wloner0809/CAST)で公開されている。

私がこれを今日選んだ理由は単純で、評価に使われている三本が Sokoban・Minesweeper・Rush Hour、つまりどれもパズル作りをしている人間が自分の手で作ったことのある形式だからだ。しかも論文は「難易度をどう定義したか」を表にして明示している。AI 側の論文でありながら、パズル設計の語彙に翻訳しやすい素材だと感じた。

背景

言語モデルにゲームを解かせる学習では、近年 RLVR(reinforcement learning with verifiable rewards、検証できる正解だけを報酬にする強化学習)という枠組みが主流になっている。答え合わせが機械的にできる課題では、人間の好みを学んだ採点モデルより信頼できるからだ。ところが長い手数のゲームでは、その「検証できる報酬」が最後の一回しか出ない。

論文が指摘する問題はここにある。GRPO のような手法では、一本の対戦(トラジェクトリ)にまとめて一つの評価値が付き、それが全ての手・全てのトークンに同じ値で配られる。著者はこれを「長手数ゲームにおける credit assignment(どの行動が結果に効いたかを割り振ること)の失敗の根源」と書いている。1手目の好手と 30手目の凡手が同じ点数を受け取るなら、モデルは何を直せばいいのか分からない。

では途中の一手ごとに点を付ければよい、という発想は当然出てくる。既存の方法は三系統あって、木探索を回す(コストが高い)、途中経過を採点する専用モデルを学習する(その採点が正しいか保証がない)、複数の対戦を横に並べて比較する(GiGPO などの方向)。著者は「計算量・教師信号・信号の信頼性のあいだでトレードオフが残る」と整理している。この隙間に「そもそもパズルには厳密に解けるソルバーがある」という当たり前の事実を差し込んだのが本論文だ。

アプローチ

CAST の中身は、言葉にすると驚くほど素朴である。ソルバーは任意の盤面について「ここからゴールまで最短で何手か」を返せる。論文はこれを cost-to-go(残り手数)と呼ぶ。学習中のモデルが一手打つたびに、打つ前の残り手数と打った後の残り手数を比べ、その差を評価にする。最善手なら残りが 1 減るので +1、何も進まない手は 0、状況を悪くする手は負の値になる。数式は使わないが、要は「一手ごとの進捗メーター」だと理解してよい。

詰みの盤面(Sokoban で箱を隅に押し込んでしまった等)では残り手数が無限になるが、そのまま無限の罰を与えると学習が壊れる。論文は「その時点までに積み上げていた残り手数の分だけ損をした」と数え直して有限に抑える。さらに、値のばらつきを潰すために二段の整形を入れる。ひとつは asinh 変換(小さい値はほぼそのまま、大きい値は圧縮して、符号を保ったまま外れ値の影響を抑える)、もうひとつはバッチ全体での大きさ揃え。ただし平均を引く操作はしない。0 が「進捗なし」を意味している以上、平均を引くとその意味が壊れるからだ。

この一手ごとの進捗信号は、従来の「勝った/負けた」の評価に係数 0.1 で足し込まれる形で使う。土台の学習アルゴリズムは DAPO(GRPO 系の改良版)で、勝敗の定義そのものは一切変えていない。理論面では、ソルバーが十分に良い手を選ぶという仮定のもとで、この進捗信号を最大化することが「ソルバーからの on-policy 蒸留(生徒が自分で歩いた盤面で先生の好みを教わる学習)」と等価になることを示している。重要なのは、そのために先生の全選択肢の確率分布が要らず、残り手数という一つの数値で足りる点である。

学習対象は Qwen3-4B-Instruct-2507 という 4B(40 億パラメータ級)のモデル一本。盤面をテキストで見せ、考えてから一手を出す ReAct 形式のやりとりで、反則手を打っても即負けにはせず「その手は無効」と返して手数だけ消費させる。三種のパズルはすべて自動生成で、Rush Hour だけは厳密ソルバーで最短手数が狙った範囲に入る盤面だけを採用している。

発見

主要な数値は Table 1 にある。三種平均の成功率(各問題に 4 回挑戦した平均、三回の学習の平均)は、素の 4B モデルが 16.6%、比較対象の学習手法が GRPO 44.9%・GSPO 41.9%・DAPO 44.7%・GiGPO 45.4% で、CAST が 62.1%。学習していない一段上の難易度では、素のモデル 5.9%、最良の比較手法 GiGPO 20.8% に対して CAST 28.4% だった。「効果があった」の中身は、同じ土台の DAPO と比べて学習時難易度で +17.4 ポイント、未学習難易度で +9.7 ポイントということになる。

個別に見ると伸び幅が最も大きいのは Minesweeper で、学習時難易度では最良の比較手法から +14.9 ポイント。ただし著者自身が「未学習難易度の 11.0 という数字は、より難しい盤面での改善余地を残している」と書いており、勝ってはいるが解けてはいない。参考として並べられた閉じたモデル群のうち、CAST の 62.1% は Gemini-2.5-Flash の 58.7% と Claude Sonnet 4.5 の 50.4% を上回るが、Opus 4.6 の 79.9% には届かない。

学習の速さも報告されている。DAPO が最終的に到達した検証成績に CAST が届くまでのステップ数は Sokoban 120・Minesweeper 200・Rush Hour 140 で、DAPO 自身の 200・400・240 に対して 1.7〜2.0 倍速い(Figure 3)。またソルバー問い合わせのコストは、環境の 1 ステップの 8.4%、一本の対戦全体の 0.01%、学習 1 ステップの実時間では 100 万分の 73 に相当する(Figure 6)。生成にかかる時間が支配的なので、先生役はほぼ無料ということだ。

設計のどこが効いているかを一つずつ外して確かめる ablation study も Sokoban で行われている。進捗信号の重みは 0.1 が最良で、小さすぎると勝敗のみの学習と変わらず、大きすぎると序盤に伸びてから崩れる。asinh を外すのが最も痛く、外れ値が更新を支配してしまう。バッチごとの大きさ揃えを外すと序盤は同じでも後半で頭打ちになる。ただしこの図には数値が載っておらず、定性的な記述に留まる点は控えておきたい。

使いどころ

一つ目。手作りパズルの難易度指標として、この論文の「残り手数の減り方」をそのまま流用できる。もし自分が Sokoban ライクを作っているなら、既にソルバーは持っているはずだ。それを使って、正解手順の各手で残り手数がどう動くかを並べてみる。残りが減り続ける平坦な区間は「手数は長いが考えどころのない場所」、逆に多くの手が 0 か負になる分岐点は「ここで詰む」場所である。論文が学習信号として使っているものは、そのまま人間向けの難所検出器になる。

二つ目。ヒント機能の設計に直接効く。多くのパズルゲームのヒントは「次の一手を教える」形をとるが、この論文の枠組みが示すのは、正解手を出さずに「今の手は進捗 +1 だった / 0 だった / 悪くなった」というスカラーだけ返す道があるということだ。答えを見せずに詰まりを解除できるので、解けた実感を壊しにくい。もしデイリーパズルなら、日々のヒント消費量を進捗メーターの動きと突き合わせれば、どの局面で人が迷うかが自動で分かる。

三つ目。自動生成の難易度キャリブレーションに使える。論文の Table 3 では、盤面サイズと個数(Sokoban は箱、Minesweeper は地雷、Rush Hour は車)だけで難易度段を作り、Rush Hour では「厳密ソルバーの最短手数が狙った範囲に入る盤面だけ採用する」という篩をかけている。ハイパーカジュアルの PCG(procedural content generation、コンテンツの自動生成)でも、生成 → ソルバーで最短手数を測る → 手数帯で棚に分ける、という三段だけで難易度カーブが引ける。実装コストはソルバー一本ぶんだ。

四つ目、これは応用寄りの提案になるが。論文は「厳密ソルバーがない場合でも、学習した評価ネットワークで代替できた」(Figure 5)と報告している。ソルバーが書けないルール、たとえば運の要素や隠れ情報を含むパズルでも、大量のプレイログから盤面の有望さを学習させれば、同じ進捗メーターを作れる可能性がある、と読める。ただしこの実験は Rush Hour 一本、数値も示されていないので、あくまで方向の提示として受け取るのが妥当だろう。

限界

まず著者自身が認めている点。Minesweeper の未学習難易度 11.0 は低く、難しい盤面には手が届いていない。Minesweeper の教師信号については「部分観測のもとでは最適な残り手数が定義できない」ため、ある決め打ちの解法が必要とする手数で代用しており、厳密な最善ではないと明記されている。加えて盤面生成で「推測なしで解けるか」の絞り込みをしていないので、運に頼るしかない盤面が混じり得るとも書かれている。理論側でも、ソルバーが最適から外れれば蒸留としての解釈は比例して劣化すると述べている。

ここから先は Fukai が読んで気づいた点である。第一に、この論文には Limitations という節が存在しない。全文を検索しても limitation という語が一度も出てこない。弱点は付録の仮定の議論に散らばっており、読者が自分で集める必要がある。preprint 段階だからかもしれないが、査読を通った論文と同じ重みで扱うべきではないと考える。

第二に、学習したモデルは Qwen3-4B 一本、サイズ一種類のみである。大きいモデルでも進捗信号が同じだけ効くのか、それとも元々計画が得意なモデルでは効果が薄まるのかは、この論文からは言えない。第三に、方法の前提は「そのゲーム専用のソルバーを書ける」ことで、これは三本ぶん個別に書かれている。パズルとしては書けて当然の三本を選んだ、と見ることもできる。学習した評価ネットワークによる代替は一本で試されただけだ。

第四に、私が最も気になったのは難易度の段差の幅である。Table 3 の「未学習難易度」は 6×6 の箱 2 個から 7×7 の箱 3 個へ、といった一段上げに過ぎない。ここで 34.8% しか取れていないという事実は、汎化の主張を控えめに読むべき理由になる。パズル設計の目から見れば、箱が 2 個から 3 個に増えるのは難易度が一段上がるどころか、要求される洞察の種類が変わる場合がある。同じ「難易度」の語で括るのは慎重でいたい。

Fukai の読み

ここは私の解釈である。私はこの論文を、機械学習の credit assignment の話としてよりも、「パズルの難しさを一次元のスカラーに潰してよいのはどこまでか」という設計論の実験として読みたい。残り手数の減り方という一本のメーターは、探索の長さとしての難しさを実に上手く捉える。だが Minesweeper で残り手数がそもそも定義できなかったこと、そして箱を一個増やすだけで成績が半分近くに落ちたことは、逆方向の証拠でもある。設計批評の語彙で言えば、この論文が自動化したのは「詰まっているかどうかの判定」であって、「なぜ面白いかの判定」ではない。前者は測れる。後者はまだ誰も測れていない。その線が、この論文の数表の裏側にはっきり引かれていると私は読む。

おわりに

この論文の一段前に何があったかを知りたい人は、まず同じ「途中経過に点を付ける」系統の GiGPO(Feng ら, 2026)を見るとよい。こちらは外部のソルバーを使わず、同じ状態に到達した複数の試行を横に並べて比較することで一手ごとの評価を作る。ソルバーを書ける場合とそうでない場合の対比として、CAST と並べて読むと地図が見える。

パズル生成側から入りたい人には、探索ベースの自動生成の系譜と、当サイトで以前扱った検証器を門番にする自己蒸留の話が近い。難易度をソルバーの最短手数で測って棚に並べる、という発想はどれも共通しており、この論文が新しく持ち込んだのは「その棚を、人ではなく学習中のモデルに一手ごとに見せる」という向きの反転だと整理できる。

私は明日もコーヒーを濃く淹れて新着を眺める。今日のように、パズルの名前が三つ並んでいる論文はうれしい日である。

参考文献

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

・CAST: Game Solvers as Turn-Level Teachers for LLM Agents (Yu Wang, Yi-Kai Zhang, Wentao Shi, Ziang Ye, Yuchun Miao, Yueqing Sun, Qi Gu, Xunliang Cai, Lan-Zhe Guo, Han-Jia Ye, Fuli Feng, 2026, arXiv preprint)

・DOI: 10.48550/arXiv.2607.25308(arXiv 発行、査読前)

・HTML 全文(付録 B の環境仕様・付録 C の理論を含む)

・実装: github.com/Wloner0809/CAST

・関連研究(本論文の主要な比較対象): Group-in-Group Policy Optimization for LLM Agent Training (Feng ら, 2026)

・被引用の確認: Semantic Scholar / Google Scholar