αβアルゴリズム(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値と等しくないこともある)
今回はここまで。我ながら読みにくい…。
αβアルゴリズム(1) Minimaxアルゴリズム
さて、予告通りαβの記事でも書く。まずは、基本のMinimaxアルゴリズムから。
ゲーム木
- ノードは局面を表す
- エッジは指し手による局面の遷移を表す
- リーフノードには数値(評価値)が与えられる
ゲーム木のリーフノードは究極的には終局面(勝ち負けが決定した局面)となるのが理想である。その場合、リーフノードの評価値は勝ちなら+1、負けなら-1、引き分けなら0とかすればいい。
しかし、○×ゲームならまだしも将棋などでは終局面まで探索するのは現実的に不可能である。実際には適当なところで打ち切ってリーフノードとする。このとき、局面からその局面の良し悪しを何らかの方法で推定して数値化したものを、リーフノードの評価値とする。局面を入力とし、評価値を出力する関数を評価関数と呼ぶ。このように、局面の情報だけから得られた評価値を静的評価値と呼ぶ。評価関数が局面の優劣を完全に判断できるならば、先読みなんて必要ないわけであるが、実際にはそのような評価関数はないので、ゲーム木探索を実行して、もっと正確な判断を行うことになる。
ゲーム木探索の問題設定
ルートノードにおいて、どのエッジを選択するのが最善か?
ここで問題となるのが、「何を持って最善とするか?」であって、これを決める方法に、子ノードのうち、自分は評価値が最も大きいもの、相手は評価値が最も小さいものを選ぶというものがあって、この方策を用いてゲーム木探索を行うアルゴリズムがMinimaxアルゴリズムである。
Minimaxアルゴリズム
negamax形式
Minimaxアルゴリズムを単純に実装しようとすると、自分の手番を表すノードと相手の手番を表すノードを区別しなければならず、面倒である。そこで、相手の手番では評価値に負号を付けることにより、常に最大のものを選ぶようにする。具体的には子ノードの評価値にマイナスをつけてから、最大となる子ノードを選ぶ。これをnegamax形式と言ったりする。今後はずっとnegamax形式で考える。図にすると下のような感じ。リーフノードの評価関数の値のプラスマイナスを、自分の手番か相手の手番かで、決めなければいけない。かなりややこしく、自分は紙に書いて考えても間違えることが多いw
擬似コード
こんな感じ。negamax形式。コードにすると簡単。
int minimax(Node n, int depth){ if(depth == 0) return eval(n); //静的評価値を返す int score = -INF; for(nの子ノードcそれぞれについて){ int g = -minimax(c, depth-1); score = max(score, g); } return score; }
計算量
探索深さを、一つのノードの子ノードの数をとしたとき、訪問リーフノード数と、訪問ノード数は、
である。つまり、計算量のオーダは、である。
今回はここまで
wikipediaとほとんど同じことしか書いてないのに、すごい時間かかったww 続けられるかな、これ。
修論発表を終了しました
ただの通過点だけど。
とにかく今は眠い。
ベンチプレス自重挙上達成!
半年以上ぶりに更新(笑)。
この前ベンチプレス85kgを1回挙げられたので嬉しかったので。
一応ここを更新していなかっただけで、筋トレ自体はずっと続けていたんだけど、フリーウェイト始めて1年でここまでしか伸びないってのは真面目にやってない証拠かと思う。どうすりゃいいんだろう。
修論そっちのけでウェイトやっていて正直そろそろやばい(苦笑)。