Giải Thuật Cắt Tỉa Alpha-Beta¶

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms - Alpha-Beta Pruning

1. Bản chất vấn đề¶

Bài toán: Tối ưu hoá cây trò chơi¶

Trong trò chơi 2 người (Minimax), cây trò chơi có độ sâu \(d\) và hệ số phân nhánh \(b\). Thuật toán Minimax thường duyệt \(O(b^d)\) nút.

Alpha-Beta Pruning: Cắt tỉa các nhánh không ảnh hưởng kết quả \(\Rightarrow\) giảm xuống \(O(b^{d/2})\) trong trường hợp tốt nhất.

So sánh¶

Thuật toán	Worst case	Best case
Minimax	\(O(b^d)\)	\(O(b^d)\)
Alpha-Beta	\(O(b^d)\)	\(O(b^{d/2})\)

2. Tư duy cốt lõi¶

Ý tưởng: Cắt tỉa bằng khoảng \([\alpha, \beta]\)¶

\(\alpha\): giá trị tốt nhất mà MAX player có thể đảm bảo (khởi tạo \(-\infty\)).
\(\beta\): giá trị tốt nhất mà MIN player có thể đảm bảo (khởi tạo \(+\infty\)).

Cắt tỉa: Nếu \(\alpha \ge \beta\), nhánh hiện tại không thể ảnh hưởng kết quả → bỏ qua.

Trace chi tiết¶

Cây trò chơi (MAX đi trước):

graph TD
    A["MAX\nα=-∞, β=+∞"] --> B["MIN\nα=-∞, β=+∞"]
    A --> C["MIN\nα=?, β=?"]
    B --> D["3"]
    B --> E["5"]
    B --> F["7"]
    C --> G["2"]
    C --> H["9"]
    C --> I["1"]

Chạy Alpha-Beta (theo dõi α tại MAX-A và β tại MIN-B/C từng bước):

Bước	Nút	Loại	\(\alpha\) (tốt nhất của MAX)	\(\beta\) (tốt nhất của MIN)	Giá trị nút	Cắt tỉa?
1	D	Lá	—	—	3
2	B	MIN (đang duyệt)	\(-∞\) (chưa có từ A)	\(\beta=\min(+∞,3)=3\)	tạm \(v=3\)
3	E	Lá	—	—	5	\(5 > \beta=3\), MIN bỏ qua
4	F	Lá	—	—	7	\(7 > \beta=3\), MIN bỏ qua
5	B (MIN)	chốt	—	3	\(\min(3,5,7)=3\)	xong, trả 3 lên A
6	A	MAX (đang duyệt)	\(\alpha=\max(-∞,3)=3\)	\(+∞\)	tạm \(v=3\)
7	G	Lá	—	—	2	\(2 \le \alpha=3\): C thấy \(v=2\le\alpha\) → cắt H, I
8	C (MIN)	chốt sớm	3	\(\beta=\min(+∞,2)=2\)	\(\min(2,\ldots)=2\) (không duyệt H, I)	\(\alpha\ge\beta\) (\(3\ge2\)) → cắt
9	A (MAX)	chốt	\(\alpha=\max(3,2)=3\)	—	\(\max(3,2)=3\)

Kết quả: MAX chọn giá trị 3. Nhánh \(H\) và \(I\) bị cắt vì \(G\) đã cho giá trị 2 < \(\alpha = 3\) (MIN-C chắc chắn trả về \(\le 2\), không bao giờ vượt được 3 mà MAX-A đã có).

Lỗi thường gặp (SAI / ĐÚNG)¶

Lỗi 1: Nhầm vai trò MAX/MIN (dùng max ở nút MIN)

// SAI: nút MIN lại lấy max
val = max(val, alphaBeta(child, ...));  // trong nhánh minimizing

// ĐÚNG: MIN dùng min + cập nhật beta; MAX dùng max + cập nhật alpha
val = min(val, alphaBeta(child, depth + 1, alpha, beta, true));
beta = min(beta, val);

Lỗi 2: Khởi tạo α/β sai

// SAI: alpha = 0, beta = 0 → cắt nhầm ngay khi giá trị âm/dương
int alpha = 0, beta = 0;

// ĐÚNG: alpha = -vô cực, beta = +vô cực ở nút gốc
alphaBeta(0, 0, INT_MIN, INT_MAX, true);

Lỗi 3: Quên sắp xếp thứ tự nước đi (mất hết hiệu quả cắt)

// SAI: duyệt con theo thứ tự ngẫu nhiên → worst case O(b^d)
// ĐÚNG: MAX duyệt con tốt nhất trước (giảm dần), MIN duyệt tệ nhất trước (tăng dần)
// → best case O(b^{d/2}). Với cờ vua: thử nước ăn quân / chiếu trước.
sort(tree[node].begin(), tree[node].end(), cmp);  // heuristic trước khi lặp

Lỗi 4: Điều kiện cắt > thay vì >=

// SAI: bỏ sót trường hợp alpha == beta (vẫn cắt được an toàn)
if (alpha > beta) break;

// ĐÚNG: chuẩn Alpha-Beta dùng >=
if (alpha >= beta) break;  // nhánh này không ảnh hưởng kết quả

3. Phân tích tính đúng đắn¶

Tại sao cắt tỉa đúng?¶

Nếu tại nút MIN, giá trị hiện tại \(v \le \alpha\) (giá trị tốt nhất của MAX ở nút tổ tiên), thì MAX đã có cách đạt \(\alpha\). Nút MIN sẽ không chọn giá trị \(> v\) (vì MIN muốn minimize). Do đó, MAX không bao giờ chọn nhánh này → cắt an toàn.

4. Đánh giá độ phức tạp¶

Trường hợp	Thời gian
Best case (tối ưu thứ tự)	\(O(b^{d/2})\)
Worst case	\(O(b^d)\)

Code minh họa¶

C++Python

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> tree;   // Cây trò chơi: danh sách kề cha → con
vector<int> values;         // Giá trị của các nút lá

// Hàm Alpha-Beta: duyệt cây trò chơi, trả về giá trị tối ưu
// node: nút hiện tại, depth: độ sâu, alpha/beta: cửa sổ cắt tỉa
// maximizing: true nếu lượt MAX, false nếu lượt MIN
int alphaBeta(int node, int depth, int alpha, int beta, bool maximizing) {
    if (tree[node].empty()) {               // Nút lá: trả về giá trị cố định
        return values[node];
    }

    if (maximizing) {                       // Lượt của MAX player
        int val = INT_MIN;                  // Khởi tạo giá trị thấp nhất có thể
        for (int child : tree[node]) {      // Duyệt tất cả con
            val = max(val, alphaBeta(child, depth + 1, alpha, beta, false));
            alpha = max(alpha, val);         // Cập nhật alpha = giá trị tốt nhất của MAX
            if (alpha >= beta) break;        // Cắt tỉa Beta: nhánh này vô ích cho MAX
        }
        return val;
    } else {                                // Lượt của MIN player
        int val = INT_MAX;                  // Khởi tạo giá trị cao nhất có thể
        for (int child : tree[node]) {      // Duyệt tất cả con
            val = min(val, alphaBeta(child, depth + 1, alpha, beta, true));
            beta = min(beta, val);           // Cập nhật beta = giá trị tốt nhất của MIN
            if (alpha >= beta) break;        // Cắt tỉa Alpha: nhánh này vô ích cho MIN
        }
        return val;
    }
}

int main() {
    // Ví dụ đơn giản: cây 3 nút
    // Nút 0: MAX, con 1, 2
    // Nút 1: MIN, con 3, 4, 5 (lá: 3, 5, 7)
    // Nút 2: MIN, con 6, 7, 8 (lá: 2, 9, 1)

    tree.resize(9);
    values.resize(9, 0);

    tree[0] = {1, 2};       // MAX có 2 lựa chọn
    tree[1] = {3, 4, 5};    // MIN có 3 lựa chọn nhánh trái
    tree[2] = {6, 7, 8};    // MIN có 3 lựa chọn nhánh phải
    // Giá trị các nút lá
    values[3] = 3; values[4] = 5; values[5] = 7;
    values[6] = 2; values[7] = 9; values[8] = 1;

    cout << alphaBeta(0, 0, INT_MIN, INT_MAX, true) << "\n"; // Kết quả = 3
    return 0;
}

import sys
sys.setrecursionlimit(10000)   # Tăng giới hạn đệ quy cho cây lớn

# Hàm Alpha-Beta: duyệt cây trò chơi, trả về giá trị tối ưu
# node: nút hiện tại, depth: độ sâu, alpha/beta: cửa sổ cắt tỉa
# maximizing: True nếu MAX, False nếu MIN
def alpha_beta(node, depth, alpha, beta, maximizing, tree, values):
    if not tree[node]:          # Nút lá: trả về giá trị
        return values[node]

    if maximizing:              # Lượt MAX
        val = float('-inf')     # Khởi tạo giá trị thấp nhất
        for child in tree[node]:
            # Đệ quy xuống nút MIN con
            val = max(val, alpha_beta(child, depth + 1, alpha, beta, False, tree, values))
            alpha = max(alpha, val)   # Cập nhật alpha
            if alpha >= beta:         # Cắt tỉa Beta
                break
        return val
    else:                       # Lượt MIN
        val = float('inf')      # Khởi tạo giá trị cao nhất
        for child in tree[node]:
            # Đệ quy xuống nút MAX con
            val = min(val, alpha_beta(child, depth + 1, alpha, beta, True, tree, values))
            beta = min(beta, val)     # Cập nhật beta
            if alpha >= beta:         # Cắt tỉa Alpha
                break
        return val

# Ví dụ cây trò chơi 9 nút (3 tầng)
tree = {
    0: [1, 2],          # MAX: 2 lựa chọn → MIN, MIN
    1: [3, 4, 5],       # MIN trái: 3 lựa chọn
    2: [6, 7, 8],       # MIN phải: 3 lựa chọn
    3: [], 4: [], 5: [], 6: [], 7: [], 8: []
}
values = {3: 3, 4: 5, 5: 7, 6: 2, 7: 9, 8: 1}

print(alpha_beta(0, 0, float('-inf'), float('inf'), True, tree, values))

Ví dụ nâng cao: Cây 4 tầng với thứ tự tối ưu¶

Xét cây trò chơi có độ sâu 4, hệ số phân nhánh 3 (81 nút lá). Nếu sắp xếp con theo thứ tự giảm dần (tốt nhất cho MAX trước), Alpha-Beta chỉ duyệt ~15 nút lá thay vì 81.

graph TD
    A["MAX"] --> B1["MIN\n(LÁ: 9)"]
    A --> B2["MIN\n(LÁ: 5)"]
    A --> B3["MIN\n(LÁ: 1)"]
    B1 --> C1["3"]
    B1 --> C2["7"]
    B1 --> C3["9"]
    B2 --> C4["1"]
    B2 --> C5["4"]
    B2 --> C6["5"]
    B3 --> C7["0"]
    B3 --> C8["-2"]
    B3 --> C9["1"]

Khi quét từ trái sang phải: nút \(B1\) trả về 9 → \(\alpha = 9\). Nút \(B2\): lá đầu là 1 < 9 → cắt toàn bộ nhánh \(B2\). Tương tự \(B3\): lá đầu là 0 < 9 → cắt. Chỉ cần đánh giá 1/3 số nút.

Bài tập luyện tập¶

Mã bài	Tên bài tập	Độ khó	Kiểu bài tập (Bản chất)	Bài học lý thuyết
`ab-win-game`	Trò chơi thắng	⭐	Alpha-Beta - Trò chơi thắng cơ bản	Alpha-Beta Pruning
`ab-minimax-basic`	Cây game	⭐⭐	Alpha-Beta - Minimax cơ bản	Alpha-Beta Pruning
`ab-coin-pick`	Nhặt xu	⭐⭐	Alpha-Beta - Nhặt xu 2 đầu	Alpha-Beta Pruning
`ab-stone-div`	Chia đá	⭐⭐⭐	Alpha-Beta - Chia đá	Alpha-Beta Pruning
`ab-subtract`	Trừ số	⭐⭐⭐	Alpha-Beta - Trừ số	Alpha-Beta Pruning
`ab-prime-game`	Số nguyên tố	⭐⭐⭐	Alpha-Beta - Xóa ước nguyên tố	Alpha-Beta Pruning
`ab-tree-game`	Game trên cây	⭐⭐⭐⭐	Alpha-Beta - Game trên cây	Alpha-Beta Pruning
`ab-coloring`	Tô màu	⭐⭐⭐⭐	Alpha-Beta - Tô màu đồ thị	Alpha-Beta Pruning
`ab-divisor`	Ước số	⭐⭐⭐⭐	Alpha-Beta - Chia ước số	Alpha-Beta Pruning