アルファベータ枝刈り

アルファベータ枝刈りは、手と応手を比較するプログラムであるチェスエンジンの探索を高速化する。探索は木として考えられ、各ノードが局面、各枝が合法手を表す。枝刈りがなければ、最終的に無関係と分かる多数の変化手順まで調べる必要がある。

この手法は探索中に二つの境界を保つ。アルファは、現在の経路で一方がすでに保証できる最良の結果である。ベータは、相手がすでに利用できる別案によって作られる上限である。ある変化が悪すぎて合理的な選手なら決して選ばないと分かれば、それ以上深く調べても上位ノードの判断は変わらない。

枝を止める理由は、単に手が見た目に悪いからではなく、探索木内の論理的な境界による。同じ深さで、探索限界の評価も同一なら、アルファベータは双方が最善の応手を選ぶと仮定した完全探索と同じ選択を返す。

節約効果は手の順序に大きく左右される。強い手を早く試すと有効な境界が早く確立し、より多くの枝を深く調べずに止められる。有限探索の終点では、局面へ数値的推定を与える評価関数が値を供給する。