Mini-Max法（ミニマックス法）
解説
Mini-Max法（ミニマックス法）とは、チェス、将棋、オセロなどの「二人零和有限確定完全情報ゲーム」において、次の手を決定するための探索アルゴリズムです。
「最大（Max）」と「最小（Min）」のせめぎ合い
このアルゴリズムは、以下の仮定に基づいて思考します。
- 自分（Maxプレイヤー）：自分の評価値（利益）が最大になるような手を打つ。
- 相手（Minプレイヤー）：こちらの評価値（利益）が最小になるような手（こちらにとって一番嫌な手）を打ってくる。
ゲーム木を深さ優先で探索し、末端（数手先）の局面の評価値を出します。そこから、「相手は最小の手を選ぶ」「自分は最大の手を選ぶ」という計算を交互に繰り返しながら現在の手まで遡り（バックトラック）、最善手を決定します。
弱点と改良（αβ法）
Mini-Max法は全ての可能性をしらみつぶしに調べるため、局面が増えると計算量が爆発します。そこで、明らかに調べる必要のない枝（選ばれる可能性がない手）を計算から除外して高速化する「αβ法（アルファベータ法）」とセットで使われるのが一般的です。
G検定対策
出題ポイント
- 適用対象：二人零和ゲーム（自分の得＝相手の損）。
- 仕組み：ゲーム木探索。「自分はMax、相手はMin」を選ぶという前提。
- 関連用語：αβ法（枝刈りによる高速化）、モンテカルロ木探索（ランダムなプレイアウトによる確率的探索・Mini-Maxとは対照的な手法）。
よくあるひっかけ問題
- × Mini-Max法は、相手がミスをすることを期待して手を決める
（解説）違い、「相手も常に最善（こちらにとって最悪）の手を打ってくる」という性悪説の前提で計算します。 - × 確率的に勝率の高い手を選ぶ手法である
（解説）それはモンテカルロ法などの説明です。Mini-Max法は評価関数に基づく決定論的なアルゴリズムです。
