O'yinlarda sun'iy intellekt haqida qiziqarli materiallarga duch keldim. Oddiy misollar yordamida sun'iy intellekt haqidagi asosiy narsalarni tushuntirish va ichida uni qulay ishlab chiqish va loyihalash uchun juda ko'p foydali vositalar va usullar mavjud. Ularni qanday, qayerda va qachon ishlatish ham mavjud.
Ko'pgina misollar psevdokodda yozilgan, shuning uchun ilg'or dasturlash bilimlari talab qilinmaydi. Kesim ostida rasmlar va giflar bilan 35 varaqli matn mavjud, shuning uchun tayyor bo'ling.
UPD. Men kechirim so'rayman, lekin men allaqachon Habré-da ushbu maqolani o'zim tarjima qilganman . Uning versiyasini o'qishingiz mumkin , lekin negadir maqola mendan o'tib ketdi (qidiruvdan foydalandim, lekin biror narsa noto'g'ri ketdi). Va men o'yinni rivojlantirishga bag'ishlangan blogda yozayotganim sababli, tarjimaning o'z versiyasini obunachilar uchun qoldirishga qaror qildim (ba'zi fikrlar boshqacha formatlangan, ba'zilari ishlab chiquvchilarning maslahati bilan ataylab o'tkazib yuborilgan).
AI nima?
O'yin AI ob'ekt joylashgan sharoitga qarab qanday harakatlarni bajarishi kerakligiga e'tibor qaratadi. Bu odatda "aqlli agent" boshqaruvi deb ataladi, bu erda agent o'yinchi xarakteri, transport vositasi, bot yoki ba'zan mavhumroq narsa: butun bir ob'ektlar guruhi yoki hatto tsivilizatsiya. Har bir holatda u o'z muhitini ko'rishi, unga asoslanib qarorlar qabul qilishi va ularga muvofiq harakat qilishi kerak bo'lgan narsadir. Bu Sense/Think/Act tsikli deb ataladi:
- Sezgi: Agent o'z muhitidagi xatti-harakatlariga ta'sir qilishi mumkin bo'lgan narsalar haqida ma'lumot topadi yoki oladi (yaqin atrofdagi tahdidlar, to'planishi kerak bo'lgan narsalar, qiziqarli joylar).
- O'ylab ko'ring: Agent qanday munosabatda bo'lishni o'zi hal qiladi (elementlarni yig'ish xavfsizmi yoki birinchi navbatda u jang qilish/yashirish kerakmi yoki yo'qligini hisobga oladi).
- Harakat: agent oldingi qarorni amalga oshirish uchun harakatlarni amalga oshiradi (dushman yoki ob'ekt tomon harakat qilishni boshlaydi).
- ... endi vaziyat belgilarning harakatlari tufayli o'zgardi, shuning uchun tsikl yangi ma'lumotlar bilan takrorlanadi.
AI odatda tsiklning Sense qismiga e'tibor qaratadi. Misol uchun, avtonom avtomobillar yo'lni suratga oladi, ularni radar va lidar ma'lumotlari bilan birlashtiradi va ularni sharhlaydi. Bu, odatda, kiruvchi ma'lumotlarni qayta ishlovchi va unga ma'no beradigan, "sizdan 20 yard oldinda yana bir mashina bor" kabi semantik ma'lumotlarni chiqaradigan mashinani o'rganish orqali amalga oshiriladi. Bu tasniflash muammolari deb ataladi.
O'yinlar ma'lumot olish uchun murakkab tizimga muhtoj emas, chunki ma'lumotlarning aksariyati allaqachon uning ajralmas qismidir. Oldinda dushman bor yoki yo'qligini aniqlash uchun tasvirni aniqlash algoritmlarini ishga tushirishning hojati yo'q - o'yin allaqachon biladi va ma'lumotni to'g'ridan-to'g'ri qaror qabul qilish jarayoniga yuboradi. Shuning uchun, tsiklning Sense qismi ko'pincha "O'ylang va harakat qiling" qismiga qaraganda ancha sodda.
O'yin AI cheklovlari
AI kuzatilishi kerak bo'lgan bir qator cheklovlarga ega:
- AIni mashinani o'rganish algoritmi kabi oldindan o'rgatish kerak emas. Rivojlanish jarayonida o'n minglab o'yinchilarni kuzatish va ularga qarshi o'ynashning eng yaxshi usulini o'rganish uchun neyron tarmoqni yozishning ma'nosi yo'q. Nega? Chunki o'yin chiqarilmagan va o'yinchilar yo'q.
- O'yin qiziqarli va qiyin bo'lishi kerak, shuning uchun agentlar odamlarga qarshi eng yaxshi yondashuvni topa olmasligi kerak.
- O'yinchilar o'zlarini haqiqiy odamlarga qarshi o'ynagandek his qilishlari uchun agentlar realistik ko'rinishi kerak. AlphaGo dasturi odamlardan ustun keldi, ammo tanlangan qadamlar o'yinni an'anaviy tushunishdan juda uzoq edi. Agar o'yin insoniy raqibni taqlid qilsa, bu tuyg'u bo'lmasligi kerak. Algoritmni o'zgartirish kerak, shunda u ideal emas, balki ishonchli qarorlar qabul qiladi.
- AI real vaqtda ishlashi kerak. Bu algoritm qaror qabul qilish uchun uzoq vaqt davomida protsessordan foydalanishni monopoliya qila olmasligini anglatadi. Hatto 10 millisekund ham juda uzun, chunki ko'pchilik o'yinlarga barcha ishlov berish va keyingi grafik ramkaga o'tish uchun atigi 16-33 millisekund kerak bo'ladi.
- Ideal holda, tizimning hech bo'lmaganda bir qismi ma'lumotlarga asoslangan bo'lishi kerak, shunda kodlovchi bo'lmaganlar o'zgartirishlar kiritishlari va sozlashlar tezroq amalga oshirilishi mumkin.
Keling, butun Sense/Think/Act tsiklini qamrab oluvchi AI yondashuvlarini ko'rib chiqaylik.
Asosiy qarorlar qabul qilish
Eng oddiy o'yindan boshlaylik - Pong. Maqsad: eshkakni shunday harakatlantiring, shunda to'p uning yonidan uchib o'tmaydi. Bu tennisga o'xshaydi, agar to'pga urmasangiz yutqazasiz. Bu erda AI nisbatan oson vazifaga ega - platformani qaysi yo'nalishda harakatlantirishni hal qilish.
Shartli gaplar
Pongdagi AI uchun eng aniq yechim har doim platformani to'pning ostiga qo'yishga harakat qilishdir.
Buning uchun psevdokodda yozilgan oddiy algoritm:
o'yin ishlayotganda har bir kadr/yangilanish:
agar to'p eshkakning chap tomonida bo'lsa:
belkurakni chapga siljiting
Aks holda, agar to'p qayiqning o'ng tomonida bo'lsa:
belkurakni o'ngga siljiting
Agar platforma to'p tezligida harakat qilsa, bu Pongdagi AI uchun ideal algoritmdir. Agar agent uchun juda ko'p ma'lumotlar va mumkin bo'lgan harakatlar bo'lmasa, hech narsani murakkablashtirishning hojati yo'q.
Ushbu yondashuv shunchalik soddaki, butun his qilish/o'ylash/harakat qilish sikli deyarli sezilmaydi. Ammo u erda:
- Sense qismi ikkita if gapdan iborat. O'yin to'p qayerda va platforma qayerda ekanligini biladi, shuning uchun AI bu ma'lumot uchun unga qaraydi.
- Fikrlash qismi ham ikkita if iborasiga kiritilgan. Ular ikkita echimni o'z ichiga oladi, bu holda ular bir-birini istisno qiladilar. Natijada, uchta harakatdan biri tanlanadi - platformani chapga siljiting, o'ngga siljiting yoki u allaqachon to'g'ri joylashtirilgan bo'lsa, hech narsa qilmang.
- Akt qismi Move Paddle Left va Move Paddle Right iboralarida topilgan. O'yin dizayniga qarab, ular platformani bir zumda yoki ma'lum bir tezlikda harakatlantirishi mumkin.
Bunday yondashuvlar reaktiv deb ataladi - dunyoning hozirgi holatiga munosabat bildiradigan va choralar ko'radigan oddiy qoidalar to'plami (bu holda koddagi bayonotlar) mavjud.
Qaror daraxti
Pong misoli aslida qarorlar daraxti deb ataladigan rasmiy AI kontseptsiyasiga teng. Algoritm "barg" ga erishish uchun u orqali o'tadi - qanday harakat qilish kerakligi haqidagi qaror.
Keling, platformamiz algoritmi uchun qarorlar daraxtining blok diagrammasini tuzamiz:
Daraxtning har bir qismi tugun deb ataladi - AI bunday tuzilmalarni tasvirlash uchun grafiklar nazariyasidan foydalanadi. Ikki turdagi tugunlar mavjud:
- Qaror qabul qilish tugunlari: har bir muqobil alohida tugun sifatida taqdim etilgan ba'zi shartlarni sinab ko'rish asosida ikkita alternativa o'rtasida tanlov.
- Yakuniy tugunlar: yakuniy qarorni ifodalovchi bajariladigan harakat.
Algoritm birinchi tugundan (daraxtning "ildizi") boshlanadi. U qaysi tugunga borish haqida qaror qabul qiladi yoki tugunda saqlangan amalni bajaradi va undan chiqadi.
Qarorlar daraxti oldingi bo'limdagi if iboralari bilan bir xil vazifani bajarishidan qanday foyda bor? Bu erda har bir qaror faqat bitta shart va ikkita mumkin bo'lgan natijaga ega bo'lgan umumiy tizim mavjud. Bu ishlab chiquvchiga daraxtdagi qarorlarni ifodalovchi maʼlumotlardan uni qattiq kodlashsiz AI yaratish imkonini beradi. Keling, uni jadval shaklida taqdim etamiz:
Kod tomonida siz satrlarni o'qish tizimiga ega bo'lasiz. Ularning har biri uchun tugun yarating, ikkinchi ustunga asoslangan qaror mantig'ini va uchinchi va to'rtinchi ustunlar asosida tugunlarni bog'lang. Siz hali ham shartlar va harakatlarni dasturlashingiz kerak, ammo endi o'yinning tuzilishi yanada murakkab bo'ladi. Bu erda siz qo'shimcha qarorlar va harakatlar qo'shasiz va keyin daraxt ta'rifi matn faylini oddiygina tahrirlash orqali butun AIni moslashtirasiz. Keyinchalik, siz faylni o'yin dizayneriga o'tkazasiz, u o'yinni qayta kompilyatsiya qilmasdan yoki kodni o'zgartirmasdan xatti-harakatni o'zgartirishi mumkin.
Qaror daraxtlari ko'p misollar to'plamidan avtomatik ravishda qurilganda (masalan, ID3 algoritmidan foydalangan holda) juda foydali. Bu ularni olingan ma'lumotlar asosida vaziyatlarni tasniflash uchun samarali va yuqori samarali vositaga aylantiradi. Biroq, biz agentlar uchun harakatlarni tanlash uchun oddiy tizimdan tashqariga chiqamiz.
Skriptlar
Biz oldindan yaratilgan shartlar va harakatlardan foydalanadigan qarorlar daraxti tizimini tahlil qildik. AIni loyihalashtirgan odam daraxtni xohlagancha tashkil qilishi mumkin, ammo u baribir hammasini dasturlashtirgan koderga tayanishi kerak. Agar dizaynerga o'z sharoitlari yoki harakatlarini yaratish uchun vositalarni bera olsak-chi?
Dasturchi Is Ball Left Of Paddle va Is Ball Right Of Paddle shartlari uchun kod yozishi shart emasligi uchun u dizayner ushbu qiymatlarni tekshirish shartlarini yozadigan tizim yaratishi mumkin. Keyin qarorlar daraxti ma'lumotlari quyidagicha ko'rinadi:
Bu mohiyatan birinchi jadvaldagi bilan bir xil, ammo yechimlarning o'z kodlari bor, biroz if iborasining shartli qismiga o'xshaydi. Kod tomonida, bu qaror tugunlari uchun ikkinchi ustunda o'qiladi, lekin bajarish uchun ma'lum shartni izlash o'rniga (Is Ball Left Of Paddle), u shartli ifodani baholaydi va mos ravishda rost yoki noto'g'ri qaytaradi. Bu Lua yoki Angelscript skript tili yordamida amalga oshiriladi. Ulardan foydalanib, ishlab chiquvchi o'z o'yinidagi ob'ektlarni (to'p va belkurak) olishi va skriptda mavjud bo'lgan o'zgaruvchilarni yaratishi mumkin (ball.position). Bundan tashqari, skript tili C++ ga qaraganda sodda. Bu to'liq kompilyatsiya bosqichini talab qilmaydi, shuning uchun u o'yin mantig'ini tezda sozlash uchun ideal va "koder bo'lmaganlar" ga kerakli funktsiyalarni o'zlari yaratishga imkon beradi.
Yuqoridagi misolda skript tili faqat shartli ifodani baholash uchun ishlatiladi, lekin u amallar uchun ham ishlatilishi mumkin. Masalan, Move Paddle Right ma'lumotlari skript bayonotiga aylanishi mumkin (ball.position.x += 10). Shunday qilib, harakat ham skriptda aniqlangan bo'lib, Move Paddle Right dasturini talab qilmasdan.
Siz yanada uzoqroqqa borib, butun qaror daraxtini skript tilida yozishingiz mumkin. Bu qattiq kodlangan shartli bayonotlar ko'rinishidagi kod bo'ladi, lekin ular tashqi skript fayllarida joylashgan bo'ladi, ya'ni ularni butun dasturni qayta kompilyatsiya qilmasdan o'zgartirish mumkin. Turli AI reaktsiyalarini tezda sinab ko'rish uchun o'yin davomida skript faylini tez-tez tahrirlashingiz mumkin.
Hodisaga javob
Yuqoridagi misollar Pong uchun juda mos keladi. Ular doimiy ravishda Sense/Think/Act siklini boshqaradi va dunyoning eng so'nggi holatiga asoslanib harakat qiladi. Ammo murakkabroq o'yinlarda siz individual voqealarga munosabat bildirishingiz kerak va hamma narsani birdaniga baholamasligingiz kerak. Pong bu holatda allaqachon yomon misoldir. Keling, boshqasini tanlaylik.
Otishmani tasavvur qiling-a, dushmanlar o'yinchini aniqlamaguncha harakatsiz, shundan so'ng ular o'zlarining "mutaxassisligi" ga qarab harakat qilishadi: kimdir "shoshilish" ga yuguradi, kimdir uzoqdan hujum qiladi. Bu hali ham asosiy reaktiv tizim - "agar o'yinchi aniqlangan bo'lsa, biror narsa qiling" - lekin uni mantiqan o'yinchi ko'rgan hodisasi va Reaktsiyaga bo'lish mumkin (javobni tanlang va uni bajaring).
Bu bizni Sense/Think/Act tsikliga qaytaradi. Biz Sense qismini kodlashimiz mumkin, u har bir kadrni AI pleerni ko'rishini tekshiradi. Agar yo'q bo'lsa, hech narsa sodir bo'lmaydi, lekin agar u ko'rsa, Player Seen hodisasi yaratiladi. Kodda "O'yinchi ko'rgan hodisasi sodir bo'lganda, bajaring" degan alohida bo'lim bo'ladi, bu erda "O'ylang va harakat qiling" qismlariga murojaat qilishingiz kerak bo'lgan javob. Shunday qilib, siz Player Seen hodisasiga reaktsiyalarni o'rnatasiz: "shoshilinch" xarakter uchun - ChargeAndAttack va snayper uchun - HideAndSnipe. Ushbu munosabatlar qayta kompilyatsiya qilmasdan tez tahrirlash uchun ma'lumotlar faylida yaratilishi mumkin. Bu yerda skript tilidan ham foydalanish mumkin.
Qiyin qarorlar qabul qilish
Oddiy reaktsiya tizimlari juda kuchli bo'lsa-da, ular etarli bo'lmagan ko'plab vaziyatlar mavjud. Ba'zida agent hozir nima qilayotganiga qarab turli qarorlar qabul qilishingiz kerak bo'ladi, lekin buni shart sifatida tasavvur qilish qiyin. Ba'zan ularni qaror daraxti yoki skriptda samarali ko'rsatish uchun juda ko'p shartlar mavjud. Ba'zan keyingi qadam haqida qaror qabul qilishdan oldin vaziyat qanday o'zgarishini oldindan baholashingiz kerak. Ushbu muammolarni hal qilish uchun yanada murakkab yondashuvlar kerak.
Cheklangan holat mashinasi
Cheklangan holat mashinasi yoki FSM (cheklangan holat mashinasi) bizning agentimiz hozirda bir nechta mumkin bo'lgan holatlardan birida ekanligini va u bir holatdan boshqasiga o'tishi mumkinligini aytish usulidir. Bunday shtatlarning ma'lum soni bor - shuning uchun nomi. Hayotdan eng yaxshi misol - svetofor. Turli joylarda turli xil yorug'lik ketma-ketligi mavjud, ammo printsip bir xil - har bir holat nimanidir ifodalaydi (to'xtash, yurish va h.k.). Svetofor istalgan vaqtda faqat bitta holatda bo'ladi va oddiy qoidalar asosida biridan ikkinchisiga o'tadi.
Bu o'yinlardagi NPClar bilan o'xshash voqea. Misol uchun, quyidagi holatlarga ega bo'lgan qo'riqchini olaylik:
- Patrullik.
- Hujum.
- Qochish.
Va uning holatini o'zgartirish uchun bu shartlar:
- Agar qo'riqchi dushmanni ko'rsa, u hujum qiladi.
- Agar qo'riqchi hujum qilsa, lekin endi dushmanni ko'rmasa, u yana patrulga qaytadi.
- Agar qo'riqchi hujum qilsa, lekin og'ir yaralangan bo'lsa, u qochib ketadi.
Shuningdek, siz qo'riqchi holati o'zgaruvchisi va turli tekshiruvlar bilan if-bayonotlarini yozishingiz mumkin: yaqin atrofda dushman bormi, NPCning sog'liq darajasi qanday va hokazo. Yana bir nechta holatlarni qo'shamiz:
- Bekorchilik - patrullar o'rtasida.
- Qidiruv - aniqlangan dushman g'oyib bo'lganda.
- Yordam topish - dushman aniqlanganda, lekin yolg'iz jang qilish uchun juda kuchli.
Ularning har biri uchun tanlov cheklangan - masalan, agar sog'lig'i past bo'lsa, qo'riqchi yashirin dushmanni qidirmaydi.
Axir, "agar" larning katta ro'yxati bor. , Bu "juda mashaqqatli bo'lib qolishi mumkin, shuning uchun biz holatlar va davlatlar o'rtasidagi o'tishlarni yodda tutishimizga imkon beradigan usulni rasmiylashtirishimiz kerak. Buning uchun biz barcha shtatlarni hisobga olamiz va har bir shtat ostida biz boshqa davlatlarga barcha o'tishlarni ular uchun zarur bo'lgan shartlar bilan birga ro'yxatda yozamiz.
Bu holat o'tish jadvali - FSMni ifodalashning keng qamrovli usuli. Keling, diagramma chizamiz va NPC xatti-harakati qanday o'zgarishi haqida to'liq ma'lumotga ega bo'laylik.
Diagramma mavjud vaziyatdan kelib chiqqan holda ushbu agent uchun qaror qabul qilishning mohiyatini aks ettiradi. Bundan tashqari, har bir o'q, agar yonidagi shart to'g'ri bo'lsa, holatlar orasidagi o'tishni ko'rsatadi.
Har bir yangilanishda biz agentning joriy holatini tekshiramiz, o'tishlar ro'yxatini ko'rib chiqamiz va agar o'tish shartlari bajarilsa, u yangi holatni qabul qiladi. Misol uchun, har bir kadr 10 soniyalik taymer muddati tugaganligini tekshiradi va agar shunday bo'lsa, qo'riqchi Bo'sh turgan holatdan Patrulga o'tadi. Xuddi shu tarzda, Hujumchi holati agentning sog'lig'ini tekshiradi - agar u past bo'lsa, u qochib ketish holatiga o'tadi.
Bu davlatlar o'rtasidagi o'tishlarni boshqarish, lekin shtatlarning o'zlari bilan bog'liq xatti-harakatlar haqida nima deyish mumkin? Muayyan davlat uchun haqiqiy xatti-harakatni amalga oshirish nuqtai nazaridan, odatda ikkita turdagi "kanca" mavjud bo'lib, biz FSMga harakatlarni tayinlaymiz:
- Joriy holat uchun vaqti-vaqti bilan bajaradigan harakatlar.
- Bir holatdan ikkinchi holatga o'tishda biz qiladigan harakatlar.
Birinchi turga misollar. Patrul holati agentni har bir kadr patrul marshruti bo'ylab harakatlantiradi. Hujum qilayotgan davlat har bir kadrda hujumni boshlashga harakat qiladi yoki bu mumkin bo'lgan holatga o'tadi.
Ikkinchi tur uchun o'tishni ko'rib chiqing "agar dushman ko'rinadigan bo'lsa va dushman juda kuchli bo'lsa, "Yordamni topish" holatiga o'ting. Agent yordam uchun qaerga borishni tanlashi va bu ma'lumotni saqlashi kerak, shunda "Yordamni topish" holati qayerga borishni biladi. Yordam topilgach, agent hujum qilish holatiga qaytadi. Shu nuqtada, u ittifoqchiga tahdid haqida aytib berishni xohlaydi, shuning uchun NotifyFriendOfThreat harakati sodir bo'lishi mumkin.
Yana bir bor, biz ushbu tizimga Sense/Think/Act tsikli ob'ektivi orqali qarashimiz mumkin. Sezgi o'tish mantig'i tomonidan ishlatiladigan ma'lumotlarda mujassamlangan. O'ylab ko'ring - o'tishlar har bir shtatda mavjud. Akt esa vaqti-vaqti bilan shtat ichida yoki davlatlar o'rtasidagi o'tishlarda amalga oshiriladigan harakatlar orqali amalga oshiriladi.
Ba'zida doimiy ovoz berish shartlari qimmatga tushishi mumkin. Misol uchun, agar har bir agent dushmanlarni ko'ra oladimi yoki yo'qligini aniqlash uchun har bir kadr murakkab hisob-kitoblarni amalga oshirsa va Patrullik holatidan hujumga o'tish holatiga o'tishi mumkinmi yoki yo'qmi, bu protsessor uchun juda ko'p vaqtni oladi.
Dunyo holatidagi muhim o'zgarishlarni ular sodir bo'lganda qayta ishlanadigan hodisalar deb hisoblash mumkin. FSM o'tish holatini tekshirish o'rniga "mening agentim o'yinchini ko'ra oladimi?" Har bir kadrda, alohida tizimni kamroq tekshirish uchun sozlanishi mumkin (masalan, soniyada 5 marta). Natijada, tekshiruvdan o'tganda Player Seen beriladi.
Bu FSMga uzatiladi, u endi Player Seen hodisasi qabul qilingan shartga o'tishi va shunga mos ravishda javob berishi kerak. Natijada, javob berishdan oldin deyarli sezilmaydigan kechikish bundan mustasno, xuddi shunday. Ammo Sense qismini dasturning alohida qismiga ajratish natijasida ishlash yaxshilandi.
Ierarxik chekli holat mashinasi
Biroq, katta FSMlar bilan ishlash har doim ham qulay emas. Agar biz MeleeAttacking va RangedAttacking-ni ajratish uchun hujum holatini kengaytirmoqchi bo'lsak, hujum holatiga olib keladigan barcha boshqa holatlardan (hozirgi va kelajak) o'tishlarni o'zgartirishimiz kerak bo'ladi.
Ehtimol, bizning misolimizda takroriy o'tishlar juda ko'p ekanligini payqadingiz. Boʻsh rejimdagi oʻtishlarning aksariyati Patrul holatidagi oʻtishlar bilan bir xil. O'zimizni takrorlamaslik yaxshi bo'lardi, ayniqsa shunga o'xshash holatlarni ko'proq qo'shsak. Idling va Patrullashni "jangovar bo'lmagan" umumiy yorlig'i ostida guruhlash mantiqan to'g'ri keladi, bu erda jangovar holatlarga o'tishning faqat bitta umumiy to'plami mavjud. Agar biz ushbu yorliqni davlat deb hisoblasak, Idling va Patrolling substatlarga aylanadi. Yangi jangovar bo'lmagan substate uchun alohida o'tish jadvalidan foydalanishga misol:
Asosiy shtatlar:
Jangdan tashqari holat:
Va diagramma shaklida:
Bu xuddi shu tizim, lekin yangi jangovar bo'lmagan holatga ega, unga Idling va Patrolling kiradi. Har bir davlat substatlari bilan FSM ni o'z ichiga olgan holda (va bu substatlar, o'z navbatida, o'z FSMlarini o'z ichiga oladi - va shunga o'xshash vaqt kerak bo'lganda), biz ierarxik chekli holat mashinasi yoki HFSM (ierarxik chekli holat mashinasi) ni olamiz. Jangovar bo'lmagan holatni guruhlash orqali biz bir qator ortiqcha o'tishlarni kesib tashladik. Umumiy o'tishlarga ega bo'lgan har qanday yangi shtatlar uchun ham xuddi shunday qilishimiz mumkin. Misol uchun, agar biz kelajakda hujum qilish holatini Melee Attacking va Missile Attacking shtatlariga kengaytirsak, ular dushmangacha bo'lgan masofa va o'q-dorilar mavjudligiga qarab bir-biridan o'tadigan substatlar bo'ladi. Natijada, murakkab xatti-harakatlar va pastki xatti-harakatlar minimal takroriy o'tishlar bilan ifodalanishi mumkin.
Xulq-atvor daraxti
HFSM bilan xatti-harakatlarning murakkab kombinatsiyasi oddiy tarzda yaratiladi. Biroq, o'tish qoidalari shaklida qaror qabul qilish hozirgi holat bilan chambarchas bog'liq bo'lgan engil qiyinchilik mavjud. Va ko'p o'yinlarda aynan shu narsa kerak bo'ladi. Va davlat ierarxiyasidan ehtiyotkorlik bilan foydalanish o'tishni takrorlash sonini kamaytirishi mumkin. Lekin ba'zida sizga qaysi shtatda bo'lishingizdan qat'iy nazar ishlaydigan yoki deyarli har qanday shtatda amal qiladigan qoidalar kerak bo'ladi. Misol uchun, agar agentning sog'lig'i 25% ga tushib qolsa, siz uning jangda, bo'sh yoki gaplashayotganidan qat'i nazar, qochishini xohlaysiz - bu shartni har bir shtatga qo'shishingiz kerak bo'ladi. Va agar sizning dizayneringiz keyinchalik sog'liqning past chegarasini 25% dan 10% gacha o'zgartirmoqchi bo'lsa, buni yana qilish kerak bo'ladi.
Ideal holda, bu vaziyat faqat bir joyda o'zgarishlar qilish va o'tish shartlariga tegmaslik uchun "qaysi holatda bo'lish" haqidagi qarorlar shtatlardan tashqarida bo'lgan tizimni talab qiladi. Bu erda xatti-harakatlar daraxtlari paydo bo'ladi.
Ularni amalga oshirishning bir necha usullari mavjud, ammo mohiyati hamma uchun taxminan bir xil va qarorlar daraxtiga o'xshaydi: algoritm "ildiz" tugunidan boshlanadi va daraxtda qarorlar yoki harakatlarni ifodalovchi tugunlar mavjud. Biroq, bir nechta asosiy farqlar mavjud:
- Endi tugunlar uchta qiymatdan birini qaytaradi: Muvaffaqiyatli (agar ish tugallangan bo'lsa), Muvaffaqiyatsiz (agar uni ishga tushirishning iloji bo'lmasa) yoki Ishlayotgan (agar u ishlayotgan bo'lsa va yakuniy natija bo'lmasa).
- Ikki muqobil o'rtasida tanlash uchun boshqa qaror tugunlari yo'q. Buning o'rniga, ular bitta bola tuguniga ega bo'lgan Dekorator tugunlari. Agar ular muvaffaqiyatli bo'lsa, ular yagona tugunni bajaradilar.
- Harakatlarni bajaradigan tugunlar bajarilayotgan amallarni ifodalash uchun Running qiymatini qaytaradi.
Ushbu kichik tugunlar to'plami ko'p sonli murakkab xatti-harakatlarni yaratish uchun birlashtirilishi mumkin. Keling, oldingi misoldagi HFSM qo'riqchisini xatti-harakatlar daraxti sifatida tasavvur qilaylik:
Ushbu tuzilma bilan Bo'sh turgan/patrullik holatidan hujumga yoki boshqa davlatlarga aniq o'tish bo'lmasligi kerak. Agar dushman ko'rinadigan bo'lsa va qahramonning sog'lig'i past bo'lsa, u ilgari qaysi tugunni bajarganligidan qat'i nazar, qochib ketish tugunida to'xtaydi - Patrullik, Bo'sh turish, Hujum yoki boshqa.
Xulq-atvor daraxtlari murakkab - ularni yaratishning ko'plab usullari mavjud va dekorativlar va murakkab tugunlarning to'g'ri kombinatsiyasini topish qiyin bo'lishi mumkin. Daraxtni qanchalik tez-tez tekshirish kerakligi haqida ham savollar bor - biz uning har bir qismidan o'tishni xohlaymizmi yoki faqat shartlardan biri o'zgarganda? Tugunlarga tegishli holatni qanday saqlaymiz - biz 10 soniya davomida ishlamay qolganimizni qanday bilamiz yoki ketma-ketlikni to'g'ri qayta ishlashimiz uchun oxirgi marta qaysi tugunlar bajarilganligini qanday bilamiz?
Shuning uchun ko'plab ilovalar mavjud. Misol uchun, ba'zi tizimlar dekorativ tugunlarni inline dekorativlar bilan almashtirdilar. Dekorator shartlari o'zgarganda ular daraxtni qayta baholaydilar, tugunlarga qo'shilishga yordam beradilar va davriy yangilanishlarni taqdim etadilar.
Utilitlarga asoslangan tizim
Ba'zi o'yinlar juda ko'p turli xil mexanikaga ega. Ular oddiy va umumiy o'tish qoidalarining barcha afzalliklarini olishlari ma'qul, lekin bu, albatta, to'liq xulq-atvor daraxti shaklida emas. Aniq tanlovlar to'plami yoki mumkin bo'lgan harakatlar daraxtiga ega bo'lish o'rniga, barcha harakatlarni tekshirish va hozirgi vaqtda eng mosini tanlash osonroq.
Utility-ga asoslangan tizim bunga yordam beradi. Bu agent turli harakatlarga ega bo'lgan va har birining nisbiy foydaliligiga qarab qaysilarini bajarishni tanlaydigan tizimdir. Bu erda foydalilik agent uchun ushbu harakatni bajarish qanchalik muhim yoki kerakli ekanligini o'zboshimchalik bilan o'lchovidir.
Joriy holat va atrof-muhitga asoslangan harakatning hisoblangan foydasi, agent istalgan vaqtda tekshirishi va eng mos keladigan boshqa holatni tanlashi mumkin. Bu FSM ga o'xshaydi, o'tishlar har bir potentsial holat, shu jumladan joriy holat uchun taxmin bilan belgilanadigan hollar bundan mustasno. Esda tutingki, biz davom etish uchun eng foydali amalni tanlaymiz (yoki uni allaqachon tugatgan bo'lsak, qolamiz). Ko'proq xilma-xillik uchun bu kichik ro'yxatdagi muvozanatli, ammo tasodifiy tanlov bo'lishi mumkin.
Tizim foydali qiymatlarning ixtiyoriy diapazonini tayinlaydi, masalan, 0 dan (mutlaqo istalmagan) 100 (to'liq istakli) gacha. Har bir harakat ushbu qiymatni hisoblashga ta'sir qiluvchi bir qator parametrlarga ega. Bizning vasiy misolimizga qaytsak:
Harakatlar o'rtasidagi o'tishlar noaniq - har qanday holat boshqasiga ergashishi mumkin. Harakat ustuvorliklari qaytarilgan yordamchi qiymatlarda topiladi. Agar dushman ko'rinsa va u kuchli bo'lsa va qahramonning sog'lig'i past bo'lsa, Fleeing va FindingHelp ikkalasi ham nolga teng bo'lmagan yuqori qiymatlarni qaytaradi. Bunday holda, FindingHelp har doim yuqoriroq bo'ladi. Xuddi shunday, jangovar bo'lmagan harakatlar hech qachon 50 dan ortiq qaytarilmaydi, shuning uchun ular har doim jangovar harakatlardan past bo'ladi. Harakatlarni yaratish va ularning foydaliligini hisoblashda buni hisobga olishingiz kerak.
Bizning misolimizda, harakatlar qat'iy doimiy qiymatni yoki ikkita sobit qiymatdan birini qaytaradi. Haqiqiyroq tizim qiymatlarning uzluksiz diapazonidan hisobni qaytaradi. Masalan, agar agentning sog'lig'i past bo'lsa, "Qochib ketish" harakati yuqori foydali qiymatlarni qaytaradi va agar dushman juda kuchli bo'lsa, "Hujum qilish" harakati pastroq foydali qiymatlarni qaytaradi. Shu sababli, agent dushmanni mag'lub etish uchun sog'lig'i etarli emasligini his qilgan har qanday vaziyatda Qochib ketish harakati hujum qilishdan ustun turadi. Bu xatti-harakatlar daraxti yoki FSMga qaraganda, bu yondashuvni yanada moslashuvchan va o'zgaruvchan qilib, har qanday mezonlar asosida harakatlarga ustuvorlik berishga imkon beradi.
Har bir harakat dasturni hisoblash uchun juda ko'p shartlarga ega. Ular skript tilida yoki bir qator matematik formulalar sifatida yozilishi mumkin. Qahramonning kundalik tartibini taqlid qiluvchi Sims qo'shimcha hisob-kitob qatlamini qo'shadi - agent foydali xizmatlar reytingiga ta'sir qiluvchi bir qator "motivatsiyalar" oladi. Agar belgi och bo'lsa, vaqt o'tishi bilan ular yanada och bo'ladi va EatFood harakatining foydali qiymati personaj buni bajarmaguncha ortadi, ochlik darajasini pasaytiradi va EatFood qiymatini nolga qaytaradi.
Reyting tizimiga asoslangan harakatlarni tanlash g'oyasi juda oddiy, shuning uchun Utility-ga asoslangan tizim ularni to'liq almashtirish sifatida emas, balki AI qarorlarini qabul qilish jarayonlarining bir qismi sifatida ishlatilishi mumkin. Qaror daraxti ikkita tugunning foydalilik reytingini so'rashi va undan yuqorisini tanlashi mumkin. Xuddi shunday, xatti-harakatlar daraxti qaysi bolani bajarish kerakligini hal qilish uchun harakatlarning foydaliligini baholash uchun kompozit Utility tuguniga ega bo'lishi mumkin.
Harakat va navigatsiya
Oldingi misollarda biz chapga yoki o'ngga siljitadigan platformamiz va patrullik qilgan yoki hujum qilgan qo'riqchimiz bor edi. Ammo ma'lum vaqt oralig'ida agent harakati bilan qanday shug'ullanamiz? Qanday qilib tezlikni o'rnatamiz, qanday qilib to'siqlardan qochamiz va manzilga etib borish to'g'ri chiziqda harakatlanishdan ko'ra qiyinroq bo'lsa, qanday qilib marshrutni rejalashtiramiz? Keling, buni ko'rib chiqaylik.
Boshqarish
Dastlabki bosqichda biz har bir agent tezlik qiymatiga ega deb hisoblaymiz, u qanchalik tez va qaysi yo'nalishda harakatlanishini o'z ichiga oladi. Uni sekundiga metr, soatiga kilometr, soniyada piksel va hokazolarda o'lchash mumkin. Sense/Think/Act tsiklini eslab, biz tasavvur qilishimiz mumkinki, Think qismi tezlikni tanlaydi va Act qismi bu tezlikni agentga qo'llaydi. Odatda o'yinlarda siz uchun bu vazifani bajaradigan, har bir ob'ektning tezligi qiymatini o'rganadigan va uni moslashtiradigan fizika tizimi mavjud. Shuning uchun siz AIni bitta vazifa bilan qoldirishingiz mumkin - agent qanday tezlikka ega bo'lishi kerakligini hal qilish. Agar agent qaerda bo'lishi kerakligini bilsangiz, uni belgilangan tezlikda to'g'ri yo'nalishda harakatlantirishingiz kerak. Juda ahamiyatsiz tenglama:
istalgan_sayohat = maqsad_joylashuvi - agent_pozitsiyasi
2D dunyoni tasavvur qiling. Agent (-2,-2) nuqtada, maqsad shimoli-sharqda (30, 20) nuqtada va agentning u yerga borishi uchun zarur bo'lgan yo'l (32, 22). Aytaylik, bu pozitsiyalar metrlarda o'lchanadi - agar agentning tezligini sekundiga 5 metr deb olsak, biz o'zgartirish vektorimizni masshtablashtiramiz va taxminan (4.12, 2.83) tezlikka ega bo'lamiz. Ushbu parametrlar bilan agent o'z manziliga deyarli 8 soniyada yetib boradi.
Siz istalgan vaqtda qiymatlarni qayta hisoblashingiz mumkin. Agar agent maqsadga yarmigacha yetib kelgan bo'lsa, harakat uzunligi yarmiga teng bo'lardi, lekin agentning maksimal tezligi 5 m/s bo'lgani uchun (biz buni yuqorida qaror qildik), tezlik bir xil bo'ladi. Bu shuningdek, harakatlanuvchi nishonlar uchun ham ishlaydi, ular harakatlanayotganda agentga kichik o'zgarishlar qilish imkonini beradi.
Ammo biz ko'proq o'zgarishlarni xohlaymiz - masalan, tik turgandan yugurishga o'tayotgan belgini taqlid qilish uchun tezlikni sekin oshirish. Xuddi shu narsani to'xtashdan oldin oxirida qilish mumkin. Bu xususiyatlar boshqaruv harakati sifatida tanilgan, ularning har biri o'ziga xos nomga ega: Izlash, Qochib ketish, Yetib kelish va hokazo. G'oya shundan iboratki, agentning holati va joriy tezligini belgilangan manzil bilan solishtirish asosida tezlashtirish kuchlari agent tezligiga qo'llanilishi mumkin. maqsadga o'tishning turli usullarini qo'llash uchun.
Har bir xatti-harakat biroz boshqacha maqsadga ega. Qidiruv va yetib kelish agentni belgilangan joyga ko'chirish usullaridir. To'siqlardan qochish va ajratish agentning harakatini maqsadga erishish yo'lidagi to'siqlardan qochish uchun moslashtiradi. Alignment va Cohesion agentlarning birgalikda harakatlanishini ta'minlaydi. Barcha omillarni hisobga olgan holda bitta yo'l vektorini ishlab chiqarish uchun har qanday miqdordagi turli xil boshqaruv harakatlari jamlanishi mumkin. Devorlardan va boshqa agentlardan uzoq turish uchun kelish, ajratish va to'siqlardan qochish xatti-harakatlaridan foydalanadigan agent. Ushbu yondashuv keraksiz tafsilotlarsiz ochiq joylarda yaxshi ishlaydi.
Qiyinroq sharoitlarda turli xatti-harakatlarning qo'shilishi yomonroq ishlaydi - masalan, kelish va to'siqlardan qochish o'rtasidagi ziddiyat tufayli agent devorga yopishib qolishi mumkin. Shuning uchun, barcha qiymatlarni oddiygina qo'shishdan ko'ra murakkabroq variantlarni ko'rib chiqishingiz kerak. Buning usuli: har bir xatti-harakat natijalarini qo'shish o'rniga, siz turli yo'nalishlarda harakatni ko'rib chiqishingiz va eng yaxshi variantni tanlashingiz mumkin.
Biroq, boshi berk ko'chaga va qaysi yo'lni tanlashga to'g'ri keladigan murakkab muhitda bizga yanada ilg'or narsa kerak bo'ladi.
Yo'l topish
Rulda harakati ochiq maydonda (futbol maydoni yoki arena) oddiy harakatlanish uchun juda mos keladi, bunda A dan B ga to'g'ri yo'l bo'lib, to'siqlar atrofida kichik aylanmalar mavjud. Murakkab marshrutlar uchun bizga yo'l topish kerak, bu dunyoni o'rganish va u orqali o'tish yo'lini tanlash usulidir.
Eng oddiy, agentning yonidagi har bir kvadratga panjara qo'llash va ulardan qaysi biri harakatlanishiga ruxsat berilganligini baholashdir. Agar ulardan biri maqsad bo'lsa, boshiga etguningizcha, har bir kvadratdan oldingisiga boradigan marshrutni kuzatib boring. Bu marshrut. Aks holda, boradigan joyingizni topmaguningizcha yoki kvadratchalar tugamaguncha jarayonni yaqin atrofdagi boshqa kvadratlar bilan takrorlang (ya'ni hech qanday marshrut yo'q). Bu rasmiy ravishda "Breadth-First Search" yoki BFS (kenglik-birinchi qidiruv algoritmi) deb nomlanadi. Har qadamda u har tomonga qaraydi (shuning uchun kenglik, "kenglik"). Qidiruv maydoni kerakli joyga yetguncha harakatlanadigan to'lqin jabhasiga o'xshaydi - qidiruv maydoni har bir qadamda oxirgi nuqta qo'shilmaguncha kengayadi, shundan so'ng uni boshidan kuzatish mumkin.
Natijada siz kerakli marshrut tuzilgan kvadratchalar ro'yxatini olasiz. Bu yo'l (shuning uchun, yo'l topish) - agent manzilga ergashayotganda tashrif buyuradigan joylar ro'yxati.
Dunyodagi har bir kvadratning o'rnini bilganimizni hisobga olsak, biz yo'l bo'ylab harakatlanish uchun boshqaruv xatti-harakatlaridan foydalanishimiz mumkin - 1-tugundan 2-tugunga, so'ngra 2-tugundan 3-tugunga va hokazo. Eng oddiy variant - keyingi kvadratning o'rtasiga borish, lekin undan ham yaxshiroq variant - joriy kvadrat va keyingi kvadrat orasidagi chekkaning o'rtasida to'xtash. Shu sababli, agent keskin burilishlarda burchaklarni kesishi mumkin bo'ladi.
BFS algoritmining kamchiliklari ham bor - u "to'g'ri" yo'nalishdagi kabi "noto'g'ri" yo'nalishdagi ko'plab kvadratlarni o'rganadi. Bu erda A* (Yulduz) deb nomlangan murakkabroq algoritm o'ynaydi. U xuddi shunday ishlaydi, lekin qo'shni kvadratlarni ko'r-ko'rona tekshirish o'rniga (keyin qo'shnilarning qo'shnilari, keyin qo'shnilarning qo'shnilari va boshqalar) u tugunlarni ro'yxatga to'playdi va ularni shunday saralaydiki, keyingi tekshiriladigan tugun har doim bo'ladi. eng qisqa yo'lga olib boradigan biri. Tugunlar ikki narsani hisobga oladigan evristik asosida saralanadi - kerakli kvadratgacha bo'lgan taxminiy marshrutning "narxi" (har qanday sayohat xarajatlarini o'z ichiga olgan holda) va ushbu kvadrat belgilangan joydan qanchalik uzoqligini taxmin qilish (qidiruvda qidiruvni chetlashtirish) to'g'ri yo'nalish).
Bu misol shuni ko'rsatadiki, agent bir vaqtning o'zida bir kvadratni o'rganadi, har safar eng istiqbolli bo'lgan qo'shni tanlaydi. Olingan yo'l BFS bilan bir xil, ammo jarayonda kamroq kvadratlar ko'rib chiqildi - bu o'yin samaradorligiga katta ta'sir qiladi.
To'rsiz harakat
Ammo ko'pgina o'yinlar tarmoqqa joylashtirilmaydi va ko'pincha realizmdan voz kechmasdan buni amalga oshirish mumkin emas. Murosaga kelish kerak. Kvadratchalar qanday o'lchamda bo'lishi kerak? Juda katta va ular kichik koridorlar yoki burilishlarni to'g'ri tasvirlay olmaydi, juda kichik va qidirish uchun juda ko'p kvadratlar bo'ladi, bu oxir-oqibatda ko'p vaqtni oladi.
Tushunish kerak bo'lgan birinchi narsa, to'r bizga bog'langan tugunlar grafigini beradi. A* va BFS algoritmlari aslida grafiklarda ishlaydi va bizning tarmoqimizga umuman ahamiyat bermaydi. Biz tugunlarni o'yin dunyosining istalgan joyiga qo'yishimiz mumkin edi: har qanday ikkita bog'langan tugun o'rtasida, shuningdek, boshlang'ich va yakuniy nuqtalar va tugunlardan kamida bittasi o'rtasida aloqa mavjud ekan, algoritm avvalgidek ishlaydi. Bu ko'pincha yo'l nuqtasi tizimi deb ataladi, chunki har bir tugun dunyoda har qanday gipotetik yo'llarning bir qismi bo'lishi mumkin bo'lgan muhim pozitsiyani ifodalaydi.
1-misol: har bir kvadratda tugun. Qidiruv agent joylashgan tugundan boshlanadi va kerakli kvadratning tugunida tugaydi.
2-misol: Kichikroq tugunlar to'plami (yo'nalish nuqtalari). Qidiruv agentning maydonidan boshlanadi, kerakli miqdordagi tugunlardan o'tadi va keyin belgilangan joyga davom etadi.
Bu butunlay moslashuvchan va kuchli tizim. Biroq, yo'l nuqtasini qayerga va qanday joylashtirishni hal qilishda biroz ehtiyot bo'lish kerak, aks holda agentlar eng yaqin nuqtani ko'rmasligi va yo'lni boshlay olmasligi mumkin. Agar biz dunyo geometriyasidan kelib chiqqan holda avtomatik ravishda yo'l nuqtalarini joylashtirsak, osonroq bo'lar edi.
Bu erda navigatsiya tarmog'i yoki navmesh (navigatsiya tarmog'i) paydo bo'ladi. Bu odatda uchburchaklarning ikki o'lchamli to'ri bo'lib, u dunyo geometriyasida - agentga yurishga ruxsat berilgan joyda qoplanadi. To'rdagi uchburchaklarning har biri grafikdagi tugunga aylanadi va grafikda qo'shni tugunlarga aylanadigan uchta qo'shni uchburchakka ega.
Ushbu rasm Unity dvigatelining namunasidir - u dunyodagi geometriyani tahlil qildi va navmeshni yaratdi (ochiq ko'k rangdagi skrinshotda). Navmeshdagi har bir ko'pburchak agent turishi yoki bir ko'pburchakdan boshqa ko'pburchakka o'tishi mumkin bo'lgan maydondir. Ushbu misolda ko'pburchaklar ular joylashgan qavatlardan kichikroq - bu agentning nominal pozitsiyasidan tashqariga chiqadigan hajmini hisobga olish uchun amalga oshiriladi.
Biz ushbu tarmoq orqali marshrutni yana A* algoritmidan foydalanib qidirishimiz mumkin. Bu bizga butun geometriyani hisobga oladigan va keraksiz tugunlarni va yo'nalish nuqtalarini yaratishni talab qilmaydigan dunyodagi deyarli mukammal marshrutni beradi.
Yo'l topish - bu juda keng mavzu bo'lib, maqolaning bitta bo'limi etarli emas. Agar siz uni batafsilroq o'rganmoqchi bo'lsangiz, unda bu yordam beradi .
rejalashtirish
Biz yo‘l-yo‘riqni o‘rganish bilan bilib oldikki, ba’zida yo‘nalishni tanlash va harakatlanishning o‘zi kifoya emas – kerakli manzilga yetib olish uchun marshrut tanlash va bir necha burilish qilishimiz kerak. Biz bu fikrni umumlashtirishimiz mumkin: maqsadga erishish - bu faqat keyingi qadam emas, balki birinchisi nima bo'lishi kerakligini bilish uchun ba'zan bir necha qadamlarni oldinga qarash kerak bo'lgan butun ketma-ketlikdir. Bu rejalashtirish deyiladi. Pathfinding rejalashtirishning bir nechta kengaytmalaridan biri sifatida ko'rib chiqilishi mumkin. Bizning Sense/Think/Act tsiklimiz nuqtai nazaridan, bu erda o'ylash qismi kelajak uchun bir nechta Act qismlarini rejalashtiradi.
Keling, Magic: The Gathering stol o'yini misolini ko'rib chiqaylik. Biz birinchi navbatda qo'limizda quyidagi kartalar to'plami bilan boramiz:
- Swamp - 1 qora mana beradi (er kartasi).
- O'rmon - 1 yashil mana (er kartasi) beradi.
- Qochqin sehrgar - chaqirish uchun 1 ko'k mana kerak.
- Elvish Mystic - Chaqirish uchun 1 yashil mana kerak.
Buni osonlashtirish uchun qolgan uchta kartani e'tiborsiz qoldiramiz. Qoidalarga ko'ra, o'yinchiga har bir turda 1 ta quruqlik kartasini o'ynashga ruxsat beriladi, u mana olish uchun ushbu kartani "bosishi" va keyin mana miqdoriga qarab afsun (shu jumladan mavjudotni chaqirishi) mumkin. Bunday holatda, inson o'yinchi Forest o'ynashni biladi, 1 yashil mana bosing va keyin Elvish Mysticni chaqiradi. Ammo o'yin AI buni qanday tushunishi mumkin?
Oson rejalashtirish
Arzimas yondashuv - har bir harakatni o'z navbatida mos keladiganlar qolmaguncha sinab ko'rish. Kartalarga qarab, AI Swamp nimani o'ynashi mumkinligini ko'radi. Va u o'ynaydi. Bu burilish qolgan boshqa harakatlar bormi? U na Elvish mistik, na qochoq sehrgarni chaqira olmaydi, chunki ularni chaqirish uchun yashil va ko'k mana kerak bo'ladi, Swamp esa faqat qora mana beradi. Va u endi Forestni o'ynay olmaydi, chunki u allaqachon Swamp o'ynagan. Shunday qilib, AI o'yin qoidalariga rioya qildi, lekin uni yomon qildi. Yaxshilash mumkin.
Rejalashtirish o'yinni kerakli holatga keltiradigan harakatlar ro'yxatini topishi mumkin. Yo'ldagi har bir kvadratning qo'shnilari bo'lgani kabi (yo'l topishda), rejadagi har bir harakatning ham qo'shnilari yoki davomchilari bor. Biz kerakli holatga etgunimizcha, ushbu harakatlar va keyingi harakatlarni izlashimiz mumkin.
Bizning misolimizda kerakli natija "iloji bo'lsa, mavjudotni chaqirish" dir. Navbatning boshida biz o'yin qoidalari bilan ruxsat etilgan ikkita mumkin bo'lgan harakatni ko'ramiz:
1. Swamp o'ynang (natija: o'yinda Swamp)
2. O'rmon o'ynang (natija: o'yinda o'rmon)
Qabul qilingan har bir harakat keyingi harakatlarga olib kelishi va boshqalarni yopishi mumkin, bu yana o'yin qoidalariga bog'liq. Tasavvur qiling, biz Swamp o'ynadik - bu keyingi qadam sifatida Swampni olib tashlaydi (biz uni allaqachon o'ynaganmiz) va bu o'rmonni ham o'chirib tashlaydi (chunki qoidalarga ko'ra siz har bir navbatga bitta er kartasini o'ynashingiz mumkin). Shundan so'ng, AI keyingi qadam sifatida 1 qora mana olishni qo'shadi, chunki boshqa variantlar yo'q. Agar u oldinga borsa va Tap the Swamp ni tanlasa, u 1 birlik qora mana oladi va u bilan hech narsa qila olmaydi.
1. Swamp o'ynang (natija: o'yinda Swamp)
1.1 “Tap” botqog‘i (natija: botqoq “bosdi”, +1 birlik qora mana)
Hech qanday amal mavjud emas - END
2. O'rmon o'ynang (natija: o'yinda o'rmon)
Amallar ro'yxati qisqa edi, biz boshi berk ko'chaga kirdik. Keyingi bosqich uchun jarayonni takrorlaymiz. Biz Forestni o'ynaymiz, "1 yashil mana oling" aktsiyasini ochamiz, bu o'z navbatida uchinchi aksiyani ochadi - Elvish Mysticni chaqirish.
1. Swamp o'ynang (natija: o'yinda Swamp)
1.1 “Tap” botqog‘i (natija: botqoq “bosdi”, +1 birlik qora mana)
Hech qanday amal mavjud emas - END
2. O'rmon o'ynang (natija: o'yinda o'rmon)
2.1 “Tap” oʻrmoni (natija: oʻrmon “tegildi”, +1 birlik yashil mana)
2.1.1 Elvish Mysticni chaqiring (natija: o'yinda Elvish Mystic, -1 yashil mana)
Hech qanday amal mavjud emas - END
Nihoyat, biz barcha mumkin bo'lgan harakatlarni o'rganib chiqdik va mavjudotni chaqiradigan rejani topdik.
Bu juda soddalashtirilgan misol. Ba'zi mezonlarga javob beradigan har qanday rejani emas, balki eng yaxshi rejani tanlash tavsiya etiladi. Umuman olganda, potentsial rejalarni ularni amalga oshirish natijasi yoki umumiy foydasiga qarab baholash mumkin. Siz quruqlik kartasini o'ynaganingiz uchun 1 ball va mavjudotni chaqirganingiz uchun 3 ball olishingiz mumkin. Swamp o'ynash 1 ball rejasi bo'ladi. O'rmon → O'rmonga teging → Elvish Mysticni chaqirish o'ynash darhol 4 ball beradi.
Magic: The Gathering-da rejalashtirish shunday ishlaydi, ammo xuddi shu mantiq boshqa vaziyatlarda ham amal qiladi. Masalan, shaxmatda episkopga joy ochish uchun piyonni harakatlantirish. Yoki shunday XCOMda xavfsiz suratga olish uchun devor orqasiga panoh oling. Umuman olganda, siz fikrni tushunasiz.
Yaxshilangan rejalashtirish
Ba'zan har bir mumkin bo'lgan variantni ko'rib chiqish uchun juda ko'p potentsial harakatlar mavjud. Magic: The Gathering misoliga qaytsak: keling, o'yinda va sizning qo'lingizda bir nechta er va jonzot kartalari mavjud - harakatlarning mumkin bo'lgan kombinatsiyalari soni o'nlab bo'lishi mumkin. Muammoning bir nechta echimlari mavjud.
Birinchi usul - orqaga zanjir bog'lash. Barcha kombinatsiyalarni sinab ko'rish o'rniga, yakuniy natijadan boshlash va to'g'ridan-to'g'ri yo'lni topishga harakat qilish yaxshiroqdir. Daraxtning ildizidan ma'lum bir bargga o'tish o'rniga, biz teskari yo'nalishda - bargdan ildizgacha harakat qilamiz. Bu usul osonroq va tezroq.
Agar dushman 1 ta sog'likka ega bo'lsa, siz "1 yoki undan ko'p zarar etkazish" rejasini topishingiz mumkin. Bunga erishish uchun bir qator shartlarga rioya qilish kerak:
1. Zarar afsun sabab bo'lishi mumkin - u qo'lda bo'lishi kerak.
2. Sehrgarlik qilish uchun sizga mana kerak.
3. Mana olish uchun siz er kartasini o'ynashingiz kerak.
4. Yer kartasini o'ynash uchun uni qo'lingizda bo'lishi kerak.
Yana bir usul - eng yaxshi birinchi qidiruv. Barcha yo'llarni sinab ko'rish o'rniga, biz eng mosini tanlaymiz. Ko'pincha, bu usul keraksiz qidiruv xarajatlarisiz optimal rejani beradi. A* eng yaxshi birinchi qidiruv shaklidir - eng istiqbolli marshrutlarni boshidan o'rganib chiqib, u boshqa variantlarni tekshirmasdan ham eng yaxshi yo'lni topishi mumkin.
Qiziqarli va tobora ommalashib borayotgan eng yaxshi birinchi qidiruv varianti Monte-Karlo daraxtini qidirishdir. Har bir keyingi harakatni tanlashda qaysi rejalar boshqalardan yaxshiroq ekanligini taxmin qilish o'rniga, algoritm oxirigacha (reja g'alaba yoki mag'lubiyatga olib kelganda) har bir qadamda tasodifiy vorislarni tanlaydi. Yakuniy natija keyin oldingi variantlarning og'irligini oshirish yoki kamaytirish uchun ishlatiladi. Ushbu jarayonni ketma-ket bir necha marta takrorlash orqali, algoritm vaziyat o'zgargan taqdirda ham (agar dushman o'yinchiga xalaqit berish uchun harakat qilsa) keyingi eng yaxshi harakat nima ekanligini yaxshi baholaydi.
Maqsadga yo'naltirilgan harakatni rejalashtirish yoki GOAP (maqsadga yo'naltirilgan harakatni rejalashtirish)siz o'yinlarni rejalashtirish haqidagi hech qanday hikoya to'liq bo'lmaydi. Bu keng tarqalgan bo'lib qo'llaniladigan va muhokama qilinadigan usul, ammo bir nechta farqlovchi tafsilotlardan tashqari, bu biz ilgari gapirgan orqaga bog'lanish usulidir. Agar maqsad "o'yinchini yo'q qilish" bo'lsa va o'yinchi yashiringan bo'lsa, reja shunday bo'lishi mumkin: granata bilan yo'q qilish → uni olish → uni otish.
Odatda bir nechta maqsadlar mavjud, ularning har biri o'z ustuvorligiga ega. Agar eng yuqori ustuvor maqsad bajarilmasa (hech qanday harakatlar kombinatsiyasi "o'yinchini o'ldirish" rejasini tuzmasa, chunki o'yinchi ko'rinmasa), AI pastroq ustuvor maqsadlarga qaytadi.
Trening va moslashish
Biz allaqachon aytdikki, AI o'yinida odatda mashinani o'rganishdan foydalanmaydi, chunki u real vaqtda agentlarni boshqarish uchun mos emas. Ammo bu siz ushbu hududdan biror narsa qarz olmaysiz degani emas. Biz otishmada nimadir o'rganishimiz mumkin bo'lgan raqibni xohlaymiz. Masalan, xaritadagi eng yaxshi pozitsiyalar haqida bilib oling. Yoki jangovar o'yindagi raqib o'yinchining tez-tez ishlatib turadigan kombinatsiyalangan harakatlariga to'sqinlik qilib, uni boshqalardan foydalanishga undaydi. Shunday qilib, mashinani o'rganish bunday vaziyatlarda juda foydali bo'lishi mumkin.
Statistika va ehtimollar
Murakkab misollarga o'tishdan oldin, keling, bir nechta oddiy o'lchovlarni olib, qaror qabul qilish uchun ulardan foydalanish orqali qanchalik uzoqqa borishimiz mumkinligini ko'rib chiqaylik. Misol uchun, real vaqt strategiyasi - o'yinning dastlabki daqiqalarida o'yinchi hujum uyushtira oladimi yoki yo'qligini qanday aniqlash mumkin va bunga qarshi qanday himoyaga tayyorgarlik ko'rish kerak? Kelajakdagi reaktsiyalar qanday bo'lishi mumkinligini tushunish uchun o'yinchining o'tmishdagi tajribasini o'rganishimiz mumkin. Birinchidan, bizda bunday xom ma'lumotlar yo'q, lekin biz ularni to'plashimiz mumkin - AI har safar odamga qarshi o'ynaganida, u birinchi hujum vaqtini yozib olishi mumkin. Bir necha mashg'ulotdan so'ng biz o'yinchining kelajakda hujum qilish uchun o'rtacha vaqtini olamiz.
O'rtacha qiymatlar bilan bog'liq muammo ham bor: agar o'yinchi 20 marta shoshilsa va 20 marta sekin o'ynasa, kerakli qiymatlar o'rtada bo'ladi va bu bizga hech qanday foydali narsa bermaydi. Bitta yechim - kirish ma'lumotlarini cheklash - oxirgi 20 ta bo'lakni hisobga olish mumkin.
Shunga o'xshash yondashuv o'yinchining o'tmishdagi afzalliklari kelajakda bir xil bo'lishini taxmin qilish orqali muayyan harakatlar ehtimolini baholashda qo'llaniladi. Agar o'yinchi bizga besh marta olovli to'p bilan, ikki marta chaqmoq bilan va bir marta jangovar hujum bilan hujum qilsa, u olov to'pini afzal ko'rishi aniq. Keling, ekstrapolyatsiya qilaylik va turli xil qurollardan foydalanish ehtimolini ko'rib chiqaylik: olov to'pi = 62,5%, chaqmoq = 25% va yaqin jang = 12,5%. Bizning o'yinimiz AI o'zini olovdan himoya qilish uchun tayyorlanishi kerak.
Yana bir qiziqarli usul - katta hajmdagi kirish ma'lumotlarini o'rganish va AI kerakli tarzda reaksiyaga kirishishi uchun vaziyatni tasniflash uchun Naive Bayes klassifikatoridan foydalanish. Bayes klassifikatorlari elektron pochta spam filtrlarida foydalanishlari bilan mashhur. U erda ular so'zlarni tekshiradilar, ularni bu so'zlar ilgari paydo bo'lgan (spamda yoki yo'q) bilan solishtiradilar va kiruvchi elektron pochta xabarlari haqida xulosa chiqaradilar. Hatto kamroq kirishlar bilan ham xuddi shunday qilishimiz mumkin. AI ko'rgan barcha foydali ma'lumotlarga (masalan, qanday dushman bo'linmalari yaratilgani yoki ular qanday sehrlardan foydalanganligi yoki qanday texnologiyalarni o'rganganligi) va yakuniy natijaga (urush yoki tinchlik, shoshilish yoki mudofaa va boshqalar) asoslangan. - biz kerakli AI xatti-harakatini tanlaymiz.
Ushbu o'qitish usullarining barchasi etarli, ammo ulardan test ma'lumotlari asosida foydalanish tavsiya etiladi. AI sizning o'yinchilaringiz ishlatgan turli strategiyalarga moslashishni o'rganadi. Chiqarilgandan so'ng o'yinchiga moslashadigan AI juda oldindan aytish mumkin yoki mag'lub bo'lish juda qiyin bo'lishi mumkin.
Qiymatga asoslangan moslashuv
Bizning o'yin dunyomizning mazmuni va qoidalarini hisobga olgan holda, biz kiritilgan ma'lumotlardan foydalanish o'rniga, qaror qabul qilishga ta'sir qiluvchi qadriyatlar to'plamini o'zgartirishimiz mumkin. Biz buni qilamiz:
- AI dunyoning holati va o'yin davomidagi asosiy voqealar haqida ma'lumot to'plashiga ruxsat bering (yuqoridagi kabi).
- Keling, ushbu ma'lumotlarga asoslanib, bir nechta muhim qiymatlarni o'zgartiraylik.
- Biz qarorlarimizni ushbu qadriyatlarni qayta ishlash yoki baholash asosida amalga oshiramiz.
Misol uchun, agent birinchi shaxs otishma xaritasida tanlash uchun bir nechta xonalarga ega. Har bir xonaning o'z qiymati bor, bu tashrif buyurish qanchalik ma'qul ekanligini belgilaydi. AI tasodifiy qiymatga qarab qaysi xonaga borishni tanlaydi. Keyin agent qaysi xonada o'ldirilganini eslaydi va uning qiymatini pasaytiradi (u erga qaytib kelish ehtimoli). Xuddi shunday teskari vaziyat uchun - agar agent ko'plab raqiblarni yo'q qilsa, u holda xonaning qiymati oshadi.
Markov modeli
Agar biz to'plangan ma'lumotlardan bashorat qilish uchun foydalansak nima bo'ladi? Agar biz o'yinchini ma'lum vaqt davomida ko'rgan har bir xonani eslasak, o'yinchi qaysi xonaga borishini taxmin qilamiz. O'yinchining xonalar (qiymatlar) bo'ylab harakatlarini kuzatish va yozib olish orqali biz ularni taxmin qilishimiz mumkin.
Keling, uchta xonani olaylik: qizil, yashil va ko'k. Shuningdek, o'yin seansini tomosha qilishda qayd etgan kuzatuvlarimiz:
Har bir xonada kuzatuvlar soni deyarli teng - biz pistirma uchun yaxshi joyni qaerdan qilishni hali ham bilmaymiz. Statistikani to'plash, shuningdek, o'yinchilarning qayta tug'ilishi bilan ham murakkablashadi, ular xaritada bir tekisda paydo bo'ladi. Ammo ular xaritada paydo bo'lgandan keyin kiradigan keyingi xona haqidagi ma'lumotlar allaqachon foydalidir.
Ko'rinib turibdiki, yashil xona o'yinchilarga mos keladi - ko'pchilik qizil xonadan unga o'tadi, ularning 50% u erda qoladi. Moviy xona, aksincha, mashhur emas, deyarli hech kim unga bormaydi va agar borsa, ular uzoq vaqt qolmaydi.
Ammo ma'lumotlar bizga muhimroq narsani aytadi - o'yinchi ko'k xonada bo'lsa, biz uni ko'radigan keyingi xona yashil emas, qizil rangda bo'ladi. Yashil xona qizil xonadan ko'ra mashhurroq bo'lsa ham, o'yinchi ko'k xonada bo'lsa, vaziyat o'zgaradi. Keyingi holat (ya'ni, o'yinchi boradigan xona) oldingi holatga (ya'ni, o'yinchi hozir bo'lgan xonaga) bog'liq. Biz bog'liqliklarni o'rganganimiz sababli, biz kuzatishlarni mustaqil ravishda hisoblagandan ko'ra aniqroq bashorat qilamiz.
O'tmishdagi ma'lumotlar asosida kelajak holatini bashorat qilish Markov modeli deb ataladi va bunday misollar (xonalar bilan) Markov zanjirlari deb ataladi. Shakllar ketma-ket holatlar orasidagi o'zgarishlar ehtimolini ifodalaganligi sababli, ular har bir o'tish atrofida ehtimollik bilan FSM sifatida vizual ravishda ko'rsatiladi. Ilgari biz FSM dan agentning xatti-harakat holatini ifodalash uchun foydalanganmiz, ammo bu tushuncha agent bilan bog'langanmi yoki yo'qmi, har qanday holatga taalluqlidir. Bunday holda, davlatlar agent egallagan xonani ifodalaydi:
Bu holat o'zgarishining nisbiy ehtimolini ifodalashning oddiy usuli bo'lib, AIga keyingi holatni bashorat qilish qobiliyatini beradi. Oldinda bir necha qadamlarni taxmin qilishingiz mumkin.
Agar o'yinchi yashil xonada bo'lsa, keyingi safar u kuzatilganda u erda qolish ehtimoli 50%. Ammo undan keyin ham u erda bo'lish ehtimoli qanday? Ikki marta kuzatuvdan so‘ng o‘yinchining yashil xonada qolib ketishigina emas, balki uni tark etib, qaytishi ehtimoli ham bor. Mana yangi ma'lumotlarni hisobga olgan holda yangi jadval:
Bu shuni ko'rsatadiki, ikki kuzatuvdan so'ng o'yinchini yashil xonada ko'rish imkoniyati 51% - 21% ga teng bo'ladi, u qizil xonadan bo'ladi, 5% o'yinchi ular orasidagi ko'k xonaga tashrif buyuradi va. 25% o'yinchi yashil xonani tark etmaydi.
Jadval shunchaki vizual vositadir - protsedura faqat har bir qadamda ehtimollarni ko'paytirishni talab qiladi. Bu shuni anglatadiki, siz bir ogohlantirish bilan kelajakka uzoq qarashingiz mumkin: biz xonaga kirish imkoniyati butunlay hozirgi xonaga bog'liq deb hisoblaymiz. Bu Markov mulki deb ataladi - kelajakdagi holat faqat hozirgi holatga bog'liq. Ammo bu yuz foiz aniq emas. O'yinchilar qarorlarni boshqa omillarga qarab o'zgartirishi mumkin: sog'liq darajasi yoki o'q-dorilar miqdori. Biz bu qiymatlarni qayd etmasligimiz sababli, prognozlarimiz unchalik aniq emas.
N-gramm
Jangovar o'yin misoli va o'yinchining kombinatsiyalangan harakatlarini bashorat qilish haqida nima deyish mumkin? Xuddi shu! Ammo bitta holat yoki hodisa o'rniga biz kombinatsiyalangan zarbani tashkil etuvchi butun ketma-ketlikni ko'rib chiqamiz.
Buning usullaridan biri har bir kirishni (masalan, Kick, Punch yoki Block) buferda saqlash va butun buferni hodisa sifatida yozishdir. Shunday qilib, o'yinchi SuperDeathFist hujumidan foydalanish uchun Kick, Kick, Punch tugmalarini qayta-qayta bosadi, AI tizimi barcha kirishlarni buferda saqlaydi va har bir qadamda ishlatilgan oxirgi uchtasini eslab qoladi.
(Qalin chizilgan chiziqlar o'yinchi SuperDeathFist hujumini boshlaganida.)
O‘yinchi “Kick”ni, so‘ngra boshqa “Kick”ni tanlaganida, sun’iy intellekt barcha variantlarni ko‘radi va keyingi kiritish har doim “Punch” bo‘lishini sezadi. Bu agentga SuperDeathFistning kombinatsiyalangan harakatini bashorat qilish va iloji bo'lsa, uni bloklash imkonini beradi.
Ushbu hodisalar ketma-ketligi N-gramm deb ataladi, bu erda N - saqlangan elementlar soni. Oldingi misolda u 3 gramm (trigram) edi, ya'ni: birinchi ikkita yozuv uchinchisini bashorat qilish uchun ishlatiladi. Shunga ko'ra, 5 grammda dastlabki to'rtta yozuv beshinchi va hokazolarni bashorat qiladi.
Dizayner N-gramm o'lchamini diqqat bilan tanlashi kerak. Kichikroq N xotira kamroq talab qiladi, lekin kamroq tarixni saqlaydi. Masalan, 2 grammlik (bigramm) Kick, Kick yoki Kick, Punch yozib oladi, lekin Kick, Kick, Punch ni saqlay olmaydi, shuning uchun AI SuperDeathFist kombinatsiyasiga javob bermaydi.
Boshqa tomondan, kattaroq raqamlar ko'proq xotirani talab qiladi va AIni o'rgatish qiyinroq bo'ladi, chunki ko'proq mumkin bo'lgan variantlar bo'ladi. Agar sizda Kick, Punch yoki Blockning uchta mumkin bo'lgan kirishi bo'lsa va biz 10 grammdan foydalansak, bu taxminan 60 ming xil variant bo'lar edi.
Bigram modeli oddiy Markov zanjiri - har bir o'tgan holat/joriy holat juftligi bigram bo'lib, siz birinchisiga asoslanib ikkinchi holatni taxmin qilishingiz mumkin. 3 gramm va undan kattaroq N-grammlarni Markov zanjiri sifatida ham tasavvur qilish mumkin, bunda barcha elementlar (N-grammdagi oxirgisidan tashqari) birgalikda birinchi holatni, oxirgi element esa ikkinchi holatni tashkil qiladi. Jang o'yini misolida Kick and Punch holatidan Kick and Punch holatiga o'tish imkoniyati ko'rsatilgan. Bir nechta kirish tarixi yozuvlarini bitta birlik sifatida ko'rib chiqish orqali biz kirish ketma-ketligini butun holatning bir qismiga aylantiramiz. Bu bizga Markov xususiyatini beradi, bu bizga Markov zanjirlaridan keyingi kirishni bashorat qilish va keyingi qanday kombinatsiya harakati bo'lishini taxmin qilish imkonini beradi.
xulosa
Biz sun'iy intellektni rivojlantirishda eng keng tarqalgan vositalar va yondashuvlar haqida gaplashdik. Shuningdek, biz ulardan foydalanish kerak bo'lgan va ayniqsa foydali bo'lgan vaziyatlarni ko'rib chiqdik.
Bu AI o'yinining asoslarini tushunish uchun etarli bo'lishi kerak. Lekin, albatta, bu barcha usullar emas. Kamroq mashhur, ammo unchalik samarali emas:
- optimallashtirish algoritmlari, jumladan, tepalikka chiqish, gradient tushish va genetik algoritmlar
- qarama-qarshi qidiruv/rejalashtirish algoritmlari (minimax va alfa-beta kesish)
- tasniflash usullari (perseptronlar, neyron tarmoqlar va vektorli mashinalarni qo'llab-quvvatlash)
- agentlarning idroki va xotirasini qayta ishlash tizimlari
- AIga arxitektura yondashuvlari (gibrid tizimlar, quyi to'plamlar arxitekturalari va AI tizimlarini qoplashning boshqa usullari)
- animatsiya vositalari (rejalashtirish va harakatni muvofiqlashtirish)
- ishlash omillari (tafsilot darajasi, istalgan vaqtda va vaqtni belgilash algoritmlari)
Mavzu bo'yicha onlayn manbalar:
1. GameDev.net mavjud , shuningdek .
2. o'yin AI rivojlanishi bilan bog'liq keng mavzularda ko'plab taqdimotlar va maqolalarni o'z ichiga oladi.
3. GDC AI sammitidagi mavzularni o'z ichiga oladi, ularning aksariyati bepul.
4. Foydali materiallarni veb-saytda ham topish mumkin .
5. AI tadqiqotchisi va o‘yin ishlab chiqaruvchisi Tommi Tompson YouTube’da videolar yaratadi tijorat o'yinlarida AIni tushuntirish va o'rganish bilan.
Mavzu bo'yicha kitoblar:
1. Game AI Pro kitoblar seriyasi - bu muayyan xususiyatlarni qanday amalga oshirish yoki muayyan muammolarni qanday hal qilish kerakligini tushuntiruvchi qisqa maqolalar to'plami.
2. AI Game Programming Wisdom seriyasi Game AI Pro seriyasining salafidir. U eski usullarni o'z ichiga oladi, ammo deyarli barchasi bugungi kunda ham dolzarbdir.
3. sun'iy intellektning umumiy sohasini tushunishni istagan har bir kishi uchun asosiy matnlardan biridir. Bu o'yinni rivojlantirish haqidagi kitob emas - u AI asoslarini o'rgatadi.
Manba: www.habr.com