Naletel sem na zanimivo gradivo o umetni inteligenci v igrah. Z razlago osnovnih stvari o AI na preprostih primerih, v notranjosti pa je veliko uporabnih orodij in metod za njegov udoben razvoj in oblikovanje. Tam je tudi, kako, kje in kdaj jih uporabiti.
Večina primerov je napisanih v psevdo kodi, zato ni potrebno napredno znanje programiranja. Pod rezom je 35 listov besedila s slikami in gifi, zato se pripravite.
UPD. Opravičujem se, vendar sem že naredil svoj prevod tega članka na Habréju . Lahko preberete njegovo različico , vendar me je članek iz nekega razloga sprešel (uporabil sem iskalnik, vendar je šlo nekaj narobe). In ker pišem na blogu, namenjenem razvoju iger, sem se odločil, da svojo različico prevoda pustim naročnikom (nekatere točke so oblikovane drugače, nekatere so bile po nasvetu razvijalcev namerno izpuščene).
Kaj je AI?
Igralna umetna inteligenca se osredotoča na dejanja, ki jih mora izvesti predmet glede na pogoje, v katerih se nahaja. To se običajno imenuje upravljanje "inteligentnega agenta", kjer je agent lik igralca, vozilo, bot ali včasih nekaj bolj abstraktnega: celotna skupina subjektov ali celo civilizacija. V vsakem primeru gre za stvar, ki mora videti svoje okolje, se na podlagi tega odločati in delovati v skladu z njim. To se imenuje cikel Sense/Think/Act:
- Občutek: agent najde ali prejme informacije o stvareh v svojem okolju, ki lahko vplivajo na njegovo vedenje (grožnje v bližini, predmeti za zbiranje, zanimiva mesta za raziskovanje).
- Pomisli: Agent se odloči, kako se bo odzval (premisli, ali je dovolj varno zbirati predmete ali naj se najprej bori/skrije).
- Delovanje: agent izvede dejanja za izvedbo prejšnje odločitve (začne se premikati proti sovražniku ali objektu).
- ...zdaj se je situacija spremenila zaradi dejanj likov, tako da se cikel ponavlja z novimi podatki.
AI se ponavadi osredotoča na Sense del zanke. Na primer, avtonomni avtomobili posnamejo slike ceste, jih združijo z radarskimi in lidarskimi podatki ter jih interpretirajo. To se običajno izvaja s strojnim učenjem, ki obdeluje dohodne podatke in jim daje pomen ter izloča semantične informacije, kot je "še en avto je 20 jardov pred vami." To so tako imenovani problemi klasifikacije.
Igre ne potrebujejo zapletenega sistema za pridobivanje informacij, saj je večina podatkov že njihov sestavni del. Ni potrebe po zagonu algoritmov za prepoznavanje slik, da bi ugotovili, ali je pred vami sovražnik – igra to že ve in posreduje informacije neposredno v postopek odločanja. Zato je smiselni del cikla pogosto veliko enostavnejši od dela Misli in ukrepaj.
Omejitve igre AI
AI ima številne omejitve, ki jih je treba upoštevati:
- AI ni treba usposobiti vnaprej, kot če bi šlo za algoritem strojnega učenja. Nima smisla pisati nevronske mreže med razvojem za spremljanje deset tisoč igralcev in učenje najboljšega načina igranja proti njim. Zakaj? Ker igra ni bila izdana in ni igralcev.
- Igra mora biti zabavna in polna izzivov, zato agenti ne bi smeli najti najboljšega pristopa proti ljudem.
- Agenti morajo izgledati realistično, da se igralci počutijo, kot da igrajo proti resničnim ljudem. Program AlphaGo je presegel ljudi, vendar so bili izbrani koraki zelo daleč od tradicionalnega razumevanja igre. Če igra simulira človeškega nasprotnika, tega občutka ne bi smelo biti. Algoritem je treba spremeniti tako, da bo sprejemal verjetne odločitve in ne idealnih.
- AI mora delovati v realnem času. To pomeni, da algoritem ne more monopolizirati uporabe procesorja za daljša obdobja za sprejemanje odločitev. Celo 10 milisekund je predolgo, saj večina iger potrebuje le 16 do 33 milisekund, da opravijo vso obdelavo in preidejo na naslednji grafični okvir.
- V idealnem primeru bi moral vsaj del sistema temeljiti na podatkih, tako da lahko nekoderji hitreje izvajajo spremembe in prilagoditve.
Oglejmo si pristope AI, ki pokrivajo celoten cikel Sense/Think/Act.
Sprejemanje osnovnih odločitev
Začnimo z najpreprostejšo igro - pong. Cilj: premaknite veslo tako, da se žogica odbije od njega, namesto da bi letela mimo njega. To je kot tenis, kjer izgubiš, če ne udariš žogice. Tukaj ima AI relativno enostavno nalogo - odločiti se, v katero smer premakniti platformo.
Pogojni operaterji
Za umetno inteligenco v Pongu je najočitnejša rešitev, da platformo vedno poskušate postaviti pod žogo.
Preprost algoritem za to, napisan v psevdokodi:
vsak okvir/posodobitev med tekom igre:
če je žoga levo od vesla:
premakni veslo levo
drugače, če je žoga desno od vesla:
premakni veslo desno
Če se platforma premika s hitrostjo žogice, potem je to idealen algoritem za AI v Pongu. Ni treba nič komplicirati, če ni toliko podatkov in možnih dejanj agenta.
Ta pristop je tako preprost, da je celoten cikel Sense/Think/Act komaj opazen. Ampak tam je:
- Del Sense je v dveh stavkih if. Igra ve, kje je žoga in kje je platforma, zato AI išče te informacije pri njej.
- Del Think je prav tako vključen v dva stavka if. Poosebljata dve rešitvi, ki se v tem primeru med seboj izključujeta. Kot rezultat je izbrano eno od treh dejanj - premaknite platformo v levo, premaknite jo v desno ali ne storite ničesar, če je že pravilno postavljena.
- Del Act je v izjavah Move Paddle Left in Move Paddle Right. Odvisno od zasnove igre lahko premaknejo platformo takoj ali z določeno hitrostjo.
Takšni pristopi se imenujejo reaktivni - obstaja preprost niz pravil (v tem primeru izjave v kodi), ki se odzivajo na trenutno stanje v svetu in ukrepajo.
Odločitveno drevo
Primer Pong je dejansko enakovreden formalnemu konceptu AI, imenovanemu drevo odločitev. Algoritem gre skozi to, da doseže "list" - odločitev o tem, kaj naj izvede.
Naredimo blokovni diagram odločitvenega drevesa za algoritem naše platforme:
Vsak del drevesa se imenuje vozlišče - AI uporablja teorijo grafov za opis takih struktur. Obstajata dve vrsti vozlišč:
- Odločitvena vozlišča: izbira med dvema alternativama na podlagi testiranja nekega pogoja, kjer je vsaka alternativa predstavljena kot ločeno vozlišče.
- Končna vozlišča: Dejanje za izvedbo, ki predstavlja končno odločitev.
Algoritem se začne s prvim vozliščem ("koren" drevesa). Bodisi se odloči, na katero podrejeno vozlišče naj gre, ali pa izvede dejanje, shranjeno v vozlišču, in zapusti.
Kakšna je prednost, če odločitveno drevo opravlja isto nalogo kot stavke if v prejšnjem razdelku? Tukaj je splošen sistem, kjer ima vsaka odločitev le en pogoj in dva možna rezultata. To omogoča razvijalcu, da ustvari AI iz podatkov, ki predstavljajo odločitve v drevesu, ne da bi ga morali trdo kodirati. Predstavimo ga v obliki tabele:
Na strani kode boste dobili sistem za branje nizov. Ustvarite vozlišče za vsako od njih, povežite logiko odločanja na podlagi drugega stolpca in podrejena vozlišča na podlagi tretjega in četrtega stolpca. Še vedno morate programirati pogoje in dejanja, vendar bo zdaj struktura igre bolj zapletena. Tukaj dodate dodatne odločitve in dejanja ter nato prilagodite celotno umetno inteligenco s preprostim urejanjem besedilne datoteke drevesne definicije. Nato prenesete datoteko oblikovalcu igre, ki lahko spremeni vedenje brez ponovnega prevajanja igre ali spreminjanja kode.
Odločitvena drevesa so zelo uporabna, če so samodejno zgrajena iz velikega nabora primerov (na primer z uporabo algoritma ID3). Zaradi tega so učinkovito in visoko zmogljivo orodje za razvrščanje situacij na podlagi pridobljenih podatkov. Vendar presegamo preprost sistem za agente za izbiro dejanj.
Scenariji
Analizirali smo sistem odločitvenega drevesa, ki je uporabil vnaprej ustvarjene pogoje in dejanja. Oseba, ki oblikuje umetno inteligenco, lahko organizira drevo, kakor hoče, vendar se mora še vedno zanesti na kodirnika, ki je vse programiral. Kaj pa, če bi lahko oblikovalcu dali orodja za ustvarjanje lastnih pogojev ali dejanj?
Da programerju ni treba pisati kode za pogoja Is Ball Left Of Paddle in Is Ball Right Of Paddle, lahko ustvari sistem, v katerega bo oblikovalec zapisal pogoje za preverjanje teh vrednosti. Potem bodo podatki drevesa odločitev videti takole:
To je v bistvu enako kot v prvi tabeli, vendar imajo rešitve same po sebi lastno kodo, podobno pogojnemu delu stavka if. Na strani kode bi se to glasilo v drugem stolpcu za vozlišča odločitve, vendar namesto iskanja določenega pogoja za izvedbo (Je žoga levo od vesla), ovrednoti pogojni izraz in ustrezno vrne true ali false. To se naredi z uporabo skriptnega jezika Lua ali Angelscript. Z njihovo uporabo lahko razvijalec vzame predmete v svoji igri (žoga in veslo) in ustvari spremenljivke, ki bodo na voljo v skriptu (ball.position). Poleg tega je skriptni jezik enostavnejši od C++. Ne zahteva popolne stopnje prevajanja, zato je idealen za hitro prilagajanje logike igre in omogoča »nekoderjem«, da sami ustvarijo potrebne funkcije.
V zgornjem primeru se skriptni jezik uporablja samo za ovrednotenje pogojnega izraza, lahko pa se uporablja tudi za dejanja. Na primer, podatek Move Paddle Right bi lahko postal skriptni stavek (ball.position.x += 10). Tako, da je dejanje definirano tudi v scenariju, ne da bi bilo treba programirati Move Paddle Right.
Lahko greste še dlje in napišete celotno drevo odločitev v skriptnem jeziku. To bo koda v obliki trdo kodiranih pogojnih stavkov, ki pa se bodo nahajali v zunanjih skriptnih datotekah, kar pomeni, da jih bo mogoče spremeniti brez ponovnega prevajanja celotnega programa. Datoteko skripta lahko pogosto uredite med igranjem, da hitro preizkusite različne odzive AI.
Odziv na dogodek
Zgornji primeri so popolni za Pong. Nenehno izvajajo cikel razum/misli/delovanje in delujejo na podlagi najnovejšega stanja sveta. Toda v kompleksnejših igrah se morate odzvati na posamezne dogodke in ne ocenjevati vsega naenkrat. Pong je v tem primeru že slab primer. Izberimo drugega.
Predstavljajte si strelec, v katerem so sovražniki nepremični, dokler ne zaznajo igralca, nato pa ukrepajo glede na svojo »specializacijo«: nekdo bo tekel, da bi »hitel«, nekdo bo napadel od daleč. To je še vedno osnovni reaktivni sistem - "če je igralec opažen, naredi nekaj" - vendar ga je mogoče logično razdeliti na dogodek Player Seen in Reaction (izberi odgovor in ga izvedi).
To nas pripelje nazaj v cikel Smisel/Razmišljanje/Dejanje. Lahko kodiramo del Sense, ki bo preveril vsak okvir, ali AI vidi igralca. Če ne, se ne zgodi nič, če pa vidi, se ustvari dogodek Player Seen. Koda bo imela ločen razdelek z napisom "ko pride do dogodka Player Seen, stori", kjer je odgovor, ki ga potrebujete za obravnavanje delov Think and Act. Tako boste nastavili reakcije na dogodek Player Seen: za lik, ki "hiti" - ChargeAndAttack, in za ostrostrelca - HideAndSnipe. Ta razmerja je mogoče ustvariti v podatkovni datoteki za hitro urejanje, ne da bi jih bilo treba ponovno prevesti. Tudi tukaj je mogoče uporabiti skriptni jezik.
Sprejemanje težkih odločitev
Čeprav so preprosti reakcijski sistemi zelo zmogljivi, obstaja veliko situacij, kjer niso dovolj. Včasih je treba sprejeti različne odločitve glede na to, kaj agent trenutno počne, vendar si je to težko predstavljati kot pogoj. Včasih je preveč pogojev, da bi jih lahko učinkovito predstavili v odločitvenem drevesu ali skriptu. Včasih morate vnaprej oceniti, kako se bodo razmere spremenile, preden se odločite za naslednji korak. Za rešitev teh težav so potrebni bolj sofisticirani pristopi.
Končni stroj
Končni avtomat ali FSM (finite state machine) je način, da povemo, da je naš agent trenutno v enem od več možnih stanj in da lahko prehaja iz enega stanja v drugo. Obstaja določeno število takih stanj - od tod tudi ime. Najboljši primer iz življenja je semafor. Na različnih mestih so različna zaporedja luči, vendar je princip enak - vsako stanje predstavlja nekaj (ustavi se, hodi itd.). Semafor je v danem trenutku samo v enem stanju in se premika iz enega v drugega na podlagi preprostih pravil.
Podobna zgodba je z NPC-ji v igrah. Za primer vzemimo stražarja z naslednjimi stanji:
- Patruljiranje.
- Napadanje.
- beg.
In ti pogoji za spremembo njegovega stanja:
- Če stražar vidi sovražnika, napade.
- Če stražar napade, vendar ne vidi več sovražnika, se vrne v patruljo.
- Če stražar napade, a je hudo ranjen, pobegne.
Napišete lahko tudi izjave if s spremenljivko stanja varuha in različnimi preverjanji: ali je v bližini sovražnik, kakšna je zdravstvena stopnja NPC-ja itd. Dodajmo še nekaj stanj:
- Brezdelje – med patruljami.
- Iskanje - ko je opaženi sovražnik izginil.
- Iskanje pomoči - ko je sovražnik opažen, vendar je premočan, da bi se boril sam.
Izbira za vsakega od njih je omejena - na primer, stražar ne bo šel iskat skritega sovražnika, če ima slabo zdravje.
Navsezadnje obstaja ogromen seznam "če" , To " lahko postanejo preveč okorni, zato moramo formalizirati metodo, ki nam omogoča, da upoštevamo stanja in prehode med stanji. Pri tem upoštevamo vsa stanja in pod vsako stanje na seznam zapišemo vse prehode v druga stanja skupaj s pogoji, ki so zanje potrebni.
To je tabela prehodov stanj - celovit način za predstavitev FSM. Narišimo diagram in dobimo popoln pregled nad tem, kako se spreminja vedenje NPC.
Diagram odraža bistvo odločanja za tega agenta glede na trenutno situacijo. Poleg tega vsaka puščica prikazuje prehod med stanji, če je pogoj zraven resničen.
Pri vsaki posodobitvi preverimo trenutno stanje agenta, pregledamo seznam prehodov in če so izpolnjeni pogoji za prehod, sprejme novo stanje. Vsak okvir na primer preveri, ali je 10-sekundni časovnik potekel, in če je tako, potem stražar preide iz stanja prostega teka v stanje patruljiranja. Na enak način Attacking stanje preveri zdravje agenta – če je nizko, gre v stanje Fleeing.
To obravnava prehode med stanji, kaj pa vedenje, povezano s samimi stanji? Kar zadeva implementacijo dejanskega vedenja za določeno stanje, običajno obstajata dve vrsti "kavljev", kjer FSM dodelimo dejanja:
- Dejanja, ki jih periodično izvajamo za trenutno stanje.
- Dejanja, ki jih izvajamo ob prehodu iz enega stanja v drugo.
Primeri za prvo vrsto. Stanje patruljiranja bo agenta premaknilo po patruljni poti vsak okvir. Stanje napada bo poskušalo sprožiti napad vsak okvir ali prehod v stanje, kjer je to mogoče.
Za drugo vrsto upoštevajte prehod »če je sovražnik viden in je sovražnik premočan, pojdite v stanje Iskanje pomoči. Agent mora izbrati, kam naj se obrne po pomoč, in te informacije shraniti, da stanje Iskanje pomoči ve, kam naj se obrne. Ko je pomoč najdena, se agent vrne v stanje napada. Na tej točki bo želel povedati zavezniku o grožnji, zato se lahko zgodi dejanje NotifyFriendOfThreat.
Še enkrat lahko na ta sistem pogledamo skozi optiko cikla Sense/Think/Act. Smisel je utelešen v podatkih, ki jih uporablja prehodna logika. Pomislite - prehodi so na voljo v vsaki državi. In Act se izvaja z dejanji, ki se občasno izvajajo znotraj države ali na prehodih med državami.
Včasih so prehodni pogoji neprekinjenega glasovanja lahko dragi. Na primer, če vsak agent izvaja zapletene izračune za vsak okvir, da ugotovi, ali lahko vidi sovražnike in razume, ali lahko preide iz stanja patruljiranja v stanje napada, bo to vzelo veliko časa procesorja.
Pomembne spremembe v stanju sveta si lahko predstavljamo kot dogodke, ki bodo obdelani, ko se zgodijo. Namesto, da bi FSM preverjal prehodni pogoj "ali moj agent vidi igralca?" vsak okvir, je mogoče konfigurirati ločen sistem za manj pogosto preverjanje (npr. 5-krat na sekundo). In rezultat je izdaja Player Seen, ko je preverjanje uspešno.
To se posreduje FSM-ju, ki bi moral zdaj preiti na prejeto stanje dogodka Player Seen in se ustrezno odzvati. Posledično vedenje je enako, razen skoraj neopazne zamude pred odzivom. Toda zmogljivost se je izboljšala zaradi ločitve dela Sense v ločen del programa.
Hierarhični končni avtomat
Vendar pa delo z velikimi FSM ni vedno priročno. Če želimo stanje napada razširiti tako, da ločimo MeleeAttacking in RangedAttacking, bomo morali spremeniti prehode iz vseh drugih stanj, ki vodijo v stanje Attacking (trenutno in prihodnje).
Verjetno ste opazili, da je v našem primeru veliko podvojenih prehodov. Večina prehodov v stanju prostega teka je enakih prehodom v stanju patruljiranja. Lepo bi bilo, da se ne ponavljamo, sploh če dodamo več podobnih držav. Smiselno je združiti Idling in Patrulling pod splošno oznako "neborbe", kjer obstaja le en skupen niz prehodov v bojna stanja. Če si to oznako predstavljamo kot stanje, potem Idling in Patrulling postaneta podstanji. Primer uporabe ločene prehodne tabele za novo nebojno podstanje:
Glavna stanja:
Status izven boja:
In v obliki diagrama:
To je isti sistem, vendar z novim nebojnim stanjem, ki vključuje prosti tek in patruljiranje. Z vsakim stanjem, ki vsebuje FSM s podstanji (in ta podstanja nato vsebujejo svoje lastne FSM - in tako naprej, kolikor dolgo potrebujete), dobimo hierarhični končni stroj ali HFSM (hierarhični končni avtomat). Z združevanjem nebojnega stanja smo izrezali kup odvečnih prehodov. Enako lahko storimo za vsa nova stanja s skupnimi prehodi. Na primer, če v prihodnosti razširimo stanje napada na stanji MeleeAttacking in MissileAttacking, bosta to podstanji, ki prehajata med seboj na podlagi razdalje do sovražnika in razpoložljivosti streliva. Posledično je mogoče zapletena vedenja in podvedenja predstaviti z najmanj podvojenimi prehodi.
Drevo obnašanja
S HFSM se na preprost način ustvarijo kompleksne kombinacije vedenj. Vendar pa obstaja majhna težava, da je odločanje v obliki prehodnih pravil tesno povezano s trenutnim stanjem. In v mnogih igrah je to točno tisto, kar je potrebno. Previdna uporaba hierarhije stanja lahko zmanjša število ponovitev prehodov. Toda včasih potrebujete pravila, ki delujejo ne glede na to, v kateri državi ste, ali ki veljajo v skoraj vseh državah. Na primer, če agentovo zdravje pade na 25 %, boste želeli, da pobegne ne glede na to, ali je bil v boju, v mirovanju ali je govoril – ta pogoj boste morali dodati vsakemu stanju. In če bo vaš načrtovalec pozneje želel spremeniti nizek zdravstveni prag s 25 % na 10 %, bo to treba storiti znova.
V idealnem primeru ta situacija zahteva sistem, v katerem so odločitve o tem, »v kakšnem stanju biti«, zunaj samih držav, da se spremembe izvajajo samo na enem mestu in se ne dotikajo prehodnih pogojev. Tu se prikažejo drevesa vedenja.
Obstaja več načinov za njihovo implementacijo, vendar je bistvo približno enako za vse in je podobno drevesu odločitev: algoritem se začne s "korenskim" vozliščem, drevo pa vsebuje vozlišča, ki predstavljajo odločitve ali dejanja. Vendar obstaja nekaj ključnih razlik:
- Vozlišča zdaj vrnejo eno od treh vrednosti: Uspešno (če je opravilo dokončano), Neuspešno (če ga ni mogoče zagnati) ali Teče (če še vedno poteka in ni končnega rezultata).
- Ni več odločitvenih vozlišč za izbiro med dvema alternativama. Namesto tega so vozlišča Decorator, ki imajo eno podrejeno vozlišče. Če jim uspe, izvedejo svoje edino podrejeno vozlišče.
- Vozlišča, ki izvajajo dejanja, vrnejo vrednost Running, ki predstavlja dejanja, ki se izvajajo.
Ta majhen nabor vozlišč je mogoče kombinirati, da se ustvari veliko število kompleksnih vedenj. Predstavljajmo si varovalo HFSM iz prejšnjega primera kot drevo obnašanja:
Pri tej strukturi ne bi smelo biti očitnega prehoda iz stanja prostega teka/patruljiranja v stanje napada ali katera koli druga stanja. Če je sovražnik viden in je zdravje lika nizko, se bo izvajanje ustavilo pri vozlišču Bežanje, ne glede na to, katero vozlišče je predhodno izvajalo – Patruljiranje, V prostem teku, Napadanje ali katero koli drugo.
Drevesa vedenja so zapletena – obstaja veliko načinov za njihovo sestavljanje in iskanje prave kombinacije okrasiteljev in sestavljenih vozlišč je lahko izziv. Pojavljajo se tudi vprašanja o tem, kako pogosto preverjati drevo – ali želimo iti skozi vsak del ali le, ko se spremeni eden od pogojev? Kako shranimo stanje, ki se nanaša na vozlišča – kako vemo, kdaj smo bili v prostem teku 10 sekund, ali kako vemo, katera vozlišča so se zadnjič izvajala, da lahko pravilno obdelamo zaporedje?
Zato obstaja veliko izvedb. Na primer, nekateri sistemi so vozlišča dekoratorjev zamenjali z vgrajenimi dekoratorji. Ponovno ovrednotijo drevo, ko se spremenijo pogoji dekoraterja, pomagajo pri združevanju vozlišč in zagotavljajo redne posodobitve.
Sistem, ki temelji na pripomočkih
Nekatere igre imajo veliko različnih mehanik. Zaželeno je, da so deležni vseh prednosti preprostih in splošnih prehodnih pravil, vendar ne nujno v obliki popolnega drevesa obnašanja. Namesto da bi imeli jasen nabor izbir ali drevo možnih dejanj, je lažje pregledati vsa dejanja in izbrati trenutno najprimernejšega.
Sistem, ki temelji na pripomočkih, bo pomagal ravno pri tem. To je sistem, v katerem ima agent vrsto dejanj in izbere, katera bo izvedel na podlagi relativne uporabnosti vsakega. Pri čemer je uporabnost poljubna mera tega, kako pomembno ali zaželeno je, da agent izvede to dejanje.
Izračunano uporabnost dejanja, ki temelji na trenutnem stanju in okolju, lahko agent kadar koli preveri in izbere najprimernejše drugo stanje. To je podobno FSM, razen kjer so prehodi določeni z oceno za vsako potencialno stanje, vključno s trenutnim. Upoštevajte, da izberemo najbolj uporabno dejanje za nadaljevanje (ali ostanemo, če smo ga že izvedli). Za večjo raznolikost je to lahko uravnotežen, a naključen izbor z majhnega seznama.
Sistem dodeli poljuben razpon vrednosti uporabnosti – na primer od 0 (popolnoma nezaželeno) do 100 (popolnoma zaželeno). Vsako dejanje ima več parametrov, ki vplivajo na izračun te vrednosti. Če se vrnemo k primeru našega skrbnika:
Prehodi med dejanji so dvoumni - vsako stanje lahko sledi kateremu koli drugemu. Prednostne naloge dejanj najdete v vrnjenih vrednostih uporabnosti. Če je sovražnik viden in je ta močan ter je zdravje lika nizko, bosta tako Beg kot Iskanje pomoči vrnila visoke vrednosti, ki niso enake nič. V tem primeru bo FindingHelp vedno višji. Prav tako nebojne dejavnosti nikoli ne vrnejo več kot 50, zato bodo vedno nižje od bojnih. To morate upoštevati pri ustvarjanju dejanj in izračunu njihove uporabnosti.
V našem primeru dejanja vrnejo bodisi fiksno konstantno vrednost ali eno od dveh fiksnih vrednosti. Bolj realističen sistem bi vrnil oceno iz neprekinjenega obsega vrednosti. Na primer, dejanje Bežanje vrne višje vrednosti uporabnosti, če je zdravje agenta slabo, dejanje Napadanje pa vrne nižje vrednosti uporabnosti, če je sovražnik premočan. Zaradi tega ima dejanje Bežanje prednost pred Napadanjem v vsaki situaciji, ko agent meni, da nima dovolj zdravja, da bi premagal sovražnika. To omogoča prednostno razvrščanje dejanj na podlagi poljubnega števila kriterijev, zaradi česar je ta pristop bolj prilagodljiv in spremenljiv kot drevo obnašanja ali FSM.
Vsako dejanje ima veliko pogojev za izračun programa. Lahko so napisani v skriptnem jeziku ali kot niz matematičnih formul. Sims, ki simulira vsakodnevno rutino lika, dodaja dodatno plast izračuna - agent prejme vrsto "motivacije", ki vpliva na ocene uporabnosti. Če je lik lačen, bo sčasoma postal še bolj lačen in vrednost uporabnosti dejanja EatFood se bo povečevala, dokler ga lik ne izvede, s čimer se zmanjša raven lakote in vrne vrednost EatFood na nič.
Zamisel o izbiri dejanj na podlagi sistema ocenjevanja je precej preprosta, zato je mogoče sistem, ki temelji na pripomočkih, uporabiti kot del procesov odločanja z umetno inteligenco in ne kot popolno nadomestilo zanje. Odločitveno drevo lahko zahteva oceno uporabnosti dveh podrejenih vozlišč in izbere višje. Podobno ima lahko drevo vedenja sestavljeno vozlišče Utility za ovrednotenje uporabnosti dejanj za odločitev, katerega podrejenega elementa izvesti.
Gibanje in navigacija
V prejšnjih primerih smo imeli platformo, ki smo jo premikali levo ali desno, in stražarja, ki je patruljiral ali napadal. Toda kako natančno obravnavamo gibanje agentov v določenem časovnem obdobju? Kako določimo hitrost, kako se izognemo oviram in kako načrtujemo pot, ko je priti na cilj težje kot le premikanje v ravni črti? Poglejmo si to.
Upravljanje
Na začetni stopnji bomo predpostavili, da ima vsak agent vrednost hitrosti, ki vključuje, kako hitro se premika in v katero smer. Lahko se meri v metrih na sekundo, kilometrih na uro, slikovnih pikah na sekundo itd. Če prikličemo zanko Sense/Think/Act, si lahko predstavljamo, da del Think izbere hitrost, del Act pa to hitrost uporabi za agenta. Običajno imajo igre fizikalni sistem, ki to nalogo opravi namesto vas, pri čemer se nauči vrednosti hitrosti vsakega predmeta in jo prilagodi. Zato lahko AI zapustite z eno nalogo - odločiti se, kakšno hitrost mora imeti agent. Če veste, kje mora biti agent, ga morate premakniti v pravo smer z nastavljeno hitrostjo. Zelo trivialna enačba:
želeno_potovanje = položaj_destinacije – položaj_agenta
Predstavljajte si 2D svet. Agent je na točki (-2,-2), cilj je nekje na severovzhodu na točki (30, 20), zahtevana pot za agenta do tja pa je (32, 22). Recimo, da so ti položaji merjeni v metrih – če vzamemo, da je hitrost agenta 5 metrov na sekundo, bomo skalirali naš vektor premika in dobili hitrost približno (4.12, 2.83). S temi parametri bi agent prispel na cilj v skoraj 8 sekundah.
Vrednosti lahko kadar koli znova izračunate. Če bi bil agent na polovici poti do cilja, bi bilo gibanje polovično, a ker je največja hitrost agenta 5 m/s (to smo določili zgoraj), bo hitrost enaka. To deluje tudi pri premikajočih se ciljih, kar agentu omogoča majhne spremembe med premikanjem.
Želimo pa več variacij – na primer počasno povečevanje hitrosti, da simuliramo premikanje lika iz stanja v stanje teka. Enako lahko storite na koncu, preden se ustavite. Te funkcije so znane kot vedenje krmiljenja, od katerih ima vsaka določena imena: Iskanje, Beg, Prihod itd. Ideja je, da se sile pospeška lahko uporabijo za agentovo hitrost na podlagi primerjave agentovega položaja in trenutne hitrosti s ciljem v da uporabite različne metode premikanja do cilja.
Vsako vedenje ima nekoliko drugačen namen. Iskanje in prihod sta načina za premikanje agenta na cilj. Obstacle Avoidance in Separation prilagodita gibanje agenta, da se izogne oviram na poti do cilja. Poravnava in kohezija omogočata, da se agenti premikajo skupaj. Poljubno število različnih vedenj krmiljenja je mogoče sešteti, da se ustvari en sam vektor poti ob upoštevanju vseh dejavnikov. Agent, ki uporablja vedenje prihoda, ločitve in izogibanja oviram, da se drži stran od sten in drugih agentov. Ta pristop dobro deluje na odprtih lokacijah brez nepotrebnih podrobnosti.
V težjih razmerah dodajanje različnih vedenj deluje slabše – na primer, agent se lahko zagozdi v steni zaradi konflikta med Prihodom in Izogibanjem oviram. Zato morate razmisliti o možnostih, ki so bolj zapletene kot preprosto dodajanje vseh vrednosti. Način je naslednji: namesto da seštevate rezultate vsakega vedenja, lahko razmislite o gibanju v različnih smereh in izberete najboljšo možnost.
Vendar pa bomo v zapletenem okolju s slepimi ulicami in možnostmi izbire o tem, kam iti, potrebovali nekaj še naprednejšega.
Iskanje poti
Obnašanje krmiljenja je odlično za preprosto gibanje na odprtem območju (nogometno igrišče ali dvorana), kjer je pot od A do B ravna pot z le manjšimi obvozi okoli ovir. Za kompleksne poti potrebujemo pathfinding, ki je način raziskovanja sveta in odločanja o poti skozi njega.
Najenostavneje je, da na vsako polje poleg agenta nanesete mrežo in ocenite, kateri od njih se sme premikati. Če je eden od njih cilj, sledite poti od vsakega polja do prejšnjega, dokler ne pridete do začetka. To je pot. V nasprotnem primeru ponovite postopek z drugimi bližnjimi kvadrati, dokler ne najdete cilja ali vam zmanjka kvadratov (kar pomeni, da ni možne poti). To je tisto, kar je uradno znano kot Breadth-First Search ali BFS (algoritem iskanja v širino). Na vsakem koraku se ozira na vse strani (od tod širina, »širina«). Iskalni prostor je kot valovna fronta, ki se premika, dokler ne doseže želene lokacije – iskalni prostor se širi na vsakem koraku, dokler ni vključena končna točka, po kateri se lahko izsledi nazaj na začetek.
Kot rezultat boste prejeli seznam kvadratov, po katerih je sestavljena želena pot. To je pot (torej iskanje poti) – seznam krajev, ki jih bo agent obiskal med sledenjem cilju.
Glede na to, da poznamo položaj vsakega polja na svetu, lahko uporabimo krmiljenje za premikanje po poti – od vozlišča 1 do vozlišča 2, nato od vozlišča 2 do vozlišča 3 itd. Najenostavnejša možnost je, da se usmerite proti sredini naslednjega kvadrata, še boljša možnost pa je, da se ustavite na sredini roba med trenutnim in naslednjim kvadratom. Zaradi tega bo agent lahko rezal ovinke na ostrih zavojih.
Algoritem BFS ima tudi slabosti - raziskuje toliko kvadratov v "napačni" smeri kot v "pravi" smeri. Tu nastopi bolj zapleten algoritem, imenovan A* (A star). Deluje na enak način, vendar namesto slepega pregleda sosednjih kvadratov (nato sosedov sosedov, nato sosedov sosedov sosedov in tako naprej), zbere vozlišča v seznam in jih razvrsti tako, da je naslednje pregledano vozlišče vedno tista, ki vodi do najkrajše poti. Vozlišča so razvrščena na podlagi hevristike, ki upošteva dve stvari – »ceno« hipotetične poti do želenega kvadrata (vključno z vsemi potnimi stroški) in oceno, kako daleč je ta kvadrat od cilja (pristranskost iskanja v prava smer).
Ta primer kaže, da agent raziskuje en kvadratek naenkrat, pri čemer vsakič izbere sosednjega, ki je najbolj obetaven. Dobljena pot je enaka kot pri BFS, vendar je bilo med postopkom upoštevanih manj polj – kar močno vpliva na zmogljivost igre.
Gibanje brez mreže
Toda večina iger ni postavljenih na mrežo in pogosto je to nemogoče storiti brez žrtvovanja realizma. Potrebni so kompromisi. Kakšne velikosti naj bodo kvadratki? Preveliki in ne bodo mogli pravilno prikazati majhnih hodnikov ali zavojev, premajhni in bo treba iskati preveč polj, kar bo na koncu vzelo veliko časa.
Prva stvar, ki jo moramo razumeti, je, da nam mreža daje graf povezanih vozlišč. Algoritma A* in BFS dejansko delujeta na grafih in ju sploh ne zanima naša mreža. Vozlišča bi lahko postavili kjerkoli v svetu igre: dokler obstaja povezava med katerima koli povezanima vozliščema, pa tudi med začetno in končno točko ter vsaj enim od vozlišč, bo algoritem deloval enako dobro kot prej. To se pogosto imenuje sistem točk poti, saj vsako vozlišče predstavlja pomemben položaj na svetu, ki je lahko del poljubnega števila hipotetičnih poti.
Primer 1: vozel v vsakem kvadratu. Iskanje se začne na vozlišču, kjer se nahaja agent, in konča na vozlišču želenega kvadrata.
Primer 2: Manjši niz vozlišč (točke poti). Iskanje se začne na kvadratu agenta, gre skozi zahtevano število vozlišč in se nato nadaljuje do cilja.
To je popolnoma prilagodljiv in zmogljiv sistem. Toda pri odločanju o tem, kje in kako postaviti točko poti, je potrebna nekaj previdnosti, sicer agenti preprosto ne bodo videli najbližje točke in ne bodo mogli začeti poti. Lažje bi bilo, če bi lahko samodejno postavljali točke poti glede na geometrijo sveta.
Tukaj se pojavi navigacijska mreža ali navmesh (navigacijska mreža). To je običajno 2D mreža trikotnikov, ki je prekrita z geometrijo sveta – povsod, kjer je agentu dovoljeno hoditi. Vsak od trikotnikov v mreži postane vozlišče v grafu in ima do tri sosednje trikotnike, ki postanejo sosednja vozlišča v grafu.
Ta slika je primer motorja Unity - analiziral je geometrijo v svetu in ustvaril mrežo za navigacijo (na posnetku zaslona v svetlo modri barvi). Vsak poligon v navigacijski mreži je območje, kjer lahko agent stoji ali se premika iz enega poligona v drugega poligona. V tem primeru so poligoni manjši od nadstropij, v katerih se nahajajo – to je narejeno zato, da se upošteva velikost agenta, ki bo segal preko njegovega nominalnega položaja.
Skozi to mrežo lahko iščemo pot, spet z uporabo algoritma A*. Tako bomo dobili skoraj popolno pot v svetu, ki upošteva vso geometrijo in ne zahteva nepotrebnih vozlišč in ustvarjanja točk poti.
Iskanje poti je preširoka tema, za katero en del članka ni dovolj. Če ga želite podrobneje preučiti, vam bo to pomagalo .
Načrtovanje
Z iskanjem poti smo se naučili, da včasih ni dovolj samo izbrati smer in se premakniti – izbrati moramo pot in narediti nekaj ovinkov, da pridemo do želenega cilja. To idejo lahko posplošimo: doseganje cilja ni samo naslednji korak, ampak celotno zaporedje, kjer je včasih treba pogledati več korakov naprej, da ugotoviš, kateri bi moral biti prvi. To se imenuje načrtovanje. Iskanje poti si lahko predstavljamo kot eno od več razširitev načrtovanja. Kar zadeva naš cikel Sense/Think/Act, tukaj del Think načrtuje več delov Delovanja za prihodnost.
Poglejmo primer namizne igre Magic: The Gathering. Najprej gremo z naslednjim kompletom kart v rokah:
- Močvirje - daje 1 črno mano (zemeljska karta).
- Gozd - daje 1 zeleno mano (zemeljska karta).
- Ubeženi čarovnik - zahteva 1 modro mano za priklic.
- Elvish Mystic - zahteva 1 zeleno mano za priklic.
Preostale tri karte zaradi lažjega ignoriramo. Po pravilih sme igralec odigrati 1 zemljiško karto na potezo, to karto lahko »tapne«, da iz nje izvleče mano, in nato izvaja uroke (vključno s klicanjem bitja) glede na količino mane. V tej situaciji človeški igralec ve, da mora igrati Forest, tapniti 1 zeleno mano in nato priklicati Elvish Mystic. Toda kako lahko AI igre to ugotovi?
Enostavno načrtovanje
Trivialen pristop je poskusiti vsako dejanje po vrsti, dokler ne ostane nobeno primerno. Ko pogleda karte, AI vidi, kaj lahko igra Swamp. In igra ga. Ali so na tem koraku še kakšna dejanja? Ne more priklicati niti Elvish Mystic niti Fugitive Wizard, saj potrebujeta zeleno oziroma modro mano, da ju prikličejo, medtem ko Swamp zagotavlja samo črno mano. In ne bo mogel več igrati Gozda, ker je že igral Močvirje. Tako je umetna inteligenca igre sledila pravilom, vendar je to storila slabo. Lahko se izboljša.
Načrtovanje lahko najde seznam dejanj, ki pripeljejo igro v želeno stanje. Tako kot je imelo vsako polje na poti sosede (pri iskanju poti), ima tudi vsako dejanje v načrtu sosede ali naslednike. Ta dejanja in naslednja dejanja lahko iščemo, dokler ne dosežemo želenega stanja.
V našem primeru je želeni rezultat "priklicati bitje, če je to mogoče." Na začetku poteze vidimo samo dve možni dejanji, ki ju dovoljujejo pravila igre:
1. Igrajte Swamp (rezultat: Swamp v igri)
2. Igrajte Gozd (rezultat: Gozd v igri)
Vsaka izvedena akcija lahko vodi v nadaljnje akcije in zapre druge, spet odvisno od pravil igre. Predstavljajte si, da smo igrali Močvirje - s tem boste odstranili Močvirje kot naslednji korak (igrali smo ga že) in s tem boste odstranili tudi Gozd (ker po pravilih lahko igrate eno zemljiško karto na potezo). Po tem AI kot naslednji korak doda pridobitev 1 črne mane, ker ni drugih možnosti. Če nadaljuje in izbere Tap the Swamp, bo prejel 1 enoto črne mane in z njo ne bo mogel narediti ničesar.
1. Igrajte Swamp (rezultat: Swamp v igri)
1.1 Močvirje »Tap« (rezultat: močvirje »tapped«, +1 enota črne mane)
Na voljo ni nobenih dejanj - KONEC
2. Igrajte Gozd (rezultat: Gozd v igri)
Seznam dejanj je bil kratek, zašli smo v slepo ulico. Postopek ponovimo za naslednji korak. Igramo Forest, odpremo akcijo "dobi 1 zeleno mano", ki bo odprla tretjo akcijo - priklic Elvish Mystic.
1. Igrajte Swamp (rezultat: Swamp v igri)
1.1 Močvirje »Tap« (rezultat: močvirje »tapped«, +1 enota črne mane)
Na voljo ni nobenih dejanj - KONEC
2. Igrajte Gozd (rezultat: Gozd v igri)
2.1 Gozd »Dotaknite se« (rezultat: Gozd je »dotaknjen«, +1 enota zelene mane)
2.1.1 Priklic Elvish Mystic (rezultat: Elvish Mystic v igri, -1 zelena mana)
Na voljo ni nobenih dejanj - KONEC
Na koncu smo raziskali vse možne akcije in našli načrt, ki prikliče bitje.
To je zelo poenostavljen primer. Priporočljivo je, da izberete najboljši možni načrt, namesto katerega koli načrta, ki izpolnjuje nekatera merila. Na splošno je možno oceniti potencialne načrte na podlagi rezultata ali splošne koristi njihovega izvajanja. Z igranjem zemljiške karte si lahko prislužite 1 točko in 3 točke za priklic bitja. Igranje Swampa bi bil načrt z 1 točko. In igranje Forest → Tap the Forest → summon Elvish Mystic bo takoj dalo 4 točke.
Tako deluje načrtovanje v Magic: The Gathering, vendar enaka logika velja tudi v drugih situacijah. Na primer premikanje kmeta, da naredite prostor za premikanje škofa v šahu. Ali pa se pokrijte za zidom in tako varno streljajte v XCOM. Na splošno razumete.
Izboljšano načrtovanje
Včasih je možnih dejanj preveč, da bi lahko razmislili o vseh možnih možnostih. Če se vrnemo k primeru z Magic: The Gathering: recimo, da je v igri in v vaši roki več kart zemlje in bitij - število možnih kombinacij potez je lahko na desetine. Rešitev problema je več.
Prva metoda je vzvratno veriženje. Namesto da preizkušate vse kombinacije, je bolje začeti s končnim rezultatom in poskusiti najti neposredno pot. Namesto od korenine drevesa do določenega lista, se premikamo v nasprotni smeri – od lista do korenine. Ta metoda je lažja in hitrejša.
Če ima sovražnik 1 zdravje, lahko najdete načrt "povzroči 1 ali več škode". Da bi to dosegli, morajo biti izpolnjeni številni pogoji:
1. Škodo lahko povzroči urok - mora biti v roki.
2. Za urok potrebujete mano.
3. Če želite dobiti mano, morate igrati zemljiško karto.
4. Če želite igrati zemljiško karto, jo morate imeti v roki.
Drug način je iskanje najprej najboljše. Namesto da bi preizkusili vse poti, izberemo najprimernejšo. Najpogosteje ta metoda daje optimalen načrt brez nepotrebnih stroškov iskanja. A* je oblika najboljšega prvega iskanja - s preučevanjem najbolj obetavnih poti od začetka lahko že najde najboljšo pot, ne da bi moral preverjati druge možnosti.
Zanimiva in vedno bolj priljubljena možnost iskanja najboljšega prvega je Iskanje po drevesih Monte Carlo. Namesto da bi pri izbiri vsakega naslednjega dejanja ugibal, kateri načrti so boljši od drugih, algoritem na vsakem koraku izbere naključne naslednike, dokler ne pride do konca (ko je načrt privedel do zmage ali poraza). Končni rezultat se nato uporabi za povečanje ali zmanjšanje teže prejšnjih možnosti. S ponavljanjem tega postopka večkrat zaporedoma algoritem dobro oceni, katera je najboljša naslednja poteza, tudi če se situacija spremeni (če sovražnik ukrepa in moti igralca).
Nobena zgodba o načrtovanju v igrah ne bi bila popolna brez ciljno usmerjenega akcijskega načrtovanja ali GOAP (ciljno usmerjeno akcijsko načrtovanje). To je pogosto uporabljena metoda, o kateri se razpravlja, vendar je razen nekaj razločevalnih podrobnosti v bistvu metoda vzvratnega veriženja, o kateri smo govorili prej. Če je bil cilj "uničiti igralca" in je igralec v kritju, bi lahko bil načrt: uniči z granato → dobi jo → vrže.
Običajno je ciljev več, vsak ima svojo prioriteto. Če cilja z najvišjo prednostjo ni mogoče dokončati (nobena kombinacija dejanj ne ustvari načrta "ubiti igralca", ker igralec ni viden), se AI vrne k ciljem z nižjo prioriteto.
Usposabljanje in prilagajanje
Rekli smo že, da umetna inteligenca v igrah običajno ne uporablja strojnega učenja, ker ni primeren za upravljanje agentov v realnem času. A to ne pomeni, da si s tega področja ne morete izposoditi česa. Želimo si nasprotnika v strelcu, od katerega se lahko nekaj naučimo. Pozanimajte se na primer o najboljših položajih na zemljevidu. Ali nasprotnik v borbeni igri, ki bi blokiral igralčeve pogosto uporabljene kombinirane poteze in ga motiviral, da uporabi druge. Tako je lahko strojno učenje zelo koristno v takih situacijah.
Statistika in verjetnosti
Preden se lotimo zapletenih primerov, poglejmo, kako daleč lahko gremo z nekaj preprostimi meritvami in jih uporabimo za sprejemanje odločitev. Na primer, strategija v realnem času - kako ugotovimo, ali lahko igralec začne napad v prvih nekaj minutah igre in kakšno obrambo pripraviti proti temu? Preučujemo lahko igralčeve pretekle izkušnje, da razumemo, kakšne bodo reakcije v prihodnosti. Za začetek nimamo tako neobdelanih podatkov, vendar jih lahko zberemo - vsakič, ko AI igra proti človeku, lahko zabeleži čas prvega napada. Po nekaj sejah bomo dobili povprečje časa, ki ga bo igralec potreboval za napad v prihodnosti.
Težava je tudi s povprečnimi vrednostmi: če je igralec 20-krat hitel in 20-krat igral počasi, bodo zahtevane vrednosti nekje na sredini in to nam ne bo dalo nič koristnega. Ena od rešitev je omejitev vnosnih podatkov – upošteva se lahko zadnjih 20 kosov.
Podoben pristop se uporablja pri ocenjevanju verjetnosti določenih dejanj ob predpostavki, da bodo igralčeve preference v prihodnosti enake. Če nas igralec petkrat napade z ognjeno kroglo, dvakrat s strelo in enkrat z bližino, je očitno, da ima raje ognjeno kroglo. Ekstrapolirajmo in poglejmo verjetnost uporabe različnih orožij: ognjena krogla=62,5%, strela=25% in blizu=12,5%. Naša igra AI se mora pripraviti, da se zaščiti pred ognjem.
Druga zanimiva metoda je uporaba naivnega Bayesovega klasifikatorja za preučevanje velikih količin vhodnih podatkov in razvrščanje situacije, tako da se AI odzove na želeni način. Bayesovi klasifikatorji so najbolj znani po svoji uporabi v filtrih neželene elektronske pošte. Tam pregledajo besede, jih primerjajo s tistimi, kjer so se te besede pojavljale prej (v vsiljeni pošti ali ne), in sklepajo o prejeti e-pošti. Enako lahko naredimo tudi z manj vložki. Na podlagi vseh uporabnih informacij, ki jih vidi AI (na primer, katere sovražne enote so ustvarjene, ali katere uroke uporabljajo, ali katere tehnologije so raziskovali), in končnega rezultata (vojna ali mir, hitenje ali obramba itd.) - izbrali bomo želeno vedenje AI.
Vse te metode usposabljanja zadostujejo, vendar jih je priporočljivo uporabljati na podlagi podatkov testiranja. Umetna inteligenca se bo naučila prilagajati različnim strategijam, ki so jih uporabili vaši igralci. Umetna inteligenca, ki se po izdaji prilagodi igralcu, lahko postane preveč predvidljiva ali pretežka za poraz.
Prilagajanje na podlagi vrednosti
Glede na vsebino našega igralnega sveta in pravila lahko spremenimo nabor vrednosti, ki vplivajo na odločanje, namesto da preprosto uporabimo vhodne podatke. Naredimo to:
- Naj AI zbira podatke o stanju sveta in ključnih dogodkih med igro (kot zgoraj).
- Spremenimo nekaj pomembnih vrednosti na podlagi teh podatkov.
- Svoje odločitve izvajamo na podlagi obdelave ali vrednotenja teh vrednosti.
Na primer, agent ima na zemljevidu prvoosebne strelske igre več sob, med katerimi lahko izbira. Vsaka soba ima svojo vrednost, ki določa, kako zaželena je za obisk. Umetna inteligenca glede na vrednost naključno izbere, v katero sobo naj gre. Agent si nato zapomni, v kateri sobi je bil umorjen, in zmanjša njeno vrednost (verjetnost, da se bo tja vrnil). Podobno velja za obratno situacijo - če agent uniči veliko nasprotnikov, se vrednost sobe poveča.
Markov model
Kaj pa, če bi zbrane podatke uporabili za napovedi? Če si zapomnimo vsako sobo, v kateri vidimo igralca v določenem časovnem obdobju, bomo predvideli, v katero sobo bi igralec lahko šel. S sledenjem in beleženjem igralčevih premikov po sobah (vrednosti) jih lahko predvidimo.
Vzemimo tri sobe: rdečo, zeleno in modro. In tudi opažanja, ki smo jih zabeležili med gledanjem igre:
Število opazovanj v vsaki sobi je skoraj enako - še vedno ne vemo, kje narediti dobro mesto za zasedo. Zbiranje statistike je zapleteno tudi zaradi ponovnega rojenja igralcev, ki se pojavljajo enakomerno po zemljevidu. Toda podatki o naslednji sobi, v katero vstopijo po pojavu na zemljevidu, so že uporabni.
Vidi se, da zelena soba ustreza igralcem - večina ljudi se preseli iz rdeče sobe vanjo, 50% jih ostane tam naprej. Modra soba, nasprotno, ni priljubljena, vanjo skoraj nihče ne zaide, če pa že, ne ostanejo dolgo.
A podatki nam povedo še nekaj pomembnejšega – ko je igralec v modri sobi, bo naslednja soba, v kateri ga vidimo, rdeča, ne zelena. Čeprav je zelena soba bolj priljubljena od rdeče sobe, se situacija spremeni, če je igralec v modri sobi. Naslednje stanje (tj. soba, v katero bo igralec šel) je odvisna od prejšnjega stanja (tj. sobe, v kateri je igralec trenutno). Ker raziskujemo odvisnosti, bomo naredili natančnejše napovedi, kot če bi zgolj neodvisno šteli opazovanja.
Napovedovanje prihodnjega stanja na podlagi podatkov iz preteklega stanja imenujemo Markovljev model, takšne primere (s sobami) pa Markovljeve verige. Ker vzorci predstavljajo verjetnost sprememb med zaporednimi stanji, so vizualno prikazani kot FSM z verjetnostjo okoli vsakega prehoda. Prej smo uporabljali FSM za predstavitev vedenjskega stanja, v katerem je bil agent, vendar se ta koncept razširi na katero koli stanje, ne glede na to, ali je povezano z agentom ali ne. V tem primeru stanja predstavljajo sobo, ki jo agent zaseda:
To je preprost način za predstavitev relativne verjetnosti sprememb stanja, kar daje AI določeno sposobnost napovedovanja naslednjega stanja. Predvidite lahko več korakov naprej.
Če je igralec v zeleni sobi, obstaja 50-odstotna verjetnost, da bo ostal tam, ko ga bodo naslednjič opazovali. Kakšne pa so možnosti, da bo tudi potem še tam? Ne samo, da obstaja možnost, da je igralec po dveh opazovanjih ostal v zeleni sobi, ampak obstaja tudi možnost, da je odšel in se vrnil. Tukaj je nova tabela z upoštevanjem novih podatkov:
Kaže, da bo možnost, da vidimo igralca v zeleni sobi po dveh opazovanjih enaka 51 % - 21 %, da bo iz rdeče sobe, 5 % jih, da bo igralec obiskal modro sobo med njima, in 25 %, ki jih igralec ne bo zapustil zelene sobe.
Tabela je preprosto vizualno orodje - postopek zahteva samo množenje verjetnosti v vsakem koraku. To pomeni, da lahko pogledate daleč v prihodnost z enim opozorilom: predvidevamo, da je možnost vstopa v sobo v celoti odvisna od trenutne sobe. To se imenuje lastnina Markov - prihodnje stanje je odvisno samo od sedanjosti. Vendar to ni XNUMX % natančno. Igralci lahko spremenijo odločitve glede na druge dejavnike: zdravstveno stanje ali količino streliva. Ker teh vrednosti ne beležimo, bodo naše napovedi manj natančne.
N-gramov
Kaj pa primer borbene igre in napovedovanje igralčevih kombiniranih potez? Enako! Toda namesto enega stanja ali dogodka bomo preučili celotne sekvence, ki sestavljajo kombinirani udarec.
Eden od načinov za to je, da vsak vnos (kot je Kick, Punch ali Block) shranite v medpomnilnik in zapišete celoten medpomnilnik kot dogodek. Tako igralec večkrat pritisne Kick, Kick, Punch, da uporabi napad SuperDeathFist, sistem AI shrani vse vnose v medpomnilnik in si zapomni zadnje tri uporabljene v vsakem koraku.
(Črte v krepkem tisku so, ko igralec sproži napad SuperDeathFist.)
Umetna inteligenca bo videla vse možnosti, ko igralec izbere Kick, čemur sledi še en Kick, in nato opazi, da je naslednji vnos vedno Udarec. To bo agentu omogočilo, da predvidi kombinirano potezo SuperDeathFist in jo blokira, če je to mogoče.
Ta zaporedja dogodkov se imenujejo N-grami, kjer je N število shranjenih elementov. V prejšnjem primeru je bil 3-gramski (trigram), kar pomeni: prva dva vnosa se uporabljata za napovedovanje tretjega. V skladu s tem v 5-gramih prvi štirje vnosi napovedujejo petega in tako naprej.
Oblikovalec mora skrbno izbrati velikost N-gramov. Manjši N zahteva manj pomnilnika, vendar tudi shrani manj zgodovine. Na primer, 2-gramski (bigram) bo posnel Kick, Kick ali Kick, Punch, vendar ne bo mogel shraniti Kick, Kick, Punch, zato se AI ne bo odzval na kombinacijo SuperDeathFist.
Po drugi strani pa večja števila zahtevajo več pomnilnika in AI bo težje trenirati, saj bo na voljo veliko več možnosti. Če bi imeli tri možne vnose Kick, Punch ali Block in bi uporabili 10-gramski, bi bilo to približno 60 tisoč različnih možnosti.
Model bigrama je preprosta Markovljeva veriga - vsak par preteklo stanje/trenutno stanje je bigram in na podlagi prvega lahko napoveste drugo stanje. 3-gramske in večje N-grame si lahko predstavljamo tudi kot Markovljeve verige, kjer vsi elementi (razen zadnjega v N-gramu) skupaj tvorijo prvo stanje, zadnji element pa drugo. Primer borilne igre prikazuje možnost prehoda iz stanja Brc in brc v stanje Brc in udarec. Z obravnavanjem več vnosov zgodovine vnosov kot ene same enote v bistvu spremenimo vnosno zaporedje v del celotnega stanja. To nam daje lastnost Markov, ki nam omogoča uporabo verig Markov za napovedovanje naslednjega vnosa in ugibanje, katera kombinirana poteza bo naslednja.
Zaključek
Pogovarjali smo se o najpogostejših orodjih in pristopih pri razvoju umetne inteligence. Ogledali smo si tudi situacije, v katerih jih je treba uporabiti in kje so še posebej uporabni.
To bi moralo biti dovolj za razumevanje osnov AI igre. Vendar to seveda niso vse metode. Manj priljubljeni, a nič manj učinkoviti vključujejo:
- optimizacijski algoritmi, vključno s plezanjem po hribu, spuščanjem po strminah in genetskimi algoritmi
- kontradiktorni algoritmi iskanja/razporejanja (minimax in alfa-beta obrezovanje)
- klasifikacijske metode (perceptroni, nevronske mreže in podporni vektorski stroji)
- sistemi za obdelavo percepcije in spomina agentov
- arhitekturni pristopi k umetni inteligenci (hibridni sistemi, podmnožične arhitekture in drugi načini prekrivanja sistemov umetne inteligence)
- orodja za animacijo (načrtovanje in koordinacija gibanja)
- dejavniki uspešnosti (raven podrobnosti, kadarkoli in algoritmi za časovno rezanje)
Spletni viri na to temo:
1. GameDev.net ima in .
2. vsebuje veliko predstavitev in člankov o številnih temah, povezanih z razvojem umetne inteligence v igrah.
3. vključuje teme z vrha GDC AI, od katerih jih je veliko na voljo brezplačno.
4. Uporabna gradiva najdete tudi na spletni strani .
5. Tommy Thompson, raziskovalec AI in razvijalec iger, snema videe na YouTubu z razlago in študijem AI v komercialnih igrah.
Knjige na to temo:
1. Serija knjig Game AI Pro je zbirka kratkih člankov, ki pojasnjujejo, kako implementirati določene funkcije ali kako rešiti specifične težave.
2. AI Game Programming Wisdom serija je predhodnica serije Game AI Pro. Vsebuje starejše metode, vendar so skoraj vse aktualne še danes.
3. je eno temeljnih besedil za vse, ki želijo razumeti splošno področje umetne inteligence. To ni knjiga o razvoju iger - uči osnov AI.
Vir: www.habr.com