賢く探すAI：A*探索と対戦ゲーム

ゴールの方角が分かるなら

近い場所から順に調べる方法だと、ゴールと逆の道まで律儀に探してしまいます。

残りの距離を大まかに予測できれば、近そうな道から探せます。この手がかりがヒューリスティックです。

壁を無視して、マスを数える

予測値を返す関数をヒューリスティック関数 $h(n)$ と呼びます。迷路なら壁を無視してゴールまでのマス数を数えます。

横に3マス、縦に4マスなら $h = 7$。これがマンハッタン距離です。

マンハッタン距離で見積もる

問題：迷路でゴールまで横に2マス、縦に5マス離れています。壁があり実際は11歩かかるとき、マンハッタン距離による予測hはいくつ？

1. 7（正解）
2. 11
3. 10

解説：マンハッタン距離は壁を無視して、横と縦のマス数を足します。2と5で7です。実際の11歩より小さく出ることが、このあと大事になります。

予測値だけを追うと、遠回りする

$h$ が一番小さいマスばかり選ぶ方法を貪欲最良優先探索といいます。まっすぐ進むので速く着くことが多いです。

ただ手前に壁があると行き止まりに引っかかり、最短ではない道を選ぶことがあります。

歩いた分も足すA*探索

歩数 $g(n)$ を足した合計 $f(n)$ が最小の場所を選ぶのがA*探索です。

Aは $g=2,h=5$ で $f=7$、Bは $g=8,h=1$ で $f=9$。$h$ だけならBですが、A*はAを優先します。

A*探索はどちらを先に調べる？

問題：A*探索の候補が2マスあります。Aは歩いた歩数1・予測5、Bは歩いた歩数6・予測2。A*が先に調べるのはどちらで、なぜ？

1. A。歩数と予測の合計が6で、Bの8より小さい（正解）
2. B。予測が2で、Aの5よりゴールに近い
3. A。歩いた歩数が1で、Bの6より近場にある

解説：A*探索は歩数と予測値の合計で比べます。Aは1と5で6、Bは6と2で8なのでAを先に調べます。予測値だけで選ぶのは貪欲最良優先探索です。

予測は、甘めでいい

A*で必ず最短ルートを見つけるには、$h$ が実際の残り歩数を超えないのが条件です。

見積もりが大きすぎると近道を逃します。壁を無視したマス数なら超えません。

A*探索の最短保証

○か✕か

○か✕か：A*探索では、予測hが実際の残り歩数より大きくなっても、最短の道は必ず見つかる。

答え：✕。予測が大きすぎると、本当は近い道の合計が膨らんで後回しになります。その間に別の道で着くと最短を見逃します。hが実際の歩数を超えないことが条件です。

相手は、こちらが困る手を打つ

三目並べでは、どこに打っても相手は一番いやな手を返してきます。

勝ちを1点、引き分けを0点、負けを-1点とし、自分は最大、相手は最小を選ぶと考えて先を読むのがMinimax法です。

点が下から上がってくる

「次へ」を押し、相手の番では小さい点、自分なら大きい点が選ばれる様子を見ましょう。

Minimax法が選ぶ手は？

問題：三目並べで打てる手が2つあります。手Aは相手しだいで1点か-1点、手Bはどう返されても0点。Minimax法が選ぶのは？

1. 手B。最悪でも0点が残るから（正解）
2. 手A。うまくいけば1点で勝てるから
3. どちらでも同じ。平均はどちらも0点だから

解説：Minimax法は、相手が最高の手を返すと仮定します。手Aは-1点にされ、手Bは0点が残るのでBを選びます。勝てる見込みや平均ではなく、最悪の点で比べています。

結論が出たら、残りは読まない

手Aは、どう返されても4点が残ると分かっています。

手Bで2点にされる返しが1つ見つかればBは2点以下。残りを読まずに切るのがアルファ・ベータ枝刈りです。

枝刈りと最終判断

○か✕か

○か✕か：アルファ・ベータ枝刈りで読む手を減らしても、Minimax法が最終的に選ぶ手は変わらない。

答え：○。削るのは、読んでも結論が変わらない枝だけです。4点が残る手があるなら、2点以下の手は選ばれません。答えはそのままで、読む量だけを減らせます。

チェスは、最後まで読めない

三目並べの展開は全部で255,168通り。最後まで読み切れます。

チェスは約 $10^{29000}$ 通り。Minimax法で最後まで読むのは不可能です。

数手先で止めて、盤面に点をつける

そこで途中で読むのを打ち切り、その盤面がどちらに有利かを評価関数で採点します。駒の損得などから計算する予測値です。

最後の1点・0点・-1点の代わりにその点数を使えば、Minimax法はそのまま動きます。

賢い探索とゲームAI

• 迷路では、壁を無視したマス数でゴールまでを見積もる
• A*探索は、歩いた歩数と見積もりの合計が小さいマスから調べる
• 相手がいるゲームは、相手が最善を返すと仮定して最悪の点で比べる
• 結論が出た枝は、読まずに切る
• 読み切れないゲームは、途中の盤面を評価関数で点にする

読み切れない将棋AIが使うのは？

問題：将棋AIが10手先で読むのを止めました。その時点の盤面それぞれに点をつけて、手を比べるのに使うのは？

1. 盤面の有利さを点にする評価関数（正解）
2. 結論の出た枝を切るアルファ・ベータ枝刈り
3. 歩数と見積もりを足すA*探索

解説：おつかれさまでした。評価関数は迷路のhと同じく、先の見えない部分を見積もる道具です。では「雨が降れば傘を開く」「いま雨が降っている」から、見積もりではなく100%確かな結論を出すには？次は、言葉を「本当かうそか」の記号に直し、手がかりからあり得ない世界を消していく推理を見ます。