💅🏽 👨🏽‍🏫 ♾ Bot saya untuk Piala AI Rusia 2019 ♊️ 🙏🏿 👨🏾‍🎓

Kebetulan kejuaraan ini adalah yang pertama bagi saya di mana saya dapat mengambil tempat yang layak, yang saya tidak malu, jadi saya memutuskan untuk menulis artikel barusan. Jalan yang saya tempuh ke tempat ini: tempat ke-1192 di kejuaraan tahun ke-13, ke-241 di kejuaraan tahun ke-17, ke-91 di kejuaraan tahun ke-18 dan, akhirnya, ke-16 (dan ke-5) e di kotak pasir) tempatkan itu.

Pikiran umum

Saya percaya bahwa salah satu alasan utama untuk kinerja yang relatif sukses di RAIC adalah perubahan dalam pendekatan untuk menulis strategi Anda.

Sebelumnya, saya mencoba untuk segera menulis sesuatu yang besar dan rumit, tanpa langkah perantara, dan versi pertama hanya dapat diisi dalam dua minggu setelah dimulainya kejuaraan, tetapi di masa lalu saya tidak bisa memasukkannya ke dalam semua waktu yang diberikan dan versi pertama diisi hanya setelah final .

Semua ini mengarah pada fakta bahwa sementara peserta lain dapat menguji strategi mereka untuk hidup, saya masih tidak memiliki solusi yang sudah jadi, meskipun yang buruk. Karena itu, ketika dimungkinkan untuk mengisinya, ternyata pendekatan yang dipilih tidak bekerja atau bekerja dengan buruk, dan karena banyak waktu dan upaya telah diinvestasikan, tidak ada kemungkinan radikal untuk mengubahnya.

Karena itu, saya memutuskan bahwa kali ini saya akan melakukan yang berbeda. Berdasarkan pengalaman dari partisipasi sebelumnya, saya perhatikan bahwa bot awal, terlepas dari segala keutamaannya, ditulis dengan cukup rasional, dan, dengan mengembangkannya, Anda dapat perlahan-lahan menambah dan menguji fitur-fitur baru, dan segera memeriksa strategi peserta lain. Terutama saya yakin untuk mencoba pendekatan ini artikel tahun lalu oleh T1024.

Saya juga memutuskan untuk diri saya sendiri bahwa semakin kompleks pendekatannya, semakin tidak efektif di tangan saya. Sebagai contoh, tidak masuk akal untuk menggunakan genetika di mana dimungkinkan untuk melakukan pencarian lengkap, dan jika ada pilihan untuk memilah lebih sedikit pilihan, tetapi semua, atau lebih banyak, tetapi genetika, lebih baik untuk memilih opsi pertama. Plus, dari membaca artikel-artikel Commando, Saya menyimpulkan bahwa optimasi khusus untuk tugas akan selalu lebih efektif daripada algoritma umum.

Namun demikian, bahkan sekarang saya terlambat tiga atau empat hari, sebelum saya berhasil mengisi versi pertama dari bot, pada saat itu mereka sudah berperang di kotak pasir.

Apa yang saya lakukan saat ini? Saya menulis sebuah simulator, yang pentingnya saya pelajari dari kejuaraan masa lalu. Tidak seperti tahun lalu, di mana pseudo-code dari simulator segera tersedia, tahun ini semua mekanik harus dibaca dari dokumentasi. Untungnya, sebagai kompensasi, mekanik permainan tidak terlalu rumit dan langsung, jadi saya tidak punya masalah khusus.

Versi awal

Jadi, di tangan saya memiliki simulator kasar yang sudah jadi, meski bengkok, hal pertama yang saya lakukan adalah mengacaukan dodge (fungsi Dodge). Karena kali ini saya memutuskan untuk bertindak sesederhana mungkin, penghindaran dibuat sesederhana mungkin - kami memeriksa pergerakan dalam sembilan arah (4 aksial, 4 diagonal dan berdiri di tempat) dan melihat arah mana dari unit ini yang akan menerima kerusakan paling sedikit.

Fungsi bot lainnya tetap hampir sepenuhnya seperti Quickstart. Penunjukan target juga primitif mungkin - rantai jika memilih tindakan yang paling cocok untuk unit: untuk musuh, dari musuh, ke kotak P3K, senjata, dll.

Anehnya, pendekatan ini, secara bertahap menjadi lebih rumit, tetapi tidak mengubah esensinya, memungkinkan untuk mencapai hampir ke puncak sebelum putaran pertama (setelah bot bahkan di tempat kedua di kotak pasir) dan umumnya tinggal di suatu tempat di sekitar sepuluh tempat pertama.

Namun demikian, ini tidak bisa bertahan selamanya, dan bot harus diperbaiki. Namun, tidak ada ide apa dan bagaimana cara meningkatkan, semua upaya untuk mengubah sesuatu dalam strategi mengarah pada kenyataan bahwa dia kehilangan versi lama. Perubahan kecil dibuat, tetapi tidak lebih.

Kurangnya ide menyebabkan fakta bahwa di babak 1 dan 2 saya masing-masing mengambil 29 dan 19 tempat, dan meskipun saya pergi ke final, menjadi jelas bahwa sesuatu harus diubah secara radikal. Sebelum finale (dan setelah finale) itulah jumlah terbesar dari perubahan signifikan dibuat.

Sudah di suatu tempat dari tengah kejuaraan saya mencoba bereksperimen dengan gerakan yang lebih cerdas, tetapi semua upaya tidak berhasil. Gagasan awal adalah memilih arah di mana perbedaan dari kemungkinan memukul botnya pada musuh dan musuh pada botnya maksimum. Untuk percobaan ini, saya menghabiskan hampir semua waktu yang dialokasikan untuk final, dengan hasil nol.

Karena itu, untuk peta multi-level akhir, bot ternyata sama sekali tidak siap. Rantai ifs menghasilkan hasil yang relatif baik pada peta tingkat tunggal dari putaran 1 dan 2, tetapi ternyata tidak cocok untuk peta multi-level final, saya juga tidak memiliki sistem navigasi untuk peta yang kompleks, karena pada peta sederhana dimungkinkan untuk mengelola perpindahan dari kode start-up.

— .

Semua kontrol penembakan ada dalam fungsi AimHelper.

Semua yang dijelaskan di bawah ini menyiratkan bahwa target adalah unit musuh yang terlihat paling dekat dengan bot.

Hanya ada tiga jenis senjata, namun masing-masing membutuhkan pendekatan sendiri. Lebih baik menembak lebih sering dari senapan mesin, membidik dengan lebih baik dari pistol, dan kemudian penting untuk menembak dari peluncur roket untuk menimbulkan lebih banyak kerusakan pada musuh daripada diri Anda sendiri.

Awalnya, tidak ada yang membidik sama sekali, bot hanya ditujukan ke pusat unit. Kemudian, prediksi pergerakan unit ditambahkan jika berada dalam penerbangan yang tidak terkontrol (jatuh atau terbang dari jumppad). Untuk melakukan ini, saya cukup mensimulasikan pergerakan unit sampai jarak yang bisa diterbangkan peluru untuk kutu N menjadi sama dengan jarak ke unit.

Ketika menguji terhadap bot awal, ia memperhatikan kebiasaannya yang sangat tidak menyenangkan yaitu terus-menerus melompat-lompat, dan jika bot selalu mengarah ke pusat musuh, ini menyebabkan penglihatan itu terus bergerak dan penyebarannya dengan sangat cepat meningkat secara maksimal. Untuk counteraction, kode ditambahkan yang memeriksa jika peluang memukul dengan sudut bertujuan saat ini lebih baik atau sama dengan peluang memukul dengan sudut tujuan baru, maka kita tidak mengubah titik di mana kita mengarahkan dan tidak meningkatkan penyebaran.

Dengan pemotretan itu lebih sulit, salah satu masalah utama bot awal adalah bahwa dia tidak memeriksa apakah dia akan menyentuh dirinya sendiri dengan ledakan. Untuk beberapa alasan, saya menyukai peluncur roket dari ketiga jenis senjata, dan karena itu prioritas pertama. Itu perlu untuk mengajar bot untuk tidak merusak dirinya sendiri.

Fungsi HitChance ditulis, yang membagi sektor menembak unit menjadi sinar N, dan memeriksa setiap sinar untuk tabrakan dengan target. Juga, ketika terkena, AOE dari ledakan diperiksa, jika itu adalah peluncur roket. Peluang untuk memukul = jumlah klik oleh sinar atau ledakan / jumlah sinar.

Ini memungkinkan kami untuk menentukan peluang statis mengenai diri kami dan musuh, tetapi tidak memperhitungkan bahwa musuh sendiri dapat secara aktif mengelak. Ada masalah lain, misalnya, fungsi tidak memperhitungkan penembakan acak di tambang.

Ini cukup untuk bertarung melawan musuh yang tidak terlalu licik, tetapi melawan atasan yang menghindari peluru dengan baik, fungsinya tidak memberikan hasil yang memadai. Diperlukan pendekatan baru.

Fungsi HitPredict juga membagi kerucut menembak menjadi sinar N, tetapi bukannya casting ulang, kami menggunakan simulasi di mana satu peluru ditembakkan dalam satu arah pada suatu waktu dan diperiksa apakah musuh dapat menghindar.

Untuk memeriksa dodges, fungsi Dodge juga digunakan, yang digunakan bot itu sendiri, tetapi dengan sangat banyak memotong waktu simulasi dan jumlah mikrotik. Metode penilaian ini ternyata cukup akurat, tetapi terlalu pesimistis. Jika Anda hanya menggunakannya, maka bot akan menembak terlalu jarang.

Dalam versi pertama, fungsi hanya mengembalikan peluang untuk memukul, dari 0-1, kemudian ditambahkan perhitungan rata-rata nilai HP target, serta kesempatan untuk membunuh dengan memukul.

Pada akhirnya, kedua fungsi bekerja bersama. Fungsi HitPredict digunakan hingga empat kali, satu untuk setiap unit. Hasil penghitungan setiap fungsi dikonversi ke kecepatan, yang menunjukkan seberapa menguntungkan / berbahaya memotret saat ini. Nilai ditambahkan. Jika nilai totalnya kurang dari nol, pemotretan diblokir. Untuk peluncur roket, perlu kecepatan lebih besar dari nol.

Menjadi mungkin untuk menembak lebih percaya diri dalam kasus-kasus di mana sekutu memblokir tembakan atau masuk ke AOE dari peluncur roket, Anda dapat menembaknya dari belakang mengetahui bahwa sekutu akan punya waktu untuk menghindar, atau itu hanya menguntungkan bagi kita untuk menembak. Misalnya, kita akan kehilangan satu unit, tetapi kita akan mengambil dua unit sekaligus.

Untuk peluncur roket, pendekatannya juga efektif, satu tembakan pada waktu yang tepat jauh lebih efektif daripada dua tembakan, ketika peluang untuk mengenai nol. Dalam bentuk ini, penembakan berada di final, dan ini memungkinkan untuk mengambil tempat ke-16.

Sekarang chip yang ditambahkan setelah final.

Tujuan akurat: jika sudut antara pandangan saat ini dan yang diinginkan tidak terlalu besar, kami mengarahkan pandangan pada kecepatan data agar tidak meningkatkan penyebaran.

Sudut informasi untuk pistol: anehnya, chip itu sangat sederhana, tetapi tidak terlintas dalam pikiran sebelumnya. Larangan menembak jika faktor pencar (pencar / pencar max) lebih besar dari 0,6 memberikan persentase kemenangan dalam mode 1x1 dalam 3: 1 terhadap versi yang menembak pada CD senjata. Mengurangi faktor menjadi 0,3 menyediakan persentase kemenangan yang sama terhadap versi dengan parameter 0,6. Jadi, salah satu optimasi paling sederhana ternyata menjadi salah satu yang paling efektif.

Visualisasi operasi fungsi HitPredict, lintasan di mana hit dijamin ditandai dengan warna merah.

Navigasi

Hingga akhir navigasi tidak ada kata sama sekali. Algoritma yang sedikit lebih baik dari bot awal digunakan, dan ini umumnya cukup.

Oleh karena itu, ketika kartu kompleks pergi, bot mengalami waktu yang sangat sulit. Algoritme pencarian BFS yang mendesak ditulis secara mendesak, yang mencari jalur tanpa memperhitungkan jangkauan fisiknya, hanya dengan ubin. Agar bot melewati jalur yang ditemukan, berbagai kruk digunakan. Semua ini bekerja dengan sangat miring, dan kadang-kadang itu tidak berhasil sama sekali, tetapi bot itu entah bagaimana bisa sampai ke senjata dan peralatan P3K, dan tidak melompat di tempat.

Setelah final, navigasi ditingkatkan secara signifikan dan, menurut pengamatan saya, berperilaku lebih efisien daripada banyak peserta dengan algoritma pencarian jalur yang lebih baik.

Prinsip kerja: bot mencari sel terjauh di jalan dalam kotak 5x5, terlihat dari pusat bot, dan mengikuti ke titik ini.

Namun demikian, sampai akhir, tetap kode kruk luar biasa yang hanya bekerja pada peta akhir dan jatuh pada yang lain, lebih kompleks.

Jalur bertanda hijau ditemukan diykstroy. Bot mengikuti titik yang ditandai dengan kotak putih.

Bergerak dan Memperkirakan Fungsi

Sampai final, tidak ada fungsi evaluasi, sebagai gantinya, rantai ifs digunakan, yang dalam urutan prioritas mengatur bot ke target sesuai dengan kondisi yang diberikan. Misalnya, yang pertama adalah mencari senjata jika bot tidak memilikinya, lalu mencari peralatan P3K jika kita terluka, dll.
Ini bekerja pada peta sederhana, meskipun bengkok, karena prioritas berubah sangat tajam dan tidak memperhitungkan berbagai faktor tambahan.

Oleh karena itu, fungsi evaluasi tetap ditulis.

parameter utama

Unit kesehatan, bonus terbesar.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
Bonus besar jika kita bisa menyentuh musuh dengan peledakan diri.

Dua parameter terakhir tidak ada di final.

Semua bonus ini dihitung untuk setiap tick, disimpulkan dan nilai total dirata-rata. Selain itu, ada estimasi parameter yang dihitung satu kali untuk setiap arah.

Bonus untuk bergerak menuju musuh terdekat.
Bonus untuk bergerak menuju kotak P3K terdekat. Semakin sedikit kesehatan yang kita miliki, semakin kuat bonusnya.
Bonus untuk pindah ke senjata terdekat jika kita tidak memiliki senjata, atau untuk pindah ke senjata dengan prioritas lebih tinggi daripada bot.
Bonus untuk pindah ke lootbox min jika bot memiliki kurang dari dua.
Bonus untuk pindah ke kotak P3K yang paling dekat dengan musuh, jika kita lebih dekat dengan kotak P3K daripada musuh.
Bonus paling menarik. Itu ditambahkan setelah final. Memungkinkan Anda untuk mencegah bot musuh tidak dirawat. Menurut pengamatan, ternyata cukup efektif.

Catatan

Kedalaman simulasi adalah 30 ticks.
Perilaku bot musuh tidak disimulasikan. Permainan ini sangat dinamis dan cukup memprediksi pergerakan musuh sangat sulit dan tidak terlalu diperlukan. Mungkin bermanfaat untuk menghindari bunuh diri yang gila, tetapi itu tidak pernah dilakukan.
Untuk menghindari masalah dengan menghindari peluru, jika mereka ada di lapangan, kami mensimulasikan dengan kualitas 100 mikrotik per tick (seperti dalam game), jika tidak kita kurangi menjadi 5.
Anda mungkin memperhatikan bahwa tidak ada koefisien atenuasi yang diterapkan. Mungkin ini kesalahan.

Opsi langkah lama ada di MoveHelperOld, yang baru di MoveHelper.

Bot saya (di sebelah kanan) menjaga kotak P3K

Tambang

Tentang tambang perlu diberitahukan secara terpisah. Jika pada awalnya itu bukan elemen gameplay yang sangat penting, itu seharusnya menambang poin-poin penting. Setelah tes beta, kemampuan untuk meledakkan ranjau tiba-tiba ditambahkan jika mereka terkena peluru atau ledakan. Selain itu, dimungkinkan untuk mengatur tambang dan merusaknya dalam tanda centang yang sama.

Artinya, jika Anda hanya menghabiskan dua kutu, Anda bisa membawa unit musuh apa pun. Musuh menerima 1000 poin untuk kematian kami, tetapi kami menerima 1000 + kesehatannya pada saat pembongkaran atas kematiannya. Jika Anda mengulangi ini dua kali, maka Anda bisa mendapatkan kemenangan dengan probabilitas yang sangat tinggi.

Eksploitasi ternyata sangat kuat sehingga satu peserta, yang berada di suatu tempat di peringkat ke-15 di peringkat keseluruhan, tiba-tiba turun ke urutan ke-4 di final, hanya karena kamikaze yang kompeten.

(Perbedaannya adalah bahwa dalam peringkat umum ada kartu sederhana dan kompleks. Pada kartu sederhana, bunuh diri bekerja lebih buruk.)

Pada akhirnya, strategi tersebut menggunakan ranjau, tetapi tidak menggunakan peledakan diri yang disengaja. Setelah final, ketika ada perjuangan untuk hadiah tambahan, modul TryPlantMine2 ditambahkan, yang mengimplementasikan demoman. Pada awalnya, karena kesalahan dalam kode, modul itu tidak terlalu efisien, tetapi dalam versi terbaru dimungkinkan untuk memperbaiki semuanya, dan strategi segera mulai naik peringkat dengan tajam. Itu sampai pada titik bahwa dia bahkan terbang ke atas 3, meskipun kemudian dia agak tergelincir.

Prinsip kerja: jika kita berada dalam posisi yang memungkinkan Anda untuk memasang ranjau, dan dapat menembak tidak lebih dari lima kutu, kami mensimulasikan tiga opsi: cukup tembak, taruh satu ranjau dan tembak, dua ranjau dan tembak. Untuk musuh dan sekutu, kami mensimulasikan gerakan menggunakan fungsi Dodge yang sama, memeriksa apakah mereka dapat melompat keluar dari zona ledakan sebelum kami siap untuk merusak (tidak yakin berapa banyak yang dibutuhkan). Untuk setiap opsi, kami memeriksa seberapa bermanfaatnya bagi kami pada poin, jika kami berada di kegelapan, kami dirusak (dengan cara ini kita dapat dirusak bahkan mengetahui bahwa dua unit kami dan satu musuh akan mati, tetapi kami masih akan menang) Pengaruh melemahkan

diri sendiri pada peringkat

temuan

Solusi sederhana seringkali lebih efektif daripada solusi yang lebih kompleks, tetapi ini memiliki batasnya sendiri. Dengan pendekatan ini, Anda dapat mencapai cukup tinggi, tetapi kemudian jatuh ke dalam perangkap ketika potensi untuk meningkatkan strategi sudah habis, dan tanpa perubahan radikal untuk meningkatkan kekuatan strategi tidak mungkin. Untuk masa depan, Anda harus memikirkan semacam opsi perantara.

Kesimpulan

Secara umum, saya menyukai kejuaraan ini, meskipun saya bias terhadapnya, karena ini adalah pertama kalinya saya berhasil mengambil tempat. Namun demikian, tanpa mempertimbangkan perasaan subjektif saya, tahun ini banyak yang telah diwujudkan pada tingkat yang lebih tinggi.

Untuk pertama kalinya dimungkinkan untuk berkomunikasi di Telegram dengan seseorang yang bertanggung jawab atas bagian teknis, dan yang segera menjawab semua pertanyaan, yang karenanya banyak terima kasih kepadanya.
Untuk pertama kalinya, visualisator bawaan bawaan hadir di localranner. Sebelumnya, untuk menghasilkan grafik debugging, Anda harus menulis sendiri.
Akhirnya, alih-alih Repeater utilitas tidak nyaman dan buggy, tombol "Repeat game" ditambahkan di LAN.

Tentu saja minusnya adalah eksploitasi besar-besaran dengan tambang.

Dan saya akan berharap bahwa prestasi saya di kejuaraan ini tidak disengaja dan bahwa lain kali saya akan dapat setidaknya menyelamatkan tempat, dan bahkan lebih baik untuk mengambil posisi yang lebih tinggi (bermimpi tidak berbahaya).

Kode bot dapat dilihat di github: github.com/silentnox/CodeSide

Bot saya untuk Piala AI Rusia 2019