Mini ai cup 2 atau hampir AgarIO - apa yang bisa dilakukan untuk menang

Halo semuanya! Kali ini saya ingin menulis tentang bagaimana saya berhasil memenangkan kompetisi Mini AI Cup 2 . Seperti pada artikel terakhir saya, praktis tidak ada detail implementasi. Kali ini tugasnya kurang banyak, tetapi bagaimanapun ada banyak nuansa dan hal-hal kecil yang mempengaruhi perilaku bot. Akibatnya, bahkan setelah hampir tiga minggu bekerja aktif di bot, masih ada ide tentang bagaimana meningkatkan strategi.



Di bawah memotong banyak gif dan traffic.

Yang gigih akan mencari tahu, sisanya akan lari ketakutan (dari komentar pada bagian singkat yang dikompresi).

Mereka yang terlalu malas untuk membaca banyak dapat pergi ke spoiler kedua dari belakang artikel untuk melihat deskripsi singkat singkat dari algoritma , dan kemudian Anda dapat mulai membaca dari awal .

Tautan ke sumber di github .

Pemilihan alat

Seperti terakhir kali, saya butuh banyak waktu untuk memikirkan di mana untuk memulai. Pilihannya adalah, antara lain, antara dua bahasa: Jawa, akrab bagi saya, dan sudah cukup dilupakan sejak masa siswa C ++. Tetapi karena sejak awal tampaknya bagi saya bahwa hambatan utama untuk menulis bot yang baik bukanlah kecepatan pengembangan seperti produktivitas dari solusi akhir, pilihan tetap jatuh pada C ++.

Setelah pengalaman sukses menggunakan visualizer saya sendiri untuk debugging bot di kompetisi sebelumnya, saya tidak ingin melakukannya tanpa kali ini juga. Tetapi visualisator yang saya tulis untuk diri saya sendiri di Qt for CodeWars tidak terlihat seperti solusi yang ideal untuk saya, dan saya memutuskan untuk menggunakan visualizer ini . Itu juga dibuat di bawah CodeWars, tetapi tidak memerlukan pemrosesan serius untuk digunakan dalam kompetisi ini. Kesederhanaan relatif dari koneksi dan kenyamanan untuk memohon rendering di mana saja dalam kode dimainkan untuknya.

Seperti sebelumnya, saya benar-benar ingin men-debug centang apa pun dalam permainan - kemampuan untuk menjalankan strategi pada saat sembarang dari permainan yang diuji. Karena plug-in visualizer tidak dapat menyelesaikan masalah ini, dengan bantuan pasangan #ifdef (di mana saya juga membungkus potongan-potongan kode yang bertanggung jawab untuk rendering) saya menambahkan ke setiap centang pada penghematan kelas Konteks, yang berisi semua nilai yang diperlukan dari variabel dari centang sebelumnya. Pada intinya, solusinya mirip dengan apa yang saya gunakan di Code Wizards, tetapi kali ini pendekatannya tidak begitu spontan. Setelah mensimulasikan seluruh permainan, Anda diminta memasukkan nomor centang permainan, yang harus dimulai ulang. Informasi tentang keadaan variabel sebelum centang ini diambil dari array, serta garis yang diterima oleh strategi input, yang memungkinkan saya untuk memainkan gerakan strategi saya dalam urutan yang diperlukan.

Mulai

Pada hari peraturan dibuka, saya tidak lewat dan pada malam pertama terlihat apa yang menanti kami. Dia tidak ragu untuk marah pada format input json (ya, itu nyaman, tetapi beberapa peserta mulai belajar YP lama yang baru atau sudah lama terlupakan di kompetisi seperti itu, dan mulai dengan parsing json bukan yang paling menyenangkan), melihat formula gerakan yang aneh dan entah bagaimana mulai membentuk kerangka masa depan strategi (untuk memahami artikel di masa depan, ada baiknya membaca aturan ). Selama 2 hari saya menulis banyak kelas seperti Ejection, Virus, Player dan lain-lain, membaca json, menghubungkan pustaka file tunggal untuk login ... Dan pada malam pembukaan kotak pasir tak bertingkat, saya sudah memiliki strategi yang hampir identik pada prinsipnya dengan C ++, tetapi secara signifikan, kode yang jauh lebih besar.

Dan kemudian ... Saya mulai mencari tahu pilihan, bagaimana mengembangkannya. Pikiran saat itu:

• Pencarian untuk negara-negara dunia tidak dapat direduksi menjadi nilai-nilai yang dapat mengalahkan minimax dan modifikasi;
• Bidang-bidang potensial bagus, tetapi mereka menjawab dengan buruk pertanyaan tentang bagaimana dunia akan mengubah n tick berikutnya;
• Genetika dan algoritma serupa akan bekerja, tetapi hanya 20 ms yang diberikan per langkah, dan kedalaman perhitungan akan diinginkan, sekilas, lebih dari sensasi yang dapat diproses menggunakan GA. Ya, dan Anda dapat bermain dengan pemilihan parameter mutasi "bahagia selamanya."

Saya pasti memutuskan satu hal: kita perlu melakukan simulasi dunia. Lagi pula, dapatkah perkiraan perhitungan "mengalahkan" perhitungan yang dingin dan akurat? Pertimbangan seperti itu, tentu saja, mendorong saya untuk melihat ke dalam kode yang seharusnya bertanggung jawab untuk mensimulasikan dunia di server, karena kali ini dimasukkan ke dalam domain publik bersama dengan aturan. Lagi pula, tidak ada yang lebih baik daripada kode yang harus secara akurat menggambarkan aturan dunia?

Jadi saya berpikir persis sampai saya mulai mempelajari kode yang seharusnya menguji bot kami di server dan secara lokal. Awalnya, dalam hal pemahaman dan kebenaran kode, semuanya tidak begitu baik, dan panitia, bersama-sama dengan para peserta, mulai secara aktif memprosesnya. Selama pengujian beta (menangkap beberapa hari setelah itu), perubahan dalam mesin permainan sangat serius, dan banyak yang tidak mulai berpartisipasi sampai saat ketika mesin pengujian tidak stabil. Tetapi pada akhirnya, menurut saya, mereka menunggu mesin yang bekerja dengan baik untuk permainan yang sangat cocok untuk format kompetisi. Saya juga tidak mulai menerapkan pendekatan serius sampai pelari lokal stabil, dan untuk minggu pertama tidak ada yang lebih masuk akal dilakukan di bot saya, kecuali untuk visualizer yang kacau.

Menjelang akhir pekan pertama di telegram, panitia membuat kelompok terpisah di mana diasumsikan bahwa orang akan dapat membantu memperbaiki dan meningkatkan pelari lokal. Saya juga mengambil bagian dalam pekerjaan di mesin dunia. Setelah berdiskusi dalam obrolan ini, sebagai ujian, saya membuat 2 permintaan tarik ke pelari lokal: menyesuaikan formula makan (dan perubahan kecil dalam urutan makan) dengan aturan, dan menggabungkan beberapa bagian menjadi satu agaric sambil mempertahankan kelembaman dan pusat massa ). Kemudian saya mulai berpikir tentang bagaimana memasukkan fisika tabrakan yang waras ke dalam kode ini, karena fisika yang ada di dunia permainan pada saat itu bekerja sangat tidak masuk akal. Karena tabrakan antara kedua agari tidak dijelaskan dalam aturan, saya meminta panitia untuk kriteria yang menurut saya implementasi logika semacam itu akan dapat diterima. Jawabannya adalah ini: agari dalam tabrakan harus "lunak" (yaitu, mereka bisa saling bertabrakan sedikit), sedangkan logika tabrakan dengan dinding tidak boleh disentuh (yaitu, dinding hanya harus menghentikan agarics, tetapi tidak mendorong mereka pergi). Dan permintaan tarik saya berikutnya adalah perubahan fisika yang serius.


Saya juga ingin menyoroti permintaan tarikan ini , yang secara signifikan mengurangi kode yang membingungkan dengan analisis keadaan dan sejumlah besar bug yang ditemukan (dan potensial) menjadi sesuatu yang jauh lebih dapat dipahami.

Menulis simulasi

Setelah membawa kode lokal pelari ke dalam bentuk waras, saya secara bertahap mulai mentransfer kode simulasi dunia dari pelari lokal ke bot saya. Pertama-tama, tentu saja, itu adalah kode untuk mensimulasikan pergerakan agaric, dan pada saat yang sama merupakan kode untuk menghitung fisika tabrakan. Butuh beberapa malam untuk menyimpan kode yang didesain ulang dari penulisan ulang bug (transfer logika tidak dilakukan dengan menyalin kode sama sekali) dan perkiraan perkiraan seberapa dalam perhitungan harus dilakukan.

Fungsi peringkat untuk setiap centang pada saat itu adalah +1 untuk makanan yang saya makan dan -1 untuk makanan yang dimakan musuh, serta nilai yang sedikit lebih besar untuk makan agariota masing-masing. Dalam konstanta untuk memakan agaric lain, pada awalnya ada perbedaan antara memakan lawan saya, lawan saya (dan, tentu saja, denda yang sangat besar untuk memakan agarika terakhir saya oleh lawan), serta dua lawan yang berbeda satu sama lain (setelah beberapa hari koefisien terakhir menjadi 0). Selain itu, kecepatan total untuk semua kutu simulasi sebelumnya, setiap kutu dikalikan dengan 1 + 1e-5 untuk mendorong bot saya melakukan tindakan yang lebih berguna setidaknya sedikit lebih awal, dan pada akhir simulasi, kecepatan untuk kutu terakhir ditambahkan sebagai bonus, juga sangat kecil . Untuk mensimulasikan pergerakan agaric, titik dipilih di tepi peta dengan langkah 15 derajat dari koordinat rata-rata aritmatika dari semua agari saya, dan sebuah titik dipilih, ketika mensimulasikan gerakan di mana fungsi estimasi mengambil nilai terbesar. Dan sudah dengan simulasi yang tampaknya primitif dan penilaian sederhana pada saat itu, bot cukup percaya diri menempatkan dirinya di 10 besar.


Pada malam Jumat dan Sabtu, simulasi penggabungan agariat, simulasi “merongrong” virus, dan menebak TTF lawan ditambahkan. TTF lawan adalah nilai perhitungan yang cukup menarik, dan dimungkinkan untuk memahami pada titik apa lawan membuat virus terbelah atau hanya dengan menangkap momen penerbangan yang tidak terkontrol, yang dapat bertahan dari sejumlah kecil kutu dengan viskositas yang besar dan hingga penerbangan melalui seluruh peta. Karena tabrakan agaric dapat menyebabkan sedikit kelebihan dari kecepatan maksimum mereka, untuk menghitung TTF lawan, saya memeriksa bahwa kecepatannya dalam dua kutu berturut-turut benar-benar sesuai dengan kecepatan sehingga Anda bisa mendapatkan dua kutu dalam satu baris dalam penerbangan gratis (dalam penerbangan gratis, agari terbang dengan lurus dan dengan memperlambat setiap centang ketat sama dengan viskositas). Ini hampir sepenuhnya menghilangkan kemungkinan positif palsu. Juga, selama pengujian logika ini, saya perhatikan bahwa TTF yang lebih besar selalu sesuai dengan id agaric yang lebih besar (yang kemudian saya yakinkan ketika mentransfer kode ledakan pada virus dan memproses pemisahan ), yang juga layak digunakan.

Setelah melihat pemisahan konstan di 3 teratas (yang memungkinkan mereka untuk secara signifikan mengumpulkan makanan di peta), sebagai ujian saya menambahkan perintah split permanen ke bot jika tidak ada musuh dalam radius visibilitas, dan pada hari Minggu pagi saya menemukan bot saya di baris kedua peringkat. Mengelola beberapa agitator kecil sangat meningkatkan peringkat, tetapi kehilangan mereka jauh lebih mudah jika Anda menemukan lawan. Dan karena rasa takut dimakan oleh para agiku sangat bersyarat (hukumannya hanya untuk makan dalam simulasi, tetapi tidak untuk mendekati lawan yang bisa makan), hal pertama yang ditambahkan adalah hukuman karena menyeberang dengan lawan yang bisa makan. Dan penilaian yang sama ini bekerja seperti bonus untuk mengejar lawan. Setelah memeriksa konsumsi CPU dengan strategi saya, saya memutuskan untuk menambahkan satu putaran simulasi lagi ketika split dilakukan pada centang pertama (logika ini, tentu saja, juga harus ditransfer ke kode saya dari pelari lokal), dan kemudian simulasi berjalan persis sama seperti sebelumnya . Logika semacam ini sangat tidak cocok untuk "menembak" musuh (meskipun kadang-kadang secara tidak sengaja itu terpecah pada saat yang sangat cocok), tetapi itu sangat baik untuk mengumpulkan makanan lebih cepat, yang merupakan apa yang dilakukan seluruh pasukan pada waktu itu. Modifikasi semacam itu memungkinkan kami untuk memasuki minggu berikutnya pada baris pertama peringkat, meskipun marginnya tidak signifikan.

Pada saat itu, ini sudah cukup, "tulang punggung" dari strategi itu berhasil, strategi itu terlihat sangat primitif dan dapat diperluas. Tapi yang benar-benar saya perhatikan adalah konsumsi CPU dan stabilitas kode secara keseluruhan. Oleh karena itu, terutama malam hari bagian kerja berikutnya dari minggu ini ditujukan untuk meningkatkan akurasi simulasi (yang mana visualizer banyak membantu), menstabilkan kode (valgrind) dan beberapa optimisasi kecepatan kerja.

Mari kita lanjutkan

Strategi pengiriman saya berikutnya, yang menunjukkan hasil yang jauh lebih baik dan lebih maju dari lawan (pada waktu itu), berisi dua perubahan signifikan: menambahkan bidang potensial untuk mengumpulkan makanan dan menggandakan jumlah simulasi jika ada lawan dengan TTF yang tidak diketahui di dekatnya.

Bidang potensial untuk mengumpulkan makanan dalam versi pertama cukup sederhana dan intinya adalah untuk mengingat makanan yang hilang dari zona visibilitas, mengurangi potensi di tempat-tempat di dekat bot musuh dan memusatkan perhatian pada zona visibilitas saya (dengan pemulihan berikutnya setiap saat). kutu sesuai dengan aturan). Ini sepertinya perbaikan yang bermanfaat, tetapi dalam praktiknya, menurut pendapat subjektif saya, perbedaannya kecil atau sama sekali tidak ada. Misalnya, pada kartu dengan inersia dan kecepatan tinggi, bot sering melewatkan makanan masa lalu dan kemudian mencoba untuk kembali ke sana, sementara kehilangan banyak kecepatan. Namun, jika dia memutuskan untuk mempertahankan kecepatan dan mengabaikan makanan yang dilewati, dia akan makan lebih banyak.


Utilitas subyektif yang sama sekali berbeda ternyata merupakan simulasi ganda musuh dengan TTF yang berbeda - minimum dan maksimum yang mungkin (dalam kasus saya tidak tahu TTF untuk semua agari terlihat di peta). Dan jika sebelumnya bot saya berpikir bahwa kumpulan musuh agarics akan menjadi satu kesatuan dan bergerak perlahan, maka sekarang dia memilih yang terburuk dari dua skenario dan tidak mengambil risiko dekat dengan musuh, tentang siapa yang dia tahu lebih sedikit daripada yang dia inginkan.

Setelah mendapatkan keuntungan yang signifikan, saya mencoba meningkatkannya dengan menambahkan definisi tentang titik di mana lawan memerintahkan agaranya untuk bergerak, dan meskipun titik ini dihitung dalam kebanyakan kasus dengan cukup akurat, ini saja tidak meningkatkan hasil bot. Menurut pengamatan saya, itu menjadi lebih buruk daripada kasus ketika agari lawan hanya bergerak ke arah yang sama dan dengan kecepatan yang sama seolah-olah lawan tidak melakukan apa-apa, jadi suntingan ini disimpan di cabang gitar yang terpisah sampai waktu yang lebih baik.


Ada juga upaya untuk mentransfer fungsi evaluasi ke penilaian massa yang diperoleh, upaya untuk mengubah fungsi mengevaluasi bahaya lawan ... Tapi sekali lagi, semua perubahan perasaan seperti itu menjadi lebih buruk. Satu-satunya hal yang berguna dengan fungsi menilai bahaya dari menjadi dekat dengan musuh adalah optimasi kinerja lain bersama dengan memperluas perkiraan ini ke jari-jari yang jauh lebih besar daripada jari-jari persimpangan dengan musuh (pada dasarnya seluruh peta, tetapi dengan penurunan kuadrat, jika sedikit disederhanakan - membuat kehadiran dalam lima jari-jari atau lebih dari lawan di wilayah 1/25 dari bahaya maksimum dimakan). Perubahan terakhir juga tidak terencana menyebabkan fakta bahwa agariks saya menjadi sangat takut untuk mendekati musuh yang jauh lebih besar, serta dalam hal ukuran mereka yang sangat superior lebih cenderung bergerak ke arah lawan. Jadi, itu ternyata menjadi pengganti yang sukses dan tidak intensif sumber daya untuk kode yang direncanakan untuk masa depan, yang seharusnya bertanggung jawab atas ketakutan serangan oleh lawan melalui perpecahan (dan sedikit bantuan dalam serangan seperti itu kepada saya nanti).

Setelah upaya yang lama dan relatif sia-sia untuk meningkatkan sesuatu, saya kembali lagi untuk memprediksi arah gerakan lawan. Saya memutuskan untuk mencobanya jika bukan hanya untuk mengganti saingan tiruan, kemudian lakukan seperti yang saya lakukan dengan opsi TTF minimum dan maksimum - mensimulasikan dua kali dan memilih yang terbaik. Tetapi untuk ini, CPU mungkin tidak cukup, dan dalam banyak game bot saya, mereka hanya bisa terputus dari sistem karena selera yang tak terpuaskan. Oleh karena itu, sebelum menerapkan opsi ini, saya menambahkan definisi perkiraan waktu yang dihabiskan dan, jika batas terlampaui, saya mulai mengurangi jumlah gerakan simulasi. Dengan menambahkan simulasi ganda musuh untuk kasus ketika saya tahu tempat di mana dia menuju, saya lagi menerima peningkatan yang agak serius di sebagian besar pengaturan permainan, kecuali untuk yang paling intensif sumber daya (dengan inersia tinggi / kecepatan rendah / viskositas rendah), yang disebabkan oleh penurunan kedalaman yang kuat Simulasi bisa menjadi sedikit lebih buruk.

Sebelum dimulainya pertandingan kutu 25k, dua perbaikan lebih bermanfaat dibuat: penalti untuk mengakhiri simulasi jauh dari pusat peta, serta mengingat posisi lawan sebelumnya jika ia meninggalkan garis pandang (serta mensimulasikan gerakannya pada saat itu).Implementasi penalti untuk posisi akhir bot dalam simulasi adalah medan bahaya statis yang sudah dihitung sebelumnya dengan nol bahaya dalam radius sedikit lebih besar dari setengah panjang lapangan bermain dan secara bertahap meningkat ketika bergerak menjauh dari lapangan bermain. Penerapan denda bidang ini pada titik akhir simulasi hampir tidak memerlukan CPU dan mencegah berjalan ekstra ke sudut-sudut, kadang-kadang menyelamatkan dari serangan musuh. Dan menghafal dengan simulasi rival berikutnya untuk sebagian besar memungkinkan kita untuk menghindari dua masalah yang kadang-kadang terwujud. Masalah pertama disajikan dalam GIF di bawah ini. Masalah kedua adalah bahwa jika musuh yang lebih besar hilang dari bidang pandang (misalnya, setelah penggabungan bagian-bagiannya), adalah mungkin untuk "berhasil" menyatukannya, juga memberi makan lawan yang sudah berbahaya.


Juga, titik-titik simulasi gerakan ditambahkan ke titik-titik di tepi peta: ke setiap agarik saingan dan dalam radius koordinat rata-rata aritmatika dari agariki saya setiap 45 derajat. Jari-jari diatur ke avgDistance dari koordinat rata-rata aritmatika dari agarics saya.

Persiapan akhir

Pada saat pembukaan permainan untuk kutu 25k dan lolos ke final, saya memiliki margin yang kuat, tetapi saya tidak berencana untuk bersantai.

Seiring dengan permainan 25k baru, berita datang: permainan selama final juga akan panjang 25k, dan batas waktu strategi untuk kutu telah menjadi sedikit lebih. Setelah mengevaluasi waktu yang dihabiskan strategi saya untuk permainan dalam kondisi baru, saya memutuskan untuk menambahkan versi lain dari simulasi: kami melakukan semuanya seperti biasa, tetapi selama simulasi saat bepergian dan melakukan split. Ini, antara lain, membutuhkan penggunaan simulasi yang ditemukan pada langkah sebelumnya, tetapi dengan pergeseran 1 langkah (misalnya, jika kami menemukan bahwa memisahkan 7 kutu dari yang sekarang, maka langkah selanjutnya kami ulangi hal yang sama, tetapi kami sudah melakukan split pada langkah ke-6). Ini secara signifikan menambahkan serangan agresif pada saingan, tetapi memakan lebih banyak waktu strategi.


Semua penyempurnaan lebih lanjut secara eksklusif terkait dengan efisiensi simulasi jika terjadi kekurangan TL: optimisasi urutan pemutusan bagian-bagian tertentu dari logika tergantung pada CPU yang dikonsumsi. Di sebagian besar gim, ini tidak seharusnya mengubah apa pun, tetapi menghasilkan sesuatu yang lebih benar maka tidak berhasil.

Alih-alih sebuah kesimpulan

Secara umum, awal kompetisi ini ternyata agak berminyak, tetapi dalam satu setengah minggu pertama tugas dibawa ke bentuk yang cukup dimainkan dengan bantuan para peserta. Awalnya, tugas itu sangat bervariasi, dan memilih pendekatan yang tepat untuk menyelesaikannya tidak tampak seperti tugas yang sepele. Yang lebih menarik adalah menemukan cara untuk meningkatkan algoritme tanpa terbang melebihi batas konsumsi CPU. Banyak terima kasih kepada penyelenggara untuk kompetisi dan untuk meletakkan kode sumber dunia untuk akses terbuka. Yang terakhir, tentu saja, sangat menambah masalah bagi mereka di awal, tetapi sangat memudahkan (jika tidak dikatakan, yang memungkinkan pada prinsipnya) pemahaman peserta tentang perangkat simulator dunia. Terima kasih khusus atas kesempatan untuk memilih hadiah! Jadi hadiahnya keluar jauh lebih berguna :-) Mengapa saya perlu MacBook lain?