ミニマックス法と基本情報「問15」

完全情報ゲーム（三目並べ・オセロ・将棋など）で次の一手を決めるアルゴリズムです。このツールは基本情報技術者試験 科目B「問15」の手順を体験できます。

1. 基本思想 (MAX-MIN)

自分は自分に有利な手を選びますが、相手も自分（相手）に有利＝こちらに不利な手を選びます。そこで 「自分は最善(MAX)、相手も最善(MIN)を打つ」と仮定して、最終的に最も良い結果になる手を選びます。

2. 評価値（問15の定義）

盤面は常に自分（○）の視点で評価します。

葉以外の節は、自分の手番なら子の最大値、相手の手番なら子の最小値を評価値とします。

3. ツリーの見方

あなたの手番のとき、盤面のマスにマウスを乗せると「そこに○を打った場合」の探索ツリーと評価値が下部に表示されます。終盤（空き6マス以下）は葉まで全て展開し、序盤は深さを制限して表示します（評価値は常に最後まで読み切った正確な値です）。マスの隅の数字は、その手を打ったときの評価値（自分視点）です。

4. 先読みの深さと枝刈り（理論）

三目並べは最後まで読み切れますが、将棋などは計算量が爆発するため「N手先まで」と深さを制限し、明らかに不利な経路の計算を打ち切る「アルファベータ枝刈り」を使います。AIの強さは「先読み深さ」で変えられます。

MAX-MIN_TIC_TAC_TOE

自分=○(青) / 相手=×(赤)　マスにマウスを乗せると木構造と評価値を表示

先手:
AI先読み深さ:
システムを起動しています...

探索ツリー（思考プロセス）

自分(○)は有利(MAX)、相手(×)はこちらに不利(MIN)な手を選ぶと仮定します。
評価値（自分視点）： +10 自分の勝ち / 0 引き分け / -10 自分の負け　 緑枠＝その手番で選ばれる手

あなたの手番のとき、盤面のマスにマウスを乗せるとツリーが表示されます。