評価値を更新した手の再探索

更新日時:

前節で、実現確率打ち切りによる探索アルゴリズムの基本形を説明した。 しかし、基本形をそのまま実装すると、確率の低い手による水平線効果 の問題が起きる。そこで本節では、「評価値を更新した手が最善手である確率」 を導入することによる対処法を示す。

前節で述べた基本形をそのまま実装すると、確率の低い手による 水平線効果の問題が起きる。その理由は、 実現確率打ち切りアルゴリズムでは、 その先どんなに不利になる指し手でも、その指し手の確率が非常 に低ければ、すぐにリーフになってしまい、 その先の不利な状況を認識しなくなるからである。

そこで新たに、「評価値を更新した手が最善手である確率」 を導入する。Min-max アルゴリズムでは、ノードの評価値は、 アルファ値からスタートし、指し手による評価値が現在の 評価値より上回ったら更新する、ということを繰り返す。 それらの「評価値を更新した手」は、他の多くの手よりも 「最善手である確率」が高いことは、直感的にも理解できる。

今までは、「直前に動いた駒を取り返す手」や「王手をかける手」 などというように、表面的な指し手の性質に注目して 確率を算出してきた。それらを、表面的な性質に基づく確率とすれば、 ここで導入する「評価値を更新した手が最善手である確率」は、 アルゴリズムに基づく確率、といえるかもしれない。

この確率を探索アルゴリズムに導入するには、具体的には、 評価値を更新した手を「評価値を更新した手が最善手である確率」 で再探索をする、という形になる。以下に、再探索を導入した アルゴリズムを、C++ライクなコードで示す。

int search(Shogiban* ban, double logp, double logp_threshold, 
           int alpha, int beta, Move best_move)
{
  // 実現確率がしきい値を下回ったらおしまい
  if (logp > logp_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;

    // 最初の探索
    //   評価値を更新するかどうかを確かめるだけなので、windowの幅は 1 でよい
    int eval = -search(ban, logp + i->logp, logp_threshold,
                       -(best_eval+1), -best_eval, dummy);

    if (eval > best_eval) {
      // 評価値を更新した場合
      //   「評価値を更新した手が最善手である確率」で再探索
      int eval = -search(ban, logp + RE_SEARCH_LOGP, logp_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;
}

激指のアルゴリズムへ戻る
ご感想・ご質問等がありましたら まで、お気軽にどうぞ。