Khi bắt đầu xây dựng trí tuệ nhân tạo (AI) cho các trò chơi đối kháng có chiến thuật như Cờ tướng, Cờ vua, hay Tic-Tac-Toe, thuật toán đầu tiên và là nền móng cho mọi engine hiện đại chính là Minimax.
Để hiểu bản chất của Minimax, chúng ta không cần lao ngay vào những thế cờ phức tạp. Hãy cùng quay ngược thời gian, bước vào một bàn tiệc luận anh hùng giữa hai nhân vật lẫy lừng thời Tam Quốc: Tào Tháo và Lưu Bị.
1. Điển Tích "Chia Báu Vật" Giữa Tào Tháo Và Lưu Bị
Giả sử Tào Tháo và Lưu Bị bắt gặp 4 chiếc hòm chứa lượng vàng khác nhau. Tào Tháo (đại diện cho AI) được quyền chọn trước một trong hai lối đi dẫn đến các cặp hòm. Tuy nhiên, Lưu Bị (đại diện cho Đối thủ) lại là người được quyền mở chiếc hòm cuối cùng trong lối đi đó để lấy vàng.
Mục tiêu của hai người hoàn toàn trái ngược nhau:
- Tào Tháo (AI / Maximizer): Luôn muốn chọn lối đi sao cho lượng vàng nhận được là lớn nhất (Max).
- Lưu Bị (Đối thủ / Minimizer): Luôn muốn chọn chiếc hòm sao cho lượng vàng Tào Tháo nhận được là nhỏ nhất (Min) (để giảm bớt sức mạnh của đối thủ).
Biết rằng Lưu Bị là người cực kỳ thông minh và luôn đưa ra quyết định tối ưu nhất, Tào Tháo phải tính toán thế nào?
2. Mô Hình Hóa Cây Quyết Định (Game Tree)
Chúng ta có thể biểu diễn các lựa chọn của Tào Tháo và Lưu Bị dưới dạng một cây quyết định gồm 3 tầng (Gốc, Lượt Lưu Bị, Lượt Tào Tháo) bằng biểu đồ trực quan dưới đây:
graph TD
A((Tào Tháo: Chọn Lối)) --> B1[Lưu Bị: Nhánh A]
A --> B2[Lưu Bị: Nhánh B]
B1 --> C1(Hòm 1: 10 Vàng)
B1 --> C2(Hòm 2: 5 Vàng)
B2 --> C3(Hòm 3: 8 Vàng)
B2 --> C4(Hòm 4: 7 Vàng)
Quy Tắc Đối Kháng (Zero-Sum): Tại Sao Lại Là Max Và Min?
Đến đây, bạn có thể thắc mắc: "Tại sao Tào Tháo lại luôn tìm Max, còn Lưu Bị lại cứ phải tìm Min?"
Đây chính là bản chất của Trò chơi có tổng bằng không (Zero-sum game) trong thực tế và lập trình đối kháng:
- Chiến thắng của người này là thất bại của người kia: Trên bàn cờ hay trên chiến trường, tài nguyên và lợi thế là hữu hạn. Nếu Tào Tháo giành được càng nhiều vàng (Điểm số càng cao $\rightarrow$ Max), thì thế lực của Lưu Bị sẽ càng bị suy yếu.
- Hành động dựa trên sự tỉnh táo của đối thủ: AI không bao giờ được phép giả định đối thủ sẽ "đi ngáo" hay nhường nhịn mình. Khi lập trình, ta phải luôn mặc định đối thủ là một kẻ cực kỳ thông minh (Perfect Play). Vì vậy, Lưu Bị sẽ luôn tìm mọi cách chọn nước đi gây bất lợi lớn nhất cho Tào Tháo (Điểm số thấp nhất $\rightarrow$ Min).
Tư duy cốt lõi của Minimax: Hãy tìm nước đi đem lại kết quả tốt nhất (Max) trong tình huống mà đối thủ luôn tìm cách ép bạn vào hoàn cảnh tồi tệ nhất (Min).
3. Cách Thuật Toán Minimax Vận Hành (Tính Từ Dưới Lên)
Minimax không đoán mò tương lai, nó đi từ kết quả cuối cùng ở các chiếc hòm và suy ngược trở lại gốc.
Bước 1: Lượt của Lưu Bị (Tầng Minimizer)
Lưu Bị sẽ đứng ở hai nhánh A và B để chọn hòm có giá trị thấp nhất cho Tào Tháo:
- Tại Nhánh A: Có hai hòm là $10$ và $5$. Lưu Bị chắc chắn sẽ chọn hòm có giá trị $5$.
- Tại Nhánh B: Có hai hòm là $8$ và $7$. Lưu Bị chắc chắn sẽ chọn hòm có giá trị $7$.
Công thức toán học tại tầng này chính là tìm giá trị nhỏ nhất:
$$V_{Nhánh} = \min(c_1, c_2)$$
Bước 2: Lượt của Tào Tháo (Tầng Maximizer)
Bây giờ, Tào Tháo nhìn vào kết quả thực tế mà mình có thể nhận được ở hai nhánh:
- Nếu đi Nhánh A, Lưu Bị sẽ ép ta chỉ nhận được $5$ vàng.
- Nếu đi Nhánh B, Lưu Bị sẽ ép ta chỉ nhận được $7$ vàng.
Là một nhà quân sự đại tài, Tào Tháo sẽ chọn giá trị lớn nhất trong hai lựa chọn đó:
$$V_{Gốc} = \max(5, 7) = 7$$
Kết luận: Tào Tháo quyết định chọn Nhánh B để mang về chắc chắn $7$ vàng, thay vì tham lam chọn Nhánh A để rồi bị Lưu Bị ép lấy hòm $5$ vàng.
4. Công Thức Toán Học Tổng Quát Của Minimax
Trong lý thuyết trò chơi, thuật toán Minimax được định nghĩa bằng công thức đệ quy tổng quát như sau:
$$f(n) = \begin{cases} \text{Evaluate}(n) & \text{nếu } n \text{ là nút lá} \\ \max_{s \in \text{Successors}(n)} f(s) & \text{nếu } n \text{ là lượt Maximizer} \\ \min_{s \in \text{Successors}(n)} f(s) & \text{nếu } n \text{ là lượt Minimizer} \end{cases}$$
Trong đó:
- $n$: Nút hiện tại trên cây quyết định.
- $\text{Evaluate}(n)$: Hàm đánh giá điểm số của trạng thái hiện tại.
- $\text{Successors}(n)$: Tập hợp tất cả các nước đi hợp lệ tiếp theo từ nút $n$.
5. Mã Giả Thuật Toán (Pseudo-code)
Để hiện thực hóa tư duy trên vào code, chúng ta sử dụng cấu trúc đệ quy. Dưới đây là đoạn mã giả mô tả thuật toán Minimax cơ bản:
public static int Minimax(Node node, int depth, bool isMaximizingPlayer)
{
// Điều kiện dừng: đạt tới độ sâu tối đa hoặc trò chơi kết thúc
if (depth == 0 || node.IsTerminal())
{
return Evaluate(node);
}
if (isMaximizingPlayer)
{
int maxEval = int.MinValue;
foreach (var child in node.GetSuccessors())
{
int eval = Minimax(child, depth - 1, false);
maxEval = Math.Max(maxEval, eval);
}
return maxEval;
}
else
{
int minEval = int.MaxValue;
foreach (var child in node.GetSuccessors())
{
int eval = Minimax(child, depth - 1, true);
minEval = Math.Min(minEval, eval);
}
return minEval;
}
}
6. Đánh Giá Thuật Toán
| Tiêu chí | Đặc điểm cấu trúc Minimax |
|---|---|
| Ưu điểm | Tối ưu theo hàm đánh giá: Đảm bảo AI luôn tìm ra nước đi tốt nhất dựa trên những gì nó biết (hàm Evaluate). Nếu đối thủ cũng chơi hoàn hảo, AI sẽ chọn được con đường an toàn nhất để không bị thua sâu. |
| Nhược điểm |
|
Trong thực tế với các trò chơi lớn như Cờ Tướng, số lượng nước đi tại một thời điểm ($b$) có thể lên tới 40. Nếu AI tính trước 10 nước ($d = 10$), số lượng trạng thái cần kiểm tra sẽ là $40^{10}$, một con số khổng lồ khiến máy tính không thể xử lý kịp thời gian thực.
Lời Kết
Minimax là một thuật toán đẹp, tư duy rõ ràng nhưng lại quá "ngây thơ" khi cố gắng duyệt qua tất cả mọi trường hợp, kể cả những nhánh chắc chắn tệ.
Để giải quyết bài toán tốc độ này, các nhà khoa học máy tính đã phát triển thêm các kỹ thuật tối ưu như Cắt nhánh Alpha-Beta, Negamax, PVS (Principal Variation Search), ... Chúng ta sẽ cùng nhau mổ xẻ các tuyệt chiêu "né tránh tính toán thừa" này ở bài viết tiếp theo nhé!
Nhận xét
Đăng nhận xét