LUẬT CỜ VÂY LÀM THAY ĐỔI ĐÁP ÁN

Giải một trò chơi nghĩa là biết kết quả của nó khi cả hai bên đều chơi hoàn hảo. Trên bàn cờ vây, kết quả đó là một giá trị: số điểm mà Đen thắng khi chơi hoàn hảo — 28 trên bàn 4×7 nghĩa là Đen chiếm cả 28 giao điểm. Cờ đam được giải năm 2007, và cờ Hex trên bàn nhỏ cũng vậy. Với cờ vây, đã có các chứng minh bằng máy tính cho nhiều bàn cờ tới 30 giao điểm, phần lớn từ một chương trình tên là MIGOS (2003 và 2009).

Có một điểm vướng. Những kết quả kinh điển đó dùng một luật đơn giản hóa cho các thế cờ lặp lại — luật “cướp” (ko) cơ bản — một người chơi không được bắt lại ngay một quân đơn lẻ vừa bắt một quân của mình, vì như vậy sẽ lặp mãi đúng hai nước đi đó — cộng thêm các quy ước đặc biệt: một nước bỏ lượt sẽ gỡ lệnh cấm cướp, ván cờ dừng lại khi gặp thế lặp, v.v. Các quy ước này được thiết kế để giá trị của một thế cờ không phụ thuộc vào con đường dẫn tới nó.

Luật mà người ta thật sự chơi

Luật Trung Quốc theo văn bản, và cờ vây máy tính, dùng superko vị trí (positional superko): không nước nào được tái tạo bất kỳ thế toàn bàn nào đã từng xuất hiện trong ván. Giải theo luật này khó hơn nhiều, vì giờ đây tính hợp lệ của một nước đi phụ thuộc vào toàn bộ lịch sử của ván cờ. Nó phá vỡ ba công cụ giúp việc giải khả thi:

• tái sử dụng kết quả của cùng một thế cờ đạt được theo một con đường khác — hai con đường có thể cấm những nước khác nhau;
• nhận ra các nhóm quân an toàn và đất mà không cần tìm kiếm, vốn giả định rằng chủ nhân luôn bắt được quân xâm nhập — dưới luật superko, nước bắt như vậy có thể bị cấm;
• cắt tỉa những nước không bao giờ có ích, như lấp mắt của chính mình — một trong những điểm trống mà một nhóm quân cần có để sống — dưới luật superko, một nước như vậy có thể trở nên quyết định.

Cái giá rất lớn: với một biến thể superko, MIGOS cần 1,1 giờ cho bàn 4×4, so với 3,3 giây theo luật cướp cơ bản. Lời giải superko đầu tiên cho bàn 5×5, năm 2024, mất 5,25 giờ trên sáu tiến trình. Vượt quá 5×5, chưa bàn nào có ít nhất hai hàng được giải theo superko.

Một lối tắt vẫn đúng đắn

Sami Kharma và Florian Schintke, ở Viện Zuse Berlin (Zuse Institute Berlin), đã xây dựng Sanko. Cốt lõi của nó là một định lý chuyển giao chứng minh (proof-transfer theorem) đơn giản: một chứng minh đã lưu rằng một người chơi thắng vẫn còn hiệu lực trên một con đường mới, trừ khi một thế cờ mà người thắng buộc phải tạo ra đã xuất hiện rồi. Chỉ các thế cờ của người thắng là quan trọng — nếu người thua không còn tái tạo được một thế, người thua chỉ mất đi một lựa chọn. Việc kiểm tra điều này tốn thời gian tỉ lệ với độ dài con đường, chứ không phải kích thước của chứng minh. Trên bàn 3×7, riêng lối tắt này đã giảm khối lượng công việc từ 664 tỉ bước xuống 112 triệu.

Họ cũng điều chỉnh cách nhận diện kinh điển các nhóm quân an toàn để nó vẫn đúng dưới luật superko, và chỉ cắt tỉa các nước của bên mà họ đang tìm cách chứng minh là thắng, sao cho một cuộc tìm kiếm thất bại được báo là chưa biết, không bao giờ là thắng cho bên kia.

Những giá trị mới

• 5×5 trong 15,7 phút trên sáu luồng — nhanh hơn khoảng 20 lần so với trước, một phần nhờ phần cứng tốt hơn; trên một luồng, 4×4 được giải nhanh hơn 58 lần. Trên một máy 192 luồng, 5×5 mất khoảng một phút rưỡi.
• Các giá trị superko đầu tiên của 23 bàn cờ khác; 11 bàn trong số đó chưa từng được giải theo bất kỳ luật nào. 3×10 đáng 8 điểm cho Đen — MIGOS mới chỉ chứng minh được ít nhất 6, và hai tháng tìm kiếm không tìm ra cận trên.
• Trên các bàn một hàng, giá trị từ 1×9 đến 1×15 lặp lại 0, 1, 2, 2 — nhưng 1×16 phá vỡ quy luật, đáng 1 thay vì 2.

Bất ngờ ở bàn 4×7

Theo luật cũ, 4×7 là thắng trọn bàn: Đen bắt hết, 28–0. Theo superko, nó đáng 12. Các tác giả đã chơi lại đường đi tối ưu 31 nước đã công bố cho MIGOS: mọi nước đều hợp lệ, và Đen vẫn chiếm trọn bàn. Giải ngược đường đi đó, họ tìm ra điểm gãy ngay sau nước thứ 25: ở thế cờ sau nước thứ 25, do Đen đi, Trắng nên đi G2 (hoặc C1) thay vì A2.

Tiếp theo là một thế cướp kỳ lạ. Trắng bắt quân; nước bắt lại của Đen sẽ tái tạo một thế cờ cũ — bị cấm. Mọi nước đi khác của Đen đều đặt nhóm quân của chính mình vào nguy hiểm. Đen phải bỏ lượt, Trắng bỏ lượt, và ván cờ kết thúc với nhóm quân Trắng còn sống: điều mà các tác giả của MIGOS đã gọi là “sống dưới ánh trăng” (moonshine life). Theo luật cũ, nước bỏ lượt sẽ gỡ lệnh cấm và Đen sẽ bắt lại rồi thắng tất cả. Theo superko, kết quả tốt nhất của Đen trên đường đi này là một thế cùng sống (seki) chỉ đáng 3 điểm, nên lối chơi hoàn hảo rời khỏi đường đi đã công bố từ sớm hơn — và kết quả tốt nhất mà Đen có thể giành được từ bàn cờ trống là 12.

Không cuộc tìm kiếm nào sai cả. Sự khác biệt đến từ những luật chỉ có ý nghĩa vào lúc thật sự cuối ván. Lời khuyên của các tác giả: không nên trích dẫn các giá trị được tính theo những quy ước làm cho sự lặp lại trở nên vô hại như thể đó là giá trị của cờ vây superko mà không kiểm tra lại.

Ai cũng kiểm chứng được

Mỗi giá trị đều dựa trên hai chứng minh độc lập, và bộ giải đã vượt qua hàng chục nghìn lần kiểm tra chéo mà không có sai lệch nào. Khác với các lời giải trước đây cho bàn cờ vây trống, mã nguồn của bộ giải và câu lệnh chính xác đằng sau mọi kết quả đều được công khai; chuỗi chứng minh cho bàn 4×7 chạy lại trong chưa đầy hai mươi giây. Các chứng minh này chưa phải là những chứng chỉ mà người ngoài có thể tự kiểm chứng độc lập, và bàn 6×6 vẫn nằm ngoài tầm với — theo ngoại suy của các tác giả, khoảng 50 ngày trên một máy của họ, hoặc hơn.