Bagaimana mesin catur “berpikir”?

Yang ingin saya ketahui adalah bagaimana mesin diprogram untuk menemukan gerakan. Saya yakin mereka pertama-tama menghitung garis yang paling memaksa seperti menangkap dan memeriksa. Tapi bagaimana dengan gerakan posisi halus dan dalam? Mereka tampaknya menemukan mereka dengan sangat cepat (Secara umum. Tentu saja mereka kehilangan gerakan seperti itu sekarang dan kemudian). Seperti, bagaimana mereka diprogram untuk mencari gerakan diam / ide posisi? Mereka tidak bisa begitu saja memaksa setiap gerakan, karena itu akan memakan waktu terlalu lama, jadi harus ada cara cerdas bagi mereka untuk tiba di gerakan terbaik dengan sangat cepat. Saya tertarik mengetahui hal ini karena saya pikir itu akan membantu pemain untuk memikirkan papan di dunia nyata juga.

Secara umum mesin catur menggunakan pohon keputusan. Akar pohon adalah posisi saat ini dan memiliki simpul anak untuk setiap posisi yang dapat dibuat dengan membuat langkah hukum. Masing-masing node ini pada gilirannya memiliki simpul anak untuk posisi yang dapat dicapai dengan membuat langkah hukum dari mereka. Mesin mendorong pohon ke kedalaman yang ditentukan oleh kemampuannya dan waktu yang diizinkan untuk "berpikir". Posisi yang dapat dijangkau dalam lebih dari satu cara hanya direferensikan silang sehingga mereka tidak harus dipertimbangkan lebih dari sekali. Setelah pohon dibuat, komputer menggunakan seperangkat aturan tertimbang untuk menganalisis posisi akhir di pohon dan mulai menghapus orang-orang yang tidak diinginkan atau yang dapat dicegah oleh lawan. Pohon ditebang dengan cara ini sampai hanya satu langkah yang tersisa dan komputer melakukan gerakan itu.

http://www.chess.com/blog/zaifrun memiliki seri atau artikel tentang cara membuat mesin catur jika Anda ingin melihat lebih dalam bagaimana mereka bekerja.

Anda mengajukan pertanyaan yang cukup rumit, tetapi baik untuk kembali ke dasar. Ada beberapa konsep yang perlu dipertimbangkan:

Evaluasi

Jika seorang pemain (nyata) ditunjukkan posisi dan bertanya "siapa yang memenangkan permainan ini?", Bagaimana mereka memutuskan? Kemungkinan besar, mereka akan memeriksa beberapa hal dasar, seperti: perbedaan bahan, sejauh mana potongan telah dikembangkan atau diposisikan "baik", pion berlipat ganda / terisolasi / terhubung / lulus, file terbuka (terkontrol), seberapa jauh papan pionnya.

Sekarang, jika Anda harus, Anda dapat menemukan cara sistematis untuk menghitung skor posisi berdasarkan di atas. Anda dapat memutuskan, misalnya, bahwa gadai bernilai 1 poin, dan gadai yang lulus bernilai 0,3 poin lebih banyak. Gadai yang terisolasi atau berlipat ganda mungkin bernilai sedikit lebih rendah, dll. Jika Anda menjumlahkan semuanya, Anda mendapatkan nilai perkiraan untuk posisi langsung yang ada.

Ini dikenal sebagai evaluasi , dan pada dasarnya semua program catur memiliki cara untuk mengevaluasi posisi (mengabaikan mesin catur AI baru yang biasanya sangat lemah).

Tapi bagaimana dengan gerakan posisi halus dan dalam?

Yah, kita baru saja menggaruk permukaan penilaian posisi. Implementasi aktual dari fungsi evaluasi bisa menjadi sederhana, untuk memungkinkan lebih banyak posisi dievaluasi per detik (walaupun dengan cara kasar), atau lebih kompleks, yang menyebabkan lebih sedikit posisi dievaluasi, tetapi dengan tingkat kepercayaan yang lebih tinggi. Bukan hal yang aneh jika fungsi evaluasi memperhitungkan ratusan atau bahkan ribuan informasi yang terpisah.

Pencarian

Saya secara khusus meninggalkan sesuatu dari atas, yang akan segera dipikirkan oleh sebagian besar pemain nyata - adakah cara untuk segera memenangkan permainan untuk kedua sisi? Adakah pasangan atau potongan "gantung" terlihat? Meskipun mudah untuk menyepelekan hal ini, itu tidak berarti apa-apa.

Apa artinya bagi seorang pemain untuk memiliki kepercayaan penuh dalam kombinasi? Pada akhirnya, itu bermuara pada telah menghitung semua opsi. Pemain sungguhan biasanya tidak akan melakukan ini (kecuali untuk hal-hal sepele atau sangat terpaksa), sebagian besar waktu kita hanya akan mempertimbangkan beberapa opsi, dan mengesampingkan orang lain yang tampaknya "tidak konstruktif" atau jelas menyebabkan kerugian . Kita sering membuat kesalahan selama perhitungan ini, misalnya kita mungkin menyadari bahwa perubahan dalam perintah bergerak membuat ancaman menguap, dll. Intinya adalah bahwa untuk benar-benar yakin kombinasi, Anda benar-benar perlu menghitung semua jalan ke kesimpulannya, dengan asumsi masing-masing pemain hanya akan membuat langkah terbaik yang tersedia bagi mereka (ini disebut "min / max").

Sekarang, mengingat catur memiliki ruang pencarian yang jauh lebih besar (inilah yang "semua kemungkinan pergerakan di masa depan" disebut) daripada apa yang layak untuk dihitung oleh komputer, kompromi perlu dilakukan. Sama seperti manusia, komputer dapat memutuskan untuk mengabaikan seluruh alur pemikiran berdasarkan kriteria tertentu. Ini dikenal sebagai heuristik . Penting untuk dicatat bahwa walaupun Anda hanya dapat benar-benar yakin akan kombinasi jika Anda memaksakannya, fungsi evaluasi yang kompleks sering kali dapat mendeteksi keberadaan ancaman (misalnya kita dapat menghitung garpu, peluang tusuk, dll, untuk memandu pencarian ke arah itu. ).

Pada akhirnya, meskipun komputer sangat cepat, heuristiklah yang memungkinkan mereka menghitung dengan sangat dalam. Yang mengatakan, Anda mungkin terkejut betapa mesin modern menghitung sepenuhnya, biasanya itu di luar 3 bergerak, bahkan dalam permainan cepat.

Kesimpulan / kombinasikan semuanya

Jadi, untuk meringkas - fungsi evaluasi memiliki banyak kecerdasan yang dibangun di dalamnya (yaitu mereka mempertimbangkan lebih banyak hal daripada pemain manusia rata-rata), heuristik memungkinkan komputer untuk menyisihkan garis pemikiran yang diputuskan mungkin tidak akan berakhir dengan baik, dan komputer sangat, sangat cepat. Tambahkan mereka, dan mereka cukup sulit dikalahkan.

Saya setuju dengan jawabannya.

Saya ingat GM Roman Dzindzichashvili membicarakannya, di salah satu video laboratorium Roman , saya tidak ingat video apa itu (jika ada yang tahu detailnya silakan edit jawaban saya).

Roman mengatakan bahwa pengembang mesin Fritz adalah temannya. Jadi Roman menguji Fritz untuk melihat seberapa bagusnya, dan pengembang memberi tahu Roman bahwa agar fritz membuat keputusan yang rumit (misalnya mengorbankan material sebagai imbalan atas keuntungan posisi), mereka harus mengubah nilai kepingan, seperti memberi tahu program. bahwa seorang uskup yang buruk bernilai 1 poin, seorang uskup di diagonal terbuka bernilai 7 poin, ksatria bernilai 5 poin di posisi dekat ...

Saya tidak tahu angka pasti untuk masing-masing bagian tetapi itulah cara kerjanya, dan sekarang mesin Anda tidak akan memiliki masalah mengorbankan uskup yang buruk atau apa pun jika Anda bisa memberi tahu dia nilai setiap bagian di setiap posisi.

EDIT

Lihat juga Wiki Pemrograman Catur .

Tidak mungkin bagi komputer untuk melihat cukup dalam (25 lapis dan lebih) dan memeriksa setiap gerakan yang mungkin.

Apa yang memungkinkan adalah teknik yang disebut pemangkasan Alpha-beta yang berarti bahwa komputer, mirip dengan manusia (tetapi jauh lebih baik) hanya mengikuti kelanjutan yang menjanjikan.

Mereka mengevaluasi posisi terus-menerus (berdasarkan beberapa aturan yang dibuat sebelumnya, menilai bahan, keselamatan raja, aktivitas, struktur gadai dll) dan melihat variasi yang tampaknya mengarahkan mereka ke posisi terbaik.

Masih dekat dengan keajaiban bagaimana mereka berhasil melakukannya dengan cukup efisien untuk mengevaluasi jutaan posisi ini dalam sedetik.

Jadi untuk meringkas - Anda benar, mereka tidak dapat melihat semua gerakan jika mereka bermain catur strategis, tetapi mereka dapat dengan cepat melihat gerakan yang layak. Masalahnya masih dengan rencana jangka panjang dan cakrawala yang dapat mereka lihat, tetapi ini sedang dikerjakan (Rybka menganalisis lebih lambat, tetapi memainkan catur lebih banyak posisi, sementara Houdini romantis dengan 'hati mekanis' yang menghitung lebih banyak gerakan dan bermain lebih agresif). Bahkan komputer memiliki gaya mereka sendiri!

Pemangkasan alfa-beta berarti bahwa jika Anda menemukan garis yang ternyata buruk bagi Anda, Anda berhenti melihat calon yang bergerak, dan alih-alih mencoba yang lain. Ini adalah jenis pemangkasan mundur yang berarti Anda tidak akan pernah melewatkan langkah yang baik sebagai hasilnya. Pemangkasan ke depan, sebaliknya, lebih didasarkan pada dugaan. Pemangkasan yang sia-sia, pengurangan gerakan lambat, dan pisau cukur adalah jenis pemangkasan ke depan, dan semua bergantung pada perasaan programmer untuk jenis gerakan apa yang harus dipertimbangkan. Sebuah program yang melakukan banyak pemangkasan ke depan mungkin kehilangan pengorbanan mengejutkan yang mengarah ke jodoh, tetapi di sisi lain, itu menghilangkan banyak gerakan yang benar-benar buruk, dan dengan demikian bisa lebih dalam dalam melihat gerakan yang disukai.

Sebagian besar mesin mencari beberapa langkah pertama pada kedalaman penuh memeriksa semua kemungkinan. Jika tidak ada gerakan yang gagal tinggi (yaitu tampak jelas lebih buruk daripada langkah yang sudah Anda pertimbangkan), Anda perluas pencarian lebih sedikit. Secara umum, Anda terus menjelajahi setiap baris sampai Anda mencapai posisi diam (tanpa cek, menangkap, ancaman pasangan, dll.), Dan kemudian melakukan evaluasi Anda. Pergerakan tenang mungkin tidak dipertimbangkan ketika mereka berada jauh di dalam pohon pencarian, tetapi begitu Anda sampai ke posisi aktual dalam permainan, mesin melihat semua gerakan, tenang dan tajam. Anda benar-benar dapat melihat ini di output mesin kadang-kadang, ketika sebuah mesin tiba-tiba memilih langkah yang tidak mempertimbangkan beberapa langkah mundur.

Mesin menghitung dengan sangat cepat sehingga tidak terlalu penting bagi mereka untuk mempertimbangkan langkah mana yang harus dilihat pada awalnya, tetapi bagi manusia ini adalah pertanyaan kunci. Jonathan Tisdall mencoba menjawab ini dalam bukunya, Tingkatkan Catur Anda Sekarang. Saat Anda menyerang, ia menyarankan Anda untuk melihat gerakan paling kejam terlebih dahulu. Ketika Anda bertahan, Anda melihat garis yang paling sulit terlebih dahulu. Ia juga mengutip aturan praktis posisi (mis. Sentralisasi, koordinasi) ketika memutuskan gerakan mana yang harus dilihat pertama kali.

Buku-buku lain yang mungkin relevan adalah Invisible Chess Moves Emmanuel Neimann dan Forcing Chess Moves karya Charles Hertan, keduanya berdebat tentang pentingnya mempertimbangkan gerakan tidak terduga atau mengejutkan di posisi yang tajam. Hertan bahkan berbicara tentang pengembangan 'mata komputer' untuk taktik semacam itu.