アルファ・ベータ法

アルファ・ベータ法（アルファ・ベータほう、）は完全情報ゲームにおける探索アルゴリズムの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 α ≥ β
                 break // βカット
        return α

     else node が対戦者のノード
         foreach child of node
             β := min(β, alphabeta(child, depth-1, α, β))
             if α ≥ β
                 break // αカット
         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 の評価値の符号を手番によって変える必要がある。

 関連項目 
 分枝限定法
 反復深化深さ優先探索
 ミニマックス法
 アーサー・サミュエル

 外部リンク 
 Game Theory Chapter 5, Sections 5.4 to 5.7
 Game Playing: Alpha - Beta Pruning
  G13GAM -- Game Theory
 Chess Tree Search
 Alpha-Beta Search
 AND/ORグラフとゲーム木

Category:ゲーム理論
Category:最適化アルゴリズムとメソッド
Category:検索アルゴリズム
Category:数学に関する記事