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