Naišao sam na zanimljiv materijal o umjetnoj inteligenciji u igrama. Uz objašnjenje osnovnih stvari o AI-u na jednostavnim primjerima, a unutra se nalaze mnogi korisni alati i metode za njegov praktičan razvoj i dizajn. Kako, gdje i kada ih koristiti također je tamo.
Većina primjera napisana je u pseudokodu, tako da nije potrebno napredno znanje programiranja. Ispod kroja je 35 listova teksta sa slikama i gifovima pa se pripremite.
UPD. Ispričavam se, ali već sam napravio vlastiti prijevod ovog članka na Habréu . Možete pročitati njegovu verziju , ali iz nekog razloga članak je prošao pored mene (koristio sam pretragu, ali nešto je pošlo po zlu). A budući da pišem na blogu posvećenom razvoju igara, odlučio sam ostaviti svoju verziju prijevoda za pretplatnike (neke su točke formatirane drugačije, neke su namjerno izostavljene prema savjetu programera).
Što je AI?
AI igre fokusira se na radnje koje objekt treba izvesti na temelju uvjeta u kojima se nalazi. To se obično naziva upravljanje "inteligentnim agentom", gdje je agent lik igrača, vozilo, bot ili ponekad nešto apstraktnije: cijela grupa entiteta ili čak civilizacija. U svakom slučaju, to je stvar koja mora vidjeti svoje okruženje, na temelju njega donositi odluke i ponašati se u skladu s njima. Ovo se naziva ciklus Sense/Misli/Djeluj:
- Osjećaj: agent pronalazi ili prima informacije o stvarima u svojoj okolini koje mogu utjecati na njegovo ponašanje (prijetnje u blizini, predmeti za prikupljanje, zanimljiva mjesta za istraživanje).
- Razmislite: Agent odlučuje kako će reagirati (razmatra je li dovoljno sigurno skupljati predmete ili bi se trebao prvo boriti/sakriti).
- Djelovanje: agent izvodi radnje za provedbu prethodne odluke (počinje se kretati prema neprijatelju ili objektu).
- ...sada se situacija promijenila zbog postupaka likova, pa se ciklus ponavlja s novim podacima.
AI se fokusira na Sense dio petlje. Na primjer, autonomni automobili snimaju slike ceste, kombiniraju ih s podacima radara i lidara te ih tumače. To se obično radi strojnim učenjem, koje obrađuje dolazne podatke i daje im značenje, izvlačeći semantičke informacije poput "još jedan automobil je 20 metara ispred vas." To su takozvani problemi klasifikacije.
Igrama nije potreban složeni sustav za izvlačenje informacija budući da je većina podataka već njihov sastavni dio. Nema potrebe za pokretanjem algoritama za prepoznavanje slike kako bi se utvrdilo postoji li neprijatelj ispred vas—igra već zna i šalje informacije izravno u proces donošenja odluka. Stoga je smisaoni dio ciklusa često puno jednostavniji od dijela Misli i djeluj.
Ograničenja igre AI
AI ima niz ograničenja koja se moraju poštivati:
- AI ne treba unaprijed trenirati, kao da je algoritam strojnog učenja. Nema smisla pisati neuronsku mrežu tijekom razvoja za praćenje desetaka tisuća igrača i naučiti najbolji način igranja protiv njih. Zašto? Zato što igra nije izdana i nema igrača.
- Igra bi trebala biti zabavna i izazovna, tako da agenti ne bi trebali pronaći najbolji pristup protiv ljudi.
- Agenti moraju izgledati realistično kako bi se igrači osjećali kao da igraju protiv stvarnih ljudi. Program AlphaGo nadmašio je ljude, ali odabrani koraci bili su vrlo daleko od tradicionalnog shvaćanja igre. Ako igra simulira ljudskog protivnika, ovaj osjećaj ne bi trebao postojati. Algoritam treba promijeniti tako da donosi uvjerljive odluke, a ne idealne.
- AI mora raditi u stvarnom vremenu. To znači da algoritam ne može monopolizirati korištenje CPU-a tijekom dugih vremenskih razdoblja za donošenje odluka. Čak je i 10 milisekundi predugo, jer većina igara treba samo 16 do 33 milisekunde da izvrše svu obradu i pređu na sljedeći grafički okvir.
- U idealnom slučaju, barem dio sustava trebao bi biti vođen podacima, tako da nekoderi mogu brže unositi promjene i prilagodbe.
Pogledajmo pristupe umjetne inteligencije koji pokrivaju cijeli ciklus Osjeti/Misli/Djeluj.
Donošenje osnovnih odluka
Počnimo s najjednostavnijom igrom - pong. Cilj: pomaknite lopaticu tako da se lopta odbije od nje, a ne da proleti pored nje. To je kao tenis, gdje gubiš ako ne udariš lopticu. Ovdje AI ima relativno lak zadatak - odlučuje u kojem smjeru pomaknuti platformu.
Uvjetne izjave
Za AI u Pongu, najočiglednije rješenje je uvijek pokušati postaviti platformu ispod lopte.
Jednostavan algoritam za ovo, napisan u pseudokodu:
svaki okvir/ažuriranje dok igra radi:
ako je lopta lijevo od lopatice:
pomakni veslo lijevo
inače ako je lopta desno od lopatice:
pomakni veslo udesno
Ako se platforma kreće brzinom lopte, onda je ovo idealan algoritam za AI u Pongu. Ne treba ništa komplicirati ako nema toliko podataka i mogućih radnji za agenta.
Ovaj je pristup toliko jednostavan da je cijeli ciklus Osjeti/Misli/Djeluj jedva primjetan. Ali tu je:
- Dio Sense sastoji se od dvije if naredbe. Igra zna gdje je lopta i gdje je platforma, tako da AI traži te informacije u njoj.
- Dio Think je također uključen u dvije if izjave. Oni utjelovljuju dva rješenja, koja se u ovom slučaju međusobno isključuju. Kao rezultat, odabire se jedna od tri radnje - pomaknite platformu ulijevo, pomaknite je udesno ili ne učinite ništa ako je već ispravno postavljena.
- Dio Act nalazi se u izjavama Move Paddle Left i Move Paddle Right. Ovisno o dizajnu igre, mogu pomicati platformu trenutno ili određenom brzinom.
Takvi se pristupi nazivaju reaktivnim - postoji jednostavan skup pravila (u ovom slučaju izjava u kodu) koji reagiraju na trenutno stanje u svijetu i poduzimaju radnje.
Stablo odlučivanja
Primjer Ponga zapravo je ekvivalentan formalnom konceptu umjetne inteligencije koji se naziva stablo odlučivanja. Algoritam prolazi kroz njega kako bi došao do "lista" - odluke o tome koju radnju poduzeti.
Napravimo blok dijagram stabla odlučivanja za algoritam naše platforme:
Svaki dio stabla naziva se čvor - AI koristi teoriju grafova za opisivanje takvih struktura. Postoje dvije vrste čvorova:
- Čvorovi odlučivanja: odabir između dvije alternative na temelju testiranja nekog uvjeta, gdje je svaka alternativa predstavljena kao zaseban čvor.
- Završni čvorovi: Radnja koju treba izvesti koja predstavlja konačnu odluku.
Algoritam počinje od prvog čvora ("korijena" stabla). Ili donosi odluku o tome na koji će čvor dijete ići ili izvršava radnju pohranjenu u čvoru i izlazi.
Koja je korist od toga da stablo odlučivanja radi isti posao kao if naredbe u prethodnom odjeljku? Ovdje postoji opći sustav u kojem svaka odluka ima samo jedan uvjet i dva moguća ishoda. To razvojnom programeru omogućuje stvaranje umjetne inteligencije iz podataka koji predstavljaju odluke u stablu bez potrebe za hardkodiranjem. Predstavimo to u obliku tablice:
Na strani koda dobit ćete sustav za čitanje nizova. Napravite čvor za svaki od njih, povežite logiku odlučivanja na temelju drugog stupca i podređene čvorove na temelju trećeg i četvrtog stupca. I dalje morate programirati uvjete i akcije, ali sada će struktura igre biti složenija. Ovdje dodajete dodatne odluke i akcije, a zatim prilagođavate cijeli AI jednostavnim uređivanjem tekstualne datoteke definicije stabla. Zatim prenosite datoteku dizajneru igre, koji može promijeniti ponašanje bez ponovnog kompajliranja igre ili mijenjanja koda.
Stabla odlučivanja vrlo su korisna kada se automatski grade iz velikog skupa primjera (na primjer, korištenjem ID3 algoritma). To ih čini učinkovitim i visokoučinkovitim alatom za klasificiranje situacija na temelju dobivenih podataka. Međutim, idemo dalje od jednostavnog sustava za agente za odabir radnji.
scenariji
Analizirali smo sustav stabla odlučivanja koji je koristio unaprijed stvorene uvjete i akcije. Osoba koja dizajnira AI može organizirati stablo kako god želi, ali se i dalje mora osloniti na kodera koji je sve to programirao. Što ako dizajneru možemo dati alate za stvaranje vlastitih uvjeta ili radnji?
Tako da programer ne mora pisati kod za uvjete Is Ball Left Of Paddle i Is Ball Right Of Paddle, on može stvoriti sustav u kojem će dizajner napisati uvjete za provjeru tih vrijednosti. Tada će podaci stabla odlučivanja izgledati ovako:
Ovo je u biti isto kao u prvoj tablici, ali rješenja unutar sebe imaju vlastiti kod, pomalo poput uvjetnog dijela naredbe if. Na strani koda, ovo bi stajalo u drugom stupcu za čvorove odluke, ali umjesto traženja određenog uvjeta za izvršenje (je li lopta lijevo od vesla), procjenjuje uvjetni izraz i prema tome vraća true ili false. To se radi pomoću skriptnog jezika Lua ili Angelscript. Koristeći ih, programer može uzeti objekte u svojoj igri (loptu i veslo) i stvoriti varijable koje će biti dostupne u skripti (ball.position). Također, skriptni jezik je jednostavniji od C++. Ne zahtijeva punu fazu kompilacije, stoga je idealan za brzo prilagođavanje logike igre i omogućuje "nekoderima" da sami kreiraju potrebne funkcije.
U gornjem primjeru, skriptni jezik se koristi samo za procjenu uvjetnog izraza, ali se također može koristiti za akcije. Na primjer, podatak Move Paddle Right mogao bi postati izjava skripte (ball.position.x += 10). Tako da je radnja također definirana u skripti, bez potrebe za programiranjem Move Paddle Right.
Možete ići i dalje i napisati cijelo stablo odlučivanja u skriptnom jeziku. To će biti kod u obliku tvrdo kodiranih uvjetnih naredbi, ali oni će se nalaziti u vanjskim skriptnim datotekama, odnosno moći će se mijenjati bez ponovnog prevođenja cijelog programa. Često možete urediti datoteku skripte tijekom igranja kako biste brzo testirali različite reakcije umjetne inteligencije.
Odgovor na događaj
Gore navedeni primjeri savršeni su za Pong. Oni kontinuirano pokreću ciklus Osjeti/Misli/Djeluj i djeluju na temelju najnovijeg stanja u svijetu. Ali u složenijim igrama treba reagirati na pojedinačne događaje, a ne ocjenjivati sve odjednom. Pong je u ovom slučaju već loš primjer. Izaberimo drugu.
Zamislite pucačinu u kojoj su neprijatelji nepomični dok ne otkriju igrača, nakon čega djeluju ovisno o svojoj “specijalizaciji”: netko će potrčati da “juri”, netko će napasti izdaleka. To je još uvijek osnovni reaktivni sustav - "ako je igrač uočen, učini nešto" - ali se može logično raščlaniti na događaj Igrač viđen i Reakciju (odaberite odgovor i izvršite ga).
Ovo nas vraća na ciklus Osjeti/Misli/Djeluj. Možemo kodirati Sense dio koji će provjeravati svaki okvir vidi li AI igrača. Ako ne, ništa se ne događa, ali ako vidi, stvara se događaj Player Seen. Kod će imati zaseban odjeljak koji kaže "kada se dogodi događaj Player Seen, učinite" gdje je odgovor koji vam je potreban za dijelove Think and Act. Tako ćete postaviti reakcije na događaj Player Seen: za lik koji "žuri" - ChargeAndAttack, a za snajperista - HideAndSnipe. Ovi se odnosi mogu stvoriti u podatkovnoj datoteci za brzo uređivanje bez potrebe za ponovnim kompajliranjem. Ovdje se također može koristiti skriptni jezik.
Donošenje teških odluka
Iako su jednostavni reakcijski sustavi vrlo moćni, postoje mnoge situacije u kojima nisu dovoljni. Ponekad morate donijeti različite odluke na temelju onoga što agent trenutno radi, ali teško je to zamisliti kao uvjet. Ponekad ima previše uvjeta da bi ih se učinkovito predstavilo u stablu odlučivanja ili skripti. Ponekad je potrebno unaprijed procijeniti kako će se situacija promijeniti prije nego što se odlučite na sljedeći korak. Za rješavanje ovih problema potrebni su sofisticiraniji pristupi.
Končni državni stroj
Konačni stroj ili FSM (finite state machine) je način da se kaže da je naš agent trenutno u jednom od nekoliko mogućih stanja, te da može prijeći iz jednog stanja u drugo. Postoji određeni broj takvih država — otuda i naziv. Najbolji primjer iz života je semafor. Postoje različite sekvence svjetala na različitim mjestima, ali princip je isti - svako stanje predstavlja nešto (stani, hodaj, itd.). Semafor je u samo jednom stanju u bilo kojem trenutku i prelazi iz jednog u drugo na temelju jednostavnih pravila.
Slična je priča i s NPC-ima u igrama. Na primjer, uzmimo stražara sa sljedećim stanjima:
- Patroliranje.
- Napadanje.
- Bježeći.
I ovi uvjeti za promjenu stanja:
- Ako stražar vidi neprijatelja, on napada.
- Ako stražar napadne, ali više ne vidi neprijatelja, vraća se u patrolu.
- Ako stražar napadne, ali je teško ranjen, on bježi.
Također možete napisati if-naredbe s varijablom stanja čuvara i raznim provjerama: ima li neprijatelja u blizini, koja je razina zdravlja NPC-a itd. Dodajmo još nekoliko stanja:
- Nerad – između patrola.
- Traženje - kada je uočeni neprijatelj nestao.
- Traženje pomoći - kada je neprijatelj uočen, ali je prejak da se bori sam.
Izbor za svakog od njih je ograničen - na primjer, čuvar neće ići tražiti skrivenog neprijatelja ako ima slabo zdravlje.
Uostalom, postoji ogroman popis "ako" , To " može postati previše glomazan, pa moramo formalizirati metodu koja nam omogućuje da imamo na umu stanja i prijelaze između stanja. Da bismo to učinili, uzimamo u obzir sva stanja i pod svakim stanjem na popisu ispisujemo sve prijelaze u druga stanja, zajedno s uvjetima koji su za njih potrebni.
Ovo je tablica prijelaza stanja - sveobuhvatan način predstavljanja FSM-a. Nacrtajmo dijagram i dobijemo potpuni pregled kako se NPC ponašanje mijenja.
Dijagram odražava bit donošenja odluka za ovog agenta na temelju trenutne situacije. Štoviše, svaka strelica pokazuje prijelaz između stanja ako je uvjet pored nje istinit.
Svakim ažuriranjem provjeravamo trenutno stanje agenta, pregledavamo listu prijelaza i ako su ispunjeni uvjeti za prijelaz, prihvaća novo stanje. Na primjer, svaki okvir provjerava je li 10-sekundni mjerač vremena istekao, i ako jest, tada stražar prelazi iz stanja mirovanja u stanje patroliranja. Na isti način, Attacking stanje provjerava agentovo zdravlje - ako je nisko, onda prelazi u Fleeing stanje.
Ovo je rukovanje prijelazima između stanja, ali što je s ponašanjem povezanim sa samim stanjima? Što se tiče implementacije stvarnog ponašanja za određeno stanje, obično postoje dvije vrste "udica" gdje dodjeljujemo akcije FSM-u:
- Radnje koje povremeno izvodimo za trenutno stanje.
- Radnje koje poduzimamo kada prelazimo iz jednog stanja u drugo.
Primjeri za prvu vrstu. Stanje patroliranja će premjestiti agenta duž patrolne rute svakog okvira. Stanje napada pokušat će pokrenuti napad svaki okvir ili prijelaz u stanje u kojem je to moguće.
Za drugu vrstu, razmislite o prijelazu "ako je neprijatelj vidljiv i neprijatelj je prejak, tada idite u stanje Traženje pomoći". Agent mora odabrati kamo će potražiti pomoć i pohraniti te informacije kako bi stanje Traženje pomoći znalo kamo treba ići. Nakon što je pomoć pronađena, agent se vraća u stanje napada. U ovom trenutku, on će htjeti reći savezniku o prijetnji, tako da se može dogoditi radnja NotifyFriendOfThreat.
Još jednom, ovaj sustav možemo pogledati kroz objektiv ciklusa Osjeti/Misli/Djeluj. Smisao je utjelovljen u podacima koje koristi prijelazna logika. Razmislite - prijelazi dostupni u svakoj državi. A Djelovanje se provodi radnjama koje se povremeno izvode unutar države ili na prijelazima između država.
Ponekad tranzicijski uvjeti traženja mogu biti skupi. Na primjer, ako svaki agent izvodi složene izračune za svaki okvir kako bi utvrdio može li vidjeti neprijatelje i razumjeti može li prijeći iz stanja Patroliranja u stanje Napadanja, to će oduzeti puno CPU vremena.
Važne promjene u stanju svijeta mogu se smatrati događajima koji će se obrađivati kako se događaju. Umjesto da FSM provjerava uvjet prijelaza "može li moj agent vidjeti igrača?" svaki okvir, zasebni sustav može se konfigurirati da provjerava rjeđe (npr. 5 puta u sekundi). A rezultat je izdavanje Player Seen kada provjera prođe.
Ovo se prosljeđuje FSM-u, koji bi sada trebao ići na uvjet primljenog događaja Player Seen i odgovoriti u skladu s tim. Rezultirajuće ponašanje je isto osim gotovo neprimjetnog kašnjenja prije odgovora. Ali performanse su poboljšane kao rezultat odvajanja dijela Sense u zasebni dio programa.
Hijerarhijski konačni stroj
Međutim, rad s velikim FSM-ovima nije uvijek prikladan. Ako želimo proširiti stanje napada kako bismo odvojili Napadanje u blizini i Napadanje iz daljine, morat ćemo promijeniti prijelaze iz svih ostalih stanja koja vode do stanja Napadanje (trenutačno i buduće).
Vjerojatno ste primijetili da u našem primjeru postoji mnogo dvostrukih prijelaza. Većina prijelaza u stanju mirovanja identična je prijelazima u stanju patroliranja. Bilo bi lijepo da se ne ponavljamo, pogotovo ako dodamo još sličnih država. Ima smisla grupirati Prazan hod i Patroliranje pod općom oznakom "ne-borba", gdje postoji samo jedan zajednički skup prijelaza u borbena stanja. Ako ovu oznaku zamislimo kao stanje, tada Prazan hod i Patroliranje postaju podstanja. Primjer korištenja zasebne prijelazne tablice za novo neborbeno podstanje:
Glavna stanja:
Status izvan borbe:
I u obliku dijagrama:
To je isti sustav, ali s novim neborbenim stanjem koje uključuje Idling i Patroling. Sa svakim stanjem koje sadrži FSM s podstanjima (a ta podstanja zauzvrat sadrže svoje vlastite FSM-ove - i tako dalje koliko vam je potrebno), dobivamo hijerarhijski konačni stroj ili HFSM (hijerarhijski konačni stroj). Grupiranjem neborbenog stanja izrezali smo hrpu suvišnih prijelaza. Možemo učiniti isto za sve nove države sa zajedničkim prijelazima. Na primjer, ako u budućnosti proširimo stanje Napadanje na stanja Napadanje u neposrednoj blizini i Napadanje raketama, to će biti podstanja koja prelaze jedno s drugim na temelju udaljenosti do neprijatelja i dostupnosti streljiva. Kao rezultat toga, složena ponašanja i pod-ponašanja mogu se prikazati s minimalnim brojem dvostrukih prijelaza.
Stablo ponašanja
Uz HFSM, složene kombinacije ponašanja stvaraju se na jednostavan način. Međutim, postoji mala poteškoća da je donošenje odluka u obliku prijelaznih pravila usko povezano s trenutnim stanjem. A u mnogim igrama to je upravo ono što je potrebno. Pažljivo korištenje hijerarhije stanja može smanjiti broj ponavljanja prijelaza. Ali ponekad su vam potrebna pravila koja funkcioniraju bez obzira u kojoj se državi nalazite ili koja se primjenjuju u gotovo svim državama. Na primjer, ako agentovo zdravlje padne na 25%, htjet ćete da pobjegne bez obzira na to je li bio u borbi, besposličar ili priča - morat ćete dodati ovaj uvjet svakom stanju. A ako vaš dizajner kasnije poželi promijeniti niski zdravstveni prag s 25% na 10%, to će se morati ponoviti.
U idealnom slučaju, ova situacija zahtijeva sustav u kojem su odluke o tome “u kakvom stanju biti” izvan samih država, kako bi se promjene vršile samo na jednom mjestu i ne dirali prijelazne uvjete. Ovdje se pojavljuju stabla ponašanja.
Postoji nekoliko načina za njihovu implementaciju, ali bit je otprilike ista za sve i slična je stablu odlučivanja: algoritam počinje s "korijenskim" čvorom, a stablo sadrži čvorove koji predstavljaju ili odluke ili akcije. Ipak postoji nekoliko ključnih razlika:
- Čvorovi sada vraćaju jednu od tri vrijednosti: Succeeded (ako je posao dovršen), Failed (ako se ne može pokrenuti) ili Running (ako još uvijek radi i nema konačnog rezultata).
- Nema više čvorova odlučivanja za izbor između dvije alternative. Umjesto toga, oni su Decorator čvorovi, koji imaju jedan podređeni čvor. Ako uspiju, izvršavaju svoj jedini podređeni čvor.
- Čvorovi koji izvode radnje vraćaju vrijednost Running koja predstavlja radnje koje se izvode.
Ovaj mali skup čvorova može se kombinirati za stvaranje velikog broja složenih ponašanja. Zamislimo HFSM čuvar iz prethodnog primjera kao stablo ponašanja:
S ovom strukturom ne bi trebalo biti očitog prijelaza iz stanja praznog hoda/patroliranja u stanje napada ili bilo koje drugo stanje. Ako je neprijatelj vidljiv, a zdravlje lika je slabo, izvršenje će se zaustaviti na čvoru Bježanje, bez obzira na to koji je čvor prethodno izvršavao - Patroliranje, Prazan hod, Napadanje ili bilo koji drugi.
Stabla ponašanja su složena - postoji mnogo načina za njihovo sastavljanje, a pronalaženje prave kombinacije dekoratora i složenih čvorova može biti izazovno. Postavljaju se i pitanja koliko često provjeravati stablo – želimo li proći kroz svaki njegov dio ili samo kada se promijeni jedan od uvjeta? Kako pohranjujemo stanje koje se odnosi na čvorove - kako znamo kada smo bili u stanju mirovanja 10 sekundi ili kako znamo koji su se čvorovi zadnji put izvršavali da bismo mogli pravilno obraditi sekvencu?
Zbog toga postoje mnoge implementacije. Na primjer, neki sustavi su zamijenili čvorove dekoratora s inline dekoratorima. Oni ponovno procjenjuju stablo kada se uvjeti dekoratera promijene, pomažu u spajanju čvorova i pružaju periodična ažuriranja.
Sustav temeljen na komunalnim uslugama
Neke igre imaju mnogo različitih mehanika. Poželjno je da dobiju sve prednosti jednostavnih i općih pravila prijelaza, ali ne nužno u obliku cjelovitog stabla ponašanja. Umjesto jasnog skupa izbora ili stabla mogućih radnji, lakše je ispitati sve akcije i odabrati najprikladniju u ovom trenutku.
Sustav temeljen na uslužnim programima pomoći će upravo u tome. Ovo je sustav u kojem agent ima niz radnji i odabire koje će izvesti na temelju relativne korisnosti svake od njih. Pri čemu je korisnost proizvoljna mjera koliko je važno ili poželjno za agenta da izvrši ovu radnju.
Izračunatu korisnost akcije na temelju trenutnog stanja i okruženja, agent može provjeriti i odabrati najprikladnije drugo stanje u bilo kojem trenutku. Ovo je slično FSM-u, osim gdje su prijelazi određeni procjenom za svako potencijalno stanje, uključujući trenutno. Imajte na umu da biramo najkorisniju radnju za nastavak (ili ostajemo ako smo je već dovršili). Radi veće raznolikosti, ovo bi mogao biti uravnotežen, ali nasumičan odabir s malog popisa.
Sustav dodjeljuje proizvoljan raspon vrijednosti korisnosti—na primjer, od 0 (potpuno nepoželjno) do 100 (potpuno poželjno). Svaka radnja ima niz parametara koji utječu na izračun ove vrijednosti. Vraćamo se na primjer našeg skrbnika:
Prijelazi između radnji dvosmisleni su - svako stanje može slijediti bilo koje drugo. Prioriteti radnji nalaze se u vraćenim vrijednostima korisnosti. Ako je neprijatelj vidljiv, i taj je neprijatelj jak, a zdravlje lika je slabo, tada će i Bježanje i Traženje pomoći vratiti visoke vrijednosti različite od nule. U ovom slučaju, FindingHelp će uvijek biti viši. Isto tako, neborbene aktivnosti nikad ne vraćaju više od 50, tako da će uvijek biti niže od borbenih. To trebate uzeti u obzir prilikom kreiranja akcija i izračunavanja njihove korisnosti.
U našem primjeru, akcije vraćaju ili fiksnu konstantnu vrijednost ili jednu od dvije fiksne vrijednosti. Realističniji sustav vratio bi procjenu iz kontinuiranog raspona vrijednosti. Na primjer, radnja Bježanje vraća veće vrijednosti korisnosti ako je agentovo zdravlje nisko, a radnja Napadanje vraća niže vrijednosti korisnosti ako je neprijatelj prejak. Zbog toga akcija Bijeg ima prednost nad Napadom u svakoj situaciji u kojoj agent smatra da nema dovoljno zdravlja da porazi neprijatelja. To omogućuje određivanje prioriteta radnjama na temelju bilo kojeg broja kriterija, čineći ovaj pristup fleksibilnijim i varijabilnijim od stabla ponašanja ili FSM-a.
Svaka akcija ima mnogo uvjeta za izračun programa. Mogu se pisati u skriptnom jeziku ili kao niz matematičkih formula. The Sims, koji simulira dnevnu rutinu lika, dodaje dodatni sloj kalkulacije - agent dobiva niz "motivacija" koje utječu na ocjene korisnosti. Ako je lik gladan, s vremenom će postati još gladniji, a vrijednost akcije EatFood će se povećavati dok je lik ne izvede, smanjujući razinu gladi i vraćajući vrijednost EatFood na nulu.
Ideja odabira radnji na temelju sustava ocjenjivanja prilično je jednostavna, tako da se sustav temeljen na uslužnim programima može koristiti kao dio procesa donošenja odluka AI-ja, a ne kao potpuna zamjena za njih. Stablo odlučivanja može tražiti ocjenu korisnosti dva podređena čvora i odabrati viši. Slično tome, stablo ponašanja može imati kompozitni Utility čvor za procjenu korisnosti radnji za odlučivanje koje dijete izvršiti.
Kretanje i navigacija
U prethodnim primjerima imali smo platformu koju smo pomicali lijevo ili desno i čuvara koji je patrolirao ili napadao. Ali kako točno rješavamo kretanje agenata tijekom određenog vremenskog razdoblja? Kako odrediti brzinu, kako izbjeći prepreke i kako planirati rutu kada je doći do odredišta teže nego samo kretati se ravnom linijom? Pogledajmo ovo.
Управление
U početnoj fazi pretpostavit ćemo da svaki agent ima vrijednost brzine, koja uključuje koliko se brzo kreće iu kojem smjeru. Može se mjeriti u metrima u sekundi, kilometrima na sat, pikselima u sekundi, itd. Prisjećajući se petlje Sense/Think/Act, možemo zamisliti da dio Think odabire brzinu, a dio Act tu brzinu primjenjuje na agenta. Obično igre imaju sustav fizike koji obavlja ovaj zadatak umjesto vas, učeći vrijednost brzine svakog objekta i prilagođavajući je. Stoga AI možete ostaviti s jednim zadatkom - odlučiti koju bi brzinu agent trebao imati. Ako znate gdje agent treba biti, tada ga morate pomaknuti u pravom smjeru određenom brzinom. Vrlo trivijalna jednadžba:
željeno_putovanje = položaj_odredišta – položaj_agenta
Zamislite 2D svijet. Agent je na točki (-2,-2), odredište je negdje na sjeveroistoku u točki (30, 20), a traženi put agenta do tamo je (32, 22). Recimo da se te pozicije mjere u metrima - ako uzmemo da je brzina agenta 5 metara u sekundi, tada ćemo skalirati naš vektor pomaka i dobiti brzinu od približno (4.12, 2.83). S ovim parametrima agent bi stigao na odredište za gotovo 8 sekundi.
Vrijednosti možete ponovno izračunati u bilo kojem trenutku. Da je agent bio na pola puta do cilja, kretanje bi bilo upola kraće, ali budući da je maksimalna brzina agenta 5 m/s (to smo odlučili gore), brzina će biti ista. Ovo također funkcionira za pokretne mete, dopuštajući agentu da napravi male promjene dok se kreću.
Ali želimo više varijacija - na primjer, polagano povećanje brzine kako bismo simulirali lik koji se kreće iz stajanja u trčanje. Isto se može učiniti na kraju prije zaustavljanja. Ove značajke poznate su kao ponašanja upravljanja, od kojih svaka ima posebna imena: traženje, bijeg, dolazak, itd. Ideja je da se sile ubrzanja mogu primijeniti na brzinu agenta, na temelju usporedbe položaja i trenutne brzine agenta s odredištem u kako bi se koristili različitim metodama kretanja do cilja.
Svako ponašanje ima nešto drugačiju svrhu. Traženje i dolazak načini su premještanja agenta na odredište. Obstacle Avoidance i Separation prilagođavaju kretanje agenta kako bi izbjegao prepreke na putu do cilja. Usklađivanje i kohezija održavaju kretanje agenata zajedno. Bilo koji broj različitih ponašanja upravljanja može se zbrojiti kako bi se dobio jedan vektor putanje uzimajući u obzir sve faktore. Agent koji koristi ponašanje dolaska, odvajanja i izbjegavanja prepreka kako bi se držao podalje od zidova i drugih agenata. Ovaj pristup dobro funkcionira na otvorenim mjestima bez nepotrebnih detalja.
U težim uvjetima zbrajanje različitih ponašanja lošije funkcionira – na primjer, agent može zapeti u zidu zbog sukoba između dolaska i izbjegavanja prepreke. Stoga morate razmotriti opcije koje su složenije od jednostavnog zbrajanja svih vrijednosti. Način je sljedeći: umjesto zbrajanja rezultata svakog ponašanja, možete razmotriti kretanje u različitim smjerovima i odabrati najbolju opciju.
Međutim, u složenom okruženju sa slijepim ulicama i izborom kojim putem ići, trebat ćemo nešto još naprednije.
Pronalaženje načina
Ponašanje upravljanja odlično je za jednostavno kretanje na otvorenom prostoru (nogometno igralište ili dvorana) gdje je dolazak od točke A do točke B ravna staza s manjim obilaskom oko prepreka. Za složene rute potrebno nam je pronalaženje puta, što je način istraživanja svijeta i odlučivanja o ruti kroz njega.
Najjednostavniji je primijeniti mrežu na svako polje pored agenta i procijeniti tko se od njih smije kretati. Ako je jedno od njih odredište, slijedite rutu od svakog kvadrata do prethodnog dok ne dođete do početka. Ovo je put. U suprotnom, ponovite postupak s drugim obližnjim kvadratićima dok ne pronađete svoje odredište ili dok vam ne ponestane kvadratića (što znači da ne postoji moguća ruta). To je ono što je formalno poznato kao Breadth-First Search ili BFS (algoritam za pretraživanje u širinu). Na svakom koraku gleda na sve strane (odatle širina, "širina"). Prostor pretraživanja je poput valne fronte koja se kreće dok ne dosegne željenu lokaciju - prostor pretraživanja se širi na svakom koraku dok se ne uključi krajnja točka, nakon čega se može pratiti natrag do početka.
Kao rezultat, dobit ćete popis kvadrata duž kojih je sastavljena željena ruta. Ovo je put (dakle, pronalaženje puta) - popis mjesta koja će agent posjetiti prateći odredište.
S obzirom na to da znamo položaj svakog kvadrata na svijetu, možemo koristiti ponašanje upravljanja za kretanje duž staze - od čvora 1 do čvora 2, zatim od čvora 2 do čvora 3, i tako dalje. Najjednostavnija opcija je krenuti prema središtu sljedećeg kvadrata, ali još bolja opcija je zaustaviti se na sredini ruba između trenutnog i sljedećeg kvadrata. Zbog toga će agent moći rezati uglove na oštrim zavojima.
BFS algoritam također ima nedostatke - istražuje onoliko kvadrata u "pogrešnom" smjeru koliko i u "pravom" smjeru. Ovdje na scenu stupa složeniji algoritam nazvan A* (A star). Radi na isti način, ali umjesto slijepog ispitivanja susjednih kvadrata (zatim susjeda susjeda, zatim susjeda susjeda susjeda i tako dalje), prikuplja čvorove u popis i razvrstava ih tako da je sljedeći ispitani čvor uvijek onaj koji vodi do najkraćeg puta. Čvorovi se razvrstavaju na temelju heuristike koja uzima u obzir dvije stvari - "cijenu" hipotetske rute do željenog kvadrata (uključujući sve troškove putovanja) i procjenu koliko je taj kvadrat udaljen od odredišta (pristrasno pretraživanje u pravi smjer).
Ovaj primjer pokazuje da agent istražuje jedan po jedan kvadrat, svaki put odabirući onaj susjedni koji najviše obećava. Rezultirajuća putanja je ista kao BFS, ali je manje kvadrata uzeto u obzir u procesu - što ima veliki utjecaj na performanse igre.
Kretanje bez mreže
Ali većina igara nije raspoređena u rešetku i često je to nemoguće učiniti bez žrtvovanja realizma. Potrebni su kompromisi. Koje veličine trebaju biti kvadrati? Preveliki i neće moći ispravno prikazati male hodnike ili skretanja, premali i bit će previše kvadrata za traženje, što će u konačnici oduzeti puno vremena.
Prva stvar koju treba razumjeti je da nam mreža daje graf povezanih čvorova. Algoritmi A* i BFS zapravo rade na grafovima i uopće ih nije briga za našu mrežu. Čvorove možemo postaviti bilo gdje u svijetu igre: sve dok postoji veza između bilo koja dva povezana čvora, kao i između početne i krajnje točke i barem jednog od čvorova, algoritam će raditi jednako dobro kao i prije. To se često naziva sustav putnih točaka, budući da svaki čvor predstavlja značajnu poziciju u svijetu koja može biti dio bilo kojeg broja hipotetskih staza.
Primjer 1: čvor u svakom kvadratu. Pretraga počinje od čvora u kojem se nalazi agent i završava na čvoru željenog kvadrata.
Primjer 2: Manji skup čvorova (putnih točaka). Pretraga počinje na kvadratu agenta, prolazi kroz potreban broj čvorova i zatim se nastavlja do odredišta.
Ovo je potpuno fleksibilan i moćan sustav. Ali potrebna je određena pažnja pri odlučivanju gdje i kako postaviti putnu točku, inače agenti jednostavno neće vidjeti najbližu točku i neće moći započeti putanju. Bilo bi lakše kad bismo mogli automatski postaviti međutočke na temelju geometrije svijeta.
Ovdje se pojavljuje navigacijska mreža ili navmesh (navigacijska mreža). Ovo je obično 2D mreža trokuta koja je prekrivena geometrijom svijeta - gdje god je agentu dopušteno hodati. Svaki od trokuta u mreži postaje čvor na grafikonu i ima do tri susjedna trokuta koji postaju susjedni čvorovi na grafikonu.
Ova slika je primjer iz Unity motora - analizirao je geometriju u svijetu i stvorio navmrežu (na snimci zaslona u svijetlo plavoj boji). Svaki poligon u navigacijskoj mreži je područje na kojem agent može stajati ili se kretati s jednog poligona na drugi poligon. U ovom primjeru, poligoni su manji od katova na kojima se nalaze - to je učinjeno kako bi se uzela u obzir veličina agenta, koja će se protezati izvan svog nominalnog položaja.
Možemo tražiti rutu kroz ovu mrežu, opet koristeći A* algoritam. To će nam dati gotovo savršenu rutu u svijetu, koja uzima u obzir svu geometriju i ne zahtijeva nepotrebne čvorove i stvaranje međutočaka.
Pathfinding je preopširna tema za koju jedan dio članka nije dovoljan. Ako ga želite detaljnije proučiti, onda će vam ovo pomoći .
planiranje
S pronalaženjem puta naučili smo da ponekad nije dovoljno samo odabrati smjer i krenuti - moramo odabrati rutu i nekoliko puta skrenuti kako bismo došli do željenog odredišta. Možemo generalizirati ovu ideju: postizanje cilja nije samo sljedeći korak, već čitav niz u kojem ponekad morate gledati nekoliko koraka unaprijed kako biste saznali koji bi trebao biti prvi. To se zove planiranje. Pronalaženje puta može se smatrati jednim od nekoliko proširenja planiranja. U smislu našeg ciklusa Razmišljaj/Misli/Djeluj, ovdje dio Razmišljanja planira više dijelova Djelovanja za budućnost.
Pogledajmo primjer društvene igre Magic: The Gathering. Idemo prvi sa sljedećim kompletom karata u rukama:
- Močvara - Daje 1 crnu manu (karta zemlje).
- Šuma - daje 1 zelenu manu (karta zemlje).
- Čarobnjak bjegunac - Za prizivanje je potrebna 1 plava mana.
- Elvish Mystic - Za prizivanje je potrebna 1 zelena mana.
Ignoriramo preostale tri karte kako bismo olakšali. Prema pravilima, igraču je dopušteno odigrati 1 kartu zemlje po potezu, on može "dodirnuti" ovu kartu kako bi iz nje izvukao manu, a zatim bacati čarolije (uključujući prizivanje stvorenja) u skladu s količinom mane. U ovoj situaciji, ljudski igrač zna igrati Forest, dodirnuti 1 zelenu manu, a zatim pozvati Elvish Mystic. Ali kako umjetna inteligencija u igri to može shvatiti?
Jednostavno planiranje
Trivijalan pristup je pokušati svaku radnju redom dok ne ostane nijedna prikladna. Gledajući karte, AI vidi što Swamp može igrati. I svira ga. Ima li još nekih radnji na ovom skretanju? Ne može prizvati ni vilenjačkog mistika ni čarobnjaka bjegunca jer im je potrebna zelena i plava mana da bi ih pozvali, dok Močvara daje samo crnu manu. I više neće moći igrati Šumu, jer je već igrao Močvaru. Dakle, igra AI slijedila je pravila, ali je to činila loše. Može se poboljšati.
Planiranje može pronaći popis radnji koje dovode igru u željeno stanje. Kao što je svaki kvadrat na stazi imao susjede (u traženju putanje), svaka radnja u planu također ima susjede ili nasljednike. Možemo tražiti te radnje i naknadne radnje dok ne postignemo željeno stanje.
U našem primjeru, željeni rezultat je "pozvati stvorenje ako je moguće." Na početku poteza vidimo samo dvije moguće akcije dopuštene pravilima igre:
1. Igrajte Swamp (rezultat: Swamp u igri)
2. Igrajte Šumu (rezultat: Šuma u igrici)
Svaka poduzeta akcija može dovesti do daljnjih akcija i zatvoriti druge, opet ovisno o pravilima igre. Zamislite da smo igrali Močvaru - ovo će ukloniti Močvaru kao sljedeći korak (već smo je igrali), a ovo će također ukloniti Šumu (jer prema pravilima možete igrati jednu kartu zemlje po potezu). Nakon ovoga, AI dodaje dobivanje 1 crne mane kao sljedeći korak jer nema drugih opcija. Ako krene naprijed i odabere Tap the Swamp, dobit će 1 jedinicu crne mane i neće moći ništa učiniti s njom.
1. Igrajte Swamp (rezultat: Swamp u igri)
1.1 "Tap" Močvara (rezultat: Močvara "tapnuta", +1 jedinica crne mane)
Nema dostupnih radnji - KRAJ
2. Igrajte Šumu (rezultat: Šuma u igrici)
Lista akcija je bila kratka, došli smo u slijepu ulicu. Ponavljamo postupak za sljedeći korak. Igramo Forest, otvorimo akciju "dobijte 1 zelenu manu", koja će zauzvrat otvoriti treću akciju - pozovite Elvish Mystic.
1. Igrajte Swamp (rezultat: Swamp u igri)
1.1 "Tap" Močvara (rezultat: Močvara "tapnuta", +1 jedinica crne mane)
Nema dostupnih radnji - KRAJ
2. Igrajte Šumu (rezultat: Šuma u igrici)
2.1 Šuma "dodirni" (rezultat: šuma je "dodirnuta", +1 jedinica zelene mane)
2.1.1 Pozvati Elvish Mystic (rezultat: Elvish Mystic u igri, -1 zelena mana)
Nema dostupnih radnji - KRAJ
Na kraju smo istražili sve moguće akcije i pronašli plan koji priziva stvorenje.
Ovo je vrlo pojednostavljen primjer. Preporučljivo je odabrati najbolji mogući plan, a ne bilo koji plan koji zadovoljava neke kriterije. Općenito je moguće procijeniti potencijalne planove na temelju ishoda ili ukupne koristi njihove provedbe. Možete osvojiti 1 bod za igranje zemlje karte i 3 boda za pozivanje stvorenja. Igrati Močvaru bio bi plan od 1 boda. I igranje Forest → Tap the Forest → summon Elvish Mystic će odmah dati 4 boda.
Ovako planiranje funkcionira u Magic: The Gathering, ali ista logika vrijedi iu drugim situacijama. Na primjer, pomicanje pješaka kako bi se napravio prostor za potez lovca u šahu. Ili se sklonite iza zida i sigurno pucajte u ovakvom XCOM-u. Općenito, shvatili ste.
Poboljšano planiranje
Ponekad ima previše potencijalnih radnji da bismo razmotrili svaku moguću opciju. Vraćajući se na primjer s Magic: The Gathering: recimo da u igri iu vašoj ruci postoji nekoliko karata zemlje i stvorenja - broj mogućih kombinacija poteza može biti u desecima. Postoji nekoliko rješenja problema.
Prva metoda je ulančavanje unazad. Umjesto isprobavanja svih kombinacija, bolje je krenuti s konačnim rezultatom i pokušati pronaći izravan put. Umjesto da idemo od korijena stabla do određenog lista, krećemo se u suprotnom smjeru – od lista prema korijenu. Ova metoda je lakša i brža.
Ako neprijatelj ima 1 zdravlje, možete pronaći plan "nanijeti 1 ili više štete". Da bi se to postiglo potrebno je ispuniti niz uvjeta:
1. Šteta može biti uzrokovana čarolijom - mora biti u ruci.
2. Da biste bacili čaroliju, potrebna vam je mana.
3. Da biste dobili manu, morate odigrati kartu zemlje.
4. Da biste igrali zemljišnu kartu, morate je imati u ruci.
Drugi način je pretraživanje prvo najbolje. Umjesto da isprobamo sve putove, biramo onaj koji nam najviše odgovara. Ova metoda najčešće daje optimalan plan bez nepotrebnih troškova pretraživanja. A* je oblik najboljeg prvog pretraživanja - ispitivanjem ruta koje najviše obećavaju od početka, već može pronaći najbolju stazu bez provjeravanja drugih opcija.
Zanimljiva i sve popularnija opcija pretraživanja najboljeg prvog je Monte Carlo Tree Search. Umjesto pogađanja koji su planovi bolji od drugih pri odabiru svake sljedeće akcije, algoritam odabire nasumične nasljednike u svakom koraku dok ne dođe do kraja (kada je plan rezultirao pobjedom ili porazom). Konačni rezultat se zatim koristi za povećanje ili smanjenje težine prethodnih opcija. Ponavljanjem ovog procesa nekoliko puta zaredom, algoritam daje dobru procjenu najboljeg sljedećeg poteza, čak i ako se situacija promijeni (ako neprijatelj poduzme akciju da ometa igrača).
Niti jedna priča o planiranju u igrama ne bi bila potpuna bez ciljano usmjerenog akcijskog planiranja ili GOAP-a (goal-oriented action planning). Ovo je naširoko korištena metoda i o kojoj se raspravlja, ali osim nekoliko razlikovnih detalja, to je u biti metoda ulančavanja unatrag o kojoj smo ranije govorili. Ako je cilj bio "uništiti igrača", a igrač je iza zaklona, plan bi mogao biti: uništiti granatom → uzeti je → baciti.
Obično postoji nekoliko ciljeva, svaki sa svojim prioritetom. Ako se cilj najvišeg prioriteta ne može dovršiti (nikakva kombinacija radnji ne stvara plan "ubiti igrača" jer igrač nije vidljiv), AI će se vratiti na ciljeve nižeg prioriteta.
Trening i prilagodba
Već smo rekli da AI igre obično ne koristi strojno učenje jer nije prikladno za upravljanje agentima u stvarnom vremenu. Ali to ne znači da ne možete posuditi nešto s ovog područja. Želimo protivnika u šuteru od kojeg možemo nešto naučiti. Na primjer, saznajte koje su najbolje pozicije na karti. Ili protivnik u borbenoj igri koji bi blokirao igračeve često korištene kombinirane poteze, motivirajući ga da koristi druge. Dakle, strojno učenje može biti vrlo korisno u takvim situacijama.
Statistika i vjerojatnosti
Prije nego što prijeđemo na složene primjere, pogledajmo koliko daleko možemo ići poduzimajući nekoliko jednostavnih mjerenja i koristeći ih za donošenje odluka. Na primjer, strategija u stvarnom vremenu - kako odrediti može li igrač pokrenuti napad u prvih nekoliko minuta igre i kakvu obranu pripremiti protiv toga? Možemo proučavati igračeva prošla iskustva kako bismo razumjeli kakve bi mogle biti buduće reakcije. Za početak, nemamo tako neobrađene podatke, ali ih možemo prikupiti - svaki put kada AI igra protiv čovjeka, može zabilježiti vrijeme prvog napada. Nakon nekoliko sesija dobit ćemo prosjek vremena koje će igraču trebati za napad u budućnosti.
Također postoji problem s prosječnim vrijednostima: ako je igrač žurio 20 puta i igrao sporo 20 puta, tada će tražene vrijednosti biti negdje u sredini, a to nam neće dati ništa korisno. Jedno od rješenja je ograničenje ulaznih podataka - može se uzeti u obzir zadnjih 20 komada.
Sličan pristup se koristi kada se procjenjuje vjerojatnost određenih radnji uz pretpostavku da će igračeve prošle preferencije biti iste u budućnosti. Ako nas igrač pet puta napadne vatrenom kuglom, dva puta munjom i jednom meleeom, očito je da više voli vatrenu kuglu. Ekstrapolirajmo i vidimo vjerojatnost korištenja različitih oružja: vatrena kugla=62,5%, munja=25% i gužva=12,5%. Naša igra AI mora se pripremiti za zaštitu od vatre.
Još jedna zanimljiva metoda je korištenje Naive Bayesovog klasifikatora za proučavanje velikih količina ulaznih podataka i klasificiranje situacije tako da AI reagira na željeni način. Bayesovi klasifikatori najpoznatiji su po svojoj upotrebi u filtrima neželjene e-pošte. Tamo ispituju riječi, uspoređuju ih s mjestima na kojima su se te riječi ranije pojavljivale (u neželjenoj pošti ili ne) i donose zaključke o dolaznim e-porukama. Možemo učiniti istu stvar čak i s manje unosa. Na temelju svih korisnih informacija koje AI vidi (kao što su neprijateljske jedinice koje su stvorene, ili koje čarolije koriste, ili koje su tehnologije istraživali), i konačni rezultat (rat ili mir, juriš ili obrana, itd.) - mi ćemo izabrati željeno ponašanje AI.
Sve ove metode obuke su dovoljne, ali ih je preporučljivo koristiti na temelju podataka testiranja. AI će se naučiti prilagoditi različitim strategijama koje su koristili vaši igrači. AI koji se prilagođava igraču nakon puštanja može postati previše predvidljiv ili previše težak za poraz.
Prilagodba temeljena na vrijednosti
S obzirom na sadržaj našeg svijeta igre i pravila, možemo promijeniti skup vrijednosti koje utječu na donošenje odluka, umjesto da jednostavno koristimo ulazne podatke. Mi radimo ovo:
- Neka AI prikuplja podatke o stanju svijeta i ključnim događajima tijekom igre (kao gore).
- Promijenimo nekoliko važnih vrijednosti na temelju ovih podataka.
- Naše odluke provodimo na temelju obrade ili procjene tih vrijednosti.
Na primjer, agent ima nekoliko soba za odabir na karti pucačine iz prvog lica. Svaka soba ima svoju vrijednost, koja određuje koliko je poželjna za posjet. AI nasumično odabire u koju će sobu otići na temelju vrijednosti. Agent se tada prisjeća u kojoj je sobi ubijen i smanjuje joj vrijednost (vjerojatnost da će se tamo vratiti). Slično je i za obrnutu situaciju - ako agent uništi mnogo protivnika, tada vrijednost sobe raste.
Markovljev model
Što ako bismo prikupljene podatke koristili za predviđanje? Ako zapamtimo svaku sobu u kojoj vidimo igrača u određenom vremenskom razdoblju, predvidjet ćemo u koju bi sobu igrač mogao otići. Praćenjem i bilježenjem kretanja igrača po sobama (vrijednosti), možemo ih predvidjeti.
Uzmimo tri sobe: crvenu, zelenu i plavu. I također zapažanja koja smo zabilježili dok smo gledali sesiju igre:
Broj promatranja u svakoj sobi je gotovo jednak - još uvijek ne znamo gdje napraviti dobro mjesto za zasjedu. Prikupljanje statistike također je komplicirano ponovnom pojavom igrača, koji se ravnomjerno pojavljuju po cijeloj mapi. Ali podaci o sljedećoj sobi u koju ulaze nakon pojavljivanja na karti već su korisni.
Vidi se da zelena soba odgovara igračima - većina ljudi prelazi iz crvene sobe u nju, njih 50% ostaje tamo i dalje. Plava soba, naprotiv, nije popularna, u nju gotovo nitko ne ide, a ako i ide, ne ostaje dugo.
No podaci nam govore nešto važnije – kada je igrač u plavoj sobi, sljedeća soba u kojoj ga vidimo bit će crvena, a ne zelena. Iako je zelena soba popularnija od crvene sobe, situacija se mijenja ako je igrač u plavoj sobi. Sljedeće stanje (tj. soba u koju će igrač otići) ovisi o prethodnom stanju (tj. sobi u kojoj se igrač trenutno nalazi). Budući da istražujemo ovisnosti, dat ćemo točnija predviđanja nego da jednostavno neovisno brojimo opažanja.
Predviđanje budućeg stanja na temelju podataka iz prošlog stanja naziva se Markovljev model, a takvi primjeri (sa sobama) nazivaju se Markovljevi lanci. Budući da uzorci predstavljaju vjerojatnost promjena između uzastopnih stanja, oni se vizualno prikazuju kao FSM s vjerojatnošću oko svakog prijelaza. Prethodno smo koristili FSM za predstavljanje bihevioralnog stanja u kojem je agent bio, ali ovaj se koncept proširuje na bilo koje stanje, bilo da je povezano s agentom ili ne. U ovom slučaju stanja predstavljaju sobu koju agent zauzima:
Ovo je jednostavan način predstavljanja relativne vjerojatnosti promjena stanja, dajući umjetnoj inteligenciji mogućnost predviđanja sljedećeg stanja. Možete predvidjeti nekoliko koraka unaprijed.
Ako je igrač u zelenoj sobi, postoji 50% šanse da će ostati tamo sljedeći put kada ga netko promatra. No, kolike su šanse da će i poslije ostati tamo? Ne samo da postoji šansa da je igrač ostao u zelenoj sobi nakon dva promatranja, već također postoji šansa da je otišao i vratio se. Evo nove tablice koja uzima u obzir nove podatke:
Pokazuje da će šansa vidjeti igrača u zelenoj sobi nakon dva promatranja biti jednaka 51% - 21% da će biti iz crvene sobe, 5% njih da će igrač posjetiti plavu sobu između njih, a 25% da igrač neće napustiti zelenu sobu.
Tablica je jednostavno vizualni alat - postupak zahtijeva samo množenje vjerojatnosti u svakom koraku. To znači da možete gledati daleko u budućnost uz jedno upozorenje: pretpostavljamo da mogućnost ulaska u sobu u potpunosti ovisi o trenutnoj sobi. To se zove Markovljevo svojstvo - buduće stanje ovisi samo o sadašnjosti. Ali ovo nije sto posto točno. Igrači mogu promijeniti odluke ovisno o drugim čimbenicima: razini zdravlja ili količini streljiva. Budući da ne bilježimo te vrijednosti, naše će prognoze biti manje točne.
N-grama
Što je s primjerom borbene igre i predviđanjem igračevih kombiniranih poteza? Isto! Ali umjesto jednog stanja ili događaja, ispitat ćemo cijele sekvence koje čine kombinirani udarac.
Jedan od načina da to učinite je pohraniti svaki unos (kao što je Kick, Punch ili Block) u međuspremnik i zapisati cijeli međuspremnik kao događaj. Dakle, igrač opetovano pritišće Kick, Kick, Punch kako bi upotrijebio napad SuperDeathFist, AI sustav pohranjuje sve unose u međuspremnik i pamti zadnja tri korištena u svakom koraku.
(Crte podebljane su kada igrač pokrene napad SuperDeathFist.)
AI će vidjeti sve opcije kada igrač odabere Kick, nakon čega slijedi još jedan Kick, a zatim primijeti da je sljedeći unos uvijek Punch. To će omogućiti agentu da predvidi kombinirani potez SuperDeathFista i blokira ga ako je moguće.
Ovi nizovi događaja nazivaju se N-grami, gdje je N broj pohranjenih elemenata. U prethodnom primjeru to je bio 3-gram (trigram), što znači: prva dva unosa koriste se za predviđanje trećeg. Sukladno tome, u 5-gramskom, prva četiri unosa predviđaju peti i tako dalje.
Dizajner mora pažljivo odabrati veličinu N-grama. Manji N zahtijeva manje memorije, ali i pohranjuje manje povijesti. Na primjer, 2-gramski (bigram) će zabilježiti Kick, Kick ili Kick, Punch, ali neće moći pohraniti Kick, Kick, Punch, tako da AI neće odgovoriti na kombinaciju SuperDeathFist.
S druge strane, veći brojevi zahtijevaju više memorije i AI će biti teže trenirati jer će biti mnogo više mogućih opcija. Ako imate tri moguća unosa Kick, Punch ili Block, a mi koristimo 10-gramski, to bi bilo oko 60 tisuća različitih opcija.
Model bigrama je jednostavan Markovljev lanac - svaki par prošlo stanje/trenutačno stanje je bigram, a drugo stanje možete predvidjeti na temelju prvog. 3-gramski i veći N-grami također se mogu smatrati Markovljevim lancima, gdje svi elementi (osim zadnjeg u N-gramu) zajedno tvore prvo stanje, a zadnji element drugo. Primjer borbene igre pokazuje mogućnost prijelaza iz stanja Kick and Kick u stanje Kick and Punch. Tretirajući višestruke unose povijesti unosa kao jednu jedinicu, u biti transformiramo slijed unosa u dio cijelog stanja. Ovo nam daje Markovljevo svojstvo, koje nam omogućuje da koristimo Markovljeve lance za predviđanje sljedećeg unosa i nagađanje koji će kombinirani potez biti sljedeći.
Zaključak
Razgovarali smo o najčešćim alatima i pristupima u razvoju umjetne inteligencije. Također smo pogledali situacije u kojima ih je potrebno koristiti i gdje su posebno korisni.
Ovo bi trebalo biti dovoljno za razumijevanje osnova AI igre. Ali, naravno, to nisu sve metode. Manje popularni, ali ne manje učinkoviti uključuju:
- optimizacijski algoritmi uključujući penjanje uzbrdo, spuštanje uz nagib i genetske algoritme
- algoritmi adversarnog pretraživanja/raspoređivanja (minimax i alpha-beta skraćivanje)
- metode klasifikacije (perceptroni, neuronske mreže i strojevi za potporne vektore)
- sustavi za obradu percepcije i pamćenja agenata
- arhitektonski pristupi AI (hibridni sustavi, arhitekture podskupova i drugi načini preklapanja AI sustava)
- alati za animaciju (planiranje i koordinacija pokreta)
- čimbenici izvedbe (razina detalja, bilo kada i algoritmi vremenskog odsječka)
Online izvori na temu:
1. GameDev.net ima I .
2. sadrži mnoge prezentacije i članke o širokom rasponu tema povezanih s razvojem umjetne inteligencije u igrama.
3. uključuje teme s GDC AI Summita, od kojih su mnoge dostupne besplatno.
4. Korisni materijali također se mogu pronaći na web stranici .
5. Tommy Thompson, AI istraživač i programer igrica, snima videe na YouTubeu uz objašnjenje i proučavanje AI u komercijalnim igrama.
Knjige na temu:
1. Serija knjiga Game AI Pro zbirka je kratkih članaka koji objašnjavaju kako implementirati određene značajke ili kako riješiti specifične probleme.
2. AI Game Programming Wisdom serija je prethodnik Game AI Pro serije. Sadrži starije metode, ali gotovo sve su relevantne i danas.
3. jedan je od temeljnih tekstova za sve koji žele razumjeti opće područje umjetne inteligencije. Ovo nije knjiga o razvoju igrica - ona podučava osnove umjetne inteligencije.
Izvor: www.habr.com