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ờ.
Minh họa robot đánh cờ vua với con người. Ảnh: Google Gemini
Đâ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.
Elon Musk nhiều lần tranh cãi với làng cờ. Ảnh: Business Insider
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ài toán vẫn không thành phép tính đơn giản. Tốc độ xử lý tăng lên không đủ để biến một không gian có quy mô khổng lồ thành một bài toán có thể duyệt hết. Nếu mỗi khả năng đều phải được tính đến, lượng dữ liệu cần xử lý sẽ vượt xa những gì con người có thể xây dựng bằng các hệ thống máy tính hiện nay.
Nếu cờ vua khó đến vậy, tại sao AI đã vượt qua con người? Câu trả lời nằm ở việc chơi cờ giỏi và giải cờ là hai bài toán khác nhau. Năm 1997, Deep Blue của IBM đánh bại Garry Kasparov trong trận đấu 6 ván với tỷ số 3,5-2,5. Đây là cột mốc lịch sử khi máy tính lần đầu thắng nhà vô địch thế giới trong một trận đấu cờ tiêu chuẩn.
Deep Blue kết hợp sức mạnh phần cứng, khả năng tìm kiếm hàng trăm triệu vị trí mỗi giây, thuật toán alpha-beta và hệ thống đánh giá được xây dựng với sự hỗ trợ của các chuyên gia cờ vua. Alpha-beta là một kỹ thuật giúp máy tính cắt bỏ những nước đi không cần tính tiếp, thay vì phải xem toàn bộ cây biến.
Garry Kasparov, kỳ thủ Nga và cựu vô địch thế giới, thực hiện nước đi đầu tiên trong ván hai, trận đấu với siêu máy tính Deep Blue của IBM tại New York, Mỹ, ngày 4/5/1997. Ảnh: Reuters
Theo Campbell, Hoane và Hsu, nhóm tác giả nghiên cứu về Deep Blue, hệ thống này là sự kết hợp giữa tìm kiếm quy mô lớn và các kỹ thuật đánh giá, chứ không phải lời giải hoàn chỉnh cho trò chơi. Deep Blue không cần biết chính xác kết quả của mọi thế cờ trong tương lai. Nó chỉ cần tìm đủ sâu và đánh giá đủ tốt để đánh bại một đối thủ cụ thể.
Hai thập kỷ sau Deep Blue, AlphaZero cho thấy AI không nhất thiết phải cố gắng duyệt ngày càng nhiều nước đi. Hệ thống của DeepMind chỉ được cung cấp luật cờ rồi tự chơi với chính nó. Qua hàng triệu ván đấu, mạng nơ-ron học cách đánh giá thế cờ và lựa chọn những nước đi có triển vọng.
Theo nhà sáng lập David Silver và cộng sự trong nghiên cứu công bố trên Science năm 2018, AlphaZero có thể đạt trình độ siêu hạng thông qua học tăng cường và tự đấu, thay vì được lập trình sẵn kiến thức cờ vua của con người. Đây là bước tiến quan trọng vì nó cho thấy AI không cần kiểm tra toàn bộ cây trò chơi để chơi ở đẳng cấp rất cao.
Các engine hiện đại tiếp tục kết hợp nhiều phương pháp. Stockfish sử dụng tìm kiếm alpha-beta cùng mạng nơ-ron NNUE, trong khi Leela Chess Zero phát triển theo hướng mạng nơ-ron và tự học tương tự AlphaZero.
Những hệ thống này có thể tìm ra nước đi tốt nhất trong thời gian rất ngắn, nhưng "tốt nhất theo đánh giá của engine" không đồng nghĩa với "đã được chứng minh là tối ưu trong toàn bộ trò chơi".
Một minh chứng rõ ràng cho khoảng cách giữa chơi cờ mạnh và giải cờ là các cơ sở dữ liệu tàn cuộc. Khi số quân trên bàn giảm xuống, không gian khả năng cũng nhỏ hơn và máy tính có thể tính toán toàn bộ các vị trí. Hiện nay, mọi thế cờ có tối đa 7 quân, tính cả hai vua, đều đã được giải (gọi là endgame tablebase).
Từ đó, máy tính có thể xác định chính xác vị trí nào thắng, hòa hoặc thua và nước đi tối ưu tương ứng. Nhưng đây chỉ là một phần cực nhỏ của cờ vua. Một bàn cờ đầy đủ có thể chứa tới 32 quân, với vô số cách sắp xếp và lịch sử nước đi khác nhau.
Theo trang Chessiverse, việc giải được các tàn cuộc 7 quân không đồng nghĩa với việc có thể mở rộng trực tiếp phương pháp này cho toàn bộ cờ vua, bởi quy mô không gian trạng thái tăng lên cực nhanh khi thêm quân.
Muốn "giải hoàn toàn" cờ vua, về lý thuyết không nhất thiết phải lưu từng ván cờ riêng biệt. Một thuật toán đủ thông minh có thể nén lời giải thành một tập quy tắc, mô hình hoặc cây bằng chứng nhỏ hơn rất nhiều so với toàn bộ không gian trò chơi.
Đó cũng là bài học từ Chinook. Nhóm Schaeffer không cần lưu toàn bộ hàng nghìn tỷ tỷ thế cờ của cờ đam để chứng minh kết quả. Họ tìm được một cấu trúc tính toán đủ để chứng minh rằng cờ đam hòa với lối chơi tối ưu.
Vì vậy, con số 10^120 không tự nó chứng minh cờ vua không thể được giải. Nó chỉ cho thấy việc duyệt toàn bộ cây trò chơi là không thực tế.
Theo phân tích của ExplainX, chưa có bằng chứng cho thấy một lời giải ngắn gọn kiểu "Chinook" là bất khả thi đối với cờ vua. Ngược lại, cũng chưa ai tìm ra lời giải như vậy. Đây vẫn là một bài toán mở.
Điểm này cũng giúp lý giải lập luận của Musk về siêu trí tuệ nhân tạo (ASI). Ông cho rằng một AI trong tương lai có thể tìm ra cách biểu diễn hoặc nén lời giải mà con người hiện chưa thể tưởng tượng.
Trong một cuộc phỏng vấn năm 1989, chính Kasparov từng nói máy tính sẽ không bao giờ có thể đánh bại ông. Nhưng chỉ sau 8 năm, ông đã phải chấp nhận thất bại trước Deep Blue. Điều đó cho thấy sự phát triển của khoa học kỹ thuật có thể vượt xa nhận định của những kỳ thủ hàng đầu.
Musk có thể đúng, rằng một ngày nào đó cờ vua sẽ được giải. Nhưng với công nghệ hiện tại, khoảng cách từ một công cụ chơi gần như hoàn hảo đến một lời giải hoàn toàn vẫn còn rất lớn.
Xuân Bình tổng hợp