探索アルゴリズムの基本形

多くの将棋プログラムの探索アルゴリズムでは、深さを探索の 打ち切り条件とするのに対して、激指の探索アルゴリズムでは、 局面の実現確率を打ち切り条件とする。つまり、局面の実現確率 があらかじめ設定されている閾値を下回ったら、葉になる （評価関数を呼ぶ）というわけである。

局面の実現確率とは、その局面が実際に実現する確率である。 一般に、読みの中の局面のほとんどは、実際に実現することはない。 そこで、どれくらい実現しないのか、あるいは実現するのか を確率的に評価したものが、ここでいう「局面の実現確率」である。 つまり、局面の実現確率を探索打ち切りの閾値とすることによって、 実際に実現の可能性の高い、すなわち、「ありそうな」局面を 読むことができる。

いま、ある指し手Mによって局面Aが局面A'に変化するとき、 局面A'の実現確率は次のように計算される。

ここで、合理的で十分に強いプレイヤーを仮定すれば、 指し手Mが最善手であれば必ずその手を指すのだから、 上の式は次のようになる。

指し手Mが最善手である確率を求める手法については別の章で述べる。

その他の点については、普通の深さ打ち切りによる探索アルゴリズム と同様である。すなわち、αβ枝刈りを用いたMin-max法となる。 以下に、 実現確率打ち切りによる探索アルゴリズムの基本形を C++ライクなコードで示す。

int search(Shogiban* ban, double probability, double probability_threshold, 
           int alpha, int beta, Move best_move)
{
  // 実現確率がしきい値を下回ったらおしまい
  if (probability < probability_threshold)
    return evaluate(ban);

  // 指し手生成（同時に、それぞれの指し手に、最善手である確率を付与）
  list<Move> move_list;  // STL (Standard Template Library) のリスト
  generate_moves(ban, move_list);

  int best_eval = alpha;
  for (list<Move>::const_iterator i = move_list.begin(); 
       i != move_list.end(); i++) {
    ban->move(*i);
    Move dummy;

    // 再帰呼び出し
    //   現局面の実現確率に、指し手の確率を掛ける
    int eval = -search(ban, probability*i->probability, probability_threshold,
                       -beta, -best_eval, dummy);
    ban->reverse();
    if (eval > best_eval) {
      best_eval = eval;
      best_move = *i;
      if (best_eval >= beta)
        return best_eval;
    }
  }
  return best_eval;
}

ここで、局面の実現確率に関して掛け算しかしていない点に注目 すると、log をとることによって、すべて足し算で処理できることがわかる。

例えば、ある局面Aの実現確率が 50% で、指し手Mの確率が 25% だとする。 そうすると、指し手Mによって実現する局面A'の実現確率は、

となるが、これを、log2 をとって計算すると

というように、足し算で計算することができる。そこで激指では、 確率をそのまま用いるのではなく、確率の log2 をとって符合を反転したものを用いている。それを logp と呼ぶことにすると、ルート局面の logp = 0 から始まり、 指し手によって、logp が増えていき（最善手の確率が高い指し手 ほど、logp の増加が少ない）、logp > logp_threshold で、 探索を打ち切る（評価関数を呼ぶ）という形になる。

ここで、logp を、普通の探索アルゴリズムにおける「深さ」と置き換えてみれば、 なんのことはない、実装上は、普通の深さ打ち切りによる探索アルゴリズムで、 深さの増加分を指し手の種類に応じて可変にしただけ、ということになる。

ご感想・ご質問等がありましたら まで、お気軽にどうぞ。