Halo semuanya!
Saya seorang siswa tahun ketiga, dan pada awal studi saya di universitas saya belajar tentang
Piala Ai Rusia , dan kemudian
Piala Mini Ai , kompetisi dalam kecerdasan buatan, dan mulai aktif berpartisipasi di dalamnya, menunjukkan hasil yang baik. Kali ini, RAIC masuk tepat ke sesi, jadi tidak ada yang bisa menghentikan saya :) Dan hari ini saya ingin memberi tahu Anda bagaimana saya berhasil mengambil tempat kedua.
Aturan kompetisi dapat ditemukan di situs web kompetisi, serta dalam
artikel ini. Tautan ke profil saya:
russianaicup.ru/profile/TonyK .
Di satu sisi, tugas tahun ini mirip dengan tugas tahun-tahun sebelumnya, dan tampaknya solusi ideologis akan sangat mirip dengan yang sebelumnya (Agar IO dan Mobil Gila); setelah sekitar satu minggu saya akan bosan dan bosan berpartisipasi.
Di sisi lain, saya mengerti bahwa saya telah belajar banyak dalam kompetisi sebelumnya dengan fisika dan sekarang saya bisa menerapkan pengalaman ini, tidak menginjak penggaruk lama dan, pada akhirnya, menunjukkan hasil yang lebih baik.
Adapun visualisasi, saya memutuskan bahwa saya akan memiliki cukup proyeksi pada sumbu yang berbeda, atau ditampilkan pada sudut tertentu. Tetapi saya sangat keliru, dan jika bukan karena visualizer ajaib yang dibangun di dalam Local Runner, yang kemudian ditambahkan oleh penyelenggara, saya harus meminjam visualisator 3D dari para peserta yang menghabiskan fase pengujian beta menulisnya dan meletakkannya di domain publik.
Kali ini pseudo-code dari simulator tersedia, yang menyamakan kemungkinan mereka yang tahu cara membalik fisika dan menulis bot yang keren, dan mereka yang tidak bisa membalik fisika, tetapi yang juga bisa menulis bot yang kuat. Saya pikir ini adalah keputusan yang baik oleh panitia.
Hal pertama yang saya lakukan adalah menulis ulang kode simulator dari dokumentasi di C ++, dan kemudian mengukur waktu simulator di komputer lama saya dan di server. Dalam kasus kedua, ternyata dua kali lebih cepat, meskipun ini diharapkan. Saya membayangkan berapa kali dan seberapa dalam saya bisa mensimulasikan. Segera menjadi jelas bahwa kita harus melupakan simulasi jujur 100 mikrotik (di server satu tik fisika dibagi menjadi 100 "mikrotik"), dan akan perlu untuk menyelesaikan masalah dengan akurasi dalam cara bundaran.
Karena fakta bahwa shell diatur sedemikian rupa sehingga permintaan tindakan untuk setiap robot dipanggil secara terpisah pada setiap centang, saya menerapkan logika sederhana: pada saat robot pertama diminta melakukan suatu tindakan, program menemukan tindakan untuk semua robot, mengingat dan memberikan aksi yang pertama, dan ketika aksi diminta dari robot yang lain, ia mengembalikan apa yang diingatnya.
Saya tidak sabar untuk mengirim bot ke pertempuran segera. Saya memutuskan untuk membuat lintasan acak dan memilih yang terbaik. Pada saat yang sama, ia ingin set yang dihasilkan memungkinkan untuk melakukan beberapa tindakan kompleks, misalnya, mengitari bola dari sisi kanan, dan kemudian memukul.
Sebuah lintasan adalah rencana aksi. Awalnya, lintasannya adalah ini:
- atur aksi pada sudut acak;
- pada centang acak lintasan, ubah sudut ke sudut acak lainnya;
- melompat sekali ke tanda centang acak lintasan.
Ruang lintasan seperti itu sangat cocok untuk pencarian acak dengan jumlah simulasi yang saya (dan, mungkin, semua orang pada saat itu) mampu lakukan dengan simulator mentah dari dokumentasi. Lintasan yang baik sering ditebak, dan karena lintasan terbaik dari kutu sebelumnya dipertahankan, pencarian ternyata membentang dalam waktu.
Semua objek ditempatkan di simulator: robot saya, robot lawan dan bola. Penilaian adalah yang paling sederhana: jumlah jarak dari bola ke gawang musuh di semua titik lintasan dan nilai-nilai besar untuk gawang kepada seseorang. Simulasi kedalaman 200 ticks. Musuh diprediksi pada kecepatan terakhir mereka.
Saya segera menambahkan aksi terpisah untuk robot kedua, serta pembatalan paksa melompat, jika selama penerbangan tidak ada kontak dengan bola, sehingga tidak melompat sia-sia. Pada saat yang sama, robot saya mendapatkan lebih dari separuh waktu dan tahu lintasan terbaik satu sama lain. Sekarang
gol pertama telah dimulai untuk lawan yang kuat, yang sudah memiliki kiper dan beberapa logika yang lebih rumit.
Ternyata lebih jauh bahwa saya tidak mempertimbangkan jarak ke gerbang musuh, tetapi ke titik di sisi tengah lapangan (bercampur
x dan
z ), tetapi ini tidak mempengaruhi strategi dengan cara apa pun. Bagus bahwa setelah koreksi itu tidak menjadi lebih buruk. Ini sering terjadi ketika Anda menulis bot.
Kemudian dia menambahkan kiper dengan mengubah skor: dia menjatuhkan penalti untuk bola di bagian saya di lapangan dan untuk gol kepada saya, dan juga memperkirakan jarak dari penjaga gawang ke tujuan saya. Sekarang kiper berdiri di depan gawang dan menendang bola. Optimasi penting adalah bahwa jika bola tidak berada di setengah lapangan saya, maka 90% dari waktu diberikan kepada penyerang dan 10% dari kiper, jika tidak 50%.
Penilaian lintasan robot di setiap titik dikalikan dengan 0,9 ^ kedalaman, saya menurunkan koefisien ini secara empiris, seperti seluruh penilaian. Nilai-nilai koefisien tidak berubah untuk waktu yang sangat lama pada prinsip "itu bekerja, oke."
Dia mulai
memenangkan puncak dan dengan cepat naik peringkat. Fase beta telah berakhir.
Untuk waktu yang lama saya tidak punya ide tentang strategi, versi terkenal untuk pengeditan kecil, perbaikan bug (ternyata saya menganggap kekuatan bouncing rata-rata
(MAX_HIT_E - MIN_HIT_E) / 2 ), dan juga mengoptimalkan simulator. Peran penting dimainkan oleh jumlah lintasan yang berhasil saya atur per tick, jadi saya fokus pada optimasi. Sinus dan akar kuadrat yang dihapus. Menambahkan kecepatan nol yang tidak mungkin pada lintasan sebelum atau setelah mengubah sudut. Skor sedikit berubah.
Versi 16
disimpan untuk waktu yang lama di puncak tabel, tetapi seminggu setelah akhir pengujian beta, seperti yang diharapkan, banyak yang mulai
menang .
Saya mencoba memperhalus lintasan dengan jumlah jarak terdekat dari musuh ke bola, dan saya mendapat perilaku yang sangat menarik. Robot saya, ketika mereka tidak bisa mengenai untung, sering mulai memblokir musuh, menghancurkan lintasan mereka dan mencegah mereka berlari ke bola, kadang-kadang ternyata sangat berhasil dan diam-diam.
Selanjutnya, saya memperbaiki akurasi sambil melompat. Jika seseorang melompat pada centang saat ini, maka pertama kita lakukan 1 microtik dua kali, dan kemudian 98 microtics, dan kemudian saya mencoba koefisien heuristik untuk mengkompensasi hilangnya akurasi dalam kasus ketika di beberapa mikrotik kecepatan maksimum tercapai. Perbaikan
sangat membantu dan ada lebih akurat, hit pra-dihitung.
Juga pada saat ini saya mulai menampilkan di situs di antara informasi debugging jumlah iterasi yang berhasil saya selesaikan. Ada 250 dari mereka pada 200 kutu, secara total saya memiliki 50.000 kutu simulasi selama waktu yang dialokasikan untuk strategi saya per kutu.
Kemudian saya menyalakan lintasan mutasi. Ini sangat meningkatkan strategi. Di sekitar setengah dari semua iterasi, itu bukan lintasan baru yang digunakan, tetapi yang terbaik dengan nilai yang sedikit berubah, yang memungkinkan untuk berkumpul di suatu tempat, misalnya, ke maksimum lokal. Itu
ternyata menjadi strategi yang
kuat pada waktu itu, yang saya putuskan untuk hengkang sampai putaran pertama, walaupun itu masih dua minggu sebelum itu. Tetapi setelah beberapa hari dia tidak lagi mendominasi puncak.
Saya menghabiskan beberapa waktu menjauh dari keacakan lengkap, misalnya, saya mencoba dengan pencarian ternary untuk menemukan sudut di mana robot perlu mempercepat untuk memukul bola. Tetapi ini tidak selalu berhasil, dan saya tidak tahu bagaimana mengembangkan ide ini lebih jauh.
Robot saya tahu bagaimana cara melompat hanya sekali per lintasan, tetapi ketika mereka berada di tanah dan ingin melompat, dan kemudian memukul bola di udara, mereka tidak tahu bahwa ketika Anda menyentuh bola Anda bisa melompat kedua kalinya, sehingga memukul bola dengan keras, dan bukan hanya mendorongnya.
Ini sudah diperbaiki, dan sekarang simulator, ketika dia memperhatikan bahwa seseorang dapat memukul bola dengan kutu saat ini, memutar mundur satu kutu dan memaksa robot untuk melompat dengan kekuatan maksimum. Sekarang, berdiri di tanah, robot itu tahu bahwa itu akan mendorong tanah dan tidak hanya mendorong, tetapi memukul bola dengan lompatan kedua.
Saya mengerti bahwa ketika nitro dan robot lain ditambahkan, semuanya akan bengkok karena kurangnya iterasi. Juga di tempat yang berbeda saya punya masalah besar dengan akurasi, yang saya tidak tahu bagaimana menyelesaikannya. Saya tidak melihat
solusi analitis atau
cara manajemen yang cerdas .
Saya membutuhkan strategi yang sama sekali baru, atau simulator ajaib yang menggabungkan akurasi dan kecepatan, dan pada tahap akhir akan memberi saya lintasan yang cukup untuk beralih. Saya tidak menemukan strategi baru (secara mengejutkan), dan mulai mengerjakan simulator.
"Simulator cerdas"
Hal pertama yang saya inginkan adalah ketepatan.
Saya mensimulasikan 100 Mikrotik pada suatu waktu, meskipun tabrakan - atau peristiwa lain - terjadi pada salah satu dari seratus Mikrotik ini. Jika Anda mengabaikan ini, objek bertabrakan lebih lambat dari kenyataan (selalu pada mikrotik ke-100), dan karenanya memantul secara berbeda. Menjelang akhir lintasan, kesalahan kecil ini dapat berubah menjadi ketidakakuratan besar. Sebagai contoh, kami berpikir bahwa bola mengenai gawang musuh, tetapi pada kenyataannya itu akan memantul
ke gawang
kami dari pos.
Sangat mudah untuk melihat bahwa dalam situasi di mana tabrakan terjadi pada mikrotik ke-i, daripada menghitung semua 100 mikrotik, cukup untuk menghitung mikrotik
i - 1 pertama pada suatu waktu (pada kenyataannya, langkah fisika dipertimbangkan untuk waktu tertentu
dt , dan sekarang waktu ini akan menjadi
t * (i - 1) , di mana
t adalah waktu yang sesuai dengan satu Mikrotik). Sekarang Anda perlu mensimulasikan 1 mikrotik (
dt = t ) dan
100 - i mikrotik yang tersisa. Kami mendapatkan hasil yang persis sama hanya dalam tiga simulasi, bukan seratus. Satu-satunya masalah adalah bahwa kita tidak tahu di mana mikrotik tabrakan akan terjadi.
Berada di beberapa centang tetap simulasi, kita dapat membuat sejumlah mikrotik dari 1 hingga 100 dalam satu simulasi dan melihat apakah ada tabrakan atau tidak. Dalam hal ini, gambar akan menjadi seperti ini: pada awalnya tidak ada sentuhan, tetapi mulai dari sejumlah mikrotik dan hingga seratus ada sentuhan. Kecuali dalam kasus yang sangat jarang, ketika tidak ada kontak pada awalnya, maka ada sentuhan pada beberapa segmen mikrotik, dan sekali lagi tidak ada sentuhan lagi.
Oleh karena itu, dimungkinkan untuk menemukan Mikrotik di mana tabrakan terjadi menggunakan pencarian biner untuk 10 simulasi dalam kasus terburuk. Dan seperti yang dijelaskan sebelumnya, untuk tiga simulasi, Anda bisa mendapatkan keadaan dunia melalui 100 mikrotik dengan akurasi sempurna.
Bahkan, ada beberapa jenis peristiwa lain selain tabrakan, dan beberapa bisa terjadi dalam satu centang, jadi hanya acara pertama yang terletak dalam satu dikotomi, kemudian acara kedua terletak pada akhiran sisa dari dikotomi centang, dan seterusnya. Dengan demikian, kutu dianggap sebagai segmen dari beberapa mikrotik per simulasi, sampai semua peristiwa dihitung.
Jadi masalah diselesaikan dengan akurasi. Tetapi karena kenyataan bahwa ada 5 objek dalam simulasi, dan oleh aturan final seharusnya ada 7, dan semuanya sering crash, dikotomi rata-rata dipanggil terlalu sering, dan ini bekerja sangat lama. Oleh karena itu, saya melanjutkan ke tahap kedua pengembangan simulator - optimasi.
Tentunya, ketika lintasan salah satu robot berhasil melaluinya, semua benda lain yang tidak dapat dihantam robot ini bergerak sama setiap saat. Jelas bahwa menghitung ulang keadaan mereka dengan simulator - misalnya, menghitung tabrakan berat dengan arena - tidak perlu.
Sebelum memilah lintasan untuk robot tertentu, cukup untuk mensimulasikan dan mengingat dengan jujur objek-objek yang tersisa dari status mereka di semua waktu, dan kemudian ambil status ini dari memori. Kami menyebutnya objek statis, dan robot yang lintasannya diurutkan adalah dinamis.
Jika tiba-tiba beberapa objek dinamis memengaruhi (bertabrakan) dengan objek statis, kami menambahkan objek statis ini ke objek dinamis hingga akhir simulasi lintasan saat ini. Bahkan, pada tahap penyimpanan keadaan untuk objek statis, grafik pengaruh satu sama lain dibangun, dan kemudian digunakan untuk mentransfer objek statis dengan benar ke objek dinamis. Sebagai contoh, robot musuh menabrak bola, dan kami membuat jalur tempat kami merobohkan robot musuh sebelum menabrak bola. Sekarang bola akan terbang lebih jauh, dan selama simulasi, ketika robot musuh ditambahkan ke objek dinamis, perlu dicatat bahwa bola harus ditambahkan ke objek dinamis sedikit kemudian, pada centang di mana robot musuh akan mengenai bola jika kita tidak mengganggunya . Dalam kasus umum, ini dilakukan secara rekursif sesuai dengan grafik pengaruh.
Sekarang simulator tidak menghitung semua objek, tetapi hanya yang dinamis, dan ini, rata-rata, adalah satu setengah objek, bukan tujuh, dan dikotomi yang panjang lebih jarang digunakan. Ternyata sangat cepat, dan tidak lagi harus menderita di final dengan robot tambahan - keren!
Versi 26 dengan simulator baru dan kedalaman simulasi berkurang dari 200 menjadi 100 dikirim untuk dimainkan di babak pertama. Tapi itu mengandung beberapa bug, dan tidak ada keuntungan yang jelas.
Masalah terakhir dengan akurasi tetap: gerakan di sepanjang arena. Dalam hal ini, untuk mencapai akurasi absolut, perlu menghitung secara jujur 100 mikrotik. Solusinya sangat sederhana: selalu melompat dari semua permukaan kecuali lantai. Tidak ada pembulatan - tidak ada masalah.
Selanjutnya, untuk beberapa waktu saya dioptimalkan, debazed dan, melihat permainan dengan strategi yang lebih cerdas, saya mengambil konstanta penilaian baru. Itu menjadi jauh lebih baik, strateginya naik tinggi di peringkat dan versi ke-37 telah mencapai hasil terbaik dari semua strategi saya di kotak pasir sepanjang waktu sebelum final.
Mulai saat ini, saya menyewa mesin 32-core di layanan cloud untuk menjalankan strategi saya satu sama lain, dan mulai banyak bereksperimen dengan segala sesuatu dalam satu baris. Mengubah konstanta. Saya mencoba menggunakan strategi saya sendiri untuk memprediksi tindakan musuh, tetapi ini tidak membantu bahkan dalam permainan melawan strategi saya.
Dengan memecahkan persamaan, ia belajar menghitung aksi terakhir musuh dan mulai memprediksi perilakunya lebih lanjut. Dukungan tambahan untuk nitro: titik acak pada permukaan bola dipilih untuk tindakan. Melakukan banyak pengeditan kecil. Tetapi tidak ada banyak kemajuan. Pada awal babak kedua, 4-5 atasan terus memenangkan saya
Meski begitu, saya tidak putus asa. Saya memiliki dua perbaikan yang saya rencanakan untuk dilaksanakan sebelum final, dan saya berharap mereka akan sangat meningkatkan strategi. Saya memutuskan untuk tidak menangani mereka sampai kotak pasir mulai sesuai dengan aturan terakhir, dan sebagai gantinya menghabiskan waktu men-debug dan mengoptimalkan apa yang sudah dilakukan untuk meminimalkan kemungkinan bug jahat dalam minggu terakhir, ketika setiap menit diperhitungkan.
Minggu terakhir sebelum final dimulai.
Perbaikan pertama yang saya buat adalah ini. Dalam pertandingan, dalam kasus umum, sebagian besar masalah saya, dan strategi lainnya muncul ketika lawan menguasai bola. Dia entah bagaimana memukulnya, melewati, secara umum - kontrol. Memprediksi lintasan bola dan merencanakan lebih lanjut beberapa tindakan menguntungkan dalam kasus ini tidak mungkin, tetap melakukan "apa pun" sampai lawan membuat kesalahan dan mentransfer kendali bola ke robot saya. Dan setelah ini, Anda harus mencoba untuk tidak melakukan tindakan seperti itu yang bisa mengarah pada fakta bahwa bola akan kembali bersama musuh.
Dengan kata lain, pada saat merencanakan lintasan, saya ingin memperhitungkan kemungkinan posisi lawan dan mencoba untuk tidak memukul bola di sana. Saya memutuskan untuk menggunakan bidang potensial empat dimensi (tiga dimensi pertama adalah koordinat, sisi kubus sama dengan diameter robot, dan dimensi keempat adalah waktunya), yang akan saya isi, menghasilkan lintasan musuh acak.
Kemudian, ketika mengevaluasi lintasan untuk robot saya, saya menghitung jumlah di semua kubus yang melintasi bola pada titik waktu yang sesuai, dan dikalikan dengan koefisien yang melebihi semua nilai lain dalam penilaian. Artinya, bidang potensial diperhitungkan dengan prioritas tertinggi setelah tujuan. Itu juga memungkinkan menghilangkan musuh dari simulasi setelah 30 tick pertama (musuh bisa melakukan apa saja selama waktu ini saat berada di tanah, dan ramalan jauh yang tidak akurat seperti itu hanya mengganggu) jika mereka tidak ada di udara (sepertinya tidak ada yang akan berada di dalam udara untuk mengubah lintasan dengan cara yang kompleks menggunakan nitro).
Dengan membuat lintasan acak untuk musuh, adalah mungkin untuk mengetahui waktu minimum yang diperlukan baginya untuk memukul bola. Nilai ini berguna untuk menyelesaikan masalah dengan lompatan awal kiper saya keluar dari gerbang. Banyak gol yang dicetak untuk saya karena kiper saya melompat lebih awal dan menjadi tidak terkendali di udara. Setelah itu, musuh dengan mudah memperkirakan bagaimana penjaga gawang saya akan terbang dan, jika ia bisa, mengubah lintasan bola sebelum kiper saya mencapainya. Sekarang saya membatalkan lompatan penjaga gawang jika musuh dapat mengenai bola lebih awal dari rencana penjaga gawang saya.
Ternyata, tanpa kerusakan signifikan pada strategi, adalah mungkin untuk menghitung lintasan tidak setiap kutu, tetapi melalui satu. Dengan mengurangi separuh waktu berjalan, saya menggandakan jumlah rata-rata iterasi. Beberapa keajaiban terjadi di sini. Tampaknya jika kita menghitung lintasan setiap detik dan menggandakan jumlah iterasi, maka jumlah rata-rata iterasi tidak akan berubah. Namun pada kenyataannya, simulator akan menghitung dua kutu (200 mikrotik) per simulasi, bukan satu. Dan lintasannya akan menjadi 50, tidak dalam 100. Itu sebabnya jumlah rata-rata iterasi akan berlipat ganda.
Tetap beberapa hari sebelum final. Meskipun strategi saya mulai kebobolan lebih sedikit gol karena kontrol bola yang baik, saya tidak mulai mencetak lebih baik. Karena itu, saya harus memotivasi dia dengan koefisien ketika segera untuk tujuan lawan. Semakin cepat suatu gol dicetak, semakin besar rasionya. Dan koefisien ini tumbuh sangat banyak untuk melebihi sisa skor dan tidak takut pada bidang potensial, ketika, misalnya, 10 tick tersisa sebelum skor.
Menambahkan perhitungan di mana musuh mengirim nitro. Ini dilakukan dengan menggunakan brute force dengan langkah tertentu. Juga, kiper mulai mengisi cadangan nitro, ketika tidak ada yang mengancam tujuan saya.
Peningkatan besar kedua adalah menggunakan minimax. Jika penggunaan kekuatan dampak yang berbeda untuk musuh selama pembangunan lintasan statis mempengaruhi penerbangan bola, maka selama pencarian kedua opsi dipertimbangkan, dengan kekuatan dampak maksimum dan minimum musuh, dan minimum perkiraan diambil.
Di final, saya punya 7 opsi untuk lintasan ketika robot berada di tanah:
- 2 sudut tanpa lompatan;
- 2 sudut dengan lompatan;
- 2 sudut dengan lompatan dan nitro codirectional speed;
- 2 sudut dengan lompatan dan nitro mengimbangi gravitasi;
- 1 sudut dengan lompatan;
- 1 sudut dengan kecepatan codirectional lompat dan nitro;
- 1 sudut dengan lompatan dan nitro mengkompensasi gravitasi (tidak digunakan karena bug, diperhatikan saat menulis artikel).
dan dua opsi saat robot ada di udara:
- nitro ke titik acak pada permukaan bola dan gaya impak acak;
- kekuatan dampak acak.
Ada kompetisi beberapa jam sebelum final, tetapi strategi saya jelas lebih baik. Sepertinya semuanya sudah dilakukan, saya belum tidur lebih dari sehari, dan tidak ada yang bergantung pada saya. Tetap menonton. Dua jam sebelum final, Andrei mengirim grail yang baru dipanggang dan berhasil memenangkan tempat pertama. Sejarah partisipasinya dapat ditemukan di sini:
habr.com/en/post/440398 .
Di interval antara tahap-tahap final, saya menambahkan bidang potensial mendorong bola menjauh dari tujuan saya, terlepas dari segala sesuatu yang lain, dan ini, sepertinya bagi saya, menyamai saya dengan Andrei. Tapi itu sudah terlambat, karena saya kehilangan 7 poin di babak pertama, dan bahkan 3/3 kemenangan di babak kedua tidak cukup.
RAIC adalah kompetisi yang sulit dan hadiah diberikan kepada peserta sangat, sangat sulit. Ketika seorang peserta berada di puncak tabel, baginya ini bukan hanya hiburan - itu adalah perjuangan. Ada banyak hal kecil yang perlu dipertimbangkan ketika menulis strategi yang kuat. Setiap keputusan yang dibuat dapat secara signifikan mempengaruhi hasil.
Kode sumber untuk strategi akan tersedia di
sini .