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

3409

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:

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é, chưa search kiểm chứng vụ này).

II, Thuật toán NegaMax

Và ta thấy việc viết code được giảm đi kha khá.

Tương tự mình có thể áp dụng cắt tỉa Alpha Beta vào NegaMax.

Mình đi vào ví dụ trực quan hóa bằng hình như bên dưới

MiniMax:

NegaMax:

Đi nhanh giải thích hình 2. Ta có kết quả cuối cùng bên trái có kết quả ở các node lá là 2 và -5 => Max(2,-5) = 2

Node cha ở trên max(a,b) = -min(a,b). Tính được như sau: 2x(-1) = -2 và có node lá còn lại là 1. Tiếp tục tương tự ta có: Max(-2,1) = 1. Và tiếp tục cho đến hết kết quả cuối cùng.

Đến đây chắc các bạn có cái nhìn sơ qua về thuật toán rồi. Mình xin kết thúc tại đây.

Có thể bạn quan tâm

TopDev via Viblo