アルファベータ法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > アルファベータ法の意味・解説 

アルファ・ベータ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/25 06:33 UTC 版)

ナビゲーションに移動 検索に移動

アルファ・ベータ法(アルファ・ベータほう、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
            α = 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 の評価値の符号を手番によって変える必要がある。

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「アルファベータ法」の関連用語

アルファベータ法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



アルファベータ法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのアルファ・ベータ法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS