2.5 Scout法

今回は、Alpha-Beta法の改良であるScout法について説明します。

Scout法では、子節点の評価を行うとき、まずそれがAlpha値を超えるか（またはBeta値未満か）どうかを調べ、超えた場合にだけ本格的な探索を行う方法です。
これはAlpha-Beta法を、次のように変更します。

  • 節点が葉以外で、子節点の評価がすべて終わってないとき

    • 節点が自局面のとき
      子節点を一つも評価していないときは、子節点の中から１つ節点を選び、その処理に移る
      そうでない場合、まず評価済みの子節点の評価値のうち最大の値をalphaに代入する
      alphaがbeta以上のときは、betaをその節点の評価値とし、親節点の処理に移る
      beta以上でない場合は、betaにalpha+1を代入して、未評価の子節点の中から１つ節点を選び、その処理に移る
      その後betaを元に戻す。
      その子節点の評価値がalphaを超えた場合にはalphaにその子節点の評価値を代入して、同じ節点の処理に移る

    • 節点が相手局面のとき
      子節点を一つも評価していないときは、子節点の中から１つ節点を選び、その処理に移る
      そうでない場合、まず評価済みの子節点の評価値のうち最小の値をbetaに代入する
      評価済みの子節点の評価値のうち最小の値をbetaに代入する
      betaがalpha以下のとき、alphaをその節点の評価値とし、親節点の処理に移る
      alpha以下でない場合は、alphaにbeta-1を代入して、未評価の子節点の中から１つ節点を選び、その処理に移る
      その後alphaを元に戻す。
      その子節点の評価値がbeta未満の場合にはbetaにその子節点の評価値を代入して、同じ節点の処理に移る

C言語の関数風に書くと次のようになります。
パスがあるときの処理は省略しています。

int sc_max(int t, int alpha, int beta) /* 自局面の節点での処理 tは葉局面までの手数 */
{
  int v;

  if(t == 0)
    return (現在の局面の評価値);

  局面に最初の子節点の手を打つ;
  v = sc_min(t-1, alpha, beta);
  局面を元に戻す;
  if(v > alpha){
    alpha = v;
    if(alpha >= beta)
      return beta;
  }

  次の子節点に移る;

  for(; 未評価の子節点がある; 次の子節点に移る){
    局面に子節点の手を打つ;
    v = sc_min(t-1, alpha, alpha+1);
    if(v > alpha)
      alpha = sc_min(t-1, v, beta);
    局面を元に戻す;
    if(alpha >= beta)
      return beta;
  }

  return alpha;
}

sc_min(int t) /* 相手局面の節点での処理 */
{
  int v;

  if(t == 0)
    return (現在の局面の評価値);

  局面に最初の子節点の手を打つ;
  v = sc_min(t-1, alpha, beta);
  局面を元に戻す;
  if(v < beta){
    beta = v;
    if(beta <= alpha)
      return alpha;
  }

  for(; 未評価の子節点がある; 次の子節点に移る){
    局面に子節点の手を打つ;
    v = sc_max(t-1, beta-1, beta);
    if(v < beta)
      beta = sc_min(t-1, alpha, v);
    局面を元に戻す;
    if(beta <= alpha)
      return alpha;
  }

  return beta;
}

Scout法は、順序付けを行った場合にはAlpha-Beta法よりも効率がよくなります。


トップに戻る
2.4 順序付けと反復深化法
2.6 ハッシュ法