Thuật toán NegaMax - Biến thể tối giản của MiniMax

Chào anh em, Đã lâu lắm không quay lại viết blog. Để ở màn cho đợt comeback lần này. Mình xin giới thiệu 1 chủ đề đã cũ nhưng được xào nấu lại là NegaMax – Biến thể tối giản của MiniMax.

Oke chúng ta đi vào bài luôn.

I, Tại sao cần phải ra đời NegaMax?

• Đầu tiên, nhắc lại kiến thức cũ 1 tí. MiniMax là thuật toán xác định kết quả định lượng tình trạng hiện tại của trò chơi từ đó sẽ chọn bước đi tiếp theo. (Xem bài viết về MiniMax của mình nếu chưa biết về MiniMax: https://viblo.asia/p/thuat-toan-minimax-ai-trong-game-APqzeaVVzVe)

Được mô tả bằng thuật toán như sau:

function minimax(node, depth, maximizingPlayer)
        if depth = 0 or node is a terminal node
        return the heuristic value of node 
        if maximizingPlayer
            bestValue := -∞
        for each child of node
            val := minimax(child, depth - 1, FALSE)
                bestValue := max(bestValue, val)
                return bestValue
        else
            bestValue := +∞
        for each child of node
                val := minimax(child, depth - 1, TRUE)
                bestValue := min(bestValue, val)
        return bestValue

Ta sẽ thấy qua là việc thực thi cho 2 bên min và max.

Liệu có cách nào có thể tối giản cho phần này không???? Oke, chúng ta gọi thì NegaMax trả lời. Dựa trên nguyên tắc thực tế max(a,b) = -min(a,b) giúp đơn giản cho việc thực hiện thuật toán MiniMax được dễ dàng hơn.

Đến đây thì cũng hiểu tại sao lại tên NegaMax rồi nhỉ. (= Negative Max theo ý kiến riêng mình suy ra nhé