Selama sekitar satu bulan, saya menyelesaikan salah satu masalah teknis paling sulit dari game baru saya,
Dicey Dungeons - sebuah AI yang ditingkatkan untuk rilis final game. Itu adalah karya yang agak menarik, dan kebanyakan baru bagi saya, jadi saya memutuskan untuk menulis sedikit tentang itu.
Untuk mulai dengan, saya akan menjelaskan: Saya bukan ahli dalam teori komputer, tetapi hanya salah satu dari mereka yang telah mempelajari pemrograman cukup untuk membuat video game, setelah itu saya lulus dari pelatihan, hanya meraih apa yang saya butuhkan. Biasanya saya bisa menyelesaikan masalah saya sendiri, tetapi seorang programmer nyata kemungkinan besar tidak akan menyetujui keputusan saya.
Saya mencoba menulis artikel pada tingkat abstraksi yang cukup tinggi sehingga ide dasarnya jelas bahkan untuk non-programmer. Tetapi saya bukan ahli dalam hal-hal seperti itu, jadi penjelasan saya tentang teori itu mungkin salah. Menulis kepada saya tentang ini di komentar ke aslinya, saya dengan senang hati akan melakukan perubahan!
Baiklah, mari kita mulai dengan menjelaskan tugas!
Tantangan
Jika Anda belum pernah bermain Dicey Dungeons, saya akan berbicara singkat tentang permainan: ini adalah RPG dengan deckbuilding, di mana setiap musuh memiliki satu set peta senjata yang melakukan berbagai tindakan. Selain itu, mereka melempar dadu! Kemudian mereka memasukkan dadu ke dalam persenjataan untuk menghasilkan kerusakan, atau menciptakan berbagai efek status, atau menyembuhkan, atau mempertahankan diri dari kerusakan, dan sejenisnya. Berikut adalah contoh sederhana tentang bagaimana katak kecil menggunakan pedang besar dan perisai kecil:
Contoh yang lebih kompleks: Jack dari semua perdagangan ini memiliki kunci pas, yang memungkinkan Anda untuk menyatukan dua dadu (yaitu, 3 + 2 akan memberikan 5, dan 4 + 5 akan memberikan 6 dan 3). Dia juga memiliki palu (Palu), yang memberikan efek "kejutan" pada pemain, jika Anda menerapkan enam padanya, dan seorang penembak kacang (Pea Shooter), yang tidak sedikit merusak, tetapi ia memiliki "hitungan mundur", kemudian ada itu berlaku untuk beberapa gerakan.
Komplikasi penting lainnya: permainan memiliki efek status yang mengubah kemampuan lawan. Yang paling penting dari ini adalah Shock, yang secara acak menonaktifkan senjata; guncangan dapat dihilangkan dengan menggunakan kubus tambahan di atasnya, dan "Bakar", yang membakar kubus. Sementara kubus terbakar, mereka dapat digunakan, tetapi setiap penggunaan akan menelan biaya 2 poin kesehatan. Inilah yang dilakukan oleh tukang pintar ketika saya menyetrum dan membakar semua senjata dan kubusnya:
Tentu saja, ada lebih banyak dalam permainan, tetapi untuk mendapatkan ide umum, ini sudah cukup.
Jadi, tugas kita: bagaimana membuat AI memilih tindakan terbaik untuk pergerakannya? Bagaimana dia bisa mengetahui kubus mana yang akan dibakar, kubus mana yang digunakan untuk meredakan kejutan, dan mana yang harus disimpan untuk senjata penting?
Seperti yang dia lakukan sebelumnya
Untuk waktu yang lama, AI di Dicey Dungeons hanya memiliki satu aturan: dia melihat semua senjata dari kiri ke kanan, menentukan kubus terbaik yang bisa digunakan padanya, dan kemudian menggunakannya. Ini bekerja dengan baik, tetapi ada pengecualian. Jadi saya menambahkan aturan baru.
Misalnya, saya berurusan dengan guncangan dengan melihat semua senjata yang tidak terkena goncangan, dan memilih dadu mana yang akan saya gunakan saat goncangan dilepas, dan kemudian menandai dadu ini sebagai "dicadangkan" untuk masa depan. Saya bekerja dengan membakar batu seperti ini: Saya memeriksa apakah saya memiliki kesehatan yang cukup untuk memadamkannya, dan secara acak memilih apakah akan melakukan ini.
Saya menambahkan aturan demi aturan untuk semua yang dapat saya bayangkan, dan sebagai hasilnya saya mendapatkan AI yang sepertinya berfungsi! Bahkan, sungguh menakjubkan betapa baiknya jalinan aturan yang berbeda ini menunjukkan dirinya sendiri - AI di Dicey Dungeons mungkin tidak selalu membuat keputusan yang tepat, tetapi selalu setidaknya dapat diterima. Setidaknya untuk game masih dalam pengembangan.
Namun seiring berjalannya waktu, sistem untuk terus-menerus menambahkan aturan baru mulai retak pada lapisannya. Orang-orang telah menemukan eksploitasi yang membuat AI berperilaku bodoh. Misalnya, dengan pendekatan yang tepat, Anda bisa mengecoh salah satu bos sehingga dia tidak akan pernah menyerang pemain. Semakin banyak aturan yang saya tambahkan untuk memperbaiki situasi, semakin banyak hal aneh mulai terjadi - beberapa aturan bertentangan dengan yang lain, kasus batas mulai muncul.
Tentu saja, salah satu solusinya adalah menambahkan aturan baru, mempertimbangkan setiap tugas satu per satu, dan membuat konstruksi baru jika untuk memprosesnya. Tetapi saya berpikir bahwa dengan cara ini saya hanya menyingkirkan solusi yang sebenarnya untuk masalah tersebut. Keterbatasan sistem adalah bahwa ia hanya mengkhawatirkan satu pertanyaan: "Apa langkah saya
selanjutnya ?" Dia tidak pernah melihat ke depan dan tidak mencoba menyarankan apa yang
bisa terjadi dari kombinasi cerdas tertentu.
Jadi saya memutuskan untuk memulai lagi.
Solusi klasik
Cobalah mencari informasi tentang AI untuk game, dan kemungkinan besar hal pertama yang Anda temui adalah solusi klasik - membuat algoritma
minimax . Berikut adalah video tentang bagaimana ia digunakan dalam mengembangkan AI untuk catur:
Implementasi minimax adalah sebagai berikut:
Pertama, kami membuat versi abstrak permainan kami yang paling sederhana, di mana ada semua informasi yang diperlukan untuk titik waktu tertentu dalam permainan. Kami akan menyebutnya
papan . Dalam hal catur, ini adalah posisi saat ini dari semua bagian. Dalam kasus Dicey Dungeons, ini adalah daftar efek dadu, senjata, dan status.
Lalu kami membuat
fungsi nilai yang mengukur seberapa baik permainan ini dimainkan untuk konfigurasi game tertentu, yaitu, untuk
papan tertentu. Misalnya, dalam catur, papan tempat potongan berada di posisi semula diberi nilai 0 poin. Papan tempat Anda memakan pion lawan memiliki nilai 1 poin, dan papan tempat Anda kehilangan pion Anda sendiri memiliki nilai -1 poin. Dan papan yang kita periksa lawan akan dievaluasi pada jumlah poin yang tak terbatas, atau sesuatu seperti itu!
Kemudian, dari papan abstrak ini, kami mensimulasikan semua gerakan yang mungkin bisa kami lakukan, yang memberi kami papan abstrak baru. Kemudian kami mensimulasikan penyelesaian semua kemungkinan langkah di papan
ini , dan seterusnya, sebanyak langkah yang Anda inginkan. Berikut ini adalah ilustrasi yang sangat baik tentang solusi serupa dari
freecodecamp.org :
Kami membuat grafik dari semua gerakan yang mungkin dilakukan oleh kedua pemain, dan menerapkan fungsi nilai untuk mengevaluasi bagaimana permainan berjalan.
Dan dalam hal ini, Dicey Dungeons berbeda dari minimax: minimax berasal dari teori matematika permainan, ia dirancang untuk menemukan serangkaian gerakan terbaik di dunia di mana lawan berusaha untuk memaksimalkan skornya. Algoritma disebut demikian karena meminimalkan kerugian pemain ketika lawan bermain untuk memaksimalkan kemenangannya.
Tapi apa yang terjadi di Dicey Dungeons? Sebenarnya, saya tidak peduli apa yang lawan saya lakukan. Agar permainan menjadi menarik, cukup bagi kecerdasan buatan untuk membuat langkah logis - untuk menentukan cara terbaik untuk menerapkan dadu pada senjata, sehingga pertempuran itu adil. Dengan kata lain, hanya "maks" yang penting bagi saya, tanpa "mini".
Yaitu, bagi AI Dicey Dungeons untuk membuat langkah yang baik, cukup bagi saya untuk membuat grafik gerakan yang mungkin dan menemukan papan yang memiliki skor tertinggi, dan kemudian membuat gerakan yang mengarah ke titik ini.
Langkah mudah musuh
Baiklah, mari kita beralih ke contoh! Mari kita lihat katak itu lagi. Bagaimana dia bisa
memutuskan apa yang harus dilakukan selanjutnya? Bagaimana dia
tahu bahwa tindakan yang dipilih adalah yang terbaik?
Bahkan, dia hanya punya dua pilihan. Tempatkan 1 di pedang lebar, dan 3 di perisai, atau lakukan yang sebaliknya. Dia jelas memutuskan bahwa lebih baik menempatkan 3 daripada 1. Tapi mengapa? Karena dia mempelajari semua hasil yang mungkin:
Jika Anda menempatkan 1 pada pedang, maka kita akan mendapatkan 438 poin. Jika Anda menempatkan 3 di atasnya, kami mendapatkan 558 poin. Hebat! Jadi, saya mendapatkan lebih banyak poin dengan menempatkan pada pedang 3, masalahnya selesai.
Dari mana kacamata ini berasal? Sistem penilaian di Dicey Dungeons saat ini mempertimbangkan aspek-aspek berikut:
- Kerusakan: Faktor paling penting adalah 100 poin untuk setiap titik kerusakan yang diberikan.
- Racun: Efek status penting yang AI anggap hampir sama pentingnya dengan kerusakan - 90 untuk setiap racun.
- Membuat efek status lainnya: misalnya, guncangan, terbakar, melemah, dll. Masing-masing harganya 50 poin.
- Efek status bonus: menambah pemain sendiri efek status positif, seperti pertahanan dan sejenisnya, masing-masing biaya 40 poin.
- Penggunaan senjata: menggunakan semua jenis senjata berharga 10 poin, karena jika tidak ada yang berhasil, AI harus mencoba menggunakan semuanya.
- Pengurangan hitung mundur: untuk mengaktifkan beberapa jenis senjata (misalnya, untuk Pea Shooter), jumlah total pada dadu cukup. Oleh karena itu, AI menerima 10 poin untuk setiap titik hitung yang dikurangi.
- Dots on Dice: AI mendapat 5 poin untuk setiap poin yang tidak digunakan pada dadu, yaitu 1 biaya 5 poin, dan 6 biaya 30 poin. Ini dilakukan agar AI memilih untuk tidak menggunakan kubus yang tidak perlu Anda gunakan, sehingga gerakannya menjadi sangat mirip dengan yang dilakukan manusia.
- Durasi: AI kehilangan 1 poin per giliran, sehingga gerakan panjang memiliki nilai yang sedikit lebih rendah daripada yang pendek. Hal ini dilakukan agar dengan adanya dua gerakan yang memiliki nilai yang sama, AI memilih yang paling pendek.
- Perawatan: biaya hanya 1 poin untuk satu titik kesehatan yang dipulihkan, karena walaupun saya ingin AI mempertimbangkan hal ini penting, saya tidak benar-benar memantau kesehatan saya. Selalu ada hal yang harus dilakukan dan lebih penting!
- Poin bonus: mereka dapat ditambahkan ke setiap gerakan untuk memaksa AI melakukan sesuatu yang dia tidak akan pernah lakukan sebaliknya. Digunakan dengan sangat moderat.
Dan akhirnya, ada dua kasus khusus - jika target yang diserang kehabisan kesehatan, maka harganya sejuta poin. Jika kesehatan berakhir dengan AI, maka harganya minus satu juta poin. Ini berarti bahwa AI tidak akan pernah secara tidak sengaja membunuh dirinya sendiri (misalnya, membayar mati dengan kesehatan yang sangat rendah), atau tidak pernah melewatkan langkah di mana ia dapat membunuh pemain.
Angka-angka ini tidak ideal - misalnya, masalah terbuka saat ini:
640 ,
642 ,
649 , tetapi ini tidak terlalu penting. Bahkan kira-kira angka yang akurat cukup untuk merangsang AI untuk melakukan lebih atau kurang dengan benar.
Gerakan musuh yang lebih sulit
Kasing katak sangat sederhana sehingga bahkan kode mengerikan saya dapat mengetahui semua opsi hanya dalam 0,017 detik. Tetapi kemudian situasinya menjadi lebih rumit. Mari kita lihat lagi contoh Jack semua perdagangan.
Pohon keputusannya “sedikit” lebih rumit:
Sayangnya, bahkan dalam kasus yang relatif sederhana, ledakan kompleksitas terjadi dengan cukup cepat. Dalam hal ini, dalam grafik kami, kami mendapatkan 2.670 node yang perlu diperiksa, dan ini membutuhkan waktu lebih lama daripada dalam kasus katak - mungkin satu atau dua detik.
Ini sebagian besar disebabkan oleh kompleksitas kombinatorial - misalnya, tidak masalah yang mana dari dua yang kami gunakan untuk meredakan kejutan pada awalnya, algoritma menganggap ini sebagai dua solusi terpisah, dan membuat pohon lengkap solusi percabangan untuk masing-masing. Akibatnya, kami mendapatkan cabang yang duplikasinya sama sekali tidak perlu. Ada juga masalah kombinatorial serupa ketika memilih blok untuk penebusan, untuk menghilangkan kejutan dari senjata, dan prosedur untuk penggunaannya.
Tetapi bahkan jika kita menemukan dan mengoptimalkan cabang yang tidak perlu seperti itu (yang saya lakukan sampai batas tertentu), akan selalu ada titik di mana kompleksitas dari semua permutasi yang memungkinkan solusi mengarah ke pohon keputusan besar, lambat, evaluasi yang akan memakan waktu tak terbatas. Jadi, ini adalah masalah serius pertama dari pendekatan ini. Ini satu lagi:
Kunci utama. Membagi kubus menjadi dua.Jenis persenjataan penting ini (dan yang serupa) menyebabkan masalah AI karena hasil penggunaannya tidak
pasti . Jika saya menempatkan enam di atasnya, saya bisa mendapatkan lima dan satu, atau empat dan dua, atau mungkin dua kali lipat. Saya tidak akan tahu ini sampai saya tahu, jadi sangat sulit untuk membuat rencana yang akan mempertimbangkan ini.
Untungnya, Dicey Dungeons memiliki solusi hebat untuk kedua masalah ini!
Solusi modern
Metode Monte Carlo Tree Search (MCTS) adalah algoritma pengambilan keputusan probabilistik. Di bawah ini adalah video yang agak aneh, yang, bagaimanapun, dengan sangat baik menjelaskan prinsip pengambilan keputusan berdasarkan metode Monte Carlo:
Bahkan, alih-alih menambahkan setiap gerakan yang mungkin ke grafik, MCTS memeriksa urutan gerakan acak, dan kemudian melacak langkah-langkah yang terbukti lebih baik. Berkat formula yang disebut Batas Keyakinan Tinggi, ia secara ajaib dapat menentukan cabang-cabang pohon keputusan mana yang "paling menjanjikan":
Ngomong-ngomong, saya mengambil formula ini dari
artikel yang sangat berguna tentang mencari pohon menggunakan metode Monte Carlo . Jangan tanya saya bagaimana cara kerjanya!
Hal yang luar biasa tentang MCTS adalah bahwa untuk menemukan solusi terbaik, kami biasanya tidak perlu melalui pencarian yang bodoh tentang semuanya, dan kami dapat menggunakan sistem simulasi papan / pemindahan abstrak yang sama seperti pada minimax. Artinya, kami agak menggunakan kedua algoritma. Ini persis skema yang saya gunakan di Dicey Dungeons. Pertama, dia mencoba menyelesaikan penyebaran lengkap pohon keputusan, yang biasanya tidak memakan banyak waktu dan mengarah pada hasil terbaik. Tetapi jika pohon itu tampak terlalu besar, maka kita kembali menggunakan MCTS.
MCTS memiliki dua fitur yang sangat keren yang sempurna untuk Dicey Dungeons:
Pertama, metode ini bekerja secara ideal dengan ketidakpastian. Karena ini dilakukan berulang-ulang, mengumpulkan data dari setiap proses, saya hanya membiarkannya mensimulasikan gerakan yang tidak terdefinisi, misalnya, menggunakan kunci utama, dengan cara alami, dan setelah banyak berjalan metode ini menciptakan rentang poin yang cukup benar yang diperoleh sebagai hasil dari langkah ini.
Kedua, dia bisa memberi saya solusi parsial. Bahkan, ketika bekerja dengan MCTS, Anda dapat melakukan simulasi sebanyak yang Anda suka. Secara teoritis, jika dilakukan tanpa henti, itu akan menyatu dengan hasil yang sama persis dengan minimax. Namun, yang lebih penting bagi saya adalah saya dapat menggunakan MCTS untuk mendapatkan solusi yang baik dalam waktu berpikir yang terbatas. Semakin banyak pencarian yang kami lakukan, semakin baik "solusi" akan ditemukan, tetapi dalam kasus Dicey Dungeons seringkali hanya beberapa ratus pencarian yang cukup, yang mengambil sebagian kecil dari satu detik.
Topik terkait yang menarik
Jadi, beginilah cara musuh di Dicey Dungeons memutuskan cara membunuhmu! Saya ingin menambahkan sistem ini ke versi selanjutnya dari game v0.15!
Dari mana grafik yang saya tunjukkan berasal, termasuk di twitter:
Saya membuatnya dengan menulis eksportir untuk
GraphML , format file grafik sumber terbuka yang dapat dibaca oleh banyak alat yang berbeda. (Saya menggunakan
YEd luar
biasa , yang sangat saya rekomendasikan.)
Bagian dari solusi untuk masalah ini adalah untuk memungkinkan AI untuk mensimulasikan gerakan, yang dengan sendirinya merupakan teka-teki yang menarik. Akibatnya, saya menerapkan sistem scripting tindakan. Sekarang lawan menggunakan berbagai jenis senjata. mereka mengeksekusi skrip kecil ini:
Script-script kecil ini dijalankan oleh parser
hscript dan penerjemah ekspresi berdasarkan haxe. Bagian ini sulit untuk diimplementasikan, tetapi upaya itu terbayar: itu membuat game super nyaman untuk membuat mod. Saya berharap bahwa setelah rilis game, orang dapat menggunakan sistem ini untuk mengembangkan senjata mereka sendiri, yaitu, mereka dapat menambah game hampir semua yang mereka bisa bayangkan. Selain itu, karena AI cukup pintar untuk mengevaluasi setiap tindakan yang ditransfer ke sana, musuh akan dapat mengetahui cara menggunakan senjata yang dimodifikasi yang akan dibuat oleh pemain!