前節で、実現確率打ち切りによる探索アルゴリズムの基本形を説明した。 しかし、基本形をそのまま実装すると、確率の低い手による水平線効果 の問題が起きる。そこで本節では、「評価値を更新した手が最善手である確率」 を導入することによる対処法を示す。
前節で述べた基本形をそのまま実装すると、確率の低い手による 水平線効果の問題が起きる。その理由は、 実現確率打ち切りアルゴリズムでは、 その先どんなに不利になる指し手でも、その指し手の確率が非常 に低ければ、すぐにリーフになってしまい、 その先の不利な状況を認識しなくなるからである。
そこで新たに、「評価値を更新した手が最善手である確率」 を導入する。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;
}
まで、お気軽にどうぞ。