なんぞ？
AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。
そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。
どうやるの？
↓こんな感じ。
- 末端では、それが経路依存な性質を持つか否かでフラグを設定する。
αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。- β以上の子ノードがあった場合、それがtrueな時だけtrue、でなくばfalseにする。1
- β以上の子ノードが無かった場合、子ノードがどれか一つでもtrueならtrueにする。2
間違えてました！ (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;
}
結局、何に使うの？
「経路依存な場合は置換表に入れない」とかしておくと、少しだけ気分が良くなるかもしれません。(それだけ)