αβアルゴリズム(2) 処理の流れ
今回も基本的にwikipediaやね。
wikipedia:アルファ・ベータ法
探索しなくてもいいノードとは?
図を用いて説明する。Minimax探索の結果、ノードBの評価値が40、ノードDの評価値が20だと分かったとする。このとき、ノードEの評価値を求めなくても、ノードAの評価値は40と求まる。なぜなら、ノードEの評価値をxとすると、max(40,min(20,x))=40が成り立ち、これはxの値とは関係ないからである。すなわち、ノードEを探索する必要はない。αβアルゴリズムはこのように訪問する必要のないノードを探索せず、枝刈りを行っていくアルゴリズムである。
擬似コード
そして天下り的にいきなり擬似コードを示す。negamax形式である。
int alphabeta(Node n, int depth, int alpha, int beta){ if(depth == 0) return eval(n); for(nの子ノードcそれぞれについて){ int g = -alphabeta(c, depth-1, -beta, -alpha); alpha = max(alpha, g); if(beta <= alpha){ return beta; } } return alpha; }
alphaとbetaは探索窓と呼ばれる。以下、探索窓を(α,β)のように書く。
このコードの挙動の例を以下に図示する。各ノードの探索窓は左側に書かれている一つ目の子ノードを探索する直前の探索窓で、右側に書かれているのが一つ目の子ノードの探索が終わって二つ目の子ノードを探索する直前の探索窓である。点線になっている部分は枝刈りによって探索しなかった部分である。
Minimaxと違うところ
リーフノード以外ではノードの評価値がMinimaxアルゴリズムの場合と異なることがある。αβアルゴリズムで探索した結果の評価値(return文で返す評価値)を、Minimaxアルゴリズムで探索したときに結果の評価値をとする。また、そのノードをはじめて訪問したときの探索窓を(,)とする。このとき、
- ならば
- ならば
- ならば
の関係がある。つまり、探索窓の中に評価値があるときに限り、その評価値はMinimaxアルゴリズムで探索したものと必ず等しい。この意味で探索窓は「正確な評価値に興味のある範囲」を表現しており、探索窓より外側になる評価値に対しては、それが探索窓を越えることだけわかればよいということになる。
さて、「あるノードの評価値」と書いた場合に混乱が生じるかもしれないので、今後このシリーズの文章では以下のように使い分ける。
- 静的評価値:探索を行わずに、局面を評価関数で評価した値
- Minimax値:Minimax探索を行って得られた評価値
- αβ値:αβ探索を行って得られた評価値(Minimax値と等しくないこともある)
今回はここまで。我ながら読みにくい…。