ミニマックス法

ミニマックス法について

ミニマックス法（Minimax Algorithm）は、1928年にジョン・フォン・ノイマンによって提唱されたゲーム理論の基本的なアルゴリズムです。 このアルゴリズムは、対戦型ゲームにおいて「相手が最善を尽くす」という最悪のケースを想定し、その中で自分にとって最も有利な手を選択します。

「ミニマックス」という名前は、自分のターン（MAX層）では評価値を「最大化」し、相手のターン（MIN層）では評価値を「最小化」することに由来しています。 この交互の最大化・最小化により、両者が最善を尽くした場合のゲームの結果を予測できます。

アルゴリズムの流れ

1. ゲームツリーの構築: 現在の盤面から可能なすべての手を列挙し、それぞれの手を打った後の盤面を子ノードとして展開します。 これを再帰的に繰り返し、ゲームが終了する（勝敗が決まる or 引き分け）まで続けます。
2. 終端ノードの評価: ゲームが終了した盤面（終端ノード）に対して、評価関数で点数をつけます。 例えば、自分の勝ちなら+10、相手の勝ちなら-10、引き分けなら0といった具合です。
3. 評価値の伝播: 終端ノードから親ノードへ評価値を伝播させます。 MAX層（自分の手番）では子ノードの中で最大の評価値を選び、MIN層（相手の手番）では最小の評価値を選びます。
4. 最善手の選択: ルートノードまで評価値が伝播したら、最も高い評価値を持つ子ノードに対応する手が最善手となります。

特徴と応用

• 完全性: ゲームツリー全体を探索するため、必ず最善手を見つけることができます
• 決定論的: 同じ盤面に対しては常に同じ手を選択します
• 計算量: O(b^d) - 分岐数bの深さdまでの探索。チェスでは計算量が膨大になります
• チェス・将棋AI: Deep BlueやAlphaZeroなどの基礎となっています
• オセロ・囲碁: 評価関数と組み合わせて実用的なAIに使用されています

擬似コード

function minimax(node, depth, isMaximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if isMaximizing:
        maxEval = -∞
        for each child of node:
            eval = minimax(child, depth - 1, false)
            maxEval = max(maxEval, eval)
        return maxEval
    else:
        minEval = +∞
        for each child of node:
            eval = minimax(child, depth - 1, true)
            minEval = min(minEval, eval)
        return minEval

よくある質問