Itu hari Rabu, ada pertemuan membosankan biasa di tempat kerja. Perancang menggaruk di belakang telinganya, dan tester mengubur dirinya di telepon. Sebuah mobil dinyalakan di luar jendela, dan saya menerima surat di telepon -
Piala AI Rusia 2018 dimulai. Sekitar tidak ada yang curiga, dan pada saat itu saya sudah tahu persis apa yang akan saya lakukan dalam satu setengah bulan berikutnya.
Halo semuanya, nama saya
Andrey Tokarev dan saya ingin berbagi pengalaman berpartisipasi dalam
Piala AI Rusia 2018 .
Apa ini
Piala AI Rusia adalah kompetisi kecerdasan buatan tahunan yang diadakan sejak 2012. Di sini Anda perlu menulis sebuah algoritma yang mengontrol seseorang atau sesuatu, dan seseorang ini atau sesuatu bersaing satu sama lain. Tahun ini perlu untuk mengendalikan robot bermain sepak bola.
Saya sudah memiliki pengalaman bermain di kompetisi tersebut. Secara khusus, saya berpartisipasi dalam Piala AI Rusia 2016 (tanpa hadiah) dan Piala AI Mini 2018 (posisi 2).
Ayo pergi
Pertama-tama, saya membuat kelas dunia game, objek, mengambil vektor 2 dan 3 dimensi dari kompetisi sebelumnya dan mengunggah semuanya ke repositori Git. Tentu saja, Anda dapat menggunakan objek dari paket bahasa, tetapi tidak ada vektor, mereka tidak dapat dimodifikasi, dan memang lebih nyaman menggunakan kelas Anda sendiri. Apa yang tidak saya tulis ulang adalah kelas arena, cocok untuk saya, dan tidak perlu mengubahnya.
Simulasi
Di sini kita memiliki dunia game, dan apa yang bisa kita lakukan?
Tapi ternyata tidak ada apa-apa, sampai kita bisa mensimulasikan dunia game, bahkan tidak menentukan apakah bola terbang ke gawang yang kosong. Jadi kami
menulis simulasi. Kode simulasi bukan bagian dari paket bahasa, itu disediakan dalam bahasa yang saya tidak tahu. Tapi sintaks C-nya sama, jadi copy-paste + definisi fungsi yang diperlukan, dan sim sudah siap 90%. Di mana perlu untuk mengatur tangan saya, saya mencoba melakukannya dengan hati-hati, karena kesalahan di sini bisa mahal dan menangkapnya tidak akan mudah. Saya masih berhasil membuat beberapa kesalahan, tetapi saya harus mengeluarkan sedikit darah.
Segera menjadi jelas bahwa jika Anda menggunakan simulasi jujur (100 kutu mikro), maka ini tidak cukup, itu jauh lebih menguntungkan untuk menghitung 100 opsi dengan satu microtik daripada satu opsi dengan 100 mikrotik. Saya masih meninggalkan 2 mikrotik sehingga perbedaannya tidak terlalu besar.
Dasar-Dasar Strategi
Jadi kita memiliki dunia game dan kita bisa mensimulasikan perubahannya. Jadi apa selanjutnya?
Ada beberapa pendekatan berbeda. Ketika ada beberapa gerakan yang mungkin dan kedalamannya tidak terlalu besar, Anda dapat mengambilnya dengan kekerasan: memilah-milah semua gerakan, bahkan pergerakan balik lawan, mereka memiliki gerakan mereka sendiri lagi ... mis. minimax Ketika ada banyak gerakan, Anda dapat membatasi mereka secara artifisial, misalnya, Anda dapat mengambil arah yang kelipatannya 15 derajat, melompat ke setiap centang ke-10, dan menggunakan minimax yang sama. Tapi pendekatan ini menurut saya cocok ketika hasilnya tidak terlalu sensitif terhadap perubahan kecil dalam gerakan, di sini penyimpangan satu derajat ke arah robot akan menyebabkan penyimpangan besar setelah tabrakan.
Ekstrem lainnya, ketika kita bergerak tanpa pencarian yang mendalam, adalah semacam heuristik. Pendekatan ini mungkin dapat dilakukan, tetapi menciptakan pemain sepak bola yang kuat dengan heuristik murni sangat sulit.
Tetapi kombinasi dari kedua metode ini terlihat menjanjikan: pertama-tama Anda dapat bergerak ke arah yang acak, dan kemudian menyelesaikan permainan dengan heuristik yang dapat berlari hingga bola dan melompat pada waktu yang tepat. Heuristik yang sama dalam kombinasi dapat digunakan untuk memprediksi gerakan lawan. Sebelumnya, saya sudah menggunakan sesuatu yang mirip dalam kompetisi, dan metode ini kurang lebih tidak terbukti buruk.
Dan jadi kami menulis heuristik (dalam RAIK-ovsky jargon pria pintar atau hanya pintar)!
Karena saya ingin melihat hasilnya secepat mungkin, smartgay ditulis dengan tergesa-gesa dan ternyata agak bodoh (bahkan kode itu memalukan). Saya baru saja menghitung waktu setelah itu robot dapat menangkap bola berdasarkan kecepatan saat ini dari bola dan kecepatan maksimum dari robot, dan berlari ke titik di mana bola akan berada pada waktu itu (tabrakan tidak diperhitungkan). Dia tidak tahu bagaimana cara melompat dan bahkan tidak memperhitungkan ketinggian bola, dia bisa dengan mudah berlari di bawah bola, dan jika bola bergerak terlalu cepat, dia biasanya berlari ke arah yang berlawanan. Karena pintar tidak bisa melompat, pertama saya membuatnya melompat pada jarak yang tetap dari bola, dan sedikit kemudian pilihan saat melompat jatuh di pundak acak yang hebat! Kurangnya pilihan lompatan yang rasional ternyata menjadi kelemahan besar, tetapi lebih pada itu nanti. Namun secara umum, smart clean tidak terlihat buruk, dan terkadang bahkan mencetak gol, meski juga di gol mereka sendiri.
Selanjutnya, kita membutuhkan fungsi evaluasi (OF).
OF awal tampak seperti ini: (1000 - centang) * goal + ball.z + beberapa fungsi posisi relatif robot dan bola sehingga berjalan hingga bola bahkan jika itu tidak dapat mencapainya. Di sini, tujuannya bisa -1,0,1 tergantung pada apakah ada tujuan dan kepada siapa, dan centang adalah centang dari awal simulasi di mana tujuan itu terjadi. Hal terakhir adalah robot tidak selalu menunda tujuan.
Sekarang kita membuat robot berjalan dalam arah acak sejumlah kutu acak, kemudian kita mentransfer kontrol ke pintar, yang mengarahkannya ke bola, pada saat acak itu melompat dan
memukul bola meleset. Selain itu, lebih baik berlari bukan ke tengah bola, tetapi dengan pergantian acak dengan jarak kecil, sehingga robot bisa mengenai sudut.
Simulasi berlangsung selama 2 detik, dan pada akhirnya OF dipanggil. Skenario seperti itu diulang beberapa kali untuk setiap robot dan yang terbaik dipilih berdasarkan peringkat.
Sejauh ini, strategi ini memiliki kelemahan serius: tidak memiliki memori - semuanya dihitung dari awal pada setiap tick, yang berarti strategi dapat melihat tujuan pada satu tick, dan tidak menemukannya pada yang berikutnya. Ini bukan masalahnya, Anda harus memperbaikinya - kami menyimpan opsi terbaik yang ditemukan untuk setiap robot dan menggunakannya kembali di centang berikutnya. Juga sekarang robot saling mengetahui tentang urusan masing-masing, misalnya, jika yang pertama akan mengenai bola, yang kedua tidak mengejar bola, tetapi mencoba mengambil umpan.
Penjaga gawang
Kami membutuhkan penjaga gawang. Kiper saya pada dasarnya berbeda dari penyerang karena diaktifkan ketika bola mendekati jarak tertentu ke gawang, jika tidak, ia hanya akan kembali ke titik dasar.
Ringkasan
Sekarang kami memiliki strategi dasar yang baik yang dapat melakukan semua yang diperlukan dan yang dapat dibangun di masa depan.
Mungkin semua yang dijelaskan di atas tampak sederhana dan logis, tetapi jujur di awal kompetisi tidak ada gambaran yang jelas tentang strategi yang tampak lebih dekat ke akhir, dan butuh dua minggu untuk menerapkan ini, dan ini adalah 1/3 dari kompetisi.
Sedikit tentang pengujian
Seiring waktu, Grails yang menggandakan kekuatan permainan akan semakin jarang terjadi, dan kita harus memilih perubahan yang memberi + 10-20% peningkatan gol. Dan kemudian ternyata keuntungan kecil seperti itu tidak mudah diidentifikasi. Untuk hasil menyeluruh, Anda membutuhkan ratusan gol yang dicetak, dan dengan frekuensi gol satu menit sekali, ini adalah waktu bermain yang berjam-jam. Untuk alasan ini, saya hampir tidak menguji strategi di server, tetapi mengendarai tes lokal yang panjang terhadap versi sebelumnya. Tetapi bahkan secara lokal menguji setiap perubahan selama setengah hari tidak akan sangat nyaman. Oleh karena itu, saya menerapkan sedikit "trik" - Saya menguji strategi terpotong. Jika, misalnya, pada server, saya menggunakan lebih dari 50 opsi per robot, maka hanya 10 secara lokal, ini memungkinkan saya untuk menjalankan tes dalam waktu yang dapat ditoleransi.
Perangkat tambahan
Selanjutnya, saya akan menjelaskan perbaikan utama, dan penilaian mereka dalam bentuk berikut: berapa persen versi baru mencetak gol lebih banyak daripada yang diterima dari yang lama. Yaitu jika misalnya yang baru mengalahkan yang lama dengan skor 120: 100 itu adalah + 20%, jika skornya 2 kali lebih banyak maka itu adalah + 100%.
- Kiper Anda harus mengalahkan gol. Jika dia tidak berhasil, beri dia lebih banyak waktu, tambah jumlah opsi hingga x10. + 15%
- Kadang-kadang, ketika penjaga gawang membentur bola, ia pergi ke penerbangan gratis dan sementara ia punya waktu untuk kembali ke tempatnya, mereka sudah mencetak gol. Segera setelah memukul bola, kami mencoba mengembalikannya ke tempatnya dan menambahkan centang yang dikembalikan ke penilaian dengan koefisien negatif kecil. + 20%
- Tendangan tambahan pada bola di depan gawang lain meningkatkan peluang gol, kami akan memberikan bonus di OF untuk ini. + 60%
- Eksperimen dengan nitro! Masih ada beberapa hari lagi sampai putaran pertama, tetapi saya memutuskan untuk menguji nitro terlebih dahulu. Secara intuitif, menurut saya nitro akan sangat memengaruhi permainan, karena di satu tangki Anda dapat melompat ke langit-langit atau terbang di atas seluruh bidang. Untuk mulai dengan, saya mengajarkan bagaimana menggunakan nitro hanya untuk penyerang, dan itupun hanya di udara, tapi saya belum mengumpulkan paket. Nitro digunakan selama penerbangan dalam arah 3 dimensi sekarang acak sekarang. Hasilnya adalah, secara halus, tidak terlalu, saya tidak berhasil memeras lebih dari + 20%, dan penggunaan nitro di tanah tidak membawa hasil apa pun. Jadi masalah dengan nitro sementara dikesampingkan, meskipun sejak saat ini saya mencoba melakukan tes dengan nitro dihidupkan.
- Terlalu banyak keacakan! Acak itu bagus, tentu saja, ia terkadang memberikan trik yang bahkan tidak dapat Anda pikirkan, tetapi di sisi lain, ketika ada terlalu banyak dari dirinya, kemungkinan bahwa semuanya akan bertepatan sangat kecil. Dan saya punya terlalu banyak. Saya memutuskan untuk mencoba mentransfer momen lompatan ke basis analitis. Karena tidak ada akselerasi horizontal di udara (lupakan nitro), mudah untuk menghitung momen pertemuan robot dan bola (t1), dan ketinggian bola pada saat itu (h1). Sekarang kita menghitung waktu (t2) setelah itu robot akan berada di ketinggian h1, lompat sekarang. Di sini kita mendapatkan persamaan kuadrat, jika tidak memiliki solusi atau t2 <t1, maka lompati lebih awal, jika tidak kita lompat.
Hasilnya sedikit mengejutkan saya, mengacaukan lompatan yang benar untuk kedua striker dan kiper, tes menunjukkan + 200%, mis. versi baru mengalahkan yang lama 3 kali dalam gol, Grail yang asli! Itu 17 Januari, setelah mengunggah strategi ke server, ia memenangkan peringkat 200+ dalam kemenangan 20 pertandingan dan menuju kotak pasir untuk sementara waktu.
- Kami mengajari kiper untuk bermain. Sampai kiper saya aktif, dia berdiri seperti pilar. Side walk yang mudah: x = ball.x / 4 memberi sedikit peningkatan.
- Lawan tidak harus diprediksi, tetapi diasumsikan! Melihat melalui pertandingan, saya perhatikan bahwa saya sering mendapatkan gol setelah kiper memukul bola tepat ke arah lawan dan dia mencetak gol untuk saya dengan cepat. Untuk memukul bola melewati lawan, Anda harus terlebih dahulu menentukan di mana ia bisa berada pada tick ke-n. Tentu saja, kami tidak akan mempertimbangkan nitro. Saya masih bisa menentukan kecepatan robot secara analitis, sepertinya ada persimpangan dua lingkaran. Tapi dia tidak bisa mengatasi wilayah yang dapat diakses. Yah, persetan dengan dia, kita adalah programmer (bukan oleh pendidikan), biarkan mesin menghitung untuk kita. Bagilah bidang menjadi n arah, pindahkan robot ke setiap arah, titik akhir akan menjadi simpul poligon, yang menentukan jangkauan.
Bagaimana cara menggunakannya? Saya menambahkan tanda centang di mana lawan bisa menyentuh bola untuk pertama kalinya, dengan koefisien yang baik di OF. Karena sekarang bukan skenario tindakan tertentu, tetapi semacam awan jangkauan dipertimbangkan untuk lawan, saya menghapus robot musuh segera setelah mereka bersentuhan dengan tanah.
Hasil + 40%. Selain itu, pendekatan ini memiliki dua keuntungan besar: penghapusan robot musuh di pertama mempercepat simulasi, dan ini, pada gilirannya, memungkinkan untuk memilah-milah lebih banyak pilihan, dan di kedua kita tidak perlu repot dengan kontrol lawan. Kesimpulan: untung!
- Kesalahan bodoh, tapi bagaimana tanpa mereka. Ada dua baris dalam simulator resmi:
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
Saya tidak tahu siapa caranya, tetapi saya membiarkan abs () berfungsi sebagaimana adanya, tetapi sia-sia. Abs-line () (jangan dikacaukan dengan std :: abs ()) mengambil nilai integer, yang berarti desimal terpotong. Dalam latihan, ini berarti bahwa saya mencatat gol hanya ketika bola sudah satu meter penuh di belakang garis gawang. Ganti abs () dengan fabs ()! Ini bukan pertama kalinya abs ini () telah mengecewakan saya.
- Nitro lagi. Babak kedua sudah dekat dan tidak ada tempat untuk menunda penggunaan normal nitro. Dia mengoptimalkan penggunaannya, memperhitungkan definisi lompatan, mengizinkan kiper untuk digunakan, dan juga mulai mengumpulkan paket secara sengaja oleh kiper.
- Mari kita kembali ke simulasi. Saya sudah mengatakan bahwa 100 opsi dengan satu mikrotik lebih menguntungkan daripada satu opsi dengan 100 mikrotik. Ini benar, tetapi ini tidak berarti bahwa dengan satu Mikrotik semuanya baik-baik saja, tanpa langkah-langkah tambahan perbedaannya cukup serius, dan ini membuatnya sulit untuk bermain sepak bola di tingkat profesional. Untuk meningkatkan akurasi simulasi, saya menerapkan metode berikut:
- Selama lompat, dua Mikrotik tambahan.
- Ketika kita menggabungkan banyak mikrotik, maka dalam bergerak lebih tepat menggunakan kecepatan rata-rata, dan bukan yang terakhir.
- Menggunakan pencarian biner, kami menemukan centang di mana tabrakan terjadi, dan kami melakukan dua sub-taktik: satu sebelum tabrakan, yang lain setelah. (Saya tidak memperhitungkan tabrakan bola dengan permukaan yang datar, di sana perbedaannya tampak tidak berarti bagi saya.)
- Berlari di sepanjang permukaan melengkung masih menyebabkan perbedaan besar dan kadang-kadang kiper terjawab karena hal ini. Karena itu, ketika penjaga gawang saya berada di permukaan melengkung, saya menggunakan 10 mikrotik.
Rata-rata, sekitar 1,4 mikrotik per kutu diperoleh, dan akurasinya mendekati ideal. Tentu saja, saya tidak mengacaukan optimasi ini pada suatu waktu, tetapi secara bertahap. Saya tidak tahu seberapa besar mereka memengaruhi kekuatan permainan, tetapi saya pikir itu sangat penting.
Apa yang kita miliki
Berkat sejumlah besar perbaikan signifikan, strategi ini tumbuh dengan mantap di peringkat, dan sebelum putaran kedua, hampir mencapai tonggak sejarah - peringkat 5000 Elo, dengan percaya diri mendapatkan tempat di tempat pertama.
Terkadang Anda bahkan tidak bisa percaya kombinasi apa yang muncul secara acak. Terima kasih kepada komunitas baik yang anonim untuk penemuan ini.Minggu lalu
Sehubungan dengan margin yang begitu baik, saya membiarkan diri saya tidak mengejar perbaikan kecil, tetapi untuk mencari sesuatu yang lebih global, terutama yang berkaitan dengan game 3x3. Namun, percobaan yang mengarah pada permainan tim yang lebih banyak, atau menanamkan pemain ketiga dalam peran khusus, atau untuk mengajar penjaga gawang untuk keluar selama kegagalan, gagal. Seluruh minggu dihabiskan hampir tidak berhasil. Meskipun demikian, beberapa hari sebelum final, saya masih memimpin dalam peringkat.
Dan sekarang hari terakhir sebelum final muncul dan saya mulai kalah dari satu, kemudian yang lain dan bahkan pesaing ketiga. Jika Anda tidak menambahkan, Anda dapat tetap tanpa hadiah. Tidak ada yang terjadi sepanjang minggu, apa yang bisa saya lakukan pada hari terakhir? Moodnya adalah - setidaknya menyerah.
Kebangkitan
Setelah menonton beberapa pertandingan yang hilang, saya perhatikan bahwa semua orang melompat
seperti kambing dengan nitro, mengoper bola di udara, tetapi milik saya tidak bisa mendapatkannya. Saya mencoba hal paling sederhana yang dapat menyebabkan perilaku ini - saya menambahkan ketinggian bola pada saat tumbukan dengan koefisien padat di OF. Hasil + 50%, wow! Terinspirasi oleh hasilnya, saya mulai memutar parameter secara intensif (yang saya abaikan selama seluruh kompetisi), menambahkan opsi pencarian baru, menambahkan kontrol waktu pada akhirnya, yang memungkinkan saya menggunakan waktu secara maksimal tanpa membahayakan hidup saya. Pada akhir hari ternyata + 150-200%, yaitu versi baru mengalahkan yang sebelumnya hampir tiga kali dalam gol! Ya, ya, yang hampir seminggu sebelum final merosot di tempat pertama dan mencapai peringkat yang belum pernah terjadi sebelumnya dalam sejarah kejuaraan 5000+. Di server, strategi itu berhasil diuji beberapa jam sebelum final. Setelah itu, saya menyiapkannya untuk peluncuran terakhir: pernyataan yang dinonaktifkan, menambahkan cek divisi ke nol, mengunggahnya ke server lagi, dan beralih ke mode siaga.
Bagian terakhir
Bagian pertama final berlangsung pada malam hari. Saya mengikuti hasilnya sampai saya tertidur, bangun pagi-pagi. 3 gelombang dimainkan (dalam satu gelombang masing-masing bermain dengan masing-masing), saya hanya kalah satu pertandingan melawan
TonyK , dan karena Anton kadang-kadang masih kalah dari pemain lain, saya memimpin dengan selisih 7 poin (2 poin untuk kemenangan). Kesenjangan yang cukup serius untuk 3 gelombang, tetapi tidak cukup untuk bersantai.
Pada hari terakhir, tentu saja, saya tidak bermaksud melakukan sesuatu yang serius, pada dasarnya memutar parameter. Beberapa perubahan telah dibuat, tetapi karena semuanya diuji dengan tergesa-gesa, saya bahkan tidak sepenuhnya yakin bahwa efeknya positif. Secara umum, kenaikannya adalah 0-20%. Tetapi Anton menambahkan secara signifikan dan setidaknya mulai bermain tidak lebih buruk dari saya.
Tidak ada hubungannya, saya harus mengirim apa yang ada, dan berharap untuk keberuntungan dan persediaan poin.
Final Bagian Dua
Untungnya, permainan diurutkan sehingga pada awalnya para pemimpin bermain di antara mereka sendiri, jadi tidak perlu khawatir, pertandingan pertama adalah melawan TonyK. Keberuntungan ada di pihak saya, saya memenangkan pertarungan pertama, serta semua pertandingan lainnya dalam gelombang ini, sementara TonyK kehilangan satu poin lagi. Kesenjangan 10 poin untuk dua gelombang hingga akhir hampir tidak mungkin untuk dimainkan, sekarang mungkin untuk bersantai.
Hasil akhir: 352 menang dan 2 kerugian (keduanya dari Anton), posisi pertama dengan selisih 12 poin.
Terima kasih dan sampah lainnya
Secara umum, saya benar-benar menyukai tugas tahun ini, itu adalah "untuk saya" (simulasi adalah milik saya, dan tiga dimensi tidak membuat saya takut) dan pertandingan itu spektakuler, saya pikir menarik untuk menonton tidak hanya para peserta.
Saya ingin mengucapkan terima kasih kepada penyelenggara atas kompetisi yang luar biasa.
Saya juga ingin mengucapkan terima kasih kepada semua peserta, terutama Anton Kozlovsky (
TonyK ) untuk kompetisi di final, Ivan Tyamgin (
tyamgin ) untuk kompetisi di kotak pasir dan Alexey Dichkovsky (
Commandos ) karena menahan diri untuk berpartisipasi dan dengan demikian meningkatkan peluang saya untuk menang.
Semoga sukses untuk semua orang di RAIK berikutnya!