Mô phỏng thuật toán Minimax (cây trò chơi)

Minimax Game Tree · Nhóm: Lý thuyết trò chơi

Duyệt cây trò chơi hai người luân phiên: tầng MAX chọn nước tốt nhất cho ta, tầng MIN giả định đối thủ chọn xấu nhất cho ta, lan giá trị từ lá lên gốc.

Ý tưởng

Đệ quy xuống lá; lá trả về điểm số của kết cục.

Nút MAX lấy giá trị lớn nhất trong các con, nút MIN lấy giá trị nhỏ nhất; giá trị gốc là kết cục khi hai bên chơi tối ưu.

Vì sao đúng

Giả định đối thủ luôn chơi tối ưu (chọn xấu nhất cho ta) cho ra giá trị bảo đảm (worst-case) của mỗi nước; đây chính là nghiệm cân bằng của trò chơi tổng bằng không hữu hạn.

Mã Python

def minimax(node, is_max):
    if node.is_leaf():
        return node.value
    vals = [minimax(c, not is_max) for c in node.children]
    return max(vals) if is_max else min(vals)

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