Cây quyết định là cách vẽ mọi lựa chọn của hai bên thành các nhánh nối tiếp, còn minimax là quy tắc chọn nhánh trên cây ấy: ở lượt mình thì chọn nhánh có lợi nhất, nhưng phải giả định ở lượt đối phương, họ chọn nhánh hại mình nhất. Nói gọn: chọn nước mà trường hợp xấu nhất của nó vẫn tốt hơn trường hợp xấu nhất của các nước khác. Đây là ý tưởng nền của mọi chương trình máy tính chơi cờ, và cũng là cách nghĩ hữu ích cho người bày sa bàn.
Cây quyết định trông như thế nào
Hãy vẽ một chấm ở trên cùng: đó là thế hiện tại. Từ chấm ấy, kẻ một đường xuống cho mỗi nước mình có thể đi. Ở cuối mỗi đường là một thế mới. Từ mỗi thế mới, lại kẻ các đường cho mỗi nước đối phương có thể đáp. Cứ thế, hình vẽ toả xuống như một cái cây lộn ngược: gốc ở trên, cành toả xuống dưới.
| Thành phần | Nghĩa |
|---|---|
| Gốc | Thế hiện tại, nơi mình đang phải quyết định |
| Nhánh | Một nước đi có thể |
| Nút | Một thế cờ sau một chuỗi nước đi |
| Tầng | Mọi nút cách gốc cùng một số nửa nước; các tầng xen kẽ lượt mình và lượt đối phương |
| Lá | Nút ở cuối, nơi ngừng tính và cho điểm thế cờ |
Ở mỗi lá, cần một con số cho biết thế đó tốt hay xấu cho mình. Nếu đã tính tới cuối ván thì dễ: thắng, hoà, thua. Nếu chưa tới cuối, phải ước lượng: hơn bao nhiêu quân, giữ bao nhiêu điểm then chốt, tiếp tế còn thông không. Hàm ước lượng ấy được gọi là hàm đánh giá.
Minimax qua một ví dụ nhỏ
Giả sử mình có hai lựa chọn, A và B. Với mỗi lựa chọn, đối phương có hai cách đáp. Sau đó mình chấm điểm thế cờ (số dương là có lợi cho mình, số âm là có hại):
- Đi A, đối phương đáp cách 1: +3. Đáp cách 2: −2.
- Đi B, đối phương đáp cách 1: +1. Đáp cách 2: +2.
Người mới nhìn thấy số +3 lớn nhất và muốn đi A. Nhưng +3 chỉ xảy ra nếu đối phương đáp dở. Đối phương tỉnh táo sẽ chọn cách 2, và A thành −2. Còn với B, đối phương đáp kiểu gì cũng chỉ làm mình còn +1.
Minimax làm phép tính từ dưới lên:
- Ở tầng của đối phương, lấy số nhỏ nhất (họ chọn cái hại mình nhất): A thành −2, B thành +1.
- Ở tầng của mình, lấy số lớn nhất: giữa −2 và +1, chọn +1. Vậy đi B.
Tên "minimax" đến từ chính hai bước này: tối thiểu hoá ở lượt đối phương, tối đa hoá ở lượt mình. Với cây sâu hơn, cứ lặp lại xen kẽ hai bước từ lá ngược lên gốc.
Cắt tỉa alpha–beta: không cần tính hết cây
Cây toả nhánh rất nhanh, nên người ta tìm cách bỏ bớt nhánh mà không làm sai kết quả. Cách nổi tiếng nhất là cắt tỉa alpha–beta, được nhiều người tìm ra độc lập vào giữa thập niên 1950.
Ý tưởng dễ hiểu qua một ví dụ khác. Mình tính A trước: đối phương có hai cách đáp, cho +3 và +5. Họ sẽ chọn +3, vậy A đáng +3. Sang B: cách đáp đầu tiên của đối phương cho −1. Tới đây đã đủ. Vì dù cách đáp thứ hai của B ra bao nhiêu, đối phương vẫn có thể chọn −1, nên B tối đa chỉ đáng −1, kém hơn A. Không cần tính tiếp các cách đáp còn lại của B.
Người cầm quân giỏi làm điều này theo bản năng: "nước này có một cách đáp làm mình thiệt rồi, không cần xem thêm." Cắt tỉa giỏi giúp tính sâu gấp đôi với cùng một lượng công sức, đặc biệt khi xét các nước tốt trước.
Đôi dòng lịch sử
- Năm 1913, nhà toán học Ernst Zermelo viết một bài báo về cờ vua mà về sau thường được coi là gốc của kết luận (dù cách ông phát biểu khác với cách hiểu phổ biến ngày nay): một trong ba điều phải đúng: bên trắng có cách thắng chắc, bên đen có cách thắng chắc, hoặc cả hai giữ được hoà — dù không ai biết là điều nào.
- Năm 1928, John von Neumann công bố định lý minimax cho các cuộc đối đầu hai bên mà được của bên này là mất của bên kia.
- Năm 1950, Claude Shannon viết bài báo nổi tiếng về cách lập trình máy tính chơi cờ, đề xuất hai hướng: tính mọi nhánh tới một độ sâu cố định, hoặc chỉ tính chọn lọc những nhánh đáng xét như người.
Khi có xúc xắc: thêm nút may rủi
Minimax gốc dành cho thế đối đầu không có may rủi. Trên sa bàn có gieo xúc xắc, cây cần thêm một loại nút thứ ba: nút may rủi. Ở nút này không ai chọn; giá trị của nó là trung bình các kết quả, có trọng số theo xác suất.
Ví dụ: mình tấn công, nếu xúc xắc ra 5 hoặc 6 (xác suất 1/3) thì thế cờ đáng +6; nếu ra 1 tới 4 (xác suất 2/3) thì thế đáng −1. Giá trị kỳ vọng của đòn tấn công là 1/3 × 6 + 2/3 × (−1) = 2 − 0,67 ≈ +1,33. So với một nước an toàn đáng +1, tấn công nhỉnh hơn một chút về trung bình, nhưng có tới hai phần ba khả năng mình bị thiệt. Chọn gì còn tuỳ mình đang cần an toàn hay cần cơ hội.
Giới hạn của minimax với người
- Nó giả định đối phương luôn đáp tốt nhất. Với người thật, đôi khi một nước "không tối ưu" lại có lợi vì đặt đối phương vào thế khó nhìn ra cách đáp đúng.
- Hiệu ứng chân trời: tính tới độ sâu cố định thì không thấy tai hoạ ở ngay sau tầng cuối. Cây có thể "đẩy" một nguy cơ ra ngoài tầm nhìn và tưởng đã tránh được.
- Hàm đánh giá quyết định tất cả: cây sâu tới đâu mà chấm điểm lá sai thì vẫn chọn sai.
- Khi không thấy hết bàn, mình không biết mình đang ở nút nào của cây, và minimax thuần không còn dùng trực tiếp được.
Góc nhìn hôm nay
Không cần vẽ cây trên giấy, ý tưởng minimax vẫn có ích trong những quyết định có người khác phản ứng lại: "nếu mình làm thế này, phản ứng tệ nhất có thể là gì, và mình có chịu được không?" Đây là cách nghĩ thận trọng, hợp với những việc không đảo ngược được. Còn với những việc nhỏ, có thể làm lại, cách nghĩ theo giá trị trung bình như nút may rủi thường hợp lý hơn. Biết lúc nào dùng cách nào là phần khó nhất.
Muốn tìm hiểu thêm:
- Bài báo của Claude Shannon năm 1950 về lập trình máy tính chơi cờ, đọc được bản tiếng Anh, khá dễ hiểu với người không chuyên.
- Các giáo trình nhập môn trí tuệ nhân tạo đều có chương về tìm kiếm đối kháng, minimax và alpha–beta, kèm hình vẽ cây.
- Tự thử: vẽ cây hai tầng cho một tình huống trên sa bàn của mình, chấm điểm lá bằng cảm giác, rồi làm phép minimax. So xem kết quả có giống quyết định theo trực giác không.
Câu hỏi thường gặp
Minimax là gì?
Minimax là quy tắc chọn nước đi trên cây quyết định: ở lượt mình thì chọn nhánh có điểm cao nhất, ở lượt đối phương thì giả định họ chọn nhánh có điểm thấp nhất cho mình. Kết quả là chọn được nước mà trường hợp xấu nhất vẫn tốt hơn các nước khác.
Cây quyết định trong cờ là gì?
Là hình vẽ toả nhánh từ thế hiện tại: mỗi nhánh là một nước đi, mỗi nút là một thế cờ mới, các tầng xen kẽ lượt hai bên. Ở cuối mỗi nhánh, người ta chấm điểm thế cờ để so sánh.
Cắt tỉa alpha–beta là gì?
Là cách bỏ qua những nhánh chắc chắn không ảnh hưởng tới lựa chọn cuối cùng. Khi đã thấy một nước có cách đáp làm mình thiệt hơn một nước đã tính, thì không cần xét thêm các cách đáp khác của nước đó. Cách này giúp tính sâu hơn với cùng công sức.
Minimax có dùng được khi có xúc xắc không?
Có, nhưng phải thêm nút may rủi. Ở nút đó không ai chọn, giá trị là trung bình các kết quả theo xác suất. Cách làm này thường được gọi là expectiminimax.
Hiệu ứng chân trời là gì?
Là lỗi khi tính tới một độ sâu cố định nên không thấy tai hoạ nằm ngay sau tầng cuối. Cây có thể chọn một nước chỉ đẩy nguy cơ ra xa hơn tầm nhìn chứ không thật sự tránh được nó.