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

なんぞ？ AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。 そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。 どうやるの？ ↓こんな感じ。 末端では、それが経路依存な性質を持つか否かでフラグを設定する。 αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。 αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。 β以上の子ノードがあった場合、そ