Halo semuanya, nama saya Olya. Dua minggu lalu, kontes lain berakhir di CodinGame - kompetisi untuk pemrograman bot untuk game. Saya masuk ke dalam 300 papan peringkat teratas dunia, jadi saya ingin memberi tahu Anda mengapa kontes itu keren dan membagikan rahasia saya. Ivan spaceorc , yang masuk ke 100 teratas dari kompetisi yang sama, juga akan berbagi rahasia.
Anda akan belajar bagaimana berhasil bersaing dalam kompetisi pemrograman AI game.
Apa itu CodinGame?
codingame.com adalah platform pendidikan untuk pengembang dari segala usia dan tingkat pelatihan. Anda dapat menulis dalam 26 bahasa : dari C # dan Python ke Bash dan Haskell. Yang paling keren adalah bahwa tugas-tugas di sana tidak membosankan dan tidak bisa dipahami, tetapi permainan nyata dengan GUI yang bagus:
Kontes adalah kompetisi 10 hari yang diadakan setiap dua bulan sekali. Siapa pun dapat berpartisipasi, tidak perlu menjadi finalis ACM ICPC. Tentu saja, untuk sampai ke puncak, Anda harus setidaknya memahami algoritma khas kecerdasan buatan game.
Tetapi untuk menghabiskan beberapa malam dengan minat, pengetahuan paling dasar sudah cukup. Di setiap kontes ada kode yang sudah jadi untuk membaca input data. Tetap hanya membaca aturan, menulis bersahaja jika-yang lain - dan ke pertempuran!
Kode kutulu
"Kode Cthulhu" adalah kontes terakhir, yang berlangsung dari 15 hingga 25 Juni. Untuk mengetahui plot dan tujuan, deskripsi sudah cukup:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Apa yang bisa berbohong selamanya tidak mati sama sekali. Dan Maut mati di aeon misterius.
Anda dan tim peneliti Anda telah menemukan makam Cthulhu. Ini adalah keputusan terburuk dalam hidup Anda, karena dia belum siap untuk bangun dan sekarang lapar akan kematian Anda. Tapi ruang bawah tanah itu adalah labirin nyata, dan Anda tidak ingat di mana pintu keluar itu ... Jika masih ada di sana!
Oh ... dan sepertinya Cthulhu tidak sendirian, dan sekarang dia mengirimkan yang dalam untukmu.
Cobalah untuk tetap hidup paling lama, tetapi ingatlah bahwa Anda sendiri tidak akan bertahan lama ...
Aturannya
Saya akan segera mengatakan bahwa alih-alih membaca deskripsi teks tentang aturan, Anda dapat menonton video analisis aturan dan taktik dasar dari Tinsane :
Kalau tidak, baca terus.
Peta
Dalam permainan, empat pemain berjalan di peta yang dihasilkan - lebih tepatnya, grafik sel yang terhubung satu sama lain. Lebih banyak di peta menjalankan antek musuh, yang tujuannya adalah untuk mengejar dan menakuti para pemain.
Karakter
- Peneliti adalah salah satu pemain. Melangkah ke segala arah di satu sel. Ia memiliki kekuatan super, tetapi lebih banyak tentang mereka nanti.
- Vanderer adalah monster hijau. Muncul di peta setiap 5 putaran, dari titik yang diketahui sebelumnya. Ini memunculkan lebih dari 3-6 gerakan, mencari pemain terdekat dan memulai pengejaran. Hanya berjalan satu kotak per putaran. Jika dia tidak menangkap siapa pun di langkah N, dia menghilang dari peta.
- Pedas - mirip dengan Kematian dengan sabit. Muncul di tempat pemain yang kesehatannya turun di bawah 200 poin, dan tetap di peta sampai akhir pertandingan. “Melihat” seorang pemain jika tidak ada dinding di antara mereka. Jika dalam 2 gerakan target tidak hilang pandangan, langkah selanjutnya melompat ke tempat di mana pemain terakhir terlihat.
Bertahan hidup
Jika pengembara atau pembunuh memasuki sel dengan pemain, pemain kehilangan 20 kesehatan. Juga, pemain kehilangan sejumlah kesehatan setiap belokan tanpa alasan. Tetapi jika ada peneliti yang hidup dalam jari-jari dua sel, maka kesehatannya sedikit berkurang.
Kekuatan super peneliti
- RENCANA - Meningkatkan kesehatan sebesar 2 poin dari 5 putaran. Jika peneliti lain termasuk dalam radius aksi, maka efeknya meluas ke mereka, dan pembuat efek menerima kesehatan +2 untuk masing-masing. Anda dapat menggunakan 2 kali per game.
- YELL - membuat takut pemain di sel berikutnya. Tindakan yang direncanakan untuk giliran berikutnya berubah menjadi WAIT (pemain hanya akan diam). Ini berguna jika pengembara mengejar musuh, dan Anda ingin menggantinya.
- LIGHT - menerangi sel dalam radius 5, Anda dapat menggunakan 3 kali per game. Membantu menakuti para pengembara: ketika mereka menghitung jalur ke target terdekat, masing-masing sel yang diterangi dihitung sebagai 4.
Akhir dari game
Seorang pemain mati jika kesehatannya turun ke nol. Setelah 200 gerakan, para pemain yang selamat mulai kehilangan kesehatan lebih cepat, dan permainan berakhir segera.
Pengembang kontes memberikan aturan kepada para pemain, tetapi pemain yang berhasil pergi ke Github dan membaca kode wasit .
Taktik
Saya harus segera mengatakan bahwa saya tidak memulai dari awal. Pada 16 Juni, Kontur mengadakan pusat pengkodean di tujuh kota - pertemuan untuk mereka yang ingin mendiskusikan kontes dan bersenang-senang di lingkungan yang menyenangkan ( foto ).
Saya lulus ujian di universitas dan tidak sampai ke pusat di Yekaterinburg, tetapi saya mengambil keuntungan dari bonus dari panitia - starter kit. Ini tersedia dalam dua bahasa - C # dan TypeScript , dan sudah mengimplementasikan seluruh infrastruktur: logika membaca keadaan permainan di setiap belokan, serta kelas yang mencirikan permainan itu sendiri (seperti keadaan dan tindakan yang mungkin), dan beberapa yang tambahan (misalnya, pengatur waktu kustom) . Saya dapat segera mulai menulis hal yang paling menarik - otak saya bot peneliti
Salah satu pemimpin hub di Yekaterinburg adalah Vanya Dashkevich ( spaceorc ). Dia telah duduk di CodinGame selama lebih dari setahun, berpartisipasi dalam tujuh kontes, dan dalam lima hit top 100 dunia:
Saya menemukan dari Vanya rincian keputusan, yang memberinya tempat ke-64 di papan peringkat dunia, dan membandingkan keputusannya dengan keputusan saya.
[1] Datanglah ke hub: di sana Anda bisa mendapatkan tautan ke starter kit, diskusikan peraturan, buat taktik dan temui orang-orang yang menarik.
Bahwa pada awal kontes, pada akhirnya, algoritma untuk memilih langkah selanjutnya terlihat sama:
- Hasilkan semua tindakan yang tersedia untuk bot;
- Terapkan pada kondisi saat ini;
- Evaluasi hasil dari langkah-langkah ini;
- Pilih yang terbaik.
Hasilkan Tindakan yang Tersedia
Ollisteka : Sudah pada langkah ini, saya mulai menerapkan heuristik - saya membayangkan diri saya di tempat peneliti ini, dan memutuskan apa yang baik dan apa yang tidak. Bisakah saya pergi ke sel bebas berikutnya? Tambahkan langkah seperti itu. Saya masih punya rencana yang tidak digunakan, dan tidak ada Wanderer atau pedang di dekatnya yang akan menyerang saya giliran berikutnya? Tambah.
Menurut skema yang sama, LIGHT dan YELL masuk dalam daftar tindakan yang mungkin, tetapi penggunaannya hanya menurunkan saya lebih rendah di papan peringkat. Karena itu, saya masih menghapusnya dari implementasi akhir.
[2] Jangan takut untuk memasukkan fantasi: sebagai permulaan, heuristik sederhana dan beberapa operator bersyarat sudah cukup.
Aplikasi stroke
Proses menerapkan pemindahan ke kondisi permainan disebut simulasi. Kehadiran simulasi memungkinkan Anda untuk menggunakan teknik pemrograman AI canggih: minimax , algoritma genetika , Pencarian Monte Carlo Tree dan lainnya.
Ollisteka : Ini adalah langkah ini yang berhubungan dengan "undersimulation" saya. "Nedo" - karena setelah saya pergi, sisa pemain harus pergi, musuh harus pergi atau respawn. Namun, saya terlalu malas untuk melakukan simulasi penuh untuk empat pemain dan sejumlah besar musuh dengan logika non-sepele. Karenanya, saya hanya mengubah kesehatan saya tergantung pada apakah saya sendirian atau dalam kelompok, dan tidak menemukan pengembara pada giliran ini.
spaceorc : Pendekatan saya yang biasa belakangan ini adalah dua langkah:
- Anda naik ke panggung dengan cara apa pun ketika penyelenggara membuka semua aturan dan menjatuhkan sumber "wasit" di Github;
- Anda mengambil wasit dan menulis, menatapnya, simulasi.
Simulasi selesai, dengan semua nuansa, tetapi tidak efektif. Saya biasanya bertaruh pada kecepatan dan kedalaman pencarian ... Tapi simulasi penuh memungkinkan Anda menjalankan banyak pertandingan secara lokal dan membandingkan berbagai strategi. Saya menguji simulasi penuh dengan CodinGame - Saya memprediksi posisi antek-antek, mengetahui bagaimana saingan turun (yaitu, langkah selanjutnya), dan menemukan perbedaan. Ketika simulasi penuh siap, saya mulai menulis yang cepat - untuk melakukan ini secara sederhana, memiliki yang berfungsi.
[3] Ingin mencapai puncak? Anda harus mengetahui aturan dan menulis simulasi.
Simulasi lawan
spaceorc : Menulis Pencarian Pohon Monte Carlo, tetapi bermain lebih buruk karena ada terlalu sedikit waktu untuk memilah. Secara umum, pendekatan ini bagi saya kurang lebih hanya di Ultimate Tic-Tac-Toe . Lawan memainkan cara yang sama - simulasi per gerakan plus skor, gerakan saya - MCTS dan bermain sampai akhir. Itu mungkin dengan cara ini untuk mensimulasikan sekitar 50 game hingga akhir dalam 50 ms. Ini tidak cukup untuk MCTS, jadi saya hentikan dan kembali ke ide semula.
Akibatnya, simulasi cepat menjadi tidak lengkap:
- berhenti mempertimbangkan para pengembara lebih jauh dari 8 sel dariku;
- berhenti menelurkan pengembara, karena mereka sudah menelurkan dalam 5 gerakan, dan ini adalah kedalaman pencarian saya sekitar.
Karena ini, kedalaman pencarian telah meningkat. Saya juga mencoba mensimulasikan hanya gerakan (tanpa YELL, LIGHT, PLAN) dari lawan saya, tetapi ternyata lebih buruk.
Fungsi evaluasi
Fungsi evaluasi membantu memilih yang terbaik dari semua gerakan yang tersedia. Dibutuhkan keadaan permainan saat masuk, dan pada output memberikan angka dengan perkiraan - semakin besar, semakin baik keadaan permainan untuk pemain saat ini.
Ollisteka : Parameter apa yang termasuk dalam penilaian saya:
- kesehatan peneliti saya;
- pengembara:
- jika dia kemungkinan akan datang ke sini langkah selanjutnya, maka ini adalah langkah yang buruk;
- jika saya berada di jalur yang sama dengannya, maka semakin jauh darinya, semakin baik;
- jika dia juga memangsa saya, maka jaraknya bahkan lebih penting.
- sel bebas di sekitar, agar tidak menemui jalan buntu;
- peneliti lain, yang lebih baik untuk tetap dekat;
- RENCANA saat ini: jika kesehatan saya turun di bawah 230, maka pengobatan adalah ide yang bagus.
Pada titik tertentu, saya mencoba untuk mengevaluasi slashers, tetapi ketika saya menghapusnya, saya dibesarkan ke beberapa lusin tempat di leaderboard. Jika saya mengerjakan logika mereka lebih baik, maka mungkin mereka akan berbuat lebih baik.
Akibatnya, penilaian saya bisa lebih kecil, tetapi seperti yang mereka katakan, itu berfungsi - jangan sentuh.
spaceorc : Saya mencoba bermain dengan fungsi evaluasi, tetapi tidak berhasil dengan baik ... Secara umum, beberapa dari mereka yang ternyata jauh lebih tinggi daripada saya di leaderboard sama sekali tidak melalui banyak hal, tetapi muncul dengan fitur bagus untuk evaluasi. Saya tidak mengatasinya. Fungsi evaluasi akhir saya termasuk:
- jumlah poin (tur yang meninggal + kesehatan);
- Gagak ;
- jarak ke peneliti asing.
[4] Eksperimen: ubah koefisien dari parameter fungsi evaluasi, tambahkan parameter baru dan hapus yang lama.
Memilih langkah terbaik
Kami menyortir gerakan dalam urutan menurun, ambil yang pertama, gunakan.
Optimasi
Untuk bersaing memperebutkan tempat di atas seratus tidak cukup untuk memiliki fungsi evaluasi yang baik dan simulasi lengkap. Semakin cepat bot bekerja, semakin banyak game yang akan disimulasikan dalam waktu yang singkat. Semakin banyak game, semakin besar kemungkinan pergerakan saat ini adalah yang paling optimal. Semakin optimal bergerak, semakin tinggi tempat di papan peringkat.
Ollisteka : Saya mengambil keuntungan dari kenyataan bahwa peta dapat direpresentasikan dalam bentuk grafik - saya menghitung di muka panjang semua jalur dari sel ke sel dan tidak menghabiskan waktu untuk ini setiap waktu.
spaceorc : Pada CodinGame, simulasi bekerja dengan cepat, dalam 50 ms itu membuat beberapa puluh ribu gerakan. Karena itu:
- Topeng bit dan kode tidak aman.
- Penjelajah - int, pengembara - int, slasher - int.
- Semua keadaan yang dapat diubah cocok dalam 128 byte, jadi semuanya bekerja sangat cepat dengannya.
- Koordinatnya adalah byte, karena peta terbesar memiliki 222 sel bebas.
- Antrian harus - var antrian = stackalloc byte [255].
- Pra-perhitungan lintasan, jarak dan hal-hal lainnya.
Saya telah melakukannya sepanjang waktu belakangan ini, ini sangat bagus. Ngomong-ngomong, saya selalu menulis banyak tes untuk simulasi seperti itu, yang tanpanya tidak bisa di-debug.
[5] Ingin berkompetisi untuk mendapatkan tempat di 100 teratas - singkirkan kode yang tidak efisien.
Apa yang menyebabkannya
Ollisteka : Sepanjang kontes, bot saya tetap berada di posisi 300 teratas. Pada titik tertentu, saya bahkan berada di posisi ke-84 di papan peringkat dunia, tetapi kemudian saya membuat versi baru dan tidak kembali lagi.
- Ini adalah kontes pertama di mana saya mengambil bagian penuh, karena selama masa lalu saya terlalu sibuk dengan studi.
- Saya menyukai permainan itu sendiri - jelas cara bermain dan apa yang harus dilakukan untuk menang.
- 15% teratas dunia - kedengarannya keren :)
Sudah jelas bahwa untuk mencapai puncak Anda perlu membuat simulasi yang lengkap dan cepat. Tetapi saya tidak ingin melakukan ini, jadi saya hanya menambahkan parameter ke fungsi evaluasi dan mengubah konstanta ajaib.
spaceorc : Saya agak puas dengan hasilnya, saya naik ke atas 100 ... Tapi saya masih harus bekerja lebih pada fungsi evaluasi, bias yang kuat terhadap simulasi ternyata. Dan saya sedikit lelah pada akhirnya, imajinasi saya tidak cukup ...
Kesimpulannya
Lihat CodinGame dan coba tangan Anda! Pada bulan Juli mereka menjanjikan kontes baru - datang ke hub, kami akan mengkodekan bot bersama.
Tautan yang bermanfaat:
UPD Terima kasih dbf atas komentarnya: Kode Kutulu telah diunggah ke multipemain . Jadi, Anda bisa mempraktikkan pengetahuan yang diperoleh dalam artikel! :)