Apakah catur merupakan permainan yang diselesaikan?

24

Catur adalah permainan zero-sum dari keputusan terbatas. Jumlah gerakan yang dimungkinkan pada titik tertentu, dan jumlah kemungkinan status dewan, semuanya terbatas.

Tic-Tac-Toe, adalah salah satu contoh termudah dari permainan yang diselesaikan. Saya tidak ingat sudah berapa tahun sejak saya terakhir kali kalah dalam pertandingan Tic-Tac-Toe. Apakah ada "strategi optimal" seperti itu untuk catur?

Apakah ada strategi yang akan menjamin pemain akan meraih kemenangan atau, paling buruk, hasil imbang?

Jika ada, tolong beri penjelasan.

Tobi Alafin
sumber

Jawaban:

26

Karena pengamatan yang Anda lakukan, bahwa pohon jalur permainan yang mungkin untuk catur terbatas, catur memang bisa dipastikan persis sama dengan tic-tac-toe. Jadi ada strategi optimal untuk catur; Namun, tidak ada yang tahu apa itu. Sementara tic-tac-toe diselesaikan berkat ruang permainan yang sangat kecil, catur tidak bisa diselesaikan karena ruang permainan yang mungkin jauh melebihi apa yang bisa ditangani oleh teknologi komputasi saat ini.

Seperti disebutkan dalam jawaban lain, tabulasi endgame memperlihatkan permainan optimal untuk semua posisi dengan jumlah potongan yang terbatas. Jadi dalam pengaturan itu, kami memiliki solusi yang eksplisit dan konkrit seperti solusi untuk tic-tac-toe. Tetapi penting untuk dicatat bahwa sementara seseorang dapat dengan mudah mengajar / mengingat strategi optimal untuk tic-tac-toe dan dengan cepat menjadi pemain tic-tac-toe yang sempurna tanpa bantuan, jumlah informasi di belakang, katakanlah, 7-bagian tabulasi Lomonosov , adalah 140 terabyte. Tidak ada deskripsi ringkas tentang strategi 7-man optimal yang bisa dipelajari / diingat dan kemudian dimainkan dengan sempurna tanpa bantuan.

ETD
sumber
5
Mungkin membantu untuk menyebutkan bahwa ada kurangnya konsensus mengenai apakah posisi awal adalah kemenangan paksa untuk putih, imbang, atau bahkan (oleh beberapa zugzwang yang kompleks rumit) kemenangan paksa untuk hitam. Ini berarti bahwa kita bahkan tidak tahu apakah memainkan strategi optimal dapat menjamin hasil seri.
Kevin
5
Tidak ada "kurangnya konsensus". Konsensus yang luar biasa adalah "draw": en.wikipedia.org/wiki/First-move_ Advantage_in_chess .
Jeff Y
1
@ Jeff JEFFY Mungkin ada beberapa perasaan konsensus, tetapi kita tidak bisa tahu sampai kita memiliki 32-laki tablebase.
11684
5
@ Jeff, saya berpikir bahwa alih-alih ungkapan yang mengganggu tentang "kurangnya konsensus," Kevin benar-benar bermaksud untuk hanya berfokus pada "kurangnya bukti". Saya pikir kita semua sepakat bahwa, tidak peduli ada konsensus pendapat yang luar biasa yang ada (dan saya setuju dengan Anda bahwa sebagian besar cenderung percaya permainan adalah hasil imbang teoretis), dan tidak peduli bukti empiris apa pun dari banyak permainan yang dimainkan oleh manusia dan / atau mesin (keduanya bermain sub-optimal), tidak ada yang mengesampingkan dengan pasti setiap kemungkinan teoritis untuk catur (menang untuk putih / draw / menang untuk hitam). .....
ETD
5
Singkatnya, saya pikir JeffY benar sekali bahwa ada konsensus kepercayaan yang cukup besar bahwa catur adalah hasil undian teoretis, dan itu sangat konsisten dengan poin akurat dari Kevin dan 11684 bahwa kita masih tidak tahu apakah catur adalah undian teoretis atau tidak. Saya pikir Anda semua mungkin melihat mata-ke-mata lebih dari komentar di atas menyarankan pada pandangan pertama.
ETD
8

Permainan catur mungkin terbatas tetapi jumlah game yang mungkin ada di luar bayangan.

Tidak ada urutan gerakan yang diketahui yang menjamin kemenangan atau hasil imbang.

Tony Ennis
sumber
8

Catur belum terpecahkan dan tidak akan ada dalam dekade mendatang (kecuali kemajuan komputasi konyol yang melibatkan komputasi kuantum atau perubahan drastis semacam itu).

Anda dapat menghitung di kepala Anda untuk langkah pertama: Putih memiliki 20 opsi dan hitam memiliki 20 respons; kami sudah memiliki 400 kemungkinan posisi. Jumlah ini tumbuh sangat cepat, jumlah posisi yang memungkinkan untuk permainan 80 bergerak sangat besar.

Juga, jika catur diselesaikan, turnamen catur dan kejuaraan pada dasarnya adalah latihan menghafal, menjadikannya sia-sia. (EDIT: ini agak berlebihan, lihat komentar.)

Saat ini, catur diselesaikan untuk posisi apa pun dengan enamtujuh potong (termasuk raja). Perkiraan terbaru yang saya dengar7-laki-laki8-men tablebase ada di suatu tempat di tahun 2020-an, dan tentu saja waktu yang dibutuhkan untuk bagian tambahan tumbuh secara eksponensial. Saya tidak berharap untuk melihat catur mendekati diselesaikan dalam hidup saya (sekali lagi, kecuali kemajuan komputasi yang benar-benar luar biasa). (Kredit untuk koreksi ke Tony Ennis.)

11684
sumber
Sudah ada tabulasi 7 orang.
Tony Ennis
Sangat? Dimana? Lalu saya salah ingat, silakan ganti 6 dengan 7 dan 7 dengan 8. @TonyEnnis
11684
3
Per komentar ETD, bahkan jika catur diselesaikan, manusia tidak akan bisa menghafal solusinya. Jadi komentar tentang "sia-sia" tidak benar.
Jeff Y
3
@ 11684 Bagaimana bisa begitu? Apakah memiliki 7 buah tablebase secara drastis mengubah sifat permainan endgame di turnamen? Saya tidak melihatnya.
Jeff Y
1
@ 11684 Semua benar. Tapi bagaimana itu akan mengubah turnamen ? Saya dapat melihat bahwa itu mungkin membuka lebih banyak garis pembuka (sebagai non-pecundang), meskipun saya tidak bisa melihat harus mengingat sedikit pun untuk memainkannya. Dan saya dapat melihat bahwa itu akan mengubah postmortem game tentunya. Tapi saya hanya tidak melihat permainan manusia-vs-manusia terpengaruh secara signifikan, sama seperti endgame 7-piece manusia-vs-manusia tidak terpengaruh oleh kehadiran tablebase 7-piece.
Jeff Y
4

Poin lain adalah bahwa permainan catur terbatas tetapi hanya dengan aturan 75 langkah (permainan akan diambil jika tidak ada tangkapan atau pion bergerak untuk 75 gerakan). Sebelumnya, ini aturan dengan pengundian tiga kali berturut-turut dari posisi, yang disebut 'Peraturan Jerman', memungkinkan jumlah permainan yang tak terbatas seperti yang ditunjukkan oleh Max Euwe .

Sylvain Julmy
sumber
3
Dengan aturan tiga kali posisi yang sama permainan akan jelas terbatas. Bayangkan saja ada sejumlah posisi yang memungkinkan dan setiap posisi dapat diulang paling banyak dua kali. Artikel yang ditautkan menunjukkan bahwa permainan dapat menjadi tak terbatas di bawah "aturan Jerman", yang meminta urutan yang sama dimainkan dari posisi yang sama tiga kali berturut
sharcashmo
Terima kasih, saya mengacaukan penjelasan saya, ini tiga kali urutan gerakan yang sama :).
Sylvain Julmy
3

Kita tahu bahwa strategi optimal ada karena ketika dalam permainan ada jumlah pemain yang terbatas dan jumlah strategi yang terbatas untuk setiap pemain, seseorang dapat menunjukkan bahwa Nash equilibra ada (sehingga Anda memainkan respons optimal Anda ke optimal pemain lain optimal respon dan sebaliknya).

Masalahnya adalah bahwa bahkan jika kita tahu bahwa strategi seperti itu ada, kita tidak tahu persis strategi mana karena keterbatasan komputasi.

pengguna10321
sumber
3

Inilah jawaban yang awalnya saya tulis di /cstheory/6563/what-is-the-computational-complexity-of-solving-chess/38102#38102 .

Seorang pemain catur yang sempurna akan selalu memaksakan kemenangan ketika mereka bisa memaksa menang dan memaksakan hasil imbang saat mereka bisa memaksakan hasil imbang. Tentu saja, kapan pun mereka bisa memaksa menang, mereka juga bisa memaksakan hasil seri. Juga ketika salah satu pemain tidak bisa memaksakan kemenangan, pemain lain bisa memaksakan hasil seri. Catur tanpa aturan 50 move atau 3 kali lipat aturan pengulangan mungkin tidak sesulit yang Anda pikirkan. Dapat ditunjukkan bahwa menambahkan aturan pengulangan 3 kali lipat tidak membuat perbedaan apakah seorang pemain dapat memaksakan kemenangan atau hasil imbang. Jumlah cara yang mungkin dilakukan suatu game setelah n bergerak terus tumbuh secara eksponensial dengan n. Jumlah negara yang dapat terjadi setelah n bergerak di sisi lain tidak terus tumbuh secara eksponensial karena tidak dapat melebihi jumlah total negara yang mungkin yang dapat terjadi dalam permainan hukum. Menuruthttps://en.wikipedia.org/wiki/Game_complexity , ada sekitar 10 ^ 47 negara yang dapat terjadi dalam permainan catur legal.

Catur dapat diselesaikan sebagai berikut: ambil satu set negara yang dapat kita buktikan berisi semua negara yang dapat terjadi dalam permainan catur yang legal tanpa aturan pengulangan 3 kali lipat atau aturan 50 gerakan. Dua negara bagian yang berbeda dapat memiliki susunan bidak catur yang sama dan berbeda berdasarkan giliran siapa, apakah Anda memiliki hak untuk ditangkap secara langsung, dan apakah raja atau benteng yang diberikan hak untuk pernah benteng lagi. Selanjutnya, ambil semua negara di mana jumlah minimum gerakan putih dapat memaksa menang adalah 1 yang harus terjadi pada giliran putih. Selanjutnya ambil semua negara di mana jumlah minimum gerakan putih dapat memaksa menang adalah 2, yang berarti giliran hitam dan tidak peduli apa pun gerakan yang mereka buat, putih dapat memaksa menang dalam 1 langkah. Selanjutnya ambil semua negara di mana jumlah minimum gerakan putih dapat memaksa menang adalah 3, yang berarti putih memiliki langkah yang akan memberi mereka kemenangan paksa dalam 2 langkah tetapi tidak bisa memaksa kemenangan dalam 1 langkah. Selanjutnya ambil semua negara di mana jumlah minimum gerakan putih dapat memaksa menang adalah 4, yang berarti giliran hitam dan tidak peduli apa pun gerakannya, putih dapat memaksa menang dalam 3 gerakan tetapi putih saat ini tidak dapat memaksa menang dalam 2 bergerak. Setelah kita mencapai angka sedemikian sehingga tidak ada negara bagian di mana jumlah minimum gerakan putih dapat memaksa menang adalah angka itu, kita telah menemukan semua negara yang putih dapat memaksa menang. Kita dapat menemukan semua negara yang hitam dapat memaksa menang dengan cara yang sama. Semua status yang tersisa adalah status di mana kedua pemain dapat memaksakan hasil seri. yang berarti giliran hitam dan tidak peduli gerakan apa pun yang mereka lakukan, putih dapat memaksa kemenangan dalam 3 gerakan tetapi putih saat ini tidak dapat memaksa kemenangan dalam 2 gerakan. Setelah kita mencapai angka sedemikian sehingga tidak ada negara bagian di mana jumlah minimum gerakan putih dapat memaksa menang adalah angka itu, kita telah menemukan semua negara yang putih dapat memaksa menang. Kita dapat menemukan semua negara yang hitam dapat memaksa menang dengan cara yang sama. Semua status yang tersisa adalah status di mana kedua pemain dapat memaksakan hasil seri. yang berarti giliran hitam dan tidak peduli gerakan apa pun yang mereka lakukan, putih dapat memaksa kemenangan dalam 3 gerakan tetapi putih saat ini tidak dapat memaksa kemenangan dalam 2 gerakan. Setelah kita mencapai angka sedemikian sehingga tidak ada negara bagian di mana jumlah minimum gerakan putih dapat memaksa menang adalah angka itu, kita telah menemukan semua negara yang putih dapat memaksa menang. Kita dapat menemukan semua negara yang hitam dapat memaksa menang dengan cara yang sama. Semua status yang tersisa adalah status di mana kedua pemain dapat memaksakan hasil seri. Kita dapat menemukan semua negara bagian yang berkulit hitam dapat memaksakan kemenangan dengan cara yang sama. Semua status yang tersisa adalah status di mana kedua pemain dapat memaksakan hasil seri. Kita dapat menemukan semua negara bagian yang berkulit hitam dapat memaksakan kemenangan dengan cara yang sama. Semua status yang tersisa adalah status di mana kedua pemain dapat memaksakan hasil seri.

Karena ada sekitar 10 ^ 47 negara yang dapat terjadi dalam permainan catur legal, dibutuhkan lebih dari seumur hidup kita untuk menggunakan kekerasan untuk membangun komputer yang akan bermain catur dengan sempurna tidak peduli bagaimana lawannya bermain. Saya percaya itu belum terbukti bahwa tidak ada algoritma yang lebih pendek yang dapat memberi tahu Anda cara bermain dengan sempurna tidak peduli bagaimana lawan Anda bermain. Misalnya mungkin hanya sebagian kecil dari keadaan yang dapat terjadi dalam permainan hukum dapat terjadi dalam permainan di mana Anda memainkan cara algoritma memberitahu Anda untuk bermain sehingga algoritma bekerja meskipun hanya memberitahu Anda cara bermain dengan sempurna di semua negara yang dapat terjadi ketika Anda selalu mengikuti algoritme itu sejak awal permainan tetapi tidak di semua negara yang dapat terjadi dalam permainan hukum. Mungkin selain itu, Algoritma itu adalah algoritme kompleks yang untuk setiap keadaan yang dapat terjadi dalam permainan di mana Anda selalu mengikutinya, membutuhkan langkah yang jauh lebih sedikit untuk menghitung langkah optimal daripada jumlah negara yang dapat terjadi dalam permainan di mana Anda selalu mengikutinya. Menuruthttp://onlinelibrary.wiley.com/doi/10.1002/sres.2171/abstract, laboratorium pembelajaran evolusi berencana untuk memecahkan masalah yang kompleks. Mungkin suatu hari nanti, mereka akan menemukan strategi rumit untuk bermain catur dengan sempurna. Mungkin bahkan jika suatu algoritma yang sangat singkat dan mengambil langkah sangat sedikit untuk menghitung langkah optimal dalam keadaan apa pun yang dapat terjadi dalam permainan di mana Anda selalu mengikuti algoritma yang tidak ada, itu masih tidak menghentikan manusia untuk dapat untuk belajar cara bermain catur dengan sempurna. Mungkin manusia dapat terus memikirkan hal-hal dan mempertahankan apa yang mereka pikirkan, mencari lebih banyak hal dari apa yang sebelumnya mereka ketahui dan mempertahankannya dengan beberapa metode yang kompleks,

Mungkin bahkan lebih sederhana bagi pemain untuk memiliki strategi yang memastikan bahwa jika lawan mereka bermain dengan sempurna, mereka juga akan bermain dengan sempurna. Saya menduga kedua pemain memiliki hasil imbang paksa sejak awal pertandingan. Mungkin lebih mudah untuk memiliki strategi yang memaksa hasil imbang daripada strategi yang menjamin bahwa jika lawan memberi Anda kemenangan yang dipaksakan, Anda tidak akan kehilangan itu. Strategi yang memaksa hasil imbang juga merupakan strategi yang memastikan bahwa jika lawan bermain sempurna, Anda akan bermain dengan sempurna. Jika mereka bermain dengan sempurna, mereka tidak akan memberi Anda kemenangan paksa di tempat pertama sehingga Anda tidak akan kehilangan kemenangan paksa setelah mereka memberi Anda satu kemenangan.

Timotius
sumber
Tautan ke jawaban Anda tentang komputer-sains-SE sangat membantu. Namun, saya tidak yakin itu layak menyalin seluruh teksnya.
Evargalo
3

Pada tahun 1949, ilmuwan informasi, Shannon, membuat perkiraan bahwa dibutuhkan 10 ^ 90 tahun untuk menyelesaikan catur dengan komputer 1 MHz. Kekuatan komputer dan teknologi penyimpanan telah meningkat pesat sejak saat itu (hukum Moore), di mana daya komputer dan kapasitas penyimpanan berlipat ganda setiap tahun. Yang diperhitungkan, akan membutuhkan sekitar 300 tahun untuk menghasilkan komputer, yang akan 10 ^ 90 kali lebih kuat daripada mesin 1 MHz Shannon. Tidak ada batasan yang dapat dihindari dalam pengembangan komputer. Sebagai contoh Intel 4004 dibuat dengan teknologi 10 mikrometer photolithography sedangkan i9s saat ini dibuat dengan teknologi 14 nm. Ketika inti menjadi lebih kuat dan lebih kecil, mudah untuk memasukkan lebih banyak inti dalam ukuran fisik yang sama dari setengah tahun sebelumnya sebagai leluhur yang kuat. Dalam photolithography kita baru saja memasukkan kategori panjang gelombang ultraviolet di bawah 10 nm, tetapi ada panjang gelombang seperti sinar gamma, yang panjang gelombangnya 1 pikometer (10.000 lebih kecil). Atom hidrogen berukuran 0,1 nm, tetapi quark sekitar 200 kali lebih kecil dari 1 pikometer (yaitu 0,43 x 10 ^ −15 mm,https://www.theguardian.com/science/life-and-physics/2016/apr/07/how-big-is-a-quark )

Markku Litola
sumber
2

tidak

kita tidak bisa mengatakan siapa yang harus menang atau apakah itu seri

ada terlalu banyak kombinasi gerakan untuk mencoba menghitung jawabannya dengan teknologi saat ini dengan mencoba semua gerakan yang mungkin dan melihat hasilnya

maka kita harus memangkas mundur untuk melihat apa jawabannya dan apakah itu unik

dan jika kita bisa permainannya tidak akan menyenangkan lagi

joe sixpak
sumber
5
"Jika kita bisa permainannya tidak akan menyenangkan lagi" -> Orang-orang masih bermain connect-4 dan beberapa permainan yang diselesaikan lainnya.
Franck Dernoncourt
2

Pada awal abad ke-20, kepercayaan bahwa catur akan segera diselesaikan (disebut "undian kematian catur") sangat populer. Juara dunia J.-R. Capablanca cenderung percaya demikian. Game-game dari pertandingan Capablanca-Alekhine (hampir semua dalam Queen's Gambit Declined) juga mengkonfirmasi keyakinan ini. Lihat, misalnya: https://en.wikipedia.org/wiki/Capablanca_chess .

Revolusi bukaan modern (Raja India dll), maka revolusi kecerdasan buatan memberikan bukti intuitif bahwa memecahkan catur tidak begitu sederhana. Memang, permainan grandmaster saat ini sering dianalisis menggunakan program dan ini mengungkapkan garis bahwa pemain (bahkan yang terbaik) mengawasi selama permainan.

Ini dikatakan, "kekuatan komputasi absolut" memang bisa memecahkan catur dalam arti teori komputasi.

Alexandre Aksenov
sumber
1

Pikiran manusia jauh lebih kompleks daripada permainan tic-tac-toe. Jadi, Anda dapat menemukan strategi yang baik untuk memainkan game semacam itu.

Catur cukup berbeda. Catur adalah permainan heuristik.

Anda tidak dapat menempatkan seorang tentara yang bertanggung jawab di atas seorang jenderal. Pikiran seorang jenderal jauh lebih kompleks daripada pikiran seorang prajurit, dalam istilah militer. Itu hanya analogi.

Kompleksitas, itulah yang penting.

Anda harus lebih kompleks daripada catur. Itu tidak mungkin, tetapi Anda harus mencoba, Anda harus mencoba. Anda dapat mencapainya di beberapa level. Banyak faktor yang terlibat. Upaya itu penting, tetapi banyak dari kita melakukan upaya besar dengan hasil yang buruk. Tetapi ada orang yang melakukan sedikit upaya dan mencapai hasil yang sangat baik.

Alam tidak adil.

Tetapi jika Anda belajar catur pada usia lima tahun peluang Anda akan lebih baik daripada jika Anda belajar catur pada usia sepuluh tahun.

Tentu saja, jika Anda dulu tinggal berjam-jam di depan TV ketika Anda masih kecil, Anda menyia-nyiakan kecerdasan Anda.

Terakhir, tapi tidak kalah pentingnya, maaf tentang bahasa Inggris saya.

Fred
sumber
-1

2000-3000 lebih banyak lagi hingga permainan sempurna, sehingga mesin terbaik saat ini setidaknya dapat menggandakan kekuatan mereka. Catur sebenarnya lebih dekat ke masa kanak-kanak daripada ke tahap selanjutnya. Misalnya, mesin terbaik saat ini hanya akan menebak satu dari 5 gerakan pembukaan terbaik. Masih jauh untuk ditempuh.

Lyudmil Tsvetkov
sumber
3
Bagaimana Anda mendapatkan nomor itu?
Annatar
Berbagai tes telah dilakukan dan dilaporkan di forum Talkchess, forum catur paling canggih di Internet, tetapi pengamatan saya juga menunjukkan ke arah itu. Juga, dengan membandingkan evaluasi mesin 20 tahun yang lalu, sekarang, dan apa yang masih bisa diperbaiki di bidang itu.
Lyudmil Tsvetkov