↑: [[G検定に関する知識]] - ミニマックス法を効率化した改良版（1956年ごろ、マッカーシーらが提唱） - 枝刈り（プルーニング）：相手がどうせ選ばない枝だと分かった瞬間、その先を読まない - 読む深さは同じでも計算量が大幅に減る - チェスや将棋のAIではアルファベータ法が実装の基本 - cf. [[ミニマックス法]] - cf. [[ブルートフォース検索]] - 枝刈りしても**ミニマックス法と同一の最適解**が得られる（最適手が変わることはない）← 重要 - α＝自分が保証できる最低値（Maxの確定下界）、β＝相手が許す最高値（Minの確定上界）。α≧βとなった部分木を打ち切る - 枝刈り効果は**探索順序に強く依存**：評価の良い手を先に並べるほど枝刈りが増える（ムーブオーダリング）。最悪順では枝刈りがほぼ起きない。「順序に依存しない」「ランダム順が最良」は誤り ← ひっかけ - 最良ケースの探索ノード数は約**O(b^(d/2))**（bは分岐数、dは深さ）→ 同じ計算量で実質的に探索深さが約2倍 - Deep Blue（チェス）などで活用。二人零和ゲーム向けで、一人解きのハノイの塔などには適用対象外