MinMax法の少し違う書き方。
「一方のプレイヤーにとっての評価値が高いならば、他方のプレイヤーにとっての評価値が低い」という性質を利用し、MinMax法におけるMINノードとMAXノードの区別を無くしたもの。
ルートノードの評価値及び各ノードの最善手はMinMax法と同一になる。
NegaMax法とは、以下の手順でノードの評価値を求める手法である。
MinMax法との違いは以下の3点である。
なお、評価関数は先後互角の場合には0を返すという実装である事を前提とする。 その為、先後互角の場合に非0の値を返す評価関数（例えば先手の勝率の予測値を返す評価関数）を使用する場合は、符号反転の部分を修正する必要がある。
＃ 森岡＞上の記述ですが、頭の中でざっと考えただけなので間違ってるかもしれません。
＃ 森岡＞実装経験のある人がいたら、修正をお願いします。
MinMax法と同様にして、以下のゲーム木を探索する場合を例にとって上記手順の動作を示す。
なお、S??の右にある数字はS??の局面で手番を持っているプレイヤーにとっての評価値である。
まず、RからE1、S11、S12、S13とたどる。E1の子ノード（S1?）の評価値を符号反転したものの最大値は-1なので、E1の評価値は-1となる。
次にE2に移ると、E1の場合と同様にE2の評価値は4となる。 同様にE3の評価値は3となる。
E1〜E3の評価値が決定出来たのでRの処理を行う。 Rの子ノード（E?）の評価値を符号反転したものの最大値である1がRの評価値となる。
以上の結果を追記したゲーム木を記す。 MinMax法での説明とはE?の評価値が異なっている事が確認出来る。
// 以下のプログラムでは、最善手の評価値は求めますが、
// 最善手自体は求めていません。
int leaf=0; // 葉ノードの数
int node=0; // 葉以外の中間ノードの数
// kは現在の局面
// depthは現在の読みの深さ（0がルートノード）
// depthMaxは、先読みを打ち切り、評価値を返す深さ
int getNegaMax(Kyokumen k,int depth,int depthMax)
{
if (depth>=depthMax) { // LEAFノードか否か判定
leaf++;
return k.evaluate(); // 局面kで手番を持っているプレイヤーにとっての評価値を返す
}
node++;
Te t[]=k.generateLegalMoves(); // 現在の局面での合法手を生成
int value=-INFINITE; // マイナス∞で初期化
Te best = null; // 最善手
for(int i=0;i<k.length;i++) {
k.move(te[i]); // te[i]で一手進める
int eval= -1 * getNegaMax(k,depth+1,depthMax); // 探索結果を符号反転する
k.back(te[i]); // te[i]で一手戻す
if (eval>value) {
best=te[i];
value=eval;
}
}
return value;
}
// ルートノードでの呼び出し方の例
int main(String[] args) {
Kyokumen kyokumen = new Kyokumen(); // ルートノードとなる局面を生成
int minMaxValue = getNegaMax(kyokumen,0,3); // 3手先まで先読みし、評価値を保存
}
NegaMax法とMinMax法はどちらも同じ結果を得る事が出来るが、NegaMax法には以下のメリット・デメリットがある。
メリット：MINノードとMAXノードの処理を区別する必要がないので、ソースコードの実装・メンテナンスが容易。
デメリット：評価値を繰り返し符号反転させるので、探索の詳細な動作を把握するのが困難。
MinMax法のメリット・デメリットはNegaMax法とはそれぞれ逆となる。
これらのメリット・デメリットはMinMaxとNegaMaxでは比較的小さい。 しかし、AlphaBetaやScoutへの拡張、LEAFノードでの静止探索?呼び出し、ハッシュテーブル?の読み書き等の各種改良を行うと徐々に大きくなっていく。
あくまで森岡個人の考えであるが、まずMinMaxで基本的な動作を学び、その後NegaMaxに書き換えてから各種拡張を行うのがお勧めである。
ネガマックス法など。