Apa batas bawah yang diketahui tertinggi untuk pasangan di N dari posisi awal?

Sunting : Sepertinya pertanyaan saya tidak cukup jelas. Biarkan saya ulangi: N apa yang terbesar yang kita dapat dengan sadar mengatakan "catur, dari posisi awal, bukan pasangan yang dipaksa dalam gerakan N"?

Catur tidak terpecahkan, yaitu tidak diketahui apa hasil dari posisi awal diberikan permainan yang sempurna.

Namun, jika posisi awal menang untuk salah satu pemain, itu adalah pasangan di N untuk beberapa N. Juga dengan contoh, jika kita tahu pasti bahwa posisi awal tidak dapat dimenangkan dalam 5 gerakan (untuk salah satu pemain), 5 adalah batas bawah untuk N.

Kira-kira seberapa dalam layak untuk mencari secara mendalam dari posisi awal dalam praktik? Seberapa tinggi batas bawah untuk N diketahui?

Ini pada dasarnya adalah pertanyaan tentang apa kompleksitas permainan catur. Perhatikan bahwa oleh finiteness, kita tahu catur yang sudah ditentukan, tapi kami tidak tahu apakah posisi awal adalah kemenangan bagi putih, kemenangan bagi hitam, atau imbang. Kompleksitas permainan catur kira-kira adalah jumlah minimum posisi yang perlu kita periksa di pohon permainan untuk menentukan keadaan posisi awal. Ini dikenal sebagai nomor Shannon . Dalam makalah yang berpengaruh Memprogram Komputer untuk Bermain Catur , Shannon memperkirakan bahwa angka Shannon setidaknya 10 ^ {120). Perhatikan bahwa jumlah partikel di Semesta diperkirakan 10 ^ (80). Untuk menjawab pertanyaan itu, sebenarnya kita ingin tahu ketinggiannyadari pohon permainan ketika posisi awal ditentukan. Kita juga harus membagi tinggi ini dengan 2, karena gerakan dalam catur biasanya dianggap sebagai gerakan putih dan hitam. Faktor percabangan pohon diperkirakan sekitar 30. Dengan demikian, kita dapat mengambil N terbesar sehingga 30 ^ (2N) <10 ^ (120).

Menjawab. Di bagian belakang amplop, N = 40 berfungsi. Secara kebetulan, ini merupakan panjang rata-rata permainan antara grandmaster (meskipun mereka sering mengundurkan diri dan tidak benar-benar memainkan permainan sampai selesai).

Edit. Moral dari cerita ini adalah saya mencoba memperkirakan batas atas untuk batas bawah Anda. Bagian pertama dari alasan Shannon bukanlah lingkaran; dia mengatakan bahwa ada sekitar 30 gerakan hukum dari setiap posisi, dan jumlah ini cukup konstan untuk bagian pertama permainan.

Dengan demikian, kita dapat memperkirakan nilai N yang diketahui saat ini (yang benar-benar apa yang Anda minta, sebut saja N ') ini paling banyak adalah log_30 (C) di mana C sama dengan jumlah daya komputasi yang telah ada dalam sejarah umat manusia. Bahkan dengan perkiraan konservatif untuk C, kita mendapatkan sesuatu seperti N 'paling banyak 20. Dalam praktiknya, saya tidak berpikir ada yang telah melakukan perhitungan ini sangat jauh di atas pohon, karena secara apriori kita tahu bahwa perhitungan menjadi tidak mungkin setelah tinggi pendek dan tidak perlu untuk mendalam mencari pohon untuk menulis program catur yang baik.

Namun perlu dicatat, bahwa Anda mengajukan pertanyaan yang sedikit lebih lemah, karena ada kemungkinan bahwa kondisi awal permainan adalah hasil imbang dengan permainan optimal. Jadi, orang bisa mendapatkan batasan untuk N dengan menulis sebuah program yang tujuannya adalah untuk tidak kehilangan selama mungkin. Kami kemudian dapat memainkan program ini melawan program-program terbaik atau pemain manusia di dunia dan melihat berapa lama permainan terpendek itu. Sekali lagi, ini tidak menjawab pertanyaan dengan benar, karena kita tidak dapat mengasumsikan bahwa lawan kita bermain optimal . Bermain optimal yang benar membutuhkan pengetahuan penuh tentang pohon permainan, tetapi kami telah melihat bahwa ini tidak layak secara komputasi. Dengan demikian, yang terbaik yang dapat kita lakukan saat ini adalah memperkirakan lawan bermain optimal dengan Kasparov atau program catur yang sangat baik.

Itu tidak benar bahwa posisi awal tidak dapat dimenangkan dalam 5 gerakan atau kurang menggunakan definisi kanonik dari gerakan penuh dalam catur. Itu bisa dilakukan dalam 2 gerakan melalui Fool's Mate .

Untuk menjawab pertanyaan Anda, kekuatan mesin catur bergantung pada perangkat lunak dan perangkat keras. Pada tahun 1997, Deep Blue adalah bukti konsep perangkat keras, superkomputer paralel masif yang mampu mengevaluasi 200 juta gerakan per detik dengan kedalaman rata-rata 7-8 gerakan. Namun, pada tahun 2006, Deep Fritz yang berjalan pada komputer pribadi dual-core memiliki hasil yang setara sementara hanya mengevaluasi 8 juta gerakan per detik.

Hari ini, superkomputer terkuat yang telah diterapkan pada catur adalah Blue Gene . Menggunakan 131.000 prosesor, Blue Gene dapat menghitung 280 triliun operasi per detik . Meskipun tidak ada data untuk mengkonfirmasi kedalaman yang bisa dihitung Blue Gene, saya kira itu akan cukup dalam. Tentu saja, ini tergantung pada berapa lama komputer beroperasi.

Namun, dalam hal ini kita tidak dapat menggunakan istilah 'lengkap' saat 'menyelesaikan' dan membuka. Mesin catur tidak perlu pergi ke ujung garis ketika dipastikan bahwa hasil akhirnya menentukan. Dengan demikian, program akan keluar ketika menjadi jelas bahwa evaluasi jelas mendukung satu sisi. Ini dikenal dalam ilmu komputer teoretis sebagai pemangkasan Alpha-Beta .

Jika saya harus membuat perkiraan kasar, saya akan mengatakan bahwa Blue Gene akan dapat menghitung sekitar antara 15 dan 20 gerakan per detik. Meskipun perangkat keras dan lunaknya sangat mengesankan, kita harus ingat bahwa kompleksitas skala catur secara eksponensial. Menurut perkiraan terbaru , kompleksitas permainan-pohon catur setidaknya 10 ^ 123 dan jumlah posisi potensial di 10 ^ 46,7.

Dengan asumsi ada kelanjutan kemenangan dari posisi yang diberikan dan mengasumsikan permainan yang sempurna, menyiratkan Nadalah tetap dan tidak terikat (jika tidak itu bermain tidak sempurna!).

Dalam hal ini seseorang harus benar-benar bekerja mundur - yang dilakukan oleh Endgame Tablebase

Tablebase dari semua endgames dengan hingga enam buah tersedia untuk diunduh gratis, dan juga dapat ditanyakan menggunakan antarmuka web (lihat tautan eksternal di bawah). Tabulasi Nalimov membutuhkan ruang penyimpanan lebih dari satu terabyte

Anda dapat mencari di sini untuk diskusi. Tentu saja Anda tidak boleh menggunakan aturan 50 move, tetapi menurut forum ini, catatan sejauh ini dipegang oleh posisi ini (hitam untuk dipindahkan):

517 bergerak ke posisi kemenangan dan 525 untuk kawin (permainan terbaik oleh kedua belah pihak). Lihat di sini , entri 316. Jadi ini adalah posisi kemenangan tanpa kemenangan dalam waktu kurang dari 525 gerakan.

Izinkan saya juga mereproduksi komentar Bourzutschky: "Akhiran 7-man yang lebih dalam mungkin ada, tetapi saya meragukannya. Kedalaman yang begitu besar masih dimungkinkan dengan begitu banyak daya tembak di papan menunjukkan bahwa ujung yang lebih dalam mungkin muncul dengan 8 buah, mungkin dalam krnnkbbn. Akhiran ini dapat dihasilkan dengan 64 GB RAM dalam beberapa bulan pada mesin CPU tunggal cepat dan sekitar 5 terabyte penyimpanan. Ada yang mengambil? "

Sunting: Maaf, sepertinya saya salah membaca pertanyaan. Dugaan saya adalah bahwa setiap N yang masuk akal berada di luar cakrawala komputer. Jika kita memasang komputer yang sangat kuat untuk menghitung posisi awal yang mungkin merupakan satu-satunya X kepercayaan diri yang bisa kita tunjukkan, katakanlah itu bisa 10 juta node per detik setelah 10 hari kita bisa menghitung 10 * 86400 * 10 ^ 8 node = 8,64 * 10 ^ 13 node. Jika kita mengasumsikan posisi rata-rata di 20 langkah pertama memiliki sekitar 15 langkah hukum (lebih rendah karena awal memiliki jauh lebih sedikit dan mungkin bahkan sedikit lebih rendah karena pemangkasan alpha-beta) yang hanya sekitar 12 langkah setelah 10 hari (posisi hanya setelah langkah 6 ) jadi Anda melihat mengapa masalah ini jelek. Namun saya pikir permainan praktis mungkin menunjukkan nilai yang jauh, jauh, jauh lebih tinggi. SAYA'

Mari kita mengabaikan catur yang kemungkinan besar seri. Kita harus mempertimbangkan aturan main catur yang sedang dimainkan. Di hampir setiap situasi turnamen ada aturan 50 langkah yang berlaku yang menyatakan bahwa permainan adalah seri jika "50 gerakan terakhir berturut-turut telah dilakukan oleh setiap pemain tanpa gerakan pion dan tanpa penangkapan bagian apa pun."

Jadi ini berarti kita bisa memiliki 49,5 gerakan per tangkapan atau pion. Setiap pion dapat bergerak hingga 6 kali dan ada 15 buah yang dapat ditangkap untuk masing-masing sisi (meskipun satu potong harus tetap untuk memberikan skakmat) sehingga kami dapat menempatkan batas atas pada jumlah gerakan.

Ini bekerja untuk 49,5 * (8 * 2 * 6 (gerakan gadai) + 29) = 6187,5 Jadi ini berarti bahwa JIKA catur adalah kemenangan yang dipaksakan untuk putih dengan mematuhi aturan 50 langkah maka ia dalam paling banyak 6188 langkah untuk putih . Saya mungkin bisa menurunkan ini sedikit tanpa melakukan terlalu banyak dengan mengatakan bahwa semua pasangan sepotong K + v K pasangan yang dipaksa (hanya Benteng di Queen) dapat dilakukan secara substansial kurang dari 50 gerakan (saya pikir sekitar 16 bermain-main dengan Nalimov untuk beberapa kasus "sulit". Jadi saya pikir kita mungkin bisa mengurangi 34 langkah dari jumlah itu dengan penuh percaya diri untuk 6134!

Oleh karena itu: Jika catur adalah kemenangan yang dipaksakan untuk putih dengan mengikuti aturan 50 move maka paling banyak ada 6134 gerakan.