Bagaimana saya berhenti menjadi takut dan menulis bot permainan

Atau pemrograman dinamis lama yang bagus tanpa ini dari jaringan saraf Anda.

Setahun setengah yang lalu, saya kebetulan berpartisipasi dalam kompetisi perusahaan (untuk tujuan hiburan) dalam menulis bot untuk game Lode Runner. 20 tahun yang lalu, saya rajin menyelesaikan semua masalah pemrograman dinamis dalam kursus yang sesuai, tetapi cukup banyak melupakan segalanya dan tidak memiliki pengalaman dalam pemrograman bot game. Saya ingat, sedikit waktu yang dialokasikan, bereksperimen saat bepergian dan secara mandiri menginjak menyapu. Tapi, tiba-tiba, semuanya bekerja dengan sangat baik, jadi saya memutuskan untuk entah bagaimana menyusun materi dan tidak menenggelamkan pembaca dengan matan.


Layar game dari server proyek Codenjoy

Untuk mulai dengan, kita akan menjelaskan aturan permainan sedikit : pemain bergerak secara horizontal di sepanjang lantai atau melalui pipa, tahu bagaimana naik dan turun tangga, jatuh jika tidak ada lantai di bawahnya. Dia juga dapat memotong lubang ke kiri atau ke kanan dari dirinya sendiri, tetapi tidak setiap permukaan dapat ditebang - dengan syarat lantai “kayu” mungkin, dan beton - tidak.

Monster berlari mengejar pemain, jatuh ke lubang yang terpotong dan mati di dalamnya. Tetapi yang paling penting, pemain harus mengumpulkan emas, untuk emas pertama yang dikumpulkan ia menerima 1 poin laba, untuk N-th ia menerima N poin. Setelah kematian, keuntungan total tetap, tetapi untuk emas pertama mereka kembali memberi 1 poin. Ini menunjukkan bahwa hal utama adalah untuk tetap hidup selama mungkin, dan untuk mengumpulkan emas entah bagaimana sekunder.

Karena ada tempat-tempat di peta yang pemain tidak bisa keluar dari dirinya sendiri, bunuh diri gratis diperkenalkan ke dalam permainan, yang secara acak menempatkan pemain di suatu tempat, tetapi pada kenyataannya memecahkan seluruh permainan - bunuh diri tidak mengganggu pertumbuhan dalam nilai emas yang ditemukan. Tetapi kami tidak akan menyalahgunakan fitur ini.

Semua contoh dari game akan diberikan dalam tampilan yang disederhanakan, yang digunakan dalam log program:

Sedikit teori

Untuk mengimplementasikan bot menggunakan beberapa jenis matematika, kita perlu mengatur beberapa fungsi objektif yang menggambarkan pencapaian bot dan menemukannya tindakan yang memaksimalkannya. Misalnya, untuk mengumpulkan emas kita mendapat +100, untuk kematian -100500, jadi tidak ada koleksi emas yang akan membunuh kemungkinan kematian.

Pertanyaan terpisah, dan tentang apa sebenarnya yang kita tentukan fungsi objektifnya, yaitu Bagaimana kondisi permainannya? Dalam kasus yang paling sederhana, koordinat pemain sudah cukup, tetapi di kami semuanya jauh lebih rumit:

• koordinat pemain
• koordinat semua lubang yang ditusuk oleh semua pemain
• koordinat semua emas di peta (atau koordinat emas yang baru saja dimakan)
• koordinat semua pemain lain

Itu terlihat menakutkan. Karena itu, mari sederhanakan tugasnya dan sampai kita mengingat emas yang kita makan (kita akan kembali ke sini nanti), kita juga tidak akan mengingat koordinat pemain dan monster lain.

Dengan demikian, kondisi permainan saat ini adalah:

• koordinat pemain
• koordinat semua lubang

Tindakan pemain mengubah status dengan cara yang dapat dimengerti:

• Perintah gerak mengubah salah satu koordinat yang sesuai
• Tim penggali lubang menambahkan satu lubang baru
• Jatuh pemain tanpa dukungan mengurangi koordinat vertikal
• Tidak adanya pemain yang berdiri di atas dukungan tidak mengubah status

Sekarang kita perlu memahami cara memaksimalkan fungsi itu sendiri. Salah satu metode klasik terhormat untuk menghitung permainan N bergerak maju adalah pemrograman dinamis. Tidak mungkin dilakukan tanpa formula, oleh karena itu saya akan memberikannya dalam bentuk yang disederhanakan. Anda harus memperkenalkan banyak notasi terlebih dahulu.

Untuk kesederhanaan, kami akan menjaga laporan waktu dari langkah saat ini, mis. langkah saat ini adalah t = 0.
Kami menunjukkan kondisi permainan selama t oleh$$$x^t$ .
Banyak$$ akan menunjukkan semua tindakan bot yang valid (dalam keadaan tertentu, tetapi untuk kesederhanaan kami tidak akan menulis indeks keadaan), melalui$$ kami menunjukkan tindakan spesifik pada t (kami menghilangkan indeks).
kondisi$$$x^t$ sedang beraksi$$ masuk ke kondisi$$$x^{t+1}_a$ .

Menangkan saat aksi a dalam keadaan$$$x^t$ menyatakan sebagai$$$P(x^t, x^{t+1}_a)$ . Ketika menghitungnya, kita mengasumsikan bahwa jika kita makan emas, maka itu sama dengan G = 100, jika mereka mati, maka D = -100500, jika tidak, 0.

Biarkan$$$F(x^t)$ adalah fungsi hasil untukgameoptimaldari bot yang dalam keadaan x pada waktu t. Maka kita hanya perlu menemukan tindakan yang memaksimalkan$$$F(x^0)$ .

Sekarang kita menulis rumus pertama, yang sangat penting dan pada saat yang sama hampir benar:

$$

$$F(x^0) = \max_{a \in A} F(x^1_a) + P(x^0, x^1_a)$$

Atau untuk titik waktu yang sewenang-wenang

$$

$$F(x^t) = \max_{a \in A} F(x^{t+1}_a) + P(x^t, x^{t+1}_a)$$

Itu terlihat cukup canggung, tetapi artinya sederhana - solusi optimal untuk langkah saat ini terdiri dari solusi optimal untuk langkah selanjutnya dan keuntungan dalam langkah saat ini. Ini adalah prinsip optimalitas Bellman yang dirumuskan secara bengkok. Kami tidak tahu apa-apa tentang nilai-nilai optimal pada langkah 1, tetapi jika kami mengetahuinya, kami akan menemukan tindakan yang memaksimalkan fungsi dengan hanya mengulangi semua tindakan bot. Keindahan hubungan perulangan adalah yang bisa kita temukan$$$F(x^1)$, menerapkan prinsip optimalitas untuk itu, mengekspresikannya dengan formula yang persis sama $$$F(x^2)$. Kami juga dapat dengan mudah mengekspresikan fungsi pembayaran pada langkah apa pun.

Tampaknya masalah telah terpecahkan, tetapi di sini kita dihadapkan dengan masalah bahwa jika pada setiap langkah kita harus memilah-milah 6 aksi pemain, maka pada langkah rekursi kita harus memilah 6 ^ N opsi, yang untuk N = 8 sudah merupakan angka yang cukup layak ~ 1.6 juta kasus. Di sisi lain, kami memiliki mikroprosesor gigahertz yang tidak ada hubungannya, dan tampaknya mereka akan sepenuhnya mengatasi tugas tersebut, dan kami akan membatasi kedalaman pencarian hanya dengan 8 langkah.

Jadi, horizon perencanaan kami adalah 8 langkah, tetapi dari mana harus mendapatkan nilai$$$F(x^9)$? Dan di sini kita baru saja datang dengan gagasan bahwa kita dapat menganalisis prospek dari posisi itu, dan menetapkan nilai berdasarkan pertimbangan tertinggi mereka. Biarkan saja$$$F(x^9)=S(x^9)$dimana $$$S(x)$ini adalah fungsi dari strategi, dalam versi paling sederhana itu hanya sebuah matriks dari mana kita memilih nilai sesuai dengan koordinat geometri bot. Kita dapat mengatakan bahwa 8 gerakan pertama itu adalah taktik, dan kemudian strategi dimulai. Sebenarnya, tidak ada yang membatasi kita dalam memilih strategi, dan kita akan menanganinya nanti, tetapi untuk saat ini, agar tidak menjadi seperti burung hantu dari lelucon tentang kuda dan landak, kita akan beralih ke taktik.

Skema umum

Jadi, kami memutuskan algoritma. Pada setiap langkah, kami menyelesaikan masalah pengoptimalan, menemukan tindakan optimal untuk langkah tersebut, menyelesaikannya, setelah itu permainan dilanjutkan ke langkah berikutnya.

Hal ini diperlukan untuk menyelesaikan masalah baru di setiap langkah, karena dengan setiap jalannya permainan tugas berubah sedikit, emas baru muncul, seseorang makan seseorang, pemain bergerak ...
Tapi jangan berpikir bahwa algoritma kami yang cerdik dapat menyediakan segalanya. Setelah menyelesaikan masalah optimisasi, Anda harus menambahkan handler yang akan memeriksa situasi yang tidak menyenangkan:

• Bot berdiri di tempat untuk waktu yang lama
• Berjalan terus-menerus kiri-kanan
• Kekurangan penghasilan terlalu lama

Semua ini mungkin memerlukan perubahan radikal dari strategi, bunuh diri, atau tindakan lain di luar kerangka kerja algoritma optimalisasi. Sifat situasi ini mungkin berbeda. Terkadang kontradiksi antara strategi dan taktik menyebabkan pembekuan bot terjadi pada titik yang tampaknya secara strategis penting baginya, yang ditemukan oleh ahli botani kuno bernama Buridanov Donkey.



Lawan Anda dapat membekukan dan menutup jalan pendek Anda ke emas yang diidamkan - kami akan menangani semua ini nanti.

Pertarungan melawan penundaan

Pertimbangkan kasus sederhana ketika satu emas terletak di sebelah kanan bot dan tidak ada lagi sel emas dalam radius 8. Langkah apa yang akan diambil bot, dipandu oleh formula kami? Bahkan - benar-benar ada. Sebagai contoh, semua solusi ini memberikan hasil yang persis sama bahkan untuk tiga gerakan:

• langkah kiri - langkah kanan - langkah kanan
• langkah ke kanan - tidak bertindak - tidak bertindak
• tidak bertindak - tidak bertindak - langkah ke kanan

Ketiga opsi memberikan satu kemenangan sama dengan 100, bot dapat memilih opsi dengan tidak ada tindakan, pada langkah berikutnya menyelesaikan masalah yang sama lagi, pilih tidak bertindak lagi ... Dan berdiri diam selamanya. Kita perlu memodifikasi formula untuk menghitung kemenangan agar dapat merangsang bot untuk bertindak sedini mungkin:

$$

$$F(x^0) = \max_{a \in A} F(x^1_a)*E + P(x^0, x^1_a)$$

kami mengalikan keuntungan di masa mendatang pada langkah berikutnya dengan "koefisien inflasi" E, yang harus dipilih kurang dari 1. Kita dapat dengan aman bereksperimen dengan nilai-nilai 0,95 atau 0,9. Tetapi jangan memilihnya terlalu kecil, misalnya, dengan nilai E = 0,5, emas yang dimakan pada langkah ke-8 hanya akan membawa 0,39 poin.

Maka, kami menemukan kembali prinsip "Jangan menunda sampai besok apa yang bisa Anda makan hari ini."

Keamanan

Mengumpulkan emas tentu baik, tetapi Anda masih perlu memikirkan keamanan. Kami memiliki dua tugas:

• Ajari bot untuk menggali lubang jika monster itu dalam posisi yang sesuai
• Ajari bot untuk melarikan diri dari monster

Tetapi kami tidak memberi tahu bot apa yang harus dilakukan, kami menetapkan nilai fungsi laba dan algoritma pengoptimalan akan memilih langkah-langkah yang sesuai. Masalah terpisah adalah bahwa kita tidak menghitung secara tepat di mana monster bisa bergerak. Oleh karena itu, untuk kesederhanaan, kami berasumsi bahwa monster sudah ada, dan kami tidak perlu mendekati mereka.

Jika mereka mulai mendekati kita, bot itu sendiri akan mulai lari dari mereka, karena akan didenda karena terlalu dekat dengan mereka (semacam isolasi diri). Jadi, kami memperkenalkan dua aturan:

• Jika kita sampai pada monster pada jarak d dan d <= 3, maka denda 100.500 * (4-d) / 4 dikenakan pada kita
• Jika monster itu cukup dekat, berada di jalur yang sama dengan kita dan ada lubang di antara kita, maka kita mendapat untung P

Konsep "mendekati monster di kejauhan d" kita akan membuka sedikit nanti, tetapi untuk sekarang, mari kita beralih ke strategi.

Kami berkeliling grafik

Secara matematis, masalah pengelakan emas yang optimal adalah masalah yang sudah lama dipecahkan oleh seorang salesman keliling, solusinya bukan kesenangan. Tetapi sebelum Anda memecahkan masalah seperti itu, Anda perlu memikirkan pertanyaan sederhana - tetapi bagaimana Anda menemukan jarak antara dua poin dalam permainan? Atau dalam bentuk yang sedikit lebih berguna: untuk emas yang diberikan dan untuk setiap titik di peta, cari jumlah minimum gerakan yang akan dicapai pemain dari emas. Untuk beberapa waktu kita akan lupa tentang menggali lubang dan melompat ke dalamnya, kita hanya akan meninggalkan gerakan alami per 1 sel. Hanya kita yang akan berjalan di arah yang berlawanan - dari emas dan melintasi peta.



Pada langkah pertama, kita memilih semua sel dari mana kita bisa menjadi emas dalam satu gerakan dan menetapkannya menjadi 1. Pada langkah kedua, kita memilih semua sel dari mana kita jatuh menjadi satu dalam satu langkah dan menetapkannya ke 2. Gambar menunjukkan kasus untuk 3 langkah. Sekarang mari kita coba menuliskan semuanya secara formal, dalam bentuk yang sesuai untuk pemrograman.

Kita akan butuh:

• Jarak array numerik dua dimensi [x, y], di mana kita akan menyimpan hasilnya. Awalnya, untuk koordinat emas, mengandung 0, untuk poin tersisa -1.
• Array oldBorder, tempat kami menyimpan titik tempat kami akan bergerak, awalnya memiliki satu titik dengan koordinat emas
• Array newBorder, tempat kami menyimpan poin yang ditemukan pada langkah saat ini

1. Untuk setiap titik p dari oldBorder kami menemukan semua titik p_a, dari mana kami dapat mencapai p dalam satu langkah (lebih tepatnya, kami hanya mengambil semua langkah yang mungkin dari p dalam arah yang berlawanan, misalnya, terbang ke atas tanpa adanya dukungan) dan jarak [p_a] = - 1
2. Kami menempatkan setiap titik seperti p_a dalam array newBorder, pada jarak [p_a] kami menulis nomor iterasi
3. Setelah semua poin selesai:
4. Tukar array dari oldBorder dan newBorder, setelah itu kita menghapus newBorder
5. Jika oldBorder kosong, maka selesaikan algoritme, jika tidak, lanjutkan ke langkah 1.

Hal yang sama dalam kode semu:

iter=1;
newBorder.clear();
distance.fill(-1);
distance[gold]=0;
oldBorder.push(gold);

while(oldBorder.isNotEmpty()) {
  for (p: oldBorder){
    for (p_a: backMove(p)) {
      if (distance[p_a]==-1) {
         newBorder.push(p_a);
         distance[p_a]=iter;
      }
    }
  }
  Swap(newBorder, oldBorder);
  newBorder.clear();
  iter++;
}

Pada output algoritma, kita akan memiliki peta jarak dengan nilai jarak dari setiap titik dari seluruh bidang permainan ke emas. Selain itu, untuk titik-titik di mana emas tidak dapat dicapai, nilai jaraknya adalah -1. Matematikawan menyebut berjalan-jalan di sekitar bidang permainan (yang membentuk grafik dengan simpul pada titik-titik di lapangan dan ujung-ujungnya yang menghubungkan simpul yang dapat diakses dalam satu gerakan) "berjalan grafik dengan lebar". Jika kami menerapkan rekursi, bukan dua array perbatasan, ini akan disebut "berkeliling grafik secara mendalam", tetapi karena kedalamannya bisa sangat besar (beberapa ratus), saya menyarankan Anda untuk menghindari algoritma rekursif ketika melintasi grafik.

Algoritma nyata akan sedikit lebih rumit karena menggali lubang dan melompat ke dalamnya - ternyata dalam 4 gerakan kita memindahkan satu sel ke samping dan dua ke bawah (karena bergerak ke arah yang berlawanan, lalu ke atas), tetapi sedikit modifikasi dari algoritma menyelesaikan masalah.

Saya melengkapi gambar dengan angka-angka, termasuk memperhitungkan menggali lubang dan melompat ke dalamnya:



Apa yang mengingatkan kita tentang hal ini?



Aroma emas! Dan bot kami akan menyukai bau ini, seperti Rocky untuk keju (tetapi pada saat yang sama ia tidak kehilangan otaknya dan menghindari monster, dan bahkan menggali lubang untuk mereka). Mari kita buat dia strategi serakah yang sederhana:

1. Untuk setiap emas, kami membuat peta jarak dan menemukan jarak ke pemain.
2. Pilih emas yang paling dekat dengan pemain dan ambil kartunya untuk menghitung strategi
3. Untuk setiap sel peta, dilambangkan dengan d jaraknya dengan emas, kemudian nilai strategis
   

   $$

   $$S(x) = \begin{cases} 0 & \text{ $d < 0$,}\\ G_s E_s^d & \text{ $d \geq0$ } \end{cases}$$

Dimana $$$G_s$ini adalah beberapa nilai imajiner emas, diinginkan bahwa nilainya beberapa kali lebih rendah dari sekarang, dan $$$E_s$ini adalah koefisien inflasi <1, karena semakin jauh emas khayalan, semakin murah. Rasio koefisien E dan$$$E_s$merupakan masalah milenium yang belum terpecahkan dan menyisakan ruang untuk kreativitas.

Jangan berpikir bahwa bot kami akan selalu berlari ke emas terdekat. Misalkan kita memiliki satu emas di sebelah kiri pada jarak 5 sel dan kemudian batal, dan di sebelah kanan dua emas pada jarak 6 dan 7. Karena emas asli lebih berharga daripada yang dibayangkan, bot akan pergi ke kanan.

Sebelum beralih ke strategi yang lebih menarik, kami akan melakukan peningkatan lain. Dalam permainan, gravitasi menarik pemain ke bawah, dan dia hanya bisa naik tangga. Jadi, emas yang lebih tinggi harus dihargai lebih tinggi. Jika ketinggian dilaporkan dari garis atas ke bawah, maka Anda dapat mengalikan nilai emas (dengan koordinat y vertikal) dengan$$$E_h^y$. Untuk koefisien$$$E_h$ istilah baru "tingkat inflasi vertikal" diciptakan, setidaknya tidak digunakan oleh para ekonom dan mencerminkan esensi dengan baik.

Strategi yang rumit

Dengan satu emas disortir, Anda perlu melakukan sesuatu dengan semua emas, dan saya tidak ingin menarik matematika yang berat. Ada solusi yang sangat elegan, sederhana dan tidak benar (dalam arti sempit) - jika satu emas menciptakan "bidang" nilai di sekitar dirinya sendiri, maka mari kita tambahkan semua bidang nilai dari semua sel dengan emas ke dalam satu matriks dan gunakan sebagai strategi. Ya, ini bukan solusi yang optimal, tetapi beberapa unit emas di jarak tengah bisa lebih berharga daripada yang dekat.

Namun, solusi baru menciptakan masalah baru - sebuah matriks nilai baru mungkin mengandung maxima lokal, di mana tidak ada emas. Karena bot kami dapat masuk ke dalamnya dan tidak ingin keluar, itu berarti bahwa kami perlu menambahkan penangan yang memeriksa bahwa bot berada pada maksimum lokal dari strategi dan tetap di tempatnya sesuai dengan hasil dari langkah tersebut. Dan sekarang kami memiliki alat untuk memerangi pembekuan - batalkan strategi ini dengan gerakan N dan kembalikan sementara ke strategi emas terdekat.

Sangat lucu untuk menyaksikan bagaimana bot yang macet mengubah strateginya dan mulai turun terus menerus, memakan semua emas terdekat, di lantai bawah peta yang disadari oleh bot dan mencoba memanjat. Semacam Dr. Jekyll dan Mr. Hyde.

Strategi tidak setuju dengan taktik

Di sini bot kami menjadi emas di bawah lantai:



Sudah jatuh ke dalam algoritma pengoptimalan, masih harus mengambil 3 langkah ke kanan, memotong lubang di kanan dan melompat ke dalamnya, dan kemudian gravitasi akan melakukan semuanya dengan sendirinya. Sesuatu seperti ini:



Tapi bot membeku di tempat. Debugging menunjukkan bahwa tidak ada kesalahan: bot memutuskan bahwa strategi optimal adalah menunggu satu gerakan, dan kemudian pergi sepanjang rute yang ditentukan dan mengambil emas pada langkah terakhir yang dianalisis. Dalam kasus pertama, ia menerima keuntungan dari emas yang diterima dan keuntungan dari emas imajiner (pada iterasi terakhir dianalisis hanya di sel di mana emas itu), dan yang kedua - hanya dari emas asli (meskipun belokan sebelumnya), tetapi keuntungan tidak ada strategi lagi, karena tempat di bawah emas itu busuk dan tidak menjanjikan. Nah, pada langkah selanjutnya dia kembali memutuskan untuk mengambil jeda satu langkah, kita sudah menyelesaikan masalah seperti itu.

Saya harus memodifikasi strategi - karena kami menghafal semua emas yang dimakan pada tahap analisis, mengurangi kartu nilai emas yang dimakan dari total matriks nilai strategis, dengan demikian, strategi memperhitungkan pencapaian taktik (dimungkinkan untuk menghitung nilai secara berbeda - menambahkan matriks hanya untuk Seluruh emas, tetapi secara komputasi lebih rumit, karena ada lebih banyak emas di peta daripada yang bisa kita makan dalam 8 gerakan).

Tetapi ini tidak mengakhiri siksaan kami. Misalkan matriks nilai strategis memiliki maksimum lokal dan bot mendekatinya untuk 7 langkah. Apakah bot akan membeku? Tidak, karena untuk setiap rute di mana bot mencapai maksimum lokal dalam 8 gerakan, kemenangannya akan sama. Penundaan tua yang bagus. Alasannya adalah bahwa keuntungan strategis tidak tergantung pada saat kita menemukan diri kita di dalam sel. Hal pertama yang terlintas dalam pikiran adalah untuk menghaluskan bot untuk yang sederhana, tetapi ini tidak membantu dengan cara apapun dari berjalan kiri / kanan yang tidak masuk akal. Adalah perlu untuk memperlakukan akar penyebab - untuk memperhitungkan keuntungan strategis di setiap belokan (sebagai perbedaan antara nilai strategis negara baru dan saat ini), menguranginya dari waktu ke waktu oleh suatu faktor.
Itu perkenalkan istilah tambahan dalam ungkapan untuk menang:

$$

$$p_{new}(x^0,x^1_a) = p(x^0,x^1_a) + (S(x^1_a) – S(x^0)).$$

nilai fungsi objektif pada yang terakhir umumnya dianggap nol: $$$F(x^9) =0$. Karena keuntungan disusutkan dengan setiap gerakan dengan mengalikan dengan koefisien, ini akan membuat bot kami mendapatkan keuntungan strategis yang lebih cepat dan menghilangkan masalah yang diamati.

Strategi yang belum diuji

Saya belum menguji strategi ini dalam praktiknya, tetapi terlihat menjanjikan.

1. Karena kita mengetahui semua jarak antara titik-titik emas, dan jarak antara emas dan pemain, kita dapat menemukan rantai pemain-N sel-sel emas (di mana N kecil, misalnya 5 atau 6) dengan panjang terpendek. Bahkan pencarian waktu yang paling sederhana pun sudah cukup.
2. Pilih emas pertama dalam rantai ini dan gunakan bidang nilainya sebagai matriks strategi.

Dalam hal ini, diinginkan untuk menutup biaya nyata dan biaya emas imajiner sehingga bot tidak tergesa-gesa ke ruang bawah tanah ke emas terdekat.

Perbaikan akhir

Setelah kita belajar untuk "menyebar" di peta, mari kita lakukan "penyebaran" yang serupa dari setiap monster untuk beberapa gerakan dan temukan semua sel di mana monster itu bisa berakhir, bersama dengan jumlah gerakan yang akan membuatnya. Ini akan memungkinkan pemain untuk merangkak melalui pipa di atas kepala monster sepenuhnya dengan aman.

Dan saat terakhir - ketika menghitung strategi dan nilai imajiner emas, kami tidak memperhitungkan posisi pemain lain, hanya "menghapus" mereka ketika menganalisis peta. Ternyata cangkang gantung individu dapat memblokir akses ke seluruh wilayah, sehingga penangan tambahan ditambahkan - untuk melacak lawan yang membeku dan menggantinya dengan blok beton selama analisis.

Fitur Implementasi

Karena algoritma utama bersifat rekursif, kita harus dapat dengan cepat mengubah objek keadaan dan mengembalikannya ke yang asli untuk modifikasi lebih lanjut. Saya menggunakan java, bahasa dengan pengumpulan sampah, mencoba jutaan perubahan yang terkait dengan membuat objek berumur pendek dapat menyebabkan beberapa kumpulan sampah dalam satu giliran permainan, yang bisa berakibat fatal dalam hal kecepatan. Oleh karena itu, seseorang harus sangat berhati-hati dalam struktur data yang digunakan, saya hanya menggunakan array dan daftar. Baik, atau gunakan proyek Valgala atas risiko dan risiko Anda sendiri :)

Kode Sumber dan Server Game

Kode sumber dapat ditemukan di sini di github . Jangan menilai dengan ketat, banyak yang telah dilakukan dengan tergesa-gesa. Server game codenjoy akan menyediakan infrastruktur untuk meluncurkan bot dan memantau game. Pada saat penciptaan, revisi itu relevan, revisi 1.0.26 digunakan.

Anda dapat memulai server dengan baris berikut:

call mvn -DMAVEN_OPTS=-Xmx1024m -Dmaven.test.skip=true clean jetty:run-war -Dcontext=another-context -Ploderunner

Proyek itu sendiri sangat penasaran, menyediakan game untuk setiap selera.

Kesimpulan

Jika Anda telah membaca semua ini sampai akhir tanpa persiapan awal dan mengerti segalanya, maka Anda adalah orang yang langka.