アルファ・ベータ枝刈りは、探索木内でミニマックスアルゴリズムが評価するノード数を減らそうとする木探索アルゴリズムである。これは、三目並べ、チェス、コネクト4などの二人用組合せゲームの機械プレイに一般的に使用される敵対的探索アルゴリズムである。このアルゴリズムは、ある手が以前に調べた手よりも劣ることを証明する可能性が少なくとも1つ見つかった時点で、その手の評価を停止するため、そのような手をさらに評価する必要はない。標準的なミニマックス木に適用すると、ミニマックスと同じ手を返すが、最終的な決定に影響を与え得ない枝を刈り取る。
このアルゴリズムは、Artificial intelligenceにおける分枝限定法アプローチの古典的な例であり、初期のチェスコンピュータや現代のエンジンを含む多くのゲームプレイプログラムの基盤となっている。その効率性の向上により、同じ計算予算内でより深い探索が可能になり、敵対的探索における基礎的な技法となっている。
歴史
ジョン・マッカーシーは、1956年のダートマス会議で、チェスプログラムを書いていたIBMのアレックス・バーンスタインと出会った。マッカーシーはアルファ・ベータ探索を発明し、バーンスタインに勧めたが、バーンスタインは「納得しなかった」。1958年にマッカーシーが「近似」と呼ぶものを使ったアレン・ニューウェルとハーバート・A・サイモンは、アルファ・ベータは「何度も再発明されたように見える」と書いた。アーサー・サミュエルは、チェッカーシミュレーション用の初期バージョンを持っていた。リチャーズ、ティモシー・ハート、マイケル・レビン、またはダニエル・エドワーズも、米国で独立にアルファ・ベータを発明した。マッカーシーはダートマス会議で同様のアイデアを提案し、1961年にMITのアラン・コトックを含む学生グループにそれを勧めた。アレクサンダー・ブルードノは独立にアルファ・ベータアルゴリズムを考案し、1963年に結果を発表した。ドナルド・クヌースとロナルド・W・ムーアは1975年にアルゴリズムを改良した。ジューディア・パールは、ランダムに割り当てられた葉の値を持つ木に対する期待実行時間の観点から、その最適性を2つの論文で証明した。アルファ・ベータのランダム化バージョンの最適性は、1986年にマイケル・サックスとアヴィ・ウィグダーソンによって示された。
核となるアイデア
ゲーム木は、チェス、チェッカー、リバーシなどの多くの二人用ゼロサムゲームを表現できる。木の各ノードは、ゲーム内の可能な状況を表す。各枝の終端ノード（結果）には、次の手を持つプレイヤーにとっての結果の価値を決定する数値スコアが割り当てられる。
このアルゴリズムは、アルファとベータという2つの値を維持する。これらはそれぞれ、最大化プレイヤーが保証される最小スコアと、最小化プレイヤーが保証される最大スコアを表す。初期状態では、アルファは負の無限大、ベータは正の無限大であり、両プレイヤーが最悪のスコアから始まることを意味する。最小化プレイヤー（「ベータ」プレイヤー）が保証される最大スコアが、最大化プレイヤー（「アルファ」プレイヤー）が保証される最小スコアよりも小さくなった場合（つまり、ベータがアルファより小さい場合）、最大化プレイヤーはこのノードのさらなる子孫を考慮する必要はない。実際のプレイではそれらに到達することはないからである。
実生活の例で説明すると、誰かがチェスをしていて、自分の番だとしよう。手「A」はプレイヤーの位置を改善する。プレイヤーは、より良い手を見逃していないことを確認するために、他の手を探し続ける。手「B」も良い手だが、その後プレイヤーは、それが相手に2手でのチェックメイトを強制することを許すと気づく。したがって、手Bをプレイした場合の他の結果は、相手が勝利を強制できるため、もはや考慮する必要はない。手Bの後に相手が強制できる最大スコアは負の無限大、つまりプレイヤーにとっての敗北である。これは以前に見つかった最小の位置よりも小さい。手Aは2手での強制敗北にはならない。
単純なミニマックスに対する改善点
アルファ・ベータ枝刈りの利点は、探索木の枝を排除できることにある。これにより、探索時間を「より有望な」部分木に限定でき、同じ時間でより深い探索を実行できる。その前身と同様に、これは分枝限定法アルゴリズムのクラスに属する。この最適化により、ノードが最適またはほぼ最適な順序で評価される場合（各ノードで手番側の最良の選択が最初に来るように並べる）、実効深さは単純なミニマックスの半分強に減少する。
（平均または一定の）分岐係数b、探索深さdプライの場合、評価される葉ノード位置の最大数（手の順序が最悪の場合）はO(b^d)であり、単純なミニマックス探索と同じである。探索の手の順序が最適である場合（つまり、最良の手が常に最初に探索される場合）、評価される葉ノード位置の数は、奇数深さでは約O(b 1 b 1 ... b)、偶数深さではO(b 1 b 1 ... 1)、つまりO(b^(d/2)) = O(sqrt(b^d))である。後者の場合、探索のプライが偶数であるとき、実効分岐係数はその平方根に減少し、同等に、同じ計算量で探索を2倍深く実行できる。b1b1...の説明は、最初のプレイヤーのすべての手を研究して最良のものを見つける必要があるが、それぞれについて、2番目のプレイヤーの最良の手だけが、最初の（そして最良の）プレイヤーの手以外のすべてを反駁するのに必要であり、アルファ・ベータは他の2番目のプレイヤーの手を考慮する必要がないことを保証する、というものである。
ノードがランダムな順序で考慮される場合（つまり、アルゴリズムがランダム化する場合）、漸近的に、バイナリの葉の値を持つ一様な木で評価されるノードの期待数はTheta(((b-1+sqrt(b^2+14b+1))/4)^d)である。同じ木で、葉の値が互いに独立に割り当てられ、0と1が両方とも同じ確率である場合、評価されるノードの期待数はTheta((b/2)^d)である。
実装上の考慮事項
実際には、アルファ・ベータ枝刈りは、探索深さを段階的に増やす反復深化とともに実装されることが多い。手の順序付けは、ほぼ最適な性能を達成するために重要であり、一般的なヒューリスティックには、キャプチャを最初に調べること、キラームーブを使用すること、トランスポジションテーブルを採用することが含まれる。このアルゴリズムは、水平線効果を避けるためのクワイエッセンス探索などの技法で拡張でき、主変動探索やネガスカウトなどのより高度なアルゴリズムの基礎を形成する。アルファ・ベータ枝刈りは、Chess computerシステムなどのプラットフォームで実行されるものを含むチェスプログラムで広く使用されており、さまざまなゲームプレイAIフレームワークに統合されている。
遺産と影響
アルファ・ベータ枝刈りは、Artificial intelligenceとゲーム理論に永続的な影響を与えてきた。これは初期のチェスプログラムの重要な構成要素であり、特に分岐係数が大きいゲームでは、現代のゲームエンジンでも関連性を保っている。このアルゴリズムの効率性の改善は広く研究されており、その原理は探索と最適化の他の分野に影響を与えてきた。Machine learningやDeep learningなどの新しい技法がゲームAIを変革したが、アルファ・ベータ枝刈りは依然として敵対的探索における基本的なツールであり、その歴史的発展はAI研究の協力的かつ反復的な性質を浮き彫りにしている。