搜尋演算法
簡單Minimax搜尋
象棋屬於零和博弈，有紅方和黑方，雙方的收益總和為0，一方的優勢總是伴隨著另一方的劣勢。此時，我們可以使用Minimax進行搜尋。
為了方便理解，我們暫且把Maximizing Player稱為「紅方」，把Minimizing Player稱為「黑方」（實際上則不一定），我們的評估函式暫時返回的是相對於紅方的分數（分高說明紅方優勢，分低說明紅方劣勢）。
博弈的雙方都想讓收益最大化，紅方想讓分數儘量高，黑方想讓分數儘量低，這樣就能最大程度上保證自己這方的優勢，同時讓對方佔到的優勢最小。
舉個例子，紅方在一個局面有兩種走法。一種走法可以吃掉對方的車，此時的分數是+500，另一種走法是送掉自己的車，此時的分數是-500。紅方當然會選擇對自己有利的走法，即第一種，所以該節點的分數就是+500。
虛擬碼如下：
int minimax(int depth, bool isMaximizingPlayer) { // 層數, 是否紅方
if (depth == 0 || isGameOver()) { // 搜尋到葉子節點或遊戲結束，直接返回評估
return evaluate();
}
if (isMaximizingPlayer) { // 如果當前是紅方
int maxEval = INT_MIN; // 初始化為負無窮，方便程式找出所有走法中分數的最大值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = minimax(depth - 1, false); // 向下一層搜尋，獲得該走法對應的子節點的分數
undoMove(move); // 恢復到走子前的局面
maxEval = std::max(maxEval, eval);
}
return maxEval;
} else { // 如果當前是黑方
int minEval = INT_MAX; // 初始化為正無窮，方便程式找出所有走法中分數的最小值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = minimax(depth - 1, true); // 向下一層搜尋，獲得該走法對應的子節點的分數
undoMove(move); // 恢復到走子前的局面
minEval = std::min(minEval, eval); // 取最小值
}
return minEval;
}
}Alpha-Beta剪枝的過程介紹
上面實現的簡單Minimax搜尋，效率其實是很低的。我們這時就要引入一種新的搜尋策略——Alpha-Beta剪枝，這種剪枝方法可以在不改變結果的前提下大大減少搜尋的節點數。
上文我們提到過，紅方的目的是使得分儘量高，也就是說當前節點的分數是所有子節點分數的最大值，黑方則相反。
參考上圖，我們可以舉個例子說明一下Alpha-Beta剪枝的原理。
引擎搜完葉子節點的5和6，可以推斷出這兩個節點的父節點（圖中ID：2）的分數是min(5,6)=5。這個節點的父節點在MAX層上（圖中ID：1），是取其子節點分數的最大值，所以它的分數至少是5。子節點的分數只有>5才有搜下去的必要，否則不會比「ID：2」這一路線更優。
接下來我們繼續搜尋「ID：3」這一路線，搜完葉子節點的「7」和「4」之後，由於「ID：3」處在MIN層，其分數是取其子節點分數的最小值，所以這個節點的分數必然≤4，不可能比「ID：2」這一條路線更優，沒有再搜下去的必要了，我們可以把後續的子節點（即灰色的5）剪掉。
其它灰色的部分也是同理，大家可自行按照上面的步驟推斷。
根據理論推斷是會了，但這仍是紙上談兵，如何編寫相關程式碼實現該功能呢？且聽下回分解。
Alpha-Beta剪枝的程式碼實現
為了用程式碼實現Alpha-Beta剪枝，我們需要引入alpha和beta兩個量，alpha是紅方能保證至少獲得的分數，beta是黑方能保證至多獲得的分數（這裡的分數都是從紅方視角看的）。也就是說，最優走法的分數必然≥alpha而且≤beta。
在最開始呼叫「alphaBeta」函式的時候，我們應該把alpha設為負無窮，把beta設為正無窮。
當我們搜尋一個節點的時候，我們需要接受從父節點傳來的alpha和beta值，接著判斷該節點處於MAX層還是MIN層。
這裡還是舉一個例子方便讀者理解，假設我們處於MAX層（即紅方），父節點傳遞的alpha值是5，beta值是8。
因為當前節點的分數是從子節點的分數中取最大值得到的，所以我們在搜尋的時候可以保證當前節點的分數≥子節點的分數，應該根據子節點的分數更新alpha的值。如果我們此時搜到一個子節點，分數為10，此時當前節點的分數必定≥10。但我們不要忘了，上一層是MIN，取的是子節點中的最小分數。若當前節點的分數超過了beta，必然不會比其父節點之前搜過的某個子節點分數低，不會被父節點採納；若當前節點的分數等於beta，必然不會比其父節點之前搜過的某個子節點更優。我們可以直接使用break跳出迴圈，進行Beta剪枝，同時返回目前搜過的子節點的最大分數（目前的搜尋程式碼中，這裡返回值不重要，只需要保證該節點不被父節點採納即可）。
判斷當前節點的分數是否≥beta，可以等同於判斷alpha≥beta，因為alpha就是按照子節點的分數通過取最大值進行更新的。
MIN層同理，這裡不再贅述。
虛擬碼如下：
int alphaBeta(int depth, int alpha, int beta, bool isMaximizingPlayer) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
if (isMaximizingPlayer) { // 如果當前是紅方
int maxEval = INT_MIN; // 初始化為負無窮，方便程式找出所有走法中分數的最大值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = alphaBeta(depth - 1, alpha, beta, false); // 向下一層搜尋，獲得該走法對應的子節點的分數
undoMove(move); // 恢復到走子前的局面
maxEval = std::max(maxEval, eval); // 取最大值
alpha = std::max(alpha, eval);
if (beta <= alpha)
break; // Beta剪枝
}
return maxEval;
} else { // 如果當前是黑方
int minEval = INT_MAX; // 初始化為正無窮，方便程式找出所有走法中分數的最小值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = alphaBeta(depth - 1, alpha, beta, true); // 向下一層搜尋，獲得該走法對應的子節點的分數
undoMove(move); // 恢復到走子前的局面
minEval = std::min(minEval, eval); // 取最小值
beta = std::min(beta, eval);
if (beta <= alpha)
break; // Alpha剪枝
}
return minEval;
}
}繼續簡化，引入Negamax
前面我們的分數一直是相對於紅方視角的，需要將紅方和黑方分類討論，這顯然使程式碼複雜化了。為了解決這個問題，我們需要引入Negamax。
引入Negamax後，我們對雙方可以使用同樣的處理策略，省去了編寫MIN 方的程式碼的必要性，但是評估函式需要改成相對於走子方的分數。
如果當前走子方是紅方，需要返回相對於紅方的分數；如果當前走子方是黑方，需要返回相對於黑方的分數。
由於我們把兩種情況合併成了一種情況，判斷紅黑方的參數可以刪去。
在搜尋子節點的時候，我們需要從MAX層切換到MIN層，或者從MIN層切換到MAX層，應該如何做呢？
在這裡，我們繼續舉一個例子來說明。假設當前節點從父節點傳下來的alpha值為5，beta值為8，說明最優走法的分數一定在5和8之間，接下來我們把分數視角切換到對手，最優走法的分數一定在-8和-5之間，-8和-5就分別是傳遞給子節點的alpha值和beta值。
所以，傳給子節點的alpha和beta值應該是-beta和-alpha。
下面是引入Negamax後的虛擬碼：
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // 初始化為負無窮，方便程式找出所有走法中分數的最大值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = -alphaBeta(depth - 1, -beta, -alpha); // 向下一層搜尋，獲得該走法對應的子節點的分數
undoMove(move); // 恢復到走子前的局面
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta)
break; // Beta剪枝
}
return maxEval;
}有些資料上的程式碼可能是這樣的：
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
for (Move move : getPossibleMoves()) {
makeMove(move);
int val = -alphaBeta(depth - 1, -beta, -alpha);
undoMove(move);
if (val >= beta) {
return beta; // Beta剪枝
}
if (val > alpha) {
alpha = val; // 更新Alpha的值
}
}
return alpha;
}其實這兩者是等價的，正常情況下，alpha<beta，所以alpha≥beta的情況只能是分數更新，導致alpha變大，發生Beta剪枝，所以直接和val進行比較也是一樣的。
空步裁剪（Null Move Pruning）
一般來說，一個局面我方什麼都不走（或者說走了一個「空步」），而是把走子權讓給對方，我方是吃虧的。即最優走法的分數一般來說不會比走「空步」的分數低。
我們可以利用這一點編寫一個剪枝策略——空步裁剪。空步裁剪是一種冒險策略，就是基於上面假設進行的，把比「空步」分數低的招法剪掉。
為了加快搜索，我們可以對「空步」搜尋的層數額外減少R（一般是2-3）層。由於我們只關心「空步」的分數和beta相比是大還是小，所以應該用零視窗搜尋（[beta - 1, beta]），使Alpha-Beta剪枝在搜尋空步時發揮的作用最大。
由於走子方互換，傳遞給子節點的alpha值和beta值也要按照之前的方法進行轉換，也就是-beta和-beta + 1。
基於空步的分數≤最優走法的分數這個假設，如果返回的評估≤beta-1，說明後續該節點的alpha值有可能達不到beta，不進行剪枝；如果返回的評估≥beta，說明最優走法的分數也一定≥beta，也就是說後續alpha在更新的時候也會≥beta，可以直接進行剪枝。
然而一些局面並不滿足之前我們提到過的假設，如國際象棋的迫移局面（Zguzwang），若使用空步裁剪，則會使引擎判斷錯誤，於是我們可以設計一個「isNullMoveAllowed」函式判斷是否滿足空步裁剪的條件，儘量規避這種現象。
虛擬碼如下：
// R是空步裁剪搜尋中額外減去的層數
const int R = 3;
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
// Null Move Pruning
if (depth >= R + 1 && isNullMoveAllowed()) {
makeNullMove(); // 走一步「空步」
int nullMoveEval = -alphaBeta(depth - R - 1, -beta, -beta + 1); // 用[beta - 1, beta]進行搜尋
undoNullMove(); // 恢復
if (nullMoveEval >= beta) {
return beta; // 如果beta的值還不如走「空步」的分數高，就直接剪掉
}
}
int value = INT_MIN;
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走棋
value = std::max(value, -alphaBeta(depth - 1, -beta, -alpha));
undoMove(move); // 恢復
alpha = std::max(alpha, value);
if (alpha >= beta) {
break; // Beta剪枝
}
}
return value;
}PVS（主要變例搜尋）
PVS是對Alpha-Beta剪枝的增強，可以提高Alpha-Beta剪枝的效率。簡單來說，PVS先對第一個子節點進行[alpha, beta]的全視窗搜尋，再對剩餘子節點使用[alpha, alpha+1]的零視窗搜尋。零視窗搜尋結束後，如果該節點搜尋返回的評估在(alpha, beta)之間，說明該節點有希望，於是繼續進行一次全視窗搜尋。如果返回的評估超出了(alpha, beta)，說明這個節點必然會被剪枝。
虛擬碼如下：
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // 初始化為負無窮，方便程式找出所有走法中分數的最大值
bool firstChild = true; // 標記是否為第一個子節點
for (const Move& move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval;
if (firstChild) {
// 對第一個子節點使用全視窗搜尋
eval = -alphaBeta(depth - 1, -beta, -alpha);
firstChild = false;
} else {
// 對剩餘子節點使用零視窗搜尋
eval = -alphaBeta(depth - 1, -alpha - 1, -alpha);
if (eval > alpha && eval < beta) {
// 如果零視窗搜尋未能確定性地剪枝，則進行全視窗重新搜尋
eval = -alphaBeta(depth - 1, -beta, -eval);
}
}
undoMove(move); // 恢復到走子前的局面
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // Beta 剪枝
}
}
return maxEval;
}注意
為了簡化程式碼，這裡並未加入空步裁剪，後文也是單獨介紹某種方法，而不是疊加在一起。
靜態搜尋
靜態搜尋（Quiescent Search）可以用來克服水平面效應。一般來說發生互相吃子，評估函式會發生劇烈變化，引入靜態搜尋，可以返回一個更加穩定的評估值。引入靜態評估後，達到葉子節點時，我們不直接返回評估函式的值，而是進行一次靜態搜尋，繼續探索吃子的走法。
虛擬碼如下：
int qsearch(int alpha, int beta) {
int standPat = evaluate(); // 當前局面不做任何動作的評估值
if (standPat >= beta) {
return beta; // 剪枝
}
if (alpha < standPat) {
alpha = standPat; // 更新 alpha
}
for (Move move : getPossibleCaptures()) { // 只考慮吃子的走法
makeMove(move);
int eval = -qsearch(-beta, -alpha); // 靜態搜尋下一層
undoMove(move);
if (eval >= beta) {
return beta; // 剪枝
}
if (eval > alpha) {
alpha = eval; // 更新 alpha
}
}
return alpha;
}
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return qsearch(alpha, beta); // 在深度為0或遊戲結束時進入靜態搜尋
}
int maxEval = INT_MIN; // 初始化為負無窮
for (Move move : getPossibleMoves()) { // 生成所有走法
makeMove(move); // 執行走法
int eval = -alphaBeta(depth - 1, -beta, -alpha); // 遞迴搜尋
undoMove(move); // 撤銷走法
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // Beta剪枝
}
}
return maxEval;
}