Định nghĩa và Ứng dụng Thuật toán Minimax trong Trò Chơi Đối Kháng | Môn Trí tuệ nhân tạo - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58778885
Định nghĩa thuật toán Minimax
Minimax là một thuật toán tìm kiếm cây trò chơi được sử dụng trong các trò chơi hai người có tính chất
đối kháng, chẳng hạn như Cờ Caro, Cờ Vua, hoặc Cờ Tướng. Mục tiêu của thuật toán là tìm ra nước đi tối
ưu cho một người chơi (gọi là MAX) trong khi giả định rằng đối thủ (gọi là MIN) cũng chơi tối ưu.
Cây trò chơi là một cấu trúc dữ liệu dạng cây (tree) được sử dụng để biểu diễn tất cả các khả năng có thể
xảy ra trong một trò chơi hai người (hoặc nhiều người) có tính chất đối kháng. Nó giúp phân tích các nước
đi, trạng thái trò chơi, và kết quả cuối cùng. Nguyên lý cơ bản •
MAX: Người chơi chính (thường là AI), cố gắng tối đa hóa điểm số (lợi ích của mình). •
MIN: Đối thủ (thường là người chơi), cố gắng tối thiểu hóa điểm số của MAX (tức là làm tệ nhất cho MAX). •
Zero-sum: Lợi ích của MAX là thiệt hại của MIN và ngược lại. Cách hoạt động
1. Xây dựng cây trò chơi:
o Mỗi nút trong cây đại diện cho một trạng thái của trò chơi (ví dụ: bàn cờ sau một nước đi).
Trong cờ caro: Một nút là một bàn cờ tại một thời điểm cụ thể, thể hiện vị trí của các quân
X và O. Mỗi nút lưu thông tin về bàn cờ tại thời điểm đó, bao gồm: Vị trí các quân X và O. Lượt
chơi hiện tại (X hoặc O).
o Mỗi nhánh từ nút là một nước đi có thể thực hiện, Mỗi ô trống tương ứng với một nhánh,
dẫn đến một trạng thái mới (nút con).
o Cây được xây đến một độ sâu nhất định (hoặc đến khi trò chơi kết thúc).
2. Đánh giá trạng thái lá:
o Khi đến độ sâu tối đa hoặc trò chơi kết thúc (thắng/thua/hòa), dùng một hàm đánh giá
(heuristic function) để gán điểm số cho trạng thái đó..hàm đánh giá giống như một
“trọng tài” chấm điểm bàn cờ, cho biết trạng thái nào có lợi hơn khi không thể tính hết mọi nước đi
3. Duyệt ngược (Backpropagation):
o Từ các nút lá, truyền giá trị ngược lên qua các lớp: lOMoAR cPSD| 58778885
Ở nút MAX: Chọn giá trị lớn nhất trong các nhánh con.
Ở nút MIN: Chọn giá trị nhỏ nhất trong các nhánh con.
o Quá trình này lặp lại qua các lớp cho đến nút gốc (trạng thái hiện tại).
4. Chọn nước đi tối ưu:
o Từ nút gốc, MAX chọn nước đi dẫn đến nhánh có giá trị cao nhất (đã được tính từ quá trình duyệt ngược).
Ví dụ minh họa đơn giản
Giả sử một trò chơi nhỏ với cây như sau: •
Trạng thái gốc (nút A): MAX chọn nước đi. •
Nút A có 2 nhánh: B (MIN) và C (MIN). •
Nút B có 2 lá: 3 và 7. Nút C có 2 lá: 1 và 9. text Thu gọnBọc lạiSao chép A (MAX) / \ B C (MIN) / \ / \ 3 7 1 9 •
Ở nút B (MIN): Chọn min(3, 7) = 3. •
Ở nút C (MIN): Chọn min(1, 9) = 1. •
Ở nút A (MAX): Chọn max(3, 1) = 3.
Kết quả: MAX chọn nhánh B vì giá trị 3 là tối ưu (trong khi giả định MIN chơi tốt nhất). • Ưu điểm: •
Đảm bảo tìm được nước đi tốt nhất nếu cây trò chơi được khám phá hết. •
Phù hợp với các trò chơi có không gian trạng thái nhỏ. • Nhược điểm: •
Tốn nhiều thời gian và bộ nhớ khi không gian trạng thái lớn (như cờ vua). •
Cần cải tiến (như cắt tỉa Alpha-Beta) để tăng hiệu quả.
Áp dụng vào Cờ Caro lOMoAR cPSD| 58778885
Trong bối cảnh code của bạn:
MAX: AI (đặt quân 1). •
MIN: Người chơi (đặt quân 2). •
Trạng thái: Ma trận bàn cờ 25x25. •
Hành động: Đặt quân tại ô trống trong possible_paths. •
Hàm đánh giá: Dùng score cho AI và score_human cho người chơi.
Các bước chi tiết 1. Xây dựng cây:
o Từ trạng thái hiện tại, liệt kê tất cả nước đi có thể của AI (possible_paths). o
Với mỗi nước đi của AI, liệt kê tất cả nước đi có thể của người chơi.
o Tiếp tục luân phiên đến độ sâu nhất định (ví dụ: 4 lớp). 2. Đánh giá lá:
o Nếu đến độ sâu tối đa hoặc có người thắng (dùng check_win): AI thắng: +1,000,000.
Người chơi thắng: -1,000,000.
Không thắng/thua: Dùng score hoặc score_human để tính điểm. 3. Duyệt ngược:
o Ở lớp người chơi (MIN): Chọn nước đi có điểm thấp nhất (tệ nhất cho AI). o
Ở lớp AI (MAX): Chọn nước đi có điểm cao nhất. o Quay lại gốc để xác định
nước đi tốt nhất cho AI. 4. Kết quả:
o AI chọn nước đi từ gốc dẫn đến giá trị tối ưu. Minimax cổ điển Cấu trúc:
o Xây dựng cây trò chơi với các nút đại diện cho trạng thái bàn cờ. o MAX
(AI): Chọn giá trị lớn nhất từ các nhánh con.
o MIN (người chơi): Chọn giá trị nhỏ nhất từ các nhánh con. o Duyệt ngược
từ lá lên gốc để tính giá trị tối ưu cho mỗi nút. Quy trình: lOMoAR cPSD| 58778885
1. Mô phỏng tất cả các nước đi có thể đến độ sâu nhất định.
2. Tính điểm cho các trạng thái lá bằng hàm đánh giá.
3. Truyền giá trị ngược lên: MAX chọn lớn nhất, MIN chọn nhỏ nhất.
Đầu ra: Giá trị tối ưu và nước đi tương ứng cho người chơi MAX.
2. Phân tích get_child
Hàm get_child là nơi AI chọn nước đi tối ưu, và nó có một số điểm tương đồng với Minimax.
2.1. Cấu trúc cây trò chơi •
Minimax cổ điển: Xây dựng cây đầy đủ với tất cả các nước đi có thể trong không gian tìm kiếm,
đến độ sâu nhất định. • get_child:
o Bắt đầu với top7_potentialPaths (5-7 nước đi tốt nhất dựa trên score).
o Mô phỏng cây đến độ sâu 5 lớp:
Lớp lẻ (layer%2!=0): Nước đi của người chơi (2), dùng score_human.
Lớp chẵn (layer%2==0): Nước đi của AI (1), dùng score.
o Ở mỗi lớp, chỉ giữ 5 nước đi tốt nhất (top3_potentialPaths). • Biến đổi:
o Không xây dựng cây đầy đủ mà giới hạn số nhánh (5 nhánh mỗi lớp), giống một dạng cắt
tỉa thủ công. Đây là sự khác biệt lớn so với Minimax cổ điển, vốn xem xét tất cả nhánh nếu
không có Alpha-Beta Pruning.
o Việc giới hạn số nhánh (ví dụ: 5 nhánh mỗi lớp) thay vì xây dựng cây đầy đủ như trong
Minimax cổ điển có tác dụng chính là giảm độ phức tạp tính toán và tăng tốc độ xử lý,
đặc biệt trong các bài toán có không gian trạng thái lớn, chẳng hạn như các trò chơi phức
tạp (cờ vua, cờ tướng, hoặc các trò chơi chiến lược khác). 2.2. Hàm đánh giá •
Minimax cổ điển: Sử dụng một hàm đánh giá duy nhất để chấm điểm trạng thái lá, sau đó
truyền giá trị lên qua MAX/MIN. • get_child: o Dùng hai hàm đánh giá: lOMoAR cPSD| 58778885
score cho AI (tấn công AI, phòng thủ người chơi).
score_human cho người chơi (tấn công người chơi, phòng thủ AI).
o Điểm được tính ở mỗi lớp, nhưng chỉ lưu điểm của lớp chẵn (AI) vào value_potential để
chọn nước đi cuối cùng. Biến đổi:
o Việc dùng hai hàm đánh giá riêng biệt là một cách tiếp cận hợp lý, nhưng không truyền giá
trị ngược lên qua MAX/MIN mà chỉ chọn điểm cao nhất ở lớp chẵn. Đây là sự đơn giản hóa lớn.
o  Sử dụng hai hàm đánh giá riêng biệt (score cho AI và score_human cho người chơi)
giúp thuật toán phân định rõ ràng giữa chiến lược tấn công và phòng thủ của hai bên. Điều này đảm bảo rằng:
o AI tập trung tối ưu hóa lợi thế của mình (tấn công AI, đồng thời phòng thủ trước người chơi).
o Đồng thời, nó đánh giá được khả năng của người chơi (tấn công AI, phòng thủ cho chính họ).
o  Tác dụng: Tạo ra một cách tiếp cận cân bằng, tránh việc chỉ ưu tiên một phía (AI) mà
bỏ qua phản ứng của đối thủ.
2.3. Tối đa hóa và tối thiểu hóa Minimax cổ điển:
o MAX: Chọn giá trị lớn nhất ở các nút của AI.
o MIN: Chọn giá trị nhỏ nhất ở các nút của người chơi.
o Quy trình này lặp lại qua các lớp để đảm bảo AI chọn nước đi tốt nhất trong khi giả định
người chơi phản ứng tối ưu. • get_child:
o Chỉ tối đa hóa cho AI:
Tính điểm cho tất cả nước đi ở mỗi lớp, lấy 5 nước đi cao nhất.
Cuối cùng chọn nước đi gốc có best_value cao nhất sau khi giảm dần bằng 0.8**layer.
o Không có tối thiểu hóa rõ ràng:
Nước đi của người chơi được mô phỏng (lớp lẻ), nhưng không chọn giá trị nhỏ
nhất để phản ánh chiến lược tối ưu của đối thủ. lOMoAR cPSD| 58778885 • Biến đổi:
o Thiếu bước MIN là điểm khác biệt cốt lõi. get_child chỉ tập trung vào tối đa hóa lợi ích của
AI mà không thực sự mô phỏng người chơi chọn nước đi tệ nhất cho AI (như Minimax yêu cầu).
2.4. Giảm giá trị theo độ sâu •
Minimax cổ điển: Không có khái niệm giảm giá trị theo độ sâu. Điểm số ở lá được giữ nguyên và truyền ngược lên. • get_child:
o Điểm số được nhân với 0.8**layer để ưu tiên các nước đi gần hơn (ít lớp hơn). • Biến đổi:
o Đây là một heuristic bổ sung, không có trong Minimax cổ điển. Nó làm thay đổi cách đánh
giá, khiến AI ưu tiên chiến thắng sớm hơn là tối ưu hóa toàn bộ cây. 2.5. Kết quả •
Minimax cổ điển: Trả về nước đi tối ưu cho MAX sau khi cân nhắc cả MAX và MIN. • get_child:
o Trả về chỉ số của nước đi tốt nhất trong top7_potentialPaths dựa trên best_value. • Biến đổi:
o Không duyệt ngược từ lá lên gốc mà chỉ chọn trực tiếp dựa trên điểm ở lớp chẵn, bỏ qua
việc tổng hợp giá trị qua các lớp. 3. Kết luận
Có biến đổi: Hàm get_child có thể được xem là một biến thể đơn giản hóa của Minimax, nhưng nó không
phải Minimax đầy đủ vì:
1. Thiếu MIN: Không tối thiểu hóa cho người chơi, chỉ tối đa hóa cho AI.
2. Không duyệt ngược: Không truyền giá trị từ lá lên gốc qua MAX/MIN.
3. Cắt tỉa thủ công: Giới hạn 5 nhánh mỗi lớp thay vì xem xét toàn bộ cây hoặc dùng AlphaBeta Pruning.
4. Heuristic bổ sung: Hệ số 0.8**layer là một thay đổi không có trong Minimax cổ điển.
Giống gì với Minimax: lOMoAR cPSD| 58778885
o Xây dựng cây trò chơi với các lượt luân phiên.
o Dùng hàm đánh giá để chấm điểm. o Chọn
nước đi tối ưu cho AI (giống MAX).
• Có, nếu gọi get_child là một dạng Minimax, thì nó đã được biến đổi mạnh mẽ:
• Loại bỏ tối thiểu hóa (MIN).
• Thay duyệt ngược bằng chọn trực tiếp điểm cao nhất.
Thêm heuristic giảm giá trị theo độ sâu.