n

Khái niệm giải hoàn toàn cờ vua dưới góc nhìn trí tuệ nhân tạo

Cờ vua từ lâu đã trở thành một bài toán kinh điển của trí tuệ nhân tạo (AI). Mặc dù các công cụ hiện nay đã sở hữu khả năng chơi siêu hạng, tìm ra những nước đi khiến đại kiện tướng bối rối và đánh giá vị trí với độ chính xác vượt trội con người, điều đó không đồng nghĩa trò chơi này đã được “giải”. Các hệ thống AI chủ yếu dựa vào tìm kiếm và mô hình đánh giá để chọn phương án tốt nhất thay vì nắm giữ lời giải hoàn chỉnh cho mọi thế cờ.

Theo định nghĩa chuyên môn, 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 hai bên đều chơi tốt nhất. Có ba mức độ giải gồm giải yếu, giải mạnh và mức tối thiểu chứng minh kết quả lý thuyết của vị trí xuất phát. Hiện tại, cờ vua chưa đạt được bất kỳ mức độ nào trong số này.

Sự khác biệt về quy mô giữa cờ vua và cờ đam

Trái ngược với cờ vua, môn cờ đam đã được giải yếu vào năm 2007 bởi nhóm nghiên cứu Chinook do Jonathan Schaeffer dẫn đầu, chứng minh ván cờ sẽ hòa nếu hai bên chơi tối ưu. Thành công này đến từ quy mô nhỏ hơn của cờ đam với khoảng 5 x 10^20 thế cờ, trong đó công trình thực tế chỉ phải xử lý khoảng 10^14 vị trí nhờ các phương pháp tìm kiếm, cắt tỉa và cơ sở dữ liệu tàn cuộc.

Cuộc tranh luận về độ phức tạp

Trong khi đó, cờ vua sở hữu không gian lớn hơn rất nhiều. Năm 1950, nhà toán học Claude Shannon đưa ra ước tính số ván cờ có thể diễn ra vào khoảng 10^120, còn số thế cờ hợp lệ vào khoảng 10^43. Các nghiên cứu hiện đại điều chỉnh số thế cờ hợp lệ lên khoảng 10^44 hoặc cao hơn. Đầu tháng 9, cuộc tranh luận giữa tỷ phú Elon Musk và nền tảng Chess đã đề cập đến các con số này, khi Musk nhắc tới khoảng 10^44 thế cờ hợp lệ còn Chess đề cập cây trò chơi khoảng 10^120 ván cờ có thể xảy ra.

Thách thức từ sự bùng nổ tổ hợp

Bản chất của cờ vua tạo ra một cái cây xuất phát từ bàn cờ ban đầu, nơi mỗi nước đi và nước trả lời sinh ra hàng loạt nhánh mới theo cấp số nhân. Với ước tính trung bình mỗi vị trí có khoảng 30-35 nước đi hợp lệ và một ván kéo dài chừng 40 nước mỗi bên, quy mô chuỗi khả năng đạt tới 10^120. Từ năm 1950, Claude Shannon đã chỉ ra rằng việc duyệt toàn bộ cây trò chơi bằng phương pháp đơn giản vượt quá khả năng tính toán. Hiện tượng này được gọi là sự bùng nổ tổ hợp, khiến tốc độ xử lý tăng lên của máy tính hiện đại vẫn chưa đủ để giải quyết toàn bộ bài toán.

Nguồn tham khảo

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