MinMax - ゲーム木の探索を行う為の、最も基本的なアルゴリズム。

目次

• 動作原理
• 探索打ち切り条件
• 深さで打ち切る例を示した擬似コード
• 応用
• 別名

ゲーム木の探索を行う為の、最も基本的なアルゴリズム。

動作原理

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手で打ち切る場合）であっても、序盤と中盤以降では探索終了までの時間が大きく異なる。 そこで、時間制限のある場合は反復深化?と併用する事が多い。

別名

ミニマックス法など。