Awalnya, saya tidak punya rencana untuk artikel, terutama tentang berbicara di sebuah konferensi. Tetapi ada sebuah konferensi. Dan setelah berbicara tentang hal itu, pemirsa memiliki pertanyaan untuk saya mengenai implementasi beberapa masalah teknis. Dan ternyata kata demi kata - sebuah artikel.
Rekaman langsung di bawah tautan .
Penafian: Artikel ini adalah upaya untuk menjawab beberapa pertanyaan ini. Saya akan senang jika pertanyaan baru muncul, menjawab mana akan ada kesempatan untuk belajar sesuatu yang baru sendiri. Dan ya, artikel ini sama sekali bukan upaya untuk merasakan denting pipa tembaga.
Jadi mari kita mulai dari awal cerita ini. Musim semi 2018, mail.ru mengumumkan kontes pemrograman yang didasarkan pada game Agairo . Inti dari kompetisi adalah penciptaan bot permainan.
Aturan persaingan di tautan ini. Tapi untuk menjadi singkat dan menguraikan aturan dengan kata-kata Anda sendiri, Anda perlu membuat bot untuk dimainkan di Agairo. Pada suatu waktu, gim Internet populer (dalam arti diluncurkan dari peramban), intinya adalah memakan adik-adik Anda dan melarikan diri dari yang lebih besar. Anda mengontrol roda warna dalam ruang dua dimensi yang terbatas. Untuk membuat gameplay di ruang ini, selain lingkaran Anda, ada lingkaran lain yang dikontrol oleh pemain lain. Ada makanan (titik berwarna) untuk pertumbuhan, hambatan tambahan diperkenalkan dalam bentuk "virus", tabrakan yang menciptakan pembagian lingkaran Anda menjadi yang lebih kecil, yang menyulitkan sebagian proses permainan, karena yang kecil memakan yang lebih besar dan yang lebih besar lebih aman.
Saya akan memberikan gambar dari varian permainan untuk kompetisi
Lebih jauh, menurut pemain kami bukan pengembang bot, tetapi bot itu sendiri.
Penyelenggara kompetisi secara keseluruhan mempertahankan konsep asli permainan, tetapi menambahkan sejumlah inovasi. Yang utama adalah pembatasan ulasan bot dan pengenalan hukum fisik sederhana yang disebut inersia. Fisika telah melalui fisika untuk waktu yang lama, jadi inersia dikaitkan tidak hanya dengan kita, tetapi juga dengan jumlah seperti massa, kecepatan dan percepatan. Kami tidak membutuhkan hal lain dari dunia fisika.
Saya berharap bagian sastra telah memberikan perhatian yang cukup dan sekarang saatnya untuk beralih ke komponen teknis dari kompetisi dan berpartisipasi di dalamnya.
Penafian 2: Saya cukup yakin bahwa apa yang diuraikan di bawah ini dapat dibuat lebih tipis, lebih elegan dan lebih pintar, tetapi bagaimana hal itu terjadi terjadi.
Jadi, tuliskan resep dan bahan utamanya, tidak semuanya baru, tetapi Anda bisa menambahkan sendiri sesuai selera Anda.
Tugas: Buat bot yang bisa memainkan Agairo sendiri.
Gagasan utama: Gunakan jaringan saraf (selanjutnya disebut jaringan saraf, jaringan saraf (NN)) sebagai elemen kontrol bot.
Alat produksi utama: Microsoft Visual Studio dan c # dengan transisi yang lancar ke c ++.
Maka hal yang paling penting bagi penulis adalah memilih atau memahami pembacanya, untuk siapa saya menulis, apakah dia tahu apa jaringan saraf, algoritma genetika dan bagaimana menggambarkan semua ini secara rinci.
Itu saja, saya memilih pembaca saya, pembaca saya tahu semua ini, tetapi tidak begitu baik untuk menggunakannya dalam praktek.
Karena itu, ketika saya menulis artikel ini, saya akan mengingat bentuk-bentuk sederhana seperti neuron dan fungsi aktivasi.
Untuk visualisasi saya akan menggunakan gambar yang digambar tangan, yang harus dibaca sebagai: jika Anda melihat ada kesalahan di sana, tulis, gambar ulang ke yang benar.
Jadi, semuanya siap dikirim ke jalur pembangunan perangkat lunak bot. Mari kita mulai:
Kami mengambil siklus, atau lebih tepatnya, penyelenggara kompetisi menyiapkannya untuk kami sebagai contoh bot sederhana. Ayo masuk lebih dalam, unduh arsip untuk peserta kontes dari repositori menggunakan tautan ini. Panitia berjanji bahwa server kontes akan hidup, dan setelah selesai, kami akan dapat memverifikasi kata-kata ini. Kami membuka arsip dan memilih bahasa pemrograman yang dapat dimengerti oleh kami.
Dokumentasi kompetisi juga menggambarkan teknologi komunikasi klien (baca bot kami) dan server pusat data yang hidup di suatu tempat di kedalaman. Singkatnya, komunikasi melewati garis konsol, dengan menulis dan membaca perintah darinya.
Kata ajaib Serialisasi harus disebutkan di sini: itu mengemas data Anda dalam format yang dipahami oleh serializer dan kemampuan untuk membaca data ini kembali ke dalam program menggunakan serializer. Ada banyak serializers, format sekuensial paling sederhana untuk menulis ke file txt juga merupakan serializer, tetapi sederhana. Yang perlu kita ketahui tentang serialis adalah bahwa mereka ada dan hampir transparan dalam hal API. Penyelenggara kemungkinan besar memahami ini dan karena itu contoh bot mereka berisi semua instruksi yang diperlukan untuk bekerja dengan serializer. Dalam kasus kami, itu adalah JSON .
Untuk bot setelah serializer, dunia game terlihat seperti array data yang diterima di awal siklus yang disebutkan. Data tentang dunia game dibatasi oleh server sesuai dengan jari-jari tampilan yang sama dengan 4 jari-jari bot, ingat bahwa bot adalah lingkaran. Dan lingkaran di sekitar lingkaran ini adalah perbatasan eksternal dari tinjauan, meskipun lingkaran luar sedikit bias terhadap pergerakan bot relatif terhadap pusat bot, tetapi ini dapat diabaikan dalam kasus kami.
Jadi kita memiliki Siklus, ukuran Siklus adalah Centang, berapa banyak siklus telah berlalu, begitu banyak kutu telah berjalan. Kemungkinan besar kita tidak akan mengingat Tick ini lagi, tetapi itu akan memperkenalkan sejumlah batasan dan penyederhanaan penting: waktu perhitungan tidak hanya dibatasi oleh Tick tunggal, waktu satu iterasi siklus, tetapi juga oleh total waktu perhitungan, setelah melebihi server permainan yang akan memutuskan bot Anda dari manajemen. Centang dan waktu untuk memberi perintah pada bot. Kami akan menganggapnya sebagai kuantum Waktu permainan, Centang adalah jumlah waktu yang tidak dapat dibagi dalam dunia permainan. Plus mengikuti dari ini. Karena centangnya sama dengan 1 secara default, lebih mudah untuk menghitung kecepatan, akselerasi dan nilai-nilai lainnya. Dalam semua rumus, kita mengalikan dengan 1, alih-alih menggunakan semacam waktu kurva t = 0,0015 detik di dalamnya. Kesalahan dalam operasi ini juga minimal.
Semua hal di atas agak mirip dengan film, sepertinya gambar di layar hidup dan bergerak, tetapi kenyataannya kita ditunjukkan 25 frame berbeda per detik, dan otak kita hanya menganggap ini frekuensi yang cukup untuk persepsi penuh tentang dinamika video. Jadi bot melihat dunia pada interval waktu tertentu. Centang adalah bingkai dari dunia game.
Jaringan saraf juga akan bekerja sesuai dengan kutu.
Gambar mulai jelas dari sisi bot:
Server mengirimkan data yang diproses tentang dunia ke bot-> Centang Mulai-> bot menerima data -> memprosesnya-> mengirimkan perintah manajemen bot ke server-> Server membaca data-> End of the Tick dan kemudian hampir tanpa akhir dalam lingkaran atau loop, 45.000 ticks di final permainan ini merupakan angka yang cukup besar.
Catatan penting: Anda dapat melewati Tick dan Anda tidak akan mendapatkan apa pun untuk itu. Ada kasus-kasus server di mana setiap Tick perlu memberi tahu sesuatu kepada server, sehingga server tidak mencurigai bot dalam kendali program kontrol.
Penulis memutuskan untuk tidak terlalu menyentuh server, tetapi saya perlu mengatakan beberapa kata tentang itu. Ada model dunia game di server, dan sesuai dengan itu, ia melakukan perhitungan dan tindakan. Program server mencakup blok berikut:
- perhitungan tabrakan bot (memproses tabrakan dengan batas-batas dunia game, yang memakan siapa, bot bot atau makanan bot, atau tabrakan dengan virus, dll.)
- perhitungan fisika bot (pergerakan bot, perubahan kecepatan bot sesuai dengan perintah bot atau tabrakan yang terjadi)
- perhitungan yang terkait dengan membagi bot atau menggabungkannya, jika mungkin, menambah makanan dan fungsi lainnya untuk mempertahankan dunia game.
- dan tentu saja mengirim dan menerima data ke bot pada kutu game.
Server seperti ini disebut "perintah". Artinya, semua tindakan terjadi di sisi server, yang menghilangkan masalah dengan sinkronisasi data. Klien (baca bot) hanya menerima gambar dunia yang sudah jadi, seperti saingannya yang lain, di sini kesetaraan posisi bot tercapai, tidak ada prioritas dan antrian. Sekali lagi, perubahan dalam koordinat bot terjadi di server, misalnya, bot memberikan perintah untuk bergeser dan hanya pada Tick berikutnya yang mengenali koordinat barunya, yang tidak selalu bertepatan dengan tim, sebagai opsi penghalang dalam bentuk dinding dunia game.
gambar dari situs penyelenggara
Kami menemukan pembacaan data dengan bot dan server manajemen, sekarang mari kita lihat kedalaman perangkat bot.
Sebagai pembaca mungkin sudah mengerti akan ada beberapa kata dan banyak pekerjaan, atau sebaliknya.
Bot dikendalikan oleh jaringan saraf. Singkat dan luas, tetapi tidak sepenuhnya jelas caranya.
Pilihan jaringan saraf dan teknik untuk implementasinya.
Saat ini, kami memutuskan bahwa jaringan saraf untuk kami adalah kotak hitam yang memiliki input dan output.
Input dan output untuk kita akan menjadi array satu dimensi dengan dimensi N = 16 untuk input dan dimensi M = 4 untuk output.
Karena sifat dari jaringan saraf tiruan secara kasar disalin dari jaringan saraf alami, akan baik bagi kita untuk membawa struktur data input lebih dekat ke yang alami. Di alam, berbagai sensor bertanggung jawab untuk ini. Jadi tetap pada sensor bot.
Opsi berikut dipilih secara eksperimental (gambar disederhanakan menjadi 8 sensor, dan jaringan saraf 4x3, tetapi ini hanya untuk membingungkan pembaca saya):
Bidang tampilan bot dibagi menjadi sektor yang sama (bahkan mungkin tidak sama). Setiap sektor memberikan sinyal ke salah satu input dari jaringan saraf. Dengan demikian, jika kami membagi area di sekitar bot menjadi 16 sektor (360/12 = 22,5 derajat tinjauan sektor), kami mendapatkan 16 input dari jaringan saraf. Biasanya, sinyal mulai dari -1 hingga 1 diterapkan pada input jaringan saraf, oleh karena itu, perlu untuk menormalkan sinyal input.
Penjatahan adalah, disederhanakan, membagi total sinyal dengan nilai maksimum yang dimungkinkan. Tentu saja dimungkinkan untuk membuat normalisasi dinamis, yaitu untuk mencari maksimum setiap kali dan membawa nilai sinyal ke normanya, tetapi kami akan menetapkan nilai maksimum dalam bentuk konstan sama dengan jumlah maksimum objek dalam satu sektor dan tidak akan mengubahnya dalam proses pengerjaan bot.
Sinyal dapat berupa positif atau negatif, kami setuju bahwa nilai sinyal dari 0 hingga 1 adalah motif positif untuk bot kami (makanan, makanan dalam bentuk bot yang lebih kecil), nilai sinyal negatif dari -1 hingga 0 adalah motif negatif untuk bot (dinding dunia game, bot lain yang lebih besar).
menggambar
Sinyal dari suatu sektor adalah kuantitas yang dinormalisasi yang terdiri dari jumlah sinyal individu. Setiap sinyal individu, seperti yang telah dikatakan, memiliki tanda dan besarnya. Besarnya sinyal didefinisikan sebagai fungsi jarak yang proporsional. Jarak minimum adalah batas lingkaran bot yang menentukan, jarak maksimum adalah batas visibilitas bot. Karenanya, jika kita menerima sinyal positif dari, misalnya, makanan hanya memasuki sektor pada jarak maksimum, maka sinyal akan lemah dan akan meningkat jika bot mendekati makanan.
Sensor dalam bentuk sektor yang paling cocok untuk kasus ini, tetapi mungkin ada probe-antena, di sini fantasi ada di pihak Anda. Tentu saja, penulis mencoba berbagai opsi untuk membagi menjadi beberapa sektor dari 4 sektor menjadi 72, tetapi praktik telah menunjukkan bahwa jaringan saraf cukup berhasil dilatih dalam 16 sektor dan siap untuk mengendalikan bot bahkan dengan empat sektor. Di sini fleksibilitas sifat alami dari jaringan syaraf dimanifestasikan.
Akhirnya, kata pelatihan jaringan saraf diucapkan. Tetapi untuk saat ini, kami memutuskan bahwa jaringan saraf adalah kotak hitam dengan input dan output, dan karena kami mengurutkan data input, masih perlu dikatakan beberapa kata tentang data output atau sinyal dari kotak ini, apa yang harus dilakukan dengan itu dan bagaimana memprosesnya.
Kami mengatur dimensi sinyal keluaran menjadi 4. Angka ini adalah manifestasi dari dualisme koordinat dan kutub Cartesian. Penulis tidak melupakan sifat pengetahuan pembacanya dan karenanya mengingatkannya dengan gambar pengetahuan yang dulu didapatnya dengan baik.
Jadi, para pengembang server secara logis menggunakan koordinat kutub untuk mensimulasikan dunia game, dan untuk bot dan pengembang mereka dengan sopan memberikan koordinat Cartesian. Oleh karena itu, penulis harus memilih sisi dalam sistem koordinat ini. Untuk jaringan saraf, sistem koordinat kutub yang hanya berisi besarnya (panjang baca) vektor dan sudut deviasinya lebih mudah dipahami. Lagi pula, Anda juga memahami kata-kata “belok kanan” daripada memindahkan dua langkah di sepanjang ordinasi dan tiga langkah di sepanjang absis.
Oleh karena itu, 4 sinyal keluaran, ini adalah 2 sinyal tentang menambah atau mengurangi sudut vektor kecepatan bot, dan 2 lainnya meningkatkan atau mengurangi besarnya vektor kecepatan.
Tetapi karena server permainan diminta untuk memberikan perintah untuk mengelola bot dalam koordinat Cartesian, sepasang rumus untuk menerjemahkan dari koordinat polar ke koordinat Cartesian dan semua aib ini didapat di tempatnya (ini adalah kode semu yang mirip dengan c #).
float rotate1 = outputs[0]; float rotate2 = outputs[1]; float speed1 = outputs[2]; float speed2 = outputs[3]; if (rotate1 > 0.65 && rotate2 < 0.65) angle = angle + 35 * PI / 180; if (rotate1 < 0.65f && rotate2 > 0.65) angle = angle - 35 * PI / 180; if (speed1 > 0.65 && speed2 < 0.65) speed = speed + 2; if (speed1 < 0.65 && speed2 > 0.65) speed = speed - 2; dx = speed * Cos(angle); dy = speed * Sin(angle);
Sinyal ada di tempat, seperti bot. Tampaknya mereka memberinya sinyal input, tetapi pada output, ada sesuatu yang tidak ada nilainya: ia berdiri atau bergerak secara acak.
Maka datanglah untuk membuka kotak hitam dan melihat ke dalam.
Untuk dilanjutkan.
Tetapi sebelum seri teaser baru:
Bot ungu di jaringan saraf bermain di Local Runner melawan bot standar yang secara default dijahit oleh penyelenggara.