A* 探索とヒューリスティック設計の基本 — てくてくピクミンで追う実装ポイント

結論

A* (エースター) はスタートからゴールまでの最短経路を効率的に探すアルゴリズムです。Dijkstra 法に「ゴールまでの残り距離の見積もり」(ヒューリスティック) を加えたもの、と捉えると全体像が素早く掴めます。そしてヒューリスティックの設計、特に許容性 (admissibility) という性質が、A* が必ず最適解を返すための核になります。

本稿では A* の基本と、そこで使うヒューリスティックの設計のポイントをまとめて整理し、最後に『てくてくピクミン』の解析で実際にどう設計したかを工程ごとに紹介します。

こんな人向けの記事

最短経路アルゴリズムを初めて触るか、改めて復習したい方
A* のヒューリスティックが「正しい答えを返すため」に満たすべき条件を、具体例で見たい方
パズルの自動解法で A* を実装した経験があり、設計の落とし穴を知りたい方

このゲームでいう「コスト」とは

経路探索アルゴリズムの用語である「コスト」「ノード」「エッジ」を、『てくてくピクミン』の言葉に置き換えておきます。これ以降の節を読む際の辞書になります。

一般的な用語	『てくてくピクミン』での意味
ノード (頂点)	ある瞬間の盤面状態 (どのピクミンがどのマスに、岩や敵の残り具合)
エッジ (辺)	「上・下・左・右」のどれかを 1 回入力する操作
エッジのコスト	1 (入力 1 回 = 1 手)
パスのコスト	スタートからゴールまでに押した入力の総数 = 手数
最短経路	最小手数でクリアする手順

つまりこのゲームでは、「最小コストのパスを求める」は「最短手数でクリアする手順を求める」と完全に同じ意味になります。後ほど出てくる $g(n)$ は「その局面までに押した手数」、$h(n)$ は「その局面から最低あと何手かかるか」の見積もり、と読み替えてください。

例えば Stage 1 は 15 手、Stage 28 は 53 手でクリアできます。これは「A* の言葉でいうと、Stage 1 の最短パスのコストが 15、Stage 28 のそれが 53」ということに相当します。

A* の基本: f = g + h

A* は探索中の各ノード (局面) に対して、次の 2 つのコストを見積もります。

g(n): スタートからノード n まで実際に動いたコスト (これまでの手数)
h(n): n からゴールまでに必要と見積もる残コスト (ヒューリスティック)

両者の和 $f(n) = g(n) + h(n)$ を「そのノードの総コスト見積もり」として扱い、$f$ が小さいノードから優先的に展開していきます。

Dijkstra 法との関係 (軽い予習)

A* を理解するには、親戚にあたる Dijkstra 法 (ダイクストラ法) を先に掴んでおくと一気に見通しがよくなります。Dijkstra 法は最短経路探索の古典的なアルゴリズムで、以下のとても素朴な手順で動きます。

スタートから到達可能なノードをリストに入れ、各ノードに「スタートからのコスト」を記録する
リストの中からコスト最小のノードを取り出し、その隣接ノードへのコストを更新する
ゴールが取り出されたら終了、そのときのコストが最短コスト

一言でいうと「現時点でスタートから一番近いノードを、近い順に広げていく」だけの方法です。直感的ですが、これで必ず最短経路が見つかることが数学的に示されています。ただし「ゴール方向を考慮しない」ため、ゴールから遠ざかる方向にも均等に広がってしまい、盤面が大きいとかなり無駄な展開をしてしまいます。

A* はこの Dijkstra に「ゴールまでの残り距離の見積もり」$h(n)$ を加えたものです。数式で並べて比較すると違いがはっきりします。

Dijkstra 法: $f(n) = g(n)$ の小さい順に展開
A*: $f(n) = g(n) + h(n)$ の小さい順に展開

つまり A* に $h \equiv 0$ を入れれば Dijkstra と同じ動作になる、と覚えておくと関係が掴みやすいです。$h$ がゴール方向を指してくれる分だけ、A* は Dijkstra より賢くなります。

図 1: Dijkstra 法と A* の探索領域の違い。着色が濃いほど展開されたノードが多い領域を表す。

ヒューリスティック関数 h(n) とは

h(n) は「n からゴールまでの残コストの見積もり」を返す関数です。下から見積もる、つまり真の残コストより小さめ (あるいは等しい) 値を返すことが A* の最適性にとって大切です。

マンハッタン距離と BFS 実距離の違い

h の具体案として候補によく挙がるのが「マンハッタン距離」と「BFS 実距離」の 2 つです。違いは 1 点だけ、壁をどう扱うかに集約されます。

まず定義から整理します。

マンハッタン距離: 2 点 $(x_1, y_1)$ と $(x_2, y_2)$ の間の $|x_1 – x_2| + |y_1 – y_2|$。横方向の差と縦方向の差を単純に足したもの。壁や穴の存在は一切考慮しない。
BFS 実距離: ゴールから幅優先探索 (BFS) を走らせて求めた、壁を避けた本物の最短マス数。各マスに実際にそこまで「何歩で行けるか」が書き込まれる。

同じ盤面でこの 2 つがどう違うかを、具体例で見てみます。

図 2: ピクミン P からゴール G までの距離。壁 (灰色) が間にあり、直線 (赤点線) では通れない。実際は下のマスへ迂回して戻る経路が必要で、BFS 実距離は 7 マスになる。

ピクミン P から宝物 G を見ると、水平距離はたった 3 マスしかありません。これがマンハッタン距離 = 3 の正体です。しかし間に壁があって直進できず、実際には下の段に降り、右に進み、また上がってくる迂回路を通るしかありません。その経路は 7 マス分になり、これが BFS 実距離 = 7 です。

どちらも真の残コスト (= 7) を超えない値なので admissible (許容的) です。ただし見積もりの精度に大きな差があります。

マンハッタン距離 (h = 3) を使う A*: 「あと 3 手で着く」と楽観視して、遠回りのパスを何度も展開してしまう
BFS 実距離 (h = 7) を使う A*: 「あと 7 手必要」と現実的に見積もれるので、明らかに無駄な寄り道を早めに捨てられる

直感的には、マンハッタン距離は「鳥のように飛べたら何マス」、BFS 実距離は「歩いて行ったら何マス」という関係です。壁が多い盤面ほど 2 つの差が広がり、BFS 実距離の優位性が大きくなります。てくてくピクミンのステージは壁・穴・岩が頻繁に並ぶ設計なので、マンハッタン距離から BFS 実距離に切り替えただけで探索速度が数十倍変わるステージが多く見られました。

7	6		4	3	2
6	5		3		1
5	4	3	2	1	G
6	5	4	3	2	1

図 3: 宝物 G を起点とした多源 BFS 実距離。全マスに「壁 ■ を避けた実際の最短マス数」が事前計算され、h はこの表から O(1) で引き出せる。

ピクミンが 2 匹以上の場合の h の計算

てくてくピクミンは 1 ステージに 1 匹とは限らず、多いステージでは 10 匹ほどが同時に動きます。各ピクミンに対して BFS 実距離はそれぞれ得られますが、A* には 1 つのノードに対して 1 つの $h$ 値を返さなければなりません。つまり「複数の距離をどう 1 つの値にまとめるか」は実装上はっきり選ぶ必要のある設計判断になります。

本稿の実装では各ピクミンの残り距離の「最大値」を $h(n)$ としました。擬似コード風に書くとこうなります。

h(n) = max(残り距離[ピクミンの現在地] for ピクミン in 全ピクミン)

なぜ「最大」を選ぶのか

クリア条件は「全ピクミンがゴールに到達すること」なので、一番ゴールから遠いピクミンがボトルネックになります。そのピクミンがゴールに届くまでに最低限必要な手数より、クリアは絶対に早くなりえません。

具体例で見てみます。3 匹のピクミンがいて、それぞれのゴールまでの実距離が 2, 3, 8 マスだったとします。この場合、

距離 8 のピクミンがボトルネック。どう頑張っても少なくとも 8 手は必要
距離 2 と 3 のピクミンは、8 手のうちの一部で先にゴールに着く
したがって真の残コスト $h^*$ は必ず 8 以上になる

つまり「最大値 = 最遠ピクミンの距離」は、常に真の残コストを超えません。これが許容性を保つ理由です。

「合計」や「平均」はダメなのか？

直感的に「全ピクミンの距離を足したほうが精度が高くなりそう」と思うかもしれません。しかし合計は許容性を崩します。

同じ例で考えると、距離 2, 3, 8 の合計は 13。では実際のクリアに 13 手かかるかというと、そうとは限りません。同方向移動ルールの下では、全員が 1 ターンに同じ方向へ 1 マスずつ動くので、3 匹が横並びに配置されていれば、全員が同時に前進します。つまり「最遠 1 匹の距離」ですべて済むケースがあります。

もし合計 h = 13 を返したとしたら、真の残コスト (= 8) より大きく、これは $h(n) \le h^*(n)$ に違反します。A* は「このパスはもう長すぎる」と早々に切り捨て、最適解を見逃す可能性が出ます。

まとめ: 同方向移動ゲームでは「最大」

「最大」は、同方向移動ルール (全員が 1 ターンに同じ方向へ 1 マスずつ進む) の下で常に真の残コスト以下に収まるため、許容性を安全に保てます。複数エージェント系の経路探索では標準的な取り扱いで、てくてくピクミンもこれに従っています。

余談ですが、各ピクミンが独立に別の方向へ動けるゲーム (たとえば通常のピクミン本編のような操作系) だと話は別で、各ピクミンの手数の合計が下界になります。対象ゲームのルールで「どう h をまとめると許容的になるか」は毎回考え直す必要があります。

許容性

真の残コスト (n からゴールまでに実際に必要な最小コスト) を $h^*(n)$ と書きます。任意の n について $h(n) \le h^*(n)$ が成り立つとき、h は許容的であると言います。

許容的な h を使えば、A* が返す解は必ず最適解です。逆に h が $h^*$ を上回る場所があると、A* はそのノードを通るパスを「もっと悪い」と誤認し、実は短いはずの最適解を見逃します。

「これで最短」と言える根拠

「A* がクリア状態を展開したとき、それが本当に最短なのか？」という問いには、数学的にはっきりと Yes と答えられます。ポイントは 1 つだけで、ヒューリスティック $h$ が許容的であること。条件が満たされていれば、A* が止まった時点で得られた手数は最短と確定します。

直感的なイメージ

図 3: 許容性が保証されている限り、A* の優先度付きキューは f 値の小さい順に取り出され、GOAL が出た瞬間に最短が確定する。

A* は毎回「今わかっている中でもっとも有望 (= $f$ が最小) なノード」を次に展開します。許容的な $h$ は「残り距離を決して過大評価しない」と保証してくれるので、$f(n) = g(n) + h(n)$ も「そのノードを通る最短パスの下界」として決して過大評価しません。

言い換えると、もし「A* がまだ見ていないもっと短いパス」があったとしても、そのパス上のノードの $f$ 値はそのパスの長さを越えません。A* は $f$ が小さい順に展開するので、そうしたノードは必ず先に展開されています。ゴールを展開した瞬間までに A* はすでに「より短いパスの候補」をすべて潰してきた、というのが最適性の直感的な説明です。

背理法による証明スケッチ

A* がゴールを展開したときに返した手数を $g(\text{goal})$ と書きます。もし「もっと短い、未発見のパス」があると仮定します。そのコストを $C^*$ とすると、$C^* < g(\text{goal})$ です。

未発見ということは、そのパス上のどこかに未展開のノード $n$ が OPEN (これから展開される候補リスト) に残っています。この $n$ の $f$ 値を評価すると次の不等式が成り立ちます。

$$f(n) = g^*(n) + h(n) \le g^*(n) + h^*(n) = C^*$$

順に見ていきます。

1 つめの等号: $f$ の定義から、$f(n)$ は「$n$ までのコスト $g^*(n)$ と残り見積もり $h(n)$ の和」
2 つめの不等号: 許容性 $h(n) \le h^*(n)$
3 つめの等号: $g^*(n) + h^*(n)$ は「$n$ を通る最短パスの全コスト $C^*$」に等しい

つまり $f(n) \le C^*$ です。一方、ゴールノードの $f$ 値は $f(\text{goal}) = g(\text{goal}) + h(\text{goal}) = g(\text{goal})$ (ゴールでは $h = 0$) になります。ここから次の不等式が立ちます。

$$f(n) \le C^* < g(\text{goal}) = f(\text{goal})$$

A* は $f$ が最小のノードを先に取り出す規則で動くので、$f(n) < f(\text{goal})$ なら $n$ はゴールより先に展開されていなければなりません。これは「$n$ が未展開で OPEN に残っている」という最初の仮定と矛盾します。

論理の核心

矛盾が生じたので、最初の仮定「もっと短い未発見のパスがある」は誤りです。したがって A* がゴールを展開した時点で返す $g(\text{goal})$ が、本当の最短コストになります。

この証明の核心は、許容性のおかげで、未展開のノードの $f$ 値が真の最短コストを上回らない点です。逆に $h$ が一度でも $h^*$ を超えると、$f(n) \le C^*$ の不等式が崩れ、最適解を取りこぼす余地が出ます。これが、A* の最適性保証にとって許容性を守ることが何より重要な理由です。

てくてくピクミンの解析でも、この性質に基づいて「A* がクリア状態を確定した時点で、その手数が最短」と断言できます。独立な 2 つの実装 (Python A* と C IDA*) が同じ答えを返したステージでは、どちらも許容性を守っているので、同じ数学的根拠で最短性が保証されている格好です。

コラム: これって総当たり法と同じ？

ここまで読むと、「結局 A* も『ひたすら手を試して最短を探す』という総当たり法 (ブルートフォース) と同じなのでは？」という疑問が湧くかもしれません。結論から言うと、得られる答えは同じだが、試す手数のスケールが別物、というのが正直な関係になります。

純粋な総当たり法で Stage 28 (最短 53 手) を解こうとすると、各ターンに上下左右の 4 択があるので、理論上は $4^{53} \approx 8.1 \times 10^{31}$ 通りの操作列を試すことになります。1 秒で 10 億通り試せる計算機を使っても、終わるまでに宇宙年齢 (約 $10^{17}$ 秒) をはるかに超える時間を要します。純粋な総当たりは、このゲームには現実的に使えません。

A* もノードを展開して状態空間を探索する点は同じですが、2 つの仕組みで実用的な時間に収まるよう削られています。

重複局面の排除: 同じ盤面状態 (map_code) を二度展開しないよう、辞書で管理します。「右 → 左 → 右 → 左」のような行ったり来たりで生まれる重複は、同一ノードとして 1 回分にまとめられます。
ヒューリスティックによる優先順位付け: $f = g + h$ が小さい順に展開するので、明らかにゴールから遠ざかる方向を後回しにできます。許容性が保たれている限り、後回しにしたところに最適解が隠れていることはありません。

実際、Stage 28 で A* / IDA* が展開したノード数は約 4,500 万個でした。総当たりの $8.1 \times 10^{31}$ と比べると、およそ 24 桁小さい規模です。同じ最短手数にたどり着くのに、これだけ探索量を削れるかどうかが、A* を「ただの総当たり」から引き離している本質と言えます。

逆に言えば、$h \equiv 0$ に設定するとヒューリスティックの恩恵が完全に失われ、A* は Dijkstra と等価になります。そうなると削減効果は「重複排除」だけに縮小し、総当たり寄りに戻ります。「総当たりではない」と言い切れるかどうかは、許容性を守った上でどれだけ実コストに近い h を用意できるかにかかっている、と整理できます。

整合性 (consistency)

より強い条件として「整合性」があります。任意のエッジ $n \to n’$ (コスト c) について $h(n) \le c + h(n’)$ が成り立つとき、h は consistent であると言います。

consistent な h は必ず許容的ですが、許容的だからといって consistent とは限りません。consistent な h では A* のノード再展開が不要で計算量が抑えられ、非整合な許容的 h では best_g 辞書による再展開で最適性を補償できます。

よくある h の候補

マンハッタン距離 — グリッド迷路の定番。斜め移動なしなら許容的かつ consistent。壁を無視するので過小評価気味。
ユークリッド距離 — 連続空間の直線距離。壁を無視する点はマンハッタン距離と同じ。
BFS 実距離 — 壁を考慮した最短マス数。事前計算は必要だが精度が高く、A* との相性もよい。
パターンデータベース — 小問題の完全解を表に持ち、残コストを引き出す。15 パズルなどで使われる。

てくてくピクミンでの設計工程

カードe+のミニゲーム『てくてくピクミン』全 68 ステージの最短解を求めるために、A* とヒューリスティックを次の順で設計していきました。

状態の定義 — 盤面 (ピクミンの位置と色、岩や敵の残存状況) を 1 本の文字列 map_code にシリアライズ。同一局面を辞書で同じキーに落とし込みます。
近傍の定義 — ある局面からの遷移は「上・下・左・右のどれかを押す」の 4 通り。ルール通りにピクミン全員を動かして次局面を生成します。
初期ヒューリスティック — 各ピクミンから宝物までのマンハッタン距離の最大値を h としました。実装は軽いのですが、壁や穴を無視するため過小評価となり、探索が広がり過ぎて速度が出ませんでした。
改良ヒューリスティック — 宝物マスを起点に多源 BFS を 1 回走らせ、盤面全体の実距離テーブルを事前計算。各ピクミンの現在地をテーブルから引くだけで精度の高い h が得られ、探索は数十倍速くなりました。
白ピクミン問題の発覚と修正 — 白ピクミンは 1 ターンに最大 2 マス進める特殊能力があります。距離 d のマスに居る白ピクミンに h = d を返すと、真の残コスト (約 d/2 ターン) を上回り許容性が崩れ、A* が最適解より 1 手多い解を返しました。白ピクミンのみ $\lceil d/2 \rceil$ に補正して許容性を回復させています。

図 4: 白ピクミンの距離を半減する補正。特殊移動を無視すると h が真の残コストを超え、A* が最適解を取りこぼす。

def heuristic(state, bfs_dist):
    max_dist = 0
    for ent in state.entities:
        d = bfs_dist[ent.y][ent.x]
        if ent.color == 'white':
            d = (d + 1) // 2   # 1 ターンに 2 マス進めるため半減
        max_dist = max(max_dist, d)
    return max_dist

この設計で、68 ステージ中 51 ステージについて数秒〜数分で最短手数を確定できました。大規模ステージでメモリが足りなくなった Stage 28 と Stage 57 は、別記事「IDA* とは？」で扱う IDA* に切り替えて解いています。

まとめ

A* は「Dijkstra 法 + ゴール方向のヒント」と捉えると一気に見通しが良くなる探索手法です。ヒントに当たる $h$ の設計、特に許容性 $h(n) \le h^*(n)$ の担保が、A* の最適性を左右します。複数エージェント問題では「各エージェントの残りコストの最大値」を使うのが典型で、同方向移動ルールのもとで許容性を崩しません。

てくてくピクミンの解析でも、宝物マスからの BFS 実距離に白ピクミンの 2 マス移動を反映する補正を加えることで、「過小評価すぎず、過大評価もしない」バランスの取れたヒューリスティックを組めました。実装が許容性を守っている限り、A* がクリア状態を展開した瞬間にその手数が最短だと数学的に断言できます。

全ステージの解析結果と実装の詳細は、本編記事「てくてくピクミン全 68 ステージの最短解 — A* 探索の実装とヒューリスティック設計」でまとめています。