Apakah ada algoritma yang sempurna untuk catur? [Tutup]

109

Baru-baru ini saya sedang berdiskusi dengan orang yang bukan pembuat kode tentang kemungkinan komputer catur. Saya tidak ahli dalam teori, tapi saya rasa saya cukup tahu.

Saya berpendapat bahwa tidak mungkin ada mesin Turing deterministik yang selalu menang atau buntu dalam catur. Saya pikir, bahkan jika Anda mencari seluruh ruang dari semua kombinasi gerakan player1 / 2, satu gerakan yang diputuskan oleh komputer di setiap langkah didasarkan pada heuristik. Berdasarkan heuristik, tidak serta merta mengalahkan SEMUA gerakan yang bisa dilakukan lawan.

Teman saya berpikir, sebaliknya, bahwa komputer akan selalu menang atau seri jika tidak pernah melakukan gerakan "kesalahan" (bagaimana pun Anda mendefinisikannya?). Namun, sebagai programmer yang telah mengambil CS, saya tahu bahwa bahkan pilihan bagus Anda - diberikan lawan yang bijak - dapat memaksa Anda untuk melakukan "kesalahan" pada akhirnya. Bahkan jika Anda tahu segalanya, langkah Anda selanjutnya adalah serakah dalam mencocokkan heuristik.

Sebagian besar komputer catur mencoba mencocokkan kemungkinan permainan akhir dengan permainan yang sedang berlangsung, yang pada dasarnya adalah penelusuran balik pemrograman dinamis. Sekali lagi, endgame yang dimaksud bisa dihindari.

Edit: Hmm ... sepertinya saya mengacak-acak beberapa bulu di sini. Itu bagus.

Memikirkannya lagi, sepertinya tidak ada masalah teoretis dengan menyelesaikan permainan terbatas seperti catur. Saya berpendapat bahwa catur sedikit lebih rumit daripada catur karena kemenangan tidak harus dengan kelelahan numerik bidak, tetapi oleh pasangan. Penegasan asli saya mungkin salah, tetapi sekali lagi saya pikir saya telah menunjukkan sesuatu yang belum terbukti secara memuaskan (secara resmi).

Saya kira eksperimen pemikiran saya adalah bahwa setiap kali cabang di pohon diambil, maka algoritme (atau jalur yang diingat) harus menemukan jalur ke pasangan (tanpa dikawinkan) untuk setiap cabang yang mungkin pada gerakan lawan. Setelah diskusi, saya akan membeli bahwa mengingat lebih banyak daripada yang dapat kita impikan, semua jalan ini dapat ditemukan.

Meluap
sumber
1
+1: topik yang luar biasa. Namun, menurut saya ini harus wiki-fied seperti yang ditunjukkan oleh variasi dan volume jawaban.
IAbstract
1
"apakah saya telah menunjukkan sesuatu yang belum terbukti secara memuaskan"? Apa yang Anda tunjukkan yang tidak terbukti secara formal?
S. Lott
2
ack! bagaimana bisa ada 20 jawaban berbeda untuk pertanyaan hitam putih seperti itu! (tidak ada permainan kata-kata).
Peter Recore
5
Saya juga heran dengan jumlah orang yang memposting jawaban spekulatif mereka tanpa menyadari bahwa jawabannya sebenarnya telah ditentukan secara matematis - jawaban dalam arti bahwa telah terbukti bahwa catur memiliki solusi - hanya saja tidak praktis untuk menghitungnya.
DJClayworth
3
Mengingatkan saya pada lelucon tentang Komputer Bermain Catur yang Sempurna. Bermain putih, ia berpikir dan berpikir dan berpikir dan kemudian .... mengundurkan diri!

Jawaban:

104

"Saya berpendapat bahwa tidak mungkin ada mesin Turing deterministik yang selalu menang atau buntu di catur."

Anda kurang tepat. Bisa ada mesin seperti itu. Persoalannya adalah luasnya ruang negara yang harus dicari. Itu terbatas, hanya SANGAT besar.

Itulah mengapa catur kembali pada heuristik - ruang negara terlalu besar (tapi terbatas). Bahkan menghitung - apalagi mencari setiap gerakan sempurna di setiap jalur dari setiap permainan yang mungkin - akan menjadi masalah pencarian yang sangat, sangat besar.

Bukaan dituliskan untuk membawa Anda ke permainan tengah yang memberi Anda posisi "kuat". Bukan hasil yang diketahui. Bahkan permainan akhir - ketika ada lebih sedikit bidak - sulit untuk dihitung untuk menentukan langkah terbaik selanjutnya. Secara teknis mereka terbatas. Tetapi jumlah alternatifnya sangat besar. Bahkan 2 benteng + raja memiliki 22 kemungkinan jurus berikutnya. Dan jika dibutuhkan 6 gerakan untuk pasangan, Anda melihat 12.855.002.631.049.216 gerakan.

Lakukan perhitungan matematika pada gerakan pembukaan. Meskipun hanya ada sekitar 20 gerakan pembuka, ada sekitar 30 atau lebih gerakan kedua, jadi pada langkah ketiga kami melihat 360.000 status permainan alternatif.

Tapi permainan catur (secara teknis) terbatas. Besar, tapi terbatas. Ada informasi yang sempurna. Ada keadaan awal dan akhir yang ditentukan, Tidak ada lemparan koin atau lemparan dadu.

S. Lott
sumber
22
Semua permainan akhir dengan 6 buah atau kurang telah disebutkan dan diselesaikan. Lihat tablebase dan bitbase di sini: en.wikipedia.org/wiki/Tablebase . Misalnya, ada permainan akhir KQNKRBN di mana dibutuhkan 517 gerakan untuk memaksa pasangan! Tetapi jumlah total permainan catur adalah sekitar (10 ^ (10 ^ 50)).
HTTP 410
2
Naskah untuk menang adalah satu hal. Mencacah secara mendalam adalah hal yang berbeda. Either way, informasinya sempurna - semuanya diketahui - permainan itu deterministik menurut definisi.
S. Lott
11
@RoadWarrior: tidak setuju. Acak berlaku untuk cuaca. Tuhan melempar dadu. Acak tidak berlaku untuk catur - menurut definisi. Catur memiliki informasi yang lengkap. Cuaca memiliki efek kuantum - tidak bisa lengkap.
S. Lotot
3
Apa yang membuat cuaca sulit untuk diramalkan adalah faktor non-linier yang kacau, bukan efek kuantum. Dengan pengetahuan dan daya komputasi yang cukup, secara teori kita dapat membuat ramalan cuaca yang "benar".
HTTP 410
3
@monojohnny: Aturan melarang tiga pengulangan posisi yang sama. Catur itu terbatas. Itu besar tapi terbatas.
S. Lotot
72

Saya hampir tidak tahu apa-apa tentang apa yang sebenarnya telah ditemukan tentang catur. Tapi sebagai matematikawan, inilah alasan saya:

Pertama-tama kita harus ingat bahwa Putih harus pergi dulu dan mungkin ini memberinya keuntungan; mungkin itu memberi Black keuntungan.

Sekarang anggap saja tidak ada strategi sempurna untuk Hitam yang membuatnya selalu menang / jalan buntu. Ini menyiratkan bahwa apa pun yang dilakukan Hitam, ada strategi yang dapat diikuti oleh Putih untuk menang. Tunggu sebentar - ini berarti ada adalah strategi yang sempurna untuk White!

Ini memberitahu kita bahwa setidaknya salah satu dari dua pemain yang memiliki strategi yang sempurna yang memungkinkan pemain selalu menang atau menggambar.

Hanya ada tiga kemungkinan, maka:

  • Putih selalu bisa menang jika dia bermain dengan sempurna
  • Hitam selalu bisa menang jika bermain sempurna
  • Satu pemain bisa menang atau seri jika bermain sempurna (dan jika kedua pemain bermain sempurna maka mereka selalu menemui jalan buntu)

Tapi mana yang benar, kita mungkin tidak pernah tahu.

Jawaban atas pertanyaannya adalah ya : harus ada algoritme yang sempurna untuk catur, setidaknya untuk salah satu dari dua pemain tersebut.

Artelius
sumber
2
+1, Itu cara yang sangat bagus untuk menjelaskannya. Aku tidak percaya aku tidak pernah memikirkan itu!
Zifre
2
Mengapa hitam tidak memiliki strategi yang sempurna menyiratkan bahwa putih memang memiliki strategi yang sempurna? Bagaimana dengan kedua pemain yang tidak memiliki strategi yang sempurna? Jika implikasi Anda benar, bukankah itu juga berlaku untuk setiap game 2 pemain, artinya setiap game memiliki strategi yang sempurna?
John M Naglick
8
@ John: Karena catur memiliki informasi yang sempurna dan tidak ada elemen acak (tidak seperti banyak, banyak permainan 2-pemain lainnya), satu-satunya cara yang mungkin untuk tidak ada strategi yang sempurna untuk ada hitam adalah jika putih dapat memaksakan kemenangan meskipun ada upaya hitam - dengan kata lain, jika ada strategi yang sempurna untuk putih.
Dave Sherohman
2
Sebenarnya logika ini tidak selalu berlaku , tapi benarkah dalam kasus ini.
BlueRaja - Danny Pflughoeft
4
@ John "kenapa begitu banyak diskusi di sini" - karena beberapa orang tidak tahu jawabannya, namun tetap posting di sini.
DJClayworth
30

Telah terbukti untuk permainan catur bahwa sebuah program selalu bisa menang atau seri. Artinya, tidak ada pilihan gerakan yang bisa dilakukan oleh satu pemain yang memaksa pemain lain untuk kalah.

Para peneliti menghabiskan hampir dua dekade melalui 500 miliar miliar kemungkinan posisi checker, yang masih merupakan bagian kecil yang sangat kecil dari jumlah posisi catur. Upaya checker termasuk pemain top, yang membantu tim riset program checker rules of thumb menjadi perangkat lunak yang mengkategorikan gerakan sebagai berhasil atau tidak berhasil. Kemudian para peneliti membiarkan program tersebut berjalan, rata-rata 50 komputer setiap hari. Beberapa hari, program berjalan pada 200 mesin. Sementara para peneliti memantau kemajuan dan menyesuaikan programnya. Faktanya, Chinook mengalahkan manusia untuk memenangkan kejuaraan dunia catur pada tahun 1994.

Ya, Anda bisa memecahkan catur, tidak, Anda tidak akan bisa dalam waktu dekat.

BCS
sumber
6
"[Y] ou tidak akan lama lagi" adalah sedikit pernyataan yang meremehkan. Selain batas perkiraan durasi alam semesta, ada masalah penyimpanan-- jumlah negara bagian di Catur jauh melebihi 500 miliar miliar checker; nyatanya, itu melebihi jumlah partikel di alam semesta.
Michael Dorfman
30
"[...] pada kenyataannya, itu melebihi jumlah partikel di alam semesta.". Selama tidak melebihi jumlah keadaan partikel di alam semesta, masih ada harapan ;-)
Carsten
1
apa jadinya bila program yang selalu memaksa lawan untuk kalah adalah bermain melawan dirinya sendiri ????
John Demetriou
1
@BCS hmm, gimana kalo ada prediksi kalo saya main sebagai pemain kedua dan yang lain menggunakan heuristik yang sama dengan saya maka lakukan ikuti heuristik ini untuk menang dan jika pemain pertama memiliki heuristik yang serupa ???? ?
John Demetriou
1
apa yang saya katakan adalah jika ada algoritme yang sempurna dan kedua pemain memilikinya, akan ada probabilitas yang tidak terbatas yang dapat diubah algoritme tersebut agar menjadi sempurna
John Demetriou
15

Ini bukan pertanyaan tentang komputer tetapi hanya tentang permainan catur.

Pertanyaannya adalah, apakah ada strategi gagal-aman agar tidak pernah kalah? Jika strategi seperti itu ada, maka komputer yang tahu segalanya dapat selalu menggunakannya dan itu bukan heuristik lagi.

Misalnya, permainan tic-tac-toe biasanya dimainkan berdasarkan heuristik. Tapi, ada strategi gagal-aman. Apapun gerakan lawan, Anda selalu menemukan cara untuk menghindari kekalahan, jika Anda melakukannya dengan benar sejak awal.

Jadi, Anda perlu membuktikan bahwa strategi seperti itu ada atau tidak untuk catur juga. Pada dasarnya sama, hanya ruang gerak yang mungkin jauh lebih besar.

ypnos
sumber
Jadi, siapa yang ingin meremehkan jawaban saya? Apakah ada yang salah di dalamnya? Ingin tampil di depan?
ypnos
@ypnos, saya tidak meremehkan jawaban Anda sama sekali. Saya hanya berkomentar untuk tidak membiarkan down-voters membuat Anda kecewa. Anda mendapatkan 30 repetisi dan hanya kalah 1. Juga, +1;)
mmcdole
1
Beberapa alasan untuk tidak memberikan suara negatif. 1) Diketahui bahwa ada algoritma untuk menyelesaikan permainan, hanya saja algoritma tersebut tidak praktis untuk dihitung menggunakan teknologi apa pun yang mungkin. 2) Memecahkan permainan TIDAK menyiratkan bahwa mereka ada strategi yang aman dari kegagalan. Tic-tac-toe terselesaikan, tetapi tidak ada strategi untuk pemain kedua yang menghindari kekalahan.
DJClayworth
2
"Ini bukan pertanyaan tentang komputer, tetapi hanya tentang permainan catur." Ilmu komputer sebenarnya bukan tentang komputer. Mereka hanyalah sebuah alat. Ilmu komputer bekerja tanpa komputer.
Janus Troelsen
1
Ini -sebenarnya adalah pertanyaan tentang komputer, karena pertanyaannya adalah apakah Mesin Turing (= Komputer) bisa ada, yang memecahkan catur.
SDwarfs
14

Saya datang ke utas ini sangat terlambat, dan Anda telah menyadari beberapa masalah. Tetapi sebagai mantan master dan mantan programmer catur profesional, saya pikir saya dapat menambahkan beberapa fakta dan angka yang berguna. Ada beberapa cara untuk mengukur kompleksitas catur :

  • Jumlah total permainan catur kira-kira 10 ^ (10 ^ 50). Angka itu sangat besar.
  • Jumlah permainan catur yang terdiri dari 40 gerakan atau kurang adalah sekitar 10 ^ 40. Itu masih angka yang sangat besar.
  • Jumlah posisi catur yang memungkinkan adalah sekitar 10 ^ 46.
  • Pohon pencarian catur lengkap (angka Shannon) adalah sekitar 10 ^ 123, berdasarkan faktor percabangan rata-rata 35 dan panjang permainan rata-rata 80.
  • Sebagai perbandingan, jumlah atom di alam semesta yang dapat diamati biasanya diperkirakan sekitar 10 ^ 80.
  • Semua permainan akhir yang terdiri dari 6 buah atau kurang telah disusun dan diselesaikan .

Kesimpulan saya: sementara catur secara teoritis dapat dipecahkan, kita tidak akan pernah punya uang, motivasi, kekuatan komputasi, atau penyimpanan untuk melakukannya.

HTTP 410
sumber
3
Ayo. Anda harus memikirkan masalahnya secara berbeda. Jangan pikirkan jumlah game, karena transposisi dan algoritme alfa-beta dan semacamnya sangat memangkasnya. Pikirkan posisi papan (10 ^ 60) atau kombinasi bidak catur (100 juta). Dengan Komputasi Kuantum, itu sepele.
lkessler
2
Alfa-beta dalam konteks ini (memecahkan catur) akan membutuhkan fungsi evaluasi yang sempurna. Begitu juga dengan posisi papan dan kombinasi bidak. Kami tidak memiliki fungsi evaluasi yang sempurna, jadi komputasi kuantum tidak membantu kami.
HTTP 410
1
Setiap kali saya berpikir bahwa ada sesuatu yang "sepele", dan saya yakin belum ada yang melakukannya, saya juga yakin saya telah salah setidaknya sekali.
Dean J
2
@lkessler: Posisi dewan tidak menceritakan keseluruhan cerita. Setidaknya beberapa sejarah permainan diperlukan untuk mengebiri atau menangkap sambil lalu atau menggambar karena kurangnya gerakan menangkap atau bidak, dan seluruh sejarah untuk menggambar dengan pengulangan. Selain itu, karena itu adalah hasil penelitian penting baru-baru ini untuk komputer kuantum ke faktor 15, saya akan mengatakan tidak ada yang sepele dengan komputasi kuantum saat ini.
David Thornley
2
Sebagai perbandingan di sini, jika Anda dapat menghasilkan semua kemungkinan posisi catur, Anda dapat dengan mudah melakukan brute-force pada sandi apa pun dengan kunci 128-bit, karena 10 ^ 46 adalah sekitar 2 ^ 152 atau 2 ^ 153. Ada alasan-alasan yang sangat bagus untuk berpikir bahwa hal ini tidak mungkin terjadi sebelum kematian panas Semesta.
David Thornley
9

Faktanya, beberapa permainan telah dipecahkan. Tic-Tac-Toe adalah cara yang sangat mudah untuk membangun AI yang akan selalu menang atau seri. Baru-baru ini, Connect 4 juga telah diselesaikan (dan terbukti tidak adil bagi pemain kedua, karena permainan yang sempurna akan menyebabkan dia kalah).

Catur, bagaimanapun, belum diselesaikan, dan menurut saya tidak ada bukti apapun bahwa ini adalah permainan yang adil (yaitu, apakah permainan yang sempurna menghasilkan seri). Berbicara secara ketat dari perspektif teoretis, Catur memiliki jumlah konfigurasi bidak yang terbatas. Oleh karena itu, ruang pencarian terbatas (meskipun sangat besar). Karena itu, mesin Turing deterministik yang bisa bermain dengan sempurna memang ada. Apakah seseorang bisa dibangun, bagaimanapun, adalah masalah yang berbeda.

Cybis
sumber
8

Rata-rata desktop seharga $ 1.000 akan dapat menyelesaikan checker hanya dalam 5 detik pada tahun 2040 (5x10 ^ 20 perhitungan).

Bahkan pada kecepatan ini, masih dibutuhkan 100 komputer ini kira-kira 6,34 x 10 ^ 19 tahun untuk menyelesaikan catur. Masih tidak layak. Bahkan tidak dekat.

Sekitar tahun 2080, rata-rata desktop kita akan memiliki sekitar 10 ^ 45 kalkulasi per detik. Satu komputer akan memiliki kekuatan komputasi untuk menyelesaikan catur dalam waktu sekitar 27,7 jam. Ini pasti akan selesai pada tahun 2080 selama daya komputasi terus tumbuh seperti halnya 30 tahun terakhir.

Pada tahun 2090, daya komputasi yang cukup akan ada di desktop seharga $ 1.000 untuk menyelesaikan catur dalam waktu sekitar 1 detik ... jadi pada tanggal itu, semuanya akan menjadi hal yang sepele.

Mengingat checker diselesaikan pada tahun 2007, dan kekuatan komputasi untuk menyelesaikannya dalam 1 detik akan tertinggal sekitar 33-35 tahun, kita mungkin dapat memperkirakan secara kasar catur akan diselesaikan di suatu tempat antara 2055-2057. Mungkin lebih cepat sejak saat lebih banyak daya komputasi tersedia (yang akan terjadi dalam 45 tahun), lebih banyak lagi yang dapat dicurahkan untuk proyek seperti ini. Namun, saya akan mengatakan 2050 paling awal, dan paling lambat 2060.

Pada tahun 2060, dibutuhkan 100 desktop rata-rata 3,17 x 10 ^ 10 tahun untuk menyelesaikan catur. Sadarilah bahwa saya menggunakan komputer seharga $ 1000 sebagai patokan saya, sedangkan sistem dan superkomputer yang lebih besar mungkin akan tersedia karena rasio harga / kinerja mereka juga meningkat. Juga, urutan besarnya daya komputasi meningkat dengan kecepatan yang lebih cepat. Misalkan sebuah superkomputer sekarang dapat melakukan perhitungan 2,33 x 10 ^ 15 per detik, dan komputer seharga $ 1000 sekitar 2 x 10 ^ 9. Sebagai perbandingan, 10 tahun yang lalu perbedaannya adalah 10 ^ 5, bukan 10 ^ 6. Pada tahun 2060 urutan perbedaan besarnya mungkin akan menjadi 10 ^ 12, dan bahkan ini dapat meningkat lebih cepat dari yang diantisipasi.

Sebagian besar tergantung pada apakah kita sebagai manusia memiliki dorongan untuk memecahkan catur, tetapi kekuatan komputasi akan membuatnya layak untuk saat ini (selama kecepatan kita terus berlanjut).

Pada catatan lain, permainan Tic-Tac-Toe, yang jauh lebih sederhana, memiliki 2.653.002 kemungkinan perhitungan (dengan papan terbuka). Kekuatan komputasi untuk menyelesaikan Tic-Tac-Toe dalam kira-kira 2,5 (1 juta kalkulasi per detik) detik dicapai pada tahun 1990.

Mundur ke belakang, pada tahun 1955, komputer memiliki kekuatan untuk menyelesaikan Tic-Tac-Toe dalam waktu sekitar 1 bulan (1 kalkulasi per detik). Sekali lagi, ini didasarkan pada apa yang akan Anda dapatkan $ 1000 jika Anda dapat mengemasnya ke dalam komputer (desktop seharga $ 1000 jelas tidak ada pada tahun 1955), dan komputer ini akan dikhususkan untuk menyelesaikan Tic-Tac-Toe .... yang mana tidak terjadi pada tahun 1955. Perhitungan itu mahal dan tidak akan digunakan untuk tujuan ini, meskipun saya tidak percaya ada tanggal di mana Tic-Tac-Toe dianggap "diselesaikan" oleh komputer, tapi saya yakin itu tertinggal dari daya komputasi yang sebenarnya.

Juga, pertimbangkan $ 1000 dalam 45 tahun akan bernilai sekitar 4 kali lebih sedikit dari sekarang, jadi lebih banyak uang dapat masuk ke proyek seperti ini sementara daya komputasi akan terus menjadi lebih murah.

jujur
sumber
9
"Tahukah Anda bahwa penjualan rekaman disko naik 400% untuk tahun yang berakhir 1976? Jika tren ini terus berlanjut ... AAY!" - Disco Stu
Jeremy Friesner
2
Hukum Moore - Daya komputasi berlipat ganda setiap 18 bulan - kemungkinan besar akan gagal sekitar tahun 2015. Atau desain prosesor komputer harus sangat berbeda. Jadi 2080 bukanlah target yang realistis.
Philip Smith
3
@Philip: Kecepatan clock prosesor komputer desktop hanya meningkat sedikit sejak tahun 2003, dan penyempurnaan sejak saat itu sebagian besar telah meningkatkan cache dan beberapa core. Karena prosesor 3 GHz memiliki satu siklus clock dalam waktu yang dibutuhkan cahaya untuk bergerak 4 inci / 10 cm, kecepatan clock tidak dapat diharapkan meningkat tanpa batas. Selain itu, paralelisme biasanya sulit. Memproyeksikan peningkatan eksponensial selama lima puluh tahun ketika mulai runtuh tujuh tahun lalu tampaknya bukan taruhan yang aman.
David Thornley
1
@David - itu semua benar. Tapi melenceng. Jika Anda setengah ukuran komponen pada chip, elektron menyelesaikan dua kali lebih banyak pada kecepatan clock yang sama. Inilah yang mendorong hukum Moore.
Philip Smith
3
@Philip: Halving tidak bisa berlangsung selamanya. Sebuah atom silikon berukuran sekitar seperempat nanometer, dan fabrikasi chip sudah turun hingga puluhan nanometer. Selain itu, pada level kuantum, partikel mematuhi aturan statistik, bukan aturan absolut, jadi perlu untuk memindahkan elektron yang cukup pada satu waktu untuk menerapkan hukum bilangan besar. Sejauh ini, hukum Moore berada di antara hukum dan ramalan yang terpenuhi dengan sendirinya, tetapi itu akan berakhir dalam waktu yang tidak lama lagi.
David Thornley
7

Sebenarnya mungkin bagi kedua pemain untuk memiliki strategi kemenangan dalam permainan tanpa batas tanpa pengaturan yang baik; Namun, catur tersusun dengan baik. Faktanya, karena aturan 50 gerakan , ada batas atas jumlah gerakan yang dapat dimiliki permainan, dan dengan demikian hanya ada banyak kemungkinan permainan catur (yang dapat dihitung untuk menyelesaikan dengan tepat .. secara teoritis, setidaknya :)

BlueRaja - Danny Pflughoeft
sumber
4
Secara teknis aturan lima puluh gerakan, seperti pengulangan tiga gerakan (yang juga membatasi banyak hal - ada sejumlah kemungkinan posisi yang terbatas, jadi mengalikan angka itu dengan tiga memberi kita batas atas) tidak menyebabkan hasil seri. Sebaliknya, itu memberi kesempatan kepada kedua pemain untuk mengklaim hasil imbang. Biasanya, pemain yang kalah akan melakukannya, tetapi itu tidak wajib. Oleh karena itu, berikut ini adalah permainan yang sepenuhnya legal: 1. Nc3 Nc6 2. Nb1 Nb8 3. Nc3 Nc6 4. Nb1 Nb8, diulang selamanya. Dan jika saya tidak salah, belum terbukti bahwa itu bukan hasil dari dua algoritme sempurna yang bermain sebagai putih dan hitam.
Lenoxus
6

Akhir argumen Anda didukung oleh cara kerja program catur modern sekarang . Mereka bekerja seperti itu karena terlalu banyak sumber daya untuk membuat kode program catur untuk beroperasi secara deterministik. Mereka tidak selalu bekerja seperti itu. Ada kemungkinan bahwa catur suatu hari akan terpecahkan , dan jika itu terjadi, kemungkinan besar akan diselesaikan oleh komputer.

Bill the Lizard
sumber
5

Sebagai catatan, ada komputer yang bisa menang atau seri di catur . Saya tidak yakin apakah hal yang sama bisa dilakukan untuk catur. Jumlah gerakannya jauh lebih tinggi. Juga, banyak hal berubah karena bidak bisa bergerak ke segala arah, tidak hanya maju dan mundur. Saya pikir meskipun saya tidak yakin, bahwa catur itu deterministik, tetapi ada terlalu banyak kemungkinan gerakan bagi komputer untuk saat ini menentukan semua gerakan dalam jumlah waktu yang wajar.

Kibbee
sumber
1
Itu bisa dilakukan, tapi bisakah itu dilakukan di komputer yang mungkin pernah kita lihat?
BCS
1
Mungkin tidak dalam hidup kita. Semua penelitian yang sangat menarik di lapangan sedang dilakukan di game Go. :)
Bill the Lizard
IIRC sebagian besar anak berusia 6 tahun dapat menggunakan komputer mana pun di Go.
BCS
2
@BCS: Tidak lagi. Program Go terbaik sekarang adalah mengalahkan pemain level dan (profesional).
Bill the Lizard
1
@BlueRaja: Itu pada tahun 2008. Saya tidak tahu apa rekornya saat ini, tapi MoGo telah mengalahkan pemain profesional dengan 6 dan 7 batu pada 19x19. ireport.cnn.com/docs/DOC-214010
Bill the Lizard
5

Saya pikir Anda sudah mati. Mesin seperti Deep Blue dan Deep Thought diprogram dengan sejumlah game yang telah ditentukan sebelumnya, dan algoritme cerdas untuk mengurai pohon ke ujung game tersebut. Ini, tentu saja, adalah penyederhanaan yang berlebihan. Selalu ada kesempatan untuk "mengalahkan" komputer sepanjang permainan. Yang saya maksud dengan ini adalah melakukan gerakan yang memaksa komputer untuk melakukan gerakan yang kurang dari optimal (apa pun itu). Jika komputer tidak dapat menemukan jalur terbaik sebelum batas waktu pemindahan, kemungkinan besar komputer membuat kesalahan dengan memilih salah satu jalur yang kurang diinginkan.

Ada kelas program catur lain yang menggunakan pembelajaran mesin nyata, atau pemrograman genetik / algoritma evolusioner. Beberapa program telah berkembang dan menggunakan jaringan saraf, dkk, untuk membuat keputusan. Dalam kasus seperti ini, saya membayangkan bahwa komputer mungkin membuat "kesalahan", tetapi tetap berakhir dengan kemenangan.

Ada sebuah buku menarik tentang GP jenis ini yang berjudul Blondie24 yang mungkin Anda baca. Ini tentang catur, tapi bisa diterapkan pada catur.

Jason Jackson
sumber
Begitulah cara Anda mengalahkan komputer saat ini dalam catur. Besok akan lebih baik. Saya setuju dengan Anda, bahwa Blondie24 sangat menarik.
Bill the Lizard
Telah memilih kembali. Posting ini tidak pantas mendapatkan skor negatif.
Cybis
Sayangnya, masalah permainan catur terlalu besar untuk pembelajaran mesin untuk bekerja. Mereka tidak pernah bisa mendapatkan program catur pembelajaran bahkan untuk bermain novicely tanpa kesalahan. Heuristik lebih baik. Tapi Brute Force bahkan lebih baik. Bidang pembelajaran mesin hanya belajar dari kegagalannya dengan catur.
lkessler
Program catur tidak membuat kesalahan jangka pendek, dan program terbaik bermain lebih baik daripada juara dunia. Saya pikir versi terbaru Rybka 64 bit diberi peringkat seperti 3200 ELO
Alex
5

Dari teori permainan, tentang apa pertanyaan ini, jawabannya adalah ya, Catur bisa dimainkan dengan sempurna. Ruang permainan dikenal / dapat diprediksi dan ya jika Anda memiliki komputer kuantum cucu Anda, Anda mungkin dapat menghilangkan semua heuristik.

Anda dapat menulis mesin tic-tac-toe yang sempurna sekarang-a-hari dalam bahasa skrip apa pun dan itu akan bermain dengan sempurna dalam waktu nyata.

Othello adalah gim lain yang dapat dimainkan dengan mudah oleh komputer saat ini, tetapi memori dan CPU mesin akan membutuhkan sedikit bantuan

Catur secara teoritis mungkin tetapi tidak mungkin secara praktis (pada tahun 2008)

i-Go itu rumit, ruang kemungkinannya berada di luar jumlah atom di alam semesta, jadi mungkin perlu waktu bagi kita untuk membuat mesin i-Go yang sempurna.

Robert Gould
sumber
Ini bukan teori permainan
BlueRaja - Danny Pflughoeft
4
Secara teknis, itu teori permainan kombinatorial.
Anaphory
5

Catur adalah contoh permainan matriks, yang menurut definisi memiliki hasil yang optimal (pikirkan ekuilibrium Nash). Jika pemain 1 dan 2 masing-masing mengambil langkah optimal, hasil tertentu akan SELALU tercapai (apakah menang-kalah-kalah masih belum diketahui).

Jon Smock
sumber
5

Sebagai programmer catur dari tahun 1970-an, saya pasti punya pendapat tentang ini. Apa yang saya tulis sekitar 10 tahun yang lalu, pada dasarnya masih berlaku sampai sekarang:

"Pekerjaan yang Belum Selesai dan Tantangan bagi Pemrogram Catur"

Saat itu, saya pikir kita bisa menyelesaikan Catur secara konvensional, jika dilakukan dengan benar.

Checkers diselesaikan baru-baru ini (Yay, University of Alberta, Canada !!!) tetapi itu secara efektif dilakukan Brute Force. Untuk bermain catur secara konvensional, Anda harus lebih pintar.

Kecuali, tentu saja, Komputasi Kuantum menjadi kenyataan. Jika demikian, catur akan diselesaikan semudah Tic-Tac-Toe.

Di awal tahun 1970-an di Scientific American, ada parodi pendek yang menarik perhatian saya. Itu adalah pengumuman bahwa permainan catur diselesaikan oleh komputer catur Rusia. Telah ditentukan bahwa ada satu langkah sempurna untuk putih yang akan memastikan kemenangan dengan permainan sempurna oleh kedua belah pihak, dan langkah itu adalah: 1. a4!

lkessler.dll
sumber
3

Banyak jawaban di sini membuat poin-poin teori permainan penting:

  1. Catur adalah permainan deterministik yang terbatas dengan informasi lengkap tentang keadaan permainan
  2. Anda dapat menyelesaikan permainan yang terbatas dan mengidentifikasi strategi yang sempurna
  3. Namun catur cukup besar sehingga Anda tidak akan bisa menyelesaikannya sepenuhnya dengan metode kekerasan

Namun pengamatan ini kehilangan poin praktis yang penting: tidak perlu menyelesaikan permainan lengkap dengan sempurna untuk menciptakan mesin yang tidak ada duanya .

Sebenarnya sangat mungkin bahwa Anda bisa membuat mesin catur yang tidak terkalahkan (yaitu tidak akan pernah kalah dan akan selalu memaksa menang atau seri) tanpa mencari bahkan sebagian kecil dari ruang negara yang mungkin.

Teknik berikut, misalnya, semuanya secara besar-besaran mengurangi ruang pencarian yang dibutuhkan:

  • Teknik pemangkasan pohon seperti Alpha / Beta atau MTD-f sudah secara besar-besaran mengurangi ruang pencarian
  • Posisi kemenangan yang dapat dibuktikan. Banyak akhiran termasuk dalam kategori ini: Anda tidak perlu mencari KR vs K misalnya, ini terbukti menang. Dengan beberapa pekerjaan adalah mungkin untuk membuktikan lebih banyak kemenangan yang dijamin.
  • Kemenangan yang hampir pasti - untuk permainan yang "cukup baik" tanpa kesalahan yang bodoh (katakanlah tentang ELO 2200+?) Banyak posisi catur yang hampir pasti merupakan kemenangan, misalnya keuntungan material yang layak (misalnya seorang Ksatria tambahan) tanpa keuntungan posisi kompensasi. Jika program Anda dapat memaksakan posisi seperti itu dan memiliki heuristik yang cukup baik untuk mendeteksi keunggulan posisi, program dapat dengan aman mengasumsikan bahwa program tersebut akan menang atau setidaknya seri dengan probabilitas 100%.
  • Heuristik penelusuran pohon - dengan pengenalan pola yang cukup baik, Anda dapat dengan cepat fokus pada subset yang relevan dari gerakan "menarik". Beginilah cara grandmaster manusia bermain, jadi ini jelas bukan strategi yang buruk ..... dan algoritme pengenalan pola kami terus menjadi lebih baik
  • Penilaian risiko - konsepsi yang lebih baik tentang "keberisikoan" suatu posisi akan memungkinkan pencarian yang jauh lebih efektif dengan memfokuskan daya komputasi pada situasi di mana hasilnya lebih tidak pasti (ini adalah perpanjangan alami dari Quiescence Search )

Dengan kombinasi yang tepat dari teknik di atas, saya akan merasa nyaman untuk menyatakan bahwa adalah mungkin untuk membuat mesin permainan catur yang "tak terkalahkan". Kami mungkin tidak terlalu jauh dengan teknologi saat ini.

Perhatikan bahwa hampir pasti lebih sulit untuk membuktikan bahwa mesin ini tidak dapat dikalahkan. Mungkin akan menjadi sesuatu seperti hipotesis Reimann - kami akan cukup yakin bahwa itu berjalan dengan sempurna dan akan memiliki hasil empiris yang menunjukkan bahwa ia tidak pernah kalah (termasuk beberapa miliar hasil imbang langsung terhadap dirinya sendiri), tetapi kami tidak benar-benar memiliki kemampuan untuk buktikan itu.

Catatan tambahan tentang "kesempurnaan":

Saya berhati-hati untuk tidak mendeskripsikan mesin sebagai "sempurna" dalam pengertian teori permainan karena itu menyiratkan kondisi tambahan yang sangat kuat, seperti:

  • Selalu menang dalam setiap situasi yang memungkinkan untuk memaksakan kemenangan, tidak peduli seberapa kompleks kombinasi kemenangan itu. Akan ada situasi di batas antara menang / seri di mana ini sangat sulit untuk dihitung dengan sempurna.
  • Memanfaatkan semua informasi yang tersedia tentang potensi ketidaksempurnaan dalam permainan lawan, misalnya menyimpulkan bahwa lawan mungkin terlalu rakus dan sengaja memainkan garis yang sedikit lebih lemah dari biasanya dengan alasan berpotensi lebih besar untuk menggoda lawan untuk melakukan kesalahan. Terhadap lawan yang tidak sempurna, sebenarnya bisa menjadi optimal untuk membuat kekalahan jika Anda memperkirakan bahwa lawan Anda mungkin tidak akan melihat kemenangan paksa dan itu memberi Anda kemungkinan lebih tinggi untuk menang sendiri.

Kesempurnaan (terutama karena lawan yang tidak sempurna dan tidak dikenal) adalah masalah yang jauh lebih sulit daripada sekadar tidak terkalahkan.

mikera
sumber
Memiliki lawan yang tidak sempurna bukanlah masalah yang nyata. Ini hanya membuat pemain yang sempurna menang / seri (apa pun hasil yang sempurna) dalam gerakan yang lebih sedikit. Gerakan optimal di setiap posisi selalu lebih baik atau sama dengan gerakan lain yang mungkin (menurut definisi). Jadi gerakan suboptimal memungkinkan lawan mencapai keadaan akhir yang optimal (menang / seri) lebih awal atau bahkan memungkinkan untuk memaksakan hasil yang lebih baik. Misalnya, jika hitam akan selalu kalah jika putih bermain sempurna, ada kemungkinan hitam menang, jika putih hanya memainkan satu gerakan suboptimal. Tapi ya, ini akan sedikit meningkatkan kompleksitas analisis.
SDwarfs
@ Stefan - Lawan yang tidak sempurna adalah masalah besar jika Anda peduli dengan permainan yang optimal . Secara khusus, Anda dapat membayangkan situasi di mana sebenarnya lebih disukai untuk memainkan gerakan kalah (yaitu gerakan di mana lawan yang sempurna pasti akan mengalahkan Anda) jika Anda tahu bahwa kemungkinan lawan membuat kesalahan cukup tinggi.
mikera
bermain optimal menurut saya berarti mencapai hasil terbaik dengan risiko nol. Lawan Anda mungkin "lemah" tetapi ketika Anda memainkan gerakan yang kalah itu, sayangnya dia mungkin memainkan gerakan yang baik secara tidak sengaja. Memperhatikan lawan yang kurang optimal hanya relevan jika hanya ada pilihan antara langkah yang kalah di mana salah satu dari mereka memiliki peluang lebih tinggi untuk melakukan kesalahan oleh lawan (permainan yang tidak optimal) yang mengarah pada hasil seri atau menang.
SDwarfs
1
Itu bukan definisi optimal yang biasa dalam teori permainan. Optimal biasanya berarti memaksimalkan hasil yang diharapkan . Dalam hal ini, pemain yang optimal akan menerima beberapa risiko asalkan mendapatkan hasil rata-rata yang lebih baik .
mikera
Dalam hal ini Anda sepenuhnya benar!
SDwarfs
2

jika Anda mencari seluruh ruang dari semua kombinasi gerakan pemain1 / 2, satu gerakan yang diputuskan oleh komputer di setiap langkah didasarkan pada heuristik.

Ada dua gagasan yang bersaing di sana. Salah satunya adalah Anda mencari setiap gerakan yang mungkin, dan yang lainnya adalah Anda memutuskan berdasarkan heuristik. Heuristik adalah sistem untuk membuat tebakan yang baik. Jika Anda mencari setiap kemungkinan gerakan, Anda tidak lagi menebak-nebak.

Joel Coehoorn
sumber
Sebenarnya, kutipannya benar. Program melihat semua kemungkinan gerakan untuk kedua sisi pada posisi saat ini , dan menggunakan heuristik untuk menemukan langkah yang baik untuk menggerakkan permainan ke arah posisi yang menguntungkan bagi komputer.
Bill the Lizard
1
Tidak, mereka tidak melihat semua kemungkinan gerakan. Mereka menggunakan heuristik gerakan nol untuk memangkas pohon.
Alex
2

"Apakah ada algoritma yang sempurna untuk catur?"

Ya ada. Mungkin White selalu menang. Mungkin Black selalu menang. Mungkin bagi keduanya untuk selalu mengikat setidaknya. Kami tidak tahu yang mana, dan kami tidak akan pernah tahu, tapi itu pasti ada.

Lihat juga

poligenelubricants
sumber
1
Menjadi pemain catur yang cukup baik dan telah mempelajari masalah secara ekstensif selama bertahun-tahun, saya 99,9% yakin bahwa strategi prefek dalam catur untuk kedua pemain menghasilkan hasil imbang (sama seperti yang telah dibuktikan dengan catur). Ada juga bukti bahwa saat kekuatan pemain meningkat, begitu pula persentase hasil imbang.
mikera
2

Saya menemukan artikel oleh John MacQuarrie ini yang merujuk pada karya "bapak teori permainan" Ernst Friedrich Ferdinand Zermelo . Ini menarik kesimpulan berikut:

Dalam catur, putih bisa memaksa menang, atau hitam bisa memaksa menang, atau kedua belah pihak bisa memaksakan setidaknya imbang.

Logikanya terdengar bagi saya.

Ben Gartner
sumber
2

Ini bisa dipecahkan dengan sempurna.

Ada 10 ^ 50 posisi ganjil. Setiap posisi, menurut perhitungan saya, membutuhkan minimal 64 byte bulat untuk disimpan (setiap kotak memiliki: 2 bit afiliasi, 3 bit). Setelah mereka disusun, posisi yang merupakan sekak dapat diidentifikasi dan posisi dapat dibandingkan untuk membentuk hubungan, yang menunjukkan posisi mana yang mengarah ke posisi lain dalam pohon hasil yang besar.

Kemudian, program hanya perlu menemukan akar skakmat satu sisi terendah saja, jika hal seperti itu ada. Bagaimanapun, Catur cukup mudah diselesaikan di akhir paragraf pertama.

Salomo
sumber
1

Saya hanya yakin 99,9% dengan klaim bahwa ukuran ruang negara membuat tidak mungkin untuk mengharapkan solusi.

Tentu, 10 ^ 50 adalah angka yang sangat besar. Mari kita sebut ukuran ruang keadaan n.

Berapa batasan jumlah gerakan dalam permainan yang terpanjang? Karena semua permainan berakhir dengan jumlah gerakan yang terbatas maka ada batasan seperti itu, sebut saja m.

Mulai dari keadaan awal, tidak bisakah Anda menghitung semua n gerakan dalam ruang O (m)? Tentu, ini membutuhkan O (n) waktu, tetapi argumen dari ukuran alam semesta tidak secara langsung membahasnya. O (m) ruang mungkin tidak terlalu banyak. Untuk ruang O (m), tidak bisakah Anda juga melacak, selama traversal ini, apakah kelanjutan dari status apa pun di sepanjang jalur yang Anda lintasi mengarah ke EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin, atau BlackMayWinOrForceDraw? (Ada kisi bergantung pada giliran siapa, beri anotasi pada setiap negara bagian dalam riwayat traversal Anda dengan pertemuan kisi.)

Kecuali saya melewatkan sesuatu, itu adalah algoritme ruang O (n) waktu / O (m) untuk menentukan kategori mana yang termasuk dalam catur. Wikipedia mengutip perkiraan usia alam semesta sekitar 10 ^ 60 kali Planck. Tanpa membahas argumen kosmologi, mari kita tebak bahwa masih ada banyak waktu tersisa sebelum panas / dingin / kematian apapun dari alam semesta. Itu membuat kita perlu mengevaluasi satu gerakan setiap 10 ^ 10 kali Planck, atau setiap 10 ^ -34 detik. Itu waktu yang sangat singkat (sekitar 16 kali lipat lebih pendek dari waktu terpendek yang pernah diamati). Mari kita secara optimis mengatakan bahwa dengan implementasi super-duper-good yang berjalan di atas garis teknologi present-or-forseen-non-quantum-P-is-a-proper-subset-of-NP kami dapat berharap untuk mengevaluasi (ambil satu langkah maju, mengkategorikan keadaan yang dihasilkan sebagai keadaan antara atau salah satu dari tiga keadaan ujung) pada kecepatan 100 MHz (sekali setiap 10 ^ -8 detik). Karena algoritma ini sangat dapat diparalelkan, ini membuat kita membutuhkan 10 ^ 26 komputer semacam itu atau sekitar satu untuk setiap atom di tubuh saya, bersama dengan kemampuan untuk mengumpulkan hasilnya.

Saya kira selalu ada sedikit harapan untuk solusi brute force. Kita mungkin beruntung dan, dalam mengeksplorasi hanya satu dari kemungkinan gerakan pembuka putih, keduanya memilih satu dengan fanout yang jauh lebih rendah dari rata-rata dan satu di mana putih selalu menang atau menang atau seri.

Kami juga dapat berharap untuk sedikit mengecilkan definisi catur dan meyakinkan semua orang bahwa secara moral itu masih permainan yang sama. Apakah kita benar-benar perlu meminta pengulangan posisi sebanyak 3 kali sebelum seri? Apakah kita benar-benar perlu membuat pihak yang kabur mendemonstrasikan kemampuan melarikan diri selama 50 langkah? Apakah ada yang bahkan memahami apa sih terserah dengan en passant aturan? ;) Lebih serius, apakah kita benar-benar perlu untuk memaksa pemain untuk bergerak (sebagai lawan baik gambar atau kehilangan) saat nya hanya bergerak untuk melarikan diri cek atau jalan buntu adalah en passant capture? Bisakah kita membatasi pilihan bidak yang mana bidak dapat dipromosikan jika promosi non-ratu yang diinginkan tidak menghasilkan cek atau skakmat langsung?

Saya juga tidak yakin tentang seberapa banyak mengizinkan akses berbasis hash setiap komputer ke database besar status game akhir dan kemungkinan hasilnya (yang mungkin relatif layak pada perangkat keras yang ada dan dengan database endgame yang ada) dapat membantu memangkas pencarian sebelumnya. Jelas Anda tidak dapat memo seluruh fungsi tanpa O (n) penyimpanan, tetapi Anda dapat memilih bilangan bulat besar dan mengingat bahwa banyak endgame menghitung mundur dari setiap kemungkinan (atau bahkan tidak mudah dibuktikan tidak mungkin, saya kira) status akhir.

Doug McClean
sumber
1
M = 5898 Anda. Aturan catur FIDE menetapkan bahwa Anda harus memindahkan bidak atau mengambil bidak (sesuatu yang mengubah permainan secara permanen) setidaknya setiap 50 gerakan (disebut aturan 50 gerakan) atau salah satu pemain dapat mengklaim hasil imbang. Telah dihitung bahwa permainan terpanjang adalah 5898 gerakan, jika kedua pemain bekerja sama dan mengklaim hasil imbang sesegera mungkin. Tidak masuk akal untuk terus bermain, jika kedua pemain bisa mengklaim hasil imbang. Jika seorang pemain mengetahui bahwa dia kalah, dia dapat mengklaim undian, memberikan hasil yang sama. Lihat: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs
1
Catatan: m = 5898 adalah jumlah "gerakan". Jumlah maksimum setengah gerakan adalah (118-3) * 100 + 3 * 99 = 11797. Anda dapat menemukan buktinya di sini (Jerman!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs
1

Saya tahu ini sedikit berlebihan, tetapi saya harus memasukkan 5 sen saya di sini. Mungkin bagi komputer, atau seseorang, untuk mengakhiri setiap permainan catur yang dia ikuti, baik dalam kemenangan atau jalan buntu.

Untuk mencapai ini, bagaimanapun, Anda harus tahu persis setiap gerakan dan reaksi yang mungkin dan seterusnya, sampai ke setiap hasil permainan yang mungkin, dan untuk memvisualisasikan ini, atau untuk membuat cara mudah untuk menganalisis informasi ini, pikirkan itu sebagai peta pikiran yang bercabang terus-menerus.

Node tengah akan menjadi awal permainan. Setiap cabang dari setiap node akan melambangkan gerakan, masing-masing berbeda dengan gerakan bretherennya. Mempresentasikannya di rumah ini akan memakan banyak sumber daya, terutama jika Anda melakukan ini di atas kertas. Di komputer, ini mungkin membutuhkan ratusan Terrabyte data, karena Anda akan memiliki sangat banyak gerakan repedatif, kecuali Anda membuat cabangnya kembali.

Namun, menghafal data semacam itu tidak masuk akal, jika bukan tidak mungkin. Untuk membuat komputer mengenali langkah paling optimal untuk mengeluarkan (paling banyak) 8 gerakan yang mungkin secara instan, mungkin saja, tetapi tidak masuk akal ... karena komputer itu harus dapat memproses semua cabang yang melewati gerakan itu, sampai ke kesimpulan, hitung semua kesimpulan yang menghasilkan kemenangan atau kebuntuan, lalu tindak lanjuti jumlah kesimpulan menang tersebut agar tidak kehilangan kesimpulan, dan itu akan membutuhkan RAM yang mampu memproses data dalam Terrabytes, atau lebih! Dan dengan teknologi saat ini, komputer seperti itu akan membutuhkan lebih dari saldo bank dari 5 pria dan / atau wanita terkaya di dunia!

Jadi setelah semua pertimbangan itu bisa dilakukan, namun tidak ada orang yang bisa melakukannya. Tugas semacam itu akan membutuhkan 30 pikiran paling cemerlang yang hidup saat ini, tidak hanya dalam catur, tetapi juga dalam sains dan teknologi komputer, dan tugas semacam itu hanya dapat diselesaikan pada (mari kita taruh seluruhnya dalam perspektif dasar) ... sangat pada akhirnya hiper komputer super-duper ... yang tidak mungkin ada setidaknya selama satu abad. Itu akan selesai! Hanya saja tidak dalam hidup ini.

MrDeeJayy
sumber
1

Ada dua kesalahan dalam eksperimen pikiran Anda:

  1. Jika mesin Turing Anda tidak "terbatas" (dalam memori, kecepatan, ...), Anda tidak perlu menggunakan heuristik tetapi Anda dapat menghitung evaluasi status akhir (menang, kalah, seri). Untuk menemukan permainan yang sempurna Anda hanya perlu menggunakan algoritma Minimax (lihat http://en.wikipedia.org/wiki/Minimax ) untuk menghitung gerakan optimal untuk setiap pemain, yang akan menghasilkan satu atau lebih permainan yang optimal.

  2. Juga tidak ada batasan pada kerumitan heuristik yang digunakan. Jika Anda dapat menghitung permainan yang sempurna, ada juga cara untuk menghitung heuristik yang sempurna darinya. Jika diperlukan, ini hanya fungsi yang memetakan posisi catur dengan cara "Jika saya dalam situasi ini S, langkah terbaik saya adalah M".

Seperti yang telah ditunjukkan orang lain, ini akan berakhir dengan 3 kemungkinan hasil: putih dapat memaksa kemenangan, hitam dapat memaksa menang, salah satunya dapat memaksa hasil imbang.

Hasil dari permainan dam yang sempurna telah "dihitung". Jika umat manusia tidak mau menghancurkan dirinya sendiri sebelumnya, akan ada juga perhitungan untuk catur suatu hari nanti, ketika komputer telah cukup berkembang untuk memiliki memori dan kecepatan yang cukup. Atau kita memiliki beberapa komputer kuantum ... Atau sampai seseorang (peneliti, ahli catur, jenius) menemukan beberapa algoritma yang secara signifikan mengurangi kompleksitas permainan. Sebagai contoh: Berapa jumlah semua angka antara 1 dan 1000? Anda dapat menghitung 1 + 2 + 3 + 4 + 5 ... + 999 + 1000, atau Anda dapat menghitung: N * (N + 1) / 2 dengan N = 1000; result = 500500. Sekarang bayangkan tidak tahu tentang rumus itu, Anda tidak tahu tentang induksi matematika, Anda bahkan tidak tahu cara mengalikan atau menjumlahkan bilangan, ... Jadi, mungkin saja ada algoritma yang saat ini tidak diketahui yang pada akhirnya mengurangi kerumitan permainan ini dan hanya perlu 5 menit untuk menghitung langkah terbaik dengan komputer saat ini. Mungkin bahkan mungkin untuk memperkirakannya sebagai manusia dengan pena & kertas, atau bahkan dalam pikiran Anda, diberi lebih banyak waktu.

Jadi, jawaban singkatnya adalah: Jika umat manusia bertahan cukup lama, itu hanya masalah waktu!

SDwarfs
sumber
0

Mungkin saja bisa dipecahkan, tapi ada sesuatu yang menggangguku: Bahkan jika seluruh pohon bisa dilintasi, masih tidak ada cara untuk memprediksi langkah lawan selanjutnya. Kita harus selalu mendasarkan langkah kita selanjutnya pada keadaan lawan, dan membuat gerakan "terbaik" tersedia. Kemudian, berdasarkan keadaan selanjutnya kami melakukannya lagi. Jadi, gerakan optimal kita mungkin akan optimal jika lawan bergerak dengan cara tertentu. Untuk beberapa gerakan lawan, gerakan terakhir kami mungkin kurang optimal.

Saya hanya gagal melihat bagaimana bisa ada gerakan yang "sempurna" di setiap langkah.

Untuk itu, harus ada untuk setiap negara [dalam permainan saat ini] ada jalan di pohon yang mengarah pada kemenangan, terlepas dari langkah lawan selanjutnya (seperti di tic-tac-toe), dan saya memiliki kesulitan waktu menghitung itu.

E Dominique
sumber
5
Langkah sempurna ditentukan oleh strategi 'minmax': Ini adalah gerakan yang memaksimalkan skor minimum Anda (mengingat semua kemungkinan gerakan yang bisa dilakukan lawan). Atau dengan kata lain, itu mengasumsikan lawan juga bermain dengan sempurna.
Nick Johnson
Ini adalah poin yang menarik. Bisakah situasi muncul di mana tanggapan terhadap gerakan terbaik akan membuat Anda dirugikan jika lawan Anda tidak mengambil langkah terbaik? Implikasi apa yang dimilikinya?
Nona Urbiz
Saya bukan ahli matematika dan bukan pemain catur yang sangat baik; Saya juga berasumsi bahwa dalam teori (haruskah seluruh pohon permainan diketahui) bahwa jawabannya adalah 'ya'. Namun, setelah Anda menyebutkan masalah ini [pilihan pemain lain], apakah ini berarti sistem berpotensi tidak dapat diprediksi? Apakah ada titik tengah dalam permainan di mana pemain lain bisa membuat kerugian? Apakah ini sedikit seperti fakta bahwa Perceptron (Neural Net) dapat mempelajari 'OR' dan 'AND' tetapi tidak pernah dapat memahami 'XOR'? Apakah Catur adalah contoh dari sistem 'Chaotic'? FWIW, IMHO Saya pikir jawabannya tampaknya 'tidak tahu' pada saat ini.
monojohnny
@Nona Secara definisi, langkah itu akan menjadi langkah terbaik. Tidak ada asumsi.
piccolbo
@ piccolbo: Lebih baik -salah satu- gerakan terbaik. Ada posisi dalam catur di mana beberapa gerakan menghasilkan hasil yang sama (menang, seri, atau kalah dalam jumlah gerakan yang sama).
SDwarfs
0

Secara matematis, catur telah dipecahkan dengan algoritma Minimax , yang berasal dari tahun 1920-an (ditemukan oleh Borel atau von Neumann). Jadi, mesin turing memang bisa memainkan catur dengan sempurna.

Namun, kerumitan komputasi catur membuatnya menjadi tidak layak. Mesin saat ini menggunakan beberapa perbaikan dan heuristik. Mesin teratas saat ini telah melampaui manusia terbaik dalam hal kekuatan permainan, tetapi karena heuristik yang mereka gunakan, mereka mungkin tidak bermain sempurna ketika diberi waktu yang tidak terbatas (misalnya, benturan hash dapat menyebabkan hasil yang salah).

Yang paling dekat yang saat ini kami miliki dalam hal permainan sempurna adalah tabel-tabel endgame . Teknik khas untuk menghasilkannya disebut analisis retrograde . Saat ini, semua posisi hingga enam buah telah diselesaikan.

Philipp Claßen
sumber
-1

Ya , dalam matematika, catur digolongkan sebagai permainan yang ditentukan, artinya memiliki algoritma yang sempurna untuk setiap pemain pertama, hal ini terbukti benar bahkan untuk papan catur yang tak terhitung jumlahnya, jadi suatu saat mungkin suatu saat ada seorang AI yang akan menemukan strategi yang tepat, dan game itu hilang

Lebih lanjut tentang ini di video ini: https://www.youtube.com/watch?v=PN-I6u-AxMg

Ada juga catur kuantom, di mana tidak ada bukti matematika yang ditentukan game http://store.steampowered.com/app/453870/Quantum_Chess/

dan di sana Anda adalah video terperinci tentang catur quantom https://chess24.com/en/read/news/quantum-chess

Dhia Hassen
sumber
-2

Tentu saja Hanya ada 10 pangkat dari lima puluh kemungkinan kombinasi bidak di papan. Karena itu, untuk bermain dalam setiap komputasi, Anda harus membuat kurang dari 10 pangkat lima puluh gerakan (termasuk pengulangan mengalikan angka itu dengan 3). Jadi, ada kurang dari sepuluh pangkat seratus gerakan dalam catur. Pilih saja yang mengarah ke skakmat dan Anda siap melakukannya

Alex
sumber
-3

Matematika 64bit (= papan catur) dan operator bitwise (= kemungkinan langkah berikutnya) adalah semua yang Anda butuhkan. Sangat sederhana. Brute Force biasanya akan menemukan cara terbaik. Tentu saja, tidak ada algoritma universal untuk semua posisi. Dalam kehidupan nyata, penghitungan juga dibatasi waktu, batas waktu akan menghentikannya. Program catur yang baik berarti kode yang berat (lulus, bidak ganda, dll). Kode kecil tidak mungkin terlalu kuat. Membuka dan mengakhiri basis data hanya menghemat waktu pemrosesan, semacam data yang telah diproses sebelumnya. Perangkat, maksud saya - OS, kepemilikan threading, lingkungan, perangkat keras menentukan persyaratan. Bahasa pemrograman itu penting. Bagaimanapun, proses pengembangannya menarik.

Pengembang AI
sumber