Source of negamax - Computer Shogi Wiki

  # negamax

negamax は、[ミニマックス法](/shogi/shogiwiki/search/minimax/)を二人零和ゲーム向けに簡潔に書き直した実装形式である。
「自分にとって良い局面は相手にとって悪い局面」という性質を使い、
最大化ノードと最小化ノードを別々に書かずに済ませる。

## 概要

ミニマックス法では、

- 自分の手番では最大値を取る
- 相手の手番では最小値を取る

と書き分ける。

しかし二人零和ゲームでは、

`max(a, b) = -min(-a, -b)`

が成り立つので、常に「最大値を取る」形に統一できる。
手番が入れ替わるたびに評価値の符号を反転すればよい。

## なぜ使われるのか

実装が短くなり、

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)を自然に書ける
- バグの入りやすい Max/Min の二重実装を避けられる
- ルート探索、[静止探索](/shogi/shogiwiki/search/quiescence-search/)、再探索系と形を揃えやすい

といった利点がある。

そのため、実際の将棋AIでは minimax を概念説明に使い、
コードは 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 score = -negamax(next, depth - 1);
        if (score > bestValue) {
            bestValue = score;
        }
    }
    return bestValue;
}
```

実戦的には、これに `alpha` と `beta` を追加して
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)へ拡張する。

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

    int bestValue = -INF;
    for (Move move : generateMoves(pos)) {
        Position next = doMove(pos, move);
        int score = -negamax(next, depth - 1, -beta, -alpha);
        if (score > bestValue) {
            bestValue = score;
        }
        if (score > alpha) {
            alpha = score;
        }
        if (alpha >= beta) {
            break;
        }
    }
    return bestValue;
}
```

## 評価関数との関係

negamax では通常、[評価関数](/shogi/shogiwiki/search/evaluation-function/)が
「手番側から見た値」を返すようにしておくと実装がきれいになる。

たとえば、

- 手番側が良い局面なら正
- 手番側が悪い局面なら負

とすれば、再帰のたびに単純に符号反転するだけでよい。

## 将棋AIでの位置づけ

将棋AIの探索コードでは、

- negamax
- negamax + alpha-beta
- negamax + quiescence

という形が基本になることが多い。

そのため、実装を読むうえでは minimax より negamax の方が直接役に立つことが多い。

## 注意点

- 評価値の向きが手番基準になっていないと符号の扱いで混乱しやすい
- 詰み値や千日手値を符号付きで扱うときは一貫した規約が必要
- minimax の概念理解がないと、なぜ符号を反転するのか分かりにくい

## 関連項目

- [ミニマックス法](/shogi/shogiwiki/search/minimax/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [評価関数](/shogi/shogiwiki/search/evaluation-function/)
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Negamax](https://www.chessprogramming.org/Negamax)
- [Chessprogramming Wiki: Minimax](https://www.chessprogramming.org/Minimax)
- [Chessprogramming Wiki: Alpha Beta](https://www.chessprogramming.org/Alpha-Beta)
negamax negamax
