-
α-β搜索法
鎖定
下棋程序關鍵之一使如何減少計算機要考慮的棋步。約翰麥卡錫發明了α-β搜索法，使計算機“明白”並不是所有情況都得考慮，有效減少了計算量。
α-β搜索法仍是解決人工智能問題中一種常用的高效方法。
- 中文名
- α-β搜索法
- 發明者
- 約翰麥卡錫
基本思想：根據倒推值的計算方法，或中取大，與中取小，在擴展和計算過程中，能剪掉不必要的分枝，提高效率。
定義：
α值：有或後繼的節點，取當前子節點中的最大倒推值為其下界，稱為α值。節點倒推值＞=α；
β值：有與後繼的節點，取當前子節點中的最小倒推值為其上界，稱為β值。節點倒推值＜=β；
α-β 剪枝：
（1） β剪枝：節點x的α值不能降低其父節點的β值，x以下的分支可停止搜索，且x的倒推值為α；
（2） α 剪枝：節點x的β值不能升高其父節點的α值，x以下的分支可停止搜索，且x的倒推值為β ；
