AI学習コースゲーム理論と高度な探索手法
将棋やチェスで人間のプロを倒すAIは、どのような仕組みで「最善の手」を見つけ出しているのでしょうか？この記事では、ゲームAIで使われる高度な探索手法について、身近な例を使って分かりやすく解説します。
ゲーム理論ってなに？
はじめに、ゲーム理論という学問について紹介します。
ゲーム理論とは、要するに「相手がいる状況で、どう行動すれば最も得をするかを考える学問」です。ここでいう「ゲーム」は、テレビゲームのことではなく、「戦略的な駆け引きが必要な状況」のことを指します。
日常生活での例：
- じゃんけん：相手が何を出すかを予想して、勝てる手を出す
- 交渉：相手の条件を予想して、自分に有利な提案をする
- 投資：他の投資家の行動を予想して、利益を最大化する
ゲームAIの場合：
- 将棋：相手がどう指してくるかを予想して、最善の手を選ぶ
- 囲碁：相手の戦略を読んで、有利な局面を作り出す
要するに、「相手も賢く行動する」という前提で、自分の戦略を決める技術です。
このように、ゲーム理論は「対戦相手がいる状況での最適戦略」を科学的に分析する手法であり、ゲームAIの基礎となっています。
Mini-Max法（ミニマックス法）
次に、ゲームAIの核心アルゴリズムであるMini-Max法について説明します。
Mini-Max法とは、要するに「相手が最善を尽くしてくることを前提に、自分にとって最も悪い結果を最小限に抑える方法」です。
■基本的な考え方
想像してみてください。あなたが将棋を指していて、3手先まで読めるとします：
- 自分の手番：できるだけ良い結果になる手を選びたい（Max）
- 相手の手番：相手は自分にとって悪い結果になる手を選んでくる（Min）
- 自分の手番：また、できるだけ良い結果になる手を選ぶ（Max）
具体例（三目並べ）：
現在の局面：
X | O |
---------
| X |
---------
| | O
自分（X）の番で、どこに置くべきか？
Mini-Max法では：
- 可能な手をすべて考える（9個のマス目のうち空いている6箇所）
- それぞれの手について、相手の最善手を予想する
- 相手が最善を尽くした場合の結果を評価する
- 最も悪い結果が最も良い手を選ぶ
■評価関数
評価関数とは、要するに「その局面がどれくらい有利かを数値で表す仕組み」です。
たとえば、将棋の場合：
- 駒の価値：歩兵=1点、飛車=10点、王将=1000点
- 駒の位置：攻めやすい位置にある駒はプラス点
- 形勢：攻撃態勢が整っているかマイナス点
たとえば、チェスの場合：
- ポーン=1点、ルーク=5点、クイーン=9点
- 中央を支配していると+2点
- キングの安全性が高いと+3点
要するに、「この局面は自分にとってどれくらい良いか」を数値化したものです。
Mini-Max法と評価関数を組み合わせることで、コンピュータが相手の作戦を読みながら最適手を選択できるようになります。
αβ法（アルファベータ法）
続いて、Mini-Max法を大幅に高速化するαβ法について解説します。
αβ法とは、要するに「明らかに悪い手は途中で計算をやめて、効率化する方法」です。Mini-Max法の改良版で、同じ結果をより速く計算できます。
■基本的なアイデア
人間が将棋を考えるとき、「この手は明らかにダメだな」と思ったら、それ以上深く考えないですよね。αβ法も同じ発想です。
具体例：
- A手を調べたら、結果が+5点だった
- B手を調べ始めたら、途中で-3点になることが確定した
- この時点で、B手はA手より悪いことが確定
- B手の残りの計算をスキップして、次のC手を調べる
効果：
- 計算時間が約半分になる
- より深く先読みできるようになる
- 同じ時間でより強いAIが作れる
■剪定（プルーニング）
剪定とは、要するば「無駄な枝を切り落とすこと」です。探索木の中で、明らかに最適解につながらない部分の計算を省略します。
たとえば：
Max（自分）
/ \
+5 Min（相手）
/ \
-3 ?
右側の？の部分は、すでに-3以下であることが確定しているので、
詳しく計算しなくても左側の+5の方が良いことが分かる
αβ法を使うことで、同じ結果を約半分の計算時間で得ることができ、より深く探索した強いAIを作ることが可能になります。
歴史的なAIシステム
次に、ゲーム理論を実装した初期の重要なAIシステムについて紹介します。
■SHRDLU（1968-1970年）
SHRDLUとは、要するに「積み木の世界で自然言語を理解できる初期のAI」です。
何ができたか：
- 「赤い積み木を青い積み木の上に置いて」という指示を理解
- 積み木を実際に動かす（コンピュータ画面上で）
- 「なぜその積み木を動かしたのか」を説明できる
重要な意味：
- 自然言語（普通の日本語や英語）をコンピュータが理解した最初の例
- ただし、非常に限定された「積み木の世界」でのみ動作
たとえば：
- 人間：「大きな赤い積み木はどこにありますか？」
- SHRDLU：「大きな赤い直方体は、現在テーブルの上にあります」
- 人間：「それを緑の積み木の上に置いてください」
- SHRDLU：「はい」（実際に動かす）
■STRIPS（1971年）
STRIPSとは、要するに「目標を達成するための行動計画を自動的に立てるシステム」です。
基本的な仕組み：
- 現在の状態：今どうなっているか
- 目標状態：どうなりたいか
- 可能な行動：何ができるか
- 計画：目標を達成するための行動の順序
たとえば、掃除ロボットの場合：
- 現在の状態：リビングにいる、バッテリー80%、ゴミ袋空
- 目標状態：全部屋掃除完了、充電台に戻る
- 可能な行動：移動、掃除、ゴミ袋交換、充電
- 計画：リビング掃除→寝室掃除→ゴミ袋交換→充電台へ移動
影響：
- 現在のロボット工学の基礎となった
- スマートフォンのAIアシスタントも、STRIPSの考え方を使っている
SHRDLUとSTRIPSは、現在のAI技術の原型となったシステムであり、今日のAIアシスタントや自動推論システムの基礎となっています。
現代のゲームAI
続いて、これらの理論が実際に人間を凄駕した現代のAIシステムについて解説します。
■Deep Blue（チェス）
Deep Blueとは、要するに「1997年に世界チェス王者を倒したIBMのコンピュータ」です。
技術的特徴：
- 1秒間に2億手の計算が可能
- 12手先まで先読み
- 巨大な評価関数（70万行のプログラム）
歴史的意義：
- AIが人間の世界チャンピオンを倒した最初の例
- 「コンピュータが人間を超える」ことの象徴的な出来事
■AlphaGo（囲碁）
AlphaGoとは、要するに「2016年に世界囲碁チャンピオンを倒したGoogleのAI」です。
従来の方法との違い：
- Mini-Max法だけでなく、機械学習も使用
- 過去の棋譜から「良い手」を学習
- モンテカルロ法でランダムな対局をシミュレーション
なぜ囲碁は難しかったか：
- 盤面が19×19=361マスと広い
- 可能な手の数がチェスの10^50倍
- 局面の評価が複雑（どちらが有利か判断が困難）
たとえば：
- チェスの可能な局面数：約10^50
- 囲碁の可能な局面数：約10^170
- 宇宙の原子の数：約10^80
要するに、囲碁は宇宙の原子の数より多くの可能性があるゲームなのです。
Deep BlueとAlphaGoの成功により、AIが人間の直感や経験を上回る戦略を編み出せることが証明されました。
推論システムの基礎
最後に、ゲームAIで使われる推論システムの基本概念について解説します。
■前向き推論と後向き推論
前向き推論とは、要するに「与えられた事実から結論を導き出す方法」です。
たとえば：
- 事実：「今日は雨が降っている」
- ルール：「雨が降っていたら傘を持って行く」
- 結論：「傘を持って行く」
後向き推論とは、要するに「結論から逆算して、必要な条件を探す方法」です。
たとえば：
- 目標：「大学に合格したい」
- 逆算：「合格するには試験で80点以上必要」
- 逆算：「80点取るには毎日3時間勉強が必要」
- 行動：「毎日3時間勉強する」
■実際の応用
医療診断システム：
- 前向き推論：症状から病気を推定
- 後向き推論：病気の診断から必要な検査を決定
カーナビゲーション：
- 前向き推論：現在地から行ける場所を計算
- 後向き推論：目的地から逆算して最適ルートを計算
前向き推論と後向き推論を組み合わせることで、効率的で実用的な推論システムを構築できます。
まとめ
ゲームAIの探索手法は、単純な「総当たり」から始まって、効率的な剪定技術、そして機械学習との組み合わせまで大きく進歩してきました。たとえば、現在のスマートフォンでも、1990年代のスーパーコンピュータより強い将棋AIが動いています。
要するに、これらの技術は「限られた時間の中で、できるだけ良い判断をする」という、人間の思考プロセスをコンピュータで再現し、さらに人間を超える性能を実現した技術なのです。
次回は、AIが知識をどのように表現し、整理するかという「知識表現とオントロジー」について、同じように分かりやすく解説していきます。