negamax は、ミニマックス法を二人零和ゲーム向けに簡潔に書き直した実装形式である。 「自分にとって良い局面は相手にとって悪い局面」という性質を使い、 最大化ノードと最小化ノードを別々に書かずに済ませる。
ミニマックス法では、
と書き分ける。
しかし二人零和ゲームでは、
max(a, b) = -min(-a, -b)
が成り立つので、常に「最大値を取る」形に統一できる。 手番が入れ替わるたびに評価値の符号を反転すればよい。
実装が短くなり、
といった利点がある。
そのため、実際の将棋AIでは minimax を概念説明に使い、 コードは negamax で書くことが多い。
最小形は次のようになる。
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 を追加して
アルファベータ法へ拡張する。
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 では通常、評価関数が 「手番側から見た値」を返すようにしておくと実装がきれいになる。
たとえば、
とすれば、再帰のたびに単純に符号反転するだけでよい。
将棋AIの探索コードでは、
という形が基本になることが多い。
そのため、実装を読むうえでは minimax より negamax の方が直接役に立つことが多い。