ゲームのキャラはどうやって道を探すのか、A*と見込みの距離

まず記号を決める。出発点$s$から点$n$までの本当の最短距離を$g^{\ast }(n)$、$n$からゴール$t$までの本当の最短距離を$h^{\ast }(n)$、$s$から$t$までの最短距離を$C^{\ast }$と書く。$g(n)$のほうは、探している途中で$n$まで見つかった経路のうち、いちばん短いものの長さだ。線の長さは正、見込みはどこでも本当の残り以下（$h(n)\le h^{\ast }(n)$）、ゴールでは$h(t)=0$とする。調べ終えた点にもっと短い経路が見つかったら、その点は候補に戻す。1968年の論文が示した手順も、この形だった。

1. 最短経路を1本とり、$P$とする。ゴールをまだ取り出していないとき、$P$上で$g=g^{\ast }$になっている調べ終えた点のうち、いちばん先にある点を$n_0$とする。$n_0$を調べたとき、$P$上で次に来る点$n^{\prime }$には$n_0$を通る長さ、つまり本当の最短距離が書き込まれた。$n^{\prime }$が調べ終えた点なら$n_0$の決め方に反するので、$n^{\prime }$は候補に残っている。

   $$g(n^{\prime })=g^{\ast }(n^{\prime })$$

2. $n^{\prime }$は最短経路上にあるので、$n^{\prime }$までの最短距離と$n^{\prime }$から先の最短距離を足すと、全体の最短距離になる。

   $$g^{\ast }(n^{\prime })+h^{\ast }(n^{\prime })=C^{\ast }$$

3. 見込みが本当の残りを超えないことを使う。

   $$f(n^{\prime })=g(n^{\prime })+h(n^{\prime })\le g^{\ast }(n^{\prime })+h^{\ast }(n^{\prime })=C^{\ast }$$

4. 遠回りでゴールに着いた経路が候補にあっても、$h(t)=0$なので$f(t)$はその経路の長さそのもので、$C^{\ast }$より大きい。先に取り出されるのは$n^{\prime }$のほうである。

   $$f(t)=g(t)>C^{\ast }\ge f(n^{\prime })$$

5. したがって、ゴールが取り出されるのは、記録された長さが$C^{\ast }$まで下がったときだけである。マス目のように点の数が有限なら、手順はいつか止まる。

   $$g(t)=C^{\ast }$$

証明を書き直す前、筆者は、見込みが探索を速くするのだから証明でも見込みが主役だろうと思っていた。

ところが手順1は、見込みに何も頼っていない。見込みが効くのは手順3の1行だけで、そこで$h\le h^{\ast }$が要る。1968年の論文は、こうして必ず最短経路を見つける探し方を許容的（admissible）と呼び、定理1として示した。

同じ不等式の鎖を使えば、見込みを$w$倍したとき（$w\ge 1$）に道がどこまで伸びるかも抑えられる。

6. $f(n)=g(n)+wh(n)$で順番を決めると、手順3は次の形になる。

   $$f(n^{\prime })\le g^{\ast }(n^{\prime })+w{h}^{\ast }(n^{\prime })\le w(g^{\ast }(n^{\prime })+h^{\ast }(n^{\prime }))=w{C}^{\ast }$$

7. ゴールを取り出すときは候補の中で$f(t)$が最小なので、見つかる経路は最短の$w$倍を超えない。

   $$g(t)=f(t)\le f(n^{\prime })\le w{C}^{\ast }$$

1968年の論文には、もう1つの条件が出てくる。どの線$m\to n$についても、見込みが三角形の辺のような関係を満たすことだ。線の長さを$c(m,n)$と書く。

1. 一貫性（consistency）の条件。1歩進んだ先の見込みに1歩の長さを足すと、元の点の見込み以上になる。

   $$h(m)\le c(m,n)+h(n)$$

2. 線の長さを、見込みの差で付け替える。条件1から、付け替えた長さは負にならない。

   $$c^{\prime }(m,n)=c(m,n)-h(m)+h(n)\ge 0$$

3. $s$から$t$までの経路で$c^{\prime }$を足すと、途中の$h$は打ち消し合い、両端だけが残る。どの経路でも差は同じ$h(s)$なので、$c^{\prime }$で最短の経路は$c$でも最短である。

   $$\sum c^{\prime }=\sum c-h(s)+h(t)=\sum c-h(s)$$

4. Aが比べる$f(n)$は、$c^{\prime }$で測った$s$からの長さ$g^{\prime }(n)$に定数$h(s)$を足したものになる。つまりAは、付け替えた地図で動かすダイクストラ法そのものだ。

   $$f(n)=g(n)+h(n)=g^{\prime }(n)+h(s)$$

5. 長さが負でない地図でダイクストラ法を使えば、取り出した点の長さはその時点で確定する。だからA*でも、調べ終えた点を候補に戻す必要がない。

   $$g(n)=g^{\ast }(n)(n\text{ を取り出した時点})$$

直線距離は、この条件をいつも満たす。$m$から$n$への道は直線$mn$より短くなれず、直線距離どうしには三角不等式が成り立つからで、論文も町と道路の例で同じ計算をしていた。オクタイル距離も同じで、1歩の長さ1か$\sqrt{2}$が、その1歩ぶんのオクタイル距離に等しい。

条件を破る例として、論文は、奇数番目の町には直線距離を、偶数番目の町には1を見込みに使う規則を挙げた。出発点の見込みが8なのに、そこから6だけ離れた偶数番目の町では見込みが1になり、$6+1<8$で条件が崩れる。論文によれば、偶奇や乱数のように地図と関係なく点ごとに変わる値で見込みを作ると、条件は破れやすい。

1972年12月、3人は学会ACMの人工知能部会が出す会報に訂正を載せた。カリフォルニア州立大学フラトン校のロン・コールマンが、A*が調べる点は最も少ないという定理について、その証明が実は一貫性を使っていないと指摘したのである。それでも訂正は、調べ終えた点で$g=g^{\ast }$となる性質には一貫性が要り、この性質があれば調べ終えた点を候補に戻す処理を省けるとして、一貫性は「実用上の意味を持ちうる」と結んだ。

話はここで終わらなかった。1985年、リナ・デクターとジューディア・パールは、見込みが本当の距離を超えないことしか仮定しないなら、Aは調べる点が最も少ない手順ではなく、最も少ない手順はそもそも存在しないことを示した。見込みが一貫性も満たす場合に限って比べれば、Aはやはり最も少ない点で済む。