こんな人向けの記事
- パズルゲームの自動解法や、探索アルゴリズムの実装に関心がある方
- A* のヒューリスティック設計で「許容性 (admissibility)」と「整合性 (consistency)」の違いが実装にどう表れるかを具体例で見たい方
- 『てくてくピクミン』の各ステージ最短手数が気になっている方
結論
成果品はこちら: てくてくピクミン 解答一覧 (非公式ファン解析)
全 68 ステージそれぞれについて、本稿で扱う最短解の動きをブラウザ上で再生できるページです。自由プレイはできず、事前に求めた正解手順をなぞる形の再生専用インターフェースにしています。
ゲームキューブ版『ピクミン2』からカードe+にインストールできたミニゲーム『てくてくピクミン』の全 68 ステージについて、Python でゲームエンジンを再現し、Claude Code に A* 探索を実装してもらって最短解 (いかに少ない移動数でクリアできるか) を調べました。主な結果は次の 3 点です。
- 最短解を導き出したのは 53 ステージで、残る 15 ステージは状態数上限や時間切れで計算しきれなかったため、作者が VBA (エクセルマクロ) で解析した解をそのまま採用しています (最短解は担保できず)。
- 7 ステージで、エクセルマクロ解より短い手数の最短解を確認しました。合計で 31 手の短縮となり、最大は Stage 58 の 11 手短縮 (57 → 46 手)、次いで Stage 28 の 8 手短縮 (61 → 53 手) です。
- Python A* で状態数上限に達してしまう大規模ステージ (Stage 28 / Stage 57) については、メモリ消費の少ない IDA* (Iterative Deepening A*) を C 言語で再実装することで到達できました。
本稿では、ゲーム仕様の再現、状態表現とヒューリスティックの設計、実装上のバグとその修正、DQN (Deep Q-Network) による別手法との比較を、順を追って整理します。
てくてくピクミンってどんなゲーム？
『てくてくピクミン』は、ゲームキューブ版『ピクミン2』にカードe+を介してインストールできたミニゲームです。全 68 ステージの同方向移動パズルで、プレイヤーが上下左右のいずれかを選ぶと、マップ上のピクミンが全員同じ方向に 1 マスずつ同時に動きます。宝物マスに全員が到達するまでの手数を短く抑えるのがゴールです。
タイルには壁、穴、火・電気・水・毒のハザード、劣化可能な岩、色変換の花、敵、宝物が配置されており、ピクミンの色によって通過可否が定義されています。赤ピクミンは火を踏めるが水は踏めない、という具合です。
最短解を比較する基準としては、作者の方がエクセル VBA でゲームを再実装し、各ステージを自力で解析した際の解答値を参照しました。本稿ではそれらを「VBA 解」と表記します。
記事はこちら:
内部仕様の説明
本稿は A* / IDA* / ヒューリスティック設計といった探索アルゴリズムの基本概念を前提に書いています。初めて触れる方や、軽く復習したい方向けに、基本を別記事にまとめました。先にこちらを読んでおくと、本編の内容がスムーズに入ると思います。
各記事には、本記事の解析工程 (どのステージでどう設計・修正したか) を補足として組み込んでいます。概念の説明だけで終わらず、実際の適用例まで一続きで読めるようにまとめています。
性能最適化: 9.7 時間から 37 秒へ
用語補足: 本稿でいう「エンティティ」とは
『てくてくピクミン』におけるエンティティ = 盤面上に 1 体ずつ存在するピクミン (駒)のことです。ゲームエンジンは各ピクミンを「id、座標 (x, y)、色、生存フラグ」といった属性を持つオブジェクトとして管理し、これをリストに入れて保持しています。ターン処理ではこのリストを何度も走査する場面が出てきて、その走査方法がそのまま全体の性能に効きます。以下はその走査まわりの話です。
Stage 43 の A* は初期実装で約 34,900 秒 (9.7 時間) かかっていました。プロファイラを掛けたところ、盤面のセルを回るたびに「その位置に居るピクミンは誰か？」をエンティティの配列から 1 つずつ探していたことが判明。ステージのサイズを $w \times h$、ピクミン数を $k$ とすると、この線形検索が盤面 1 枚あたり $w \times h \times k$ 回走る計算で、実測では 5 万状態を処理する間に約 1,220 万回の検索が発生していました。
対処は単純で、盤面を走る前に一度だけ「座標 → エンティティ」の対応表を辞書として作り、以降はその辞書を引くようにしました。計算量が $O(w \times h \times k)$ から $O(w \times h)$ に落ちるイメージです。
エンティティ一致探索の高速化
もう一つの重たい処理が、ターン終了後に新しい盤面のピクミンを前ターンのどのエンティティと対応付けるかを判定する「エンティティ一致探索」です。移動後もエンティティ ID を維持しないと、アニメーションの補間や内部の追跡が崩れるため、毎ターンこの対応付けが必要になります。
素朴な実装では、新しい盤面に現れた各ピクミンについて、前ターンの全エンティティを順番に見比べて一番近いものを選ぶ方針を取っていました。エンティティが増えると、これも $O(k^2)$ 相当のコストになります。色は移動で変わらない (花に乗った時を除く) ので、「色ごとにグループを作っておいて、同じ色の候補だけ見比べる」と差し替えるとチェック回数が大きく減ります。
このエンティティ一致探索の差し替えに加えて、盤面のディープコピーを Python の copy.deepcopy から直接構築に切り替えたことで、Stage 43 の実行時間は 34,900 秒から 37 秒にまで短縮されました。約 950 倍の差で、複数回の計測でも再現しています。プロファイラが示すボトルネックに手を入れるだけで、ここまで効くという単純な例になりました。
全 68 ステージの探索結果
各ステージに対して状態数上限 (500K 〜 30M) を設定し、作者の VBA 解析解との比較を行いました。探索手法は 2 種類用意しており、標準的な A* で収束できなかったステージは、C 言語で再実装した IDA* (Iterative Deepening A*) にかけ直しています。
IDA* は A* と同じく $f(n) = g(n) + h(n)$ を最小化する手法ですが、オープン集合を陽に保持せず、$f$ 値のしきい値を徐々に引き上げながら深さ優先探索を繰り返す構造です。メモリ消費が一定に抑えられるため、状態空間が大きい問題でも探索を続けられる反面、同じノードを複数回展開するので時間はより多く要します。本稿では Python の A* で収束しなかった 2 ステージに対して採用しました。
全体の内訳は次の通りです。
- Python A* で最適性を確認: 51 ステージ (VBA 解と一致 46、VBA より短縮 5)
- C IDA* で最適性を確認: 2 ステージ (Stage 28, Stage 57 — いずれも VBA より短縮)
- ソルバー未収束で VBA 解をそのまま採用: 15 ステージ (状態数上限や時間切れにより最適性は未確認)
- 合計短縮手数: -31 手 (7 ステージ)
短縮に成功した 7 ステージは以下の通りです。「手法」列は最短解を確定させたソルバーを指し、Python A* は results_v2.csv、C IDA* は tools/solver/*.log が一次ソースです。
| Stage | ピクミン数 | VBA 解 | 採用解 | 短縮 | 手法 |
|---|---|---|---|---|---|
| 11 | 10 | 32 | 31 | -1 | Python A* |
| 28 | 4 | 61 | 53 | -8 | C IDA* |
| 38 | 3 | 28 | 26 | -2 | Python A* |
| 42 | 3 | 74 | 69 | -5 | Python A* |
| 57 | 6 | 53 | 52 | -1 | C IDA* |
| 58 | 3 | 57 | 46 | -11 | Python A* |
| 63 | 3 | 36 | 33 | -3 | Python A* |
最大の差分は Stage 58 の 11 手短縮 (57 → 46 手) で、Python A* が約 66 万状態の展開で到達しています。Stage 28 の 8 手短縮 (61 → 53 手) は、Python A* では状態数上限に到達してしまい見つけられなかったものを、C 言語の IDA* ソルバーで約 45M 状態 / 約 11 分かけて発見した解です。双方向に同種の「機械的な全探索が、人手の解析では拾いにくい経路を選ぶ」傾向が観察できました。Stage 57 の IDA* 解は約 30 億状態 / 1.75 時間を要しています。
一方で、15 ステージについてはソルバーが状態数上限や時間切れにより最短解を見つけられませんでした。こちらはいずれも VBA 作者の解析解をそのまま採用して本稿の一覧には含めていますが、厳密にはソルバー側の最適性保証はついていません。VBA 解そのものが最短である可能性は十分にありますが、本稿では「確認済み 53 ステージ + 未確認 15 ステージ」という内訳になります。
最適性を確認できなかった 15 ステージは次の通りです。採用手数は作者の VBA 解析解をそのまま採用した値になります。
| Stage | ピクミン数 | マップサイズ (横×縦) | 採用手数 (VBA 解) |
|---|---|---|---|
| 6 | 10 | 16 × 7 | 44 |
| 7 | 3 | 21 × 9 | 107 |
| 8 | 3 | 22 × 9 | 115 |
| 21 | 3 | 22 × 9 | 47 |
| 22 | 6 | 17 × 8 | 37 |
| 24 | 4 | 22 × 9 | 82 |
| 27 | 2 | 25 × 11 | 70 |
| 39 | 5 | 10 × 6 | 29 |
| 50 | 3 | 16 × 7 | 14 |
| 60 | 5 | 22 × 9 | 83 |
| 64 | 3 | 13 × 10 | 18 |
| 66 | 2 | 11 × 11 | 14 |
| 67 | 3 | 16 × 11 | 31 |
| 68 | 5 | 22 × 9 | 43 |
| 69 | 4 | 16 × 10 | 19 |
Stage 7, 8, 21, 24, 60, 68 のように 22 × 9 前後の広いマップと 40 手を超える手数が重なるステージは、単純に探索空間が大きく Python / C どちらのソルバーでも制限内に到達できませんでした。一方で Stage 50, 64, 66, 69 のようにマップ自体は小さく手数も短いものも未確認に含まれています。こちらは探索の規模より、PASS 3 ロジックや初期実装時点のヒューリスティック設計との相性が原因と推測され、アルゴリズム側の調整余地が残っていると考えられます。
DQN による比較実験
古典探索だけでは視点が偏るため、強化学習でも同じステージを解いて比較しました。Deep Q-Network (DQN) を用い、ピクミンの色・位置やタイル種別を 18 チャンネルのテンソルとしてエンコードして CNN ベースの Q 関数を訓練します。報酬はクリア +100、死亡 -100、1 ステップあたり -1 の素朴な設計としました。
補足: Deep Q-Network (DQN) とは？
DQN は強化学習 (Reinforcement Learning) の代表的な手法のひとつで、ニューラルネットワークを使って「各状況でどの行動を取れば将来の累積報酬が最大になるか」を学習するアルゴリズムです。
- 状態 (state): ゲームでいえば現在の盤面。本稿では 18 チャンネルのテンソルとして表現。
- 行動 (action): 次の一手。ここでは「上・下・左・右」の 4 択。
- 報酬 (reward): 行動の結果得られる数値 (クリア +100、死亡 -100 など)。強化学習は累積報酬を最大化する方針を学ぶ。
- Q 関数: 「この状態でこの行動を取った時、将来的にどれくらい累積報酬が見込めるか」を返す関数。DQN はこれをニューラルネットワークで近似する。
A* / IDA* がゲームのルールを前提とした経路探索なのに対し、DQN は「ルールを事前に与えず、エピソードを何度もプレイして経験から方針を学ぶ」アプローチです。ゲーム固有の設計 (ヒューリスティックなど) が不要な代わりに、学習のために大量のエピソードが必要になるというトレードオフがあります。
Stage 33 (白ピクミン 2 体、8 手最適) を 1,000 エピソード訓練したところ、130 エピソード目に A* と同じ 8 手の最適解を発見し、終盤のクリア率は 73% 程度で安定しました。Stage 47 (赤 2 体 + 白 1 体、同じく 8 手最適) では 1,500 エピソード訓練して 166 エピソード目に最適解を確認しています。後者の学習曲線では、約 400 エピソード時点で 78% まで上がった後、800 エピソード付近で 30% まで後退し、1,100 エピソードで 93% まで回復する形が観測されました。
これは DQN で見られる一時的な性能悪化 (catastrophic forgetting に近い現象) と考えられます。経路探索の効率だけで比べれば A* が圧倒的 (0.01 秒 vs 10 〜 30 分) ですが、DQN の利点は「ルールを事前に与えなくても、経験から方針を獲得できる」点にあります。両手法が同じ最短手数に収束した事実は、結果の正しさを別角度から裏付ける意味でも有用でした。
DQN で最適解は見つけられるか？
DQN と A* が同じ最短手数に収束したことを確認できたので、自然と「では DQN が A* を超えて既知の最短解を更新できるのか」という問いが浮かびます。結論から言うと、現在の実装ではほぼ No です。理論面・実測面・設定面・所要時間という 4 つの観点から、その理由を整理しておきます。
1. 理論上「更新」は起こらない
本稿の A* / IDA* は、宝物マスを起点とした多源 BFS の実距離にもとづく 許容的 なヒューリスティックを使っています。許容性が担保されていれば、A* が返す解は数学的にも最適 (ノードの重みを 1 に揃えた Dijkstra と等価) です。したがって 53 ステージについては、現時点で既に「グローバル最短」が確定していると見なせます。DQN はあくまで経験から方針を学習する手法のため、ベストケースで A* に並ぶだけであり、原理的にそれを更新することはありません。
逆に言えば、もし DQN が A* 解より短い手数でクリアするケースが出れば、それは「ヒューリスティックが実は許容的ではなかった」「process_turn 側に A* が辿り損ねる遷移が残っていた」のどちらかを示すシグナルになります。Stage 28 (53 手) や Stage 57 (52 手) など、IDA* で時間をかけて得た解を DQN で叩いて同値以下が出るかどうかを見るのは、正しさの間接検証として意味を持ちます。
2. 現行実装の DQN 実測値
学習済みチェックポイントを展開して現実的な到達点を確認すると、楽観的には見られません。
| Stage | マップサイズ | VBA 解 | IDA* / A* (許容的) | DQN best |
|---|---|---|---|---|
| 1 | 14 × 5 | 15 | (未計測) | 未クリア |
| 33 | 9 × 6 | 8 | 既に最短と推定 | 8 (一致) |
| 34 | 11 × 9 | 9 | 既に最短 | 11 (VBA より劣化) |
| 47 | 7 × 7 | 8 | 既に最短 | 8 (一致) |
7 〜 9 マス角の小規模ステージで、ようやく VBA / A* 解に追いつくのが精一杯というレベルです。Stage 34 は VBA の 9 手より悪い 11 手で頭打ちになっており、規模が上がるほど学習効率が落ちていく傾向がはっきり出ています。
3. 現設定のボトルネック
学習が頭打ちになる主因は次のとおりです。どれも単体で十分に効きますが、組み合わさると一層苦しくなります。
- 報酬が sparse — clear +100、step -1、death -100、ピクミン消費 +10 のみ。20 手を超える盤面では、ε=1 のランダム探索で一度もクリアに到達できない確率が高くなります。クリア報酬がごく稀にしか返ってこないため、学習信号がほとんど立ち上がりません。
- CNN 入力が盤面サイズ依存 — 全結合層の
flat_size = 64 × H × Wと設定しているため、ステージごとにネットワークを作り直す必要があります。つまり「あるステージで学んだ重み」を他のステージに流用できず、転移学習が実質的に不可能です。 - ε-decay の時定数 — 0.995 / エピソードの減衰だと、約 900 エピソードで ε ≈ 0.006 まで下がります。序盤のランダム探索でクリアを一度も踏めないままこの値に落ちてしまうと、不十分な方針のまま固定されてしまいます。
- 補助手法が未導入 — カリキュラム学習、報酬整形 (reward shaping)、n-step return、Double DQN のいずれも入れていません。素の DQN に ε-greedy を合わせた最小構成のままです。
4. 所要時間の見積もり
参考値として、Stage 47 (7 × 7、最短 8 手) は 1,500 エピソード、CPU で数時間の学習で best = 8 に到達しています。この設定をそのまま Stage 28 (30 × 11、最短 53 手) に適用した場合の見通しを素朴に見積もると次のようになります。
- 1 エピソードあたりの step 上限: 仮に 200 step
- 1 エピソード実時間: 盤面が Stage 47 比で約 7 倍、CNN forward も重くなる分を合わせて 10 〜 30 秒/ep (CPU)
- 53 手クリアへのランダム到達確率: ε=1 で $4^{-53} \times (\text{許容枝の割合})$。現実的な期待値はゼロに近く、reward shaping やカリキュラムがないと 105 〜 106 エピソード回しても 1 回もクリアに到達できない可能性が濃厚です。
素の設定で動かした場合の到達確率と実時間のオーダー感は下表のとおりです。いずれも精密な確率ではなく、あくまで桁のオーダーを揃えるための見積もりと読んでください。
| 目標 | 必要エピソード | CPU 実時間 | GPU 実時間 | 到達確率 |
|---|---|---|---|---|
| Stage 28 を 1 回でもクリア | 105+ | 週 〜 月単位 | 日 〜 週単位 | 10% 以下 |
| Stage 28 で VBA (61 手) に並ぶ | 106+ | 月単位 | 週単位 | 数 % |
| Stage 28 で IDA* 解 (53 手) に並ぶ | — | — | — | ほぼ 0 |
| Stage 57 (52 手) を更新 | — | — | — | 理論上 0 (IDA* が最適) |
結局のところ、本稿のスコープで素の DQN に期待できるのは「少ピクミン・短手数のステージで A* と同じ最適解を再現できること」までで、大規模ステージの最適解更新は原理的にも実装的にも届きません。更新を狙うなら、reward shaping やカリキュラム、パラメータ共有型のネットワーク (盤面サイズに依存しない GNN や Transformer 系) を導入したうえで、ベンチマーク対象ステージを段階的に広げる設計が必要になるでしょう。
まとめ
てくてくピクミン全 68 ステージを、Python の A* と C の IDA* ソルバーで調べました。最適性を確認できたのは 53 ステージで、うち 7 ステージは作者の VBA 解析解より短い解を発見できました (合計 -31 手の短縮)。残る 15 ステージはソルバーが状態数上限や時間切れで収束しきれず、VBA 解析解をそのまま採用しています。状態空間の規模が大きい Stage 28 と Stage 57 については、メモリ消費の少ない IDA* を C 言語で再実装することで最短解に到達できました。
技術面で得るところが多かったのは、ヒューリスティックの許容性 (admissibility) を実装レベルで意識することの重要性です。白ピクミンが条件付きで 2 マス進めるという特殊移動をヒューリスティックに反映しきれていなかった初期実装では、下界の見積もりが真の残コストを上回り、A* の最適性が局所的に崩れる事象が発生しました。$h(n) \le h^*(n)$ という条件は原理としては簡潔ですが、対象ゲームのルールを網羅する形で表現できているかは、実装を進めて挙動を観察して初めて気づく落とし穴があります。
未確認のまま残した 15 ステージについては、パターンデータベースや双方向探索など、別系統のアプローチが必要になると考えられます。機会があれば改めて取り組みたいところです。
本稿で触れた全ステージの最短解は、別途公開している解答一覧ページで可視化しています。再度リンクを貼っておきます: てくてくピクミン 解答一覧 (非公式ファン解析)
コメント