アルファベータ法
結果に影響しえない枝を証明付きで切り捨てるミニマックスの最適化で、答えは同じまま作業量だけが大幅に減る。
探索は二つの境界値を持ち回る。すでに確保できると分かっている最善スコアのアルファと、相手がすでに確保できると分かっている最善スコアのベータだ。ある枝が、すでに見つけた別の選択肢より悪いと判明した時点で、その残りを調べる必要はなくなる。相手がそこへ進ませてくれるはずがないからである。得られる答えは、完全なミニマックスとまったく同じだ。
この発想は1950年代に複数のグループがそれぞれ独立に思いつき、1975年にドナルド・クヌースとロナルド・ムーアが解析した。手の順序が理想的なら訪れるノード数はおよそ平方根まで減り、実用上は読める深さが約2倍になる。チェスエンジンが有望な手から先に試すことに力を注ぐのはそのためで、トランスポジションテーブルの助けを借りることも多い。ディープ・ブルーも同じ原理の上に作られていた。