アルファ・ベータ枝刈りは、ゲーム木探索において最善手を効率的に見つけるためのアルゴリズムです。ミニマックス法を改良し、探索する必要のない無駄な枝を途中で切り捨てることで、計算量を大幅に削減し高速化を実現します。
アルファ・ベータ枝刈りとは
アルファ・ベータ枝刈りとは、ミニマックス法を用いたゲーム木の探索において、結果に影響しない無駄な探索を省略し、処理を高速化するアルゴリズムです。
詳しく解説
チェスや将棋などの完全情報ゲームでは、未来の手番をすべて木構造として予測するゲーム木が用いられます。基本的なミニマックス法ではすべての末端ノードを探索するため、手数が深くなるほど計算量が爆発的に増加します。アルファ・ベータ枝刈りは、すでに得られた最善の評価値を基準（アルファ値とベータ値）として保持し、それより明らかに悪化することが確定した枝の探索を途中で打ち切ります。これにより、探索の精度を落とすことなく、計算効率を飛躍的に向上させることが可能となります。
具体例・使われ方
将棋やチェスなどのボードゲームAIにおいて、コンピュータが自身の次の一手を考える際に利用されます。例えば、相手が絶対に選ばないような不利な選択肢の枝があらかじめ判明した場合、その枝の内部を細かく計算する時間をスキップし、他の有望な手番の探索に計算資源を集中させます。
似た用語との違い
ベースとなるミニマックス法がすべてのノードをしらみつぶしに探索するのに対し、アルファ・ベータ枝刈りは条件を満たさないノードをスキップする点が異なります。また、ディープラーニングを用いる近代的なゲームAIの探索手法であるモンテカルロ木探索とは異なり、評価関数と完全な探索木をベースに厳密な数値を計算するアプローチをとります。
注意点
アルファ・ベータ枝刈りの効率性は、次に探索する手の順序付けに強く依存します。最初に最善手やそれに近い手を探索できれば多くの枝を刈り込めますが、最悪の手順で探索すると枝刈りの効果がほとんど得られず、通常のミニマックス法と変わらない計算量になってしまう点に注意が必要です。