Jadi

Nama saya, seperti tahun lalu, adalah Andrei Rybalka, hanya saja saat ini saya berusia 33. Dan, karena saya berada di sepuluh besar, saya memutuskan untuk berbagi pendekatan saya dalam menulis bot permainan untuk Piala AI Rusia 2018 lagi.

Kali ini tugasnya adalah sepakbola. Tugas itu sendiri agak mengingatkan pada 2014 RAIC, ketika itu hoki, tetapi solusinya benar-benar berbeda.

Kali ini dunia tiga dimensi dan tiga dimensi ini digunakan secara penuh. Permainan itu sendiri paling mengingatkan pada Liga Rocket .

Saya tidak akan menanggung bagian pengantar, lebih mudah untuk menunjukkan tampilannya. Anda dapat menonton pertandingan di situs web atau di video:

Agar hidup kami tidak terlihat terlalu manis, para pengembang, selain tidak menentukan dunia permainan, juga membagi centang permainan menjadi 100 subwoofer, yang pada awalnya mengakhiri simulasi yang akurat untuk sebagian besar peserta, dan bahkan lebih lagi bagi saya, berniat untuk menulis bot di Jawa lambat.

Juga, saya harus mengatakan bahwa kejuaraan dibagi menjadi beberapa ronde, yang mungkin akan lebih tepat untuk memanggil ronde.

Secara singkat tentang sistem turnamen

Sebagai permulaan, 2 minggu diberikan untuk pengembangan. Kemudian babak pertama berlalu. 300 yang terbaik melangkah lebih jauh.

Setelah putaran, aturan permainan berubah (khusus, nitro ditambahkan ke permainan) dan 2 minggu lagi diberikan, setelah itu putaran kedua berlalu.

Kemudian aturannya rumit lagi (pemain ketiga ditambahkan), satu minggu lagi diberikan dan kami memainkan final.

Tapi ini bukan akhirnya. Setelah final ada satu minggu lagi, di mana sandbox hanya berhenti, dan 6 yang terbaik di dalamnya, tidak termasuk pemenang final, juga diberikan. Perbedaan mendasar antara final sandbox dan final kejuaraan adalah bahwa di sandbox, permainan dibuat dalam format acak, dan bukan hanya dalam format putaran saat ini.

Cerita partisipasi

Bagian teknis akan lebih rendah. Kepada siapa sejarah tidak menarik, Anda dapat menggulir ke bawah sampai menjadi baik.

Babak pertama

Dia mulai, seperti kebanyakan, dengan satu minggu beta. Menghabiskan banyak waktu, 4+ jam setiap malam.
Sebelum Anda mengisi versi pertama, butuh beberapa iterasi
kami kode sampai kami mulai mengalahkan versi sebelumnya - kami kumpulkan - kami mempertimbangkan versi saat ini dari versi sebelumnya - kami ulangi .

Saya tidak terburu-buru dengan isian pertama dan itu terjadi beberapa hari sebelum putaran. Dan, sejak, sampai sekarang, bot saya belum bermain dengan siapa pun, saya tidak tahu seperti apa dunia saya dan posisi apa di peringkat yang bisa saya klaim. Ketika saya melihat bahwa saya telah memenangkan lebih dari 100 pertandingan berturut-turut tanpa kehilangan satu pun, saya menjadi tenang.

Secara umum, kekalahan pertama, saya pikir, ada di tempat ke-12, berdasarkan batas waktu, dan pertandingan pertama yang hilang berturut-turut sudah ada di 10 besar.

Singkatnya, saya menyadari bahwa saya memiliki peluang untuk masuk ke babak kedua, di mana 300 teratas masuk.
Karena itu, saya tidak mengejar posisi di dalamnya dan tidak membanjiri yang lain untuk putaran, tetapi hanya terus bekerja.

Pada saat itu, saya melihat bahwa masih ada banyak ruang untuk perbaikan tanpa menghubungkan nitro (yang muncul setelah ronde 1), jadi saya fokus pada bagian utama dari strategi, menyadari bahwa sebelum ronde kedua akan ada lebih dari 2 minggu atau lebih dan saya akan punya waktu untuk mengikat nitro.

Babak kedua

Minggu pertama saya aktif pemrograman, tetapi masih tidak terhubung nitro. Saya ingin melakukan ini di minggu kedua. Tetapi semuanya ternyata berbeda, karena pada akhir minggu pertama saya terjangkit pneumonia. Saya tidak dapat memprogram, jadi saya hanya mengunggah apa itu, dan, dapat dikatakan, partisipasi aktif dalam kejuaraan bagi saya di tempat ini sudah berakhir.

Selama 3 minggu ke depan sebelum akhir kejuaraan, saya mengerjakan strategi dalam jumlah mungkin 20 jam.

Akibatnya, di babak kedua, bot saya, pada prinsipnya, tidak tahu bahwa ada nitro dalam permainan, tetapi entah bagaimana masih menempati posisi ke-16.

Terakhir

Di final, pemain ketiga ditambahkan.

Saya menulis di Jawa lambat, dan bukan di C ++, karena 7 dari 8 orang lebih tinggi dari saya di peringkat, dan sebelum itu bot saya sering jatuh ke dalam batas waktu, jadi dengan munculnya pemain ketiga, mulai turun dalam 100% permainan. Untungnya, game di kotak pasir dibuat dalam format acak, jadi saya otomatis
kalah hanya setiap pertandingan ketiga dan karena itu terbang tidak terlalu banyak. Tampaknya telah jatuh ke posisi ke-18.

Kecuali untuk pemrograman, mengedit koefisien dalam fungsi evaluasi dan menjalankan tes, kemudian untuk pertama kalinya, setelah awal penyakit, saya duduk di bot malam hari sebelum final. Dia menambahkan nitro yang sangat sederhana yang diarahkan ketat ke atas sehingga dua penyerang akan berhenti berlari pada titik yang sama dan bertabrakan satu sama lain di sana, dan mengurangi semua yang dia bisa untuk permainan 3x3, mulai dari kedalaman render dan berakhir dengan akurasi simulasi, sehingga hanya bot yang tidak mati karena batas waktu.
Dalam bentuk ini, ia memainkan final.

Dalam selang waktu antara separuh babak final, saya kembali duduk di bot dan menghabiskan beberapa jam yang baik 10. Untuk sebagian besar, perubahan menyangkut pemilihan koefisien yang dinamis, gangguan genetika awal, dll. Secara umum, saya mencari keseimbangan antara akurasi dan kedalaman dan kecepatan kesalahan perhitungan.
Selain bertarung melawan kecepatan, ia membuat beberapa perubahan lagi:

Mengirim penyerang jauh (relatif terhadap bola) ke titik di tengah-tengah antara bola dan gawang lawan
Saya memperbaiki nitro sedikit (uraiannya ada di bagian teknis). Itu masih sangat sederhana, tetapi menjadi jauh lebih efisien.

Total, setelah menjalankan tes dan melihat skor 395: 254 melawan versi sebelumnya, saya menenangkan ini. Ini memungkinkan saya untuk mengambil tempat ke-9 di final.

Sandbox Finale

Saya terus terluka dan tidak bekerja pada bot untuk hampir sepanjang minggu. Sehari sebelum akhir, saya melihat bahwa beberapa orang mengunggah versi baru, yang sering menang melawan saya dan dapat membuang kotak pasir dari hadiah. Jadi saya menghabiskan beberapa jam lagi.

Satu-satunya perubahan besar adalah saya menggali cabang saya di Git tiga minggu lalu, di mana saya melakukan simulasi gerakan musuh menggunakan algoritma saya yang disederhanakan. Pada saat itu itu bekerja dengan buruk, tetapi saya membawanya ke pikiran, menjalankan tes, melihat
yang mengungguli versi sebelumnya hampir dua kali lipat dan banjir. Total, pada saat berhenti, saya berada di posisi ke-10 di tabel keseluruhan, yang sesuai dengan ke-4 di final kotak pasir.

Bagaimana cara kerjanya (bagian teknis)

Saya mohon maaf sebelumnya jika ada ketidakakuratan dalam terminologi. Juga, saya menulis dari memori, jadi mungkin saja di suatu tempat saya tidak akan menjelaskan versi finalnya.

Jadi, algoritma genetika adalah intinya. Kromosom terdiri dari beberapa gen:

Nomor pecahan dalam rentang -PI..PI, menentukan arah gerakan
Integer di kisaran 0..10 yang menentukan jumlah pengulangan tindakan ini
Angka pecahan dari 0 hingga 1. Jika nilainya di atas ambang tertentu, lakukan lompatan

Genotipe dapat mencakup jumlah kromosom yang berbeda, tetapi sedemikian rupa sehingga jumlah tindakan (termasuk pengulangan) adalah 40.

Awalnya, saya membuat beberapa lusin genotipe acak. Untuk mereka saya tambahkan:

Lintasan tepat di atas bola
Lintasan langsung ke segala arah, hanya 10 buah dengan offset 36 derajat
Genotipe yang tidak melakukan apa-apa (tanpanya, bot selalu berjalan di suatu tempat, bahkan jika sudah berada pada titik optimal)
Genotipe terbaik dari centang sebelumnya

Kemudian semuanya disimulasikan dan dijalankan melalui fungsi evaluasi. N genotipe terbaik "bertahan" dan dikloning M kali dengan mutasi. Setelah mutasi, setiap gen berubah dalam kisaran yang diberikan dengan probabilitas 10%. Nah, ini sudah berulang selama beberapa generasi.
Tidak ada persimpangan, dalam masalah ini saya tidak melihat adanya arti di dalamnya.

Secara total, jumlah lintasan maksimum yang dimungkinkan per kutu per pemain sepak bola adalah sekitar 800, tetapi pada kenyataannya, dalam banyak kasus itu jauh lebih sedikit, karena dalam beberapa kasus (misalnya, ketika dalam waktu dekat kami pasti tidak akan bisa menyentuh bola), pergerakan pemain digantikan oleh heuristik sederhana. Selain itu, N, M dan jumlah generasi tergantung pada situasi di lapangan. Pertama-tama, dari jarak ke bola. Juga, perhitungan yang salah terganggu sebelum jadwal (tetapi tidak lebih awal dari generasi ke-5) jika lintasan dengan estimasi yang dapat diterima ditemukan.

Makro

Kiper berlari ke titik di depan pusat gawang. Tes saya menunjukkan bahwa yang terbaik bagi saya adalah bermain sambil berdiri di depan gawang, dan tidak di dalam gawang, seperti kebanyakan pemain di atas.

Posisi titik menyimpang dari pusat tergantung pada beberapa faktor: posisi dan arah penerbangan bola, titik bola mengenai tujuan saya, jika tujuan direncanakan, lokasi lawan menyerang terdekat, dll.

Jika bola ada di sisi lawan dan terbang menuju tujuannya, kita bisa pergi untuk nitro.

Jika kiper saya dapat mengenai bola lebih awal dari penyerang saya (ditambah beberapa kondisi lainnya), maka penyerang mengabaikan bola dan berlari ke titik di tengah antara bola dan gawang lawan. Saya pergi melalui banyak pilihan, di mana tepatnya dia menjalankan. Dalam kasus saya, yang ini bekerja paling baik.

Kalau tidak, jika bola terlalu jauh, penyerang berlari dalam garis lurus ke titik kontak terdekat bola dengan lantai, di mana ia dapat mencegat bola (jika kita tidak punya waktu untuk titik kontak pertama - periksa yang berikutnya, dll)

Jika tidak (ketika bola mencapai), penyerang berlari ke tempat fungsi evaluasi memberitahunya. Ya, dan juga, jika nitro terletak di dekatnya dan kami dapat mengambilnya, kami memilihnya.

Dalam pertandingan 3x3, penyerang kedua lebih cenderung membidik bola dan dengan sedikit berlari ke depan, mengharapkan umpan dari kiper. Tetapi jika masih berjalan, maka titik lain dipilih - lebih dekat ke garis tengah.

Juga, setiap tick sekali mensimulasikan bola 100 ticks forward dengan 100 microtics (with caching).

Lintasan ini telah digunakan di banyak tempat. Sebagai contoh:

Untuk menentukan titik sentuh bola dengan lantai
Untuk mengetahui apakah bola mengancam gawang saya dan apakah kiper perlu beralih ke mode simulasi

Lintasan yang persis sama digunakan dalam simulasi lintasan para pemain, agar tidak menghitung bola setiap saat. Namun hanya sampai tabrakan pertama bola dengan pemain sepakbola apa pun.

Ngomong-ngomong, menulis Footballist itu malas, kata-kata Player, Robot dicadangkan oleh strategi,
jadi kelas pembungkus saya hanya dipanggil Bung :)

Simulasi

Dalam kebanyakan kasus, ia berjalan dengan satu mikrotik, tetapi dalam beberapa situasi beralih ke mode akurat dengan sejumlah besar mikrotik (pada awalnya 100, kemudian dikurangi menjadi 50 dalam permainan 2x2, karena tes menunjukkan bahwa perbedaan hasil berada dalam margin kesalahan, dan ke 10). dalam 3x3, karena kalau tidak terbang ke timeout).

Dalam mode akurat, saya beralih pada saat memantul, atau menjadi sangat dekat dengan bola sehingga tabrakan pada tik berikutnya mungkin terjadi. Selain itu, ada juga banyak kruk kecil, retasan, optimisasi, di mana saya sendiri tidak akan mengerti.

Sebagai contoh, bola terbang masih disimulasikan dengan 1 Mikrotik, tetapi jika setelah Mikrotik berikutnya saya melihat bahwa ada tabrakan, ia berguling kembali ke posisi sebelumnya dan disimulasikan lagi dengan akurasi yang lebih besar.

Selain itu, saya juga berpura-pura menjadi pemain lain (baik saya sendiri dan orang lain) jika mereka ada di udara (dan karena itu lintasan mereka lebih mudah diprediksi), atau dekat dengan bola. Untuk lawan, versi final menggunakan versi sederhana dari strategi pengambilan keputusan saya sendiri, yang diluncurkan setiap 5 ticks (lebih sering tidak memungkinkan kecepatan).

Saat mensimulasikan setiap karakter, saya menghitung diri saya sendiri, bola dan pemain sepak bola lainnya 40 kutu di depan (batas saya pada jumlah aksi dalam genotipe) dan kemudian mensimulasikan jumlah kutu yang sama hanya satu bola.

Nitro

Sederhana hingga tidak senonoh.

Dalam versi final, nitro selalu dihidupkan jika ya, jika pemain ada di udara, dan jika dia belum mengenai bola dalam beberapa kutu terakhir.

Pada awalnya, saya selalu mengarahkan nitro lurus ke atas, tetapi kemudian saya mencoba bereksperimen dan opsi untuk pergi tepat ke tengah bola bekerja paling baik. Saya juga mencoba opsi sehingga arah nitro dipilih oleh genetika.

Itu bekerja jauh lebih buruk. Mungkin karena kurangnya kedalaman pencarian.

Fungsi peringkat

Jumlah skor untuk setiap tick dengan atenuasi 2% per tick.

Bobot terbesar, tentu saja, punya tujuan. Beberapa hal memengaruhi berat badannya:

Jarak dari bola ke gawang musuh pada saat gol (semakin jauh semakin baik)
Y mengoordinasikan bola (karena di bagian atas gawang lebih sulit untuk mengenai)
Kecepatan bola di sepanjang sumbu Z (yang diarahkan ke gawang musuh)

Ketika menyerang saya, semuanya persis sama, hanya dengan tanda yang berlawanan.

Selanjutnya, untuk penyerang, skor keseluruhan bergantung pada:

Jarak dari pemain ke bola (sehingga dia berlari ke bola bahkan jika dia tidak bisa memukulnya)
Penalti untuk lompat (melompat hanya jika itu membawa begitu banyak poin sehingga mereka akan melebihi penalti ini)
Jarak pada tick berikutnya dari simulasi dari bola ke lawan
Koordinat bola Y (semakin tinggi itu, semakin sedikit peluang musuh untuk mencegatnya)
Kosongkan sudut antara arah bola dan pusat gawang musuh
Tandai jika saya menyentuh bola
Bendera, apakah musuh menyentuh bola
Bonus untuk pemilihan nitro

Juga, ada bonus kecil untuk memukul pemain musuh. Meski sebenarnya sudah terjadi, tetapi jarang.

Untuk penjaga gawang:

Bonus untuk jarak ke bola, kecepatan bola di Z, posisi bola di Y
Hukuman untuk lompat
Hukuman untuk menemukan bola di daerah di depan gawang saya
Jarak ke musuh dan penyerang saya diperhitungkan (sehingga bola akan terbang menjauh dari musuh, tetapi, jika mungkin, terbang lebih dekat ke penyerang saya)
Dan beberapa hal kecil lagi.

Pembelajaran mesin

Itu hanya sedikit di salah satu cabang git sebagai percobaan. Tapi bagi saya sepertinya layak disebut. Saya tidak berhasil membawanya ke pikiran saya (dan saya tidak yakin apa yang masuk akal).

Secara umum, saya mencoba memprediksi dengan bantuannya apakah musuh dapat mencegat bola berdasarkan posisi dan kecepatan musuh dan bola. Saya berencana untuk menggunakan ini dalam fungsi evaluasi. Menghukum lintasan yang mungkin untuk mencegat.

Tetapi saya segera mengerti bahwa saya tidak hanya mampu memiliki jaringan saraf, tetapi tidak ada yang serius sama sekali, karena ini harus dilakukan 80 kali per lintasan. Ya, meskipun 40 atau 20, jika tidak setiap kutu dihitung, tapi bagaimanapun, saya tidak punya cadangan waktu sama sekali, jadi saya bahkan tidak mempertimbangkan opsi ini.

Inilah yang saya lakukan:

Saya menjalankan beberapa permainan dengan bot yang dimodifikasi, di mana, ketika mencari lintasan, saya menyimpan data tentang diri saya dan bola, serta bendera, apakah lintasan ditemukan di mana saya mencegat bola.

Saya menganggap semua koordinat relatif terhadap pemain sepak bola. Yaitu Saya selalu memilikinya di koordinat [0,0,0], jadi saya hanya menyimpan 10 bidang: posisi relatif bola, vektor kecepatan bola, vektor kecepatan pemain sepak bola, bendera intersepsi biner. Saya menyimpan dataset hanya untuk bagian tengah bidang, karena Saya menyadari bahwa algoritma sederhana belum akan menarik dan memperhitungkan papan.

Kemudian saya memberi makan dataset DecisionTreeClassifier ini dengan max_depth = 7. Pohon yang terlatih memberikan akurasi, sejauh yang saya ingat, dari urutan 90%.

Selanjutnya, saya mengekspor pohon ke satu set ifs (yang pada dasarnya DecisionTree).

Itu terlihat seperti ini:

public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) { if (ball_vel_z <= 6.4765448570251465) { if (dude_vel_y <= -6.087389945983887) { if (ball_vel_z <= -20.188323974609375) { if (dude_vel_x <= 13.032730102539062) { if (ball_rel_pos_y <= -1.1829500198364258) { return ball_vel_y <= 18.906089782714844; } else { return false; } } else { return true; } } else { // ............................

Pada tahap ini, saya menjalankan tes, tidak melihat peningkatan, dan menunda persidangan sampai nanti, yang, karena petualangan saya, tidak pernah tiba.

Schroedinbag

Di suatu tempat setelah putaran pertama, saya menangkap hewan langka ini di rumah saya.

Siapa yang tidak tahu, ini adalah bug yang mereka temukan hanya dengan membaca kode, dan setelah menemukannya, pengembang bertanya-tanya bagaimana program bisa bekerja sama sekali. Dan dalam kasus saya, dia juga berada di 10 besar.

Secara umum, bugnya adalah konstruktor dipanggil dalam fungsi salin gen, di mana argumen opsional dihilangkan yang mengandung nilai gen ini. Dengan tidak adanya argumen ini, nilai dipilih secara acak. Jadi, ketika mencoba menyalin gen, bukannya salinan, ia menciptakan contoh acak baru.

Sebenarnya, alih-alih genetika, saya melakukan pencarian acak, karena setiap centang hanya menghasilkan beberapa ratus jalur acak dan memilih yang terbaik.

Setelah koreksi (terdiri dari menambahkan 2 karakter ke kode), permainan menjadi sekitar 3 kali lebih baik.

Menari ritual

Pada titik waktu tertentu, saya perhatikan bahwa pemain terkadang bangkit tanpa alasan, karena jauh dari bola, terlepas dari penalti.

Penjelasannya berubah sehingga saya menghitung momen lompatan dengan akurasi 100 mikrotik. Dan kadang-kadang ternyata hanya pada saat lompatan ada tabrakan bola dengan barbel. Dan tergantung pada keakuratan perhitungan tepat dalam centang ini, lintasan yang diusulkan dapat mengarah ke tujuan atau tidak.

Secara kasar, bola terbang ke gawang lawan dan membentur tiang gawang. pemain sepak bola saya, berlari di ujung lain lapangan, mensimulasikan lintasan tanpa melompat (dengan 1 mikrotik) dan melihat bahwa bola tidak mengenai sasaran.

Kemudian lintasan lain datang, dengan lompatan tepat pada saat bola menyentuh mistar. Dan karena saya menghitung tanda centang dengan lompatan 100 Mikrotik tidak hanya untuk pemain sepak bola, tetapi juga untuk bola, sudut pantulan bola yang dihitung berbeda dari sudut yang diperoleh di jalur dengan 1 mikrotik, dan mungkin terjadi bahwa bola dalam lintasan yang lebih akurat ini jatuh ke dalam gerbang.

Dan karena itu, lintasan inilah yang akan dipilih dan bot akan melompat.

Secara umum, dengan melakukan tarian ritual dengan memantul, para pemain menidurkan gol :)

Fitur pembunuh

Bukan dia

Pengujian

Saya mengendarai game tanpa akhir dalam 8 utas (4 di setiap komputer dan laptop). Saya memilih jumlah game sehingga signifikan secara statistik.

Dengan peningkatan yang signifikan dalam strategi dapat dipenuhi dengan setengah ribu gol secara total,
dengan koreksi yang lebih kecil, dibiarkan malam dan kemudian tagihan masuk ke ribuan.

Pemilihan konstanta genetik

Saya mencobanya sebelum babak pertama. Itu tidak memberikan apa pun dengan alasan bahwa untuk genetika Anda perlu memainkan turnamen dari sejumlah besar permainan.

Saya mencoba memainkan permainan 100.000 kutu, tetapi itu tidak cukup. Dengan perbedaan kecil dalam kekuatan (dan biasanya ketika memilih konstanta inilah yang terjadi), pemenang per 100 k kutu tergantung terlalu banyak pada kasing. Anda harus bermain lebih banyak untuk memastikan pemenangnya. Dan saya tidak mampu meninggalkan seleksi selama sehari atau lebih, jadi saya menolak usaha ini.

Kesimpulannya

Terima kasih tradisional kepada panitia. Tugas itu menarik. Sangat disayangkan bahwa saya terpaksa kehilangan hampir setengah dari kejuaraan dan benar-benar tidak melakukan apa pun untuk nitro atau tiga pemain.

Akibatnya, sampai paling akhir saya menyaksikan di kotak pasir bagaimana strategi saya menang dalam mode 2x2 tanpa nitro dengan skor 13: 2 melawan Mr.Smile mana pun, yang mengambil tempat ke-3 di final, dan setelah beberapa pertandingan kalah baginya 12: 2 dalam mode 3x3 dengan nitro :)

Dan tentu saja, video dari visualizer milik saya:

Hanya Anda yang mungkin harus mengucapkan selamat tinggal pada visualizer ini di kejuaraan mendatang.
Untuk setiap kali saya semakin yakin bahwa jika Anda melamar tempat normal, satu-satunya pilihan adalah menulis di ...

... yah, Anda mengerti maksudnya.

Capek setiap waktu untuk beristirahat di kelambatan Jawa dan mengurangi kekuatan strategi untuk memenuhi waktu yang ditentukan.

Saya harap seseorang menemukan sendiri sesuatu yang menarik atau berguna dalam karya saya ini dengan catatan karakter otobiografi :)

Piala AI Rusia 2018, sejarah 9 tempat