- Không tồn tại thế cờ nào có thể đi nhiều hơn 218 nước so với thế cờ 218 nước do Nenad Petrović công bố vào năm 1964
- Vì việc duyệt toàn bộ mọi thế cờ là bất khả thi trên thực tế, nghiên cứu đã chứng minh giới hạn này bằng tối ưu hóa toán học và kỹ thuật mô hình hóa bằng máy tính
- Không gian tìm kiếm được thu hẹp hiệu quả bằng cách loại bỏ quân không cần thiết, cho phép bố trí quân từng phần, đơn giản hóa nhập thành và nhiều biện pháp khác
- Cuối cùng, nghiên cứu xác nhận 218 là mức tối đa bằng công cụ tối ưu hóa Gurobi, đồng thời kiểm chứng thêm các kỷ lục như 144 nước (không tính phong cấp)
- Nghiên cứu này giúp các nhà phát triển engine cờ vua và công cụ nén loại bỏ sự bất định về giới hạn số nước đi tối đa
Giới thiệu: tranh luận về thế cờ 218 nước
Kể từ khi đại kiện tướng sáng tác thế cờ Nenad Petrović công bố một thế cờ có 218 nước vào năm 1964, đã có nhiều nỗ lực nhằm phá kỷ lục này. Tác giả, với vai trò là một nhà khoa học máy tính, muốn khép lại câu hỏi này bằng cách phân tích các thế cờ bằng máy tính. Dù có khoảng 4.8 × 10^44 thế cờ cờ vua có thể đạt được, việc tìm kiếm trên quy mô khổng lồ như vậy là không khả thi trong thực tế.
Đưa tối ưu hóa toán học vào bài toán
Giảm thiểu quân cờ và tổ hợp không cần thiết
- Việc bổ sung thêm quân đen trên bàn cờ chỉ làm tăng số nước đi trong những trường hợp hạn chế
- Chẳng hạn khi cho phép tốt trắng bắt quân, hoặc khi giúp tránh một tình huống chiếu đối với vua đối phương
- Phần lớn quân đen có thể bị loại bỏ mà không ảnh hưởng đến số nước đi tối đa
- Chừng nào còn thỏa điều kiện về số lượng quân, có thể thay quân đen bằng các quân yếu hơn hoặc điều chỉnh cách bố trí dưới một số ràng buộc nhất định (như ghim quân)
- Ngược lại, với quân trắng, nếu thay toàn bộ bằng các quân mạnh như hậu để tạo thế cờ tối ưu thì có thể phát sinh thế cờ bất hợp lệ, nên cần điều chỉnh rất tinh tế
Tình huống chiếu và giới hạn số nước đi
- Trạng thái vua đen đang bị chiếu không phải là một thế cờ hợp lệ, nên không cần xét
- Khi vua trắng bị chiếu, khả năng di chuyển bị hạn chế nghiêm trọng (tối đa 120 nước), hoàn toàn không thể chạm mốc 218 nước
- Vì vậy có thể chỉ tìm kiếm trong các thế cờ không có chiếu
Bố trí quân từng phần và mô hình hóa toán học
Để giảm độ phức tạp tổ hợp, nghiên cứu tiếp cận bài toán bằng mô hình nới lỏng với bố trí quân từng phần (fractional), nước đi từng phần, và một số luật cờ vua được làm lỏng.
- Ví dụ, một quân cờ có thể tồn tại với xác suất 27.3% ở e4 và 72.7% ở một vị trí khác
- Theo cách này, bài toán được triển khai dưới dạng quy hoạch tuyến tính nguyên (ILP, Integer Linear Programming) bằng các công cụ tối ưu hiện đại như Gurobi
- Ban đầu, nghiên cứu vấp phải giới hạn về bộ nhớ và thời gian (hết bộ nhớ sau khoảng 55.000 giây)
- Để đơn giản hóa không gian tìm kiếm, nghiên cứu tiếp tục áp dụng các biện pháp như đơn giản hóa luật nhập thành, bỏ qua chiếu, bỏ qua ghim quân, đơn giản hóa điều kiện bắt tốt qua đường và hơn thế nữa
Tối ưu hóa và kết luận
Cuối cùng, sau khi cải tiến mô hình bằng cách bổ sung các ràng buộc phụ trợ để chặn việc duyệt những tổ hợp không cần thiết, quá trình tối ưu hóa đã được hoàn tất bằng chương trình Gurobi.
- Cận trên được thu hẹp dần từ 305 nước → 271.67 nước → 218 nước
- Xác nhận rằng chỉ có 12 thế cờ tiêu biểu cho khả năng đạt 218 nước là có thể đạt được
- Chứng minh rằng các thế cờ này đều là thế cờ hợp lệ, có thể đạt tới một cách tự nhiên bằng proof game
Ngoài ra, nghiên cứu cũng hoàn tất việc kiểm chứng các kết quả như tối đa 144 nước nếu không phong cấp, tối đa 288 nước trong thế cờ bất hợp lệ, và kỷ lục 271 nước trong các thế cờ hợp lệ nhưng không thể đạt tới.
Kết quả và ý nghĩa
- Nhờ kết quả này, các nhà phát triển engine cờ vua và nhà nghiên cứu thuật toán nén có thể tự tin rằng giới hạn 256 nước là đủ cho các thiết kế như bố trí bộ nhớ
- Đã được chứng minh bằng toán học rằng không tồn tại thế cờ nào có thể đi từ 218 nước trở lên theo một lộ trình hợp lệ
Tóm tắt FAQ
- Một ván cờ có thể dài hơn 218 nước, nhưng nghiên cứu này xét số lựa chọn tối đa có thể có trong 'một lượt'
- Nếu có thế cờ nào đó trông như không thể đạt được, tác giả lưu ý rằng vẫn có nhiều lộ trình, chẳng hạn trường hợp nước đi trước kết thúc bằng một nước bắt quân
- Phương pháp nghiên cứu áp dụng kỹ thuật oracle toán học để nhanh chóng loại bỏ những tổ hợp 'tuyệt đối bất khả thi' trong không gian tổ hợp khổng lồ
- Mã nguồn sử dụng và cả tính đúng đắn toán học của các bằng chứng được công bố để bảo đảm độ tin cậy
Bài toán tương lai và gợi ý nghiên cứu thêm
Kỹ thuật này có thể được áp dụng để thử sức với nhiều bài toán cờ vua khác như 'số nước bắt tối đa', 'nhiều thế bí tối đa', 'nhiều lần chiếu tối đa', 'nhiều thế chiếu hết tối đa', 'nhiều bài toán mate trong 2 nước tối đa' v.v. Tuy nhiên, trong một số trường hợp có thể sẽ cần các thuật toán tối ưu hóa sáng tạo riêng.
Kết luận
- 218 là số nước đi tối đa chính thức có thể có trong một lượt ở một thế cờ vua
- Về ý nghĩa thực tiễn, phần mềm cờ vua và giới nghiên cứu có thể thiết kế cấu trúc xoay quanh mốc 218 (hoặc 256)
- Mã nguồn liên quan và kết quả tối ưu hóa được công khai trên GitHub
Tham khảo
- Bao gồm các liên kết tới proof game và thế cờ như thế cờ 218 nước của Nenad Petrović, 144 nước của Jenő Bán (không phong cấp), v.v.
- Xem giải thích chi tiết và mã nguồn tại Github repository
1 bình luận
Ý kiến trên Hacker News
Trình độ chơi ở các biến thể như 960 hay Crazyhouse trên Lichess cao hơn Chess.com rất nhiều
Nói thật là tốt đến mức vô lý. Nếu có thể thì nên ủng hộ họ
Điều thú vị là các solver mixed integer linear programming (MILP) đã hỗ trợ cách xử lý này. Trong thuật ngữ kỹ thuật, nó được gọi là 'row generation', thường dùng khi viết bài toán dưới dạng ma trận mà hàng là ràng buộc còn cột là biến
Việc thêm các hàng mới một cách động về bản chất cũng giống như chỉ đưa ràng buộc vào khi nó bị vi phạm
Cách này thường được dùng để giải bài toán Traveling Salesman Problem
(Nhân tiện, Wikipedia có Column generation nhưng không có row generation)
Việc nới lỏng hoặc lược bỏ luật cờ cũng ảnh hưởng đến cách chọn biến. Trước khi đi vào mô hình toán học, tôi đã thử những thứ như lazy constraints, nhưng không thấy cải thiện tốc độ đáng kể. Ví dụ, chỉ riêng việc không xét xem vua trắng có đang bị chiếu hay không cũng đã giúp đơn giản hóa rất nhiều
(giả sử Gurobi không có bug, và cách tác giả định nghĩa bài toán cũng như hiện thực nó cũng không có bug)
Tôi thắc mắc liệu Gurobi có thể bị kẹt ở cực đại cục bộ hay không, hay là nó thực sự đã chứng minh được nghiệm tối ưu toàn cục
Nếu Gurobi và code của tôi hoạt động đúng như dự định, và quá trình đơn giản hóa mô hình cờ vua không có sai sót logic, thì kết quả tôi có được chính là chứng minh rằng "giá trị tối đa của số nước đi hợp lệ có thể có trong một thế cờ vua có thể đạt được bằng chuỗi nước đi hợp lệ từ vị trí ban đầu có cả cận trên lẫn cận dưới đều bằng 218". Nói cách khác, Gurobi đã dùng các cận để chứng minh trên toàn bộ không gian tìm kiếm rằng "không thể có trường hợp nào tốt hơn thế này"
Từ góc độ tính toán, toàn bộ không gian bài toán mới quan trọng hơn, vì phải "tính" tất cả trước khi xét chúng có hợp lệ hay không. Không có cách đơn giản nào để chỉ duyệt qua các thế cờ hợp lệ
Nhờ một người quen báo nên tôi mới biết bài viết của mình đang được thảo luận ở đây
Xin lỗi vì đã chọn một tiêu đề chưa đủ rõ ràng; hy vọng giờ thì đã rõ hơn. Cảm ơn mọi người vì phản hồi và những lời động viên ấm áp
Nếu có câu hỏi nào khác về việc chứng minh những sự thật tương tự trong cờ vua, tôi cũng sẵn lòng trả lời ^^
Cảm ơn
Tobi
Cập nhật: bài viết nói có khoảng 8.7x10^45 thế cờ vua có thể đạt được, và https://github.com/lechmazur/ChessCounter lấy đó làm cận trên
(điều này tương ứng khoảng 153 bit)
Nhưng để giải mã hiệu quả, bạn sẽ cần 153 bit, là giá trị log2 làm tròn lên của con số được dự án ChessPositionRanking khuyến nghị (8726713169886222032347729969256422370854716254). ChessCounter không cung cấp code giải mã hiệu quả
Xe/hậu/mã cũng vậy, nhưng trong cờ vua chúng có thể đã bị ăn nên tổng cộng cần 65 trạng thái cho mỗi quân trong số 5 quân đó
Tượng thì chỉ đi được trên một nửa số ô, nên mỗi quân có 33 trạng thái
Tốt có 4 kiểu phong cấp, có thể bị ăn, và tùy trường hợp nhưng đại khái có khoảng 20~30 vị trí cho trạng thái tốt, tổng thể khoảng 290 trạng thái cho mỗi tốt
Tính như vậy thì cần khoảng 112 bit để biểu diễn trạng thái bàn cờ cho một bên màu quân, làm tròn thì cả hai bên cộng lại là 224 bit
En Passant và các ràng buộc castling (ví dụ không còn quyền nhập thành) khi làm tròn lên thì không cần thêm bit nào, vì chỉ cần cộng thêm vài trạng thái cho từng quân là được
Đây có lẽ là dạng biểu diễn bàn cờ độ dài cố định nén nhất
Nếu dùng biểu diễn thưa, do luôn có hai vua nên có thể dùng một số thập phân n chữ số để biểu diễn các quân còn sống cùng với n+2 số 64 bit biểu diễn vị trí, rồi thêm chút thông tin phụ cho castling, en passant, v.v. Nếu trung bình khoảng một nửa số quân đã biến mất thì sẽ cần cỡ 180 bit để biểu diễn trạng thái bàn cờ
Lịch sử nước đi cũng cần khoảng 10 bit mỗi nước (một cặp trắng/đen, một ply là 5 bit), nên chỉ lưu được khoảng 18 nước. Con số này có phần ngắn hơn điểm giữa của độ dài trung bình một ván cờ
Muốn nén hơn nữa thì có vẻ phải triển khai một từ điển cực lớn
Vậy nên nếu mã hóa toàn bộ bàn cờ theo độ dài cố định thì sẽ là 644=256 bit=32 byte
Hoặc nếu dùng biểu diễn độ dài biến thiên chỉ cho các quân, thì lấy chỉ số của mỗi ô trong 64 ô bằng 6 bit, tức là số_lượng_quân10 bit
Ví dụ, vị trí ban đầu sẽ là 32*10=320 bit=40 byte
Còn 5.68e50 "general" mới là cận trên thật sự, cho phép mọi kiểu phong cấp có thể có
Con tốt đó chỉ có đúng một khả năng (ăn con mã bên cạnh) thôi. Nếu không có nó thì bốn hậu trắng và mã có thể đi vào b2. Nhưng trên thực tế những nước đó không thể tồn tại vì vua đen khi ấy đã bị chiếu hết rồi
Rất dễ bị cám dỗ muốn đặt con hậu ở e5 sang chỗ khác để không tạo chiếu hết ngay lập tức, đồng thời mở ô b2 hơn nữa
Tái bút: có vẻ con tốt đó phải còn sống ở vị trí đó để ngăn thế stalemate
Nếu là lượt đen, thì nó cũng không đi được vì vua đang bị ghim bởi hậu trắng ở e5. Nếu không bị ghim thì nó có thể đi 4 nước. Underpromotion cũng có thể
Thế cờ là White to move. Ngay cả nếu con tốt b2 không ghim vua bởi hậu trắng, thì tốt đen đó cũng không thể đi
Con tốt b2 là bắt buộc để che chắn cho vua đen khỏi bị chiếu. Nếu không thì bản thân thế cờ đã không hợp lệ
Tôi đã kiểm tra mọi thứ cực kỳ kỹ, nên có thể yên tâm là mọi nỗ lực để tạo ra hơn 218 nước cho bên trắng đều không thành công. Dù vậy tôi vẫn rất bất ngờ và biết ơn vì có nhiều người quan tâm đến bài viết của mình như vậy, haha ^^
Có vẻ như có thể đổi một trong các tốt đen thành mã trắng để tăng số nước đi, nhưng thực ra cả hai mã đều đã có mặt, và tất cả tốt đều đã được phong cấp, nên điều đó là không thể. (Nếu đổi cả hai tốt thì đen sẽ không thể đi tới trạng thái này ở lượt trước)
Bạn đã đọc hết bài chưa?
Không phải 271, mà là 271.666... :) Con số đó đến từ mô hình trong đó mọi quyết định (0 hoặc 1) được nới lỏng thành giá trị liên tục (0.0~1.0 và mọi giá trị ở giữa). Tức là có thể giả sử một quân cờ tồn tại ở mức 0.23 chẳng hạn. Xác suất một nước đi nào đó khả thi cũng có thể được xử lý kiểu 0.843.
Với kiểu 'black magic' này, tốc độ tính toán sẽ nhanh hơn rất nhiều, và cũng có thể cho ra nhiều nước đi hơn mức thực sự tồn tại.
Vì vậy có thể dùng nó để nhanh chóng loại bỏ các không gian con tệ tiềm năng. Nếu không có kỹ thuật như vậy thì việc vét cạn toàn bộ không gian tìm kiếm là bất khả thi
Nhân tiện, có lẽ bạn đã hiểu nhầm rằng các tốt đen đang ở vị trí ban đầu. Thực ra đó là tốt đen đã đi sang tận phía bên kia bàn cờ (phía quân trắng)