アルファ・ベータ法
アルファ・ベータ法の最新ニュースをまとめて検索！
アルファ・ベータ法（— ほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの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
β := min(β, alphabeta(child, depth-1, α, β))
if α ≥ β
return α // カット
return β
else // node が自分のノード
foreach child of node
α = max(α, 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）』 Text is available under GNU Free Documentation License.
最終更新 2009年8月11日 (火) 18:13 （日時は個人設定で未設定ならばUTC）。
【アルファ・ベータ法】変更履歴
