Mô phỏng thuật toán Cắt tỉa Alpha-Beta

Alpha-Beta Pruning · Nhóm: Lý thuyết trò chơi

Minimax có cắt tỉa: mang theo alpha (cận dưới của MAX) và beta (cận trên của MIN) khi đi xuống, bỏ qua nhánh không thể cải thiện kết quả đã có.

Ý tưởng

Đi xuống như Minimax nhưng cập nhật alpha ở nút MAX, beta ở nút MIN.

Tại nút MIN nếu giá trị tụt xuống <= alpha thì các con còn lại vô ích · cắt tỉa (beta cutoff); tương tự alpha cutoff ở nút MAX khi v >= beta.

Vì sao đúng

Nếu MAX đã bảo đảm được ít nhất alpha, một nhánh MIN đã tụt xuống dưới hoặc bằng alpha không thể được MAX chọn nên phần còn lại của nhánh đó là thừa; cắt tỉa không đổi kết quả, chỉ bỏ nhánh chắc chắn vô dụng.

Mã Python

def alphabeta(node, alpha, beta, is_max):
    if node.is_leaf():
        return node.value
    if is_max:
        v = -INF
        for c in node.children:
            v = max(v, alphabeta(c, alpha, beta, False))
            alpha = max(alpha, v)
            if v >= beta: break   # alpha cutoff
        return v
    else:
        v = +INF
        for c in node.children:
            v = min(v, alphabeta(c, alpha, beta, True))
            beta = min(beta, v)
            if v <= alpha: break  # beta cutoff · prune rest
        return v

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.