alpha-beta剪枝算法實作中國象棋人機對戰
Github倉庫：https://github.com/dick20/Artificial-Intelligence
問題介紹
本實驗要求編寫一個中國象棋博弈程式，使用alpha-beta剪枝算法，實作人機對弈。因為是人機博弈，是以我們需要使得電腦比較聰明，而方法就是要電腦選擇走比較好的步驟。機器是基于搜尋來下棋的，我們需要讓機器考慮比較長遠的情況，然後做出比較好的選擇，而為了提高搜尋效率，就應用到了alpha-beta剪枝算法。
算法介紹
對于博弈問題，我們首先考慮的是極小極大搜尋算法。我們規定：MAX代表程式方，MIN代表對手方，P代表一個棋局（即一個狀态）。有利于MAX的勢态， f ( P ) f(P) f(P)取正值；有利于MIN的勢态， f ( P ) f(P) f(P)取負值；勢态均衡， f ( P ) f(P) f(P)取零。 f ( P ) f(P) f(P)的大小由棋局勢态的優劣來決定。評估棋局的靜态函數要考慮兩個方面的因素：
- 雙方都知道自己走到了什麼程度
- 雙方都知道下一步能夠做什麼
基于這個前提，博弈雙方要考慮的問題是：如何産生一個最好的走步，能盡快獲勝。是以，就引出來極小極大搜尋算法。
極小極大搜尋的基本思想是：
- 當輪到MIN走步的節點時，MAX應考慮最壞的情況（是以， f ( P ) f(P) f(P)取極小值）。
- 當輪到MAX走步的節點時，MAX應考慮最好額情況（是以， f ( P ) f(P) f(P)取極大值）。
- 當評價往回倒退時，相應于兩位棋手的對抗政策，不同層上交替地使用1、2兩種方法向上傳遞倒推值。
MIN、MAX過程将生成後繼節點與估計格局兩個過程分開考慮，即需要先生成全部搜尋樹，然後再進行每個節點的靜态估計和倒推值計算。實際上，這種方法效率極低。而alpha-beta基于這個過程，給了我們一個高效的算法。在極大層中定義下界值 α \alpha α，它表明該MAX節點向上的倒推值不會小于 α \alpha α；在極小層中定義上界值 β \beta β，它表明該MIN節點向上的倒推值不會大于 β \beta β。
剪枝規則如下：
- α \alpha α剪枝。若任一極小層節點的 β \beta β值不大于它任一前驅極大層節點的 α \alpha α值，即 α \alpha α（前驅層） ≥ β \ge \beta ≥β（後繼層），則可以中止該極小層中這個MIN節點以下的搜尋過程。這個MIN節點最終的倒推值就确定為這個 β \beta β值。
- β \beta β剪枝。若任一極大層節點的 α \alpha α值不小于它任一前驅極小層節點的 β \beta β值，即 α \alpha α（後繼層） ≥ β \ge \beta ≥β（前驅層），則可以中止該極大層中這個MAX節點以下的搜尋過程。這個MAX節點最終的倒推值就确定為這個 α \alpha α值。
算法實作
本次項目的UI是參考了網上的代碼，使用Java實作。重點分析alpha-beta剪枝算法，關于UI部分就不詳細分析了。
首先我們來看棋局的評估，能否對棋局有一個好的評估是這個算法很關鍵的一環。我們需要對棋局做出合适的評估，以确定最好的走步。評估的方面有三個，一個是下一步的棋力，第二個是下一步能做什麼，第三個是棋子的價值。先看棋力，棋力的評估主要是根據棋子所在的位置來分析。這裡我們寫好了每個棋子在不同位置的棋力，這是參考了一些論文得出來的。第二個是下一步能做什麼，我們可以根據下一步能做什麼來判斷這個走步的好壞。在象棋遊戲中，一個好的走步我們期望是能夠吃掉對方的棋，而且吃掉的棋子價值越大，這個走步越好。當然，如果下一步能夠将軍，那麼這個走步很有可能就是我們想要的。于是我們對下一步能做什麼做一個估值：如果下一步能将軍，那麼它的估值将大大增加（+9999）；如果下一步能吃掉對方的棋子，那麼它的估值将會有一定的增加（車：+500，馬或炮：+100）；如果下一步隻能吃掉對方的卒，那麼它的估值就會下降（-20），因為多數情況下吃掉對方的卒都沒什麼好處。最後是棋子的價值，這是比較固定的因素，因為我們普遍認為某些棋子的價值是比其他棋子大的（比如車的價值一般來說都比卒要大）。
每次估值都需要分開兩方的棋子來進行估值。即算出程式方棋局的總體價值和對手方棋局的整體價值。用程式方估值-對手方估值作為這個狀态下的估值。如果這個估值大于0，說明程式方占優勢；反之，說明對手方占優勢。
完成好估值後，就可以開始alpha-beta的剪枝算法了。首先确定博弈樹的深度，通俗來說就是要讓程式往後推演幾步。當然推演的步數越多，越能找到一個好的走步，但是所需的時間也就越多。然後我們需要使用一個标記來表示目前是極大層還是在極小層，根據标記來計算目前節點的 α \alpha α或 β \beta β。如果在極大層，我們需要獲得它下面所有極小層的倒推值的極大值（實際上不是所有）；如果在極小層，就需要獲得它下面所有極大層的倒推層的極小值（實際上不是所有）。這裡就牽涉到了剪枝。以在極大層為例，如果目前MAX節點提供的倒推值 α \alpha α大于其前驅極小層MIN節點的 β \beta β，那麼說明這個MAX節點以下搜尋提供的值不可能小于 α \alpha α，也就沒有繼續搜尋的意義了，是以就可以直接結束這個MAX節點的搜尋，這就是剪枝。
關鍵代碼分析
- 棋子本身的價值評估：
- 将軍：80
- 士：0
- 象：0
- 馬：300
- 車：500
- 炮：300
- 卒：100
- 棋子位置的價值評估：
- 将軍
int[][] JiangPosition = new int[][] { {0, 0, 0, 1, 5, 1, 0, 0, 0}, {0, 0, 0, -8, -8, -8, 0, 0, 0}, {0, 0, 0, -9, -9, -9, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0} }; - 士
int[][] ShiPosition = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 3, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0} }; - 象
int[][] XiangPosition = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {-2, 0, 0, 0, 3, 0, 0, 0, -2}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0} }; - 馬
int[][] MaPosition = new int[][] { {0, -3, 2, 0, 2, 0, 2, -3, 0}, {-3, 2, 4, 5, -10, 5, 4, 2, -3}, {5, 4, 6, 7, 4, 7, 6, 4, 5}, {4, 6, 10, 7, 10, 7, 10, 6, 4}, {2, 10, 13, 14, 15, 14, 13, 10, 2}, {2, 10, 13, 14, 15, 14, 13, 10, 2}, {2, 12, 11, 15, 16, 15, 11, 12, 2}, {5, 20, 12, 19, 12, 19, 12, 20, 5}, {4, 10, 11, 15, 11, 15, 11, 10, 4}, {2, 8, 15, 9, 6, 9, 15, 8, 2}, {2, 2, 2, 8, 2, 8, 2, 2, 2} }; - 車
int[][] JuPosition = new int[][] { {-6, 6, 4, 12, 0, 12, 4, 6, -6}, {5, 8, 6, 12, 0, 12, 6, 8, 5}, {-2, 8, 4, 12, 12, 12, 4, 8, -2}, {4, 9, 4, 12, 14, 12, 4, 9, 4}, {8, 12, 12, 14, 15, 14, 12, 12, 8}, {8, 11, 11, 14, 15, 14, 11, 11, 8}, {6, 13, 13, 16, 16, 16, 13, 13, 6}, {6, 8, 7, 14, 16, 14, 7, 8, 6}, {6, 12, 9, 16, 33, 16, 9, 12, 6}, {6, 8, 7, 13, 14, 13, 7, 8, 6} }; - 炮
int[][] PaoPosition = new int[][] { {0, 0, 1, 3, 3, 3, 1, 0, 0}, {0, 1, 2, 2, 2, 2, 2, 1, 0}, {1, 0, 4, 3, 5, 3, 4, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {-2, 0, -2, 0, 6, 0, -2, 0, -2}, {3, 0, 4, 0, 7, 0, 4, 0, 3}, {10, 18, 22, 35, 40, 35, 22, 18, 10}, {20, 27, 30, 40, 42, 40, 30, 27, 20}, {20, 30, 45, 55, 55, 55, 45, 30, 20}, {20, 30, 50, 65, 70, 65, 50, 30, 20}, {0, 0, 0, 2, 4, 2, 0, 0, 0} }; - 卒
int[][] BingPosition = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {-2, 0, -2, 0, 6, 0, -2, 0, -2}, {3, 0, 4, 0, 7, 0, 4, 0, 3}, {10, 18, 22, 35, 40, 35, 22, 18, 10}, {20, 27, 30, 40, 42, 40, 30, 27, 20}, {20, 30, 50, 65, 70, 65, 50, 30, 20}, {0, 0, 0, 2, 4, 2, 0, 0, 0} };
- 對下一步吃子進行估值：
private int estimate_myself(Piece piece) { // System.out.println(piece.Info); if (piece.Info == "bb0" || piece.Info == "rb0") return 0; int totalValue = 0; ArrayList<int[]> next = Rule.getNextMove(piece.Info, piece.pos, Board); for (int[] n : next) { Piece p = Board.getPiece(n); if (p != null && Board.getPiece(n).character == 'b') { totalValue += 9999; break; } if (p != null && Board.getPiece(n).character == 'j') { totalValue += 500; break; } if (p != null && Board.getPiece(n).character == 'm' && Board.getPiece(n).character == 'p') { totalValue += 100; } if (p != null && Board.getPiece(n).character == 'z') { totalValue -= 20; } } return totalValue; }
- 下一步能将軍，估值+9999（相當于直接選擇這個值了）
- 下一步能吃【車】，估值+500
- 下一步能吃【馬】或【炮】，估值+100
- 下一步能吃【卒】，估值-20
- 對每個狀态的估值
對每個狀态的估值包含了上面三種估值，然後用程式方估值-對手方估值得出最終結果。public int estimate(ChessBoard Board) { int[][] totalValue = new int[2][3]; for (Map.Entry<String, Piece> pieceEntry : Board.pieces.entrySet()) { Piece piece = pieceEntry.getValue(); switch (piece.character) { case 'b': if (piece.color == 'b') { totalValue[0][0] += estimate_value(0); totalValue[0][1] += estimate_position(0, piece.pos); } else { totalValue[1][0] += estimate_value(0); totalValue[1][1] += estimate_position(0, getOppositePos(piece.pos)); } break; case 's': if (piece.color == 'b') { totalValue[0][0] += estimate_value(1); totalValue[0][1] += estimate_position(1, piece.pos); } else { totalValue[1][0] += estimate_value(1); totalValue[1][1] += estimate_position(1, getOppositePos(piece.pos)); } break; case 'x': if (piece.color == 'b') { totalValue[0][0] += estimate_value(2); totalValue[0][1] += estimate_position(2, piece.pos); } else { totalValue[1][0] += estimate_value(2); totalValue[1][1] += estimate_position(2, getOppositePos(piece.pos)); } break; case 'm': if (piece.color == 'b') { totalValue[0][0] += estimate_value(3); totalValue[0][1] += estimate_position(3, piece.pos); } else { totalValue[1][0] += estimate_value(3); totalValue[1][1] += estimate_position(3, getOppositePos(piece.pos)); } break; case 'j': if (piece.color == 'b') { totalValue[0][0] += estimate_value(4); totalValue[0][1] += estimate_position(4, piece.pos); } else { totalValue[1][0] += estimate_value(4); totalValue[1][1] += estimate_position(4, getOppositePos(piece.pos)); } break; case 'p': if (piece.color == 'b') { totalValue[0][0] += estimate_value(5); totalValue[0][1] += estimate_position(5, piece.pos); } else { totalValue[1][0] += estimate_value(5); totalValue[1][1] += estimate_position(5, getOppositePos(piece.pos)); } break; case 'z': if (piece.color == 'b') { totalValue[0][0] += estimate_value(6); totalValue[0][1] += estimate_position(6, piece.pos); } else { totalValue[1][0] += estimate_value(6); totalValue[1][1] += estimate_position(6, getOppositePos(piece.pos)); } break; } totalValue[0][2] += estimate_myself(piece); totalValue[1][2] += estimate_myself(piece); } int red = totalValue[1][0] + totalValue[1][1] + totalValue[1][2]; int black = totalValue[0][0] + totalValue[0][1] + totalValue[0][2]; int result_value = black - red; return result_value; } - alpha-beta剪枝算法。
整個剪枝算法是自頂向下的，是以要判斷層數，當// alpha-beta algorithm. private int alpha_beta_search(int depth, int alpha, int beta, boolean isMax) { // Recursion end: if the depth is 0 or Gameover. if (depth == 0 || controller.hasWin(Board) != 'x') { return estimate(Board); } // Generate all the situation the current position will go. // 隻有在極大值層的時候才會生成 ArrayList<AlphaBetaNode> allNextStep = new ArrayList<AlphaBetaNode>(); for (Map.Entry<String, Piece> entry : Board.pieces.entrySet()) { Piece piece = entry.getValue(); if ((piece.color == 'b' && isMax) || (piece.color == 'r' && !isMax)) { for (int[] next : Rule.getNextMove(piece.Info, piece.pos, Board)) { AlphaBetaNode newNode = new AlphaBetaNode(piece.Info, piece.pos, next); allNextStep.add(newNode); } } } for (AlphaBetaNode n : allNextStep) { Piece Eaten_piece = Board.updatePiece(n.piece_key, n.to); if (isMax) { alpha = Math.max(alpha, alpha_beta_search(depth-1, alpha, beta, false)); } else { beta = Math.min(beta, alpha_beta_search(depth-1, alpha, beta, true)); } Board.updatePiece(n.piece_key, n.from); if (Eaten_piece != null) { Board.pieces.put(Eaten_piece.Info, Eaten_piece); Board.backPiece(Eaten_piece.Info); } // 剪枝過程 if (beta <= alpha) break; } return isMax ? alpha : beta; }depth=0
isMax
isMax
alpha
beta
- 然後封裝一個函數給外部調用。這個函數向外部傳回的是估值最好的一個走步。
對于每一個棋局，将所有的走步都變成一個節點，然後對每一個走步使用alpha-beta剪枝算法進行極小極大搜尋。注意，如果下一步有将軍的走步，直接作為最優節點傳回。public AlphaBetaNode search(ChessBoard board) { this.Board = board; ArrayList<AlphaBetaNode> allNextStep = new ArrayList<AlphaBetaNode>(); for (Map.Entry<String, Piece> entry : Board.pieces.entrySet()) { Piece piece = entry.getValue(); if (piece.color == 'b') { for (int[] next : Rule.getNextMove(piece.Info, piece.pos, Board)) { AlphaBetaNode newNode = new AlphaBetaNode(piece.Info, piece.pos, next); allNextStep.add(newNode); } } } AlphaBetaNode best = null; for (AlphaBetaNode n : allNextStep) { Piece p = Board.getPiece(n.to); if (p != null && p.character == 'b') { return n; } } long start = System.currentTimeMillis(); for (AlphaBetaNode n : allNextStep) { Piece eaten = Board.updatePiece(n.piece_key, n.to); if (eaten != null) n.value += 100; n.value = alpha_beta_search(depth, Integer.MIN_VALUE, Integer.MAX_VALUE, false); if (best == null || n.value >= best.value) { best = n; } Board.updatePiece(n.piece_key, n.from); if (eaten != null) { board.pieces.put(eaten.Info, eaten); board.backPiece(eaten.Info); } } long finish = System.currentTimeMillis(); System.out.println("Calculate Time: " + (finish-start) + "ms"); System.out.println("From: (" + best.from[0] + ", " + best.from[1] + ") to (" + best.to[0] + ", " + best.to[1] + ")"); return best; }
測試與分析
初始界面
走了第一步，紅方中炮，黑方上馬：
第二步，紅方用炮吃掉黑方的卒後，黑方的馬會吃掉炮：
若幹步後，黑方炮處于将軍狀态：
如果紅方不做出回應，黑方會直接将軍，遊戲獲勝：
測試過程中需要不斷調整棋局估算的參數，經過多次測試，目前的這個參數是比較智能的一個狀态了。
分析：從一些運作結果來看，程式方還是具有一定的智能的。因為時間效率問題，這裡隻實作了兩層的博弈樹，如果玩家水準比較不錯的話，程式方一般是比較難獲勝的。
總結
相比起極小極大搜尋法，alpha-beta剪枝算法得到的結果是完全相同的，它并沒有在搜尋解上有更加好的結果，但是，MIN、MAX要将整個圖都搜尋完畢，而alpha-beata剪枝算法隻需要搜尋其中的部分節點，是以它具有更高的效率。是以，給定相同的時間，alpha-beta能夠搜尋更深的深度，因而能夠獲得更好的走步。
這裡再給出一些日後優化的思路。一個是可以加深博弈樹的層數，兩層顯然還是比較簡單，基本不能戰勝玩家。而四層卻會需要大量的時間。一個比較好的方法是，對于那些明顯比較有優勢的走步，我們不需要看其它的走步，直接就選擇這一步。比方說，如果目前走步是能夠吃掉對方的車，那麼很大機率上這都是一個很好的走步，是以我就不需要管後面的事情了，也相當于是一個基于啟發式函數的剪枝。當然，具體的實作還要經過大量的測試才行。希望假期能有時間，繼續把這個項目完善。
參考資料
- 象棋局面評估：https://blog.csdn.net/jb80400812/article/details/4174410
- 調整評價函數：http://www.xqbase.com/computer/evalue_intro2.htm
- UI參考：https://github.com/geeeeeeeeek/IntelligentChineseChessSystem