Bài giảng Trí tuệ nhân tạo - Bài 7: Trò chơi đối kháng xác định

Nội dung text: Bài giảng Trí tuệ nhân tạo - Bài 7: Trò chơi đối kháng xác định

1. TRÍ TUỆ NHÂN TẠO Bài 7: Trò chơi đối kháng xác định
2. Nội dung 1. Một số khái niệm 2. Phân loại hình trạng trong không gian trò chơi 3. Hàm Grundy 4. Đồ thị tổng 5. Bài tập Trương Xuân Nam - Khoa CNTT 2
3. Phần 1 Một số khái niệm TRƯƠNG XUÂN NAM 3
4. Trò chơi đối kháng . Có 2 bên tham gia . Quyền lợi các bên đối lập nhau (thắng-thua) . Còn gọi là zero-sum game (trò chơi có tổng bằng 0) . Cần phân biệt với trò chơi hợp tác (win-win) . Hai bên thay nhau biến đổi trạng thái trò chơi . Khái niệm turn-base: chơi theo lượt, mỗi bên đến lượt mình có quyền thay đổi trạng thái của trò chơi và (tất nhiên) sẽ cố gắng thay đổi sao cho họ được nhiều lợi thế nhất . Trong thực tế thì trò chơi nào cũng có thể mô hình hóa thành trò chơi theo lượt (vấn đề là định nghĩa “lượt” như thế nào) . Có định nghĩa kết thúc một cách rõ ràng . Có thể có kết cục hòa: ngăn chặn trò chơi kéo dài mãi Trương Xuân Nam - Khoa CNTT 4
5. Trò chơi xác định . Mọi hình trạng của trò chơi đều được xác định trạng thái thông qua tính toán . Trò chơi không xác định: . Số hình trạng quá nhiều, không thể tính toán kết cục . Hình trạng có những điểm “mờ”: thông tin không rõ ràng • Chẳng hạn như khi chơi bài, ta không thể biết chính xác các quân bài trên tay đối phương . Không có định nghĩa rõ ràng việc thắng-thua . Trò chơi đối kháng xác định: đối kháng + xác định Trương Xuân Nam - Khoa CNTT 5
6. Phần 2 Phân loại hình trạng trong không gian trò chơi TRƯƠNG XUÂN NAM 6
7. Phân loại trạng thái trò chơi . Những trạng thái thắng-thua theo định nghĩa: áp dụng luật chơi để xác định thắng thua . Những trạng thái thắng-thua do tính toán: không có trong định nghĩa, nhưng bằng tính toán và suy luận, ta có thể biết loại trạng thái là gì . Trạng thái thắng: mọi nước đi tiếp theo đều dẫn đến trạng thái thua . Trạng thái thua: tồn tại ít nhất một nước đi đến trạng thái thắng . Trạng thái hòa: Trò chơi bế tắc không thể kết thúc (theo định nghĩa) hoặc chuỗi trạng thái xuất hiện chu trình Trương Xuân Nam - Khoa CNTT 7
8. Trò chơi di chuyển quân Hậu • Quân Hậu ở vị trí (p, q) trên bàn cờ • Hai người lần lượt di chuyển quân Hậu nhưng chỉ được phép đi xuống, đi sang trái hoặc đi chéo trái-xuống • Ai không đi được nữa là thua TRƯƠNG XUÂN NAM 8
9. Tính toán loại trạng thái . Định nghĩa trạng thái của trò chơi: mỗi vị trí đứng của quân Hâu sẽ là một trạng thái, như vậy trạng thái đại diện bởi một cặp (p, q) . Quy ước trước khi tính toán: . Trạng thái thắng = 1: đi được đến đó thì sẽ thắng . Trạng thái thua = 0: đi vào đó thì có thể thua (nếu đối thủ biết chơi) . Trạng thái hòa hoặc chưa tính được = -1 . Thắng theo định nghĩa: ô (0, 0) – vì hết nước đi . Tính toán giá trị cho các trạng thái khác như thế nào? Trương Xuân Nam - Khoa CNTT 9
10. Phần 3 Hàm Grundy TRƯƠNG XUÂN NAM 10
11. Hàm Grundy . Xét hình trạng X có các nước đi tiếp theo là X1, X2, , Xn = 푖푛 − ( 푖) 푖 = 1. . 푛 . Ở đây N là tập số tự nhiên . Như vậy, hàm Grundy phát biểu bằng lời sẽ là: “số tự nhiên nhỏ nhất không trùng với các số gán cho các trạng thái con” . Ví dụ: . X đi được đến A, B, C & D . G(A) = 1, G(B) = 4, G(C) = 0, G(D) = 1 . G(X) = min {N \ {1, 4, 0, 1}} = 2 Trương Xuân Nam - Khoa CNTT 11
12. Hàm Grundy . Có sự tương đương giữa giá trị của hàm Grundy và trạng thái thắng thua của trò chơi: . G(X) = 0 Đi đến đâu cũng là ô khác 0 trạng thái thắng . G(X) > 0 Luôn tìm được đường đi đến ô 0 trạng thái thua . Vì vậy nếu tính được G(X) cũng là tính được trạng thái của trò chơi Trương Xuân Nam - Khoa CNTT 12
13. Tính hàm grundy của các hình trạng sau A B C D E F G H I J K L N P Q M O Trương Xuân Nam - Khoa CNTT 13
14. Phần 4 Đồ thị tổng TRƯƠNG XUÂN NAM 14
15. Khái niệm đồ thị tổng . Một trò chơi đối kháng theo lượt ~ đồ thị . Nếu trò chơi này có thể tách thành cách trò chơi con: . Độc lập về trạng thái . Một lượt đi tác động tới một số trò chơi con . Những trò chơi khác bỏ qua (null move) . Số trò chơi tác động đồng thời gọi là “bậc” của đồ thị cha, bậc = 1 ~ đồ thị tổng Trương Xuân Nam - Khoa CNTT 15
16. Hàm Grundy trên đồ thị tổng . Người ta chứng minh được, nếu đồ thị D là tổng của các đồ thị con D1, D2, , Dn thì: = 1 표 2 표 표 ( 푛) . Ví dụ: . D = A + B + C . G(A) = 3, G(B) = 5, G(C) = 6 . G(D) = 3 xor 5 xor 6 = 0 Trương Xuân Nam - Khoa CNTT 16
17. Phần 5 Bài tập TRƯƠNG XUÂN NAM 17
18. Bài 1: Trò chơi “Bốc sỏi” Trò chơi “Bốc sỏi” 2 người: • Có 2 đống sỏi, đống 1 có m viên, đống 2 có n viên • Lần lượt từng người đi, hoặc bốc ở 1 đống không quá 4 viên, hoặc bốc ở cả 2 đống không quá 3 viên (bốc 2 đống số sỏi như nhau) Với số sỏi ban đầu (20, 30), xác định trạng thái ban đầu là thắng hay thua đối với người đi trước. Trương Xuân Nam - Khoa CNTT 18
19. Bài 2: Trò chơi “Chuyển sỏi” Luật chơi như sau: • Một dải băng có 19 ô • Đầu trái có viên sỏi đen, đầu phải có viên sỏi trắng • Người chơi thứ nhất được dịch viên sỏi đen, người chơi thứ hai được dịch viên sỏi trắng • Được dịch viên sỏi đi không quá 3 ô và không nhảy qua đầu viên sỏi của đối phương • Ai không dịch được nữa là thua Tính Grundy cho các trạng thái. Trương Xuân Nam - Khoa CNTT 19
20. Bài 3: Cờ DAM • Sự mở rộng của trò chơi chuyển sỏi • Mỗi người chỉ được chọn 1 viên sỏi để đi một lượt • Không hạn chế số ô dịch chuyển • Ai không đi được nữa là thua Trương Xuân Nam - Khoa CNTT 20
21. Bài 4: Trò chơi “Tô màu” Một dải băng n ô vuông. Có 2 người chơi, lần lượt tô màu 2 hoặc 3 ô liên tiếp trên dải băng, điều kiện: Không được tô đè lên những ô đã có màu. Ai đến lượt mình mà không tô được nữa thì thua. Câu hỏi: • Xây dựng chiến lược đi cho người đi trước • Xây dựng chiến lược đi tối ưu cho cả 2 người chơi Tính hàm Grundy cho n = 2, 3, 5, 11, 20, 100. Trương Xuân Nam - Khoa CNTT 21
22. Bài 5: Chia socola Một phong socola kích thước M x N. Hai người thực hiện phương án chia socola như sau: • Mỗi người lần lượt chọn 1 thanh và bẻ theo đường chia ngang hoặc dọc thanh đó • Nếu sau khi thực hiện việc bẻ, có một (hoặc vài) khối socola kích thước 1 x 1 thì người thực hiện việc bẻ có thể lấy khối đó Xây dựng chiến lược chơi có lợi nhất cho người thứ nhất. Trương Xuân Nam - Khoa CNTT 22