ミニマックス法（minimax法）は、二人零和有限確定完全情報ゲームにおいて、 「自分は自分にとって最も良い手を選び、相手も相手にとって最も良い手を選ぶ」 と仮定して局面の価値を決める考え方である。
コンピュータ将棋では、ゲーム木をたどって末端局面の値を決め、 その値を親ノードへ逆向きに伝搬させることで局面の価値を求める。 将棋AIの探索を理解するための基本概念であり、アルファベータ法やnegamaxの土台でもある。
ミニマックス法では、
という操作を繰り返す。
末端局面が終局なら勝敗で値を決め、終局でないなら評価関数で値を与える。 その値を葉から根へ戻していくことで、ルート局面での最善手候補が決まる。
ある局面でこちらに3通りの候補手 A, B, C があり、 それぞれの先で相手も最善応手を選ぶとする。
+300+120-500であれば、自分の手番では最も値が高い A を選ぶ。
一方、相手番のノードでは、相手は自分に不利になる手を選ぶので、 そのノードの値は「子ノードの中で最も低い値」になる。
教科書的なミニマックス法は分かりやすいが、そのままでは探索量が非常に大きい。 将棋は分岐数が大きく、単純に全手を読むのは現実的でないためである。
そのため実際の将棋ソフトでは、ミニマックス法そのものを使うというより、
といった形で発展させた探索が主に使われる。
したがってミニマックス法は、実戦用の完成形というより、 将棋AIの探索が何を計算しているかを理解するための基本原理とみるのが適切である。
二人零和ゲームでは、 「自分にとって良い局面は相手にとって悪い局面」である。
この性質を使うと、最大化ノードと最小化ノードを別々に書かずに、 常に最大化だけを行い、手番が変わるたびに評価値の符号を反転する形で実装できる。 これが negamax である。
教育用の最小例としては、最大化ノードと最小化ノードを分けて次のように書ける。
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 で書かれることが多い。
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;
}この形はミニマックス法と本質的に同じであり、 さらに アルファベータ法 へ拡張しやすい。
アルファベータ法は、ミニマックス法と同じ答えを保ったまま、 結果に影響しない枝を途中で読まずに済ませる改良である。
特に手の並べ替えがうまくいくと探索量を大きく減らせるため、 ミニマックス系探索の実用化にはほぼ必須の技術といってよい。