勝ち手を読むAI──Mini-Max法、αβ法
盤の前に、AIが座っています。
将棋でも、チェスでもいい。目の前には、いくつもの未来が枝分かれしています。
この手を打ったら、相手はこう来る。そうしたら、こちらはこう返す。さらに相手は……。まだ起きていない未来が、何層にも重なって広がっています。
ここでAIが使うのが、Mini-Max法。
自分は、いちばん良くなる手を選ぶ。相手は、いちばんこちらが困る手を選ぶ。
つまり、
自分は「最大（Max）」を目指し
相手は「最小（Min）」を選んでくる
と仮定して、その中でそれでも一番マシな未来を探す。
でも、未来を全部読もうとすると、分岐が多すぎて、時間がいくらあっても足りません。枝、枝、枝。無限に増える未来。
そこで登場するのが、αβ法。
これはMini-Maxの相棒。
「もう、この先を見なくても、この道はダメだとわかったら、そこで打ち切ろう。」
つまり、すでにもっと良い選択肢があるなら、明らかに負ける枝は途中で切り捨てるのです。未来を全部見ない。見なくていい未来は、見ません。
Mini-Maxが真面目に全部考えようとするタイプなら、αβ法は空気を読んで黙るタイプ。
この二つが組み合わさって、AIは、相手の出方を想像し、最悪を受け入れたうえで、それでも一番ましな一手を選ぶようになります。
第１次AIブームの時代、これはとても画期的でした。AIはもう、ただ迷路を歩くだけじゃなく、対話する未来を読むようになったのです。
道を一つずつ探すAI──探索木（幅優先探索/深さ優先探索/ブルートフォース）
目の前に、迷路があります。
分かれ道。また分かれ道。その先にも、さらに分かれ道。どこがゴールかは、わからない。
AIは、ここに立たされます。
まずAIは、頭の中に地図を描きます。
この分かれ道からは、ここへ行ける。そこからは、さらに二つに分かれる。
こうして作られるのが、探索木。
未来の可能性を、枝分かれした「木」の形で表したもの。
幅優先探索──近くから順番に見る
幅優先探索は、とても慎重。
まずは、今いる場所のすぐ近く。次に、その一歩先。さらにその先。
同じ深さの道を、横に広がるように確認していく。
ゴールが近くにあれば、見つけやすい。でも、探索範囲がすぐ広がって、メモリをたくさん使う。
深さ優先探索──とりあえず奥まで行く
深さ優先探索は、幅優先探索とは、真逆。
一本の道を、行けるところまで、ぐーっと進む。行き止まりになったら、戻って別の道へ。
メモリは少なくて済むけど、遠回りになることも多い。
ブルートフォース──総当たり
いちばん原始的な方法、ブルートフォース。
可能性を、全部調べます。
賢くない。効率も悪い。でも、確実。
計算量が爆発するから、現実サイズの問題には向きません。
でも、「何も工夫しない探索」として、すべての基準になる存在。
確率で未来をのぞくAI──モンテカルロ法
ここまでのAIは、とても真面目でした。
Mini-Maxは、未来をできるだけ正確に読もうとしました。
探索木たちは、道を一つずつ、律儀に歩きました。
でも、あるとき人々は気づきます。
未来は、広すぎる。分岐は、多すぎる。全部見るなんて、無理……。
そこで、少し考え方を変えてみます。
「全部調べなくてもいい。実際にたくさんたくさん試してみればいいんじゃない？」
こうして登場するのが、モンテカルロ法。
やり方は、とても大胆。
可能性の中を、ランダムに、何度も歩いてみる。
右へ行った未来。左へ行った未来。たまたま良かった未来。たまたま悪かった未来。
それを何百回、何千回と繰り返して、「この道、なんとなく勝率高そう」という場所を見つける。
全部の道を調べない。代わりに、サイコロを振るみたいに、いろんな未来を軽やかに試す。
そして統計的に、「ここ、希望が多いね」という方向を選ぶのです。
これは、これまでの探索と決定的に違うところ。
Mini-Maxは、最悪を想定して慎重に選ぶ。
幅優先や深さ優先は、決められた順番で歩く。
でもモンテカルロ法は、勘と確率で進む。たくさん転びながら、「だいたい良さそう」な未来を見つけるAI。
この考え方は、のちに、ゲームAIや強化学習、さらに第３次AIブームの技術とも結びついていきます。