Nama saya Igor Volkov. Saya bekerja di perusahaan konsultan sebagai pengembang, arsitek, pemimpin tim, manajer teknis Java. Peran yang berbeda tergantung pada kebutuhan proyek saat ini. Dia menarik perhatian untuk kontes dari mail.ru untuk waktu yang lama, tetapi ternyata berpartisipasi aktif hanya di Paper IO.
Kali ini, penyelenggara mengusulkan untuk menerapkan strategi manajemen bot berdasarkan permainan populer. Baca lebih lanjut tentang aturan di sini . Kode strategi saya dapat ditemukan di sini , dan contoh-contoh permainan di situs web kejuaraan .
Pada awal kompetisi, menurut saya, ide implementasi pop-up yang paling umum adalah penggunaan MCTS . Karena itu, saya menghabiskan sedikit waktu untuk bereksperimen dengan algoritma ini. Dan tanpa mengetahui bagaimana menggunakannya secara efektif untuk menyelesaikan masalah, saya memutuskan untuk memulai dengan menghasilkan banyak rute persegi panjang (dengan dua, dan kemudian dengan tiga putaran) dan evaluasi selanjutnya.
Algoritma Strategi
Algoritme strategi tingkat tinggi dapat diwakili oleh 6 poin berikut:
- Baca keadaan dunia
- Konversi objek pesan menjadi objek kerja
- Bentuk satu set rute persegi panjang
- Nilai setiap rute yang dihasilkan
- Pilih rute terbaik
- Kirim tim
Algoritma ini tidak berubah selama kompetisi. Hanya metode pembentukan rute bot dan penilaiannya yang dimodifikasi.
Kelas SimpleStrategy berisi versi awal dari strategi, dan kelas BestStrategy adalah versi yang ditingkatkan, yang menempati posisi ke-2 dalam kompetisi.
Membaca keadaan dunia
Keadaan dunia ditransmisikan sebagai objek JSON melalui STDIN . Saya melihat di pom.xml bahwa Anda dapat menggunakan perpustakaan Gson dan tugas membaca keadaan dunia telah sangat disederhanakan. Menggunakan pustaka Gson, deserialized string JSON membaca dari aliran input standar menjadi turunan dari kelas pesan . Kode ini ada di Main.java (baris 44-49) .
Buat benda kerja
Menggunakan objek transportasi dalam kode program utama biasanya tidak terlalu nyaman dan secara arsitektur salah. Misalnya, penyelenggara, karena satu dan lain hal, dapat mengubah format pesan. Oleh karena itu, perlu untuk mengubah objek transportasi menjadi pekerja, yang akan digunakan dalam kode program utama. Kelas Player dan PlayerState mempertahankan status bot, dan kelas utilitas MessagePlayer2PlayerConverter membantu untuk membuat kelas-kelas ini berdasarkan data dari pesan transport. Kelas Bonus berisi informasi tentang bonus sel di lapangan bermain. Kode untuk membuat objek kerja terletak di Main.java (baris 61-74) .
Dalam versi pertama strategi ( SimpleStrategy ), jalur ditetapkan menggunakan kelas MovePlanWithScore dan Move . Move menetapkan arah gerakan dan berapa banyak sel yang harus dipindahkan bot ke arah ini, dan MovePlanWithScore berisi rute yang ditentukan oleh array Arahan dan perkiraan rute ini. Array dapat berisi dari satu hingga empat objek Pindahkan . Terlepas dari kenyataan bahwa hanya rute persegi panjang dengan tidak lebih dari tiga belokan dipertimbangkan, pada kenyataannya rute bot diperoleh dalam bentuk garis putus-putus. Ini dicapai dengan memilih rute empat persegi panjang terbaik di setiap belokan. Fungsi pembuatan rute , diimplementasikan sebagai loop bersarang, membentuk daftar dari MovePlanWithScore untuk evaluasi lebih lanjut.
Formasi lintasan bot seperti itu tidak terlalu efektif dalam hal kinerja penilaian berikutnya, karena itu perlu untuk menghitung lintasan yang sama beberapa kali, tetapi itu sangat berguna untuk memahami mekanisme permainan.
Dalam versi strategi yang lebih baru, BestStrategy mulai menggunakan pohon rute. Kelas MoveNode mencerminkan simpul pohon ini. Pohon sepenuhnya terbentuk pada awal strategi. Perhatikan metode init dari kelas MoveNode . Ini sangat mirip dengan menghasilkan rute dari kelas SimpleStrategy . Pada dasarnya, rute yang dimaksud tidak jauh berbeda dengan versi pertama.
Pembentukan rute, saya pikir, bisa ditingkatkan sedikit lebih dengan menambahkan twist lain. Tetapi tidak ada cukup waktu untuk optimasi.
Peringkat Rute
Di mana pun bot itu berada, rute terbaik yang berakhir di wilayahnya selalu dipilih untuknya. Untuk mengevaluasi rute, saya memperkenalkan dua indikator: skor dan risiko. Skor - kira-kira mencerminkan jumlah poin yang dicetak per kutu jalur, dan risiko - jumlah kutu yang tidak cukup untuk menyelesaikan jalur (misalnya, karena fakta bahwa lawan dapat meraih dengan ekor). Risiko tidak segera muncul. Dalam versi pertama, jika bot tiba-tiba menemukan di tengah jalan bahwa ia tidak punya waktu untuk menyelesaikan rute, itu "menjadi gila", karena semua jalur berbahaya sama buruknya untuk itu. Dari semua rute yang dipertimbangkan, yang paling "aman" dipilih dengan jumlah maksimum poin per centang jalan.
Untuk menilai keamanan rute, saya menghitung matriks reachability: untuk setiap sel lapangan bermain saya menemukan centang di mana bot lawan dapat muncul di dalamnya. Pertama, hanya centang, dan kemudian menambahkan perhitungan panjang ekor. Bonus yang dapat diambil sepanjang jalan juga tidak diperhitungkan dalam versi pertama strategi. Kelas TimeMatrixBuilder menghitung matriks kutu dan panjang ekor bot lawan. Matriks ini kemudian digunakan untuk menilai risiko. Jika bot saya berada di wilayahnya pada saat menghitung langkah selanjutnya - tingkat risiko maksimum ditetapkan untuk rute berbahaya, jika bot sudah dalam perjalanan di wilayah asing atau netral, risiko dinilai sebagai perbedaan antara kutu penyelesaian jalur (bot datang ke wilayahnya) dan kutu saat dapat mengancam bahaya (misalnya, bot orang lain dapat menginjak ekor).
Dalam versi pertama strategi, skor dianggap hanya berdasarkan wilayah yang ditangkap dan bonus sedikit diperhitungkan. Untuk menemukan sel yang ditangkap, saya menggunakan algoritma rekursif . Banyak kontestan mengeluh tentang keanehan dan kompleksitas komputasi yang berlebihan dari algoritma yang digunakan oleh penyelenggara di Local Runner . Saya akan berasumsi bahwa ini dilakukan dengan sengaja agar tidak memberikan solusi siap pakai kepada para peserta kompetisi.
Aneh, tetapi terlepas dari keutamaan versi pertama dari strategi, itu menunjukkan dirinya dengan cukup baik: tempat ke-10 di kotak pasir. Benar, di babak prefinal ia mulai turun dengan cepat: peserta lain meningkatkan strategi mereka.
Bot saya sering mati. Pertama-tama, karena fakta bahwa rute sedang dibangun ke wilayah yang ditangkap oleh bot saingan. Jalannya tiba-tiba memanjang dan bot saya tertangkap oleh ekor. Sering mati karena prediksi yang salah tentang panjang ekor dan kecepatan bot lawan. Misalnya, bot lawan yang mengalami pelambatan berbahaya, karena dalam perhitungan perkiraan, strategi tersebut berasumsi bahwa ia seharusnya sudah meninggalkan sel, dan ia masih ada di sana. Untuk mengatasi masalah ini, saya mulai menghitung sejumlah besar indikator untuk setiap sel di lapangan bermain (kelas AnalyticsBuilder dan CellDetails ).
Menghitung sel bidang bermain
- Centang di mana bot lawan dapat menempati kandang (centang di bagian ekor)
- Centang di mana bot lawan bisa memasuki sel
- Panjang ekor saat memasuki kandang
- Centang di mana bot lawan dapat keluar dari kandang
- Panjang ekor saat meninggalkan kandang
- Centang di mana sel dapat ditangkap oleh bot lawan
- Centang di mana sel dapat menjadi target untuk menangkap wilayah
- Centang tempat sel dapat dipukul dengan gergaji
Kedalaman analitik terbatas pada 10 gerakan. Saya pikir itu mungkin untuk mencapai kedalaman yang lebih besar dengan menolak untuk menghitung pesaing individu atau memperkenalkan kedalaman mengambang, tetapi tidak ada cukup waktu untuk optimasi. Selain AnalyticsBuilder, ia mulai menggunakan SimpleTickMatrixBuilder jika tidak ada kedalaman render untuk AnalyticsBuilder . Hasil analisis digunakan oleh BestStrategy .
Fungsi peringkat juga sedikit meningkat:
- Saya mulai memperhitungkan bonus akun: penalti untuk mengambil bonus deselerasi dan bonus untuk mengambil akselerasi dan melihat bonus. Akibatnya, bot mulai berhasil menghindari bonus buruk dan mengambil yang baik di sepanjang jalan.
- Dia mulai memperhitungkan bentrokan kepala. Menambahkan beberapa poin untuk pertandingan kemenangan. Semakin jauh kemungkinan tabrakan, semakin sedikit poin.
- Untuk mengurangi kemungkinan lingkungan, ia menambahkan beberapa poin untuk mengambil sel batas lawan.
- Mengurangi nilai sel kosong di perbatasan: semakin jauh dari pusat, semakin rendah nilainya. Menyaksikan perkelahian final, saya sampai pada kesimpulan bahwa untuk fakta menangkap sel kosong tidak perlu mengumpulkan poin sama sekali. Nilai sel kosong harus bergantung pada kedekatan dengan kelompok besar sel musuh. Sayangnya, di final tidak mungkin lagi untuk mengedit strategi.
- Menambahkan poin untuk mengelilingi kepala bot lawan. Tidak yakin apakah ini membantu. Mungkin dengan strategi paling sederhana.
- Dia menambahkan poin bahkan untuk meraih sia-sia oleh ekor (bot lawan berhasil menangkap wilayah dengan kutu yang sama di mana bot saya menginjak ekornya). Saya benar-benar tidak yakin, tetapi saya pikir ini mencegah bot lawan dari menangkap wilayah orang lain dan mereka sering harus kembali ke wilayah mereka.
- Dalam hal deteksi kemungkinan kematian dari penangkapan sangat meningkatkan biaya sel-sel batas wilayah lawan.
Strategi debugging
Versi pertama dari strategi berisi sejumlah besar kesalahan ketik dan kesalahan: tampaknya, hasil dari pemrograman malam. Misalnya, di kelas Sel , indeks dianggap salah: alih-alih this.index = x * Game.sizeY + y , this.index = x * Game.width + y . Pada awalnya saya mencoba hanya mengandalkan tes, tetapi intuisi saya menyarankan bahwa tanpa visualisasi dan tanpa bermain pertandingan yang dimainkan sebelumnya, akan sulit untuk menemukan kesalahan dalam kode dan menganalisis alasan untuk membuat keputusan yang salah. Akibatnya, visualisator DebugWindow muncul , di mana Anda dapat melihat game yang dimainkan sebelumnya langkah demi langkah, serta mulai men-debug pada centang yang diinginkan. Kode ini tidak terlalu indah, ditulis dengan tergesa-gesa, tetapi banyak membantu saya ketika debugging. Misalnya, kesalahan segera terdeteksi dengan perhitungan indeks sel yang salah. Banyak kontestan yang menampilkan informasi debug di konsol, tetapi menurut saya itu tidak cukup.
Optimasi
Agar tidak membuang waktu membuat objek dan menjalankan GC, saya mencoba membuat beberapa objek terlebih dahulu. Ini adalah sel-sel dari lapangan bermain (kelas sel ). Selain itu untuk setiap sel tetangga diidentifikasi. Membuat pohon kemungkinan jalur sebelumnya (kelas MoveNode ).
Saya berasumsi bahwa banyak skenario harus disimulasikan, dan dalam proses keadaan saat ini akan memburuk dan harus dipulihkan setiap waktu. Karena itu, untuk menjaga keadaan dunia, saya mencoba menggunakan sebanyak mungkin struktur yang dikemas. Untuk menyimpan wilayah yang diduduki - BitSet (kelas PlayerTerritory ). Setiap sel bidang bermain diberi nomor, dan nomor sel sesuai dengan nomor bit di BitSet. Untuk menyimpan buntut, saya menggunakan BitSet bersama dengan ArrayDeque (kelas PlayerTail ).
Benar, saya tidak sempat memainkan berbagai skenario karena kekurangan waktu. Dan karena fungsi utama menghitung jalur menjadi rekursif dan seluruh negara dapat disimpan di tumpukan, optimisasi terbaru tidak terlalu berguna bagi saya.
Ide yang belum direalisasi
Ketika menilai risiko rute bot saya, saya memperhitungkan setiap lawan secara independen. Bahkan, masing-masing rival juga takut mati. Karena itu, ada baiknya mempertimbangkan hal ini dalam penilaian risiko. Setidaknya, ini pasti harus diperhitungkan di pertandingan final.
Akuntansi kematian calon lawan. Kadang-kadang terjadi bahwa bot menangkap wilayah lawan, dan lawan tiba-tiba mati. Ini memalukan, karena sebagai hasilnya, Anda hanya menangkap sel kosong.
Akuntansi sel kosong yang akan ditangkap dalam waktu dekat sebagai fungsi evaluasi.
Rekomendasi dan terima kasih
Saya merekomendasikan bahwa semua pengembang berpartisipasi aktif dalam kontes Piala AI. Ini mengembangkan pemikiran dan bantuan melalui permainan untuk mempelajari algoritma baru. Dan seperti yang ditunjukkan oleh pengalaman saya, semangat kecil sudah cukup untuk menempati tempat hadiah dan bahkan kode yang sederhana dan tidak terlalu optimal dapat membawa hasil.
Banyak terima kasih kepada panitia. Meskipun ada beberapa masalah teknis, kompetisi ini ternyata menarik. Saya menantikan yang berikutnya!