Pendahuluan

Artikel ini akan memperkenalkan Anda pada berbagai konsep kecerdasan buatan dalam game (“game AI”), sehingga Anda memahami alat apa yang dapat digunakan untuk menyelesaikan masalah AI, bagaimana mereka bekerja bersama dan bagaimana memulai implementasinya di mesin yang dipilih.

Saya akan berasumsi bahwa Anda terbiasa dengan permainan video, sedikit berpengalaman dalam konsep matematika seperti geometri, trigonometri, dll. Sebagian besar contoh kode akan ditulis dalam pseudo-code, jadi Anda tidak perlu tahu bahasa tertentu.

Apa itu "game AI"?

Game AI terutama berkaitan dengan pemilihan tindakan suatu entitas tergantung pada kondisi saat ini. Dalam literatur AI tradisional, ini disebut manajemen " agen cerdas ." Agen biasanya merupakan karakter dalam permainan, tetapi dapat berupa mesin, robot, atau bahkan sesuatu yang lebih abstrak - seluruh kelompok entitas, negara, atau peradaban. Bagaimanapun, itu adalah objek yang memonitor sekitarnya, membuat keputusan berdasarkan itu, dan bertindak sesuai dengan keputusan ini. Ini kadang-kadang disebut siklus tindakan persepsi-berpikir (Sense / Think / Act):

• Persepsi: agen mengakui - atau diberitahu tentang hal itu - informasi tentang lingkungan yang dapat memengaruhi perilakunya (misalnya, bahaya terdekat, barang yang dikumpulkan, poin penting, dan sebagainya)
• Berpikir: agen memutuskan bagaimana merespons (misalnya, memutuskan apakah aman untuk mengumpulkan barang, apakah ia harus bertarung, atau lebih baik bersembunyi terlebih dahulu)
• Tindakan: agen melakukan tindakan untuk mengimplementasikan keputusannya (misalnya, mulai bergerak di sepanjang rute ke musuh atau ke subjek, dan sebagainya)
• ... kemudian, karena aksi karakter, situasinya berubah, sehingga siklus harus diulang dengan data baru.

Tugas AI dunia nyata, terutama yang relevan saat ini, biasanya fokus pada "persepsi." Sebagai contoh, kendaraan tak berawak harus menerima gambar jalan di depannya, menggabungkannya dengan data lain (radar dan lidar) dan mencoba menafsirkan apa yang mereka lihat. Biasanya tugas ini diselesaikan dengan pembelajaran mesin, yang bekerja sangat baik dengan array besar data bising dunia nyata (misalnya, dengan foto-foto jalan di depan mobil atau beberapa frame video) dan memberi mereka beberapa makna, mengekstraksi informasi semantik, misalnya, “ada 20 meter di depan saya mobil lain. " Tugas semacam itu disebut masalah klasifikasi .

Permainan tidak biasa karena mereka tidak memerlukan sistem yang rumit untuk mengekstraksi informasi ini, karena ini merupakan bagian integral dari simulasi. Tidak perlu melakukan algoritma pengenalan gambar untuk mendeteksi musuh di depan Anda; permainan tahu bahwa ada musuh dan dapat mengirimkan informasi ini langsung ke proses pengambilan keputusan. Oleh karena itu, "persepsi" dalam siklus ini biasanya sangat disederhanakan, dan semua kompleksitas muncul dalam implementasi "berpikir" dan "tindakan".

Keterbatasan Pengembangan Game AI

Game AI biasanya memperhitungkan batasan berikut:

• Berbeda dengan algoritma pembelajaran mesin, biasanya tidak melatih di muka; ketika mengembangkan permainan, tidak praktis untuk menulis jaringan saraf untuk memantau puluhan ribu pemain untuk menemukan cara terbaik untuk bermain melawan mereka, karena permainan belum dirilis dan tidak memiliki pemain!
• Biasanya diasumsikan bahwa permainan harus menghibur dan menantang pemain, dan tidak menjadi "optimal" - karena itu, bahkan jika Anda dapat melatih agen untuk melawan pemain dengan cara terbaik, maka paling sering desainer membutuhkan sesuatu yang berbeda dari mereka.
• Seringkali agen diharuskan untuk memiliki perilaku "realistis" agar pemain merasa bahwa mereka bersaing dengan lawan seperti manusia. Program AlphaGo ternyata jauh lebih baik daripada orang-orang, tetapi gerakan yang dipilihnya jauh dari pemahaman tradisional tentang permainan yang lawan-lawannya alami katakan sebagai permainan melawan alien. Jika permainan berpura-pura menjadi lawan manusia, maka ini biasanya tidak diinginkan, sehingga algoritma perlu diatur sehingga membuat keputusan yang masuk akal , bukan yang ideal .
• AI harus dijalankan secara real time. Dalam konteks ini, ini berarti bahwa algoritma tidak dapat, untuk suatu keputusan, memonopoli sumber daya prosesor untuk waktu yang lama. Bahkan 10 milidetik untuk mengambil keputusan terlalu banyak, karena sebagian besar permainan hanya memiliki 16-33 milidetik untuk menyelesaikan semua operasi untuk kerangka grafik berikutnya.
• Idealnya, setidaknya bagian dari sistem harus bergantung pada data, dan tidak dikodekan sedemikian rupa sehingga yang bukan pemrogram dapat membuat perubahan lebih cepat.

Setelah mempelajari semua ini, kita dapat mulai mempertimbangkan pendekatan yang sangat sederhana untuk penciptaan AI, yang menerapkan seluruh siklus "tindakan berpikir-persepsi" dengan cara yang memastikan efisiensi dan memungkinkan perancang permainan untuk memilih perilaku rumit yang mirip dengan tindakan manusia.

Pengambilan keputusan mudah

Mari kita mulai dengan gim yang sangat sederhana, seperti Pong. Tugas pemain adalah menggerakkan "raket" sehingga bola memantul darinya, alih-alih terbang melewati. Aturannya mirip dengan tenis - Anda kalah jika Anda melewatkan bola. AI memiliki tugas yang relatif sederhana untuk membuat keputusan tentang memilih arah gerakan raket.

Konstruksi bersyarat hard-coded

Jika kita ingin menulis AI untuk mengendalikan raket, maka ada solusi intuitif dan sederhana - terus-menerus menggerakkan raket sehingga berada di bawah bola. Ketika bola mencapai raket, itu sudah dalam posisi sempurna dan bisa mengenai itu.

Algoritma sederhana untuk ini, dinyatakan dalam pseudo-code, dapat berupa:

  di setiap frame / perbarui saat game sedang berjalan:

 jika bola ada di sebelah kiri raket:

	 gerakkan raket ke kiri

 sebaliknya jika bola ada di kanan raket:

	 gerakkan raket ke kanan 

Jika kita mengasumsikan bahwa raket dapat bergerak dengan kecepatan tidak kurang dari bola, maka ini akan menjadi algoritma yang sempurna untuk pemain AI di Pong. Dalam kasus di mana tidak ada begitu banyak "persepsi" data untuk diproses dan beberapa tindakan yang dapat dilakukan agen, kita tidak perlu sesuatu yang lebih rumit.

Pendekatan ini sangat sederhana sehingga hampir tidak menunjukkan seluruh siklus "tindakan berpikir-persepsi." Tapi dia.

• Persepsi adalah dua jika pernyataan. Permainan tahu di mana bola dan raket berada. Oleh karena itu, AI meminta permainan untuk posisi mereka, sehingga "merasa" apakah bola ada di sebelah kiri atau kanan.
• Berpikir juga dibangun menjadi dua jika pernyataan. Mereka berisi dua solusi, yang dalam hal ini saling eksklusif, mengarah ke pilihan salah satu dari tiga tindakan - pindahkan raket ke kiri, pindahkan ke kanan atau tidak lakukan apa-apa jika raket sudah berada dengan benar.
• "Aksi" adalah "memindahkan raket ke kiri" atau "memindahkan raket ke kanan". Bergantung pada bagaimana permainan diimplementasikan, ini dapat berupa bergerak instan posisi raket atau mengatur kecepatan dan arah raket sehingga dapat digeser dengan benar dalam kode permainan lain.

Pendekatan semacam itu sering disebut "reaktif" karena ada seperangkat aturan sederhana (dalam kasus kami, ini adalah pernyataan "jika" dalam kode) yang merespons keadaan dunia dan langsung memutuskan bagaimana untuk melanjutkan.

Pohon keputusan

Contoh Pong ini sebenarnya mirip dengan konsep AI formal yang disebut pohon keputusan . Ini adalah sistem di mana keputusan disusun dalam bentuk pohon dan algoritma harus mengitarinya untuk mencapai "lembar" yang berisi keputusan akhir tentang tindakan yang dipilih. Mari kita menggambar representasi grafis dari pohon keputusan untuk algoritma raket Pong menggunakan diagram alur:


Dapat dilihat bahwa itu menyerupai pohon, hanya terbalik!

Setiap bagian dari pohon keputusan biasanya disebut "simpul" karena dalam AI, teori grafik digunakan untuk menggambarkan struktur tersebut. Setiap node dapat menjadi salah satu dari dua jenis:

1. Node solusi: pilihan dua alternatif berdasarkan verifikasi suatu kondisi. Setiap alternatif disajikan sebagai simpulnya sendiri;
2. End nodes: Suatu tindakan yang dilakukan yang mewakili keputusan akhir yang dibuat oleh pohon.

Algoritme dimulai dari simpul pertama yang ditetapkan oleh "root" dari pohon, setelah itu ia memutuskan simpul anak mana yang akan dituju berdasarkan kondisi, atau melakukan tindakan yang disimpan dalam simpul, dan kemudian berhenti bekerja.

Pada pandangan pertama, keuntungan dari pohon keputusan tidak jelas, karena ia melakukan pekerjaan yang persis sama dengan pernyataan if dari bagian sebelumnya. Tetapi ada sistem yang sangat umum di mana setiap solusi memiliki tepat 1 kondisi dan 2 hasil yang memungkinkan, yang memungkinkan pengembang untuk membangun AI dari data yang mewakili solusi di pohon, dan menghindari menulis dengan keras dalam kode. Sangat mudah untuk membayangkan format data sederhana untuk menggambarkan pohon seperti itu:

Nomor node	Keputusan (atau "akhir")	Aksi	Aksi
1	Bola di sebelah kiri raket?	Hah? Periksa Node 2	Tidak Periksa Node 3
2	Akhirnya	Gerakkan raket ke kiri
3	Bola di sebelah kanan raket?	Hah? Pergi ke simpul 4	Tidak Pergi ke simpul 5
4	Akhirnya	Pindahkan raket ke kanan
5	Akhirnya	Jangan lakukan apa pun

Dari sudut pandang kode, kita perlu memaksa sistem untuk membaca setiap baris ini, membuat untuk setiap node, melampirkan logika keputusan berdasarkan kolom kedua dan melampirkan node anak berdasarkan kolom ketiga dan keempat. Kita masih perlu secara manual mendefinisikan kondisi dan tindakan, tetapi sekarang kita bisa membayangkan permainan yang lebih kompleks di mana Anda dapat menambahkan solusi dan tindakan baru, serta mengkonfigurasi seluruh AI dengan mengubah satu-satunya file teks yang berisi definisi pohon. Kami dapat mentransfer file ke desainer game, yang akan dapat menyesuaikan perilaku tanpa perlu mengkompilasi ulang game dan mengubah kode - asalkan kode tersebut sudah memiliki kondisi dan tindakan yang bermanfaat.

Pohon keputusan dapat sangat kuat ketika mereka dibangun secara otomatis berdasarkan sejumlah besar contoh (misalnya, menggunakan algoritma ID3 ). Itu membuat mereka alat yang efektif dan berkinerja tinggi untuk mengklasifikasikan situasi berdasarkan data yang masuk, tetapi topik ini berada di luar cakupan desainer untuk menciptakan sistem sederhana untuk memilih tindakan untuk agen.

Scripting

Di atas, kami memeriksa sistem pohon keputusan yang menggunakan kondisi dan tindakan yang telah dibuat sebelumnya. Pengembang AI dapat membangun kembali pohon dengan cara apa pun yang dia butuhkan, tetapi dia harus mengandalkan fakta bahwa programmer telah menciptakan semua kondisi dan tindakan yang diperlukan untuknya. Tetapi bagaimana jika kita memberi perancang alat yang lebih kuat yang memungkinkan dia untuk membuat kondisinya sendiri, dan mungkin tindakannya?

Misalnya, alih-alih memaksa pembuat enkode untuk menulis kondisi "Bola di sebelah kiri raket?" dan “Bola di sebelah kanan raket?”, ia dapat dengan mudah membuat sistem di mana perancang secara independen menulis kondisi untuk memeriksa nilai-nilai ini. Akibatnya, data pohon keputusan mungkin terlihat seperti ini:

Nomor node	Keputusan (atau "akhir")	Solusi	Aksi
1	ball.position.x <paddle.position.x	Hah? Periksa Node 2	Tidak Periksa Node 3
2	Akhirnya	Gerakkan raket ke kiri
3	ball.position.x> paddle.position.x	Hah? Periksa Node 4	Tidak Periksa Node 5
4	Akhirnya	Pindahkan raket ke kanan
5	Akhirnya	Jangan lakukan apa pun

Sama seperti sebelumnya, tetapi sekarang solusinya memiliki kode sendiri, mirip dengan bagian kondisional dari pernyataan if. Kode akan membaca node keputusan dari kolom kedua dan bukannya mencari kondisi tertentu (misalnya, "bola di sebelah kiri raket?"), Hitung ekspresi kondisional dan kembalikan benar atau salah. Ini dapat diimplementasikan dengan menanamkan bahasa scripting , seperti Lua atau Angelscript, yang memungkinkan pengembang untuk mengambil objek dari permainan (misalnya, bola dan raket) dan membuat variabel yang dapat diakses dari skrip (misalnya posisi ball.position). Biasanya lebih mudah untuk menulis dalam bahasa scripting daripada di C ++, dan tidak memerlukan tahap kompilasi yang lengkap, oleh karena itu sangat cocok untuk membuat perubahan cepat ke logika permainan dan memungkinkan anggota tim yang kurang mengerti secara teknis untuk membuat fungsi-fungsi permainan tanpa campur tangan pembuat enkode.

Dalam contoh di atas, bahasa skrip hanya digunakan untuk mengevaluasi ekspresi kondisional, tetapi tindakan akhir juga dapat dijelaskan dalam skrip. Misalnya, tindakan ini dari jenis "pindahkan raket ke kanan" dapat menjadi skrip konstruksi seperti ball.position.x += 10 , yaitu, tindakan juga diatur dalam skrip tanpa menulis kode fungsi MovePaddleRight.

Jika Anda mengambil langkah maju, Anda dapat (dan ini sering dilakukan) pergi ke kesimpulan logis dan menulis seluruh pohon keputusan dalam bahasa scripting, dan bukan sebagai daftar baris data. Ini akan menjadi kode yang mirip dengan konstruksi kondisional yang ditunjukkan di atas, hanya saja mereka bukan "hard-coded" - mereka berada dalam file skrip eksternal, yaitu, mereka dapat diubah tanpa mengkompilasi ulang seluruh program. Bahkan seringkali dimungkinkan untuk memodifikasi file skrip selama eksekusi game, yang memungkinkan pengembang untuk dengan cepat menguji berbagai pendekatan untuk implementasi AI.

Reaksi terhadap berbagai peristiwa

Contoh-contoh yang ditunjukkan di atas dimaksudkan untuk eksekusi satu frame dalam game sederhana seperti Pong. Idenya adalah bahwa mereka terus melakukan siklus "tindakan berpikir-persepsi" dan terus bertindak atas dasar keadaan terakhir di dunia. Namun dalam game yang lebih kompleks, alih-alih komputasi, seringkali lebih masuk akal untuk bereaksi terhadap "peristiwa", yaitu, terhadap perubahan penting di lingkungan game.

Ini tidak berlaku untuk Pong, jadi mari kita pilih contoh lain. Bayangkan sebuah permainan penembak di mana musuh tidak bergerak sampai mereka menemukan pemain, setelah itu mereka mulai melakukan tindakan tergantung pada kelas mereka - pejuang jarak dekat dapat bergegas menuju pemain, dan penembak jitu tetap berada di kejauhan dan mencoba membidik. Pada dasarnya, ini adalah sistem reaktif sederhana - "jika kita melihat pemain, maka kita melakukan sesuatu" - tetapi itu dapat secara logis dibagi menjadi suatu peristiwa ("melihat pemain") dan reaksi (pilih respons dan jalankan itu).

Ini membawa kita kembali ke siklus persepsi-berpikir-tindakan. Kami mungkin memiliki fragmen kode, yang merupakan kode "persepsi", yang memeriksa di setiap frame apakah musuh melihat pemain. Jika tidak, maka tidak ada yang terjadi. Tetapi jika dia melihat, ini menciptakan sebuah acara "melihat pemain". Kode akan memiliki bagian terpisah, yang mengatakan: "ketika acara" melihat pemain "terjadi, maka kita melakukan" xyz ", dan" xyz "adalah respons apa pun yang kita inginkan untuk memproses pemikiran dan tindakan. Untuk petarung karakter, Anda dapat menghubungkan respons lari dan serang ke acara "lihat pemain". Untuk sniper, kami akan menghubungkan fungsi respons "sembunyikan dan arahkan" ke acara ini. Seperti dalam contoh sebelumnya, kita dapat membuat asosiasi seperti itu di file data sehingga mereka dapat dengan cepat diubah tanpa membangun kembali mesin. Selain itu, dimungkinkan (dan ini sering digunakan) untuk menulis fungsi respons seperti itu dalam bahasa scripting sehingga mereka dapat membuat solusi yang kompleks ketika peristiwa terjadi.

Pengambilan Keputusan yang Lebih Baik

Meskipun sistem reaktif sederhana sangat kuat, ada banyak situasi di mana mereka tidak cukup. Kadang-kadang kita perlu membuat keputusan berbeda berdasarkan apa yang dilakukan agen saat ini, dan menyajikannya sebagai suatu kondisi yang tidak nyaman. Kadang-kadang ada terlalu banyak kondisi untuk menyajikannya secara efektif dalam bentuk pohon keputusan atau naskah. Terkadang kita perlu berpikir terlebih dahulu dan mengevaluasi bagaimana situasi akan berubah sebelum memutuskan langkah selanjutnya. Untuk tugas seperti itu dibutuhkan solusi yang lebih kompleks.

Mesin negara

Finite state machine (FSM) adalah cara untuk mengatakan dengan kata lain bahwa beberapa objek - katakanlah, salah satu agen AI kami - saat ini berada di salah satu dari beberapa kemungkinan keadaan, dan bahwa ia dapat pergi satu negara ke negara lain. Ada sejumlah negara seperti itu, maka nama itu. Contoh dari dunia nyata adalah seperangkat lampu lalu lintas, beralih dari merah ke kuning, lalu ke hijau, dan kembali lagi. Di tempat yang berbeda ada urutan cahaya yang berbeda, tetapi prinsipnya sama - setiap negara berarti sesuatu ("berdiri," "makan," "berdiri, jika mungkin," dll.), Pada waktu tertentu hanya ada satu negara, dan transisi di antara mereka didasarkan pada aturan sederhana.

Ini berlaku baik untuk NPC di game. Penjaga mungkin memiliki status yang dipisahkan dengan jelas berikut ini:

• Patroli
• Penyerangan
• Penerbangan

Dan kita bisa membuat aturan berikut untuk transisi antar negara:

• Jika penjaga melihat musuh, dia menyerang
• Jika penjaga menyerang, tetapi tidak lagi melihat musuh, ia kembali berpatroli
• Jika seorang penjaga menyerang tetapi terluka parah, ia melarikan diri

Skema ini cukup sederhana dan kita dapat menuliskannya dengan operator “jika” yang didefinisikan dengan ketat dan variabel di mana keadaan penjaga keamanan dan berbagai pemeriksaan akan disimpan - kehadiran musuh di dekatnya, tingkat kesehatan penjaga keamanan, dll. Tetapi bayangkan kita perlu menambahkan beberapa status lagi:

• Menunggu (antara patroli)
• Cari (ketika musuh yang sebelumnya terlihat bersembunyi)
• Melarikan diri untuk membantu (ketika musuh terlihat, tetapi dia terlalu kuat untuk bertarung sendirian dengannya)

Dan pilihan yang tersedia di setiap negara biasanya terbatas - misalnya, seorang penjaga mungkin tidak ingin mencari musuh yang telah kehilangan pandangan jika kesehatannya terlalu rendah.

Cepat atau lambat, daftar panjang "jika <x dan y tetapi tidak z> maka <p>" menjadi terlalu canggung, dan pendekatan formal untuk implementasi negara dan transisi di antara mereka dapat membantu di sini. Untuk melakukan ini, kami mempertimbangkan semua negara bagian dan di bawah setiap negara bagian kami mendaftar semua transisi ke negara bagian lain bersama dengan kondisi yang diperlukan untuk mereka. Kita juga perlu menunjukkan keadaan awal sehingga kita tahu harus mulai dari mana sebelum menerapkan kondisi lain.

Ketentuan	Kondisi transisi	Kondisi baru
Menunggu	diharapkan selama 10 detik	Patroli
	musuh terlihat dan musuh terlalu kuat	Cari bantuan
	musuh terlihat dan banyak kesehatan	Penyerangan
	musuh terlihat dan sedikit kesehatan	Penerbangan
Patroli	rute patroli selesai	Menunggu
	musuh terlihat dan musuh terlalu kuat	Cari bantuan
	musuh terlihat dan banyak kesehatan	Penyerangan
	musuh terlihat dan sedikit kesehatan	Penerbangan
Penyerangan	musuh tidak terlihat	Menunggu
	sedikit kesehatan	Penerbangan
Penerbangan	musuh tidak terlihat	Menunggu
Cari	mencari 10 detik	Menunggu
	musuh terlihat dan musuh terlalu kuat	Cari bantuan
	musuh terlihat dan banyak kesehatan	Penyerangan
	musuh terlihat dan sedikit kesehatan	Penerbangan
Cari bantuan	teman lihat	Penyerangan
Status awal: menunggu

Skema seperti itu disebut tabel transisi negara. Ini adalah cara yang kompleks (dan tidak menarik) untuk mewakili pesawat ruang angkasa. Dari data ini, Anda juga dapat menggambar diagram dan mendapatkan representasi grafis yang kompleks tentang bagaimana perilaku NPC.


Ini menangkap esensi dari membuat keputusan untuk agen berdasarkan situasi di mana dia berada. Setiap panah menunjukkan transisi antar negara jika kondisi di sebelah panah itu benar.

Dengan setiap pembaruan (atau "siklus"), kami memeriksa status agen saat ini, lihat daftar transisi, dan jika kondisi transisi terpenuhi, maka lanjutkan ke status baru. Status Tertunda memeriksa di setiap frame atau siklus apakah timer 10 detik telah kedaluwarsa. Jika kedaluwarsa, ia memulai transisi ke status "Patroli". Demikian pula, kondisi "Serangan" memeriksa apakah agen memiliki banyak kesehatan, dan jika demikian, itu membuat transisi ke status "Penerbangan".

Ini adalah bagaimana transisi negara ditangani - tetapi bagaimana dengan perilaku yang terkait dengan negara itu sendiri? Dari sudut pandang melakukan tindakan sendiri untuk suatu negara, biasanya ada dua jenis tindakan melampirkan ke pesawat ruang angkasa:

1. Tindakan untuk kondisi saat ini dilakukan secara berkala, misalnya, di setiap frame atau "siklus".
2. Tindakan dilakukan selama transisi dari satu kondisi ke kondisi lainnya.

Contoh dari tipe pertama: status "Patroli" di setiap frame atau siklus terus memindahkan agen di sepanjang rute patroli. Status "Serang" di setiap frame atau siklus mencoba meluncurkan serangan atau memindahkannya ke posisi dari mana dimungkinkan. Dan sebagainya.

Contoh dari tipe kedua: pertimbangkan transisi "jika musuh terlihat dan musuh terlalu kuat → Cari bantuan." Agen harus memilih ke mana harus pindah untuk mencari bantuan, dan menyimpan informasi ini sehingga negara bagian "Bantuan Pencarian" tahu ke mana harus pergi. Demikian pula, dalam kondisi "Pencarian Pencarian", ketika bantuan ditemukan, agen kembali ke status "Serangan", tetapi pada saat ini ia ingin memberi tahu karakter ramah tentang ancaman tersebut, sehingga mungkin ada tindakan "beri tahu teman tentang bahaya" yang dilakukan selama transisi ini.

Dan di sini kita kembali dapat mempertimbangkan sistem ini dari sudut pandang "tindakan berpikir-persepsi". Persepsi tertanam dalam data yang digunakan oleh logika transisi. Berpikir dibangun ke dalam transisi yang tersedia untuk setiap negara. Dan tindakan tersebut dilakukan oleh tindakan yang dilakukan secara berkala dalam suatu negara atau selama transisi antar negara.

Sistem sederhana ini bekerja dengan baik, meskipun terkadang kondisi pemungutan suara yang terus menerus dapat menjadi proses yang mahal. Misalnya, jika masing-masing agen perlu melakukan perhitungan yang rumit di setiap bingkai untuk menentukan visibilitas musuh dan memutuskan transisi dari patroli ke serangan, maka ini bisa memakan banyak waktu prosesor. Seperti yang kita lihat sebelumnya, adalah mungkin untuk melihat perubahan penting dalam keadaan dunia sebagai "peristiwa" yang diproses setelah terjadi. Oleh karena itu, alih-alih secara eksplisit memeriksa kondisi transisi "dapatkah agen saya melihat pemain?" Di setiap bingkai, kita dapat membuat sistem visibilitas terpisah yang melakukan pemeriksaan ini sedikit lebih jarang (misalnya, 5 kali per detik) dan menciptakan "pemain lihat ”ketika tes dipicu. Ini dikirim ke mesin negara, yang sekarang memiliki kondisi untuk transisi "Menerima acara" pemain melihat "", dan yang merespons sesuai. Perilaku yang dihasilkan akan serupa, dengan pengecualian dari keterlambatan reaksi yang hampir tidak terlihat (dan bahkan meningkatkan realisme), tetapi produktivitas akan meningkat karena pemindahan "persepsi" ke bagian terpisah dari program.

Mesin negara hirarkis

Semua ini bagus, tetapi dengan mesin-mesin negara besar itu menjadi sangat tidak nyaman untuk bekerja. Jika kita ingin memperluas status "Serangan" dengan menggantinya dengan status "Serangan jarak dekat" dan "Serangan dari jauh" yang terpisah, maka kita harus mengubah transisi yang masuk dari setiap negara, sekarang dan masa depan, yang membutuhkan kemampuan untuk beralih ke status "Serangan".

Anda mungkin juga memperhatikan bahwa dalam contoh kami ada banyak transisi duplikat. Sebagian besar transisi di negara bagian "Tertunda" identik dengan transisi di negara bagian "Patroli", dan alangkah baiknya untuk menghindari duplikasi karya ini, terutama jika kita ingin menambahkan lebih banyak lagi keadaan serupa. Adalah logis untuk menggabungkan "Menunggu" dan "Patroli" ke dalam beberapa kelompok "Negara-negara non-tempur", yang hanya memiliki satu set transisi umum ke negara-negara tempur. Jika kami menampilkan grup ini sebagai negara, kami dapat mempertimbangkan "Menunggu" dan "Patroli" sebagai "substate" dari negara ini, yang akan memungkinkan kami untuk secara lebih efektif menggambarkan keseluruhan sistem. Contoh menggunakan tabel konversi terpisah untuk substrat non-tempur baru:

Kondisi utama:

Ketentuan	Kondisi transisi	Kondisi baru
Non-tempur	musuh terlihat dan musuh terlalu kuat	Cari bantuan
	musuh terlihat dan banyak kesehatan	Penyerangan
	musuh terlihat dan sedikit kesehatan	Penerbangan
Penyerangan	musuh tidak terlihat	Non-tempur
	sedikit kesehatan	Penerbangan
Penerbangan	musuh tidak terlihat	Non-tempur
Cari	mencari 10 detik	Non-tempur
	musuh terlihat dan musuh terlalu kuat	Cari bantuan
	musuh terlihat dan banyak kesehatan	Penyerangan
	musuh terlihat dan sedikit kesehatan	Penerbangan
Cari bantuan	teman lihat	Penyerangan
Status awal: non-tempur

Status non-tempur:

Ketentuan	Kondisi transisi	Kondisi baru
Menunggu	diharapkan selama 10 detik	Patroli
Patroli	menyelesaikan rute patroli	Menunggu
Status awal: menunggu

Dan dalam bentuk grafik:


Sebenarnya, ini adalah sistem yang sama, hanya sekarang ada negara non-tempur yang menggantikan "Patroli" dan "Menunggu", yang dengan sendirinya adalah mesin negara dengan dua gardu patroli dan menunggu. Jika setiap negara berpotensi berisi mesin negara substate (dan substate ini juga dapat berisi mesin negara sendiri, dan seterusnya), maka kita memiliki mesin keadaan hierarkis (HFSM). Dengan mengelompokkan perilaku non-tempur, kami memotong banyak transisi yang tidak perlu, dan kami dapat melakukan hal yang sama untuk setiap negara baru yang mungkin memiliki transisi yang sama. Misalnya, jika di masa depan kami memperluas status "Serangan" ke "Serangan jarak dekat" dan "Serangan proyektil", mereka dapat menjadi substate, transisi yang didasarkan pada jarak ke musuh dan keberadaan amunisi, yang memiliki transisi keluar umum berdasarkan tingkat kesehatan dan hal-hal lain. Dengan demikian, dengan minimal duplikasi transisi, perilaku kompleks dan sub-perilaku dapat diwakili.

Pohon perilaku

Dengan HFSM, kami mendapatkan kemampuan untuk membuat serangkaian perilaku yang cukup rumit dengan cara yang agak intuitif. Namun, segera terlihat bahwa pengambilan keputusan dalam bentuk aturan transisi terkait erat dengan keadaan saat ini. Banyak game hanya membutuhkan itu. Dan penggunaan hati-hati dari hierarki negara mengurangi jumlah transisi duplikat. Tetapi kadang-kadang kita membutuhkan aturan yang berlaku terlepas dari keadaan saat ini, atau berlaku di hampir semua negara. Misalnya, jika kesehatan agen telah turun hingga 25%, ia mungkin ingin melarikan diri, terlepas dari apakah ia sedang bertempur, atau sedang menunggu, atau berbicara, atau berada di negara bagian lain. Kami tidak ingin mengingat bahwa kami perlu menambahkan kondisi ini ke setiap status yang dapat kami tambahkan ke karakter di masa mendatang. Jadi ketika perancang nanti mengatakan bahwa dia ingin mengubah nilai ambang batas dari 25% menjadi 10%, kita tidak perlu memilah dan mengubah setiap transisi yang sesuai.

Ideal dalam situasi seperti itu adalah sistem di mana keputusan tentang negara mana yang akan ada secara terpisah dari negara itu sendiri, sehingga kita dapat mengubah hanya satu elemen, dan transisi masih diproses dengan benar. Di sinilah pohon perilaku berguna.

Ada beberapa cara untuk menerapkan pohon perilaku, tetapi esensinya sama untuk sebagian besar dan sangat mirip dengan pohon keputusan yang disebutkan di atas: algoritma mulai bekerja dari "simpul akar", dan ada simpul di pohon yang menunjukkan keputusan atau tindakan. Namun, ada perbedaan utama:

• Node sekarang mengembalikan salah satu dari tiga nilai: "berhasil" (jika pekerjaan selesai), "tidak berhasil" (jika pekerjaan itu tidak selesai), atau "dilakukan" (jika pekerjaan masih diselesaikan dan tidak sepenuhnya berhasil atau gagal).
• Sekarang kita tidak memiliki simpul keputusan di mana kita memilih dari dua alternatif, tetapi ada simpul dekorator dengan satu simpul anak. Jika mereka "berhasil," maka mereka mengeksekusi simpul anak mereka satu-satunya. Node dekorator sering berisi kondisi yang menentukan apakah eksekusi berakhir dengan sukses (yang berarti Anda perlu menjalankan subtree mereka) atau kegagalan (maka tidak ada yang perlu dilakukan). Mereka juga dapat kembali "dalam proses."
• Melakukan node tindakan mengembalikan nilai "berjalan" untuk menunjukkan apa yang terjadi.

Satu set kecil node dapat digabungkan, menciptakan sejumlah besar perilaku kompleks, dan seringkali skema ini sangat singkat. Sebagai contoh, kita dapat menulis ulang CA hirarkis penjaga dari contoh sebelumnya dalam bentuk pohon perilaku:


Ketika menggunakan struktur ini, tidak perlu untuk transisi eksplisit dari status “Waiting” atau “Patrol” ke status “Attack” atau yang lainnya - jika pohon dilintasi dari atas ke bawah dan dari kiri ke kanan, keputusan yang tepat dibuat berdasarkan situasi saat ini. Jika musuh terlihat dan karakter memiliki sedikit kesehatan, maka pohon akan menyelesaikan proses pada simpul "Penerbangan", terlepas dari simpul yang telah diselesaikan sebelumnya ("Patroli", "Menunggu", "Menyerang", dll.).

Anda mungkin memperhatikan bahwa kami belum memiliki transisi untuk kembali ke status "Menunggu" dari "Patroli" - dan di sini dekorator tanpa syarat akan berguna. Node dekorator standar adalah "Ulangi" - tidak memiliki kondisi, itu hanya memotong simpul anak yang mengembalikan "berhasil" dan menjalankan simpul anak lagi, mengembalikan "dieksekusi". Pohon baru terlihat seperti ini:


Pohon perilaku cukup kompleks karena seringkali ada banyak cara berbeda untuk membuat pohon, dan menemukan kombinasi yang tepat dari dekorator dan komponen komponen dapat menjadi tugas yang menakutkan. Ada juga masalah dengan seberapa sering kita perlu memeriksa pohon (apakah kita ingin melintasi setiap frame atau ketika sesuatu terjadi yang dapat mempengaruhi kondisi?) Dan bagaimana menyimpan keadaan relatif terhadap node (bagaimana kita tahu bahwa kita menunggu 10 detik? Bagaimana akankah kita mengetahui berapa banyak node yang terakhir dieksekusi untuk menyelesaikan urutan dengan benar?) Oleh karena itu, ada banyak implementasi yang berbeda. Misalnya, pada beberapa sistem, seperti sistem pohon perilaku Unreal Engine 4, simpul dekorator diganti dengan dekorator string yang memeriksa pohon hanya ketika kondisi dekorator berubah dan menyediakan "layanan",yang dapat terhubung ke node dan memberikan pembaruan berkala bahkan ketika pohon tidak diperiksa lagi. Pohon perilaku adalah alat yang kuat, tetapi mempelajari cara menggunakannya dengan benar, terutama dengan begitu banyak implementasi yang berbeda, bisa menjadi tugas yang menakutkan.

Sistem Berbasis Utilitas

Beberapa permainan memerlukan adanya berbagai tindakan, sehingga mereka memerlukan aturan transisi yang lebih sederhana dan tersentralisasi, tetapi mereka tidak membutuhkan kekuatan untuk sepenuhnya mengimplementasikan pohon perilaku. Daripada membuat set pilihan atau pohon tindakan potensial secara eksplisit dengan posisi fallback tersirat yang ditentukan oleh struktur pohon, mungkin lebih baik hanya memeriksa semua tindakan dan memilih yang paling berlaku saat ini?

Inilah yang dilakukan oleh sistem berbasis utilitas - ini adalah sistem di mana agen memiliki banyak tindakan yang dapat dilakukan, dan ia memilih untuk melakukan satu berdasarkan utilitas yang relatifsetiap aksi. Kegunaan di sini adalah ukuran kepentingan atau keinginan yang sewenang-wenang bagi agen untuk melakukan tindakan ini. Dengan menulis fungsi utilitas untuk menghitung utilitas tindakan berdasarkan kondisi agen saat ini dan lingkungannya, agen dapat memeriksa nilai utilitas dan memilih status yang paling tepat saat ini.

Ini juga sangat mirip mesin keadaan terbatas, kecuali bahwa transisi ditentukan oleh penilaian setiap keadaan potensial, termasuk yang saat ini. Perlu dicatat bahwa dalam kasus umum, kita memilih transisi ke tindakan yang paling berharga (atau berada di dalamnya jika kita sudah melakukan tindakan ini), tetapi untuk variabilitas yang lebih besar itu bisa menjadi pilihan acak tertimbang (mengutamakan tindakan yang paling berharga, tetapi memungkinkan pilihan orang lain) , pilihan tindakan acak dari lima teratas (atau jumlah lainnya), dll.

Sistem berbasis utilitas standar menetapkan kisaran nilai utilitas tertentu yang sewenang-wenang - misalkan dari 0 (benar-benar tidak diinginkan) hingga 100 (benar-benar diinginkan), dan setiap tindakan dapat memiliki serangkaian faktor yang memengaruhi cara nilai dihitung. Kembali ke contoh kita dengan penjaga, orang dapat membayangkan sesuatu seperti ini:

Aksi	Perhitungan utilitas
Cari bantuan	Jika musuh terlihat dan musuh kuat, dan kesehatan rendah, maka kembalikan 100, jika tidak kembalikan 0
Penerbangan	Jika musuh terlihat dan ada sedikit kesehatan, maka kembalikan 90, jika tidak kembalikan 0
Penyerangan	Jika musuh terlihat, kembalikan 80
Menunggu	Jika kita dalam keadaan menunggu dan sudah menunggu 10 detik, kembalikan 0, jika tidak 50
Patroli	Jika kita berada di ujung rute patroli, kembalikan 0, jika tidak 50

Salah satu aspek terpenting dari skema ini adalah bahwa transisi antar tindakan dinyatakan secara implisit - dari negara mana pun Anda dapat sepenuhnya masuk ke negara lain. Selain itu, prioritas tindakan tersirat dalam nilai utilitas yang dikembalikan. Jika musuh terlihat, dan jika dia kuat, dan karakter memiliki sedikit kesehatan, nilai-nilai bukan nol mengembalikan Penerbangan dan Pencarian Pencarian , tetapi Bantuan Pencarian selalu memiliki peringkat yang lebih tinggi. Demikian pula, tindakan non-tempur tidak pernah kembali lebih dari 50, sehingga mereka selalu dikalahkan oleh pertempuran. Dengan mengingat hal ini, tindakan dan perhitungan utilitasnya dibuat.

Dalam contoh kami, tindakan mengembalikan nilai utilitas konstan atau salah satu dari dua nilai utilitas konstan. Sistem yang lebih realistis menggunakan nilai balik dari rentang nilai kontinu . Misalnya, tindakan Liburan dapat mengembalikan nilai utilitas yang lebih tinggi jika kesehatan agen lebih rendah, dan tindakan Serangan dapat mengembalikan nilai utilitas yang lebih rendah jika musuh terlalu kuat. Ini akan memungkinkan Getaway untuk diutamakan dari Assault.dalam situasi apa pun di mana agen merasa bahwa dia tidak cukup sehat untuk melawan musuh. Ini memungkinkan Anda untuk mengubah prioritas tindakan relatif berdasarkan sejumlah kriteria, yang dapat membuat pendekatan ini lebih fleksibel daripada pohon perilaku atau pesawat ruang angkasa.

Setiap tindakan biasanya memiliki beberapa kondisi yang mempengaruhi perhitungan utilitas. Agar tidak membuat semuanya sulit dalam kode, Anda dapat menulisnya dalam bahasa scripting atau sebagai serangkaian rumus matematika, disatukan bersama-sama dengan cara yang dimengerti. Lebih banyak informasi tentang ini dalam kuliah dan presentasi oleh Dave Mark ( @IADaveMark ).

Dalam beberapa permainan yang mencoba mensimulasikan kehidupan sehari-hari karakter, misalnya, di The Sims, lapisan perhitungan lain ditambahkan di mana agen memiliki "aspirasi" atau "motivasi" yang mempengaruhi nilai utilitas. Misalnya, jika karakter memiliki motivasi Kelaparan, maka itu dapat meningkat dari waktu ke waktu, dan menghitung utilitas untuk aksi Makan akan mengembalikan nilai yang lebih tinggi dan lebih tinggi hingga karakter dapat melakukan tindakan ini, mengurangi kelaparan, dan tindakan “ Makan ”dikurangi menjadi nilai utilitas nol atau mendekati nol.

Gagasan memilih tindakan berdasarkan sistem poin cukup mudah, jadi jelas bahwa Anda dapat menggunakan pengambilan keputusan berdasarkan utilitas dalam proses pengambilan keputusan AI lainnya, dan tidak menggantinya sepenuhnya dengan itu. Pohon keputusan dapat meminta nilai utilitas dari dua simpul turunannya dan memilih simpul dengan nilai tertinggi. Demikian pula, pohon perilaku dapat memiliki simpul utilitas komposit yang menghitung utilitas untuk memilih simpul anak untuk dijalankan.

Gerakan dan navigasi

Dalam contoh sebelumnya, ada raket sederhana, yang kami pesan untuk bergerak ke kiri-kanan, atau karakter penjaga, yang selalu diperintahkan untuk berpatroli atau menyerang. Tetapi bagaimana tepatnya kita mengendalikan pergerakan agen selama periode waktu tertentu? Bagaimana kita dapat mengatur kecepatan, menghindari rintangan, merencanakan rute ketika tidak mungkin mencapai titik akhir secara langsung? Sekarang kita akan mempertimbangkan tugas ini.

Kemudi

Pada tingkat paling sederhana, sering kali bijaksana untuk bekerja dengan masing-masing agen seolah-olah ia memiliki nilai kecepatan yang menentukan kecepatan dan arah gerakannya. Kecepatan ini dapat diukur dalam meter per detik, dalam mil per jam, dalam piksel per detik dan seterusnya. Jika kita mengingat kembali siklus kita "tindakan berpikir-persepsi", kita dapat membayangkan bahwa "berpikir" dapat memilih kecepatan, setelah itu "tindakan" menerapkan kecepatan ini kepada agen, menggerakkannya di seluruh dunia. Biasanya dalam permainan ada sistem fisika yang melakukan tugas ini secara independen, mempelajari nilai kecepatan masing-masing entitas dan mengubah posisinya. Oleh karena itu, sering kali mungkin untuk menetapkan pekerjaan tersebut ke sistem ini, sehingga AI hanya tugas memilih kecepatan agen.

Jika kita tahu di mana agen ingin berada, maka kita perlu menggunakan kecepatan kita untuk memindahkan agen ke arah ini. Dalam bentuk sepele, kita mendapatkan persamaan berikut:

 diinginkan_travel = destination_position - agent_position 

Bayangkan dunia 2D di mana agen berada pada koordinat (-2, -2), dan titik target kira-kira di timur laut, pada koordinat (30, 20), yaitu, untuk menuju ke sana Anda harus bergerak (32, 22). Mari kita asumsikan bahwa posisi ini ditunjukkan dalam meter. Jika kami memutuskan bahwa agen dapat bergerak dengan kecepatan 5 m / s, maka kurangi skala vektor perpindahan ke nilai ini dan perhatikan bahwa kami perlu mengatur kecepatannya kira-kira (4,12, 2,83). Bergerak berdasarkan nilai ini, agen akan tiba di titik akhir hanya di bawah 8 detik, seperti yang diharapkan.

Perhitungan dapat dilakukan lagi kapan saja. Misalnya, jika agen berada di tengah-tengah target, maka gerakan yang diinginkan akan menjadi setengahnya, tetapi setelah penskalaan ke kecepatan agen maksimum 5 m / s, kecepatannya tetap sama. Ini juga berfungsi untuk memindahkan target (sesuai alasan), yang memungkinkan agen melakukan penyesuaian kecil di sepanjang jalan.

Namun, seringkali kita perlu lebih banyak kontrol. Sebagai contoh, kita mungkin perlu meningkatkan kecepatan secara perlahan, seolah-olah karakter pertama kali diam, kemudian bergerak ke langkah, dan kemudian berlari. Di sisi lain, kita mungkin perlu memperlambatnya saat mendekati target. Seringkali, tugas-tugas tersebut diselesaikan menggunakan apa yang disebut " perilaku kemudi""memiliki nama sendiri seperti Seek, Flee, Arrival, dan sebagainya. (Di Habré ada serangkaian artikel tentang mereka: https://habr.com/post/358366/ .) Gagasan mereka adalah Anda dapat menerapkan kecepatan agen kekuatan akselerasi berdasarkan perbandingan posisi agen dan kecepatan gerakan saat ini menuju target, menciptakan berbagai cara bergerak menuju target.

Setiap perilaku memiliki tujuan yang sedikit berbeda. Seek and Arrival digunakan untuk memindahkan agen ke tujuannya. Penghindaran Hambatan dan Pemisahan membantu agen membuat gerakan korektif kecil untuk menghindari hambatan kecil antara agen dan tujuannya. Penyelarasan dan kohesi memaksa agen untuk bergerak bersama, meniru binatang ternak. Setiap variasi dari perilaku kemudi yang berbeda dapat digabungkan bersama, seringkali dalam bentuk jumlah tertimbang, untuk menciptakan nilai total yang memperhitungkan semua faktor yang berbeda ini dan membuat vektor hasil tunggal. Misalnya, agen dapat menggunakan perilaku Kedatangan bersama dengan perilaku Pemisahan dan Penghindaran untuk menjauh dari dinding dan agen lainnya. Pendekatan ini bekerja dengan baik di lingkungan terbuka yang tidak terlalu rumit dan ramai.

Namun, dalam lingkungan yang lebih kompleks, hanya menambahkan nilai-nilai output dari perilaku tidak bekerja dengan baik - kadang-kadang gerakan di dekat objek terlalu lambat, atau agen macet ketika perilaku Kedatangan ingin melewati rintangan, dan perilaku Penghindaran Rintangan mendorong agen ke sisi asalnya. . Karenanya, terkadang masuk akal untuk mempertimbangkan variasi perilaku mengarahkan yang lebih rumit daripada sekadar menjumlahkan semua nilai. Salah satu keluarga dari pendekatan semacam itu terdiri dari implementasi yang berbeda - kami tidak mempertimbangkan setiap perilaku yang memberi kami arahan, diikuti oleh kombinasinya untuk mendapatkan konsensus (yang dengan sendirinya mungkin tidak memadai). Sebagai gantinya, kami mempertimbangkan gerakan di beberapa arah yang berbeda - misalnya, di delapan arah kompas, atau pada 5-6 poin di depan agen,setelah itu kami memilih yang terbaik.

Namun, dalam lingkungan yang kompleks dengan jalan buntu dan opsi menikung, kita akan membutuhkan sesuatu yang lebih maju, dan kita akan segera beralih ke ini.

Menemukan jalan

Perilaku kemudi sangat bagus untuk gerakan sederhana di area yang cukup terbuka, seperti lapangan sepak bola atau arena, di mana Anda bisa berpindah dari A ke B dalam garis lurus dengan sedikit penyesuaian untuk menghindari rintangan. Tetapi bagaimana jika rute ke titik akhir lebih rumit? Kemudian kita membutuhkan "pencarian jalan" - menjelajahi dunia dan merencanakan jalur di sepanjang itu sehingga agen mencapai titik akhir.

Cara paling sederhana adalah dengan meletakkan kisi-kisi di dunia, dan untuk setiap sel di sebelah agen, lihat sel tetangga di mana kita bisa bergerak. Jika salah satu dari mereka adalah titik terakhir kita, maka kembali rute, dari setiap sel ke yang sebelumnya, sampai kita sampai ke awal, sehingga memperoleh rute. Jika tidak, ulangi proses dengan tetangga yang dapat dijangkau dari tetangga sebelumnya hingga kami menemukan titik akhir atau kami kehabisan sel (ini berarti bahwa tidak ada rute). Secara formal, pendekatan ini disebut algoritma Breadth-First Search (BFS), karena pada setiap langkah terlihat di semua arah (yaitu, "lebar") sebelum memindahkan pencarian. Ruang pencarian seperti muka gelombang yang bergerak sampai menemukan tempat yang kami cari.

Ini adalah contoh sederhana dari pencarian yang sedang beraksi. Area pencarian meluas di setiap tahap sampai titik akhir dimasukkan di dalamnya, setelah itu Anda dapat melacak jalur ke awal.


Sebagai hasilnya, kami mendapatkan daftar sel kisi, membuat rute yang harus Anda tuju. Biasanya itu disebut "jalan", jalan (maka "pencarian jalan", merintis jalan), tetapi Anda juga dapat membayangkannya sebagai rencana, karena ini adalah daftar tempat yang perlu Anda kunjungi untuk mencapai tujuan Anda, yaitu titik akhir.

Sekarang kita mengetahui posisi setiap sel di dunia, Anda dapat menggunakan perilaku kemudi yang dijelaskan di atas untuk bergerak di sepanjang rute - pertama dari titik awal ke titik 2, kemudian dari titik 2 ke titik 3, dan seterusnya. Pendekatan yang paling sederhana adalah bergerak menuju pusat sel berikutnya, tetapi ada juga alternatif yang populer - bergerak ke tengah rusuk antara sel saat ini dan berikutnya. Hal ini memungkinkan agen untuk memotong tikungan tajam untuk menciptakan gerakan yang lebih realistis.

Seperti yang Anda lihat, algoritme ini dapat menyia-nyiakan sumber daya karena memeriksa sebanyak mungkin sel di arah yang "salah" seperti di yang "benar". Juga, itu tidak memungkinkan untuk memperhitungkan biaya pergerakan, di mana beberapa sel mungkin "lebih mahal" daripada yang lain. Di sini kita sampai pada bantuan algoritma yang lebih kompleks yang disebut A *. Cara kerjanya hampir sama dengan pencarian pertama, tetapi alih-alih menjelajahi tetangga secara buta, lalu tetangga tetangga, lalu tetangga tetangga, tetangga, dan seterusnya, ia menempatkan semua simpul ini dalam daftar dan mengurutkannya sehingga simpul berikutnya yang diselidiki selalu menjadi satu. kemungkinan besar mengarah ke rute terpendek. Node diurutkan berdasarkan heuristik (yaitu, pada kenyataannya, asumsi yang masuk akal),yang memperhitungkan dua aspek - biaya rute hipotetis ke sel (sehingga memperhitungkan semua biaya yang diperlukan untuk bergerak) dan penilaian seberapa jauh sel ini dari titik akhir (sehingga memindahkan pencarian ke arah yang benar).


Dalam contoh ini, kami menunjukkan bahwa ia memeriksa satu sel pada satu waktu, setiap kali memilih sel tetangga yang memiliki prospek terbaik (atau salah satu yang terbaik). Jalur yang dihasilkan mirip dengan jalur pencarian pertama, tetapi lebih sedikit sel yang diperiksa dalam proses, dan ini sangat penting untuk kinerja gim di tingkat kompleks.

Gerakan tanpa jala

Dalam contoh-contoh sebelumnya, sebuah grid yang ditumpangkan pada dunia digunakan, dan kami meletakkan rute di seluruh dunia melalui sel-sel dari grid ini. Tetapi sebagian besar permainan tidak tumpang tindih grid, dan karenanya overlay grid dapat menyebabkan pola pergerakan yang tidak realistis. Juga, pendekatan ini mungkin memerlukan kompromi mengenai ukuran masing-masing sel - jika terlalu besar, maka itu tidak akan dapat secara memadai menggambarkan koridor dan belokan kecil, jika terlalu kecil, maka mencari melalui ribuan sel mungkin terlalu lama. Apa alternatifnya?

Hal pertama yang perlu kita pahami adalah bahwa, dari sudut pandang matematis, grid memberi kita " grafik"dari node yang terhubung. Algoritma A * (dan BFS) bekerja dengan grafik, dan mereka tidak peduli dengan grid. Oleh karena itu, kita dapat menempatkan node di posisi sewenang-wenang dunia, dan jika ada garis lurus antara dua node yang terhubung, tetapi ada garis antara awal dan akhir jika hanya ada satu simpul, algoritme kami akan berfungsi seperti sebelumnya, dan faktanya bahkan lebih baik, karena akan ada lebih sedikit simpul.Ini sering disebut sistem titik jalan, karena setiap simpul menunjukkan posisi penting di dunia yang dapat membuat bagian dari sejumlah pu hipotetis s.


Contoh 1: sebuah simpul di setiap sel dari kisi. Pencarian dimulai dengan simpul di mana agen berada, dan berakhir dengan sel terakhir.


Contoh 2: jumlah node, atau titik jalan yang jauh lebih kecil . Pencarian dimulai dengan agen, melewati jumlah titik arah yang diperlukan dan bergerak ke titik akhir. Perhatikan bahwa pindah ke titik pertama jalur barat daya pemain adalah rute yang tidak efisien, sehingga beberapa pemrosesan pasca jalur yang dihasilkan biasanya diperlukan (misalnya, untuk mengetahui bahwa jalur dapat langsung menuju titik arah di timur laut).

Ini adalah sistem yang cukup fleksibel dan kuat, tetapi membutuhkan lokasi titik jalan yang hati-hati, jika tidak, agen mungkin tidak melihat titik jalan terdekat untuk memulai rute. Akan lebih bagus jika kita entah bagaimana bisa menghasilkan titik arah secara otomatis berdasarkan geometri dunia.

Dan kemudian navmesh datang untuk menyelamatkan. Ini kependekan dari navigasi mesh. Intinya, ini adalah (biasanya) jaring segitiga dua dimensi, kira-kira tumpang tindih dengan geometri dunia di tempat-tempat di mana permainan memungkinkan agen untuk bergerak. Setiap segitiga dalam jala menjadi simpul grafik dan memiliki hingga tiga segitiga berdekatan yang menjadi simpul berdekatan grafik.

Di bawah ini adalah contoh dari mesin Unity. Mesin menganalisis geometri dunia dan menciptakan navmesh (biru), yang merupakan perkiraan geometri. Setiap nammesh poligon adalah area di mana agen dapat berdiri, dan agen dapat bergerak dari satu poligon ke yang berdekatan. (Dalam contoh ini, poligon dibuat lebih sempit dari lantai di mana mereka terletak untuk memperhitungkan jari-jari agen, yang melampaui posisi nominal agen.)



Kita dapat mencari rute melalui mesh menggunakan A * lagi, dan ini akan memberi kita rute yang ideal di seluruh dunia yang memperhitungkan semua geometri dan tidak memerlukan jumlah node tambahan yang berlebihan (seperti halnya dengan grid) dan partisipasi manusia dalam menghasilkan poin jalan.

Menemukan jalan adalah topik yang luas, yang ada banyak pendekatan, terutama jika Anda perlu memprogram rincian tingkat rendah sendiri. Salah satu sumber informasi tambahan terbaik adalah situs Amit Patel (terjemahan artikel tentang Habré: https://habr.com/post/331192/ ).

Perencanaan

Menggunakan pencarian untuk jalur sebagai contoh, kami melihat bahwa kadang-kadang tidak cukup hanya dengan memilih arah dan mulai bergerak di dalamnya - kita perlu memilih rute dan membuat beberapa gerakan sebelum mencapai titik akhir yang diinginkan. Kita dapat menggeneralisasi ide ini ke berbagai konsep di mana tujuannya bukan hanya langkah selanjutnya. Untuk mencapainya, Anda perlu mengambil serangkaian langkah, dan untuk mengetahui apa langkah pertama yang harus dilakukan, Anda mungkin perlu melihat beberapa langkah ke depan. Pendekatan ini disebut perencanaan . Menemukan jalan dapat dianggap sebagai salah satu aplikasi perencanaan yang spesifik, tetapi konsep ini memiliki lebih banyak aplikasi. Kembali ke siklus "tindakan berpikir-persepsi", perencanaan ini adalah fase pemikiran yang mencoba merencanakan beberapa fase tindakan untuk masa depan.

Mari kita lihat game Magic: The Gathering. Anda memiliki langkah pertama Anda, ada beberapa kartu di tangan Anda, di antaranya adalah "Rawa", yang memberikan 1 titik mana hitam, dan "Hutan", yang memberikan 1 titik mana hijau, "Pengusir setan", yang membutuhkan 1 titik mana biru untuk memanggil, dan " Elven Mystic ”, untuk memanggil mana Anda membutuhkan 1 titik mana hijau. (Untuk kesederhanaan, kami menghilangkan tiga kartu yang tersisa.) Peraturan mengatakan bahwa seorang pemain dapat memainkan satu kartu tanah per giliran, dapat "menyentuh" ​​kartu tanahnya untuk mendapatkan mana dari mereka, dan dapat melemparkan sebanyak mungkin mantra (termasuk makhluk pemanggilan) berapa banyak mana yang dia miliki. Dalam situasi ini, pemain cenderung bermain "Hutan", menyentuhnya untuk mendapatkan 1 titik hijau mana, dan kemudian memanggil "Elven Mystic". Tapi bagaimana sebuah game AI tahu bahwa keputusan seperti itu perlu dibuat?

"Penjadwal" sederhana

Pendekatan naif mungkin hanya dengan mengulangi setiap tindakan secara berurutan, sampai ada yang sesuai. Melihat tangannya, AI melihat bahwa ia dapat memainkan "Rawa", dan karenanya melakukannya. Apakah ada tindakan lagi yang tersisa setelah belokan ini? Dia tidak bisa memanggil Elven Mystic atau Exile Wizard, karena ini membutuhkan mana hijau atau biru, dan rawa yang dimainkan hanya memberikan mana hitam. Dan kami tidak dapat memainkan "Hutan" karena kami telah memainkan "Rawa". Artinya, pemain AI akan melakukan langkah sesuai aturan, tetapi itu tidak akan sangat optimal. Untungnya, ada solusi yang lebih baik.

Dalam cara yang hampir sama dengan pencarian jalur menemukan daftar posisi untuk bergerak di seluruh dunia untuk mencapai titik yang tepat, perencana kami dapat menemukan daftar tindakan yang menempatkan permainan dalam kondisi yang tepat. Sama seperti setiap posisi di jalan memiliki set tetangga, yang merupakan opsi potensial untuk memilih langkah berikutnya di sepanjang jalan, setiap tindakan dalam rencana memiliki tetangga, atau "ahli waris," yang merupakan kandidat untuk langkah selanjutnya dari rencana. Kita dapat mencari tindakan ini dan tindakan berikut hingga mencapai kondisi yang diinginkan.

Misalkan, sebagai contoh kita, hasil yang diinginkan adalah "memanggil makhluk, jika memungkinkan." Pada awal langkah, kami hanya memiliki dua tindakan potensial yang diizinkan oleh aturan permainan:

 1. Mainkan "Swamp" (hasil: "Swamp" meninggalkan tangan dan memasuki permainan)
2. Mainkan "Hutan" (hasil: "Hutan" meninggalkan tangan dan memasuki permainan) 

Setiap tindakan yang diambil dapat membuka tindakan lebih lanjut atau menutupnya, juga sesuai dengan aturan permainan. Bayangkan kita memilih untuk bermain "Rawa" - ini menutup peluang untuk memainkan kartu ini sebagai tindakan warisan yang potensial (karena "Rawa" telah dimainkan), menutup peluang untuk bermain "Hutan" (karena aturan permainan memungkinkan Anda bermain hanya satu kartu land per putaran) dan menambahkan kemampuan untuk menyentuh "Rawa" untuk mendapatkan 1 poin mana hitam - dan ini, pada kenyataannya, adalah satu-satunya tindakan yang diwariskan. Jika kita mengambil satu langkah lagi dan memilih "sentuh" ​​Rawa "", kita akan mendapatkan 1 titik mana hitam yang dengannya kita tidak dapat melakukan apa pun, jadi ini tidak ada gunanya.

 1. Mainkan "Swamp" (hasil: "Swamp" meninggalkan tangan dan memasuki permainan)
            1.1 Sentuh "Rawa" (hasil: kami menyentuh "Rawa", +1 mana hitam tersedia)
                        Tidak ada tindakan yang tersisa - AKHIR
2. Mainkan "Hutan" (hasil: "Hutan" meninggalkan tangan dan memasuki permainan) 

Daftar tindakan singkat ini tidak memberi kita banyak dan mengarah pada "jalan buntu", jika kita menggunakan analogi dengan mencari jalan. Karena itu, kami ulangi proses untuk langkah selanjutnya. Kami memilih untuk bermain Forest. Ini juga menghilangkan kemampuan untuk "bermain Hutan" dan "bermain Rawa", dan terbuka sebagai langkah potensial (dan hanya) selanjutnya "menyentuh Hutan." Ini memberi kita 1 titik mana hijau, yang pada gilirannya membuka langkah ketiga - "panggilan" Elven Mystic "."

 1. Mainkan "Swamp" (hasil: "Swamp" meninggalkan tangan dan memasuki permainan)
            1.1 Sentuh "Rawa" (hasil: kami menyentuh "Rawa", +1 mana hitam tersedia)
                        Tidak ada tindakan yang tersisa - AKHIR
2. Mainkan "Hutan" (hasil: "Hutan" meninggalkan tangan dan memasuki permainan)
            2.1 Sentuh "Hutan" (hasil: kami menyentuh "Rawa", +1 mana hijau tersedia)
                        2.1.1 Panggil "Elven Mystic" (hasil: "Elven Mystic" di permainan, -1 mana hijau tersedia)
                                    Tidak ada tindakan yang tersisa - AKHIR 

Sekarang kita telah menyelidiki semua tindakan dan tindakan yang mungkin dihasilkan dari tindakan ini, menemukan rencana yang memungkinkan kita untuk memanggil makhluk itu: "mainkan Hutan", "sentuh Hutan", "panggil" Elven Mystic "".

Jelas, ini adalah contoh yang sangat sederhana, dan biasanya Anda harus memilih yang terbaikrencana, dan bukan hanya rencana yang memenuhi beberapa kriteria (misalnya, "memanggil makhluk"). Anda biasanya dapat mengevaluasi rencana potensial berdasarkan hasil akhir atau manfaat kumulatif dari menggunakan rencana tersebut. Sebagai contoh, Anda dapat memberi diri Anda 1 poin untuk peta daratan yang sudah diletakkan dan 3 poin untuk memanggil makhluk. "Mainkan" Rawa "" akan menjadi rencana singkat yang memberikan 1 poin, dan rencana untuk "bermain" Hutan "→ sentuh" ​​Hutan "→ panggil" Elven Mystic "" memberikan 4 poin, 1 untuk tanah dan 3 untuk makhluk itu. Ini akan menjadi paket paling menguntungkan yang tersedia, jadi Anda harus memilihnya jika kami menunjuk poin tersebut.

Di atas, kami menunjukkan bagaimana perencanaan bekerja dalam satu Sihir: Gerakan Berkumpul, tetapi juga dapat diterapkan pada tindakan dalam serangkaian gerakan (misalnya, "memindahkan pion untuk memberikan ruang bagi pengembangan uskup" dalam catur atau "bertemu dengan unit) dia bisa menembak giliran berikutnya, aman "di XCOM) atau dengan strategi umum seluruh permainan (misalnya," membangun tiang ke semua bangunan protoss lainnya "di Starcraft, atau" minum ramuan Fortify Health sebelum menyerang musuh "di Skyrim).

Perencanaan yang lebih baik

Terkadang ada terlalu banyak tindakan yang mungkin pada setiap langkah, dan mengevaluasi setiap opsi tidak masuk akal. Mari kita kembali ke contoh Sihir: The Gathering - bayangkan bahwa kita memiliki beberapa makhluk di tangan, banyak tanah telah dimainkan, sehingga kita dapat memanggil makhluk apa saja, beberapa makhluk dengan kemampuan mereka dimainkan, dan ada beberapa kartu tanah lagi di tangan - jumlah permutasi tanah, penggunaan lahan, memanggil makhluk dan menggunakan kemampuan makhluk bisa sama dengan ribuan atau bahkan puluhan ribu. Untungnya, ada beberapa cara untuk menyelesaikan masalah ini.

Yang pertama disebut rantai mundur"(" Perjalanan pulang-pergi "). Alih-alih memeriksa semua tindakan dan hasil mereka, kita dapat mulai dengan masing-masing hasil akhir yang diinginkan dan melihat apakah kita dapat menemukan jalur langsung ke sana. Anda dapat membandingkan ini dengan mencoba menjangkau daun tertentu di pohon - jauh lebih logis mulai dari daun ini dan kembali, meletakkan rute di sepanjang batang (dan rute ini kita dapat pergi dalam urutan yang berlawanan), daripada mulai dari batang dan mencoba menebak cabang mana yang akan dipilih pada setiap langkah. Jika Anda mulai dari ujung dan pergi ke arah yang berlawanan, kemudian dibuat e rencana akan jauh lebih cepat dan lebih mudah.

Misalnya, jika musuh memiliki 1 titik kesehatan yang tersisa, maka mungkin berguna untuk mencoba menemukan rencana untuk "memberikan 1 atau lebih poin kerusakan langsung pada musuh." Sistem kami tahu bahwa untuk mencapai tujuan ini, ia harus menggunakan mantra kerusakan langsung, yang pada gilirannya berarti harus ada di tangan kami dan kami membutuhkan cukup mana untuk mengucapkannya. Ini, pada gilirannya, berarti bahwa kami perlu menyentuh cukup banyak tanah untuk menerima mana ini, yang mungkin mengharuskan Anda untuk memainkan peta tanah tambahan.

Cara lain adalah dengan mencari berdasarkan kecocokan terbaik pertama. Alih-alih berkeliling semua permutasi untuk waktu yang lama, kami mengukur seberapa "baik" setiap rencana parsial (mirip dengan bagaimana kami memilih dari opsi rencana di atas) dan menghitung yang tampak terbaik setiap kali. Seringkali ini memungkinkan Anda untuk membuat rencana yang optimal, atau setidaknya cukup baik tanpa perlu mempertimbangkan setiap rencana penataan ulang yang mungkin. A * adalah variasi dari pencarian untuk pertandingan terbaik pertama - itu pertama mengeksplorasi rute yang paling menjanjikan, sehingga biasanya dapat menemukan jalan ke tujuan tanpa harus naik terlalu jauh ke arah lain.

Opsi pencarian yang menarik dan semakin populer untuk pertandingan terbaik pertama adalah pencarian pohon Monte Carlo .. Alih-alih menebak rencana mana yang lebih baik daripada yang lain ketika memilih setiap tindakan berikutnya, metode ini memilih tindakan selanjutnya secara acak pada setiap langkah sampai mencapai akhir di mana tidak ada tindakan yang mungkin lagi - mungkin karena rencana hipotetis mengarah pada keadaan menang atau kalah - dan menggunakan hasil ini untuk memberikan bobot lebih atau kurang untuk opsi yang dipilih sebelumnya. Jika proses ini diulang berkali-kali, metode ini dapat membuat penilaian yang baik tentang langkah terbaik berikutnya, bahkan jika situasinya berubah (misalnya, jika musuh mencoba menggagalkan rencana kami).

Akhirnya, tidak ada diskusi perencanaan dalam permainan yang akan lengkap tanpa menyebutkan perencanaan tindakan berbasis tujuan(Perencanaan Tindakan yang Berorientasi Sasaran, GOAP). Ini adalah teknik yang banyak digunakan dan dibahas secara luas, tetapi jika Anda mengabaikan beberapa detail implementasi tertentu, itu pada dasarnya adalah perencana perjalanan pulang-pergi yang dimulai dengan tujuan dan mencoba mengambil tindakan yang mengarah ke tujuan itu, atau, lebih mungkin, daftar tindakan yang mengarah ke ke tujuan. Misalnya, jika tujuannya adalah untuk "membunuh pemain" dan pemain dalam perlindungan, maka rencananya adalah: "Asap pemain dengan granat" → "Tarik senjata" → "Serang".

Biasanya ada beberapa tujuan, dan masing-masing memiliki prioritas sendiri. Jika tujuan dengan prioritas tertinggi tidak dapat dicapai, misalnya, tidak ada rangkaian tindakan yang dapat membentuk rencana "Bunuh pemain" karena pemain tidak terlihat, maka sistem kembali ke tujuan dengan prioritas yang lebih rendah, misalnya, "Patroli" atau "Penjaga di tempat".

Pelatihan dan adaptasi

Pada awal artikel, kami menyebutkan bahwa game AI umumnya tidak menggunakan "pembelajaran mesin" karena biasanya tidak cocok untuk kontrol real-time agen cerdas di dunia game. Namun, ini tidak berarti bahwa kami tidak dapat meminjam sesuatu dari area ini di mana itu masuk akal. Kita mungkin membutuhkan lawan komputer dalam penembak untuk mencari tahu tempat terbaik untuk bergerak untuk mendapatkan hasil terbanyak. Atau kita mungkin ingin lawan dalam permainan pertempuran. misalnya, di Tekken atau Street Fighter, dia belajar mengenali pemain menggunakan kombo yang sama untuk mulai memblokirnya, memaksa pemain untuk menggunakan taktik yang berbeda. Artinya, ada kalanya persentase pembelajaran mesin tertentu berguna.

Statistik dan Peluang

Sebelum kita beralih ke contoh yang lebih kompleks, ada baiknya mencari tahu seberapa jauh kita bisa pergi dengan hanya melakukan pengukuran dan menggunakan data ini untuk membuat keputusan. Sebagai contoh, katakanlah kita memiliki permainan dalam genre strategi real-time, dan kita perlu memahami apakah pemain akan mulai terburu-buru dalam beberapa menit pertama untuk memutuskan apakah akan membangun lebih banyak pertahanan. Kami dapat memperkirakan perilaku pemain sebelumnya untuk memahami seperti apa perilaku di masa depan. Pada awalnya, kami tidak memiliki data yang dapat diekstrapolasi, tetapi setiap kali AI bermain melawan musuh yang hidup, ia dapat merekam waktu serangan pertama. Setelah beberapa pertandingan, waktu ini dapat dirata-ratakan, dan kami akan mendapatkan perkiraan waktu serangan pemain yang cukup baik di masa depan.

Masalah dengan rata-rata sederhana adalah bahwa biasanya konvergen dari waktu ke waktu di pusat. Karena itu, jika seorang pemain menggunakan strategi terburu-buru 20 kali pertama, dan 20 kali berikutnya beralih ke strategi yang jauh lebih lambat, maka nilai rata-rata akan berada di suatu tempat di tengah, yang tidak akan memberi kami informasi yang berguna. Salah satu cara untuk meningkatkan data adalah dengan menggunakan jendela rata-rata sederhana yang memperhitungkan hanya 20 titik data terakhir.

Pendekatan serupa dapat digunakan untuk menilai kemungkinan tindakan tertentu, dengan asumsi bahwa preferensi pemain sebelumnya akan berlanjut di masa depan. Misalnya, jika seorang pemain menyerang lima kali dengan bola api, dua kali dengan petir dan satu-ke-tangan hanya satu kali, maka kemungkinan besar ia akan lebih memilih bola api 5 dari 8 kali. Mengekstrapolasi dari data ini, kita dapat melihat bahwa probabilitas menggunakan senjata adalah: Fireball = 62,5%, Lightning = 25% Melee = 12,5%. Karakter AI kami akan menyadari bahwa mereka lebih baik menemukan baju besi tahan api!

Metode lain yang menarik adalah dengan menggunakan Naive Bayes Classifier untuk mempelajari volume besar data input untuk mengklasifikasikan situasi saat ini sehingga agen AI dapat merespons sesuai. Pengklasifikasi Bayesian mungkin paling dikenal karena penggunaannya dalam filter email spam, di mana mereka mengevaluasi kata-kata dalam email, membandingkannya dengan kata-kata yang paling sering ditemukan dalam spam dan pesan normal di masa lalu. Berdasarkan perhitungan ini, mereka memutuskan kemungkinan bahwa pesan terakhir yang diterima adalah spam. Kita dapat melakukan hal serupa, hanya dengan input yang lebih sedikit. Dengan merekam semua informasi bermanfaat yang dapat diamati (mis., Unit musuh yang dibuat,menggunakan mantra atau teknologi penelitian) dan melacak situasi yang dihasilkan (perang / perdamaian, strategi terburu-buru / strategi pertahanan, dll.), kita dapat memilih perilaku yang sesuai berdasarkan ini.

Menggunakan semua teknik pengajaran ini bisa cukup, dan sering dan lebih disukai diterapkan pada data yang dikumpulkan selama playtesting sebelum rilis game. Hal ini memungkinkan AI untuk beradaptasi dengan berbagai strategi yang digunakan oleh penguji permainan dan tidak berubah setelah rilis game. AI yang beradaptasi dengan pemain setelah permainan dirilis mungkin menjadi terlalu mudah ditebak atau bahkan terlalu rumit untuk dikalahkan.

Adaptasi berbasis berat yang mudah

Mari kita selangkah lebih maju. Alih-alih hanya menggunakan data input untuk memilih antara strategi yang telah ditentukan sebelumnya, Anda dapat mengubah serangkaian nilai yang memengaruhi pengambilan keputusan. Jika kita memahami dunia game dan aturan mainnya dengan baik, maka kita dapat melakukan hal berikut:

• ( );
• «» ;
• .

Bayangkan seorang agen komputer yang dapat memilih kamar pada peta dalam penembak orang pertama. Setiap kamar memiliki bobot yang menentukan keinginan mengunjungi ruangan ini. Awalnya, semua kamar memiliki arti yang sama. Saat memilih kamar, AI memilihnya secara acak, tetapi dengan pengaruh bobot ini. Sekarang bayangkan bahwa ketika agen komputer terbunuh, ia ingat di ruang mana hal ini terjadi dan mengurangi bobotnya sehingga kecil kemungkinannya untuk kembali ke sana di masa depan. Demikian pula, bayangkan seorang agen komputer telah melakukan pembunuhan. Kemudian ia dapat menambah bobot ruangan tempat ia berada untuk mengangkatnya dalam daftar preferensi. Jadi jika satu ruangan menjadi sangat berbahaya bagi pemain AI, maka ia mulai menghindarinya di masa depan, dan jika beberapa ruangan lain memungkinkan AI untuk mendapatkan banyak pembunuhan,maka dia akan kembali ke sana.

Model Markov

Bagaimana jika kami ingin menggunakan data yang kami kumpulkan untuk membuat prakiraan? Sebagai contoh, jika kita merekam setiap ruangan tempat kita melihat pemain untuk jangka waktu tertentu, kita dapat memprediksi ruang mana yang bisa dia masuki. Dengan melacak ruang saat ini di mana pemain berada dan yang sebelumnya, dan merekam pasangan nilai-nilai ini, kita dapat menghitung seberapa sering masing-masing situasi sebelumnya mengarah ke situasi berikutnya, dan menggunakan pengetahuan ini untuk perkiraan.

Bayangkan ada tiga ruangan - merah, hijau dan biru, dan selama sesi permainan kami menerima pengamatan seperti itu:

Ruang pertama di mana pemain terlihat	Pengamatan total	Kamar sebelah	Berapa kali dilihat	Persentase
Merah	10	Merah	2	20%
		Hijau	7	70%
		Biru	1	10%
Hijau	10	Merah	3	30%
		Hijau	5	50%
		Biru	2	20%
Biru	8	Merah	6	75%
		Hijau	2	25%
		Biru	0	0%

Jumlah deteksi di masing-masing kamar cukup adil, jadi ini tidak memberi kita pemahaman tentang kamar mana yang bisa menjadi tempat yang baik untuk penyergapan. Data dapat terdistorsi oleh fakta bahwa pemain secara seragam menelurkan pada peta, dengan probabilitas yang sama untuk muncul di salah satu dari tiga kamar ini. Tetapi data tentang kunjungan ke kamar sebelah dapat berguna dan membantu kami memperkirakan pergerakan pemain di peta.

Kami dapat segera melihat bahwa ruang hijau sangat menarik bagi pemain - sebagian besar pemain dari ruang merah berubah menjadi hijau, dan 50% dari pemain yang terlihat di ruang hijau tetap ada di sana selama pemeriksaan berikutnya. Kita juga dapat memperhatikan bahwa ruang biru adalah tempat yang agak tidak menarik. Orang jarang berpindah dari kamar merah atau hijau ke biru dan tampaknya tidak ada yang suka berlama-lama di dalamnya.

Tetapi data memberi tahu kita sesuatu yang lebih spesifik - mereka mengatakan bahwa ketika seorang pemain berada di ruang biru, kemudian mengikutinya dia kemungkinan besar memilih merah, bukan hijau. Terlepas dari kenyataan bahwa ruang hijau adalah tempat yang jauh lebih populer daripada ruang merah, kecenderungannya agak berlawanan jika pemain berada di ruang biru. Tampaknya keadaan berikutnya (yaitu ruangan tempat ia memutuskan untuk bergerak lebih jauh) tergantung pada keadaan sebelumnya (yaitu, ruang di mana ia sekarang), sehingga data ini memungkinkan kami untuk membuat prakiraan yang lebih baik tentang perilaku pemain dibandingkan dengan penghitungan observasi independen.

Gagasan bahwa kita dapat menggunakan pengetahuan tentang keadaan sebelumnya untuk memprediksi keadaan di masa depan disebut model Markov, dan contoh serupa di mana kami telah secara akurat mengukur peristiwa (misalnya, "di mana ruang pemain berada") disebut rantai Markov. Karena mereka mewakili probabilitas transisi antara keadaan berturut-turut, mereka sering diwakili secara grafis dalam bentuk mesin keadaan terbatas, di dekat setiap transisi yang probabilitasnya ditunjukkan. Sebelumnya, kami menggunakan mesin keadaan untuk mewakili keadaan perilaku di mana agen berada, tetapi konsep ini dapat diperluas ke semua jenis negara, apakah mereka terkait dengan agen atau tidak. Dalam kasus kami, negara menunjukkan kamar yang ditempati oleh agen. Ini akan terlihat seperti ini:


Ini adalah pendekatan sederhana untuk menunjukkan probabilitas relatif transisi ke berbagai negara, yang memberikan AI kemampuan untuk memprediksi keadaan berikutnya. Tapi kita bisa melangkah lebih jauh dengan menciptakan sistem yang melihat ke masa depan dalam dua langkah atau lebih.

Jika seorang pemain terlihat di ruang hijau, kami akan menggunakan data yang memberi tahu kami bahwa ada kemungkinan 50 persen bahwa ia masih akan berada di ruang hijau pada pengamatan berikutnya. Tapi apa kemungkinan dia akan tetap di sana untuk ketiga kalinya? Ini bukan hanya probabilitas bahwa ia akan tetap di ruang hijau untuk dua pengamatan (50% * 50% = 25%), tetapi juga probabilitas bahwa ia akan meninggalkannya dan kembali. Berikut adalah tabel baru dengan nilai-nilai sebelumnya yang diterapkan pada tiga pengamatan: satu saat ini dan dua hipotesis di masa depan.

Pengamatan 1	Pengamatan hipotetis 2		3
		30%		20%	6%
				70%	21%
				10%	3%
		50%		30%	15%
				50%	25%
				20%	10%
		20%		75%	15%
				25%	5%
				0%	0%
				:	100%

Di sini kita melihat bahwa kemungkinan melihat seorang pemain di ruang hijau setelah 2 pengamatan adalah 51% - 21% dari apa yang akan dia dapatkan dari ruang merah, 5% dari apa yang kita lihat pemain mengunjungi ruang biru, dan 25% dari apa yang dia miliki sepanjang waktu akan tinggal di ruang hijau.

Tabel hanyalah petunjuk visual, prosedur hanya membutuhkan penggandaan probabilitas di setiap tahap. Ini berarti bahwa kita dapat melihat jauh ke masa depan, tetapi dengan satu peringatan signifikan: kita membuat asumsi bahwa kemungkinan memasuki ruangan sepenuhnya tergantung pada ruangan apa yang kita masuki saat ini. Gagasan bahwa keadaan masa depan hanya bergantung pada arus disebut properti Markov. Meskipun memungkinkan kita untuk menggunakan alat yang kuat seperti rantai Markov, itu biasanya hanya perkiraan. Pemain dapat memutuskan untuk mengunjungi kamar berdasarkan faktor lain, seperti tingkat kesehatan mereka dan jumlah amunisi, dan karena kami tidak mencatat informasi ini sebagai bagian dari kondisi, prediksi kami akan kurang akurat.

N gram

Mari kita kembali ke contoh kita dengan pengakuan kombo dalam game pertempuran. Ini adalah situasi yang serupa di mana kami ingin memprediksi keadaan masa depan berdasarkan masa lalu (untuk memutuskan bagaimana memblokir serangan atau menghindarinya), tetapi alih-alih mempelajari satu keadaan atau peristiwa, kami akan mempertimbangkan urutan peristiwa yang membuat gerakan kombo.

Salah satu cara untuk melakukan ini adalah menyimpan setiap input pemain (misalnya, tendangan , tangan atau blok ) ke buffer dan tulis seluruh buffer sebagai suatu peristiwa. Bayangkan bahwa seorang pemain terus-menerus menekan tendangan , tendangan , tendangan untuk menggunakan serangan " Kanker Kematian " ", dan sistem AI menyimpan semua input pemain ke buffer dan mengingat 3 entri terakhir yang digunakan pada setiap langkah.

Masuk	Urutan input yang ada	Memori input baru
Tendangan	Tendangan	tidak
Pemogokan tangan	Tendangan, Tendangan	tidak
Tendangan	Tendangan, Tendangan, Tendangan	Tendangan, Tendangan, Tendangan
Tendangan	Tendangan, Tendangan, Tendangan, Tendangan	Tendangan, Tendangan, Tendangan
Pemogokan tangan	Tendangan, Tendangan, Tendangan, Tendangan, Tendangan	Tendangan, Tendangan, Tendangan
Blokir	Kick, Kick, Kick, Kick, Kick, Block	Tendangan, Tendangan, Blokir
Tendangan	Kick, Kick, Kick, Kick, Kick, Block, Kick	Tendangan, blokir, tendang
Tendangan	Kick, Kick, Kick, Kick, Kick, Block, Kick, Kick	Blokir, tendang, tendang
Pemogokan tangan	, , , , , , , ,	, ,

(Dalam garis tebal, pemain melakukan serangan "Superbuck of Death".)

Anda dapat melihat saat-saat ketika pemain memilih tendangan di masa lalu , diikuti oleh tendangan lain , dan perhatikan bahwa input berikutnya selalu merupakan pukulan . Ini memungkinkan agen AI untuk membuat prediksi bahwa jika seorang pemain baru saja memilih tendangan, diikuti dengan tendangan, dia kemungkinan besar akan memilih tendangan berikutnya , sehingga meluncurkan Death Superkulak . Ini memungkinkan AI untuk memutuskan untuk memilih tindakan yang menangkal pukulan ini, seperti blok atau penghindaran.

Urutan peristiwa seperti itu disebut N-gram.di mana N adalah jumlah item yang disimpan. Pada contoh sebelumnya, itu 3 gram, juga disebut trigram, yaitu, 2 elemen pertama digunakan untuk memprediksi yang ketiga. Dalam 5-gram, yang kelima diprediksi untuk 4 elemen pertama, dan seterusnya.

Pengembang harus hati-hati memilih ukuran N-gram (kadang-kadang disebut pesanan). Semakin kecil angkanya, semakin sedikit memori yang diperlukan, karena semakin kecil jumlah permutasi yang diizinkan, tetapi semakin sedikit histori yang disimpan, yang berarti bahwa konteksnya hilang. Misalnya, 2 gram (juga disebut "bigram") akan berisi catatan untuk menendang , menendang, dan rekaman untuk menendang , menendang , tetapi tidak dapat menyimpan tendangan .tendangan , karena itu tendangan , tidak dapat melacak kombo ini.

Di sisi lain, semakin besar urutannya, semakin banyak memori yang dibutuhkan, dan sistem kemungkinan besar akan lebih sulit untuk dilatih, karena kita akan memiliki permutasi yang jauh lebih besar, yang berarti kita tidak pernah dapat memenuhi dua kali yang sama. Misalnya, jika ada tiga input yang mungkin ( tendangan , tangan dan blok ) dan kami menggunakan 10-gram, maka akan ada hampir 60 ribu permutasi yang berbeda.

Model bigram pada dasarnya adalah rantai sepele Markov - setiap pasangan "negara masa depan / negara saat ini" adalah bigram dan kita dapat memprediksi negara kedua berdasarkan yang pertama. Trigram dan N-gram besar juga dapat dianggap sebagai rantai Markov, di mana semua elemen N-gram, kecuali yang terakhir, membentuk status pertama, dan elemen terakhir adalah status kedua. Dalam contoh permainan pertempuran kami, probabilitas transisi dari keadaan menendang dan menendang ke keadaan menendang, kemudian menendang disajikan. Mempersepsikan beberapa elemen dari sejarah input sebagai elemen tunggal, kami pada dasarnya mengubah urutan input menjadi satu fragmen negara, yang memberi kita properti Markov, memungkinkan kita untuk menggunakan rantai Markov untuk memprediksi input berikutnya, yaitu menebak gerakan kombo mana yang akan mengikuti.

Representasi pengetahuan

Kami membahas beberapa cara untuk membuat keputusan, membuat rencana, dan memperkirakan, dan semuanya didasarkan pada pengamatan agen terhadap keadaan dunia. Tetapi bagaimana kita bisa secara efektif mengamati seluruh dunia game? Di atas, kami melihat bahwa cara merepresentasikan geometri dunia sangat memengaruhi pergerakan sepanjang itu, sehingga mudah untuk membayangkan bahwa ini berlaku untuk aspek lain dari game AI. Bagaimana kita dapat mengumpulkan dan mengatur semua informasi yang diperlukan secara optimal (sehingga sering diperbarui dan dapat diakses oleh banyak agen) dan praktis (sehingga informasi tersebut dapat dengan mudah digunakan dalam proses pengambilan keputusan)? Bagaimana cara mengubah data sederhana menjadi informasi atau pengetahuan ? Untuk gim yang berbeda, solusinya mungkin berbeda, tetapi ada beberapa pendekatan yang paling populer.

Tag / Tag

Terkadang kita sudah memiliki sejumlah besar data yang berguna, dan satu-satunya yang kita butuhkan adalah cara yang baik untuk mengategorikan dan mencarinya. Sebagai contoh, di dunia game bisa ada banyak objek, dan beberapa di antaranya adalah perlindungan yang baik dari peluru musuh. Atau, misalnya, kami memiliki banyak dialog audio yang direkam yang dapat diterapkan dalam situasi tertentu, dan kami membutuhkan cara untuk mengetahuinya dengan cepat. Langkah yang jelas adalah menambahkan sepotong kecil informasi tambahan yang dapat Anda gunakan untuk mencari. Fragmen seperti itu disebut tag atau tag.

Mari kita kembali ke contoh tempat penampungan; di dunia game bisa ada banyak objek - kotak, barel, tandan rumput, pagar kawat. Beberapa dari mereka cocok untuk tempat tinggal, misalnya, kotak dan barel, yang lain tidak. Karena itu, ketika agen kami melakukan tindakan "Pindah ke Tempat Tinggal", ia harus mencari benda-benda terdekat dan mengidentifikasi kandidat yang cocok. Dia tidak bisa hanya mencari berdasarkan nama - mungkin gim ini memiliki Crate_01, Crate_02, hingga Crate_27, dan kami tidak ingin mencari semua nama ini dalam kode. Kami tidak ingin menambahkan nama lain ke kode setiap kali artis membuat variasi baru kotak atau laras. Sebagai gantinya, Anda dapat mencari nama apa pun yang mengandung kata "Crate", tetapi suatu hari seorang artis dapat menambahkan "Broken_Crate" dengan lubang besar, tidak cocok sebagai tempat berlindung.

Karenanya, sebagai gantinya, kami akan membuat tag "COVER" dan meminta seniman dan desainer untuk melampirkan tag ini ke semua objek yang dapat digunakan untuk tempat berteduh. Jika mereka menambahkan tag ke semua barel dan kotak (keseluruhan), maka prosedur AI hanya perlu menemukan objek dengan tag ini, dan ia akan tahu bahwa objek tersebut cocok untuk tujuan ini. Tag akan berfungsi bahkan jika objek kemudian diubah namanya, dan itu dapat ditambahkan ke objek di masa depan tanpa membuat perubahan yang tidak perlu pada kode.

Dalam kode tersebut, tag biasanya direpresentasikan sebagai string, tetapi jika semua tag yang digunakan diketahui, maka Anda dapat mengonversi string ke angka unik untuk menghemat ruang dan mempercepat pencarian. Di beberapa mesin, tag adalah fungsi bawaan, misalnya, di Unity dan di Unreal Engine 4 , oleh karena itu, cukup untuk menentukan pilihan tag di dalamnya dan menggunakannya untuk tujuan yang dimaksudkan.

Benda pintar

Tag adalah cara menambahkan informasi tambahan ke lingkungan agen, untuk membantunya mengetahui opsi yang tersedia, sehingga pertanyaan seperti "Temukan saya semua tempat terdekat untuk bersembunyi" atau "Temukan saya semua musuh di dekatnya yang dapat memberikan mantra" dilakukan secara efisien dan dengan sedikit usaha untuk sumber daya gim yang baru. Tetapi terkadang tag tidak mengandung informasi yang cukup untuk penggunaan penuh.

Bayangkan sebuah simulator dari sebuah kota abad pertengahan di mana para petualang berkeliaran di tempat yang mereka inginkan, jika perlu, latih, berkelahi dan bersantai. Kami dapat mengatur situs pelatihan di berbagai bagian kota dan memberi mereka tag "PELATIHAN" sehingga karakter dapat dengan mudah menemukan tempat untuk pelatihan. Tapi mari kita bayangkan bahwa salah satunya adalah jarak tembak untuk pemanah, dan yang lainnya adalah sekolah penyihir. Dalam setiap kasus ini, kita perlu menunjukkan animasi kita, karena dengan nama umum "pelatihan" mereka mewakili tindakan yang berbeda, dan tidak setiap petualang tertarik pada kedua jenis pelatihan. Anda dapat masuk lebih dalam dan membuat tag ARCHERY-TRAINING dan MAGIC-TRAINING, pisahkan prosedur pelatihan dari satu sama lain dan sematkan di setiap animasi yang berbeda. Ini akan membantu menyelesaikan masalah. Tapi bayangkanbahwa para desainer nantinya akan menyatakan "Mari kita memiliki sekolah Robin Hood di mana Anda dapat belajar memanah dan bertarung pedang"! Dan kemudian, ketika kita menambahkan pertarungan pedang, mereka meminta penciptaan Akademi Mantra dan Pedang Gandalf Gandalf. Akibatnya, kita harus menyimpan beberapa tag untuk setiap tempat dan mencari animasi yang berbeda berdasarkan aspek pelatihan apa yang dibutuhkan karakter, dll.

Cara lain adalah dengan menyimpan informasi secara langsung di objek bersama dengan pengaruh yang dimilikinya pada pemain, sehingga aktor AI dapat dengan mudah membuat daftar opsi yang mungkin dan memilih dari mereka sesuai dengan kebutuhan agen. Setelah itu, ia dapat pindah ke tempat yang tepat, melakukan animasi yang sesuai (atau tindakan wajib lainnya), sebagaimana ditunjukkan dalam objek, dan menerima hadiah yang sesuai.

	Menjalankan animasi	Hasil Pengguna
Jarak tembak	Tembak-panah	+10 Keterampilan Panahan
Sekolah Sihir	Duel pedang	+10 Keterampilan Pedang
Sekolah Robin Hood	Tembak-panah	+15 Keterampilan Panahan
	Duel pedang	+8 Keterampilan Pedang
Akademi Gandalf	Duel pedang	+5 Keterampilan Pedang
	Mantra mantra	+10 Keahlian Sihir

Karakter pemanah di sebelah 4 lokasi ini akan memiliki 6 opsi, 4 di antaranya tidak berlaku baginya jika dia tidak menggunakan pedang atau sihir. Membandingkan hasil dalam hal ini dengan peningkatan keterampilan, daripada nama atau tag, kita dapat dengan mudah memperluas kemungkinan dunia dengan perilaku baru. Anda dapat menambahkan hotel untuk beristirahat dan memuaskan rasa lapar Anda. Anda dapat membiarkan karakter pergi ke perpustakaan dan membaca tentang mantra dan teknik memanah lanjutan.

Nama objek	Menjalankan animasi	Hasil akhir
Hotel	Beli	-10 kelaparan
Hotel	Tidur	-50 sampai lelah
Perpustakaan	Baca buku	+10 Keterampilan Ejaan
Perpustakaan	Baca buku	+5 Keterampilan Panahan

Jika kita sudah memiliki perilaku "latihan memanah", maka bahkan jika kita menandai perpustakaan sebagai tempat untuk PELATIHAN ARCHERY, maka kita kemungkinan besar membutuhkan kasus khusus untuk memproses animasi baca-buku alih-alih animasi pedang-pedang yang biasa. Sistem ini memberi kita lebih banyak fleksibilitas dengan memindahkan asosiasi ini ke data dan menyimpan data di dunia.

Keberadaan objek atau lokasi - perpustakaan, hotel atau sekolah - memberi tahu kami tentang layanan yang mereka tawarkan, tentang karakter yang bisa mendapatkannya, memungkinkan Anda untuk menggunakan sejumlah kecil animasi. Kemampuan untuk membuat keputusan sederhana tentang hasil memungkinkan Anda membuat berbagai perilaku menarik. Alih-alih secara pasif menunggu permintaan, objek-objek ini dapat memberikan banyak informasi tentang bagaimana dan mengapa menggunakannya.

Kurva reaksi

Seringkali ada situasi di mana bagian dari keadaan dunia dapat diukur sebagai nilai berkelanjutan. Contoh:

• "Persentase kesehatan" biasanya berkisar dari 0 (mati) hingga 100 (benar-benar sehat)
• "Jarak ke musuh terdekat" bervariasi dari 0 hingga beberapa nilai positif yang berubah-ubah

Selain itu, game mungkin memiliki beberapa aspek dari sistem AI, yang membutuhkan input nilai kontinu dalam beberapa interval lainnya. Misalnya, untuk membuat keputusan untuk melarikan diri, sistem peringkat utilitas mungkin memerlukan jarak ke musuh terdekat dan kesehatan karakter saat ini.

Namun, sistem tidak dapat dengan mudah menambahkan dua nilai keadaan dunia untuk mendapatkan tingkat "keamanan" tertentu, karena dua unit pengukuran ini tidak dapat dibandingkan - sistem akan menganggap bahwa karakter yang hampir mati 200 meter dari musuh berada dalam keamanan yang sama seperti benar-benar sehat. karakter 100 meter dari musuh. Selain itu, sementara nilai persentase kesehatan dalam arti luas adalah linier, jaraknya tidak begitu - perbedaan jarak dari musuh 200 dan 190 meter kurang signifikan daripada perbedaan antara 10 meter dan nol.

Idealnya, kita membutuhkan solusi yang mengambil dua indikator dan mengubahnya menjadi interval yang sama sehingga mereka dapat dibandingkan secara langsung. Dan kita membutuhkan desainer untuk dapat mengontrol bagaimana transformasi ini dihitung untuk mengontrol kepentingan relatif dari setiap nilai. Untuk tujuan ini kurva reaksi (Kurva Respons) digunakan.

Cara termudah untuk menjelaskan kurva reaksi adalah sebagai grafik dengan input sepanjang sumbu X, nilai acak, misalnya, "jarak ke musuh terdekat" dan output di sepanjang sumbu Y (biasanya nilai yang dinormalisasi dalam kisaran 0,0 hingga 1,0). Garis atau kurva pada bagan menentukan pengikatan input ke output yang dinormalisasi, dan desainer menyesuaikan garis-garis ini untuk mendapatkan perilaku yang mereka butuhkan.

Untuk menghitung tingkat "keamanan", Anda dapat mempertahankan linearitas dari nilai persen kesehatan - misalnya, kesehatan 10% lebih banyak - ini biasanya baik ketika karakter terluka parah, dan ketika ia terluka dengan mudah. Oleh karena itu, kami menetapkan nilai-nilai ini ke interval dari 0 hingga 1 secara langsung:


Jarak ke musuh terdekat sedikit berbeda, jadi kami sama sekali tidak terganggu oleh musuh di luar jarak tertentu (katakanlah 50 meter), dan kami jauh lebih tertarik pada perbedaan pada jarak pendek daripada jarak jauh.

Di sini kita melihat bahwa output "keamanan" untuk musuh di 40 dan 50 meter hampir sama: 0,96 dan 1,0.


Namun, ada perbedaan yang jauh lebih besar antara musuh di 15 meter (sekitar 0,5) dan musuh di 5 meter (sekitar 0,2). Jadwal seperti itu lebih baik mencerminkan pentingnya musuh semakin dekat.

Dengan menormalkan kedua nilai ini dalam rentang dari 0 hingga 1, kita dapat menghitung nilai keamanan total sebagai rata-rata dari kedua nilai input ini. Karakter dengan kesehatan 20% dan musuh pada jarak 50 meter akan memiliki skor keamanan 0,6. Karakter dengan kesehatan 75% dan musuh yang hanya berjarak 5 meter akan memiliki skor keamanan 0,47. Karakter yang terluka parah dengan kesehatan 10% dan musuh 5 meter akan memiliki indeks keamanan hanya 0,145.

Hal-hal berikut harus dipertimbangkan di sini:

• — , .
• — , , 50 — , , .
• , ( ) . , — , Unity AnimationCurve , .

Blackboards

Seringkali kita menemukan diri kita dalam situasi di mana AI untuk agen harus mulai memantau pengetahuan dan informasi yang diperoleh selama pertandingan sehingga mereka dapat digunakan dalam pengambilan keputusan lebih lanjut. Sebagai contoh, seorang agen mungkin perlu mengingat karakter terakhir yang diserang untuk fokus pada serangan karakter itu untuk waktu yang singkat. Atau dia harus ingat berapa banyak waktu telah berlalu setelah dia mendengar suara, sehingga setelah periode waktu tertentu dia berhenti mencari alasannya dan kembali ke studi sebelumnya. Sangat sering, sistem perekaman data sangat terpisah dari sistem pembacaan data, sehingga harus mudah diakses dari agen, dan tidak dibangun langsung ke berbagai sistem AI. Membaca dapat terjadi beberapa saat setelah menulis, sehingga data perlu disimpan di suatu tempat,sehingga mereka dapat diambil nanti (dan tidak dihitung berdasarkan permintaan, yang mungkin tidak layak).

Dalam sistem AI yang dikode keras, solusinya mungkin dengan menambahkan variabel yang diperlukan dalam proses kebutuhan. Variabel-variabel ini berhubungan dengan instance dari karakter atau agen, baik mengintegrasikan langsung ke dalamnya, atau membuat struktur / kelas terpisah untuk menyimpan informasi tersebut. Prosedur AI dapat diadaptasi untuk membaca dan menulis data ini. Dalam sistem yang sederhana, ini akan bekerja dengan baik, tetapi karena lebih banyak informasi ditambahkan, itu menjadi rumit, dan biasanya membutuhkan pembangunan kembali permainan setiap kali.

Pendekatan yang lebih baik adalah mengubah gudang data menjadi struktur yang memungkinkan sistem membaca dan menulis data yang berubah-ubah. Solusi ini memungkinkan Anda untuk menambahkan variabel baru tanpa perlu mengubah struktur data, sehingga memberikan kemampuan untuk meningkatkan jumlah perubahan yang dapat dibuat dari file data dan skrip tanpa perlu reassembly. Jika masing-masing agen menyimpan daftar pasangan nilai kunci, yang masing-masing merupakan bagian pengetahuan yang terpisah, maka sistem AI yang berbeda dapat bekerja sama dengan menambahkan dan membaca informasi ini jika perlu.

Dalam pengembangan AI, pendekatan seperti itu disebut "papan tulis" ("papan tulis"), karena setiap peserta - dalam kasus kami, ini adalah prosedur AI (misalnya, persepsi, menemukan jalan dan membuat keputusan) - dapat menulis ke "papan tulis", dibaca dari mana data untuk kinerja tugas mereka dapat berupa peserta lain. Anda dapat membayangkan ini sebagai tim ahli berkumpul di sekitar papan tulis dan menulis sesuatu yang berguna di atasnya yang perlu Anda bagikan dengan grup. Pada saat yang sama, mereka dapat membaca catatan sebelumnya dari kolega mereka sampai mereka membuat keputusan atau rencana bersama. Daftar variabel umum dalam kode yang sulit dikodekan kadang-kadang disebut "papan tulis statis" (karena elemen di mana informasi disimpan konstan selama pelaksanaan program), dan daftar sewenang-wenang dari pasangan nilai kunci sering disebut "papan tulis dinamis".Tetapi mereka digunakan kira-kira dengan cara yang sama - sebagai penghubung antara bagian-bagian dari sistem AI.

Dalam AI tradisional, penekanan biasanya ditempatkan pada kolaborasi sistem yang berbeda untuk pengambilan keputusan bersama, tetapi relatif sedikit sistem hadir dalam game AI. Namun, tingkat kerja sama tertentu mungkin masih ada. Bayangkan hal berikut dalam RPG tindakan:

• Sistem "persepsi" secara teratur memindai area dan menulis entri berikut ke papan tulis:
  
  • Musuh Terdekat: Goblin 412
    
  • "Jarak ke musuh terdekat": 35.0
    
  • "Teman dekat": "Prajurit 43"
    
  • “Jarak ke teman terdekat”: 55.4
    
  • "Waktu kebisingan terakhir diperhatikan": 12:45
• Sistem seperti sistem tempur dapat merekam peristiwa penting di papan tulis, misalnya:
  
  • Kerusakan Terakhir Diambil: 12:34

Banyak dari data ini mungkin terlihat berlebihan - pada akhirnya, Anda selalu bisa mendapatkan jarak ke musuh terdekat, hanya mengetahui siapa musuh ini dan memenuhi permintaan untuk posisinya. Tetapi ketika diulang beberapa kali per frame, untuk memutuskan apakah agen mengancam sesuatu atau tidak, ini menjadi operasi yang berpotensi lambat, terutama jika dia perlu melakukan pencarian spasial untuk menentukan musuh terdekat. Dan cap waktu dari "kebisingan terakhir yang terlihat" atau "kerusakan terakhir yang diterima" masih tidak akan dapat terjadi secara instan - Anda perlu mencatat waktu terjadinya peristiwa ini, dan papan tulis adalah tempat yang nyaman untuk ini.

Unreal Engine 4 menggunakan sistem papan tulis dinamis untuk menyimpan data yang dikirimkan oleh pohon perilaku. Berkat objek data umum ini, desainer dapat dengan mudah menulis nilai baru ke papan tulis berdasarkan cetak biru mereka (skrip visual), dan pohon perilaku kemudian dapat membaca nilai-nilai ini untuk memilih perilaku, dan semua ini tidak memerlukan kompilasi ulang mesin.

Mempengaruhi Peta

Tugas standar dalam AI adalah memutuskan ke mana agen harus pindah. Dalam penembak kita dapat memilih aksi "Pindah ke tempat berlindung", tetapi bagaimana cara memutuskan di mana tempat perlindungan berada dalam kondisi memindahkan musuh? Demikian pula dengan tindakan "Melarikan diri" - di mana cara paling aman untuk melarikan diri? Atau di RTS, kita mungkin perlu pasukan untuk menyerang titik lemah di pertahanan musuh - bagaimana kita menentukan di mana titik lemah ini?

Semua pertanyaan ini dapat dianggap sebagai tugas geografis, karena kami mengajukan pertanyaan tentang geometri dan bentuk lingkungan dan posisi entitas di dalamnya. Dalam permainan kami, semua data ini kemungkinan besar sudah tersedia, tetapi memberi mereka makna bukanlah tugas yang mudah. Misalnya, jika kita ingin menemukan titik lemah di pertahanan musuh, maka cukup memilih posisi bangunan terlemah atau benteng tidak cukup baik jika mereka memiliki dua sistem senjata yang kuat di sisi-sisi. Kami membutuhkan cara untuk memperhitungkan daerah setempat dan memberikan analisis yang lebih baik tentang situasi tersebut.

Untuk inilah struktur data "peta pengaruh". Ini menggambarkan "pengaruh" yang dimiliki suatu entitas terhadap area di sekitarnya. Menggabungkan pengaruh beberapa entitas, kami menciptakan tampilan yang lebih realistis pada seluruh lanskap. Dari sudut pandang implementasi, kami memperkirakan dunia game dengan melapiskan kisi 2D di atasnya, dan setelah menentukan sel kisi mana yang digunakan entitas, kami menerapkan penilaian dampak pada ini dan sel-sel di sekitarnya, menunjukkan aspek gameplay yang ingin kami simulasikan. Untuk mendapatkan gambaran lengkap, kami mengakumulasikan nilai-nilai ini dalam kisi yang sama. Setelah itu, kita dapat melakukan berbagai permintaan kisi untuk memahami dunia dan memutuskan posisi dan target poin.

Ambil contoh, "titik terlemah dalam pertahanan musuh." Kami memiliki tembok pertahanan, di mana kami ingin mengirim prajurit perang, tetapi ada 3 ketapel di belakangnya - 2 dekat satu sama lain di sebelah kiri, 1 di sebelah kanan. Bagaimana kita memilih posisi serangan yang baik?

Untuk memulainya, kita bisa menetapkan +1 poin perlindungan ke semua sel grid dalam serangan ketapel. Menggambar titik-titik ini pada peta pengaruh untuk satu ketapel terlihat seperti ini:


Kotak biru membatasi semua sel tempat Anda dapat meluncurkan serangan di dinding. Kotak merah menunjukkan +1 pengaruh ketapel. Dalam kasus kami, ini berarti area serangan mereka dan ancaman terhadap unit penyerang.

Sekarang kita tambahkan efek ketapel kedua:


Kami memiliki area gelap di mana pengaruh dua ketapel terbentuk, yang memberikan perlindungan sel-sel ini +2. Sel +2 di dalam zona biru bisa menjadi tempat yang sangat berbahaya untuk menyerang dinding! Tambahkan pengaruh ketapel terakhir:


[Ikon: CC-OLEH: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

Sekarang kami memiliki penunjukan lengkap untuk area yang dicakup oleh ketapel. Di zona serangan potensial, ada satu sel dengan +2 pengaruh ketapel, 11 sel dengan pengaruh +1, dan 2 sel dengan pengaruh ketapel 0 - ini adalah kandidat utama untuk posisi serangan, di dalamnya kita dapat menyerang dinding tanpa takut akan tembakan ketapel.

Keuntungan dari peta pengaruh adalah mereka mengubah ruang kontinu dengan set posisi yang hampir tak terbatas menjadi seperangkat posisi perkiraan yang berbeda, yang dengannya kita dapat mengambil keputusan dengan sangat cepat.

Namun, kami memperoleh keuntungan ini hanya dengan memilih sejumlah kecil posisi serangan potensial. Mengapa kita harus menggunakan peta pengaruh di sini daripada secara manual memeriksa jarak dari setiap ketapel ke masing-masing posisi ini?

Pertama, menghitung peta pengaruh bisa sangat murah. Setelah poin pengaruh diletakkan di kartu, itu tidak perlu diubah sampai entitas mulai bergerak. Ini berarti bahwa kita tidak perlu terus-menerus melakukan perhitungan jarak atau menginterogasi setiap unit yang mungkin secara iteratif - kita “memanggang” informasi ini ke dalam peta dan dapat mengirim permintaan kepadanya beberapa kali.

Kedua, kita bisa tumpang tindih dan menggabungkan peta pengaruh yang berbeda untuk memenuhi pertanyaan yang lebih kompleks. Misalnya, untuk memilih tempat yang aman untuk melarikan diri, kita dapat mengambil peta pengaruh musuh kita dan mengurangi peta teman-teman kita - sel-sel grid dengan nilai negatif terbesar akan dianggap aman.


Semakin merah, semakin berbahaya, dan semakin hijau, semakin aman. Area di mana pengaruh tumpang tindih dapat dinetralkan sepenuhnya atau sebagian untuk mencerminkan area pengaruh yang saling bertentangan.

Akhirnya, peta pengaruh mudah divisualisasikan saat render di dunia. Mereka dapat menjadi petunjuk berharga bagi desainer yang perlu menyesuaikan AI berdasarkan sifat yang terlihat, dan mereka dapat ditonton secara real time untuk memahami mengapa AI memilih keputusannya.

Kesimpulan

Saya harap artikel ini memberi Anda gambaran tentang alat dan pendekatan paling populer yang digunakan dalam game AI, serta situasi di mana mereka dapat diterapkan. Artikel itu tidak mempertimbangkan banyak teknik lain (mereka jarang digunakan, tetapi berpotensi sama efektifnya), termasuk yang berikut:

• algoritma tugas pengoptimalan, termasuk pendakian ke atas, gradient descent, dan algoritma genetika.
• algoritma pencarian / perencanaan kompetitif seperti kliping minimax dan alpha beta
• teknik klasifikasi, misalnya, perceptrons, jaringan saraf, dan metode vektor dukungan
• persepsi agen dan sistem pemrosesan memori
• pendekatan arsitektur untuk AI, seperti sistem hibrida, arsitektur predikatif (arsitektur Brooks) dan cara lain untuk mendekomposisi sistem AI menjadi lapisan
• alat animasi seperti perencanaan gerak dan pencocokan gerak
• tugas yang berhubungan dengan kinerja seperti level detail, algoritma kapan saja, dan penentuan waktu

Untuk membaca lebih lanjut tentang topik ini, serta topik yang dibahas dalam artikel ini, Anda dapat mempelajari sumber-sumber berikut.

• GameDev.net memiliki artikel dan tutorial tentang kecerdasan buatan , serta forum tentang kecerdasan buatan .
• Pada AiGameDev.com memiliki banyak presentasi dan artikel tentang berbagai topik kecerdasan buatan dalam konteks pengembangan game
• GDC Vault memiliki laporan dengan KTT GDC AI, banyak di antaranya tersedia secara gratis: https://www.gdcvault.com/
  
• Selain itu, Aliansi Pemrogram Game AI memiliki banyak tautan ke artikel dan presentasi lama dari KTT ini: http://gameai.com/
  
• Peneliti dan pengembang game AI Tommy Thompson memiliki saluran YouTube yang didedikasikan untuk menjelaskan dan menjelajahi AI dalam game komersial: https://www.youtube.com/user/tthompso

Banyak bahan berkualitas tinggi dapat ditemukan di buku-buku, termasuk yang berikut:

• Seri Game AI Pro adalah kumpulan artikel pendek yang menjelaskan cara menerapkan fitur tertentu atau menyelesaikan masalah tertentu. Di http://www.gameaipro.com/ memposting cuplikan gratis dari buku-buku sebelumnya.
  
  • Game AI Pro: Koleksi Kebijaksanaan Game AI Professionals
    
  • Game AI Pro 2: Himpunan Dikumpulkan dari Game AI Professionals
    
  • Game AI Pro 3: Himpunan Dikumpulkan dari Game AI Professionals
    
  
  
• AI Game Programming Wisdom Game AI Pro. , . , !
  
  
  • AI Game Programming Wisdom 1
    
  • AI Game Programming Wisdom 2
    
  • AI Game Programming Wisdom 3
    
  • AI Game Programming Wisdom 4
    
• Artificial Intelligence: A Modern Approach — , . , , , .

Selain itu, ada beberapa buku bagus tentang game AI pada umumnya, yang ditulis oleh para profesional di industri ini. Sulit untuk memberikan preferensi kepada siapa pun - baca ulasan dan pilih yang cocok untuk Anda.