Panduan langkah demi langkah untuk membuat AI catur sederhana

Mari jelajahi beberapa konsep dasar yang akan membantu kita membuat AI catur sederhana:

  • bergerak-generasi
  • evaluasi dewan
  • minimum
  • dan pemangkasan alfa beta.

Di setiap langkah, kami akan meningkatkan algoritme kami dengan salah satu teknik pemrograman catur yang telah teruji waktu ini. Saya akan mendemonstrasikan bagaimana masing-masing memengaruhi gaya bermain algoritme.

Anda dapat melihat algoritma AI terakhir di sini di GitHub.

Langkah 1: Pindahkan pembuatan dan visualisasi papan

Kami akan menggunakan perpustakaan catur.js untuk generasi bergerak, dan papan catur.js untuk memvisualisasikan papan. Pustaka generasi bergerak pada dasarnya menerapkan semua aturan catur. Berdasarkan ini, kami dapat menghitung semua langkah hukum untuk suatu negara dewan tertentu.

Menggunakan pustaka ini akan membantu kita fokus hanya pada tugas yang paling menarik: membuat algoritme yang menemukan langkah terbaik.

Kami akan mulai dengan membuat fungsi yang hanya mengembalikan gerakan acak dari semua kemungkinan gerakan:

Meskipun algoritme ini bukan pemain catur yang solid, ini adalah titik awal yang baik, karena kita sebenarnya bisa bermain melawannya:

Langkah 2: Evaluasi posisi

Sekarang mari kita coba memahami pihak mana yang lebih kuat dalam posisi tertentu. Cara termudah untuk mencapai ini adalah dengan menghitung kekuatan relatif potongan-potongan di papan tulis menggunakan tabel berikut:

Dengan fungsi evaluasi, kami dapat membuat algoritme yang memilih langkah yang memberikan evaluasi tertinggi:

Satu-satunya peningkatan nyata adalah algoritme kami sekarang akan menangkap bagian jika bisa.

Langkah 3: Cari pohon menggunakan Minimax

Selanjutnya kita akan membuat pohon pencarian dari mana algoritma dapat memilih langkah terbaik. Ini dilakukan dengan menggunakan algoritma Minimax.

Dalam algoritme ini, pohon rekursif dari semua gerakan yang mungkin dieksplorasi hingga kedalaman tertentu, dan posisinya dievaluasi pada akhir “daun” pohon.

Setelah itu, kita mengembalikan nilai terkecil atau terbesar dari anak ke simpul induk, tergantung pada apakah itu putih atau hitam untuk dipindahkan. (Artinya, kami mencoba meminimalkan atau memaksimalkan hasil di setiap level.)

Dengan adanya minimum, algoritme kami mulai memahami beberapa taktik dasar catur:

Efektivitas algoritma minimax sangat didasarkan pada kedalaman pencarian yang dapat kami capai. Ini adalah sesuatu yang akan kami tingkatkan pada langkah berikutnya.

Langkah 4: Pemangkasan alfa-beta

Pemangkasan alfa-beta adalah metode pengoptimalan algoritma minimax yang memungkinkan kita mengabaikan beberapa cabang di pohon pencarian. Ini membantu kami mengevaluasi pohon pencarian minimax lebih dalam, sambil menggunakan sumber daya yang sama.

Pemangkasan alfa-beta didasarkan pada situasi di mana kita dapat berhenti mengevaluasi bagian dari pohon pencarian jika kita menemukan gerakan yang mengarah ke situasi yang lebih buruk daripada langkah yang ditemukan sebelumnya.

Pemangkasan alfa-beta tidak mempengaruhi hasil dari algoritma minimax - itu hanya membuatnya lebih cepat.

Algoritma alpha-beta juga lebih efisien jika kita kebetulan mengunjungi pertama path yang mengarah bergerak baik.

Dengan alpha-beta, kami mendapatkan peningkatan yang signifikan pada algoritma minimax, seperti yang ditunjukkan pada contoh berikut:

Ikuti tautan ini untuk mencoba versi AI catur yang ditingkatkan alfa-beta.

Langkah 5: Fungsi evaluasi yang ditingkatkan

Fungsi evaluasi awal cukup naif karena kami hanya menghitung materi yang ditemukan di papan. Untuk meningkatkan ini, kami menambahkan ke evaluasi faktor yang memperhitungkan posisi bidak. Misalnya, kesatria di tengah papan lebih baik (karena memiliki lebih banyak pilihan dan lebih aktif) daripada kesatria di tepi papan.

Kami akan menggunakan versi yang sedikit disesuaikan dari tabel bujur sangkar yang awalnya dijelaskan di wiki-pemrograman-catur.

Dengan peningkatan berikut, kami mulai mendapatkan algoritme yang memainkan beberapa catur "layak", setidaknya dari sudut pandang pemain biasa:

Kesimpulan

Kekuatan dari algoritma permainan catur yang sederhana adalah bahwa ia tidak membuat kesalahan yang bodoh. Namun demikian, pemahaman strategisnya masih kurang.

Dengan metode yang saya perkenalkan di sini, kami dapat memprogram algoritma permainan catur yang dapat memainkan catur dasar. "Bagian AI" (tidak termasuk generasi bergerak) dari algoritme akhir hanya 200 baris kode, yang berarti konsep dasarnya cukup sederhana untuk diterapkan. Anda dapat melihat versi finalnya di GitHub.

Beberapa perbaikan lebih lanjut yang dapat kami lakukan pada algoritme misalnya:

  • pindah-memesan
  • generasi bergerak lebih cepat
  • dan evaluasi khusus permainan akhir.

Jika Anda ingin mempelajari lebih lanjut, lihat wiki pemrograman catur. Ini adalah sumber yang berguna untuk mengeksplorasi lebih dari konsep dasar yang saya perkenalkan di sini.

Terima kasih sudah membaca!