Bagian terakhir.
Dalam bab-bab sebelumnya ( bagian 1 , bagian 2 , bagian tentang GPU ), kami menyentuh kondisi kontes, jaringan saraf, algoritma genetika, jadi mari kita lanjutkan.
Tetapi sebelum melanjutkan, ada tautan ke GitHub dengan kode sumber untuk program di c ++ dan untuk mendukung judul artikel - file yang dapat dieksekusi di bawah Windows di folder bin , yang sangat mirip dengan screeen saver. Di ruang bawah tanah artikel itu ia mengatur "hall of fame" kejuaraan masa lalu.
Jadi, kami menentukan arsitektur program, yang terdiri dari dua bagian terpisah (program), bagian yang hanya berisi jaringan saraf dan protokol komunikasi dengan server permainan dari penyelenggara kontes (permainan bot itu sendiri) dan bagian utama, yang terdiri dari blok-blok berikut:
Secara singkat tentang masing-masing bagian.
Mesin fisika. Berdasarkan modul perhitungan fisika dari sumber resmi, dikerjakan ulang untuk GPU dan menambahkan perhitungan sensor bot, fungsi kebugaran, tabrakan bot. Kode sumber menghapus virus dan bot mencoba untuk berbagi, membagi bagian yang tidak stabil dari program. Karena itu, saya tidak membagikan kesalahan saya.
Jaringan saraf. Kami membicarakannya dengan cukup detail terakhir kali, termasuk tentang implementasi dalam kode, jadi saya akan berasumsi bahwa banyak juga yang jelas di sini, terutama karena tidak ada pertanyaan khusus dari pembaca.
Algoritma genetika. Ada kesenjangan dalam cakupan implementasinya. Sekarang saya kemungkinan besar akan mengulanginya, tetapi lebih mudah untuk mengulanginya sekali lagi.
Saya ingat banyak dari slide presentasi. Karena itu, pertanyaan utama tetap: bagaimana menggerakkan evolusi? Untuk ini, fungsi Kebugaran diciptakan. Tujuan utama dari fungsi kebugaran adalah pemilihan genotipe untuk transmisi dari populasi bot saat ini ke yang berikutnya.
Bagaimana pilihan fungsi kebugaran kemungkinan besar menjadi jelas. Masalah persilangan masih ada.
Ada beberapa metode dasar kawin silang, lebih banyak pada tautan . Tetapi prinsip dasarnya adalah pertukaran acak gen antara genotipe orang tua. Dua orang tua biasanya dipilih, ada juga beberapa metode untuk memilih orang tua dari suatu populasi, tautannya bisa dibaca lebih detail. Meskipun pilihan orang tua dibuat secara acak, kemungkinan memilih orang tua tertentu tumbuh sebanding dengan fungsi kebugarannya.
Selanjutnya, fungsi mutasi diterapkan pada genotipe yang sudah jadi.
Dalam kasus kami, dari waktu ke waktu, algoritma mengubah gen yang dipilih secara acak menjadi gen acak, dengan kata lain, salah satu bobot dari perubahan jaringan saraf menjadi gen acak.
Kami mendapat populasi baru dan evolusi lebih lanjut berlanjut ke hasil yang diinginkan. Ada beberapa poin, yang pertama: semakin banyak bot dalam populasi, semakin cepat algoritma genetika akan menemukan solusi optimal atau menyatu dengan solusi (rasio bobot optimal dalam jaringan saraf). Misalnya, jika bot memiliki 1000 gen, maka ruang pencarian meluas secara signifikan dengan populasi 3000 bot, dibandingkan dengan populasi 300 bot. Tapi masalah lain muncul, jika Anda melepaskan semua 3.000 bot ke dalam arena yang dirancang untuk 4-8 bot, maka kemungkinan besar bot di dalamnya akan ramai secara fisik dan jika mereka mempelajari sesuatu, maka itu jelas bukan permainan di Agario. Oleh karena itu, ada dua cara utama untuk menghindari kelebihan populasi di arena: yang pertama memilih beberapa bot dari populasi secara bergantian dan bersaing di arena, dan berkali-kali hingga kami mengumpulkan statistik game untuk setiap bot. Yang kedua yang penulis tuju adalah peluncuran beberapa arena secara paralel, misalnya 50-300, semuanya tergantung pada kekuatan komputer tertentu, dan secara paralel seluruh populasi bot berpartisipasi dalam kompetisi. Populasi dapat dibagi menjadi subpopulasi dengan fungsi kebugaran dan pengidentifikasi (sesuai dengan jumlah arena), dan kemudian bertukar genotipe antara subpopulasi. Atau bayangkan semuanya sebagai satu populasi besar bot yang bermain di arena berbeda. Penulis mencoba kedua opsi, tetapi dalam versi sumber dengan satu populasi bot. Parameter dalam program Depth adalah nomor arena.
Jadi dia memberi tahu prinsip dasar membangun program. Siapa yang ingin melihat langsung, selamat datang di tautan ke github .
jika Anda tidak bisa memulainya, maka video pendek akan mencerahkan saat ini:
Pengumuman: Pada bulan Agustus, mail.ru akan menyelenggarakan piala mini AI lainnya, pengumuman resmi belum terlihat benar. Tetapi menurut informasi dari telegram grup, dasar kompetisi adalah mesin fisika, sesuatu tentang mobil. Karena itu, secara singkat tentang prinsip-prinsip membuat bot, mereka yang akan tertarik tentu saja:
Di sini, seperti tim sepak bola kami, disarankan untuk meninggalkan grup, final adalah lagu yang terpisah. Biarkan para finalis menulis tentang kemenangan, tetapi partisipasi utama kami.
Yang paling jelas dan sederhana:
Tulis lebih banyak kondisi berbeda di badan kode bot, misalnya, jika (lubang) -> lompat, dll. Kondisi sederhana efektif di awal kejuaraan, maka kompleksitas bot akan tumbuh dan keuntungan dari solusi bersyarat akan hilang.
Dan metode yang paling menjanjikan di banyak game strategis:
Metode PP ( atau bidang potensial ). Idenya indah, mencari maksimum atau minimum dalam lingkungan yang dinamis. Kotak dimensi yang dipilih dibangun di seluruh lapangan bermain atau hanya di area sekitar bot, semuanya tergantung pada ruang lingkup bot. Selanjutnya, pada setiap titik nodal dari kisi ini, kami mempertimbangkan jarak ke objek yang menarik bagi kami atau, sebagai opsi, potensi segera, mereka bisa positif (daya tarik, ini yang menarik bot) dan negatif (bahaya bot). Dengan demikian, potensi pada titik tersebut dirangkum dan kami memperoleh potensi total pada setiap titik dari grid. Bidang potensi. Bot hanya dapat memilih potensi terkecil atau terbesar, tergantung pada tugas saat ini. Pada dasarnya, bidang potensial adalah implementasi 2D, meskipun 3D akan terlihat keren, tetapi akan ada banyak sumber daya untuk perhitungan.
Yang paling sulit:
Dua implementasi utama adalah metode Brute Force atau metode Monte Carlo . Masing-masing dari mereka adalah topik dari artikel yang terpisah, tetapi menurut sensasinya, metode inilah yang akan menuntun Anda ke final. Jika ini adalah tesis, maka bot tidak hanya dapat melihat waktu saat ini atau masa lalu, tetapi jika ingin, bot dapat melihat ke masa depan, corong (kerucut) dari hasil yang mungkin muncul di sini dan semakin jauh bot ingin melihat lebih banyak opsi muncul. Sebagai contoh, pada titik waktu Tick Zero, bot memutuskan untuk pergi di salah satu dari delapan arah, pada langkah Tick + 1 di masing-masing dari delapan koordinat baru itu memiliki kesempatan untuk pergi lagi di delapan arah, dll. perlu untuk memperhitungkan kemungkinan pergerakan musuh selama ini. Setiap hasil yang mungkin dari perhitungan menghasilkan kemungkinan manfaat atau kerugian. Berdasarkan bot yang bergerak di salah satu arah. Dan selanjutnya perhitungan seperti itu di kedalaman masa depan tegang berjalan setiap tanda centang. Kedalaman tampilan gerakan ditentukan oleh sumber daya komputer yang memungkinkan. Oleh karena itu, untuk sumber daya komputer kecil, muncul masalah dalam mengoptimalkan perhitungan ini.
Tentang sumbernya, jika ada minat, saya akan mengedit komentar pada kode, sementara saya meletakkannya seperti sebelumnya.
Di sumbernya, sinyal dari Tick saat ini dan Tick sebelumnya dikirim ke input neuron, itu menjadi lebih menarik, terima kasih kepada pembaca: tongohiti untuk idenya.
Bagi mereka yang mengingat tesis tentang distribusi bobot awal dalam jaringan saraf, topik yang menarik adalah Inisialisasi Xavire.
Terima kasih atas perhatian anda Temui saya di kompetisi AI.
Artikel terkait dari peserta, tetapi penyimpangan pertama:
Dia duduk di lantai
Dan mengurutkan tumpukan surat
Dan seperti abu dingin
Saya mengambilnya di tangan saya dan melemparkannya.
Mengambil lembar yang familier
Dan luar biasa dia melihat mereka,
Bagaimana jiwa terlihat dari atas
Pada mereka tubuh yang ditinggalkan ...
Oh betapa banyak kehidupan di sini
Mengalami ireversibel!
Oh, berapa menit yang menyedihkan
Cinta dan sukacita terbunuh! ..
Strategi saya di Piala AI Rusia 2017
Sejarah partisipasi (dan hampir kemenangan) dalam kompetisi tahunan Piala AI Rusia 2016
Sejarah Kemenangan di Piala AI Rusia tahunan 2015
Piala AI Rusia 2014: strategi pemenang
Medali emas di Piala AI Rusia 2013 - bagaimana semuanya
Jalan menuju medali perak di Piala AI Rusia 2012