Tidak ada posisi catur yang dapat dicapai dengan lebih dari 218 langkah legal

 (lichess.org)
1 poin oleh GN⁺ 2025-09-27 | 1 komentar | Bagikan ke WhatsApp
  • Tidak ada posisi yang memiliki lebih banyak langkah legal daripada posisi catur 218 langkah yang dipublikasikan oleh Nenad Petrović pada 1964
  • Karena menelusuri semua posisi secara menyeluruh secara praktis mustahil, batas ini dibuktikan dengan memanfaatkan optimisasi matematis dan teknik pemodelan berbantuan komputer
  • Ruang pencarian diperkecil secara efektif dengan menghapus bidak yang tidak perlu, mengizinkan penempatan bidak parsial, serta menyederhanakan castling dan aturan lain
  • Pada akhirnya, alat optimisasi Gurobi digunakan untuk memastikan bahwa 218 adalah maksimum, sekaligus memverifikasi rekor lain seperti 144 langkah (tanpa promosi)
  • Penelitian ini menghilangkan ketidakpastian tentang batas jumlah langkah maksimum bagi pengembang engine catur dan kompresi

Pendahuluan: perdebatan posisi catur 218 langkah

Sejak grandmaster komposisi catur Nenad Petrović menerbitkan posisi 218 langkah pada 1964, berbagai upaya terus dilakukan untuk memecahkan rekor tersebut. Penulis, sebagai seorang ilmuwan komputer, ingin mengakhiri pertanyaan ini dengan menganalisis semua posisi menggunakan komputer. Ada sekitar 4.8 × 10^44 posisi catur yang dapat dicapai, tetapi pencarian sebesar itu secara praktis mustahil dilakukan.

Penerapan optimisasi matematis

Meminimalkan bidak dan kombinasi yang tidak perlu

  • Bidak hitam hanya dalam kasus terbatas dapat menambah jumlah langkah
    • Misalnya ketika memungkinkan pion putih melakukan tangkapan, atau saat menghindarkan posisi skak terhadap raja lawan
  • Sebagian besar bidak hitam dapat dihapus tanpa memengaruhi jumlah langkah maksimum
  • Selama jumlah bidak masih diizinkan, bidak hitam dapat diganti dengan bidak yang lebih lemah atau penempatannya disesuaikan di bawah beberapa batasan tertentu (seperti pin)
  • Untuk bidak putih justru sebaliknya: jika semuanya diganti dengan bidak kuat seperti ratu demi membentuk posisi optimal, bisa muncul posisi ilegal, sehingga diperlukan penyesuaian yang cermat

Posisi skak dan batas jumlah langkah

  • Karena raja hitam yang sedang skak bukan posisi legal, kasus itu tidak perlu dipertimbangkan
  • Saat raja putih sedang skak, pergerakan sangat dibatasi (maksimum 120 langkah), sehingga mustahil mencapai 218 langkah
  • Karena itu, pencarian dapat difokuskan hanya pada posisi tanpa skak

Penempatan bidak parsial dan pemodelan matematis

Untuk mengurangi kompleksitas kombinatorial, pendekatan dilakukan dengan model yang melonggarkan penempatan bidak parsial (fractional), pergerakan, dan sebagian aturan catur

  • Sebagai contoh, sebuah bidak bisa berada di e4 dengan probabilitas 27.3%, dan 72.7% sisanya berada di posisi lain
  • Dengan pendekatan ini, masalah diimplementasikan dalam bentuk integer linear programming (ILP) menggunakan alat optimisasi modern seperti Gurobi
  • Pada tahap awal, proses ini terbentur batas memori dan waktu (kehabisan memori setelah sekitar 55 ribu detik)
  • Untuk menyederhanakan ruang pencarian, diterapkan langkah tambahan seperti penyederhanaan aturan castling, mengabaikan skak, mengabaikan pin, dan menyederhanakan kondisi en passant

Optimisasi dan kesimpulan

Pada akhirnya, setelah model diperbaiki dengan menambahkan batasan bantu yang mencegah eksplorasi kombinasi yang tidak perlu, optimisasi berhasil diselesaikan melalui program Gurobi

  • Batas atas dipersempit bertahap dari 305 langkah → 271.67 langkah → 218 langkah
  • Dipastikan bahwa hanya 12 posisi representatif dengan 218 langkah yang benar-benar dapat dicapai
  • Posisi-posisi ini juga dibuktikan sebagai posisi legal yang dapat dicapai tanpa kesulitan melalui proof game

Selain itu, juga terverifikasi bahwa maksimum tanpa promosi adalah 144 langkah, maksimum pada posisi ilegal adalah 288 langkah, dan rekor 271 langkah untuk posisi legal yang tidak dapat dicapai juga valid

Hasil dan makna

  • Berkat hasil penelitian ini, pengembang engine catur dan peneliti algoritme kompresi kini yakin bahwa batas 256 langkah sudah memadai untuk desain memori dan kebutuhan serupa
  • Kini telah dibuktikan secara matematis bahwa tidak ada posisi yang dapat dicapai secara legal dengan lebih dari 218 langkah dalam satu giliran

Ringkasan FAQ

  • Sebuah permainan catur bisa berlangsung lebih lama dari 218 langkah, tetapi penelitian ini membahas jumlah maksimum pilihan langkah yang tersedia dalam 'satu giliran'
  • Jika ada posisi tertentu yang tampak tidak dapat dicapai, disebutkan bahwa ada berbagai jalur lain, misalnya jika langkah sebelumnya berakhir dengan tangkapan
  • Metode penelitian ini menerapkan teknik oracle matematis untuk dengan cepat menyaring kombinasi yang 'benar-benar mustahil' dalam ruang kombinasi yang sangat besar
  • Kode yang digunakan dan validitas matematis dari bukti yang dihasilkan juga dipublikasikan demi memastikan keandalannya

Tugas selanjutnya dan usulan riset tambahan

Teknik ini dapat diterapkan untuk menantang berbagai persoalan catur lain seperti 'jumlah tangkapan terbanyak', 'stalemate terbanyak', 'skak terbanyak', 'skakmat terbanyak', dan 'mate dalam 2 langkah terbanyak'. Namun, untuk beberapa kasus mungkin dibutuhkan algoritme optimisasi kreatif yang terpisah.

Kesimpulan

  • 218 adalah jumlah resmi maksimum langkah legal yang dapat dimainkan dari satu posisi catur dalam satu giliran
  • Secara praktis, perangkat lunak catur dan para peneliti dapat merancang strukturnya dengan acuan 218 (atau 256)
  • Kode terkait dan hasil optimisasi dipublikasikan di GitHub

Referensi

  • Tautan ke proof game dan posisi seperti posisi 218 langkah karya Nenad Petrović, serta 144 langkah karya Jenő Bán (tanpa promosi), juga disertakan
  • Penjelasan rinci dan kode dapat dilihat di repositori Github

Bacaan terkait

1 komentar

 
GN⁺ 2025-09-27
Komentar Hacker News
  • Mereka tidak mengatakannya secara langsung, tetapi yang dimaksud di sini adalah "dalam posisi ini pemain memiliki 218 langkah legal yang bisa dipilih"
    • Saya kaget ternyata selama ini saya salah membaca artikelnya, terima kasih. Saya memahaminya sebagai "jumlah langkah maksimum yang diperlukan untuk mencapai suatu posisi catur adalah 218". Jadi saya heran kenapa artikel ini sama sekali tidak masuk akal bagi saya
    • Saya juga mengira maksudnya "berapa banyak langkah yang dibutuhkan dalam sebuah permainan untuk mencapai posisi ini?"
    • Betul, cukup aneh bahwa artikel itu sama sekali tidak pernah memakai frasa "possible moves". Kata kuncinya adalah "possible". Artikelnya terus memakai ungkapan seperti "have moves", yang terdengar tidak lazim bagi orang awam (meski mungkin lebih umum dalam istilah catur)
    • Terima kasih. Saya bingung soal artikel ini, saya kira ini tentang posisi unik yang membutuhkan jumlah langkah terbanyak
  • Saya benar-benar ingin memuji Lichess. Layanannya dan kontennya luar biasa serta gratis, dan fitur-fitur yang berbayar di Chess.com juga bisa dipakai gratis di sana. Variasi permainannya juga banyak sekali
    Level permainan varian catur seperti 960 atau Crazyhouse di Lichess jauh lebih tinggi daripada di Chess.com
    • Gratis, fungsinya setara dengan server komersial, open source, dan ramah pengembang. Tidak ada iklan (bahkan sama sekali tidak ada iklan untuk akun gratis), serta punya struktur organisasi yang transparan di bawah hukum Prancis
      Benar-benar luar biasa. Saya sangat menyarankan untuk berdonasi jika memungkinkan
  • Dalam tulisan https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow, penulis menjelaskan bahwa pada awalnya ia menghapus sebagian aturan yang rumit, lalu bersedia menambahkannya kembali bila perlu (jika hasil solusi melanggar aturan tersebut)
    Yang menarik, solver mixed-integer linear programming (MILP) sebenarnya sudah mendukung pendekatan seperti ini. Istilah teknisnya adalah 'row generation', biasanya dipakai saat masalah ditulis dalam bentuk matriks, dengan baris sebagai constraint dan kolom sebagai variabel
    Menambahkan baris baru secara dinamis pada dasarnya sama dengan hanya memperkenalkan constraint ketika terjadi pelanggaran
    Pendekatan ini sering dipakai untuk menyelesaikan Traveling Salesman Problem
    (Sebagai catatan, Wikipedia punya artikel tentang Column generation, tetapi tidak ada untuk row generation)
    • Halo, saya penulis artikel Lichess itu
      Melonggarkan atau mengabaikan aturan catur juga memengaruhi pemilihan variabel. Sebelum masuk ke pemodelan matematika, saya sempat mencoba hal seperti lazy constraints, tetapi tidak memberi peningkatan kecepatan yang berarti. Misalnya, hanya dengan tidak mempertimbangkan apakah raja putih sedang skak saja, sudah terjadi banyak penyederhanaan
    • Pendekatan seperti ini biasanya lebih sering disebut lazy constraints (penjelasan terkait)
    • Saya benar-benar penasaran apakah solver MILP bisa selesai pada ruang pencarian sebesar ini, tebakan saya sih tidak mungkin
  • Saya bertanya karena benar-benar penasaran: jika solver integer programming dari Gurobi tidak menemukan solusi yang lebih baik daripada 218, apakah itu menjamin bahwa memang tidak ada solusi yang lebih baik dari 218? Dan apakah ini setara dengan bukti matematis?
    (Dengan asumsi tidak ada bug di Gurobi, dan tidak ada bug juga pada definisi masalah maupun implementasi penulis)
    Saya ingin tahu apakah mungkin saja Gurobi terjebak pada maksimum lokal, atau apakah ia benar-benar membuktikan bahwa itu adalah solusi optimal global
    • Gurobi tidak hanya memberikan solusi integer terbaik yang ditemukan sejauh ini, tetapi juga batas untuk solusi optimal yang mungkin. Batas ini memakai berbagai teknik seperti relaksasi linear masalah, cutting planes, dan lain-lain. Jadi jika solver-nya tidak punya bug, maka itu memang benar-benar solusi optimal
    • Saya penulisnya!
      Jika Gurobi dan kode saya bekerja sebagaimana mestinya, dan tidak ada kesalahan logika dalam proses penyederhanaan model catur, maka hasil yang saya peroleh membuktikan bahwa "nilai maksimum jumlah langkah legal yang mungkin pada posisi catur yang dapat dicapai dari posisi awal melalui urutan langkah legal memiliki batas atas dan bawah yang sama-sama 218". Dengan kata lain, Gurobi membuktikan melalui bounding atas seluruh ruang pencarian bahwa "tidak ada yang lebih baik dari ini"
    • Saya tidak tahu persis bagaimana Gurobi diterapkan di sini, tetapi secara umum solver optimisasi kombinatorial seperti ini membangun pohon bukti yang menunjukkan bahwa tidak mungkin menemukan solusi yang lebih baik untuk alokasi variabel apa pun. Dalam kasus sederhana, Anda bahkan bisa memeriksa pohon itu sendiri dan mengikuti pembuktian dengan kontradiksi. Untuk kasus di artikel ini, pohon buktinya kemungkinan sangat besar. Kalau mau, tetap bisa ditinjau
    • Secara teoretis ini bukan bukti, tetapi dalam praktiknya hampir sama seperti bukti

  • Tidak ada posisi catur yang dapat dicapai dengan lebih dari 218 langkah
    Akan jauh lebih jelas jika ditulis "tidak ada lebih dari 218 langkah legal yang tersedia untuk dimainkan selanjutnya"

Memeriksa semua sekitar 8.7x10^45 posisi catur yang dapat dicapai?
Angka itu sebenarnya terlalu tinggi
https://github.com/tromp/ChessPositionRanking memberi perkiraan yang lebih akurat, yaitu sekitar 4.8x10^44 posisi catur legal

  • Bukankah itu cuma beda sekitar 20 kali lipat? Di skala seperti ini rasanya bukan perbedaan besar
  • Yang satu adalah "legal", yang satu lagi adalah "seluruh ruang masalah"
    Dari sudut pandang komputasi, seluruh ruang masalah lebih penting. Karena semuanya tetap harus "dihitung" sebelum ditentukan legal atau tidak. Tidak ada cara sederhana untuk hanya menelusuri posisi legal saja
  • Halo semuanya
    Seorang teman memberi tahu saya bahwa artikel saya sedang dibahas di sini
    Maaf karena memilih judul yang kurang jelas, semoga sekarang sudah lebih jelas. Terima kasih atas masukan dan kata-kata baiknya
    Kalau ada pertanyaan juga soal pembuktian fakta catur serupa, saya bisa coba jawab ^^
    Terima kasih
    Tobi
    • Jadi untuk memastikan: maksudnya adalah pada setiap posisi papan, jumlah langkah yang bisa dipilih tidak pernah melebihi 218? Apakah saya memahaminya dengan benar?
  • Berapa jumlah bit minimum yang dibutuhkan untuk merepresentasikan papan catur yang dapat dicapai?
    Pembaruan: artikel itu menyebut ada sekitar 8.7x10^45 posisi catur yang dapat dicapai, dan https://github.com/lechmazur/ChessCounter menempatkan angka ini sebagai batas atas
    (Itu setara dengan sekitar 153 bit)
    • Jika kira-kira 4.8x10^44, maka log2(4.8x10^44) adalah 149 bit
      Tetapi untuk dekode yang efisien, Anda perlu 153 bit, yaitu pembulatan ke atas dari log2 angka yang direkomendasikan proyek ChessPositionRanking (8726713169886222032347729969256422370854716254). ChessCounter tidak menyediakan kode dekode yang efisien
    • Raja bisa berada di salah satu dari 64 petak
      Benteng/menteri/kuda juga bisa, tetapi karena bisa saja sudah tertangkap, total ada 65 kemungkinan status untuk masing-masing dari 5 bidak itu
      Gajah hanya bisa berada di separuh petak tersebut, jadi masing-masing 33 status
      Pion punya 4 promosi, bisa tertangkap, dan tergantung situasinya dapat berada di sekitar 20~30 posisi, jadi secara keseluruhan sekitar 290 kemungkinan per pion
      Dengan begitu, untuk satu warna bidak, dibutuhkan sekitar 112 bit untuk merepresentasikan keadaan papan; dibulatkan menjadi 224 bit untuk kedua sisi
      En Passant dan batasan castling (misalnya tidak bisa castling) jika dibulatkan tidak membutuhkan bit tambahan, karena cukup menambah beberapa status pada tiap bidak
      Mungkin ini bentuk representasi papan dengan panjang tetap yang paling terkompresi
      Untuk representasi sparse, karena kedua raja selalu ada, Anda bisa menyatakan bidak yang masih hidup dengan angka desimal n digit dan posisi dengan n+2 buah angka 64 bit, lalu castling, en passant, dan sebagainya hanya butuh sedikit informasi tambahan. Jika kira-kira separuh bidak sudah hilang, rata-rata representasi keadaan papan memerlukan sekitar 180 bit
      Riwayat langkah juga memerlukan sekitar 10 bit per langkah penuh (satu ply 5 bit), sehingga bisa memuat hingga sekitar 18 langkah. Ini sedikit lebih pendek dari titik tengah panjang rata-rata permainan catur
      Untuk kompresi lebih jauh, sepertinya harus memakai kamus berukuran sangat besar
    • Jenis dan warna bidak bisa direpresentasikan dalam 4 bit
      Jadi jika seluruh papan dienkode dengan panjang tetap, hasilnya 644=256 bit=32 byte
      Atau, dengan representasi panjang variabel hanya untuk bidaknya, tiap indeks 64 petak butuh 6 bit, jadi totalnya jumlah_bidak      10 bit
      Sebagai contoh, posisi awal adalah 32*10=320 bit=40 byte
    • Nilai 8.7e45 "restricted" di GitHub itu membatasi beberapa pola promosi pion
      5.68e50 "general" adalah batas atas yang sebenarnya dan mengizinkan semua promosi yang mungkin
  • Pion hitam di b2 sangat mengurangi jumlah langkah yang mungkin bagi bidak-bidak lain
    Pion itu hanya punya satu kemungkinan gerak (memakan kuda di sebelahnya). Jika pion itu tidak ada, empat menteri putih dan kuda bisa masuk ke b2. Tetapi pada kenyataannya langkah-langkah itu tidak bisa ada, karena raja hitam sudah skakmat
    Menggeser menteri di e5 ke tempat lain agar tidak langsung skakmat sambil membuka petak b2 lebih lebar memang terlihat menggoda
    P.S.: rasanya pion itu harus tetap hidup di sana untuk mencegah stalemate
    • Pion hitam di b2 tidak bisa bergerak dalam posisi White to move
      Kalau giliran hitam, raja tetap membuatnya tidak bisa bergerak karena ter-pin oleh menteri putih di e5. Kalau pin itu tidak ada, ia bisa punya 4 langkah. Underpromotion juga mungkin
    • Saya juga bingung dengan ungkapan "bidak hitam tidak berguna". Kelihatannya salah satu menteri yang saling berhadapan itu bisa diubah jadi hitam sehingga keduanya bisa saling menangkap... tetapi akhirnya saya sadar bahwa "hanya satu pihak yang bisa bergerak" adalah poinnya
    • Saya penulisnya
      Posisinya White to move. Bahkan andaipun pion b2 tidak membuat raja hitam ter-pin oleh menteri putih, pion hitam itu tetap tidak bisa bergerak
      Pion b2 itu wajib ada untuk melindungi raja hitam dari skak. Kalau tidak, posisinya sendiri tidak legal
      Saya benar-benar sudah memeriksa semuanya dengan sangat teliti, jadi tenang saja, semua upaya untuk membuat lebih dari 218 langkah dari sisi putih memang gagal. Tapi saya tetap terkejut dan berterima kasih karena begitu banyak orang tertarik pada artikel saya, haha ^^
    • Giliran putih. Jika giliran putih sementara hitam sedang skak, maka posisi itu tidak legal dan tidak dapat dicapai. Tidak ada kemungkinan posisi seperti itu bisa dibuat secara legal pada giliran hitam sebelumnya
      Kelihatannya Anda bisa menambah jumlah langkah dengan mengganti salah satu pion hitam menjadi kuda putih, tetapi kedua kuda sudah ada dan semua pion sudah dipromosikan, jadi itu tidak mungkin. (Kalau kedua pion diganti, maka hitam tidak mungkin mencapai keadaan ini pada giliran sebelumnya)
  • Saya bingung. Tetapi setelah model 271, perubahan apa yang menghasilkan solusi optimal? Hanya tertulis "dengan model yang ditingkatkan ini..."
    • Saya penulisnya!
      Sudah baca artikel lengkapnya?
      Bukan 271, melainkan 271.666... :) Angka itu berasal dari model yang me-relaksasi semua keputusan (0 atau 1) menjadi nilai kontinu (0.0~1.0 dan nilai di antaranya). Jadi seolah-olah sebuah bidak bisa ada sebesar 0.23. Probabilitas sebuah langkah tertentu bisa dimainkan juga diperlakukan seperti 0.843, dan seterusnya.
      Dengan memakai semacam 'sihir hitam' ini, perhitungannya jadi jauh lebih cepat dan bisa menghasilkan jumlah langkah yang lebih besar daripada yang benar-benar mungkin ada.
      Karena itu pendekatan ini dipakai untuk dengan cepat menyingkirkan subruang yang buruk namun masih mungkin. Tanpa teknik seperti ini, mustahil memeriksa seluruh ruang pencarian secara menyeluruh
  • Mungkin saya melewatkan sesuatu, atau posisi yang ditampilkan di awal itu sebenarnya tidak dapat dicapai? Giliran putih, tetapi pion-pion hitam ada di posisi awal, dan rajanya tidak punya petak kosong yang berdekatan, serta tampak terjebak oleh bidak dan pion, jadi rasanya posisi itu tidak mungkin dicapai
    • Bukti bahwa posisi tersebut memang dapat dicapai ada di sini: https://lichess.org/study/PLtuv3v5/zWPNxbSA
      Sebagai catatan, sepertinya Anda salah paham bahwa pion-pion hitam ada di posisi awal. Sebenarnya pion hitam itu telah bergerak sampai ke sisi seberang papan (wilayah putih)
    • Pion hitam berada di wilayah putih (rank 1~2)