risk game ai agent
1.0.0
Risiko adalah permainan papan strategi diplomasi, konflik dan penaklukan untuk dua hingga enam pemain. Giliran berputar di antara pemain yang mengontrol pasukan bermain yang dengannya mereka berusaha untuk menangkap wilayah dari pemain lain, dengan hasil yang ditentukan oleh gulungan dadu. Tujuan dari permainan ini adalah untuk menempati setiap wilayah di papan tulis dan dengan melakukannya, menghilangkan pemain lain. Setiap belokan terdiri dari dua tindakan:
Tujuan dari proyek ini adalah untuk mengimplementasikan permainan risiko dengan beberapa perubahan yang dibuat dalam aturan dan merancang agen cerdas yang secara artifisial yang mampu memainkan permainan dengan benar dan memiliki peluang yang sangat tinggi untuk menang ketika menghadapi lawan lainnya termasuk kedua manusia yang sebenarnya pemain atau pemain agen lainnya.
Gim ini diimplementasikan menggunakan bahasa pemrograman Java. Mengontrol belokan, melakukan tindakan yang diminta pemain, memperbarui peta permainan, memeriksa apakah semuanya terjadi sesuai dengan aturan, dll., Adalah hal -hal yang dilakukan bagian dari kode ini. Game UI juga dirancang melalui file .fxml yang menarik peta dan merupakan platform yang menghubungkan pemain ke logika game.
Bagian ini berfokus pada implementasi dan evaluasi heuristik yang mengarah pada AI yang kuat untuk risiko permainan.
Implementasi didasarkan pada algoritma pemangkasan minimax alpha-beta. Pemain membangun pohon prediksi berdasarkan algoritma DFS.
Setiap kali giliran agen untuk bermain, sebuah pohon dibuat. Node pohon adalah keadaan permainan (peta permainan di negara bagian itu) dan masing -masing tepi adalah kemungkinan serangan yang dibuat dari keadaan saat ini untuk menyerang hasil peta. Tindakan serangan terdiri dari koordinat awal dan wilayah target dan jumlah unit yang dipilih untuk berada di pasukan yang menyerang. Node root adalah keadaan peta saat ini yang harus dipilih pemain. Meskipun, pohon tidak dapat memprediksi sampai keadaan akhir permainan karena sejumlah besar kemungkinan gerakan yang dapat dimiliki pemain di setiap negara bagian yang tidak diizinkan oleh batasan memori dan waktu. Oleh karena itu, pemain hanya dapat membangun pohon ke kedalaman tertentu yang telah kami tentukan dalam kode. Ada juga beberapa penyederhanaan yang diterapkan pada bagian -bagian tertentu dari strategi permainan agen yang semuanya akan dijelaskan di bagian berikut. Untuk membuat keputusan terbaik, heuristik didefinisikan untuk node terdalam yang mungkin (daun pohon) yang mengevaluasi seberapa banyak mencapai keadaan itu dapat bermanfaat bagi pemain. Kata heuristik akan dijelaskan lebih lanjut dalam laporan. Ketika nilai-nilai daun ditentukan, pohon akan diteruskan ke pemangkasan minimax alpha-beta dan algoritma terkenal ini akan menemukan serangkaian tindakan terbaik yang dapat dimiliki pemain.
Memasok unit ke wilayah bisa menjadi tugas yang sulit; Dalam arti bahwa kami ingin meningkatkan kekuatan serangan kami tetapi juga memastikan memiliki kekuatan pertahanan yang cukup di wilayah yang dalam bahaya diserang. Menyebarkan unit -unit di negara -negara yang berdekatan dengan wilayah musuh bisa menjadi cara cerdas untuk menjaga keseimbangan antara kedua tujuan ini.
Penyederhanaan draft:
Memprediksi dan memasukkan semua skenario rancangan yang mungkin dalam pohon prediksi akan menyebabkan pohon kompleks yang akan menghadapi masalah yang disebutkan sebelumnya; Oleh karena itu, salah satu penyederhanaan yang dibuat adalah bahwa kami menggunakan heuristik penyusunan yang terbukti selalu memiliki hasil terbaik dan memprediksi bahwa lawan membuat pendekatan ini dalam penyusunan juga; Dengan kata lain, kami menghapus hasil penyusunan karena kemungkinan membentuk pohon prediksi dan mengubahnya menjadi skenario rancangan yang pasti.
Untuk melakukannya, kami mengambil langkah -langkah berikut:
Draft Heuristic:
Langkah 1:
Aking penjumlahan semua unit di negara -negara musuh yang berdekatan dengan negara X akan memberikan langkah yang kami sebut Ancaman Keamanan Perbatasan (BST) di x.
Langkah 2:
Membagi BST ini dengan unit yang terletak di X memberikan rasio keamanan perbatasan (BSR) yang dapat dibandingkan di antara semua negara perbatasan.
Negara -negara dengan BSR tinggi lebih cenderung ditaklukkan oleh pemain musuh, karena jumlah unit musuh di negara -negara musuh yang berdekatan relatif lebih tinggi daripada jumlah unit di negara itu sendiri. Memilih negara -negara dengan BSR tinggi untuk memasok untuk meningkatkan kekuatan pertahanan mereka dengan menurunkan BSR. Memasok unit ke negara -negara dengan BSR yang lebih rendah, yang berarti bahwa mereka sudah memiliki sikap defensif yang lebih baik, akan meningkatkan kekuatan ofensif mereka, meningkatkan peluang serangan yang berhasil dari negara -negara ini.
Langkah 3:
Normalisasi BSR dengan membaginya dengan jumlah semua BSR negara, yang dimiliki pemain, akan memberikan pengukuran langsung yang dengannya seseorang dapat mengatur unit. Rasio keamanan perbatasan yang dinormalisasi (NBSR) dihitung oleh:
Ini memberikan rasio langsung tentang bagaimana unit dapat didistribusikan di antara negara -negara. Pada titik ini kita dapat melihat akan ada masalah dengan rasio ini karena beberapa data tidak relevan, dan kami tidak ingin menambahkan unit ke semua wilayah kami sehingga kami menetapkan ambang batas di antara langkah dua dan tiga dengan mengurutkan data BSRX masuk Perintah yang menurun (kami lebih fokus pada membuat kekuatan pertahanan lebih kuat), membagi data dari tengah dan mengatur angka di bagian bawah ke nol.
Langkah 4:
Langkah 4 akan dilanjutkan sampai tidak ada lagi unit yang tersedia untuk ditambahkan.
Ada beberapa penyederhanaan yang diterapkan dalam fase serangan untuk membuat pohon kurang rumit sehingga kita dapat memprediksi ke tingkat yang lebih dalam. Ini dapat dilakukan dengan memeriksa skenario serangan mana yang memiliki peluang lebih tinggi untuk memenangkan pertempuran dan hanya memasukkannya ke dalam pohon.
Untuk mengevaluasi seberapa menguntungkan daun pohon untuk pemain spesifik itu; Kami telah mendefinisikan empat fitur heuristik yang ditemukan oleh bobot terbaik mereka selama pembelajaran heuristik yang akan dijelaskan nanti. Semua fitur mengembalikan hasil antara nol ke satu karena ketika fitur dinilai dalam rasio dekat satu sama lain, pembelajaran dan penetapan berat akan lebih akurat.
Fiturnya adalah:
Memberi bobot untuk masing -masing heuristik di bagian sebelumnya membantu mengevaluasi seberapa penting dan berpengaruh masing -masing dari mereka untuk memenangkan permainan. Proses menemukan bobot ini adalah melalui genetik dan belajar. Setiap gen adalah satu set empat bobot untuk keempat fitur tersebut. Kami mulai dengan menghasilkan 100 set bobot acak dalam kisaran [0,10]. Setelah itu, 10 turnamen akan terjadi. Untuk setiap turnamen 10 gen dari populasi utama akan dipilih secara acak. Setiap pasangan gen yang mungkin akan bermain melawan satu sama lain dan hasil dari setiap pertandingan di setiap turnamen akan didokumentasikan. Fungsi kebugaran didefinisikan sebagai (jumlah kemenangan / jumlah game) untuk setiap gen. Tiga gen teratas di setiap turnamen (berdasarkan fungsi kebugaran) akan dipilih sehingga sekarang kami memiliki 30 gen terpilih teratas. Di antara ini kami memilih 12 pasangan acak dan untuk setiap pasangan melakukan crossover yang menciptakan gen baru dengan menghitung berat rata -rata pasangan gen. Karena itu, kami sekarang memiliki 12 gen baru dari crossover ini. Di sisi lain, 3 gen dipilih secara acak dalam 30 gen yang kami miliki dan bermutasi dengan mengubah satu berat acak masing -masing menjadi berat acak lain dalam kisaran [0,10]. Setelah semua ini, kami sekarang memiliki 15 gen baru yang dimasukkan ke dalam populasi utama, mengganti yang 15 paling tidak bagus yang sudah kami miliki di sana. Pada titik ini generasi kedua gen dihasilkan. Proses ini akan terus berulang sampai Generasi 4 gen dihasilkan. Gen teratas dalam populasi itu akan dipilih sebagai bobot terbaik kami untuk fitur heuristik kami yang akan digunakan agen untuk bermain.
