Jika ada strategi kemenangan, apakah itu untuk White?

13

Kita tidak tahu, mengingat dua pemain sempurna Putih dan Hitam, apakah permainan akan selalu berakhir imbang, atau harus berakhir dengan kemenangan (baik Hitam atau Putih).

Namun, dapatkah kita membuktikan bahwa jika ada strategi kemenangan, maka itu untuk White? Dengan kata lain, dapatkah kita membuktikan bahwa Black harus kalah atau seri?

theory Randomblue
sumber
1
Tidak, kami tidak dapat membuktikan bahwa hitam harus kalah atau seri. Mungkin dengan komputer kuantum kita akan dapat ...
Tony Ennis
1
Di samping itu, seorang grandmaster terkenal Inggris pernah bercanda mengatakan bahwa pada posisi awal kedua belah pihak berada dalam zugzwang bersama. Oleh karena itu, White adalah yang pertama untuk merusak posisinya sehingga catur dipecahkan untuk Black's :)
Andrew Ng
Saya pikir Anda harus menentukan bahwa Anda mengacu pada "strategi" dalam arti permainan-teoretis daripada rasa "catur"
David

Jawaban:

8

Jika ada bukti seperti itu, tidak ada yang menemukannya, dan saya sangat meragukan bukti tersebut ada (sulit untuk membayangkan strategi "dijamin-menggambar" yang dapat dibuktikan secara matematis sebagai Putih). Seseorang tentu berharap White memiliki keuntungan jika ada yang melakukannya, tetapi ada beberapa kelemahan untuk menjadi yang pertama juga (Anda harus mengungkapkan informasi sebelum lawan Anda), sehingga secara teoritis mungkin bahwa kerugian lebih besar daripada keuntungannya. Yang mengatakan, kemungkinan itu menjadi kasus tampaknya sangat kecil.

dfan
sumber
3
Terima kasih. Apakah anda memiliki sumbernya?
Randomblue
1
Saya tidak punya sumber untuk pernyataan bahwa tidak ada yang menemukan bukti seperti itu selain bahwa sangat kecil kemungkinannya bahwa saya tidak akan pernah mendengarnya (selain alasan bahwa bukti seperti itu sangat tidak mungkin ada apakah saya pernah mendengar atau tidak).
dfan
Untuk sumber: artikel "Memecahkan Catur" Wikipedia . Berikut ini kutipan yang relevan: No complete solution for chess in either of the two senses is known, nor is it expected that chess will be solved in the near future. There is disagreement on whether the current exponential growth of computing power will continue long enough to someday allow for solving it by "brute force", i.e. by checking all possibilities. Meskipun ini berkaitan dengan solusi lengkap, saya cukup yakin mereka akan menyebutkan sebagian.
Daniel B
4
Ya, tentu saja kami tahu bahwa salah satu pemain memiliki strategi menang / menggambar, tetapi kami tidak tahu apakah pemain itu Putih atau Hitam. Pertanyaannya adalah "Bisakah kita membuktikan bahwa jika ada strategi kemenangan, maka itu untuk White?", Dan kita tidak memiliki bukti itu.
dfan
4
White mengungkapkan informasi tentang apa yang dia lakukan. Hitam dapat mengambil tindakan berdasarkan informasi itu. Ada banyak permainan informasi sempurna di mana pemain kedua menang dengan permainan terbaik karena alasan ini. Contoh paling sepele adalah permainan Gunting Kertas Batu di mana para pemain mengungkapkan pilihan mereka secara bergantian, bukan secara bersamaan.
dfan
4

Secara teori dapat dibuktikan, tetapi tidak dengan teknologi saat ini.

Jika Anda mengambil pendekatan brute force, ada beberapa kesulitan karena jumlah posisi.

Dalam analisis Nomor Shannon , disarankan bahwa kompleksitas pohon permainan setidaknya 10 ^ 123 untuk game dengan panjang maksimum 80 gerakan. Mari kita asumsikan bahwa 10 ^ 123 untuk keperluan diskusi ini.

10 ^ 81 = Perkiraan jumlah atom di alam semesta

10 ^ 12 = Operasi per detik dari inti prosesor terahertz (prosesor Anda mungkin berjalan sekitar 1/300 dari kecepatan ini.)

10 ^ 7 = Bulat-off detik per tahun

10 ^ 12 = 1 triliun tahun

Mari kita juga berasumsi bahwa prosesor kami dapat mengevaluasi posisi catur hanya dalam 1 siklus prosesor.

Jadi, mari kita buat setiap atom di alam semesta beroperasi sebagai inti prosesor terahertz selama 1 triliun tahun.

Bisakah kita mengevaluasi setiap posisi untuk permainan panjang 80-maks?

Tidak.

10 ^ 81 x 10 ^ 12 x 10 ^ 7 x 10 ^ 12 = 10 ^ 112

Kami gagal mencapai hanya 0,0000000001% yang lengkap dengan perhitungan.

Dengan pemangkasan tingkat lanjut (membuang garis buruk dan turunannya), teknologi yang lebih baik, dan beberapa pemrograman yang cerdik ... mungkin kita akan melihat 40-max game diselesaikan dalam hidup kita! Kami juga dapat memangkas posisi yang telah kami lihat sebelumnya (kami dapat tiba di sana melalui transposisi), tetapi perlu diingat bahwa setidaknya diperlukan siklus CPU untuk menentukan bahwa kami telah mengevaluasi posisi sebelumnya!

Namun, ini akan membantu Anda melihat mengapa hal itu begitu jauh dari jangkauan saat ini.

Referensi

Brian Webster
sumber
Pertanyaannya bukan menanyakan apakah catur dapat dipecahkan secara efektif, tetapi apakah kita dapat membuktikan apakah hasil (yang tidak dapat diakses oleh kita) akan memiliki beberapa karakteristik tertentu (Hitam tidak memiliki strategi kemenangan).
dfan
1
Ini memang menjawab pertanyaan dalam konteks brute force. Metode paling sederhana untuk membuktikan strategi kemenangan adalah menganalisis setiap posisi. Saya memberikan konteks mengapa hal ini tidak memungkinkan mengingat teknologi saat ini.
Brian Webster
3

Secara teori, catur dapat "diselesaikan", karena ini adalah permainan "terbatas" dengan "informasi sempurna". Lebih tepatnya, ada strategi sedemikian rupa sehingga satu pemain memiliki kemenangan dijamin, atau kedua pemain memiliki hasil imbang dijamin bermain sempurna. Berikut ini adalah artikel teknis tentang konsep-konsep Game Theory dasar (baik, dasar bagi mereka yang akrab dengan ekonomi / matematika) bagi mereka yang tertarik dengan spesifik. Intinya, setiap game yang memiliki "informasi sempurna",yaitu setiap pemain dapat melihat semua bagian, dan menyadari semua langkah hukum dari bagian tersebut di semua titik selama pertandingan (contoh tandingan dari permainan informasi yang sempurna akan menjadi permainan kartu, di mana Anda tidak dapat melihat lawan Anda tangan), ** sejumlah pemain terbatas dan sejumlah gerakan legal terbatas **, yaitu permainan tidak berjalan tanpa batas waktu, maka ia memiliki strategi menang atau menggambar yang dijamin untuk salah satu pemain.

Dalam praktiknya, kami tidak memiliki teknologi atau kecerdasan (ok, mungkin jika semua pikiran catur terbaik saat ini berkolaborasi dalam menemukan strategi, kami mungkin memiliki kecerdasan yang cukup. MAYBE.) Dan waktu untuk melakukannya secara manual.

Untuk menjawab pertanyaan Anda: Ya, ada strategi menang (atau menggambar). Tidak, kami tidak tahu apakah itu putih atau hitam.

Ya, catur ditakdirkan untuk dipecahkan suatu hari nanti. Tetapi kita tidak akan memiliki teknologi (menurut saya satu-satunya cara untuk melakukannya) untuk itu selama beberapa dekade (semoga bahkan berabad-abad) yang akan datang.

chubbycantorset
sumber
3
Bagian pertama tersirat pada pertanyaan saya.
Randomblue
Saya sudah membaca artikel itu. Sepertinya saya Backwards Induction (Teorema Zermelo) tampaknya hampir intuitif ketika dijuluki "Permainan catur harus selalu berakhir, sehingga memberikan pandangan ke depan yang cukup, baik pemain 1 atau pemain 2 harus memiliki strategi pemaksaan."
ldog
Meskipun tentu saja itu sama sekali tidak memberikan wawasan tentang game itu sendiri! Jika Anda membayangkan seorang pemain pemula bermain melawan mesin catur terbaik di dunia, pemain pemula akan selalu menang atau seri asalkan ia memiliki gerakan membatalkan yang tidak terbatas.
ldog
Hanya komentar tentang "catur pasti akan terpecahkan suatu hari nanti" - ini tentu saja benar jika hukum Moore (pada dasarnya, pertumbuhan kekuatan komputasi eksponensial) berlaku tanpa batas. Pada tingkat saat ini, ini akan menyebabkan catur layak untuk diselesaikan sekitar 250 tahun dari sekarang. Bahkan ekstrapolasi terliar (diskon teori singularitas) memiliki hukum ini selama itu (misalnya Intel mengharapkan hukum untuk mendatar sebelum 2020, karena tunneling kuantum). Saya juga harus bertanya-tanya seperti apa peradaban pasca-manusia yang akan memiliki kekuatan pemrosesan seperti itu, hanya untuk mengubahnya menjadi pemecahan catur :)
Daniel B
1
Tidak. Bahkan dengan pikiran-pikiran itu yang bekerja bersama, kita tidak akan
David
0

Menurut pendapat saya, saya pikir strategi kemenangan ada dalam pikiran pemain. Karena langkah Anda selanjutnya akan tergantung pada gerakan lawan Anda.

pengguna17445
sumber
Selamat Datang di Pertukaran Catur Stack! Perhatikan bahwa kami umumnya lebih suka pendapat yang didukung dengan bukti nyata; kami adalah situs tanya jawab yang objektif dan bukan forum diskusi. Silakan luangkan waktu untuk mengikuti tur ini .
Glorfindel
0

Sangat tidak mungkin bahwa hitam dapat memiliki kemenangan yang dipaksakan karena setiap garis yang ditunjukkan sebagai menang untuk hitam dapat dimainkan sebagai putih dengan tempo naik. Misalnya, jika 1.e4, c5 adalah kemenangan yang dipaksakan untuk hitam, maka putih dapat memainkan 1.c4 menuju garis yang sama terbalik.

Savage47
sumber
-2

Putih memiliki sedikit keuntungan karena lebih dulu. Kita berbicara tentang 2% lebih banyak kemenangan di tingkat grandmaster. Keuntungan kecil ini mulai naik seiring permainan berlangsung. Diambil secara ekstrim, dalam permainan yang dimainkan dengan sempurna, mereka mungkin akan menggambar.

Tyler Langan
sumber
-5

White akan mendapat keuntungan dari membuka permainan, tetapi saya akan ragu apakah ada strategi kemenangan seperti yang Anda sarankan.

Thang Do
sumber
4
Silakan baca kembali pertanyaannya.
Randomblue
@Randomblue Anda menggunakan kata "strategi" di forum catur, jadi orang menganggap Anda menggunakannya dengan makna caturnya, alih-alih makna teori permainannya
David