ATURAN GO YANG MENGUBAH JAWABANNYA

Memecahkan sebuah permainan berarti mengetahui hasilnya jika kedua pihak bermain sempurna. Di papan go, hasil itu berupa nilai: jumlah poin kemenangan Hitam dengan permainan sempurna — 28 pada papan 4×7 berarti Hitam menguasai seluruh 28 persilangan. Dam dipecahkan pada 2007, begitu pula Hex di papan kecil. Untuk go, sudah ada bukti komputer untuk banyak papan hingga 30 persilangan, sebagian besar dari program bernama MIGOS (2003 dan 2009).

Ada masalahnya. Hasil-hasil klasik itu memakai aturan yang disederhanakan untuk posisi berulang — aturan “ko” dasar — seorang pemain tidak boleh langsung menangkap balik satu batu tunggal yang baru saja menangkap salah satu batunya, karena itu akan mengulang dua langkah yang sama tanpa henti — ditambah konvensi khusus: langkah pas mencabut larangan ko, permainan berhenti pada posisi berulang, dan seterusnya. Konvensi ini dirancang agar nilai suatu posisi tidak bergantung pada cara posisi itu dicapai.

Aturan yang benar-benar dimainkan orang

Aturan Tiongkok sebagaimana tertulis, dan go komputer, memakai superko posisional: tidak boleh ada langkah yang menciptakan ulang posisi seluruh papan mana pun yang sudah pernah terjadi dalam permainan. Memecahkan dengan aturan ini jauh lebih sulit, karena sah tidaknya suatu langkah kini bergantung pada seluruh riwayat permainan. Ini merusak tiga alat yang membuat pemecahan mungkin dilakukan:

• memakai ulang hasil dari posisi yang sama yang dicapai melalui jalur lain — kedua jalur itu bisa melarang langkah yang berbeda;
• mengenali kelompok dan wilayah yang aman tanpa pencarian, yang mengandaikan pemiliknya selalu bisa menangkap penyusup — di bawah superko, penangkapan semacam itu bisa terlarang;
• memangkas (pruning) langkah yang tak pernah membantu, seperti mengisi mata sendiri — salah satu titik kosong yang dibutuhkan sebuah kelompok agar tetap hidup — di bawah superko, langkah seperti itu bisa menjadi penentu.

Biayanya sangat besar: dengan salah satu varian superko, MIGOS memerlukan 1,1 jam untuk papan 4×4, dibandingkan 3,3 detik dengan ko dasar. Solusi superko pertama untuk 5×5, pada 2024, memakan 5,25 jam dengan enam proses. Di atas 5×5, belum ada papan dengan setidaknya dua baris yang pernah dipecahkan di bawah superko.

Jalan pintas yang tetap sahih

Sami Kharma dan Florian Schintke dari Zuse Institute Berlin membangun Sanko. Intinya adalah teorema transfer bukti (proof-transfer theorem) yang sederhana: bukti tersimpan bahwa seorang pemain menang tetap berlaku di jalur baru, kecuali jika sebuah posisi yang harus diciptakan si pemenang sudah pernah muncul. Hanya posisi milik pemenang yang penting — jika pihak yang kalah tidak lagi bisa menciptakan ulang suatu posisi, ia hanya kehilangan satu pilihan. Pemeriksaannya memakan waktu sebanding dengan panjang jalur, bukan ukuran bukti. Pada papan 3×7, jalan pintas ini saja memangkas kerja dari 664 miliar langkah menjadi 112 juta.

Mereka juga mengadaptasi pengenalan klasik kelompok aman agar tetap benar di bawah superko, dan hanya memangkas langkah-langkah pihak yang kemenangannya sedang mereka coba buktikan, sehingga pencarian yang gagal dilaporkan sebagai tidak diketahui, bukan sebagai kemenangan pihak lawan.

Nilai-nilai baru

• 5×5 dalam 15,7 menit dengan enam thread — sekitar 20 kali lebih cepat daripada sebelumnya, sebagian berkat perangkat keras yang lebih baik; dengan satu thread, 4×4 dipecahkan 58 kali lebih cepat. Pada satu mesin dengan 192 thread, 5×5 memakan waktu sekitar satu setengah menit.
• Nilai superko pertama untuk 23 papan lagi; 11 di antaranya belum pernah dipecahkan dengan aturan apa pun. 3×10 bernilai 8 poin bagi Hitam — MIGOS hanya membuktikan setidaknya 6, dan dua bulan pencarian tidak menemukan batas atas.
• Pada papan satu baris, nilai dari 1×9 hingga 1×15 berulang 0, 1, 2, 2 — tetapi 1×16 mematahkan pola itu, bernilai 1, bukan 2.

Kejutan 4×7

Menurut aturan lama, 4×7 adalah kemenangan seluruh papan: Hitam menangkap semuanya, 28–0. Di bawah superko, nilainya 12. Para penulis memutar ulang jalur optimal 31 langkah yang dipublikasikan untuk MIGOS: setiap langkah sah, dan Hitam tetap mengambil seluruh papan. Dengan memecahkan jalur itu dari belakang, mereka menemukan titik patahnya tepat setelah langkah 25: pada posisi setelah langkah 25, yang dimainkan Hitam, Putih seharusnya memainkan G2 (atau C1), bukan A2.

Yang terjadi kemudian adalah ko yang aneh. Putih menangkap; tangkapan balik Hitam akan menciptakan ulang posisi sebelumnya — terlarang. Setiap langkah Hitam yang lain membahayakan kelompoknya sendiri. Hitam harus pas, Putih pas, dan permainan berakhir dengan kelompok Putih tetap hidup: yang oleh para penulis MIGOS sudah disebut “hidup cahaya bulan” (moonshine life). Menurut aturan lama, langkah pas itu akan mencabut larangan, dan Hitam akan menangkap balik dan memenangkan semuanya. Di bawah superko, hasil terbaik Hitam dalam jalur ini adalah hidup bersama (seki) yang hanya bernilai 3 poin, sehingga permainan sempurna meninggalkan jalur yang dipublikasikan lebih awal — dan hasil terbaik yang bisa dijamin Hitam dari papan kosong adalah 12.

Tak satu pun pencarian itu salah. Perbedaannya berasal dari aturan yang baru berpengaruh di bagian paling akhir permainan. Saran para penulis: nilai yang dihitung dengan konvensi yang membuat pengulangan tidak berbahaya jangan dikutip sebagai nilai go superko tanpa diperiksa.

Dapat diperiksa siapa saja

Setiap nilai bertumpu pada dua bukti independen, dan pemecah itu lolos puluhan ribu pemeriksaan silang tanpa satu pun ketidakcocokan. Berbeda dengan solusi papan go kosong sebelumnya, kode sumber pemecah dan perintah persis di balik setiap hasil terbuka untuk publik; rantai bukti 4×7 dapat diputar ulang dalam kurang dari dua puluh detik. Bukti-bukti itu belum berupa sertifikat yang dapat diverifikasi secara independen oleh pihak luar, dan 6×6 masih di luar jangkauan — menurut ekstrapolasi para penulis, sekitar 50 hari di salah satu mesin mereka, atau lebih.