Mengembangkan AI yang licik dalam permainan taktis berdasarkan heuristik dan mutasi

Dalam permainan taktis, AI sangat penting. Jika AI dilihat sebagai "idiot buatan", maka gim ini dapat disimpan oleh multipemain, plot, suasana, dan grafik yang menakjubkan (ini tidak akurat). Solusinya sudah jelas: buat AI yang bagus, apa masalahnya?


Dalam perinciannya. Di bawah ini adalah langkah-langkah saya untuk membangun AI yang kuat dengan karakter. Tidak super kuat [ 1 ], tetapi dapat dengan cepat bekerja secara lokal di peramban rakus dari PC medium-lemah. Saya telah menerapkan pendekatan sistem pakar menggunakan seperangkat heuristik dan mutasi. 15 langkah transformasi bertahap AI dijelaskan, masing-masing langkah dapat dirasakan.

Deskripsi singkat

Dalam gim browser eksperimental, AI didasarkan pada generasi dari banyak kemungkinan keadaan - hasil dari gerakan saat ini. (Karena spesifik dan kenyamanan gim, status yang dihasilkan dalam artikel ini disebut skenario giliran atau strategi AI, tergantung pada konteksnya) . Kemudian skenario kursus dimutasi. Menurut skenario yang diperoleh, estimasi "sukses" dihitung. Yang paling sukses dan dilakukan oleh pemain komputer.

Misalnya, tiga strategi dihasilkan:

1. Berlari panik semua maju dan menyerang semua yang muncul lengan. Poin dari status akhir: 37000 poin.
2. Serang pemanah dari jarak yang aman, sementara sisanya bersembunyi di sudut. 45000 poin.
3. Semua mundur, kelompokkan dan sembunyikan dari musuh. Jika Anda dapat melukai musuh mana pun dari jarak yang aman, maka serang. 18000 poin.
4. Dalam hal ini, strategi ke-2 akan dipilih.

Yah, semuanya tampak standar. Tidak juga.

Semua bubur adalah bagaimana skrip dihasilkan dan bagaimana koefisien nilai skrip dihitung. Kenakan salah satu dari mereka, dan hasilnya akan membuat Anda sedih.

Aturan gim

Pemain dan AI awalnya memiliki 6 unit identik di sudut. Setiap tim secara bergiliran bergantian oleh semua unit sekaligus. Opsi untuk kemajuan setiap unit:

• lewati langkah;
• bergerak dan lewati;
• bergerak dan menyerang ( Anda bisa dan kadang-kadang Anda perlu menyerang Anda sendiri ).

Lapangan permainan dan komposisi tim dihasilkan secara prosedural ( yaitu, secara acak, tetapi dengan pemeriksaan paten dan "kebijaksanaan" yang dapat diterima ). Jenis unit:

1. Fighter F, unit jarak dekat dengan kemampuan bertahan, kerusakan, dan mobilitas terbesar. Semacam tangki + kerusakan.
2. Archer A, kerusakan terendah, tetapi serangannya berada pada jarak 1-7 dalam garis lurus.
3. Sorcerer W, mati dengan satu pukulan petarung, tetapi serangannya berada pada jarak 1-5 dalam garis lurus melalui semua unit.

Lapangan bermain selalu berukuran 10 * 10.

Bidang yang mungkin ada di peta:

• Bumi - tidak memberlakukan batasan apa pun.
• Tembok - melalui itu Anda tidak bisa menembak atau melewati.
• Air - tidak mungkin untuk melewatinya, tetapi seorang pemanah dapat menembak melaluinya (seorang penyihir yang berapi tidak bisa ).

Permainan ini sepenuhnya ditentukan, yaitu, tidak ada elemen peluang di dalamnya (100% kemungkinan mengenai pukulan, tidak ada kerusakan kritis, dll.). Ini juga permainan dengan informasi lengkap, yaitu, saingan tahu segalanya tentang kondisi pasukan satu sama lain pada waktu tertentu. Seperti di biji.

AI lebih kuat dari pemain daging, tetapi yang terakhir di tingkat pertama memiliki cacat dalam bentuk satu unit. Pada tanggal 3, pemain, sebaliknya, memiliki cacat satu unit dan jauh lebih sulit untuk menang (saya memiliki sekitar 15% dari kemenangan pada tahap ini). Kemudian muncul versi Game + yang lebih acak.


Permainan ini dikembangkan pada javascript asli: pada gaya divs dan css, dan ini adalah solusi yang paling disayangkan mungkin [ 2 ]. Ini adalah game browser. Mesinnya tidak digunakan. Satu-satunya tujuan dari proyek ini adalah untuk menciptakan pemain komputer yang kuat "dengan karakter" dan kemampuan untuk mengubah karakter ini (menghitung cyborg, orc agresif, elf berbahaya, zombi bodoh).

Untuk mengurangi "gaya komputer" musuh, beberapa trik diterapkan:

• Pemain setelah gilirannya tidak menunggu sampai AI berpikir tentang kepindahannya. Musuh "segera" mulai membuat gerakannya ( pada kenyataannya, ini adalah ilusi ).
• Pemutar komputer juga mengontrol unit menggunakan kursornya ( dan ini juga ilusi, kursor hanya terbang bersamaan dengan animasi unit ).
• AI dapat menggunakan umpan berbahaya untuk memaksa berkelahi ( semuanya adil ).

Dan apa yang rumit?

Pada awalnya, mungkin terlihat bahwa semuanya sederhana: Anda dapat dengan mudah memilah-milah semua opsi dari semua gerakan dan memilih yang terbaik. Tetapi segera menjadi jelas bahwa semuanya sangat sulit.
Penghitungan lengkap tidak dimungkinkan karena efek ledakan kombinatorial [ 3 ], yang terdiri dari fakta bahwa ketika jumlah elemen yang akan diperiksa dalam skenario meningkat, kompleksitas perhitungan tumbuh secara eksponensial. Selanjutnya, saya akan menjelaskan apa artinya ini dalam permainan khusus saya.

Pertama, karena Pada setiap belokan, unit tim berjalan sekaligus , maka urutannya mungkin berbeda. Dan dengan 6 unit dalam tim kombinasi tersebut menjadi 720 (1 * 2 * 3 * 4 * 5 * 6). Jika akan ada lebih banyak unit, maka akan ada sejumlah besar kombinasi (pada 7 - 5040, pada 8 - 40320 ...). Jika Anda tidak memperhitungkan hasil maksimal, maka pemain berisiko mencoba kesenangan untuk mengantisipasi langkah selanjutnya selama 5-10 menit ( dan jika ia gigih, maka penundaan akan tumbuh hingga jutaan tahun, tidak semua orang akan menderita ). Karena karakteristik ini maka AI saya di awal pertempuran kurang efektif daripada di akhir. Memang, menjelang akhir, setengah dari tim sudah meninggal.


Kedua, setiap unit dapat berpindah ke berbagai titik peta . Petarung dengan rentang pergerakan 4 mungkin menyerupai 1-41 posisi berbeda. Untuk penyihir dan pemanah dengan gerakan mereka di 3, jumlah gerakan yang mungkin adalah 1-25. Misalnya, komposisi tim dapat berupa: 4 pejuang, 1 penyihir dan 1 pemanah. Kami mendapatkan total kombinasi gerakan yang berbeda untuk item ini: 41 * 41 * 41 * 41 * 25 * 25 = 1766100625. Pada kenyataannya, karena persimpangan satu sama lain dan medan yang tidak dapat dilewati, akan ada lebih sedikit kombinasi, tetapi dalam situasi yang jarang terjadi "pencar di peta" jumlah kombinasi akan menjadi mendekati nomor itu.

Ketiga, setiap unit setelah gerakan dapat melewatkan gerakan atau serangan di salah satu dari 4 arah. Yaitu, kami memiliki 5 kemungkinan tindakan akhir per unit. Total kombinasi: 5 ^ 6 = 15625.

Total kombinasi: 720 * 1766100625 * 15625 = 19868632031250000.

Dan di setiap kombinasi yang valid, perlu untuk menghitung poin dari status yang dihasilkan. Fungsi evaluasi meliputi: emulasi gerakan, serangan, menyebabkan kerusakan, kematian unit dan menghitung sisa poin yang selamat. Tentu saja, jumlah kombinasi terlalu berlebihan, karena dalam kondisi nyata, variabilitas akan berkurang karena batas-batas dan hambatan pada peta, tetapi itu masih akan menjadi jumlah kombinasi yang tak tertahankan. Dan semua ini terjadi setelah semua di browser normal.

Bagaimana ini dilakukan?

Untuk mengatasi masalah yang sama, pendekatan heuristik digunakan, algoritma umum yang dapat dijelaskan sebagai berikut:

1. Hasilkan skenario yang berbeda berdasarkan strategi yang telah ditentukan (~ 20 buah).
2. Selama masih ada waktu, mutasi skripnya, tinggalkan yang paling menguntungkan.
3. Pada akhirnya, pilih skenario dengan peringkat tertinggi.
4. Lakukan langkah pertama unit dari skrip, tetapi jangan berjalan selebihnya. Mulai animasi langkah pertama, dan saat animasi ditampilkan, terus tingkatkan skrip untuk unit yang tersisa.
5. Ulangi untuk unit yang tersisa dari langkah 1.

Metode heuristik adalah metode yang dapat bekerja (menurut McConnell [ 4 ]). Lebih dan lebih ketat di Wikipedia [ 5 ].

Poin-poin penting dalam algoritma ini adalah: pembuatan skenario, mutasi, dan penilaian profitabilitas negara yang benar. Masing-masing titik ini menggunakan heuristik lokalnya sendiri. Namun demikian, sedapat mungkin, algoritma digunakan dengan hasil optimal yang dijamin, misalnya, A * untuk menemukan jalur [ 6 ].

Pendekatan evolusi yang saya gunakan tidak dapat disebut genetik lengkap [ 7 ], karena dari dia, saya hanya menggunakan mutasi dan kelangsungan hidup "yang terkuat", dan saya secara manual menyesuaikan koefisien pengaruh heuristik individu. Algoritma untuk pembentukan populasi dan persilangan tidak digunakan. Setelah mutasi, hanya satu yang bertahan: baik mutan atau orang tua.



Saya tidak menggunakan jaringan saraf [ 8 ] karena sifat masalahnya. Pertama, karena kompleksitas implementasi yang sukses di lingkungan yang selalu berubah (munculnya mekanik, keterampilan, kemampuan baru). Kedua, karena kompleksitas dalam personalisasi terkontrol mereka (jika Anda ingin membuat dua perilaku: cepat Suvorov dan Kutuzov hati-hati [ 9 ]).

Evolusi idiot buatan menjadi kecerdasan buatan

0) Pada awalnya, hanya 3 strategi dengan gerakan acak diperkenalkan pada AI. { Kesulitan permainan # 0 }. Skor kondisinya hanyalah angka acak. Dan karena AI bukan satu-satunya elemen pengembangan, saya harus tahan dengan perilaku ikan gila selama beberapa waktu.

1) Kemudian, dalam perhitungan evaluasi strategi, pemeriksaan unit yang tersisa dan kehidupan mereka dengan AI dan pemain ditambahkan. { Kesulitan permainan # 10 }. Untuk unit mati, tim dianugerahi 0 poin. Untuk titik X yang benar-benar sehat (misalnya, 100.000 untuk pejuang F, 70.000 untuk pemanah A, 85.000 untuk penyihir W). Untuk yang terluka dibebankan 50% dari nilai inti, dan 50% sisanya sebanding dengan sisa hidup maksimum. Berkat ini, itu lebih menguntungkan bagi AI untuk membunuh musuh, dan jika dia hanya bisa melukai, maka dia memilih lawan dengan lebih sedikit nyawa - lebih rentan.

Bergerak acak menjadi lebih bermakna - AI terkadang memberi kembali.

2) Kemudian strategi awal yang lebih bermakna ditambahkan:
max_agro - semua prajurit berlari sedekat mungkin dengan musuh dan mencoba menimbulkan kerusakan sebanyak mungkin . { Kesulitan permainan # 20 }. Satu strategi menggunakan urutan gerakan asli unit, yang kedua berjalan dalam urutan terbalik.

AI mulai berperilaku seperti idiot buatan paling primitif dalam permainan taktis. Dan cukup sering AI seperti itu digunakan dalam permainan taktis. Ini populer karena keandalan dan kesederhanaannya. Yang ini bahkan bisa menang - tetapi sangat jarang.

Inilah tepatnya perilaku AI dalam game Master of Monsters - Disciples of Gaia yang gagal, yang membuatnya membosankan untuk bermain di dalamnya [ 10 ].


3) Kemudian strategi ditambahkan yang memperhitungkan kemungkinan kerusakan dari musuh selama gerakan, dan pilih gerakan yang menyebabkan bahaya paling kecil - lebih baik nol. { Kesulitan permainan # 30 }. Dan AI segera menjadi terlalu pengecut, menghindari kedekatan dengan musuh - lebih baik melarikan diri daripada menyerang dan melukai, karena musuh dapat memberikan lebih banyak perubahan!

Oleh karena itu, penilaian kondisi juga mulai memperhitungkan kemungkinan kerusakan pada musuh . Poin penalti dari potensi kerusakan dari musuh mulai dihitung dengan koefisien yang menurun dari 0,20 ( koefisien itu secara konstan dikonfigurasi ulang ). Ini memaksa AI untuk memilih opsi agresif ketika memilih antara serangan atau penerbangan, karena itu membawa poin 5 kali lebih banyak daripada penerbangan. Tetapi AI masih tetap pengecut untuk waktu yang lama, karena untuk masuk ke dalam situasi pilihan seperti itu, musuh harus sudah dalam jangkauan, dan AI itu sendiri, dengan penilaian seperti itu, tidak akan pernah menempatkan dirinya sebagai yang pertama diserang. Artinya, itu tidak akan menuju pemulihan hubungan. Tentu saja, pemain akan merasa dicurangi, karena AI memiliki kesabaran yang tak ada habisnya dan dapat melarikan diri dari bahaya selamanya, memaksa pemain untuk agresi.

Perlu dicatat bahwa perhitungan kerusakan yang mungkin terjadi sangat lama tanpa menggunakan cache. Satu kesalahan perhitungan yang lengkap dari suatu strategi tanpa optimasi pada awalnya memakan waktu 700 milidetik. Tapi saya punya batasan pada keseluruhan satu unit ~ 4000 ms! Setelah optimisasi dan cache yang dihabiskan, kali ini berkurang hingga 20 milidetik dengan strategi yang sangat mirip ( sayangnya, cache tidak dapat dihitung sebelumnya karena efek ledakan kombinatorial, sehingga 20 ms tidak selalu tercapai ).

Karena itu, ketika saya memperkenalkan teknologi perhitungan dengan meramalkan beberapa langkah ke depan , waktu perhitungan untuk kedalaman hanya 2 langkah (musuh dan AI) telah mencapai +700 milidetik. Dalam hal ini, optimasi digunakan dengan memotong cabang "lemah". Jika Anda menggunakan strategi max_agro primitif untuk ini, maka peningkatan waktu adalah +30 milidetik dan caching hampir tidak mengurangi perbedaan ini ( karena posisi pada peta benar-benar baru ).

Akibatnya, saya membuat 5 pendekatan berbeda untuk pengembangan pendekatan ini, tetapi pada akhirnya saya benar-benar meninggalkannya, karena mutasi dengan heuristik memberikan hasil yang lebih baik dan lebih cepat.

4) Strategi berikut ditujukan untuk memperluas keragaman awal strategi:
far_attack_and_hide - unit mencoba menyerang sejauh mungkin dari musuh, dan jika mereka tidak menyerang, mereka bersembunyi dari serangan apa pun.

close_group_flee - unit mundur dari pertempuran dan kelompok sedekat mungkin satu sama lain. Jika Anda dapat dengan aman menyerang musuh pada saat bersamaan, serang.
{ Kesulitan permainan # 40 }.

Ini meningkatkan proses pertempuran itu sendiri, tetapi dimulainya pertempuran selalu tidak menguntungkan bagi AI: itu terus mundur, tetapi itu bisa dipancing ke dalam serangan dan ditakuti sehingga kelompok AI dibagi menjadi beberapa kelompok kecil yang dapat dihancurkan secara terpisah.

5) Maka sudah saatnya mutasi . { Kesulitan permainan # 50 }.

Algoritma mutasi sangat sederhana:

• ketika mengulangi strategi yang dipilih, satu salinan dari strategi itu dibuat;
• dalam salinan ini, mutasi kursus dibuat;
• jika langkah tersebut menjadi tidak valid, maka itu dikoreksi ke setidaknya beberapa yang valid sesuai dengan salah satu strategi standar;
• Poin-poin dari strategi yang bermutasi dihitung;
• jika mutan memiliki lebih banyak poin, maka mutan menggantikan orang tuanya.

Pada saat yang sama, orang luar tidak menghapus strategi, dan juga berpartisipasi dalam mutasi, karena selalu ada kemungkinan serangkaian mutasi yang sangat berhasil.

Pada awalnya, tipe mutasi yang paling primitif diterapkan: dari 1 hingga 3 gerakan digantikan oleh yang acak, urutan gerakannya tetap sama. Selama satu iterasi perhitungan, rata-rata, sekitar 5-15 mutasi diciptakan untuk setiap strategi. Selain itu, rata-rata, setiap mutasi kelima lebih menguntungkan dan menggantikan strategi orang tua.

6) Umpan heuristik . { Kesulitan permainan # 60 }.

Heuristik ini mengulangi taktik yang dengannya aku memancing AI untuk menyerang dengan satu unit untuk membunuhnya satu per satu. Trik ini juga diajarkan kepada AI.

Untuk melakukan ini, dalam fungsi menghitung poin untuk keadaan strategi, diperiksa apakah keadaan saat ini sesuai dengan situasi umpan:

• Hanya satu prajurit AI yang bisa diserang;
• Hanya satu musuh yang dapat menyerang unit yang dirayapi;
• Unit pemutar komputer harus selamat setelah serangan ini;
• Setidaknya dua unit komputer akan dapat menyerang sebagai respons. Semakin banyak unit penghukuman, semakin banyak poin untuk heuristik.

Efeknya ternyata sangat bagus: menjadi lebih mudah bagi pemain untuk memulai pertempuran sendiri. Selain itu, lebih sering daripada tidak, itu masih lebih menguntungkan bagi pemain untuk "bertahan" pada umpan ini, karena setelah serangan balik ia akan dapat jatuh pada AI dengan seluruh pasukannya ( ini jika ia dikelompokkan secara wajar sebelumnya ). Dan di sana semua keputusan taktis lokal yang kompeten akan menyelesaikan segalanya.


7) Kemudian mulai menarik perhatian saya bahwa para pejuang AI terus-menerus menyebar seperti kecoak . { Kesulitan permainan # 70 }. Juga, tentara bisa bersembunyi di sudut atau masuk ke terowongan yang ketat, di mana AI sangat kehilangan efektivitasnya dalam memilah kemungkinan serangan.
Oleh karena itu, heuristik untuk memperkirakan jarak antara unit dan topografi peta dengan asumsi berikut ditambahkan ke fungsi evaluasi:

• Semakin dekat sekutu satu sama lain "rata-rata" - semakin baik (unit-unit mulai tersebar ke berbagai bagian peta lebih jarang).
• Semakin dekat prajurit AI dengan tentara "rata-rata" musuh, semakin baik (saya membutuhkan AI ofensif).
• Semakin besar jarak maksimum antara pasangan sekutu, semakin buruk. Pada saat yang sama, jarak 4 tidak dihukum, dan semua yang lebih besar dihukum secara eksponensial (ini berhenti menarik tentara ke barisan rentan).
• Jika seorang prajurit AI tidak dapat berlari dan menyerang musuh setidaknya dalam 2 putaran, maka ia harus didenda (ini memaksanya untuk maju, tetapi tidak berdiri sendiri di bawah serangan).
• Jika dalam radius 2 langkah dari prajurit ada terlalu banyak posisi pemblokiran, maka denda dia (jarang mereka mulai berjalan ke terowongan).
• Jika seorang tentara berada di perbatasan peta, maka denda dia lebih keras. Sebagai hasil dari ini, kemampuan manuver AI sangat meningkat, seperti Unit dapat berjalan dari area terbuka ke posisi yang jauh lebih besar daripada dari sudut atau terowongan.

8) Maka saatnya untuk mengembangkan strategi. { Kesulitan permainan # 80 }. Saya tidak bisa menambahkan enumerasi lengkap tentang urutan gerakan unit yang mungkin, tapi saya bisa menghitung gerakan mereka berdasarkan tipe : petarung, pemanah, penyihir. Oleh karena itu, strategi muncul untuk urutan gerakan, dari bentuk W_A_F: pertama semua penyihir berjalan, lalu semua pemanah, lalu semua pejuang.

Dengan demikian, 6 strategi baru ditambahkan: W_A_F, W_F_A, A_W_F, A_F_W, F_A_W, F_W_A. Mereka tidak menyelesaikan semua masalah, tetapi secara signifikan meningkatkan kualitas permainan.

9) Saya mengalami mutasi, tetapi tidak banyak berguna. { Kesulitan permainan # 90 }. Sebagian besar mereka meningkatkan strategi yang lemah, sedangkan yang sukses jarang membaik. Oleh karena itu, mutasi dimodifikasi dan setiap kali salah satu jenis mutasi acak bekerja:

• Dari 1 hingga 3 gerakan diganti dengan yang acak, urutan gerakannya tetap sama (cara lama);
• Tukar urutan langkah dua unit acak. Biarkan mereka tidak berubah, bahkan jika mereka tidak optimal. Jika langkah itu tidak dapat diulang, maka itu diciptakan kembali secara acak oleh salah satu strategi biasa ke keadaan yang valid;
• Tukar urutan gerakan dua unit acak dan hitung gerakan mereka lagi. Semua gerakan yang gagal di unit berikutnya diperbaiki dengan strategi konvensional acak.

Pengenalan mutasi ini mulai dengan serius mengkompensasi ketidakmungkinan untuk sepenuhnya menghitung semua kombinasi unit move. Meskipun, karena kecelakaannya, ia tidak memberikan jaminan bahwa kudeta akan ditemukan dalam waktu terbatas yang tersedia.

10) Kemudian, lebih banyak strategi semi-acak ditambahkan . { Kesulitan permainan # 100 }. Urutan gerakan secara acak dihasilkan, dan gerakan itu sendiri dipilih sesuai dengan prinsip-prinsip berikut (untuk mengurangi kepentingannya):

• menimbulkan kerusakan maksimum;
• menanggapi sesedikit mungkin kerusakan sebagai tanggapan;
• Dapatkan sedekat mungkin dengan musuh Anda.

Saya tidak melihat peningkatan yang nyata di sini, tetapi proyek telah pindah ke tahap di mana setiap peningkatan mengarah pada efek yang dapat direproduksi yang kurang terlihat.

11) Aku bosan dengan kesalahan mencolok dari AI, ketika dia menyerang tentaraku saat menyerang dengan penyihirnya, tetapi pada saat yang sama melukai sekutunya. { Kesulitan permainan # 110 }. Meskipun sebelum itu, dia benar-benar bisa berkeliling dengan mereka dan mengeluarkan mereka dari garis api. Oleh karena itu, strategi yang dibuat dengan keras dengan pemeriksaan manual dibuat :

• jika ada tukang sihir, maka temukan tempat dari mana ia akan menimbulkan kerusakan maksimum;
• jika ada sekutu di tempat ini atau di sepanjang jalan serangan, ingatlah mereka;
• pertama, semua sekutu yang mereka ingat pergi dan mereka tidak dapat mengambil posisi yang disediakan oleh tukang sihir (yaitu, membersihkan jalan);
• tukang sihir itu berjalan;
• unit yang tersisa sedang berjalan.

Strategi ini mudah dijelaskan dalam kata-kata, tetapi itu keren untuk memprogramnya.

12) Kadang-kadang unit " melarikan diri ke semak-semak " tepat sebelum dimulainya permusuhan. { Kesulitan permainan # 120 }. Sebagai akibatnya, ketika pertukaran serangan dimulai, satu atau bahkan dua unit bisa terlalu jauh dari operasi militer dan tidak membantu sekutu. Jika ini terjadi, maka saya hampir dijamin untuk mengalahkan AI. Jika itu tidak terjadi, maka saya sering kalah. Saya menyingkirkan ini dengan memperkenalkan heuristik baru untuk mengevaluasi poin-poin strategi yang dihasilkan. Untuk setiap unit, dilakukan pemeriksaan:

1. Jika unit menyerang giliran ini, maka ia menerima +1500 poin.
2. Jika Anda tidak menyerang, maka posisi dihitung dari mana musuh dapat menimbulkan kerusakan pada sekutu. Lanjutkan menghitung jika ada lebih dari 0 posisi seperti itu (N> 0).
2.1. Jika suatu unit tidak dapat mencapai dan menyerang pada posisi apa pun (n = 0), maka ia menerima penalti -1000 poin.
2.2. Jika sebuah unit dapat mencapai semua posisi, maka ia mendapat +1200 poin.
2.3. Jika sebuah unit dapat menyerang hingga posisi tertentu, maka ia mendapat + (n / N) * 1000 poin.

Ini telah sangat meningkatkan "kohesi" unit AI. Sayangnya, kasus "satu pembelot" mulai muncul, ketika dalam situasi yang kalah salah satu unit yang terluka lebih suka bersembunyi di belakang punggung rekan-rekan mereka daripada berkontribusi dengan menyerang musuh. Itu tampak konyol ketika komputer hanya memiliki 2 unit yang tersisa, dan pemain memiliki 3 atau lebih. Heuristik korektif tambahan adalah aturan berikut:

IF ("   ,   " AND "    3 ") THEN "      " 

13) Pada akhir pengenalan strategi, mereka sudah mengumpulkan di bawah 25 buah. { Kesulitan permainan # 130 }.

Mutasi masing-masing telah menjadi terlalu mahal. Oleh karena itu, diputuskan untuk menghapus yang paling tidak berhasil dan hanya menyisakan 8 buah. Sejak awal, saya tidak ingin menggunakan pendekatan ini dengan harapan bahwa mutasi orang luar dapat menghasilkan hasil yang luar biasa, bukan hanya yang baik. Memasuki pemrosesan ini pada akhirnya menyebabkan peningkatan dalam game AI.

14) Sekitar awal masih ada revisi yang menarik. Awalnya, nilai skenario dihitung sebagai selisih jumlah poin:

 _ = _ - _ 

Tetapi setelah beberapa perbaikan, saya ingat bahwa ini bukan solusi terbaik, karena maka untuk AI, situasi "2 tentara versus 1 tentara tunggal" dan "4 tentara versus 3 tentara" akan sama. Oleh karena itu, poin mulai dihitung sebagai rasio:

 _ = _ / _ 

Perubahannya kecil, dan hasilnya sangat serius. Tanpa modifikasi, harga kesalahan dengan peningkatan risiko selalu sama. Setelah disempurnakan, AI mulai mengambil risiko dengan kurang ceroboh menjelang akhir pertempuran, dan ini secara nyata memperkuatnya.

Saya ingin mencatat bahwa semua peningkatan ini diperkenalkan secara bertahap, meskipun dalam urutan yang ditunjukkan, tetapi banyak dari mereka yang diperbaiki, diproses dan diperbaiki dari bug dalam urutan yang lebih kacau. Ada lebih dari 100 iterasi nyata.

Begini cara bermain AI terakhir { Kesulitan permainan # 9999 }:

AI berjalan segera, tidak membuang waktu untuk berpikir

Untuk mempercepat perhitungan sendiri, optimasi algoritma secara aktif digunakan dalam bentuk partisi loop bersarang menjadi loop berurutan ( mengurangi kompleksitas ) dan pengenalan beberapa array dengan perhitungan awal yang di-cache ( dan optimasi selanjutnya dari cache yang sangat ini ). Menurut perkiraan saya, optimasi lebih lanjut dapat memberi saya peningkatan ganda (atau bahkan lebih besar) dalam kecepatan, tetapi ini akan mengarah pada peningkatan yang tidak dapat dibenarkan dalam biaya waktu dan semakin hilangnya pembacaan kode yang lebih besar.

Teknologi utama kecepatan tinggi adalah perhitungan pendahuluan saat downtime. Metode ini terdiri dari memecah proses menjadi dua bagian: perhitungan sendiri dan animasi dari hasil perhitungan:

• perhitungan jalannya unit pertama dimulai segera setelah giliran pemain, sementara jendela terbang bahwa giliran lawan akan dimulai. Dan ini sebanyak 4 detik, yang pemain tidak anggap sebagai harapan kosong;
• perhitungan gerakan kedua dan selanjutnya dimulai ketika animasi jalannya unit terakhir hanya dimulai (yaitu, ketika kursor AI baru saja memulai gerakannya). Dan waktu semua animasi sudah 4,5 detik. Meskipun akan lebih tepat untuk menyebut ini bukan perhitungan langkah selanjutnya, tetapi perbaikan dari strategi masa lalu yang sudah dikembangkan dan pencarian yang baru, karena pada setiap iterasi, pergerakan seluruh tim dihitung;
• ketika menghidupkan AI bergerak ke unit yang bergerak, kursor AI terbang, yang berpura-pura mengkliknya. Kursor terbang secepat mungkin, tetapi agar kenyamanan untuk melacaknya tetap ada. Selain itu, menambahkan kursor tidak hanya diizinkan untuk meningkatkan margin waktu komputasi dari 2 detik menjadi 4,5, tetapi juga membuat melihat kemajuan komputer lebih nyaman bagi seseorang;
• waktu pergantian pemain juga tidak sia-sia. Selama pemain berpikir, hampir tidak ada perhitungan yang dibuat, jadi saat ini kemungkinan cache untuk pergerakan lawan komputer di masa depan dihitung secara intensif.

Untuk mencegah semua ini tertinggal di browser dan bekerja dengan FPS yang cukup stabil, perhitungan dilakukan secara serempak oleh pekerja (pekerja Web ) [ 11 ].

Dengan melakukan ini, saya ingin menyingkirkan jendela tunggu "Computer walks" yang mengganggu. Die yang tidak menyenangkan seperti itu ada di banyak game bagus, misalnya, di Xenonauts [ 12 ]. Saya percaya bahwa saya dapat mengatasi masalah ini.


Jadi, AI selalu menghabiskan waktu yang sama untuk memikirkan langkahnya - terlepas dari kerumitannya. Fitur yang sangat aneh dari pendekatan ini adalah bahwa semakin kuat pemain memiliki komputer, semakin banyak mutasi AI akan memiliki waktu untuk memilah-milah, dan karena itu akan semakin kuat, semakin kuat komputer pemain. Saya pertama kali menghapus efek ini dengan memperbaiki waktu berjalan dan pra-menghitung kecepatan komputer. Namun, kemudian saya menghapus fiksasi ini, karena pemilik komputer yang kuat, ini akan memungkinkan mereka untuk bertarung dengan komputer "mereka", daripada yang rata-rata.

Apa hasilnya dan apa kerugiannya

Dengan demikian, musuh komputer yang dihasilkan tahu bagaimana bertarung dengan layak dan memanfaatkan pengawasan pemain mana pun, dan tidak membuat terlalu banyak miliknya sendiri. Namun demikian, saya, mengetahui semua fitur karyanya, meskipun dengan ketegangan, tapi saya selalu mengalahkannya (dalam kondisi yang sama). Tapi saya ingin yang sebaliknya: bahkan mengetahui tentang fitur-fiturnya, hampir selalu kalah darinya. AI jauh dari ideal, karena seperangkat heuristik yang saya gunakan mengarah ke sinergis tumpang tindih "kesalahan persepsi saya" pada satu sama lain. Kesalahan ini adalah:

1. Ketidaksempurnaan dan ketidaklengkapan strategi saya sendiri, saya tidak tahu semua strategi terbaik, dan karena itu saya tidak dapat mengidentifikasi dan menerapkannya dalam permainan.
2. Kehilangan efisiensi (yang tidak begitu ideal) dari heuristik yang berhasil ketika mentransfernya ke kode program. Sebagai contoh, heuristik manusia saya: "Unit tetap dekat, tetapi tidak terlalu dekat untuk menghindari kerusakan ganda dari penyihir dan tidak terjebak dalam lorong yang sempit." Heuristik ini membantu saya mengalahkan AI, tetapi ketika saya mengajarkannya kepada lawan komputer saya, saya harus menerjemahkan deskripsi kualitatif menjadi algoritmik dengan perkiraan kuantitatif, dan di sini kehilangan data dimungkinkan.
3. Saling konflik antara heuristik. Ketika ada terlalu banyak heuristik, mereka secara bertahap mulai tumpang tindih. Sebagai akibatnya, amplifikasi tak terduga dapat terjadi karena penghitungan ganda tersembunyi atau duplikasi parsial. Atau semacam heuristik akan berhenti mempengaruhi apa pun, karena kontribusinya sepenuhnya diblokir oleh koefisien bersaing besar.
4. Kendala waktu yang ketat dan perbaikan langkah-demi-langkah dari strategi yang dipilih mengarah pada fakta bahwa langkah pertama akan selalu kurang dipikirkan. Ini berarti bahwa satu gerakan pertama yang gagal dapat memblokir gerakan yang jelas lebih efektif dari unit-unit tim yang tersisa. Ini diekspresikan dalam kenyataan bahwa F pejuang pertama alih-alih bergerak menjauh dapat dengan marah menyerang musuh dan kemudian penyihir sekutunya W harus melukai sendiri untuk menghabisi musuh.

Algoritma genetika lengkap, alih-alih “mencocokkan dengan mata,” kemungkinan besar akan memungkinkan untuk memilih koefisien yang lebih optimal dalam heuristik. Tapi ini sudah menjadi tugas untuk proyek penuh di masa depan - saya tidak ingin terjebak dengan prototipe untuk waktu yang lama. Saya cukup puas dengan AI saat ini: itu adalah bijaksana, sedikit berbahaya, cukup agresif dan tidak akan membiarkan pemain untuk mengalahkan dirinya sendiri kering ( pada kenyataannya, sangat jarang untuk memungkinkan ).

Fitur tambahan

Metode implementasi ini memungkinkan Anda untuk mencapai bonus tambahan dalam pengembangan game ( dalam banyak hal dari sudut pandang pengembang dan ketentuan-ketentuannya ):

1. Munculnya mekanik baru dalam permainan tidak akan menghancurkan kekuatan pemain komputer, meskipun secara bertahap akan melemahkannya dibandingkan dengan pemain. Pelemahan ini dapat dikompensasi dengan diperkenalkannya heuristik tambahan. Agar hal ini tidak mengarah pada pengeluaran sumber daya yang progresif, dimungkinkan untuk menerapkan heuristik baru ini hanya jika mekanik baru ini hadir dalam pertempuran saat ini.
2. Tingkat kesulitan yang sangat cerdas. Sekarang pada dasarnya tingkat kesulitan menentukan bonus apa yang akan diterima pemain komputer sebagai sumber daya ( lebih banyak emas di awal atau bonus dalam penambangan ) atau berapa banyak pasukannya yang akan dikalahkan ( + 50% untuk kerusakan ). Ini bekerja, tetapi Anda dapat membuat AI sedikit kurang pintar hanya dengan secara bertahap menonaktifkan beberapa heuristik saat kompleksitas berkurang.
3. Dalam kelanjutan paragraf kedua, Anda dapat membuat berbagai ras / faksi lawan komputer : hanya strategi agresif yang bekerja untuk orc; dalam kerumunan zombie, hanya primitif "berlari maju dan menyerang"; dan cyborg menggunakan kekuatan penuh AI. Berkat pemain ini sebelum serangan harus mengevaluasi tidak hanya jumlah lawan, tetapi juga kecerdasan mereka.

Semua ini terdengar menjanjikan, tetapi Anda harus ingat bahwa semua ini indah di atas kertas, dan dalam permainan nyata itu mungkin tidak berfungsi, ternyata tidak menarik atau bahkan tidak terlihat oleh pemain. Tapi ini alasan yang bagus untuk bereksperimen.

Tempat merasakan

Anda dapat menguji kekuatan AI ini di peramban taktis AI. Uji subjek "gratis di situs-situs seperti itch.io [ 13 ]. GET parameter ai (nilai 0 hingga 140 dalam langkah 10) akan mengurangi kompleksitas AI.

Menurut harapan saya, mengalahkan AI dengan syarat yang sama akan sangat, sangat sulit bagi Anda. Bahkan setelah terbiasa dengan aturan main. Saya sarankan mempertimbangkan game ini sebagai prototipe, yang intinya adalah (tidak ada musik, suara, dan harga di dalamnya ).

Silakan tinggalkan pendapat Anda di komentar tentang ketertarikan AI, tip dan kritik tentang kemungkinan penerapan AI menggunakan berbagai metode pengajaran. Jika Anda tiba-tiba tertarik pada penelitian saya yang lain, silakan pertimbangkan untuk berlangganan di sini ke akun saya.

Referensi

1. DeepMind - artikel tentang Habré .
2. Game HTML5: Kanvas vs. SVG vs. div pada stackoverflow .
3. Ledakan kombinasi - Wikipedia .
4. Kode Steve McConnell yang sempurna adalah Habr .
5. Metode heuristik - Wikipedia .
6. A * - Game Red Blob .
7. Algoritma genetik. Hanya tentang yang sulit - Habr .
8. Delapan game luar biasa dengan kecerdasan buatan dari perusahaan Google - Habr .
9. Sangat singkat tentang Suvorov dan Kutuzov .
10. Master of Monsters - Disciples of Gaia - Tinjauan di IGN .
11. Penjelasan terperinci tentang Loop dan Waktu Game JavaScript .
12. Xenonauts dan layar siaga AI yang panjang .
13. AI taktis gemuruh. Subjek uji - pada gatal.