|
アルファ・ベータ法（— ほう、）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 == 擬似コード == アルファ・ベータ法の擬似コードを以下に示す。alphabeta関数がアルゴリズムの実装であり、minimax関数はミニマックス法とインタフェースを揃えるためのラッパーである。 function minimax(node, depth) return alphabeta(node, depth, -∞, +∞) function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 if node が自分のノード foreach child of node α = max(α, alphabeta(child, depth-1, α, β)) if α ≥ β return β // カット return α else node が対戦者のノード foreach child of node β := min(β, alphabeta(child, depth-1, α, β)) if α ≥ β return α // カット return β αとβが表しているのは関心のある値の範囲である。例えば max(min(...),min(...),...,min(...)) の値を調べるときに、最初の min の値が3だったとすると、3以下の値は max により選ばれることはなくなる。つまり関心の下限(=α)が3となる。そして2つめの min の中に3以下の値が表れればminの値は必ず3以下となるが、その値には興味がないので、3以下の値が現れた時点で探索をやめる(カット)。同じようにβは関心の上限を表し、max の中で値が関心の上限を超えると分かるとカットとなる。 上記のalphabeta関数はより簡単化できる。（ネガアルファ法） function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 foreach child of node α := max(α, -alphabeta(child, depth-1, -β, -α)) if α ≥ β return α // カット return α ただしネガアルファ法では node の評価値の符号を手番によって変える必要がある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「アルファ・ベータ法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Alpha-beta pruning 」があります。 スポンサード リンク
|