| ネガスカウト法 | prev Page next Page |
nega scout
scout はボーイスカウトのスカウト。「偵察」という意味。
コストがほとんど必要ない ヌルウィンドウサーチ を用いて、不必要な評価を回避する方法
(α, α + 1）の範囲で子ノードの探索を行うと、αβカットが頻繁に発生するので、短い時間で探索を終了する。
返ってきた値を s とすれば、s <= α または α + 1 <= s である。
s <= α の場合、子ノードの正しい評価値 ev も ev <= αであるから、その子ノードを探索する必要はない
s >= βであれば、ev >= s >= β であるからβカットが発生する
α < s < βであれば、（s, β) の範囲で子ノードを探索し、結果 ev をαに代入する。
（α < s <= ev なので、ev はαよりも大きい）
以上をすべての子ノードについて行う
int negaScout(uint64 black, uint64 white, int alpha, int beta, int depth)
{
if( !depth ) // 末端ノード
return eval(black, white);
for( m = すべての着手について ) {
m に着手;
int s = -negaScout(white, black, -(alpha + 1), -alpha, depth-1); // ヌルウィンドウサーチ
if( s >= beta ) {
着手を元に戻す;
return s; // βカット
}
if( s > alpha )
alpha = -negaScout(white, black, -beta, -s, depth-1);
着手を元に戻す;
if( alpha >= beta ) break; // αβ cut
}
return alpha;
}
参照：探索アルゴリズム
このページへのトラックバックURL： http://vivi.dyndns.org/wtb/267
2,015 page views,
page owner : びびすけ
2007/06/12 09:11 modified by びびすけ