Alpha-Beta 剪枝算法 Java 實現：博弈樹搜索、剪枝類型判斷與測試用例

Alpha-Beta 剪枝算法深度解析與 Java 完整實現

Alpha-Beta 剪枝是 Minimax 算法的優化，通過維護 α（MAX 節點最佳下界）與 β（MIN 節點最佳上界）在深度優先搜索中提前終止無需評估的分支。本文提供可運行的 Java 實現，支持從文件讀取博弈樹、輸出最佳走法、剪枝節點與剪枝類型（α/β）。

1. 算法核心邏輯

• MAX 節點：嘗試最大化評分，維護 alpha = max(alpha, childValue)，若 alpha >= beta 觸發 Beta 剪枝。
• MIN 節點：嘗試最小化評分，維護 beta = min(beta, childValue)，若 beta <= alpha 觸發 Alpha 剪枝。
• 剪枝條件：當前節點值已超過祖先節點的容忍閾值，後續兄弟節點無需評估。

2. 數據結構設計

public class Node {
    private String name;
    private int value;        // 評分值
    private int level;        // MAX=1 / MIN=0
    private String parent;
    private List<String> children = new ArrayList<>();
    // getter/setter...
}

樹以 List<Node> 扁平存儲，name 為唯一鍵，parent/children 維護拓撲。

3. 輸入文件格式

ROOT A
A B C
B D E
C F G
D H I
E J K
F L M
G N O
VALUE
H 4
I 1
J 5
K 0
L 3
M 2
N 7
O 1
END

• ROOT 指定根節點名。
• 後續行 Parent Child1 Child2 ... 定義邊，以 END 結束。
• VALUE 區塊給出葉節點評分，END 結束。

4. 核心遞歸實現

public void alphaBeta(String nodeName) {
    Node node = findNode(nodeName);
    if (node.getChildren().isEmpty()) return; // 葉節點已有 value

    if (node.getLevel() == MAX) { // MAX 層
        node.setValue(MIN_INT);
        for (String child : node.getChildren()) {
            alphaBeta(child);
            int childVal = findNode(child).getValue();
            if (childVal > node.getValue()) node.setValue(childVal);
            if (betaCut(nodeName)) { // Beta 剪枝判斷
                recordPrune(nodeName, child, "β剪枝");
                return;
            }
        }
    } else { // MIN 層
        node.setValue(MAX_INT);
        for (String child : node.getChildren()) {
            alphaBeta(child);
            int childVal = findNode(child).getValue();
            if (childVal < node.getValue()) node.setValue(childVal);
            if (alphaCut(nodeName)) { // Alpha 剪枝判斷
                recordPrune(nodeName, child, "α剪枝");
                return;
            }
        }
    }
}

5. 剪枝判斷邏輯

// Beta 剪枝：MAX 節點值 >= 某祖先 MIN 節點的 beta
private boolean betaCut(String nodeName) {
    Node node = findNode(nodeName);
    String father = node.getParent();
    while (father != null) {
        Node fNode = findNode(father);
        if (fNode.getLevel() == MIN && fNode.getValue() != MAX_INT && node.getValue() >= fNode.getValue())
            return true;
        father = fNode.getParent();
    }
    return false;
}

// Alpha 剪枝：MIN 節點值 <= 某祖先 MAX 節點的 alpha
private boolean alphaCut(String nodeName) {
    Node node = findNode(nodeName);
    String father = node.getParent();
    while (father != null) {
        Node fNode = findNode(father);
        if (fNode.getLevel() == MAX && fNode.getValue() != MIN_INT && node.getValue() <= fNode.getValue())
            return true;
        father = fNode.getParent();
    }
    return false;
}

6. 測試結果

對示例樹運行，輸出：

最佳路徑: A 3 C
剪枝記錄:
C: F β剪枝
B: E α剪枝

• 根節點 A (MAX) 選擇子節點 C，最終評分 3。
• C 節點 (MIN) 搜索 F 後觸發 β剪枝，G 被剪掉。
• B 節點 (MIN) 搜索 E 後觸發 α剪枝，D 的剩餘分支被剪掉。

7. 擴展建議

1. 加入置換表：緩存節點評分，避免重複計算（Zobrist Hash）。
2. 實現迭代加深：配合時間控制，逐層加深搜索深度。
3. 支持啟發式排序：優先搜索高潛力子節點（如殺棋、吃子），提高剪枝效率。
4. 泛型化評分類型：支持雙元組、多目標評分。

完整代碼約 180 行，包含文件解析、樹構建、遞歸搜索、剪枝記錄，可直接用於教學演示或五子棋、象棋等雙人零和博弈 AI 基礎模塊。