Một trò chơi được gọi là "đã được giải" khi người ta biết chắc kết quả của nó nếu cả hai bên chơi hoàn hảo: bên đi trước thắng, bên đi sau thắng, hay hoà. Nhờ máy tính, một số trò quen thuộc đã được giải: Connect Four và cờ caro năm ô trên bàn 15x15 theo luật tự do là bên đi trước thắng chắc; cờ đam kiểu Anh trên bàn 8x8 là hoà. Cờ vua, cờ tướng, cờ vây trên bàn chuẩn thì chưa ai giải được.
Bài này giải thích ba mức "giải" khác nhau, kể các trò đã được giải theo cách được giới nghiên cứu công nhận, vì sao cờ vua còn xa, và điều đó có ý nghĩa gì với người chơi cờ caro ở quán nước hay người chơi cờ vua phong trào. Phần trò chơi bàn cờ cho gia đình có danh mục riêng; ở đây là góc nhìn của máy.
Ba mức "giải" một trò chơi
Giải siêu yếu. Biết kết quả của thế ban đầu khi hai bên chơi hoàn hảo, nhưng không nhất thiết biết cách chơi để đạt kết quả đó. Ví dụ kinh điển là cờ Hex: nhà toán học John Nash và những người khác đã chứng minh bằng lập luận "ăn cắp chiến lược" rằng bên đi trước luôn có cách thắng, nhưng trên bàn lớn không ai biết cụ thể cách đó là gì.
Giải yếu. Biết kết quả từ thế ban đầu và có một chiến lược cụ thể để đạt được kết quả đó, dù đối phương chơi thế nào. Cờ đam kiểu Anh và cờ caro tự do 15x15 thuộc loại này. Chiến lược đó thường được lưu trong máy dưới dạng cây nước đi khổng lồ.
Giải mạnh. Biết kết quả đúng và nước tốt nhất cho mọi thế cờ hợp lệ, kể cả các thế không xuất hiện khi hai bên chơi tốt. Cờ ca rô ba ô trên bàn 3x3 là ví dụ dễ nhất. Các bảng tàn cuộc cờ vua đến bảy quân là dạng giải mạnh cho một phần nhỏ của cờ vua.
Vì sao phân biệt. Khi đọc tin "máy đã giải trò X", bạn nên hỏi giải ở mức nào. Một trò được giải siêu yếu vẫn có thể chơi rất thú vị vì không ai biết đường thắng; một trò được giải mạnh thì máy không bao giờ đi sai, nhưng người vẫn chơi được với nhau bình thường.
Các trò chơi bàn cờ đã được máy giải
Bảng dưới chỉ ghi những kết quả được giới nghiên cứu trò chơi tổ hợp công nhận rộng rãi. Luật cụ thể (kích thước bàn, luật năm ô hay từ năm ô trở lên) ảnh hưởng tới kết quả, nên đọc kỹ cột luật.
| Trò chơi | Luật được giải | Kết quả | Ghi chú |
|---|---|---|---|
| Cờ ca rô ba ô | Bàn 3x3, ba ô liền thắng | Hoà | Giải được bằng tay, trẻ em tự phát hiện sau vài chục ván |
| Connect Four | Bàn 7 cột 6 hàng, thả quân từ trên xuống | Bên đi trước thắng | Hai nhà nghiên cứu giải độc lập năm 1988; đi đầu ở cột giữa là then chốt |
| Cờ caro (gomoku) | Bàn 15x15, năm ô liền, không luật chặn | Bên đi trước thắng | Victor Allis công bố đầu thập niên 1990, dùng kỹ thuật tìm kiếm theo chuỗi đe doạ |
| Cờ đam kiểu Anh | Bàn 8x8, 12 quân mỗi bên | Hoà | Nhóm làm chương trình Chinook công bố trên tạp chí Science năm 2007, sau gần hai mươi năm tính |
| Cờ vua | Chỉ các thế từ bảy quân trở xuống | Biết chắc từng thế | Bảng tàn cuộc; cả ván cờ vua vẫn chưa được giải |
Điều đáng lưu ý: "cờ đam" mà nhiều người Việt chơi thường là cờ đam quốc tế trên bàn 10x10, khác cờ đam kiểu Anh 8x8. Cờ đam quốc tế lớn hơn nhiều và chưa được giải. Tương tự, cờ caro chơi ở quán thường có luật "chặn hai đầu không tính", luật này làm phép giải ở trên không còn áp dụng trực tiếp.
Chinook và cờ đam: hai mươi năm để chứng minh một ván hoà
Câu chuyện giải cờ đam kiểu Anh gắn với chương trình Chinook do nhóm của Jonathan Schaeffer ở Đại học Alberta (Canada) phát triển từ cuối thập niên 1980. Ban đầu, mục tiêu là làm ra chương trình chơi giỏi nhất. Chinook gặp nhà vô địch Marion Tinsley, người được coi là kỳ thủ cờ đam vĩ đại nhất, hầu như không thua ai trong nhiều thập niên. Tinsley thắng trận đầu năm 1992. Đến trận thứ hai năm 1994, sau sáu ván hoà, Tinsley phải rút lui vì lý do sức khoẻ, và Chinook trở thành nhà vô địch.
Sau đó nhóm đặt mục tiêu lớn hơn: chứng minh kết quả của cả trò chơi. Họ kết hợp hai mảnh. Từ cuối ván, máy tính ngược mọi thế có ít quân thành bảng tàn cuộc. Từ đầu ván, máy tìm kiếm xuôi xuống, chứng minh các nhánh chính đều dẫn tới thế đã biết kết quả. Khi hai mảnh gặp nhau, kết quả của thế ban đầu được xác định. Công bố năm 2007 kết luận: nếu hai bên chơi hoàn hảo, cờ đam kiểu Anh là hoà.
Phần đáng nể nhất của dự án không nằm ở sức tính mà ở sự cẩn trọng. Một lỗi nhỏ trong bảng tàn cuộc có thể làm sai cả chứng minh, nên nhóm phải kiểm chéo dữ liệu nhiều lần, so kết quả giữa các lần tính độc lập trước khi tin vào một nhánh đã chứng minh. Với người làm khoa học, đây là ví dụ hay về chuyện kết quả tính bằng máy cũng cần được kiểm như một chứng minh viết tay.
Bài học của Chinook với người chơi: một trò chơi "hoà nếu chơi hoàn hảo" vẫn có rất nhiều ván thắng thua giữa người với người, vì không ai chơi hoàn hảo. Cờ vua nhiều khả năng cũng là trò hoà, nhưng chuyện đó không làm ván cờ của bạn bớt thú vị.
Vì sao cờ vua, cờ tướng, cờ vây còn xa mới được giải
Khó khăn không nằm ở thuật toán mà ở kích thước. Có thể hình dung bằng vài bước so sánh.
- Cờ đam kiểu Anh có khoảng 5 nhân 10 mũ 20 thế cờ hợp lệ theo ước tính của nhóm Chinook. Ngay cả với số đó, nhóm vẫn phải dùng rất nhiều máy chạy trong nhiều năm và chỉ cần chứng minh một phần nhỏ thế cờ.
- Cờ vua có số thế cờ hợp lệ được ước tính vào khoảng 10 mũ 44 trở lên, lớn hơn cờ đam hàng chục bậc độ lớn. Mỗi bậc là gấp mười lần.
- Bảng tàn cuộc bảy quân của cờ vua đã cần dung lượng lưu trữ rất lớn. Mỗi quân thêm vào làm dung lượng tăng lên nhiều lần, nên bảng tám quân vẫn là dự án dang dở và rất tốn kém.
- Cờ tướng có bàn lớn hơn và luật về chiếu dai, bắt dai phức tạp, khiến việc định nghĩa chính xác thế nào là "hoà" hay "thua" trong mọi trường hợp lặp lại đã khó, chưa nói tới giải.
- Cờ vây trên bàn 19x19 có số thế cờ hợp lệ khoảng 2 nhân 10 mũ 170, như bài về AlphaGo trong danh mục đã nhắc. Chỉ các bàn rất nhỏ mới được giải.
Vì vậy, nhận định chung của giới nghiên cứu là cờ vua sẽ không được giải bằng máy tính theo cách hiện nay trong tương lai gần. Máy chơi mạnh hơn người rất xa, nhưng "mạnh hơn người" và "biết kết quả hoàn hảo" là hai chuyện khác nhau.
Cờ caro ở quán nước: biết "bên đi trước thắng chắc" để làm gì
Cờ caro là trò rất nhiều người Việt chơi, trên giấy kẻ ô hoặc trên điện thoại. Kết quả giải ở trên có vài hệ quả thực tế.
- Luật mở hoàn toàn thì bên đi trước có lợi lớn. Đó là lý do nhiều nơi chơi luật "chặn hai đầu" hoặc luật riêng cho bên đi trước. Muốn công bằng khi chơi với bạn, hãy luân phiên người đi trước sau mỗi ván.
- Biết thắng chắc không có nghĩa là người làm được. Chiến lược thắng do máy tìm ra rất dài và phức tạp. Ngay cả kỳ thủ caro chuyên nghiệp cũng không thuộc hết; họ chơi bằng hình mẫu tấn công "bốn ba", "ba ba" như mọi người khác.
- Các giải caro chuyên nghiệp dùng luật khác. Biến thể renju có luật cấm một số thế đối với bên đi trước để giảm lợi thế. Theo các tài liệu về trò chơi tổ hợp, renju cũng đã được nhóm nghiên cứu giải đầu thập niên 2000 với kết quả bên đi trước thắng, nên giới thi đấu tiếp tục điều chỉnh luật khai cuộc.
- Chơi với máy caro trên điện thoại. Ở mức khó cao, máy caro gần như không thể bị đánh bại khi được đi trước. Muốn luyện, hãy giành quyền đi trước cho mình, hoặc chọn mức vừa sức, và tập nhận ra thế đe doạ kép.
- Dạy trẻ. Trò ca rô ba ô là cách hay để giải thích cho trẻ ý tưởng "nếu cả hai chơi đúng thì hoà": sau một thời gian, trẻ tự phát hiện mình không thể thua nếu cẩn thận. Đây là bài học tư duy hay, không cần biết máy tính.
Điều "được giải" nói lên về trí tuệ nhân tạo
Giải một trò chơi và chơi giỏi trò chơi đó là hai hướng khác nhau của trí tuệ nhân tạo. Giải trò chơi là việc chứng minh, cần tính trọn vẹn và không chấp nhận sai sót: một nhánh chưa kiểm là chưa giải. Chơi giỏi là việc ra quyết định tốt trong điều kiện không biết hết, chấp nhận đánh giá gần đúng. Máy cờ vua, cờ vây hiện nay thuộc hướng thứ hai.
Các kỹ thuật dùng để giải trò chơi, như tìm kiếm theo số chứng minh, bảng tàn cuộc dựng ngược, lại có ích ở chỗ khác, chẳng hạn kiểm chứng phần mềm và giải các bài toán tổ hợp. Còn các kỹ thuật chơi giỏi, như mạng nơ-ron kết hợp tìm kiếm, có ích cho các bài toán ra quyết định mà không thể tính hết.
Với người chơi, phân biệt này giúp đọc đúng con số máy báo. Khi máy phân tích báo "chiếu hết sau 12 nước" ở tàn cuộc ít quân, đó là kết quả đã được chứng minh từ bảng tàn cuộc. Khi máy báo "hơn 0,8 tốt" ở trung cuộc, đó chỉ là đánh giá của máy, có thể đổi khi máy tính lâu hơn. Hai loại con số trông giống nhau trên màn hình nhưng độ tin cậy rất khác.
Câu hỏi thường gặp
Cờ caro có phải bên đi trước luôn thắng không?
Trên bàn 15x15 với luật năm ô tự do, đã được chứng minh bên đi trước có chiến lược thắng nếu chơi hoàn hảo. Nhưng chiến lược đó rất phức tạp, và với luật chặn hai đầu hay bàn kích thước khác thì kết quả không còn áp dụng trực tiếp. Giữa người với người, bên đi sau vẫn thắng thường xuyên.
Cờ vua có phải là trò hoà nếu chơi hoàn hảo không?
Chưa ai chứng minh được. Nhiều kỳ thủ và nhà nghiên cứu tin rằng cờ vua là hoà khi chơi hoàn hảo, dựa trên tỉ lệ hoà rất cao giữa các máy mạnh nhất. Nhưng niềm tin dựa trên quan sát chưa phải chứng minh.
Bảng tàn cuộc có làm cờ vua kém thú vị đi không?
Không với người chơi bình thường. Bảng tàn cuộc chỉ phủ các thế rất ít quân, và người chơi không được dùng nó khi thi đấu. Nó chủ yếu giúp phân tích sau ván và giúp tác giả sách tàn cuộc kiểm chứng kết luận của mình.
Cờ tướng có bảng tàn cuộc như cờ vua không?
Có các cơ sở dữ liệu tàn cuộc cờ tướng do cộng đồng và các nhóm nghiên cứu dựng, phủ các thế ít quân. Việc này khó hơn cờ vua một phần vì luật lặp nước cờ tướng phức tạp. Muốn dùng, bạn nên kiểm phần mềm phân tích mình đang dùng có hỗ trợ không.
Máy giải một trò chơi cần bao lâu?
Tuỳ kích thước trò chơi. Connect Four được giải trên máy tính cuối thập niên 1980. Cờ đam kiểu Anh cần gần hai mươi năm làm việc của một nhóm, với nhiều máy chạy song song trong nhiều năm. Với cờ vua, cách làm hiện nay không đủ dù dùng toàn bộ máy tính trên thế giới.
Có nên dạy trẻ chơi caro với máy không?
Có thể, nếu chọn mức dễ và chơi cùng con. Máy ở mức khó gần như không thua, khiến trẻ nản. Phụ huynh nên dùng caro như trò chơi trò chuyện, cùng con tìm thế đe doạ, thay vì để con chơi một mình với máy quá lâu.