ゲーム木の探索を行う為の、最も基本的なアルゴリズム。 *動作原理 &verb(MinMax法)とは、以下の手順でノードの評価値を求める手法である。 - MAXノードでは、子ノードの評価値の最大値をそのノードの評価値とする。 - MINノードでは、子ノードの評価値の最小値をそのノードの評価値とする。 - 探索を打ち切る深さになると[[評価関数]]を用いてMAXプレイヤーにとっての評価値を求め、その値を返す。 以下の[[ゲーム木]]を探索する場合を例にとって上記手順の動作を示す。 R、E?、S??はノードの名称である。 ここでは、RがMAXノード、E?がMINノード、S??がLEAFノードである。 S??の右にある数値がそのノードのMAXプレイヤーにとっての評価値である。 Rは通常、現在の（最後に対局相手が指した後の）局面であり、ルートノードと呼ぶ。 詳しくは[[ゲーム木]]を参照。 また、探索を打ち切る条件は手数とし、2手指した時点で打ち切るものとする。 - 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はMINノードなので子ノード（S1?）の評価値の最小値である1がE1の評価値となる。 次にE2に移ると、E1の場合と同様にE2の評価値は-4となる。 同様にE3の評価値は-3となる。 E1〜E3の評価値が決定出来たのでRの処理を行う。 RはMAXノードなので、子ノード（E?）の評価値の最大値である1がRの評価値となる。 以上の結果を追記したゲーム木を記す。 各ノードの評価値は子ノードの評価値の最大値または最小値になっている事が確認出来る。 - 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 *探索打ち切り条件 上記の例では探索打ち切りの条件を手数としたが、他の打ち切り条件には下記の様なもの等がある。 :実現確率:局面間の遷移確率をもとに局面の実現確率を計算し、実現確率が閾値以下になった場合に探索を打ち切る。[[激指]]が採用。http://www.logos.t.u-tokyo.ac.jp/~gekisashi/algorithm/index.html 参照。 :共謀深さ:ルートノードから現在探索中のノードの間で、展開中の手よりも評価値が高い（MAXノードの場合）または低い（MINノードの場合）兄弟手の数が閾値を上回った場合に探索を打ち切る。[[KFEnd]]が採用。http://www31.ocn.ne.jp/~kfend/inside_kfend/abc_search.html 参照。 *深さで打ち切る例を示した擬似コード --( // 以下のプログラムでは、最善手の評価値は求めますが、 // 最善手自体は求めていません。 int leaf=0; // 葉ノードの数 int node=0; // 葉以外の中間ノードの数 // kは現在の局面 // depthは現在の読みの深さ（0がルートノード） // depthMaxは、先読みを打ち切り、評価値を返す深さ int getMin(Kyokumen k,int depth,int depthMax) { if (depth>=depthMax) { // LEAFノードか否か判定 leaf++; return k.evaluate(); // MAXプレイヤーにとっての評価値を返す } 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=getMax(k,depth+1,depthMax); // MAXノードの探索 k.back(te[i]); // te[i]で一手戻す if (eval<value) { // 前よりも小さな評価の手があれば… best=te[i]; value=eval; // その結果をvalueに保存。 } } return value; } // kは現在の局面 // depthは現在の読みの深さ（0がルートノード） // depthMaxは、先読みを打ち切り、評価値を返す深さ int getMax(Kyokumen k,int depth,int depthMax) { if (depth>=depthMax) { // LEAFノードか否か判定 leaf++; return k.evaluate(); // MAXプレイヤーにとっての評価値を返す } 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=getMin(k,depth+1,depthMax); // MINノードの探索 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 = getMax(kyokumen,0,3); // 3手先まで先読みし、評価値を保存 } --) *応用 MinMax法の少し違う書き方としてNegaMax法がある。 MinMax法と同じ結果をより短時間で得られる手法としてAlphaBeta法があり、実際のコンピュータ将棋ではAlphaBeta法を用いる事の方が多い。 また、合法手の数は序盤では数十であるが、中盤以降（特に持ち駒が増えた場合)は優に百を超える。 この為、探索打ち切り条件を固定した場合（例えば3手で打ち切る場合）であっても、序盤と中盤以降では探索終了までの時間が大きく異なる。 そこで、時間制限のある場合は[[反復深化]]と併用する事が多い。 *別名 ミニマックス法など。