Bisakah ada algoritma catur yang sempurna?

15

Algoritma catur saat ini berjalan sekitar 1 atau mungkin 2 level di pohon jalur yang mungkin tergantung pada gerakan pemain dan gerakan lawan. Katakanlah kita memiliki kekuatan komputasi untuk mengembangkan algoritma yang memprediksi semua kemungkinan pergerakan lawan dalam permainan catur. Algoritma yang memiliki semua jalur yang memungkinkan yang dapat diambil lawan pada saat tertentu tergantung pada pergerakan pemain. Adakah algoritma catur sempurna yang tidak akan pernah hilang? Atau mungkin suatu algoritma yang akan selalu menang? Maksud saya dalam teori seseorang yang dapat memprediksi semua gerakan yang mungkin harus dapat menemukan cara untuk mengalahkan masing-masing dan setiap dari mereka atau hanya memilih jalan yang berbeda jika seseorang tertentu akan secara membimbing membawanya ke kekalahan .....

edit - Apa pertanyaan saya sebenarnya. Katakanlah kita memiliki kekuatan komputasi untuk algoritma yang sempurna yang dapat bermain secara optimal. Apa yang terjadi ketika lawan bermain dengan algoritma optimal yang sama? Itu juga akan berlaku di semua 2 pemain game dengan jumlah terbatas (sangat besar atau tidak) bergerak. Adakah algoritma optimal yang selalu menang?

Definisi pribadi: Algoritma optimal adalah algoritma sempurna yang selalu menang ... (bukan yang tidak pernah kalah, tetapi yang selalu menang

algorithms turing-machines John Demetriou
sumber
1
lihat juga apa kompleksitas komputasi penyelesaian catur, tcs.se
vzn
Pertanyaan ini didasarkan pada beberapa kesalahpahaman. Pertama, komputer catur terlihat lebih jauh dari satu atau dua lapis di depan: bahkan lima tahun yang lalu pada laptop biasa, program catur yang biasa terlihat 15-16 lapis di depan, dan 25+ di jalur kritis. Kedua, definisi "sempurna" sebagai "selalu menang" tidak dapat dicapai, seperti yang ditunjukkan dalam jawaban. Ketiga, mesin catur tidak "memprediksi" gerakan: mereka menghitung dan memainkan gerakan yang baik terhadap kemungkinan respons apa pun.
David Richerby

Jawaban:

13

Pertanyaan Anda mirip dengan kastanye tua: "Apa yang terjadi ketika suatu kekuatan yang tak tertahankan bertemu dengan objek yang tak tergoyahkan?" Masalahnya ada pada pertanyaan itu sendiri: dua entitas seperti yang dijelaskan tidak dapat ada di alam semesta yang konsisten secara logis sama. Algoritme optimal Anda, algoritme yang selalu menang, tidak dapat dimainkan oleh kedua belah pihak dalam permainan di mana satu sisi harus menang dan yang lain harus dengan definisi kalah. Dengan demikian, algoritma optimal Anda sebagaimana didefinisikan tidak dapat ada.

Kyle Jones
sumber
3
Yah itu bisa, misalnya, suatu algoritma yang memungkinkan pemain pertama menang. Ini berarti bermain dulu memiliki keunggulan. Atau mungkin algoritma optimal hanya memungkinkan pemain kedua menang. Ini akan memberi pemain kedua keuntungan. Kemungkinan ketiga adalah algoritma yang memungkinkan salah satu pemain untuk selalu memaksakan hasil imbang, meskipun tidak menjamin kemenangan (karena OP ingin tahu, inilah yang terjadi, misalnya, jika kedua pemain memainkan strategi kemenangan yang sama , jika tidak ada keuntungan dalam bermain pertama atau kedua).
Realz Slaw
3
@Realz Nah, ya, jika Anda mengubah definisi "algoritma optimal" maka Anda dapat membuktikan apa pun yang Anda suka. Saya menggunakan definisi yang diminta penanya untuk kami gunakan.
Kyle Jones
Ini adalah jawaban yang saya coba untuk keluar dari orang. Tidak mungkin ada algoritma yang selalu menang karena ini adalah permainan yang terdiri dari 2 pemain sehingga tidak ada algoritma yang dapat bekerja karena kedua pemain dapat memiliki algoritma yang sama sehingga setidaknya salah satu dari keduanya dipaksa untuk tidak menang (kalah atau seri) . Saya mengajukan pertanyaan yang sama kepada guru saya dan kami perlu banyak bicara untuk sampai pada kesimpulan ini
John Demetriou
3
@ JohnDemetriou Masalahnya adalah kesimpulan itu salah . Catur bukan permainan simetris karena keuntungan penggerak pertama - sangat mungkin bahwa ada algoritma optimal yang memungkinkan Putih untuk bermain dan menang, tetapi Hitam tidak dapat menggunakan algoritma itu karena alasan sederhana bahwa ia bukan Putih!
Steven Stadnicki
Perlu juga, saya perhatikan, bahwa menjadi yang pertama sebenarnya bukan suatu keuntungan dan bahwa sebenarnya ada algoritma yang selalu memungkinkan Hitam menang melawan permainan terbaik oleh White - tetapi harus segera jelas bahwa tidak ada algoritma yang selalu bisa memungkinkan seseorang untuk menang apakah Hitam atau Putih. Inilah sebabnya mengapa orang berbicara tentang 'hasil terbaik', karena 'menang dari kedua belah pihak' tidak mungkin.
Steven Stadnicki
23

Pertama-tama, saya percaya bahwa algoritma catur terlihat lebih dari 2, meskipun mereka tidak mempertimbangkan semua kemungkinan yang berbeda; pemangkasan pohon pencarian sangat penting untuk menghindari ledakan kombinatorial dalam jumlah gerakan yang mungkin.

Untuk permainan seperti catur, ada tiga kemungkinan identitas pemenang: pemain 1 memiliki strategi kemenangan, atau pemain 2 memiliki strategi kemenangan, atau kedua pemain menggambar di bawah permainan optimal. Tidak diketahui yang merupakan kasus untuk permainan catur. Namun, karena catur adalah permainan yang terbatas, ada algoritma komputer, yang terdiri dari meja yang sangat besar, yang memainkan catur secara optimal.

Tentu saja, algoritma seperti itu tidak praktis. Tetapi untuk beberapa gim yang lebih sederhana, "nilai" gim tersebut (yang dimenangkan pemain, jika ada) telah ditentukan, dan algoritma optimal telah dirancang. Game seperti itu dikenal sebagai game yang dipecahkan .

Subjek matematika yang berhubungan dengan (yang dikenal sebagai) game kombinatorial adalah teori permainan kombinatorial . Matematikawan telah mengembangkan metode rekursif untuk menentukan nilai permainan mengingat grafik permainan, yang mencakup semua posisi dan gerakan yang diperbolehkan. Anda harus dapat menemukan deskripsi algoritma ini di entri Wikipedia atau catatan kuliah apa pun tentang subjek tersebut.

Yuval Filmus
sumber
ya, memang, tapi saya mencoba menjawab setiap jawaban dengan pertanyaan lain, apa yang terjadi ketika kedua pemain bermain dengan algoritma optimal ???? apa yang terjadi jika seorang pemain menemukan cara untuk mengalahkan algoritma optimal?
John Demetriou
11
@JohnDemetriou Saat kedua pemain bermain secara optimal, Anda akan mendapatkan hasil. Hasil itu disebut nilai permainan. Jika catur putih menang, itu berarti bahwa tidak ada yang hitam bisa lakukan bisa mengalahkan pemain putih bermain optimal. White secara efektif memiliki buku yang sangat besar (atau mampu menghasilkan perpindahan dari buku semacam itu secara komputasional) yang berisi penghitung sempurna untuk gerakan apa pun yang dapat dibuat oleh hitam dalam situasi apa pun yang mungkin terjadi sejak awal permainan. BTW, chillax pada tanda tanya. Satu per kalimat sudah cukup.
rrenaud
Saya minta maaf untuk tanda tanya. Itu hanya cara saya mengetik secara umum. Bagaimana jika catur adalah kemenangan paling optimal. Jika putih dan hitam memiliki buku yang sama dan memiliki counter yang sama? Lalu apa yang akan terjadi?
John Demetriou
1
@JohnDemetriou "Optimal" berarti "yang terbaik". Jika konsekuensi matematika dari aturan catur adalah bahwa hitam terbaik yang mungkin dapat dilakukan terhadap putih optimal adalah draw (atau bahkan hanya dapat menunda kemenangan putih selama mungkin), maka algoritma optimal untuk hitam adalah yang mencapai itu, dan mampu menang melawan lawan yang paling tidak optimal.
Ben
1
@ JohnDemetriou Ada kemungkinan bahwa ada algoritma yang selalu menang sebagai Putih ; jelas bahwa algoritma tidak selalu dapat menang sebagai Hitam karena alasan yang telah diuraikan (karena itu akan bermain melawan dirinya sendiri). Bahkan mungkin saja ternyata catur Black 'win' dimainkan dengan sempurna, dan ada algoritma yang menjamin kemenangan bagi Black melawan oposisi apa pun. Jika Anda maksudkan 'suatu algoritma yang selalu menang dari kedua sisi' maka saya sarankan menggunakan terminologi itu; 'optimal' sudah memiliki makna yang jelas.
Steven Stadnicki
8

Pertama-tama, algoritma catur yang baik terlihat lebih dari 1 atau 2 level. Alih-alih menggunakan pencarian pohon naif, mereka melakukan pemangkasan alpha-beta untuk mempersempit jumlah opsi yang perlu dipertimbangkan. Perhatikan bahwa untuk permainan pembuka dan akhir, basis data gerakan yang besar digunakan karena memiliki kinerja yang lebih baik daripada penelusuran pohon, yang digunakan di tengah-tengah permainan.

Untuk pertanyaan: apa yang Anda tanyakan saya yakin adalah "Apakah catur bisa dipecahkan ?". Secara hipotesis, meskipun pendapat berbeda tentang apakah hasil ini akan dapat dicapai dalam waktu dekat. Checker diselesaikan pada tahun 2007 misalnya, tetapi memiliki posisi yang jauh lebih sedikit (sekitar akar kuadrat dari angka dalam catur). Lihat artikel Wikipedia untuk informasi lebih lanjut.

Kebetulan, AI catur terbaik saat ini hampir selalu mengalahkan atau menggambar dengan juara dunia; jadi walaupun saat ini tidak sempurna, algoritme setidaknya cukup bagus!

sjmeverett
sumber
6

Pada prinsipnya, catur dapat dipecahkan seperti game lainnya. Namun, seperti yang ditunjukkan oleh jawaban lain, ini tidak diharapkan terjadi dalam waktu dekat.

Sunting: telah ditunjukkan dalam komentar bahwa [1] adalah tipuan jadi abaikan sisa jawaban ini.

Yang mengatakan, ada beberapa perkembangan terakhir dalam arah ini. [1] mengklaim telah menunjukkan bahwa pembukaan catur yang disebut King's Gambit telah terpecahkan : hanya ada satu gerakan yang menarik bagi Putih, sementara semua gerakan pembukaan lainnya mengarah pada kemenangan bagi Hitam. Perhatikan bahwa [1] tidak menjelajahi pohon permainan secara mendalam, tetapi hanya mengklaim hasil ini bertahan dengan probabilitas tinggi.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

Peter
sumber
1
Artikel yang sangat menarik!
Paresh
Maka itu bukan algoritma yang optimal. Saya bertanya apakah suatu algoritma optimal dapat pernah ada (jika kita memiliki kekuatan komputasi)
John Demetriou
1
Benar, dan mempertimbangkan definisi Anda tentang "algoritma optimal" sebagai algoritma yang selalu menang, algoritma seperti itu tidak bisa ada untuk kedua pemain, Hitam dan Putih. Selain dari pohon permainan yang lebih besar (tetapi terbatas), tidak ada yang istimewa tentang catur dalam hal ini dibandingkan dengan permainan lain seperti misalnya Hex, yang solusinya sudah diketahui: Jika pemain pertama menggunakan strategi optimal (dikenal) untuk bermain Hex , maka pemain pertama selalu menang, tidak masalah algoritma apa yang digunakan oleh pemain kedua.
Peter
Artikel King's Gambit yang dipecahkan ternyata hanya tipuan. Perhatikan artikel ini dimulai "Pada 31 Maret penulis program Rybka, Vasik Rajlich, dan keluarganya pindah dari Warsawa, Polandia ke apartemen baru di Budapest, Hongaria. Keesokan harinya, terlepas dari kesibukan kotak dan pengaturan yang bergerak. telepon dan koneksi Internet, Vas, setuju untuk wawancara berikut "- dengan kata lain, ini pada 1 April ...
Joe K
-1

Apakah mungkin untuk selalu memenangkan permainan catur atau tidak tergantung pada aturan permainan. Namun, ada teknik / algoritma bernama Minimax (untuk detail, lihat https://en.wikipedia.org/wiki/Minimax ). Algoritme terdiri dari upaya untuk memprediksi pemain mana yang unggul dalam skenario yang berbeda dengan fungsi rekursif. Berikut ini adalah penjelasan yang jelas tentang cara kerjanya dengan permainan yang lebih sederhana: Tic-tac-toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13 .

Luke the Geek
sumber
Meskipun jawaban lain tidak secara eksplisit merujuk pada minimax, beberapa memang merujuk pada tautan yang akhirnya mengarah pada mereka atau pemangkasan alpha-beta, suatu algoritma untuk mengimplementasikan minimax lebih efisien. Apa yang ditambahkan jawaban ini yang belum dikatakan?
Kadal diskrit
-3

akan menambahkan jawaban lain yang menekankan ruang keadaan masif, tidak benar-benar dikonseptualisasikan dalam pertanyaan atau ditunjukkan dalam jawaban lain. harus tidak setuju dengan premis Anda:

Katakanlah kita memiliki kekuatan komputasi untuk mengembangkan algoritma yang memprediksi semua kemungkinan pergerakan lawan dalam permainan catur.

lihat info di kertas shannons 1950, "Programming a Computer for Playing Chess" yang memperkenalkan bidang permainan / algoritma catur berbasis komputer dan yang analisisnya pada dasarnya tidak berubah & masih bersuara (bahkan oleh revolusi komputer berikutnya dan hukum Moor ). itu memperkirakan jumlah gerakan. itu benar-benar astronomi. dalam kisaran "tidak pernah dalam perangkat keras yang mungkin bahkan dengan kemajuan revolusioner yang tak terduga".

ini adalah fakta psikologis yang terdokumentasi [3], mungkin salah satu dari banyak bias psikologis [2], bahwa manusia memiliki kesulitan memahami angka sebesar ini. lihat juga pemikiran kontrafaktual . [4] sementara superkomputer menghitung masalah besar, itu tidak kontroversial dalam jangkauan superkomputer mana pun yang saat ini dibangun atau pernah dapat dibangun. (dan banyak penggemar catur akan membantah "ledakan kombinatorial" ini dalam kemungkinan pergerakan / posisi adalah aspek intrinsik dari "rasa" permainan yang tampaknya dirancang dengan sengaja ke dalam permainan ribuan tahun yang lalu).

oleh karena itu catur pada dasarnya berbeda dari beberapa gim yang memiliki ruang keadaan "dipecahkan" yang lebih kecil [di mana ada beberapa studi dalam ilmu komputer & teori gim dll] dan dalam beberapa cara kunci tidak dapat dievaluasi dalam kerangka itu.

Allis juga memperkirakan kompleksitas permainan-pohon setidaknya 10123, "berdasarkan faktor percabangan rata-rata 35 dan panjang permainan rata-rata 80". Sebagai perbandingan, jumlah atom di alam semesta yang dapat diamati, yang sering dibandingkan, diperkirakan antara4×1079 dan 1081.

sekarang, yang mengatakan, bisa dibayangkan (tetapi tidak mungkin) bahwa mungkin ada wawasan teoritis ke dalam permainan yang dapat digunakan untuk memangkas ruang pencarian secara substansial. yang telah terjadi sejak 1950 tetapi tidak benar-benar dengan cara terobosan fundamental.

Lihat juga

[1] apa kompleksitas komputasional dalam memecahkan catur, tcs.se

[2] bias manusia dalam penilaian dan pengambilan keputusan

[3] Siswa psikologi mempublikasikan penelitian tentang angka konseptualisasi

[4] pemikiran kontrafaktual

vzn
sumber
baik secara teori pertanyaan saya dimulai sebagai katakanlah kita memiliki kekuatan komputasi, kami menggabungkan setengah komputer di dunia untuk bekerja sebagai cluster untuk putih dan setengah lainnya untuk hitam ....
John Demetriou
1
Bung, itu berlaku bahkan jika menghubungkan setiap superkomputer yang sekarang ada, atau pernah ada. pertanyaan Anda kemudian berjumlah "dalam teori, jika teori itu salah ..." teori (termasuk dari fisika) pada dasarnya mengatakan Anda tidak bisa menghitung lebih banyak jalur (jauh) daripada ada atom di alam semesta, sekarang atau di masa depan .. .
vzn
3
benar, tetapi pertanyaan dimulai dengan BIARKAN KATAKAN KITA MEMILIKI KEKUATAN KOMPUTASI, dapatkah ini dilakukan? ini pertanyaan sebenarnya, jika kita memiliki kekuatan, dapatkah ada algoritma?
John Demetriou
1 untuk menyatakan fakta bahwa secara fisik tidak mungkin untuk mencapai kekuatan komputasi yang dibutuhkan untuk menyelesaikan catur dengan tepat. Juga, tidak tahu mengapa semua -1 dengan jawaban ini, saya pikir itu adil dan menambah wawasan yang baik untuk jawaban lainnya.
Alejandro Piad