Thuật toán NegaMax – Biến thể tối giản của MiniMax
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- ...
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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é, chưa search kiểm chứng vụ này).
II, Thuật toán NegaMax
|
1 2 3 4 5 6 7 8 9 10 |
function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the heuristic value of node bestValue := -∞ foreach child of node val := -negamax(child, other_player) bestValue := max( bestValue, val ) return bestValue |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function negamax(node, depth, α, β, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node childNodes := generateMoves(node) childNodes := orderMoves(childNodes) value := −∞ foreach child in childNodes do value := max(value, −negamax(child, depth − 1, −β, −α, −color)) α := max(α, value) if α ≥ β then break (* cut-off *) return value |
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
