α-β搜尋法

下棋程式關鍵之一使如何減少計算機要考慮的棋步。約翰麥卡錫發明了α-β搜尋法，使計算機“明白”並不是所有情況都得考慮，有效減少了計算量。

α-β搜尋法至今仍是解決人工智慧問題中一種常用的高效方法。

基本思想：根據倒推值的計算方法，或中取大，與中取小，在擴展和計算過程中，能剪掉不必要的分枝，提高效率。

定義：

α值：有或後繼的節點，取當前子節點中的最大倒推值為其下界，稱為α值。節點倒推值>=α；

β值：有與後繼的節點，取當前子節點中的最小倒推值為其上界，稱為β值。節點倒推值<=β；

α-β 剪枝：

（1） β剪枝：節點x的α值不能降低其父節點的β值，x以下的分支可停止搜尋，且x的倒推值為α；

（2） α 剪枝：節點x的β值不能升高其父節點的α值，x以下的分支可停止搜尋，且x的倒推值為β ；