PVS探索 (Principal Variation Search)

2001/01/17 PVSの文献を探していて自分の理解のためにまとめてみました。

PAB探索 ... Principal Variation Alpha-Beta。
            前回の最善手を最初に探索して、それ以外の手はすべて悪いだろう、という仮定の元に
            αβの範囲を+1にして探索する方法。探索が成功すれば（悪いことが判明すれば）
            効率は上がる。もし、失敗した場合は再度、αβの範囲を広げて再探索する必要がある。

PVS探索 ... PABで、再探索をした場合にも、その下のノードで新たに+1の幅の探索をする方法。






// PVS探索 (Principal Variation Search)

int PVS_max(int alpha, int beta)
{
    current = -無限大;
    if (末端) return 評価関数;
    // 手を生成する    個数 = n;   n == 0 ならば評価関数を返すかcurrent(負け)を返す。まあ色々でしょう。

    for (i=0;i<n;i++) {
        // 手を進める
        if ( i == 0 ) {
            value = PVS_min(alpha,beta);              // 前回の最善手はそのまま探索    
        } else {
            value = PVS_min(alpha,alpha+1);           // 幅１のNull Window 探索 ... 他の手はおそらく悪い手なので（一種の「賭け」）
            if ( alpha < value && value < beta ) {    // もし、Null Window でここにきた場合、(+5,+6) の間にvalueが収まることは「あり得ない」
                                                      // つまり、Null Window 探索を開始したノード以外では再探索はされない
                value = PVS_min( value, beta );       // "High 失敗" 再探索。value を新たな下限とする。
            }
        }
        // 手を戻す
        if ( value > current ) {    // 現在の最善手が決まった
            current = value;        // とりあえず価値が高ければ更新（value < alpha でも更新される事が大事 ---> Null Window 探索で）
            if ( current > alpha ) alpha = current;
            if ( alpha >= beta ) break;    // 枝刈。
        }
    }
    return current; // alpha を返すのではない。(alpha,beta) の範囲外でも最大の数値を返す。これが探索失敗時のPVS_min()関数の上限となりうる。
                    // (+5, +6) で current = 1; ならば、この値が探索失敗時に新しい(α,β) = (-無限大,1) となるかも。
                    // ここでalphaを返してしまうと再探索で (+5,+6) ならば (α,β) = (-無限大,+5) としかならない。

}

int PVS_min(int alpha, int beta)
{
    current = +無限大;
    if (末端) return 評価関数;
    // 手を生成する 

    for (i=0;i<n;i++) {
        // 手を進める
        if ( i==0 ) {
            value = PVS_max(alpha,beta);
        } else {
            value = PVS_max(beta-1,beta);               // value という仮の値で Null Window の結果を保存する
            if ( alpha < value && value < beta ) {    
                value = PVS_max( alpha, value );        // "low 失敗" 再探索
                                                        // ここは current = PVS_max(); としても通常はOKのはず。
                                                        // しかし、複雑な延長などの処理をしている場合、再探索したら評価が下がることはあるかも
            }
        }
        // 手を戻す
        if ( value < current ) {
            current = value;
            if ( current < beta ) beta = current;
            if ( alpha >= beta ) break;
        }
    }
    return current;
}



http://www.xs4all.nl/~verhelst/chess/search.html#principal
にあった正しい記述をしていると思われるアルゴリズム。
・・・しかし、個人的にはalphaとbetaをひっくり返して記述するこの形式は
理解しづらいので抵抗がある。
たしかにこれで正しいし簡潔にかけると思うのだが評価値が深さ毎に反転する、
なんてデバッグしづらいと思う。

int PrincipalVariation (pos, depth, alpha, beta)
{
    if (depth == 0) return Evaluate(pos);
    succ = Successors(pos);
    pos = RemoveOne(succ);
    best = -PrincipalVariation(pos, depth-1, -beta, -alpha);
    while (not Empty(succ) && best < beta)
    {
        pos = RemoveOne(succ);
        if (best > alpha) alpha = best;
        value = -PrincipalVariation(pos, depth-1, -alpha-1, -alpha);
        if (value > alpha && value < beta) 
            best = -PrincipalVariation(pos, depth-1, -beta, -value);
        else if (value > best)
            best = value;
    }
    return best;
}




---------------------------------------------------------------------
PAB ... 幅１の探索が失敗して再探索した場合には普通のαβに戻る
PVS ... 再探索の場合でも、その下のノードで幅１の探索をする

PABとPVSについて正しく記述してある本。
アメリカのアマゾンで探したらもう絶版になっていました。
http://www.amazon.com/exec/obidos/ASIN/3540974156/ 


ちなみにPABの事が書いてあった論文は
http://citeseer.nj.nec.com/361651.html
こちらの13ページで、PVSが書いてあったのが
http://citeseer.nj.nec.com/marsland85parallel.html
ここの3ページめです。
・・・、この3ページ目のPVSのアルゴリズムは間違ってます。たぶん、いやきっと。

論文の方のELSEは直前のif文にかかっているのですよね？
とすると
if ( value > alpha ) {
　　if (value < beta) 
　　　　best = -PrincipalVariation(pos, depth-1, -beta, -value);
　　else 
　　　　best = value;
}　　

こうで、ホームページの方が
if (value > alpha && value < beta) 
　　best = -PrincipalVariation(pos, depth-1, -beta, -value);
else if (value > best)
　　best = value;

こうなので best = value; の条件が違う・・・。

(Alpha,Beta)=(+5, +6)
という幅１の探索をしている時に、MAXノードに来て、後1手しか読まない、
(次が末端）とします。
で、２つの候補手があって、それぞれ、+2,+3 だとすると
論文の方法だと最初にみつけた+2という値を上に返してしまいます。
ホームページの方は+3という正しい値を返すと思うのです。