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