Buat Catur AI Sederhana: 5 Langkah Mudah

Kami menerjemahkan untuk Anda sebuah artikel oleh Lauri Hartikka tentang menciptakan AI paling sederhana untuk catur. Itu ditulis kembali pada tahun 2017, tetapi prinsip-prinsip dasar tetap sama. Semua file yang digunakan Lori juga tersedia.

Kecerdasan buatan sederhana yang dapat bermain catur dapat dibuat berdasarkan empat konsep:

1. 1. Bergerak;
2. 2. Evaluasi dewan;
3. 3. Minimax ;
4. 4. Kliping alfa beta . Pada setiap tahap bekerja dengan algoritma, salah satunya akan digunakan, ini akan secara bertahap meningkatkan kemampuan game AI.

Skillbox merekomendasikan: Kursus Data Online Terapan Analis Data Python .

Kami mengingatkan Anda: untuk semua pembaca "Habr" - diskon 10.000 rubel saat mendaftar untuk kursus Skillbox apa pun menggunakan kode promo "Habr".

Kode sumber yang sudah jadi dapat ditemukan di GitHub .

Tahap 1. Visualisasi papan catur dengan generasi gerakan

Pada titik ini, kita akan menggunakan perpustakaan chess.js untuk menghasilkan gerakan dan papan catur.js untuk membuat papan catur. Perpustakaan, yang bertanggung jawab untuk menghasilkan gerakan, memungkinkan Anda untuk menerapkan semua aturan catur, sehingga kami dapat menghitung setiap tindakan untuk pengaturan potongan tertentu.


Ketika Anda mengklik pada gambar, itu akan terbuka dalam resolusi penuh.

Bekerja dengan perpustakaan ini memungkinkan Anda untuk berkonsentrasi pada tugas utama - mencari dan membuat algoritma yang memungkinkan Anda menemukan langkah optimal. Kami memulai pekerjaan dengan menulis fungsi yang mengembalikan gerakan acak dari daftar semua yang mungkin.

var calculateBestMove =function(game) { //generate all the moves for a given position var newGameMoves = game.ugly_moves(); return newGameMoves[Math.floor(Math.random() * newGameMoves.length)]; }; 

Terlepas dari kenyataan bahwa algoritma ini bukan pemain catur yang ideal, ini akan cukup untuk sebagian besar pemain levelnya.


Hitam bergerak secara acak. ( sumber dan game online )

Tahap 2. Evaluasi Posisi

Sekarang mari kita cari tahu sisi mana yang memiliki keunggulan dalam posisi ini atau itu. Cara termudah adalah dengan menghitung kekuatan relatif dari potongan-potongan di papan tulis, ini bisa dilakukan dengan menggunakan tabel.



Menggunakan fungsi evaluasi, kami mendapat kesempatan untuk membuat algoritma yang memilih langkah dengan peringkat maksimum.

 var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null; //use any negative large number var bestValue = -9999; for (var i = 0; i < newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //take the negative as AI plays as black var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue > bestValue) { bestValue = boardValue; bestMove = newGameMove } } return bestMove; }; 

Pada prinsipnya, levelnya sama, tetapi algoritme sudah dapat mengambil sosok orang lain ketika ada peluang seperti itu.


Hitam mendapat kesempatan untuk mengambil potongan putih. (Sumber dan game ada di sini ).

Tahap 3. Cari pohon dengan minimax

Setelah itu kami membuat pohon pencarian. Sekarang program dapat memilih langkah terbaik darinya. Ini dilakukan dengan menggunakan algoritma minimax.

Di sini pohon rekursif dengan tampilan semua gerakan yang mungkin dianalisis hingga kedalaman tertentu. Posisi diperkirakan oleh daun pohon kita.

Selanjutnya, kami mengembalikan nilai minimum atau maksimum anak ke simpul orangtua. Itu semua tergantung pada sisi mana yang saat ini salah perhitungan. Dengan kata lain, hasilnya dimaksimalkan atau diminimalkan di setiap tingkat.


Di sini, b2-c3 adalah langkah terbaik bagi White, karena ia memastikan bahwa pemain mencapai posisi dengan skor -50.

 var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } }; 

Dengan algoritma minimax, AI kami sudah mulai memahami taktik dasar catur.

Minimax dengan kedalaman 2 (Sumber dan game di sini )

Perlu dicatat bahwa efisiensi dari algoritma minimax meningkat dengan kedalaman pencarian. Langkah selanjutnya bertanggung jawab untuk ini.

Tahap 4. Kliping Alpha Beta

Ini adalah metode optimasi algoritma minimax yang memungkinkan untuk mengabaikan beberapa cabang di pohon pencarian. Dan ini memungkinkan Anda untuk meningkatkan kedalaman pencarian, menghabiskan jumlah sumber daya yang sama.

Kliping alpha beta didasarkan pada situasi di mana kita dapat berhenti mengevaluasi cabang tertentu jika ditemukan bahwa langkah baru akan mengarah pada situasi yang lebih buruk daripada yang kita lihat ketika mengevaluasi yang sebelumnya.

Optimalisasi tidak memengaruhi hasil minimal, tetapi semuanya mulai bekerja lebih cepat.

Algoritma ini jauh lebih efisien jika Anda pertama kali memeriksa jalur yang mengarah ke gerakan yang baik.


Gambar menunjukkan gerakan yang menjadi tidak perlu saat menggunakan kliping alpha beta.

Seperti yang Anda lihat, dengan kliping alpha-beta, minimax dioptimalkan, dan sangat signifikan.


Jumlah posisi yang akan dievaluasi dalam kasus pencarian dengan kedalaman 4 dan posisi awal, yang ditunjukkan di atas. (sumber dan game tersedia di sini )

Langkah 5. Peningkatan Fungsi Evaluasi

Fungsi evaluasi awal cukup sederhana, karena hanya menghitung titik-titik potongan di papan tulis. Untuk mengoptimalkannya, Anda dapat memperhitungkan posisi angka. Misalnya, jika Anda meletakkan kuda di tengah papan, maka itu menjadi lebih mahal - rentang gerakan yang tersedia untuk bagian ini akan melebar.

Pada titik ini, kita akan bekerja dengan versi tabel persegi yang sedikit dimodifikasi yang sebelumnya dijelaskan dalam wiki Programme Catur .



Dan sekarang algoritma kami sudah bermain cukup baik, tentu saja, dibandingkan dengan pemain rata-rata.


Sumber dan permainan tersedia di sini.

Kesimpulan

Keuntungan dari algoritma yang diusulkan adalah tidak membuat kesalahan yang sangat bodoh. Tentu saja, strategi di sini hampir tidak bisa disebut sempurna, tetapi tetap saja.

Implementasi algoritma kami hanya 200 baris kode, jadi prinsip dasarnya cukup sederhana. Versi terakhir dari program ini dapat berupa <a href= target github.com/lhartikk/simple-chess-ai'> yang terlihat di GitHub.

Modul lain dapat ditambahkan ke algoritme, termasuk:

• perampingan gerakan ;
• percepatan generasi gerakan ;
• dan skor endgame .

Lebih lanjut tentang algoritma catur dapat ditemukan di Wiki Programming Catur .

Skillbox merekomendasikan:

• Kursus praktis "PRO Pengembang Seluler"
• Kursus Online "Profesi Pengembang Web"
• Kursus praktis dua tahun "Saya adalah pengembang web PRO . "