Apakah jumlah kemungkinan permainan catur tidak terbatas?

16

Pertanyaan ini agak terkait dengan Bisakah jumlah total kemungkinan menang / seri / kalah dihitung? , tetapi sedikit berbeda.

Ada episode acara TV baru-baru ini yang mengklaim bahwa "ada lebih banyak permainan catur yang mungkin terjadi daripada atom di alam semesta". Mereka melanjutkan bahwa "setiap gerakan yang mungkin mewakili permainan yang berbeda, alam semesta yang berbeda [..]"; "Pada langkah kedua ada 72084 kemungkinan game, pada game ketiga - 9 juta, game keempat --- 318 juta".

Jadi, apakah jumlah total permainan catur tidak terbatas, untuk semua tujuan praktis mengingat keterbatasan manusia dan teknologi? Dan apakah angka-angka di atas benar-benar bertahan sampai pengawasan? (mis. Berapa perkiraan game yang mungkin dilakukan, katakanlah, langkah ke-10?)

Anehnya, Wikipedia tampaknya menyiratkan bahwa jumlah game dapat diperkirakan:

jumlah game yang dimungkinkan [in Go] sangat besar (10 761 dibandingkan, misalnya, dengan 10 120 kemungkinan dalam catur)

theory statistics game-complexity Landroni
sumber
3
Jika Anda mendefinisikan "gim" sebagai sejarah gim, setiap gim yang memungkinkan pengulangan memiliki gim yang tak terbatas. Snakes and Ladders memiliki "permainan" yang tak terbatas. Jika Anda tertarik dengan kerumitan dalam menyelesaikan permainan, abaikan sejarah pergerakan dan lihat jumlah kemungkinan status yang bisa dicapai oleh dewan.
Schwern
3
Catatan: orang-orang ilmu komputer akan segera menolak "tidak terbatas, untuk semua tujuan praktis." Sangat berbahaya untuk "mengumpulkan" hingga tak terbatas. Secara umum, ketika mereka membuat kesalahan dengan melakukan itu, seseorang dengan cepat memecah algoritme mereka dengan menunjukkan bahwa itu sebenarnya tidak terbatas yang mereka hadapi. Dalam enkripsi, bukan hal yang mustahil untuk memiliki algoritma yang tampaknya "tidak bisa dipecahkan hingga panasnya kematian alam semesta" yang rusak karena beberapa trik yang mengurangi ukuran masalah sebesar 10 ^ 80 atau lebih
Cort Ammon - Reinstate Monica
2
Jika saya tidak salah, Anda merujuk pada acara TV yang menarik, bukan? Apa yang mereka maksudkan adalah dengan memperkirakan langkah selanjutnya yang mungkin Anda harus buat pohon keputusan untuk menghitung semua kemungkinan. Ketika Harold mengacu pada 'langkah kedua', ia berarti melihat dua gerakan ke depan (milik Anda dan lawan; dalam ilmu komputer ini adalah tingkat kedalaman pohon ke-2). Jadi tanpa melakukan perhitungan saya yakin itu mungkin benar. Setidaknya itu pasti jumlah yang besar.
CMPSoares
Anda mungkin menemukan video ini menarik. youtu.be/Km024eldY1A
Jivan Scarano

Jawaban:

17

Jumlah maksimum gerakan dalam permainan catur tidak terbatas, itu 11797 lapisan = 5.689 bergerak setengah. Ini karena aturan lima puluh langkah.

Jadi tidak, jumlah permainan catur yang mungkin tidak terbatas.

Jumlah maksimum gerakan hukum dalam posisi adalah 218. Jadi batas atas kasar untuk jumlah permainan catur yang mungkin adalah 218 ^ 11797 = 10 ^ 27586

Tunggu, sebenarnya setelah lima puluh gerakan tanpa gerakan menangkap atau menggadaikan, pemain juga dapat terus bermain tanpa mengklaim hasil imbang ...

Pasal 9.3 UU FIDE Catur menyatakan bahwa:

9.3

Permainan ditarik, berdasarkan klaim yang benar oleh pemain yang pindah, jika:

  • ia menulis langkahnya, yang tidak dapat diubah, pada lembar skornya dan menyatakan kepada wasit niatnya untuk melakukan gerakan ini yang akan menghasilkan 50 gerakan terakhir oleh setiap pemain yang dibuat tanpa gerakan pion dan tanpa tangkapan apa pun, atau
  • 50 gerakan terakhir oleh masing-masing playerhave telah selesai tanpa gerakan bidak dan tanpa tangkapan.

Jadi saya kira jumlah permainan catur yang mungkin bisa dianggap tidak terbatas maka ...

Tetapi jika Anda tidak tertarik dengan angka-angka teoritis sebelumnya:
Jumlah rata-rata gerakan hukum dalam suatu posisi adalah sekitar 35, dan panjang rata-rata permainan catur adalah sekitar 40 gerakan = 80 lapisan, jadi perkiraan jumlah " permainan catur "rasional adalah 35 ^ 80 = 10 ^ 123
Adapun jumlah posisi hukum, itu berada di antara 10 ^ 40 dan 10 ^ 50.

Takdir
sumber
Masalah pengulangan dapat diselesaikan dengan mengubah pertanyaan menjadi bukan tentang gerakan tetapi tentang negara. Berapa banyak kemungkinan konfigurasi papan Catur yang memungkinkan? Itulah pertanyaan menarik dari sudut pandang kompleksitas. Pengulangan tidak masalah, itu mengulangi keadaan yang sama. Banyak negara bagian yang tidak dapat dihubungi karena mereka akan melakukan lebih dari 50 gerakan, atau tidak mungkin karena pembatasan pergerakan potongan (terutama pion).
Schwern
3
@Tony Ennis: Saya mengedit. Namun sebenarnya tidak, aturan 50 langkah tidak menjamin permainan akan berakhir, karena para pemain juga dapat memilih untuk tidak mengklaim hasil seri.
Nasib
2
Bisakah Anda mengedit jawaban Anda sehingga dibaca sebagai jawaban, bukan diskusi dengan diri Anda sendiri? Anda mulai dengan membuat klaim yang salah bahwa jumlah game terbatas, lalu koreksi diri Anda sendiri. Pertama-tama buat klaim yang benar; jika Anda ingin mengatakan "Tetapi jika para pemain selalu mengambil hasil imbang segera setelah mereka berhak untuk itu ..." tidak apa-apa.
David Richerby
11
Sebenarnya, pada Juli tahun lalu, ada aturan 75 langkah yang adalah wajib. Jadi aturan 50 move tidak menjamin berakhirnya game, tetapi aturan 75 move tidak, meskipun game terpanjang meningkat menjadi 17.697 lapisan. Diberikan faktor percabangan rata-rata 35, orang mungkin memperkirakan jumlah permainan yang mungkin pada 35 ^ 17697, atau sekitar 10 ^ 27000.
Deedlit
1
Bahkan jika kita mengabaikan aturan 50-langkah dan 75-langkah, jika para pemain bermain tanpa mengklaim hasil imbang, pada beberapa titik pengulangan tiga kali lipat harus terjadi. Saya tidak tahu apakah mengambil hasil imbang di sini diperlukan, tetapi saya akan mempertimbangkan sejumlah game berbeda dengan kemungkinan tak terbatas untuk mengulang sejumlah game yang mungkin, untuk keperluan pertanyaan ini.
11684
6

T1: Ya. Jumlah total permainan catur dapat dianggap tak terbatas untuk semua tujuan praktis. Kami tidak memiliki teknologi untuk memaksa selama 13 gerakan pertama dari posisi awal.

T2: Angka aktual hingga kedalaman 13 diketahui. Jumlah pasti posisi yang memungkinkan untuk gerakan ke-10 adalah 69.352.859.712.417. Baca artikel Wikipedia ini untuk lebih jelasnya.

Ada upaya untuk kedalaman 14 tetapi sejauh ini perhitungan setelah berbulan-bulan masih berjalan.

Halo Dunia
sumber
Ya, angka yang mengesankan. Lucu kita tidak bisa menghitung di atas 14 gerakan ... Saya ingin tahu berapa banyak gerakan yang dapat dihitung untuk Go ... Tiga? :)
landroni
Tidak perlu "dianggap tak terbatas untuk semua tujuan praktis" karena sebenarnya tak terbatas. Meskipun aturan pengulangan 50 langkah dan tiga kali lipat memungkinkan salah satu pemain untuk mengklaim hasil seri, mereka tidak secara otomatis mengakhiri permainan.
David Richerby
1
@landroni Go mungkin lebih mudah dihitung daripada catur. Ada 361 game satu langkah, 361 * 360 dua game, dan 361 * 360 * 359 tiga game. Jumlah empat game bergerak tergantung pada apakah bunuh diri diizinkan. Jika ya, maka akan ada 358 kemungkinan gerakan keempat, kecuali dua batu pertama hitam mengambil batu pertama putih di sudut, dalam hal ini ada 359. Jadi, 361 * 360 * 359 * 358 + 8 empat game bergerak. Jika bunuh diri tidak diperbolehkan, maka ada 361 * 360 * 359 * 358 - 8 * 358 empat game bergerak. Anda dapat melanjutkan dengan cara ini, memisahkan ke dalam kasus - 14 gerakan mungkin bisa dilakukan dengan upaya komputer.
Deedlit
4
Catatan bahwa ini adalah 13 setengah -Memindahkan, atau lapis - tujuh bergerak dengan putih dan enam dengan warna hitam.
RemcoGerlich
2
@ DavidVicherby: aturan 75 move (baru sejak Juli 2014) adalah wajib.
RemcoGerlich
2

Pada titik tertentu Anda akan kehabisan kombinasi. Jadi jawabannya pada dasarnya tidak.

Nuach
sumber
1

Satu argumen sederhana bahwa jumlah permainan catur terbatas adalah sebagai berikut.

Karena aturan 50 langkah, setiap 50 langkah berikutnya dari permainan catur yang diberikan akan berisi setidaknya satu tangkapan atau langkah gadai. Karena ada banyak potongan di papan tulis, dan karena pion hanya bisa bergerak berkali-kali selama permainan, jumlah gerakan dalam permainan catur memiliki batas yang terbatas. Karena dalam setiap gerakan, hanya ada banyak kemungkinan, jumlah semua permainan terbatas.

Perhatikan bahwa argumen ini hampir tidak berguna jika seseorang ingin mendapatkan perkiraan jumlah game yang mungkin. Jika tidak ada yang lain, satu-satunya hal yang saya gunakan di atas adalah aturan 50-langkah dan bagaimana potongan bergerak, sehingga pengulangan diperbolehkan (maks. 50 kali lipat pengulangan, tentu saja). Karenanya, argumennya hanya teoretis, tidak praktis.

Zvonimir
sumber
0

Aturan 50 langkah termasuk 'atas klaim yang benar': Tidak ada klaim, tidak ada implementasi aturan. Hal yang sama berlaku untuk pengulangan. Ergo, tak terbatas.

Tanpa jumlah maksimum langkah wajib, tentu saja.

x1797n7917
sumber
4
Tidak lagi. Hukum Catur FIDE yang baru memiliki aturan 75 langkah dengan pengundian otomatis. Lihat fide.com/fide/handbook.html?id=171&view=article $ 9,6.
Dag Oskar Madsen
0

Tentang memahami undang-undang FIDE-Pertama-tama hukum ini digunakan untuk permainan turnamen- jadi dengan informasi tersebut apakah Anda mengerti bagaimana hukum FIDE tidak berhubungan dengan dua teman yang memutuskan untuk bermain? Untuk dua teman, yang mengurangi menjadi dua raja saja, mereka dapat saling mengejar di papan dalam jumlah yang tidak terbatas jika mereka mau. (Masuk akal-tidak benar-benar, mungkin-ya)

Pada hukum FIDE 9.2 - 50 gerakan berurutan harus dilakukan di mana tidak ada pion yang dipindahkan dan tidak ada tangkapan yang dilakukan. Ini jelas tidak akan menjadi "permainan 50-langkah" (mis. 1.e4 akan berarti 50 gerakan berurutan lainnya tanpa pion digerakkan atau tangkapan dibuat)

Pada hukum FIDE 9.6 - 75 gerakan berurutan ... Alasan yang sama bahwa ini bukan permainan 75 gerakan.

Salah satu bukti pertama dari game yang direkam adalah 14 gerakan berturut-turut (1. e4 b6 2. d4 Bb7 3. Bd3 f5 4. ef5 Bg2 5. Qh5 g6 6. fg6 Nf6 7. gh7 Nh5) Meskipun ke-15 adalah skakmat- jika pemenang memutuskan untuk tidak melakukan skakmat, ia masih akan membutuhkan 75 gerakan lagi untuk menyatakan undian dalam hukum FIDE 9.6 (dengan 12 pion tersisa di papan - saya ragu itu akan terjadi dalam 75 gerakan)

Dengan hormat, CFC

Clayton Currier
sumber
2
Nah, jika dua teman yang tidak peduli dengan aturan resmi suka memainkan permainan omong kosong dan menyebutnya catur, mereka bisa! Tetapi haruskah kita menyebutnya catur untuk tujuan situs ini? Posisi dengan hanya dua raja adalah undian langsung.
RemcoGerlich
0

Karena jawaban lain di sini mengarah pada pengulangan atau serupa, saya ingin mengubah pertanyaan Anda menjadi, "Apakah jumlah POSISI catur yang mungkin tak terbatas. Jawabannya adalah" Tidak. "Totalnya sangat besar dan diperkirakan sekitar 10 pangkat ke-120. Jumlah total atom di alam semesta diperkirakan hanya 10 pangkat 80. Wow!

Angka 10 pangkat 134 yang diberikan oleh responden sebelumnya mungkin benar.

Gim Cina "Go" bahkan lebih bervariasi daripada catur (tetapi membosankan jika dibandingkan karena catur memiliki bidak dengan kemampuan yang berbeda, sedangkan di Go semua bidak sama).

markbolles44
sumber
0

Saya mungkin melihat ini terlalu sederhana tetapi menurut saya jumlahnya harus terbatas. Jika kita melihat papan dan potongan-potongan daripada permainan catur dan menghitung jumlah variasi yang mungkin kita dapat memperoleh jawaban yang terbatas. Pikiran luar biasa besar tapi terbatas. Mengingat tidak semua kombinasi dimungkinkan dalam permainan catur, jumlah kombinasi dalam permainan catur harus kurang dari angka terbatas ini dan oleh karena itu angka terbatas itu sendiri.

Justin
sumber