Vì sao AI vẫn chưa thể giải hoàn toàn cờ vua?

Dù AI đã vượt xa kỳ thủ mạnh nhất, cờ vua vẫn chưa được giải hoàn toàn vì máy tính chưa thể xác định kết quả tối ưu từ mọi thế cờ hợp lệ.

Cờ vua đã trở thành bài toán kinh điển của trí tuệ nhân tạo (AI), nhưng khả năng chơi siêu hạng không đồng nghĩa với việc máy tính đã "giải" được trò chơi.

Các công cụ hàng đầu hiện nay có thể tìm ra những nước đi mà ngay cả đại kiện tướng cũng khó hiểu, đồng thời đánh giá vị trí với độ chính xác vượt xa con người. Tuy nhiên, chúng vẫn chủ yếu dựa vào tìm kiếm và các mô hình đánh giá để lựa chọn phương án tốt nhất, thay vì sở hữu lời giải hoàn chỉnh cho mọi thế cờ.

Đây cũng là điểm cốt lõi trong cuộc tranh luận giữa tỷ phú Elon Musk và nền tảng Chess đầu tháng 9. Musk cho rằng cờ vua cuối cùng sẽ được giải như cờ đam, trong khi nền tảng đánh giá cao quy mô khổng lồ của trò chơi này.

Một trò chơi được coi là giải hoàn toàn khi có thể xác định kết quả tối ưu từ mọi vị trí hợp lệ, với giả định cả hai bên đều chơi tốt nhất.

Có ba mức độ giải. "Giải yếu" là xác định được kết quả tối ưu từ vị trí ban đầu và xây dựng chiến lược bảo đảm kết quả đó. "Giải mạnh" đòi hỏi biết nước đi tối ưu từ mọi vị trí có thể xuất hiện. Còn ở mức tối thiểu, người ta có thể chỉ cần chứng minh kết quả lý thuyết của vị trí xuất phát, chẳng hạn cờ vua là hòa nếu cả hai bên chơi hoàn hảo.

Cờ vua hiện chưa đạt bất kỳ mức nào trong số này. Trong khi đó, cờ đam đã được giải yếu vào năm 2007, khi nhóm Chinook do Jonathan Schaeffer dẫn đầu chứng minh rằng ván cờ sẽ hòa nếu hai bên chơi tối ưu. Kết quả này được công bố trên tạp chí Science.

Sự khác biệt nằm ở quy mô. Cờ đam có khoảng 5 x 10^20 (500 tỷ tỷ) thế cờ, nhỏ hơn rất nhiều so với cờ vua. Chinook cũng không cần duyệt toàn bộ không gian đó mà sử dụng tìm kiếm, cắt tỉa và cơ sở dữ liệu tàn cuộc để xây dựng một cây bằng chứng nhỏ hơn đáng kể. Theo Schaeffer và cộng sự, công trình giải cờ đam chỉ phải xử lý khoảng 10^14 (100.000 tỷ) vị trí.

Với cờ vua, khoảng cách này lớn hơn rất nhiều. Một "ván cờ" là chuỗi nước đi từ đầu đến cuối. Một "thế cờ" chỉ là cách sắp xếp các quân trên bàn tại một thời điểm. Nhiều chuỗi nước đi khác nhau có thể dẫn tới cùng một thế cờ.

Năm 1950, nhà toán học Claude Shannon đưa ra ước tính nổi tiếng đầu tiên về độ phức tạp của cờ vua. Số ván cờ có thể diễn ra vào khoảng 10^120, trong khi số thế cờ hợp lệ được ước tính ở mức khoảng 10^43.

Các nghiên cứu và ước tính hiện đại đưa số thế cờ hợp lệ lên khoảng 10^44, thậm chí cao hơn, tùy phương pháp tính. Điều đó vẫn nhỏ hơn rất nhiều so với số chuỗi ván cờ có thể diễn ra.

Trong cuộc tranh luận, Chess đề cập tới cây trò chơi với khoảng 10^120 ván cờ có thể xảy ra. Musk nhắc tới khoảng 10^44 thế cờ hợp lệ. Cả hai đều đang sử dụng những con số có cơ sở, nhưng trả lời hai câu hỏi khác nhau. Vấn đề quan trọng hơn là không phải cứ biết số thế cờ là có thể giải được cờ vua.

Hãy hình dung bàn cờ ban đầu là điểm xuất phát của một cái cây. Mỗi nước đi tạo ra một nhánh mới, rồi mỗi nước trả lời của đối phương lại tạo thêm hàng loạt nhánh khác.

Theo cách ước tính của Shannon, một vị trí cờ vua có trung bình khoảng 30-35 nước đi hợp lệ. Nếu một ván kéo dài khoảng 40 nước mỗi bên, số chuỗi khả năng tăng theo cấp số nhân và đạt quy mô khoảng 10^120. Shannon kết luận rằng việc duyệt toàn bộ cây trò chơi bằng phương pháp đơn giản là vượt quá khả năng tính toán trong thời đại của ông.

Trong toán học, đây là sự bùng nổ tổ hợp (combinatorial explosion). Tức là chỉ cần thêm một vài lớp nước đi, số trường hợp cần kiểm tra tăng lên theo cấp số nhân.

Ngay cả khi máy tính ngày nay mạnh hơn nhiều so với năm 1950, bà