アルファベータ枝刈りとは
アルファベータ枝刈りとは、チェスのようなゲームでコンピュータが次の一手を先読みするとき、調べても結論が変わらない展開の検討を途中で打ち切り、計算を大幅に節約する技法です。互いに最善を尽くす前提で手を読むミニマックス法とセットで使われ、ゲームAIの探索を支えてきました。
「これ以上調べても無駄」を見抜く仕組み
すでに有望な手Aが見つかっているとします。次に手Bを調べ始めたところ、相手に手痛い反撃を許す筋が一つ見つかりました。この瞬間、Bの残りの展開を調べる意味は消えます。どう転んでもAより悪いと確定したからです。
名前のアルファとベータは、この「打ち切ってよいか」を判定するために持ち歩く2つの基準値のことです。自分が確保できる下限と相手が許す上限を更新しながら読み進め、範囲から外れた枝を端から刈っていく。地味ながら強力な発想でしょう。
読みは2倍深く、答えは同じ
効果は劇的です。理想的な順序で調べた場合、同じ計算量でおよそ2倍の深さまで先読みでき、チェスの例では100万を超える局面の評価が約2,000まで減った（99.8%減）と報告されています。しかも刈るのは結論に影響しない枝だけなので、最終的に選ばれる手は、全部調べた場合と変わりません。検討の量を絞っても判断の質を落とさない。経営の意思決定にも通じる、資源配分のお手本のような考え方です。
AI黎明期から磨かれてきた技法
原型のアイデアは、「人工知能」という言葉が生まれた1956年のダートマス会議のMcCarthyに始まり、Newell・Simon（1958年）、Brudno（1963年）ら複数の研究者が独立にたどり着きました。1975年にKnuthとMooreが理論を整理し、後にPearlが最適性を証明しています。ChatGPT登場の60年以上前から、AIは「先読みの効率化」を競っていたわけです。
Topicチェス王者を倒したDeep Blueの中身も、この枝刈りだった
1997年5月、IBMのDeep Blueが世界チェス王者カスパロフを破った歴史的な一戦。その頭脳は、専用チップで並列化したアルファベータ探索で、毎秒2億局面を評価するものでした。データから学ぶニューラルネットワークではなく、ルールに基づく探索と枝刈りの徹底で人類の王者に勝った、記号的AIの金字塔です。「学習だけがAIではない」ことを示す好例といえるでしょう。
アルファベータ枝刈りに関するよくある質問
- 「アルファ」と「ベータ」は何を指していますか？
- 先読みの最中に持ち歩く2つの基準値の名前です。自分側が少なくとも確保できる評価の下限がアルファ、相手側がそれ以上許さない上限がベータで、この範囲を外れた展開は調べずに打ち切ります。
- 途中で打ち切って、好手の見落としは起きないのですか？
- 起きません。打ち切るのは「選ばれないことが既に確定した手の続き」だけなので、すべて調べた場合と同じ手にたどり着きます。速くなるだけで、結論の質は落ちません。
- アルファベータ枝刈りはチェス以外でも使われますか？
- チェッカーやリバーシなど、二人が交互に打ち合うゲームのAIで広く使われてきました。互いの最善を読み合う構造を持つゲームに向いた技法です。
