Monti et al.: 一本道の倉庫番で、AI の「計画する力」を測る — Fukai が読む

一段落要約

大規模言語モデル(LLM。大量の文章で学習し、次に来る言葉を予測する形で文章を作る AI)は、近頃「推論モデル」として、答えを出す前に思考の筋道を文章で書き出すよう訓練されている。この論文が問うのは、その推論モデルが「長い手順を最後まで見通して計画する力」をどれだけ持っているか、である。著者らは倉庫番(Sokoban。箱を目標地点まで押し込むパズル)を題材にし、わざとパズルを極限まで単純にした——一本道の通路に、動かせる箱が一つだけ、という構成だ。

結果は明快である。人間にはあくびが出るほど簡単なこの一本道でも、解くのに 25〜30 手より多くの先読みが必要になると、最新の推論モデルはどれも崩れた。外部のソルバー(解を厳密に計算する専用プログラム)を道具として持たせると平均では多少なめらかになるが、根本的な弱さは消えない。著者らは、つまずきの中心は「マスの数を正しく数え続けられないこと」にあると見ている。本記事は、この一本を論文を開かずに要点が掴めるよう解説する。

はじめに

今日紹介するのは「SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models」という論文だ。著者は Sebastiano Monti、Carlo Nicolini、Giovanni Pellegrini(いずれもイタリアの Ipazia SpA)、Jacopo Staiano(トレント大学)、Bruno Lepri(Fondazione Bruno Kessler および Ipazia SpA)。arXiv に 2026 年に投稿されたプレプリント(arXiv:2601.20856。投稿されたばかりの原稿で、まだ査読を通っていない段階の可能性がある)である。被引用数もまだ積み上がっておらず、広く議論される前の段階だと添えておく。

私がこれを今日選んだのは、テーマがパズルそのものだからだ。倉庫番という、パズルを作る人なら誰もが知る古典を、AI の能力を測る「ものさし」として使っている。しかも著者らの手つきが面白い。普通なら難しいパズルを並べて AI を困らせるところを、彼らはむしろ「これ以上ないほど簡単な」パズルだけを並べる。それでも AI が崩れるなら、崩れる理由は難しさそのものではなく、もっと手前の何かにある——そういう設計の論文だ。

もう一点。この論文は AI の評価が主題だが、私はパズル設計の語彙でも読めると考えている。難しさをたった一本の軸に絞り込む発想や、表現形式が成績を左右するという観察は、ゲームを作る人にも持ち帰れる。だから本記事は、AI 研究としての読みと、設計者としての読みの両方を行き来する。

背景

「計画(プランニング)」とは、目標に到達するための行動の並びを組み立てることだ。AI 研究では古くからの主題で、形式言語 PDDL(Planning Domain Definition Language。世界の状態と行動の規則をきっちり書き表すための記述言語)や、木探索(取りうる手を枝分かれさせて調べていく方法)といった道具で取り組まれてきた。一方、近年の LLM は文章理解や知識の引き出しでは目覚ましいが、「計画」となると弱いことが繰り返し報告されている。

倉庫番が評価の題材として好まれるのには理由がある。解ける盤面を効率よく自動生成でき、環境は完全に決定的(同じ操作なら必ず同じ結果になる)で、厳密なソルバーで答え合わせができる。さらにハノイの塔のように「同じ手順の繰り返し」では解けない——箱を一つ動かすと道が塞がったり開いたりするため、盤面ごとに固有の解が要る。だからこそ国際計画競技会(2023 年版)でも採用されるほど、計画能力の試金石とされてきた。

ここまでで分かっていなかったのは、LLM が計画でつまずく「本当の原因」だ。難しさそのもの(枝分かれの多さや探索の深さ)のせいなのか、それとも、もっと素朴な操作——たとえば正しく数を数える、今どこにいるかを覚えておく——の取りこぼしなのか。著者らはこの切り分けに踏み込もうとした。

アプローチ

著者らの核心は「複雑さを足さずに、手数だけを長くする」ことだ。盤面は幅 ℓ・高さ 1 の一本道で、登場するのはプレイヤー一人・箱一つ・目標一つだけ。三つが同じ列に一直線に並び、目標が一方の端、プレイヤーが反対の端、箱はその間にある。盤面の自由度は通路の長さ ℓ ただ一つで、これが難しさの代わりになる(長いほど手数が増え、難しい)。ℓ は 5 から 100 まで 5 刻みで、各長さに 90・180・270 度回転と元の向きの 4 種を用意し、合わせて 80 盤面。データは公開されている。

なぜこんなに単純にするのか。著者らは「長い手順を見通す力」を「状態を覚え続ける力」から切り離したいのだ。一本道なら枝分かれはほぼゼロ。だから AI が失敗するとしたら、それは選択肢の海で迷ったからではなく、まっすぐな道を最後まで数え切れなかったから——という切り分けが効く。盤面は ASCII(記号で絵を表す文字列)で表し、解答は LURD(left・up・right・down の頭文字で移動を表す記法)で書かせる。

実験は二段構えだ。一つ目は「1-shot 推論」——例題を一つだけ見せ、あとはモデルの内部記憶だけで解かせる(外部の道具なし)。二つ目は「LLM-Modulo」——モデルに PDDL の構文確認役・検証役・ソルバーを道具として与える。ここでモデルの役目は、解そのものを出すことではなく、問題を PDDL の形に書き起こすことだけ。書き起こした問題は専用ソルバー(Fast-Downward など)が解く。道具は Anthropic が公開した接続規格 MCP(Model Context Protocol。AI と外部ツールをつなぐ共通の作法)経由で渡している。

評価の物差しは三つ。完全一致の正解率(模範解答と文字列がぴったり一致した割合)、途中まで合っていれば部分点を与える接頭辞正解率、そして最後に到達した位置と目標との距離(マンハッタン距離。縦と横の移動量を足した距離)だ。三つ目は「完全には外したが方向は合っていた」惜しい失敗と、完全な迷子とを区別するための、いわば柔らかい失敗信号である。

発見

まず 1-shot 推論。正解率を通路の長さに対して描くと、論文(Figure 3)はおおむね三つの領域に分かれる。短い通路では高い正解率を保つ「易しい領域」、長さが増すと急激に正解率が落ちる「中間領域」、そしてモデルが正しい手順をまったく返せなくなる「困難領域」だ。どこで崩れるかはモデルごとに違う。結論部で著者らは、最新の推論モデルでも目標を 25〜30 手より先まで見通す必要があると崩れる、と述べている。

なぜ落ちるのか。著者らの見立ては「数え間違いの蓄積」だ。一手ごとにマスの数をわずかに数え損なう確率があると、それが手数の分だけ掛け合わさって、長い通路では成功確率が指数的にしぼむ(数式は割愛するが、著者は一歩ごとの小さな誤りが積み上がる形で説明している)。実際、長い通路ではモデルが同じ手や同じ思考を延々と繰り返し、出力上限(完了トークンを 32,768 に制限)に達して止まる様子が観察された。著者はこれを「系統的に探索せず、あてもなくさまよっている(wandering)」状態だと表現している。

興味深い副産物もある。正解時の出力量は通路の長さにつれてほぼ直線的に増える一方、不正解時は出力量のばらつきがずっと大きい。著者らは、別の研究で報告された「難しすぎると推論を早々に切り上げる」現象は今回は観測しなかったと明記している。むしろモデルは最後まで考え続け、それでも当てられないのだ。また GPT-5-mini が長さ 50 付近で不自然に正解率の山を作る現象も見られたが、これは記憶(学習データに含まれていた可能性)によるものではないかと著者は推測している(断定はしていない)。

次に LLM-Modulo。外部ソルバーを噛ませると正解率の曲線はなめらかになり、急な山や急落が消えて、落ち方がゆるやかになった。ただし改善は控えめだ。道具をうまく使えたのは試したうちで GPT-5-mini だけで、DeepSeek R1・Gemini-2.5-Flash-Preview・Claude-3.5-Haiku は道具の操作や正しい PDDL 問題の生成でつまずいた。しかも興味深いのは失敗の中身で、PDDL の構文エラー(ソルバーが受け付けない書式の誤り)は 80 構成×4 試行のうちわずか 7 回。多くは構文は正しいのに、盤面の大きさを取り違えた「意味のずれた」問題を生成してしまう。専門家が用意した正しいソルバーを使ってなお、モデルが空間を正しく数え表せないことが残る——これが著者らの読みだ。なお参考として、著者らは先行研究(Valmeekam ら, 2025)が o1-preview で直接解 約10〜12%、ソルバー併用で 約43% と報告したことにも触れている(これは先行研究の数値である)。

使いどころ

パズルを作る人として、まず実務に効くのは「生成の検証に LLM を解き手として信用しない」という教訓だ。もし自分が自動レベル生成つきの倉庫番ライクを作っているなら、生成したステージが本当に解けるかの判定は、LLM ではなく決定的なソルバー(Fast-Downward のような専用プログラム)に任せるべきだ。この論文の LLM-Modulo の結果は、LLM はむしろ「問題を形式に書き起こす係」として使い、解の保証は古典ソルバーに渡す分業が現実的だと示している(著者の主張に沿った読みだ)。

二つ目。AI を「自動プレイテスター」や「難易度推定器」に使う計画があるなら、その壊れどころを先に知っておける。人間には自明な一本道でも、25〜30 手を超える先読みが要ると最新モデルでも崩れた。つまり LLM ベースの難易度推定は、短い手数のパズルに限るか、ソルバーを道具として持たせる前提で組むべきだ。長手数の詰めパズルを LLM だけに評価させると、当てにならない数字が返ってくる恐れがある。

三つ目は設計思想そのものへのヒントだ。著者らは難しさを「通路の長さ」ただ一本の軸に絞った。これはチュートリアルや序盤の難易度カーブを引くときの好例になる。複数のパラメータを同時にいじる前に、まず一本の読みやすい軸で難しさを上下させてみる——プレイヤーにも自分にも挙動が見通せる。もしハイパーカジュアルの PCG(Procedural Content Generation。コンテンツの自動生成)を回しているなら、まず単一軸で難度を刻み、効果を確かめてから軸を足すと制御が崩れにくい。

四つ目。表現形式が成績を左右した点も実務的だ。論文では縦向きの通路(改行が多く入る盤面)で成績が落ちる非対称が見られた。もし自分のツールがレベル配置を LLM に渡している(ヒント生成・NPC・自動採点など)なら、ASCII か、行・列に番号を振った格子か、LURD か——どの符号化で渡すかで信頼性が変わる。表現を正規化し、向きや改行の癖が結果を歪めていないか一度確かめる価値がある。

限界

著者自身が認める限界は率直だ。盤面は箱一つの一本道に限っており、これは複数の箱やデッドロック(箱を押し込んで二度と動かせなくなる詰み)を含む本来の倉庫番の難しさは測っていない。だから本ベンチマークは計画能力の「下限」を示すだけだ、と書いている。評価は模範解答との完全一致で行っており(一本道なら最適解は一通りなので妥当だが)、一般の倉庫番では複数の最適解があるため、今後はソルバーによる検証に切り替える予定だという。

ほかにも、向きや改行の有無といったプロンプトの書式に成績が左右されること、API 経由ゆえにモデルや提供基盤が時とともに変わりうること、回転で多少和らげても学習データへの混入(コンタミネーション)を完全には排除できないこと、そして一本道の結果がより豊かな計画課題に当てはまる保証はないこと——これらを著者は「妥当性への脅威」として並べている。彼ら自身、本設定は主に動作確認(サニティチェック)であり、今後は障害物や枝分かれ、デッドロックを足すと述べている。

Fukai がここで指摘するのは、二点だ。一つは、検証した推論モデルが少数(DeepSeek R1、GPT-5 系、GPT-oss 120B)で、しかも LLM-Modulo に至っては実質 GPT-5-mini 一つに絞られている点。結論の射程は、ここで試した特定のモデル群に限って読むのが安全だと考える。もう一つは、計算コストの重さだ。LLM-Modulo は GPT-5-mini で図 6(a) を集めるのに平均 75 分かかったと報告されている。実運用で「ソルバー併用なら安心」と言うには、この遅さと費用を設計段階から見込む必要がある、と私は読む。

Fukai の読み

ここからは私の解釈だと断っておく。私はこの研究を、「賢さの頭打ちは派手な難問ではなく、地味な状態管理で露わになる」という近年の流れの中に置きたい。設計批評の語彙で言えば、これは難しさを一本の軸に還元する「難易度の最小単位化」の実験に近い。倉庫番というパズルを、AI の弱点を映す鏡として一直線に削ぎ落としたとき、見えてきたのは知能の輪郭ではなく、数を数え、今いる場所を覚え続けるという、人間なら指で追えば済む営みの脆さだった。パズル作家が経験的に知っている「単純なのに最後まで気が抜けない設計」が、奇しくも AI の急所を突いている——と私は読む。

おわりに

もっと深く知りたい人へ、地図を描く手がかりを置いておく。この論文が前提として踏まえている「LLM は計画が苦手だが、ソルバーと組ませる枠組み(LLM-Modulo)なら手伝える」という立場は、Kambhampati らの議論に連なる。また、推論モデルが難問の前で崩れる様子を扱った Shojaee らの「思考の幻想(The Illusion of Thinking)」とは、本論文が随所で結果を突き合わせている。倉庫番そのものの計算量(PSPACE 完全という、解の探索が本質的に重い性質)に興味があれば Culberson の古典が出発点になる。

パズルを作る側からは、生成と検証を同じループに入れる発想——AI に問題を書かせ、ソルバーに解かせて確かめる——が、当面いちばん実りある持ち帰りだろう。AI を万能の解き手と見るより、形式に書き起こす相棒と見て、保証は古典的な道具に委ねる。地味だが、崩れにくい。次に倉庫番ライクの自動生成を組むときは、その分業を思い出してほしい。

参考文献

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

・SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models (Monti, Nicolini, Pellegrini, Staiano, Lepri, 2026, arXiv preprint)

・データセット: sokobanlevels (Hugging Face)

・関連研究: Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks (Kambhampati et al., 2024)

・関連研究: The Illusion of Thinking (Shojaee et al., 2025)