Dalam permainan catur yang bisa anda mainkan secara offline di gadget yang anda miliki, tentu saja permainan ini menggunakan algoritma catur yang dipakai untuk lawan bermain anda. Kami akan menjelaskan bagaimana algoritma catur ini bekerja. Dan ini adalah cara bekerjanya ;
Perwakilan Dewan
Papan catur direpresentasikan dengan cara yang paling sederhana – sebagai matriks 8 kali 8, masing-masing berisi Sepotong (dengan bidak “kosong” mewakili ruang papan kosong). Selanjutnya, variabel bendera melacak apakah rokade sisi ratu/raja diperbolehkan untuk masing-masing pemain, dan apakah gerakan penangkapan en-passant diperbolehkan pada titik waktu tertentu. Untuk menghemat ruang dan waktu selama pencarian min-max, optimal untuk tidak memiliki instance papan terpisah di setiap cabang. Lagipula, merekahanya berbeda dengan posisi one piece.
Oleh karena itu setiap gerakan berisi informasi tidak hanya tentang bagian mana yang dipindahkan dari mana ke mana, tetapijuga apakah itu mempengaruhi castling, en passant, dan apakah itu menangkap bidak musuh dalam prosesnya. Jadi membalikkan gerakan di papan sangat sederhana.Dengan demikian, algoritme hanya membutuhkan satu objek papan, di mana ia membuat dan membalikkan semua gerakan yang dipertimbangkannya selama pencariannya.Program bermain catur tingkat lanjut memiliki representasi papan yang jauh lebih pintar, yang beroperasi pada bit.
Instance terpisah disimpan untuk dilacakpotongan individu, dan seringkali operasi bit-bijaksana dapat mengungkapkan banyak informasi tentang posisi papan dengan sangat cepat (terutama yang berkaitan dengan pion).Bertahun-tahun penelitian telah dihabiskan untuk mencoba mengoptimalkan representasi ini untuk kecepatan.
Pencarian Min-maks Algoritma Catur
Inti dari algoritma catur dalam permainan adalah pencarian min-max lokal dari gamespace. Algoritma mencoba untuk MINimize skor lawan, dan MAXimize sendiri. Pada setiap kedalaman (atau “ply” sebagaimana dimaksud dalam terminologi catur komputer), semua kemungkinan gerakan diperiksa, dan fungsi evaluasi papan statis digunakan untuk menentukan skor pada daun pohon pencarian.
Skor ini menyebar ke atas pohon dan digunakan untuk memilih gerakan optimal pada setiap kedalaman. Lebih besar ply, semakin baik gerakan yang dipilih (karena algoritme dapat melihat ke depan lebih banyak gerakan). Itu faktor percabangan biasanya antara 25 dan 40 gerakan per lapis (rata-rata sekitar 35).
Pemangkasan Alfa-beta
Fungsi pemangkasan umum algoritma catur ini digunakan untuk sangat mengurangi ruang pencarian min-max dalam algoritma catur. Ini pada dasarnya melacak gerakan terburuk dan terbaik untuk setiap pemain sejauh ini, dan menggunakan kaleng itu sepenuhnya menghindari mencari cabang yang dijamin menghasilkan hasil yang lebih buruk. Menggunakan ini pemangkasan akan mengembalikan gerakan yang sama persis seperti menggunakan min-max (yaitu tidak ada kehilangan akurasi).
Idealnya, itu dapat menggandakan kedalaman pohon pencarian tanpa menambah waktu pencarian. Untuk mendekati optimal algoritma catur ini, gerakan yang tersedia di setiap cabang harus diurutkan dengan tepat. Penyortiran dilakukan dengan melihat skor dari setiap kemungkinan gerakan, hanya melihat 1 ply ke depan. Itu pengurutan intuitif adalah mengaturnya dari yang terbaik ke yang terburuk, tetapi itu tidak selalu yang terbaik.
Kebanyakan bergerak dalam catur berakhir dengan keuntungan dan kerugian kecil (yang meningkatkan posisi, belum tentu menangkap potongan), jadi masuk akal untuk memesan gerakan “tepukan berdiri” terlebih dahulu. Jadi pengurutan didasarkan pada nilai mutlak dari skor bergerak (dengan yang lebih kecil datang lebih dulu). Faktor percabangan rata-rata untuk min-max dalam catur adalah sekitar 35, tetapi dengan pemangkasan dan penyortiran alfa-beta, program mencapai faktor percabangan sekitar 25.
Null Move Heuristik
Heuristik sederhana dalam algoritma catur ini meningkatkan awal pencarian alfa-beta. Awalnya, tidak ada nilai untuk apa gerakan terburuk dan terbaik adalah, jadi mereka masing-masing default ke negatif dan positif tak terhingga. Tapi menggunakan heuristik ini algoritma dapat menemukan batas bawah awal pada gerakan terbaik. Ini memungkinkan pemain lawan bermain dua gerakan secara berurutan (memilihnya berdasarkan pencarian min-maks kecil-lapis), dan menghitung skor setelah itu. Tentu saja, setiap gerakan yang dilakukan oleh pemain saat ini harus mengalahkan skor yang diperoleh lawan dengan mendapatkan dua peluang
untuk bergerak.
Pencarian Algoritma Catur Keheningan
Karena kedalaman pencarian min-max terbatas, masalah dapat terjadi di perbatasan. Sebuah langkah yang mungkin tampak hebat sebenarnya bisa bencana karena sesuatu yang bisa terjadi pada langkah berikutnya. Melihat semua kemungkinan ini berarti meningkat ply dengan 1, yang bukan solusi, karena kita perlu memperluasnya ke kedalaman besar yang sewenang-wenang.
Tujuannya adalah untuk mencari pohon sampai posisi “diam” ditemukan – yaitu posisi yang tidak terlalu memengaruhi posisi saat ini (kebanyakan manuver dalam catur hanya menghasilkan sedikit kelebihan atau kekurangan masing-masing pemain, bukan yang besar sekaligus). Oleh karena itu, melihat kedalaman yang lebih tinggi hanya penting untuk signifikan bergerak – seperti menangkap. Pertimbangkan misalnya langkah di mana Anda menangkap ksatria lawan dengan ratu Anda. Jika itu adalah batas pencarian min-max Anda, tampaknya menjadi langkah besar – Anda menerima poin untuk menangkap ksatria lawan.
Tapi anggaplah itu di langkah berikutnya lawan Anda dapat menangkap ratu Anda. Maka langkah itu jelas terlihat buruk, karena menukar ratu dengan ksatria adalah untuk kerugian Anda. Pencarian algoritma catur dalam ketenangan akan dapat mendeteksinya dengan melihat ini langkah selanjutnya. Sekali lagi, tidak perlu melakukan ini untuk setiap gerakan – hanya untuk gerakan yang sangat memengaruhi skor (seperti tangkapan). Satu peringatan penting dalam algoritme pencarian diam adalah bahwa ia seharusnya hanya melihat gerakan yang tersedia karena gerakan yang sedang dilakukan. Pertimbangkan situasi berikut. Uskup Anda terancam oleh pion lawan, dan Anda memiliki kemampuan untuk tangkap ksatria lawan dengan pion yang berbeda.
Misalkan algoritma catur hanya melihat 1 lapis ke depan, dan sedang memeriksa beberapa yang tidak menangkap pindah. Itu tidak akan menyadari bahwa uskup dapat ditangkap di giliran berikutnya. Tapi apa yang terjadi saat dia memeriksa jurus penangkap ksatria dengan ketenangan. Ini akan melihat bahwa lawan dapat mengambil uskup Anda, yang akan meratakan kepemilikan bidak, membuat gerakannya tampak tidak bagus. Jadi kemungkinan besar algoritme akan memilih langkah selain menangkap ksatria, sehingga kehilangan uskup di giliran berikutnya tidak perlu. Untuk mencegah hal ini, algoritme harus melihat HANYA pergerakan yang tersedia karena pergerakannya sendiri. Sejak lawan “pion menangkap uskup” tersedia terlepas dari apakah Anda menangkap ksatria atau tidak, itu harus diabaikan.
