-
Alpha-Beta算法
鎖定
機器博弈是人工智能研究的重要分支，人類對機器博弈的研究衍生了大量的研究成果。Alpha -Beta 搜索算法是機器博弈領域中最為重要的算法之一。
- 中文名
- Alpha-Beta搜索算法
- 外文名
- Alpha-Beta搜索算法
- 別 名
- Alpha-Beta剪枝
- 適用領域
- 計算機博弈
- 應用學科
- 計算機
Alpha-Beta算法概念
在極大極小搜索的過程中，存在着2 種明顯的冗餘現象：
極大值冗餘
在圖b是與極大值冗餘對偶的現象，稱為極小值冗餘。節點A 的值應是節點B 和節點C 的值中之較小者。 現在已知節點B 的值小於節點D 的值。 由於節點C 的值應是它的諸子節點的值中之極大者，此極大值一定大於等於節點 D 的值,因此也大於節點B的值，這表明，繼續搜索節點C 的其他諸子節點已
極小值冗餘
把Alpha -Beta 剪枝應用到極大極小算法中，就形成了Alpha -Beta搜索算法。
Alpha-Beta算法實現
在搜索過程中，max 方節點的當前最優值被稱為α值，min 方節點的當前最優值被稱為β 值。在搜索開始
時，α 值為-∞，β值為+∞，在搜索過程中，max 節點使α 值遞增，min 節點則使 β值遞減，兩者構成一個區
間[ α ，β] ，這個區間被稱為窗口。窗口的大小表示當前節點值得搜索的子節點的價值取值範圍，向下搜索
的過程就是縮小窗口的過程，最終的最優值將落在這個窗口中。一旦max 節點得到其子節點的返回值大於
β值或min 節點得到其子節點的返回值小於α 值，則發生剪枝。具體算法如下所示：
1)A lpha -Be ta算法，入口參數為( P ，α ， β， d),其中P 是節點，[ α ，β]是初始窗口，d 是搜索深度；
2)若P 為葉節點，則取靜態估計值返回；
3)產生P 的所有合理着法mi ，1≤i≤n ；
4)v=-∞；
5)i=1；
6)由着法 mi 生成子節點P i ；
7)t=-A lpha -Be ta( Pi , -β, -α , d -1) ( 遞歸調用下一層)；
8)若t>v ，則v =t ，否則,轉11)；
9)若v>α ，則 α =v；
10)若v≥β，則取v 值返回；
11)i=i+1；
12)若i≤n ，則轉6)；
13)取v 值返回；
該算法使用了負極大值原理，算法只檢查是否出現β剪枝，而不需檢查是否有 α 剪枝。在Alpha -Beta 搜索中，有 3 種不同類型的評價值：高出邊界型( fail high)，由於發生了剪枝，只知道返回評分至少是 β ，不知道具體值；低出邊界型( faillow)，由於沒找到較好着法,只知道返回評分最多是α ，不知道具體值; 精確型,即返回評分在α 和β之間。
Alpha-Beta算法效率分析
將搜索樹平均分枝因子數記作b ，搜索深度記作 d ，那麼採用極大極小算法搜索的節點數為
1975 年，Knuth 等證明了，在節點排列最理想的情形下，使用A lpha -Be ta剪枝生成的節點數目為
d為偶數：
d為奇數：
這個數字大約是極大極小算法搜索節點數的平方根的2 倍左右。那麼根據公式
我們得出：如果着法順序的排列最為理想，那麼在同樣的情況下，我們可以搜索原來深度( 即不用A lpha -Beta 剪枝時的深度) 的2 倍。
Alpha-Beta算法示例代碼
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0) //如果是葉子節點（到達搜索深度要求）
return Evaluate(); //則由局面評估函數返回估值
GenerateLegalMoves(); //產生所有合法着法
while (MovesLeft()) //遍歷所有着法
{
MakeNextMove(); //執行着法
int val = -AlphaBeta(depth - 1, -beta, -alpha); //遞
歸調用 UnmakeMove(); //撤銷着法
if (val >= beta) //裁剪
{
if (val > alpha) //保留最大值
alpha = val;
return beta;
}
}
return alpha;
}
- 參考資料
-
- 1. 中國象棋Alpha-Beta搜索算法的研究與改進 ．中國知網．2009[引用日期2016-03-17]
- 2. 基於Alpha-Beta搜索算法的中國象棋人機對戰的設計與實現 ．中國知網．2012[引用日期2016-03-17]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：2次歷史版本
- 最近更新： 阿妧云