新手立體四子棋AI教程(3)——極值搜索與Alpha-Beta剪枝

上一篇我們講了評估函數，這一篇我們來講講立體四子棋的搜索函數。

一、極值搜索

極值搜索是game playing領域裡非常經典的演算法，它使用深度優先搜索（因為限制最大層數，所以也可以稱為迭代加深搜索）來遍歷未來n步的走子情況。在每層模擬中都會選擇對自己最優的位置，通過最大化自己的利益（也就是上一篇提到的評估演算法）來取勝。α-β剪枝也是類似的思想，只不過效率更高，因為它刪減了一些不需要遍歷的結點。

下圖是一個極小極大演算法的例子，MAX層代表自己，總是選取下面三個結點中的最大值，MIN層代表對手，總是選取下面一層結點中的最小值。在此例子中，MAX下一步會選擇a1。

Minimax的偽代碼如下(遞歸實現)：

function minimax(node, depth) // 指定當前節點和搜索深度 // 如果能得到確定的結果或者深度為零，使用評估函數返回局面得分 if node is a terminal node or depth = 0 return the heuristic value of node // 如果輪到對手走棋，是極小節點，選擇一個得分最小的走法 if the adversary is to play at node let α := +∞ foreach child of node α := min(α, minimax(child, depth-1)) // 如果輪到我們走棋，是極大節點，選擇一個得分最大的走法 else {we are to play at node} let α := -∞ foreach child of node α := max(α, minimax(child, depth-1)) return α;

二、實現

首先我們聲明可能會用到的函數：

int dfs(int board[4][4][4], int deep = 6);int findWhiteScoreMaxValue(int board[4][4][4],int deep);int findWhiteScoreMinValue(int board[4][4][4],int deep);

dfs函數是我們函數對外調用的介面，也是DFS搜索的啟動函數。接下來的搜索為了避免混亂，我們都將白方考慮為自己。

findWhiteScoreMaxValue(board, deep);

在dfs函數中中我們通過上述語句開始搜索。

int ChessBoard::findWhiteScoreMaxValue(int board[4][4][4], int deep){if(deep <= 0) { int score = getSideScore(board, chessPicesStatus::white) - getSideScore(board, chessPicesStatus::black); return score; } else { int maxVal = -1000000; PicesPosList list = getAvailablePos(board,chessPicesStatus::white); for(auto iter = list.begin();iter != list.end();iter++) { board[iter->x][iter->y][iter->z] = chessPicesStatus::white; int val = findWhiteScoreMinValue(board, deep -1); if(val > maxVal) { maxVal = val; whiteTargetPos.x = iter->x; whiteTargetPos.y = iter->y; whiteTargetPos.z = iter->z; } board[iter->x][iter->y][iter->z] = chessPicesStatus::empty; } return maxVal; }}

在上述代碼中，我們首先判斷是不是葉子節點，如果是則直接返回當前的結果，如果不是，開始下一步迭代。

在迭代中，我們用第一篇介紹過的方法，產生當前所有可能的落子位置，然後在每個位置下棋，進入Min層（對手走子）的搜索，在當前節點所有可能性搜索完畢後，判斷當前節點是否是最大節點，如果是則保存當前最大值以及走子位置，如果不是則繼續搜索下一個位置。Min層與Max大部分代碼一致，此處不再貼出。

三、Alpha-Beta剪枝演算法

在大部分棋類AI中，剪枝是必須的。假設我們計算未來六步的結果，也就是六層的迭代，每層都有16中可能性，那麼節點數量將達到16^6=16，777，216個，耗時極大，實際上最好一步能控制在 5 秒 以內。順便說一下層數的問題，首先思考層數必須是偶數。因為奇數節點是AI，偶數節點是玩家，如果AI下一個子不考慮玩家防守一下，那麼這個估分明顯是有問題的。然後，至少需要進行4層思考，如果連4四層都考慮不到，那就是只看眼前利益，那麼棋力會非常非常弱。 如果能進行6層思考基本可以達到隨便贏普通玩家的水平了。

Alpha Beta 剪枝演算法的基本依據是：棋手不會做出對自己不利的選擇。依據這個前提，如果一個節點明顯是不利於自己的節點，那麼就可以直接剪掉這個節點。

前面講到過，AI會在MAX層選擇最大節點，而玩家會在MIN層選擇最小節點。那麼如下兩種情況就是分別對雙方不利的選擇：

1. 在MAX層，假設當前層已經搜索到一個最大值 X， 如果發現下一個節點的下一層（也就是MIN層）會產生一個比X還小的值，那麼就直接剪掉此節點。

解釋一下，也就是在MAX層的時候會把當前層已經搜索到的最大值X存起來，如果下一個節點的下一層會產生一個比X還小的值Y，那麼之前說過玩家總是會選擇最小值的。也就是說這個節點玩家的分數不會超過Y，那麼這個節點顯然沒有必要進行計算了。

通俗點來講就是，AI發現這一步是對玩家更有利的，那麼當然不會走這一步。

1. 在MIN層，假設當前層已經搜索到一個最小值 Y， 如果發現下一個節點的下一層（也就是MIN層）會產生一個比Y還大的值，那麼就直接剪掉此節點。

這個是一樣的道理，如果玩家走了一步棋發現其實對AI更有利，玩家必定不會走這一步。

如上圖所示，在第二層，也就是MIN層，當計算到第三個節點的時候，已知前面有一個3和一個6，也就是最小值為3。 在計算第三個節點的時候，發現它的第一個孩子的結果是5，因為它的孩子是MAX節點，而MAX節點是會選擇最大值的，那麼此節點的值不會比5小，因此此節點的後序孩子就沒有必要計算了，因為這個節點不可能小於5，而同一層已經有一個值為3的節點了。

其實這個圖裡面第三層分數為7的節點也是不需要計算的。

這是 MAX 節點的剪枝，MIN節點的剪枝也是同樣的道理，就不再講了。 Alpha Beta 剪枝的 Alpha 和 Beta 分別指的是MAX 和 MIN節點。

我們直接上代碼：

int ChessBoard::findWhiteScoreMaxValue(int board[4][4][4], int deep,int alpha,int beta){ if(deep <= 0) { int score = getSideScore(board, chessPicesStatus::white) - getSideScore(board, chessPicesStatus::black); return score; } else { int maxVal = -1000000; PicesPosList list = getAvailablePos(board,chessPicesStatus::white); for(auto iter = list.begin();iter != list.end();iter++) { board[iter->x][iter->y][iter->z] = chessPicesStatus::white; int val = findWhiteScoreMinValue(board, deep -1,alpha,maxVal > beta ? maxVal : beta); if(val > maxVal) { maxVal = val; whiteTargetPos.x = iter->x; whiteTargetPos.y = iter->y; whiteTargetPos.z = iter->z; } board[iter->x][iter->y][iter->z] = chessPicesStatus::empty; if(maxVal > alpha) break; } return maxVal; }}int ChessBoard::findWhiteScoreMinValue(int board[4][4][4], int deep,int alpha,int beta){ if(deep <= 0) { int score = getSideScore(board, chessPicesStatus::white) - getSideScore(board, chessPicesStatus::black); return score; } else { int minVal = 1000000; PicesPosList list = getAvailablePos(board,chessPicesStatus::black); for(auto iter = list.begin();iter != list.end();iter++) { board[iter->x][iter->y][iter->z] = chessPicesStatus::black; int val = findWhiteScoreMaxValue(board, deep -1, minVal < alpha ? minVal : alpha ,beta); if(val < minVal) { minVal = val; blackTargetPos.x = iter->x; blackTargetPos.y = iter->y; blackTargetPos.z = iter->z; } board[iter->x][iter->y][iter->z] = chessPicesStatus::empty; if(val < beta) break; } return minVal; }}

至此，我們的搜索函數已經基本完成。但是此時的剪枝效率非常低，因為剪枝的效率依賴於大小排列是否整齊。比如在Max層，最理想的效果一定是各個節點從大到小排列，Min層也是一樣的道理。所以在下一篇文章中我會講到到啟發式搜索。

本文首發於我的博客：新手立體四子棋AI教程(3)--極值搜索與Alpha-Beta剪枝 - Scobbing - 博客園

參考文獻：

https://www.cnblogs.com/pangxiaodong/archive/2011/05/26/2058864.html

https://www.zhihu.com/question/27221568/answer/127599152

http://blog.csdn.net/lihongxun945/article/details/50668253

致謝！