Source of ミニマックス法 - Computer Shogi Wiki

  ミニマックス法（minimax法）は、二人零和有限確定完全情報ゲームにおいて、
「自分は自分にとって最も良い手を選び、相手も相手にとって最も良い手を選ぶ」
と仮定して局面の価値を決める考え方である。

コンピュータ将棋では、[ゲーム木](/shogi/shogiwiki/search/search-tree/)をたどって末端局面の値を決め、
その値を親ノードへ逆向きに伝搬させることで局面の価値を求める。
将棋AIの探索を理解するための基本概念であり、[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)や[negamax](/shogi/shogiwiki/search/negamax/)の土台でもある。

## 概要

ミニマックス法では、

- 自分の手番では子ノードの中で最も値が高いものを選ぶ
- 相手の手番では子ノードの中で最も値が低いものを選ぶ

という操作を繰り返す。

末端局面が終局なら勝敗で値を決め、終局でないなら[評価関数](/shogi/shogiwiki/search/evaluation-function/)で値を与える。
その値を葉から根へ戻していくことで、ルート局面での最善手候補が決まる。

## 簡単な例

ある局面でこちらに3通りの候補手 A, B, C があり、
それぞれの先で相手も最善応手を選ぶとする。

- A を指した後、相手の応手まで読んだ結果の評価値が `+300`
- B を指した後、相手の応手まで読んだ結果の評価値が `+120`
- C を指した後、相手の応手まで読んだ結果の評価値が `-500`

であれば、自分の手番では最も値が高い A を選ぶ。

一方、相手番のノードでは、相手は自分に不利になる手を選ぶので、
そのノードの値は「子ノードの中で最も低い値」になる。

## 将棋AIでの位置づけ

教科書的なミニマックス法は分かりやすいが、そのままでは探索量が非常に大きい。
将棋は分岐数が大きく、単純に全手を読むのは現実的でないためである。

そのため実際の将棋ソフトでは、ミニマックス法そのものを使うというより、

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)で不要な枝を刈る
- [negamax](/shogi/shogiwiki/search/negamax/)で実装を簡潔にする
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)や[置換表](/shogi/shogiwiki/search/transposition-table/)を併用する
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)や各種枝刈りを加える

といった形で発展させた探索が主に使われる。

したがってミニマックス法は、実戦用の完成形というより、
将棋AIの探索が何を計算しているかを理解するための基本原理とみるのが適切である。

## negamax との関係

二人零和ゲームでは、
「自分にとって良い局面は相手にとって悪い局面」である。

この性質を使うと、最大化ノードと最小化ノードを別々に書かずに、
常に最大化だけを行い、手番が変わるたびに評価値の符号を反転する形で実装できる。
これが [negamax](/shogi/shogiwiki/search/negamax/) である。

## 実装例

教育用の最小例としては、最大化ノードと最小化ノードを分けて次のように書ける。

```cpp
int minimax(Position pos, int depth, bool maximizingPlayer) {
    if (depth == 0 || pos.isTerminal()) {
        return evaluate(pos);
    }

    if (maximizingPlayer) {
        int bestValue = -INF;
        for (Move move : generateMoves(pos)) {
            Position next = doMove(pos, move);
            int value = minimax(next, depth - 1, false);
            bestValue = std::max(bestValue, value);
        }
        return bestValue;
    } else {
        int bestValue = INF;
        for (Move move : generateMoves(pos)) {
            Position next = doMove(pos, move);
            int value = minimax(next, depth - 1, true);
            bestValue = std::min(bestValue, value);
        }
        return bestValue;
    }
}
```

ただし実際の将棋AIでは、最大化側と最小化側で処理を分けると重複が多くなるため、
通常は [negamax](/shogi/shogiwiki/search/negamax/) で書かれることが多い。

```cpp
int negamax(Position pos, int depth) {
    if (depth == 0 || pos.isTerminal()) {
        return evaluate(pos);
    }

    int bestValue = -INF;
    for (Move move : generateMoves(pos)) {
        Position next = doMove(pos, move);
        int value = -negamax(next, depth - 1);
        bestValue = std::max(bestValue, value);
    }
    return bestValue;
}
```

この形はミニマックス法と本質的に同じであり、
さらに [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) へ拡張しやすい。

## アルファベータ法との関係

[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)は、ミニマックス法と同じ答えを保ったまま、
結果に影響しない枝を途中で読まずに済ませる改良である。

特に[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)がうまくいくと探索量を大きく減らせるため、
ミニマックス系探索の実用化にはほぼ必須の技術といってよい。

## 注意点

- 葉で使う評価関数が弱いと、ミニマックス法自体が正しくても手の良し悪しを誤る
- 将棋のように分岐数が大きいゲームでは、枝刈りや手の並べ替え無しでは実用になりにくい
- 浅い探索では[地平線効果](/shogi/shogiwiki/search/horizon-effect/)のような問題が起こる

## 関連項目

- [探索](/shogi/shogiwiki/search/)
- [ゲーム木](/shogi/shogiwiki/search/search-tree/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [negamax](/shogi/shogiwiki/search/negamax/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [地平線効果](/shogi/shogiwiki/search/horizon-effect/)
ミニマックス法 minimax
