Pendekatan terbaik untuk menulis mesin catur? [Tutup]

Saya seorang penggemar catur dan seorang programmer. Baru-baru ini saya memutuskan untuk mulai membuat mesin catur menggunakan catur dan pengetahuan pemrograman saya. Jadi inilah pertanyaan saya:

Bahasa apa (saya terbiasa dengan Java, C ++ dan Python) dan metodologi yang harus saya adaptasi saat menulis mesin catur?

Sedikit bimbingan akan sangat dihargai.

Edit:

Jadi saya memutuskan untuk membuatnya dalam JavaScript. Saya mengunduh UI Catur ini dari github dan sekarang saya siap! Langkah pertama saya adalah menulis langkah hukum untuk itu. Jadi, adakah yang bisa mengarahkan saya ke arah yang benar? (Saya baru mengenal jQuery tetapi memiliki banyak pengalaman pemrograman).

PS: Saya tidak mencoba membuat mesin yang sangat efisien (saya tahu jalannya terlalu sulit), saya hanya ingin membiasakan diri dengan proses dan mempelajari beberapa teknik baru di sepanjang jalan.

2072-dinilai pemain catur di sini. Saya membuat situs web ini dalam JavaScript murni selama akhir pekan. Ini bukan mesin catur (saya mendesainnya untuk membuat posisi pembukaan yang menghibur sebagai semacam mesin Chess960 yang sesat), tetapi ini adalah titik awal. Kode sumber ada di sini .

Ada banyak komplikasi yang terlibat dalam pembuatan papan fungsional. Ini termasuk:

• Pertama, mencari tahu cara mewakili langkah hukum dasar. Anda harus melakukan matematika dengan koordinat awal dan akhir. Misalnya, dengan gerakan rook, salah satu koordinat harus sama sebelum dan sesudah. Dengan gerakan ksatria, jumlah nilai absolut dari perubahan koordinat harus menjadi 3, dan kedua koordinat harus berubah. Dengan gerakan uskup, jumlah koordinat tetap sama, atau keduanya meningkat dengan jumlah yang sama. Pion adalah yang paling sulit karena Anda tidak hanya harus mencari tahu apakah mereka dapat memindahkan dua kotak atau satu (periksa baris dan warna alih-alih menyimpan berapa banyak gerakan yang telah mereka buat) tetapi juga harus berurusan dengan seluruh tangkapan - secara diagonal, pindahkan hal-ke depan.
• Menangkap adalah tantangan karena bidak dan cek. Anda tidak bisa hanya mengatakan bahwa jika sepotong pindah ke kotak sepotong lain, maka itu adalah tangkapan. Lagipula, pion tidak bisa bergerak ke kotak lain untuk ditangkap - mereka punya cara menangkap khusus.
• Anda harus mencari cara yang efisien untuk melihat apakah potongan musuh menghalangi langkah untuk memutuskan apakah itu legal atau tidak.
• Cek itu sulit untuk dihadapi. Setelah setiap gerakan, Anda harus memeriksa semua kotak yang dapat dituju oleh musuh dan melihat apakah salah satu dari mereka melibatkan raja Anda, dan jika demikian, ini merupakan tindakan ilegal.
• Castling, en passant, promosi, jalan buntu, undian paksa, pengulangan - tidak ada yang sepele untuk ditangani mengingat skala masalah.

Semua mesin catur bekerja dengan melihat semua (mungkin himpunan bagian yang ditentukan secara heuristik) dari langkah hukum dalam suatu posisi dan mengevaluasi angka untuk mewakili nilai relatif mereka dengan membuat gerakan tersebut dan secara rekursif melakukan hal yang sama untuk posisi yang dihasilkan. Masalah kembar Anda di sini adalah

• Cara menyimpan data ini secara efisien
• Bagaimana cara melanjutkan pencarian rekursif ini - lagipula, Anda tidak bisa membiarkannya berlangsung selamanya, jadi Anda harus memberi batasan dan kemudian mencari tahu bagaimana merancang algoritma Anda untuk melakukan pencarian yang paling optimal dan menyeluruh dalam batas itu. Misalnya, Anda ingin memastikan bahwa setidaknya muncul dengan beberapa evaluasi untuk setiap langkah awal yang mungkin, tetapi Anda mungkin juga ingin itu menghabiskan lebih banyak waktu untuk mengevaluasi langkah-langkah yang lebih menjanjikan daripada memberikan jumlah waktu yang sama untuk setiap gerakan.

Ini semua di atas merancang algoritma di tempat pertama, yang ada banyak informasi tersedia di.

Mengenai bahasa mana yang harus digunakan (walaupun saya kira Anda sudah memutuskan JavaScript), saya pikir itu lebih tergantung pada tujuan Anda daripada yang lain. Saya ingin membuat milik saya online (dan menjadi lebih baik di JavaScript), jadi JavaScript adalah pilihan saya. Bahasa pemrograman berorientasi objek apa pun akan melakukannya.

Setelah Anda merasa nyaman dengan apa yang Anda lakukan, sumber daya berikut mungkin akan terbukti sangat membantu:

• Wiki Pemrograman Catur
• Forum Pemrograman Catur
• StockFish di Github

Semoga berhasil!

Masalah dengan "program catur" sebagai konsep adalah bahwa ada banyak bagian yang dapat menyerap banyak waktu, dan belum tentu menarik bagi Anda saat ini. Anda dapat menghabiskan waktu bertahun-tahun hanya bekerja pada grafik, atau pencarian alpha-beta, atau visualisasi untuk membantu mengembangkan mesin pencari, atau ... yah, ada banyak bagian.

Saya merekomendasikan menemukan program catur open source (pasti ada banyak) dan mulai memperbaiki bagian-bagian yang paling menarik minat Anda. Anda pada akhirnya dapat mengganti seluruh program, satu fungsi pada satu waktu, atau Anda mungkin cukup belajar dan termotivasi untuk membuangnya dan merancang program Anda sendiri dari awal. Bagaimanapun, kuncinya adalah memulai "cahaya" dan mempelajari tali sebelum mencoba merancang seluruh program.

Jika Anda terbiasa dengan aturan catur, titik awal yang baik tentang teknik dasar adalah http://www.frayn.net/beowulf/theory.html Koleksi Bahan dan tautan luas yang dapat Anda temukan di sini: http: // program catur .wikispaces.com / Dan ketiga: Belajar dari kode orang lain. Lihatlah sumber-sumber Crafty . Ini adalah mesin open source terkemuka. Sangat penting untuk memikirkan tentang Uji kasus, untuk melihat apakah Anda melakukan peningkatan: Mulai misalnya dengan beberapa posisi akhir permainan yang mudah sederhana dengan 3 atau 4 angka.

Seperti yang disebutkan, tidak ada yang sangat sulit tentang membangun mesin catur. Mungkin, Anda harus berkonsentrasi pada bagaimana ingin menggunakan dan (berpotensi) menggunakan aplikasi ini karena ini mungkin akan menentukan pilihan bahasa Anda.

Jika ini hanya latihan yang menyenangkan, Anda mungkin ingin membuatnya dalam Javascript dan menyebarkannya sebagai halaman web. Jika Anda tidak pernah ingin membuatnya menjadi permainan catur ahli, setidaknya orang lain akan dapat bermain dengannya dan kode sumbernya.

Jika Anda ingin mempelajari teknologi tertentu secara bersamaan, katakanlah WPF, maka ini mungkin cara yang baik untuk membunuh dua burung dengan satu batu. MVVM mungkin berlebihan untuk aplikasi ini, tetapi Anda setidaknya akan mempelajarinya.

Jika Anda ingin menargetkan perangkat Android, maka Java akan menjadi pilihan yang baik. Demikian pula, Objective-C untuk perangkat iOS.

Panjang dan pendek, pilihan bahasa tidak ada dalam ruang hampa.

Saya berasumsi Anda sudah tahu tentang konsep Min-Max, pohon dan pemangkasan, heuristik dan dasar-dasar lainnya dan apa yang saya tulis di sini hanyalah beberapa detail yang mungkin telah diremehkan.

Saya bersama seorang teman menulis mesin catur kami sendiri beberapa waktu yang lalu. Saya berbagi beberapa masalah dan ide yang kami miliki dan saya harap Anda menemukan mereka berguna.

Karena kami berdua adalah programmer java, bahasa kami berubah menjadi java dan kami mulai dengan pendekatan berorientasi objek. Potongan adalah objek, papan adalah objek, file dan pangkat (baris dan kolom dalam literatur catur) adalah objek. Dan ini salah. Biaya overhead sangat besar dan program ini berjuang untuk melangkah lebih jauh dari 2 gerakan (4 ply) di pohon pencarian.

Jadi dengan beberapa pencarian kami berakhir dengan ide cemerlang (bukan milik kami sekalipun!): Mewakili potongan dan papan sebagai bilangan bulat Panjang (64bit). Ini masuk akal karena papan catur memiliki 64 kotak. Sisanya adalah operasi yang sedikit bijaksana (berjalan sangat dekat dengan cpu = sangat cepat). Sebagai contoh, pertimbangkan bilangan bulat 64 bit biner di mana yang menyajikan kotak di papan yang dapat menyerang bagian Anda. Sekarang jika Anda menjalankan "DAN" logis antara dua angka seperti ini, hasil non-nol menyatakan bahwa Anda memiliki kotak dengan penyerang. Ada beberapa cara melakukan presentasi papan catur dan potongan-potongan, Jadi:

1 - Putuskan tentang Presentasi Dewan Anda

Maka Anda perlu dan membuka basis data. Pembukaan catur entah bagaimana diselesaikan dan sangat disarankan untuk memiliki dan membuka buku. Dalam hal ini, Anda memiliki banyak waktu ekstra dalam permainan blitz.

2 - Temukan sendiri buku pembuka.

Kami melakukan ini, tetapi masih jauh dari baik:

3 - Mesin catur yang baik harus dapat melihat 6 gerakan (12 ply) di depan.

Jadi yang kami lakukan saat itu adalah menggunakan waktu mati (jika itu adalah mesin manusia vs komputer).

4 - Gunakan waktu ketika lawan berpikir untuk membuat beberapa level pohon Anda.

Dan kami masih jauh dari 12 lapisan. Dengan belajar lebih lanjut, kami menemukan beberapa trik! Misalnya disarankan untuk melewati satu lapis pohon dan mulai dari lapisan berikutnya (seperti tidak ada lawan). Idenya adalah bahwa jika suatu langkah sangat bodoh, lalu mengapa membuang waktu dan melihat apa tanggapan lawan terhadap langkah itu. Namun, satu mesin yang bagus harus bisa membedakan antara langkah idiot dan pengorbanan ratu jenius.

5 - Pelajari trik pemrograman untuk masalah khusus ini (catur).

Saya dan teman saya, dalam keadaan ini, masih buruk: / Apa yang bisa kami lakukan - dan kami lakukan sebagian - adalah untuk menyelamatkan posisi yang dihitung. Jika Anda menghitung posisi, maka simpan untuk masa depan! Hal yang sama berlaku untuk loop di pohon pencarian. Intinya adalah untuk menyimpan / mengambil yang efisien:

6 - Simpan data yang Anda hasilkan ... Efisien!

dan akhirnya:

7 - Kode dengan optimasi maksimal.

Masalah ini sangat mahal baik dalam waktu dan memori CPU. Sangat penting untuk menulis kode Anda dengan sangat efisien. Ingatlah bahwa kita berbicara tentang faktor cabang 35. Ini berarti "jika" di suatu tempat dalam heuristik Anda yang 3.3792205e+18tidak berguna , dapat berubah menjadi tidak berguna "jika ada di suatu tempat jauh di dalam pohon pencarian Anda.

Pemrograman catur adalah tantangan yang sangat sangat menarik dan inilah saatnya Anda dapat menguji kemampuan pemrograman Anda dengan serius. Ada beberapa poin lagi yang bisa saya sarankan tetapi saya yakin Anda akan menemukannya sendiri. Ada banyak lagi poin yang saya tidak tahu tetapi Anda dapat menemukannya di internet!

Semoga berhasil dan selamat bersenang - senang!

ps Saya tidak tahu javascript dengan baik tetapi ada sesuatu yang mengatakan kepada saya berdasarkan pada kesulitan masalahnya, mungkin, mengingat semua yang ditawarkan C ++, akan lebih baik untuk menjatuhkan javascript dan melakukannya di C ++.

Sesuai hasil edit Anda, Anda sampai pada tahap mendefinisikan gerakan 'legal'.

Ada dua cara untuk menggambarkan gerakan dalam catur. Notasi deskriptif dan notasi aljabar . Apa yang mungkin Anda inginkan adalah fungsi yang mengambil bagian, posisi awal dan posisi akhir sebagai parameter. misalnya. Knight dari QN1 ke QB2 tidak valid, tetapi Knight dari QN1 ke Q2 valid. Memikirkan hal itu, notasi aljabar mungkin lebih sederhana karena kemampuan untuk dengan mudah menghitung posisi 'relatif'.

Untuk memastikan Anda menulis jumlah kode minimum yang diperlukan, saya akan mulai dengan menulis tes untuk fungsi itu terlebih dahulu . Jika Anda menggunakan notasi aljabar, Anda mungkin tidak perlu tes per potong / mulai / selesai. Buat setiap tes berfungsi, dan nyalakan kembali duplikasi sebelum beralih ke 'langkah' berikutnya. Kode Anda akan berakhir lebih bersih.

Setelah Anda cukup membahas langkah-langkah legal dan ilegal untuk masing-masing bagian, saya akan mulai menambahkan cek untuk variabel lain (seperti memindahkan seorang raja ke kondisi 'memeriksa' dan 'teman').

Saya merekomendasikan qunit untuk tes unit dan melati untuk tes perilaku dalam JavaScript.

Saya sebenarnya telah menulis mesin catur. Persiapkan diri Anda untuk camilan dan mimpi buruk. Ketika teman-teman saya dan saya melakukannya, itu dalam kontes pemrograman waktunya dan bahasa yang kami putuskan untuk digunakan adalah Java. Saya merasa Java atau C adalah pilihan terbaik Anda, tetapi saya melihat bahwa Anda telah memutuskan untuk menggunakan Javascript. Aku tidak bisa mengetuknya karena aku tidak terbiasa dengannya.

Masalah utama di sini adalah bahwa ada begitu banyak skenario pemindahan / kemenangan dengan setiap bagian yang perlu Anda pertanggungjawabkan, jadi saya akan merekomendasikan agar Anda menuliskan semua situasi yang mungkin untuk setiap bagian sebelum Anda benar-benar memulai pengkodean. Hanya melompat tanpa perencanaan akan mengubah proyek menyenangkan ini menjadi tugas yang berulang. Tapi itu benar-benar hal utama. Hanya rencanakan di luar kode terlebih dahulu dan pastikan Anda mendapatkan setiap skenario untuk satu bagian pada satu waktu.

Semoga berhasil

Untuk bagian pengambilan keputusan pemain komputer, saya tidak bisa merekomendasikan cukup buku "Inteligensi Buatan: Pendekatan Modern" (situs web http://aima.cs.berkeley.edu/ ). Tergantung pada latar belakang Anda dalam matematika (teori grafik membantu) itu mungkin sedikit tingkat tinggi, tetapi ditulis sesederhana mungkin hal akademik ini dan berisi ikhtisar yang sangat up-to-date (dan beberapa kedalaman) teknik untuk membuat program memutuskan sesuatu.

Ini akan menunjukkan hal-hal kepada Anda seperti menyatakan tujuan (yaitu skakmat atau nol), mengevaluasi seberapa dekat negara tertentu (tata letak papan) dengan tujuan itu, cara membuat negara berikut yang mungkin berbeda mulai dari yang sekarang, dan bagaimana melintasi apa yang merupakan ruang masalah besar.

Satu hal yang mungkin membantu dalam merancang algoritma AI adalah untuk mengetahui cara memutuskan langkah mana yang akan dimainkan selanjutnya seolah-olah Anda memiliki semua waktu di dunia, mulai dari situasi yang sangat dekat dengan permainan yang dimenangkan. Anda mengoptimalkannya sehingga menemukan solusi dalam jumlah waktu (jam) yang masuk akal, kemudian menemukan cara untuk memilih jalur kemenangan meskipun Anda belum menjelajahi semua hasil, sehingga Anda benar-benar dapat mengganggu "pemikiran" untuk nilai waktu giliran.

Hanya kemudian saya akan melihat mengoptimalkan representasi untuk membuat perhitungan individu lebih cepat, seperti menggunakan bilangan bulat panjang seperti yang disarankan. Tidak peduli seberapa cepat sehingga Anda dapat membuat perbandingan tunggal, jika cara Anda melintasi ruang masalah tidak memiliki heuristik yang baik, perlu waktu lama untuk melakukannya.

Anda dapat benar-benar melakukan apa saja yang Anda inginkan, tetapi ini adalah pemikiran saya tentang masalah ini:

Saya akan menggunakan Java karena memungkinkan Anda untuk menjadi sangat tingkat tinggi, dan memiliki perpustakaan antarmuka pengguna (AWT, Swing) yang dapat Anda gunakan langsung. Anda dapat menggunakan pendekatan berorientasi objek untuk memodelkan papan catur dan potongan-potongan. Objek lain bisa berdiri untuk sejarah bergerak dan mencetak gol. Bahkan pemain bisa menjadi objek, dan kemudian Anda mungkin di masa depan memperluas Playerkelas Anda untuk menyediakan pemain komputer cerdas buatan.

Anda mungkin ingin melihat model-view-controller (MVC) karena itu adalah pendekatan yang sangat bagus dalam hal ini untuk mengikat objek model Anda (model domain) ke antarmuka pengguna (tampilan) dan untuk memungkinkan pengguna untuk memanipulasi model (melalui controller).

Anda mungkin juga ingin menerapkan pengembangan yang digerakkan oleh pengujian , yang tidak hanya memastikan bahwa semua metode berperilaku seperti yang Anda harapkan, tetapi juga memaksa Anda untuk menulis kode modular yang dapat diuji.

Aturan catur itu sendiri cukup sederhana. Anda hanya perlu dapat membuat matriks (array 2 dimensi) untuk papan, dan menemukan cara untuk menyandikan konsep potongan, aturan gerakan untuk setiap bagian, validasi bahwa gerakan itu legal, dan kondisi yang menandakan akhir pertandingan. Tidak ada yang sulit tentang semua itu. Anda harus menggunakan bahasa apa pun yang paling Anda kenal.

Sekarang jika Anda ingin membuat AI bermain catur yang akan mengambil peran salah satu pemain, di situlah segalanya menjadi rumit. Tetapi sekali lagi, pilihan bahasa bukanlah masalah terbesar di sini; memahami prinsip AI yang terlibat adalah. Itu akan menjadi faktor yang jauh lebih penting.

(Karena itu, pengambilan keputusan semacam ini bisa sangat intensif secara komputasi, dan Anda mungkin ingin menggunakan sesuatu yang mengkompilasi kode asli daripada bahasa scripting. Dan C ++ adalah pilihan yang sangat buruk, bukan karena itu tidak baik -Disebabkan oleh masalah ini tetapi hanya karena itu adalah bahasa yang sangat buruk secara umum, dan mencoba untuk mengimplementasikan hal-hal rumit di dalamnya adalah cara yang baik untuk membuat kode segala macam sakit kepala untuk diri Anda sendiri.)