AlphaBeta探索で経路依存の値を判定する方法

なんぞ？

AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。

そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。

どうやるの？

↓こんな感じ。

• 末端では、それが経路依存な性質を持つか否かでフラグを設定する。
• αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。
• αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。
• β以上の子ノードがあった場合、それがtrueな時だけtrue、でなくばfalseにする。¹
• β以上の子ノードが無かった場合、子ノードがどれか一つでもtrueならtrueにする。²

間違えてました！ (2015/05/10追記)

@merom686 にご指摘頂きました。

追加で、以下の条件を満たせばbestValueが下限にはなるという知見も。

• αを超える
• αを超えた子ノードがfalse
• αを超えなかった子ノードがどれか一つでもtrue

この場合、bestValue自体は経路依存ではあるけれど、bestValue以上であることは経路に依存せず保証できているようです。

擬似コードで

Value AlphaBeta(SearchStack* ss, 他色々) {
    ss->isHistorical = false;

    if (経路非依存な判定) {
        return 値;
    }
    if (経路依存な判定) {
        ss->isHistorical = true;
        return 値;
    }

    for (Move move : pos.GetMoves()) {
        pos.DoMove(move);
        Value v = -AlphaBeta(ss + 1, -beta, -alpha, 色々);
        pos.UndoMove(move);

        /* ここでvが経路依存か否かが (ss + 1)->isHistorical に入ってる。 */

        if (beta <= v) {
            // βカットする場合は、その子ノードがtrueなときだけtrueにする
            ss->isHistorical = (ss + 1)->isHistorical;
        }
        if (v < beta) {
            // βカットしない場合は、子ノードがどれか一つでもtrueならtrueにする
            ss->isHistorical = ss->isHistorical || (ss + 1)->isHistorical;
        }
    }

    /* ここでは bestValue が経路依存か否かが ss->isHistorical に入ってる。 */

    return bestValue;
}

結局、何に使うの？

「経路依存な場合は置換表に入れない」とかしておくと、少しだけ気分が良くなるかもしれません。(それだけ)

1. これがtrueな場合、falseでかつβカットする別の子ノードがある可能性もあるが、それを探すとMinMaxになってしまうので妥協する。falseな場合は、少なくともその手がβ以上である事が分かっているので他の手を見る必要はない。(false positive) ↩

2. 子ノードでのβカット時の判定がfalse positiveなので、この結果もfalse positiveになる。全ての子ノードがfalse(経路非依存)としてβカットしたなら、そのノードは経路に依存しないことは保証できている。(が、裏は真ならず) ↩