Contoh Strategi Optimal yang Ditemukan Komputer dalam Game

8

Saya mencari contoh dalam permainan seperti Go, Chess, dan Backgammon, di mana langkah yang diyakini-optimal ternyata tidak optimal ketika komputer menemukan strategi yang lebih baik.

gt.game-theory board-games combinatorial-game-theory fkenter
sumber
8
Tidak ada yang namanya "lebih optimal".
Jeffε
1
Anda tidak bisa mengatakan itu strategi "optimal", tetapi komputer tampaknya telah membuat perbedaan besar dalam pembukaan catur.
Peter Shor

Jawaban:

12

Contoh yang paling dikenal mungkin adalah dam (juga dikenal sebagai draft ), yang telah diselesaikan baru-baru ini pada tahun 2007 (permainan ini seri). Contoh lain tercantum di halaman Wikipedia pada permainan yang diselesaikan ; terkemuka di antara mereka menghubungkan empat dan sembilan pria . Selain itu, beberapa permainan catur telah diselesaikan.

Ini mungkin sepertinya bukan jawaban untuk pertanyaan Anda, tetapi jika seorang ahli (seperti Marion Tinsley ) kehilangan program komputer, maka komputer itu pasti telah menemukan langkah "lebih optimal".

Yuval Filmus
sumber
8

Lihat Wolfe dan Berlekamp - Matematika Go . Menggunakan teori permainan Conway, mereka menunjukkan bagaimana menganalisis jenis permainan Go tertentu. Solusi mereka ternyata jauh lebih baik daripada solusi yang diberikan oleh pemain Go top. (Tidak cukup jawaban untuk masalah Anda, karena solusi terakhir itu mungkin tidak pernah diklaim optimal.)

Neal Young
sumber
1
Saya bukan ahli Go, tetapi kesan saya tentang karya Math Go adalah bahwa matematika itu jauh lebih menarik daripada Go yang menarik, dan bahwa struktur yang mereka temukan - sebagian besar - tidak benar-benar berkorelasi dengan struktur yang terjadi dalam game sebenarnya. Mungkin seseorang dengan lebih banyak pengalaman Go dapat membicarakan hal ini?
Steven Stadnicki
1
Ya, itu kurang lebih pemahaman saya juga.
Neal Young
1

Teknik endgame catur telah sangat ditingkatkan dengan munculnya tablase endgame. Bilah tab endgame adalah tabel pencarian yang memecahkan catur ketika tidak ada lebih dari (saat ini) tujuh buah di papan tulis. Ini adalah basis data online yang pernah saya gunakan di masa lalu yang berfungsi hingga enam buah.

Secara algoritmik, tabulasi ini tidak terlalu menarik; mereka sebagian besar dihasilkan oleh kekuatan kasar. Namun, mereka telah berkontribusi pada beberapa aspek dari teori endgame. Wikipedia memiliki ringkasan yang bagus tentang beberapa hal menarik di sini.

Penemuan ini juga memiliki implikasi untuk "aturan lima puluh langkah," yang menyatakan bahwa setelah lima puluh bergerak tanpa penangkapan atau gadai, pemain dapat mengklaim hasil seri. Bahkan sebelum analisis komputer, beberapa permainan akhir dianggap mengambil lebih dari lima puluh gerakan, dan aturannya sedikit diperluas dalam keadaan itu (mungkin yang paling terkenal adalah rook dan uskup vs rook endgame ). Karena jumlah posisi yang membutuhkan gerakan ini menjadi lebih besar, ekstensi ini dicabut dan aturan 50 langkah normal diaktifkan kembali dalam semua kasus. Analisis modern telah menunjukkan bahwa beberapa permainan akhir mengambil beberapa ratus langkah .

Ini adalah artikel lain yang menarik, merangkum beberapa efek dari tablebase tujuh potong pada teori endgame. Saya sangat suka mutual zugzwang yang ditunjukkan di posisi terakhir.

SamM
sumber
1

Ini bukan "strategi permainan" yang tepat, namun pada tahun 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, dan John Dethridge menemukan bahwa semua posisi kubus Rubik dapat diselesaikan dengan maksimum 20 putaran wajah menggunakan bukti yang dibantu komputer [1] ... hasil yang bagus.

Kode sumber beranotasi tersedia di http://cube20.org/src/ .

Jumlah rata-rata gerakan yang diambil dengan metode penyelesaian standar adalah ~ 50-60, tetapi ada juga hall of fame "gerakan paling sedikit" resmi :

  #player          #moves
1 Tomoaki Okayama  20  Japan    Czech Open 2012     
2 Moritz Karl      21  Germany  BW Open 2013     
3 István Kocza     22  Hungary  Czech Open 2010     
  Jimmy Coll       22  Belgium  Barcelona Open 2009     
5 Adrian Lehmann   23  Germany  German Open 2013

(perhatikan bahwa batas atas 20 hanya tercapai satu kali pada tahun 2012 ... jadi dalam kejuaraan kubus Rubik manusia jauh dari bermain "strategi optimal" :)

[1] Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge: Diameter Grup Kubus Rubik Adalah Dua Puluh. SIAM J. Discrete Math. 27 (2): 1082-1105 (2013)

Marzio De Biasi
sumber