Narazil som na zaujímavý materiál o umelej inteligencii v hrách. S vysvetlením základných vecí o AI pomocou jednoduchých príkladov a vo vnútri je veľa užitočných nástrojov a metód na jej pohodlný vývoj a dizajn. Ako, kde a kedy ich použiť, je tam tiež.
Väčšina príkladov je napísaná v pseudokóde, takže nie sú potrebné žiadne pokročilé znalosti programovania. Pod strihom je 35 listov textu s obrázkami a gifkami, tak sa pripravte.
UPD. Ospravedlňujem sa, ale už som urobil vlastný preklad tohto článku o Habrém . Môžete si prečítať jeho verziu , ale z nejakého dôvodu ma článok prešiel (použil som vyhľadávanie, ale niečo sa pokazilo). A keďže píšem na blogu venovanom vývoju hier, rozhodol som sa svoju verziu prekladu nechať pre predplatiteľov (niektoré body sú naformátované inak, niektoré boli na radu vývojárov zámerne vynechané).
čo je AI?
Herná AI sa zameriava na to, aké akcie by mal objekt vykonávať na základe podmienok, v ktorých sa nachádza. Toto sa bežne označuje ako riadenie „inteligentného agenta“, kde agentom je postava hráča, vozidlo, bot alebo niekedy niečo abstraktnejšie: celá skupina entít alebo dokonca civilizácia. V každom prípade ide o vec, ktorá musí vidieť svoje prostredie, na základe neho sa rozhodovať a konať v súlade s ním. Toto sa nazýva cyklus Zmysel/Mysli/Konaj:
- Zmysel: Agent nachádza alebo prijíma informácie o veciach vo svojom prostredí, ktoré môžu ovplyvniť jeho správanie (hrozby v okolí, predmety na zber, zaujímavé miesta na preskúmanie).
- Premýšľajte: Agent sa rozhodne, ako zareaguje (zváži, či je dostatočne bezpečné zbierať predmety, alebo či by mal najprv bojovať/skryť sa).
- Akt: agent vykoná akcie na vykonanie predchádzajúceho rozhodnutia (začne sa pohybovať smerom k nepriateľovi alebo objektu).
- ...teraz sa situácia vplyvom postáv postáv zmenila, takže cyklus sa opakuje s novými údajmi.
AI má tendenciu sústrediť sa na časť slučky Sense. Autonómne autá napríklad fotia cestu, kombinujú ich s údajmi z radaru a lidaru a interpretujú ich. Zvyčajne sa to robí strojovým učením, ktoré spracováva prichádzajúce údaje a dáva im význam, pričom extrahuje sémantické informácie, ako napríklad „20 yardov pred vami je ďalšie auto“. Ide o takzvané klasifikačné problémy.
Hry nepotrebujú zložitý systém na získavanie informácií, pretože väčšina údajov je už ich neoddeliteľnou súčasťou. Nie je potrebné spúšťať algoritmy na rozpoznávanie obrazu, aby ste zistili, či je pred nami nepriateľ – hra už vie a vkladá informácie priamo do rozhodovacieho procesu. Preto je časť cyklu Zmysly často oveľa jednoduchšia ako časť Mysli a konaj.
Obmedzenia hry AI
AI má niekoľko obmedzení, ktoré je potrebné dodržiavať:
- AI nie je potrebné trénovať vopred, ako keby to bol algoritmus strojového učenia. Nemá zmysel písať počas vývoja neurónovú sieť, aby ste sledovali desaťtisíce hráčov a naučili sa, ako najlepšie proti nim hrať. prečo? Pretože hra nevyšla a nie sú tam žiadni hráči.
- Hra by mala byť zábavná a náročná, takže agenti by nemali nájsť najlepší prístup proti ľuďom.
- Agenti musia vyzerať realisticky, aby mali hráči pocit, že hrajú proti skutočným ľuďom. Program AlphaGo prekonal ľudí, ale zvolené kroky boli veľmi vzdialené od tradičného chápania hry. Ak hra simuluje ľudského protivníka, tento pocit by nemal existovať. Algoritmus je potrebné zmeniť tak, aby robil skôr prijateľné rozhodnutia ako ideálne.
- AI musí fungovať v reálnom čase. To znamená, že algoritmus nemôže monopolizovať využitie CPU na dlhé časové obdobia, aby mohol robiť rozhodnutia. Aj 10 milisekúnd je príliš dlho, pretože väčšina hier potrebuje iba 16 až 33 milisekúnd na vykonanie celého spracovania a prechod na ďalší grafický rámec.
- V ideálnom prípade by aspoň časť systému mala byť riadená údajmi, aby mohli nekódovači vykonávať zmeny a úpravy rýchlejšie.
Pozrime sa na prístupy AI, ktoré pokrývajú celý cyklus Zmysel/Mysli/Konaj.
Robiť základné rozhodnutia
Začnime s najjednoduchšou hrou - Pong. Cieľ: posunúť lopatku tak, aby sa loptička od nej odrazila a neletela okolo nej. Je to ako tenis, kde prehráte, ak netrafíte loptičku. Tu má AI pomerne ľahkú úlohu - rozhodnúť sa, ktorým smerom pohnúť platformou.
Podmienečné vyhlásenia
Pre AI v Pong je najzrejmejším riešením vždy sa pokúsiť umiestniť platformu pod loptu.
Jednoduchý algoritmus na to, napísaný v pseudokóde:
každá snímka/aktualizácia počas spustenia hry:
ak je loptička naľavo od pádla:
posuňte pádlo doľava
inak, ak je loptička napravo od pádla:
posuňte pádlo doprava
Ak sa platforma pohybuje rýchlosťou lopty, potom je to ideálny algoritmus pre AI v Pong. Netreba nič komplikovať, ak nie je toľko údajov a možných úkonov pre agenta.
Tento prístup je taký jednoduchý, že celý cyklus Zmysel/Mysli/Konaj je sotva postrehnuteľný. Ale je tam:
- Časť Zmysel je v dvoch príkazoch if. Hra vie, kde je lopta a kde je platforma, takže AI hľadá tieto informácie.
- Časť Think je tiež zahrnutá v dvoch príkazoch if. Stelesňujú dve riešenia, ktoré sa v tomto prípade navzájom vylučujú. V dôsledku toho sa vyberie jedna z troch akcií - posuňte plošinu doľava, posuňte ju doprava alebo nerobte nič, ak je už správne umiestnená.
- Časť Act sa nachádza v príkazoch Move Paddle Left a Move Paddle Right. V závislosti od herného dizajnu môžu pohybovať platformou okamžite alebo špecifickou rýchlosťou.
Takéto prístupy sa nazývajú reaktívne - existuje jednoduchý súbor pravidiel (v tomto prípade príkazov v kóde), ktoré reagujú na aktuálny stav sveta a konajú.
Rozhodovací strom
Príklad Pong je v skutočnosti ekvivalentom formálneho konceptu AI nazývaného rozhodovací strom. Algoritmus ním prechádza, aby dosiahol „list“ – rozhodnutie o tom, akú akciu podniknúť.
Urobme blokovú schému rozhodovacieho stromu pre algoritmus našej platformy:
Každá časť stromu sa nazýva uzol – AI používa na opis takýchto štruktúr teóriu grafov. Existujú dva typy uzlov:
- Rozhodovacie uzly: výber medzi dvoma alternatívami na základe testovania nejakej podmienky, kde každá alternatíva je reprezentovaná ako samostatný uzol.
- Koncové uzly: Akcia, ktorá sa má vykonať, ktorá predstavuje konečné rozhodnutie.
Algoritmus začína od prvého uzla („koreň“ stromu). Buď sa rozhodne, na ktorý podriadený uzol pôjde, alebo vykoná akciu uloženú v uzle a ukončí sa.
Aká je výhoda toho, že rozhodovací strom vykonáva rovnakú prácu ako príkazy if v predchádzajúcej časti? Existuje tu všeobecný systém, kde každé rozhodnutie má iba jednu podmienku a dva možné výsledky. To umožňuje vývojárovi vytvárať AI z údajov reprezentujúcich rozhodnutia v strome bez toho, aby ho museli napevno kódovať. Uveďme si to vo forme tabuľky:
Na strane kódu získate systém na čítanie reťazcov. Vytvorte uzol pre každý z nich, pripojte rozhodovaciu logiku založenú na druhom stĺpci a dcérske uzly na základe tretieho a štvrtého stĺpca. Stále musíte naprogramovať podmienky a akcie, ale teraz bude štruktúra hry zložitejšia. Tu pridáte ďalšie rozhodnutia a akcie a potom prispôsobíte celú AI jednoduchou úpravou textového súboru s definíciou stromu. Potom prenesiete súbor k hernému dizajnérovi, ktorý môže zmeniť správanie bez rekompilácie hry alebo zmeny kódu.
Rozhodovacie stromy sú veľmi užitočné, keď sú automaticky zostavené z veľkého súboru príkladov (napríklad pomocou algoritmu ID3). To z nich robí efektívny a vysoko výkonný nástroj na klasifikáciu situácií na základe získaných údajov. Ideme však nad rámec jednoduchého systému pre agentov na výber akcií.
Skriptá
Analyzovali sme systém rozhodovacieho stromu, ktorý využíval vopred vytvorené podmienky a akcie. Osoba, ktorá navrhuje AI, môže organizovať strom, akokoľvek chce, ale stále sa musí spoliehať na kódera, ktorý to všetko naprogramoval. Čo keby sme mohli dať dizajnérovi nástroje na vytváranie vlastných podmienok alebo akcií?
Aby programátor nemusel písať kód pre podmienky Is Ball Left Of Paddle a Is Ball Right Of Paddle, môže si vytvoriť systém, v ktorom bude konštruktér písať podmienky na kontrolu týchto hodnôt. Potom budú údaje rozhodovacieho stromu vyzerať takto:
To je v podstate rovnaké ako v prvej tabuľke, ale riešenia v sebe majú svoj vlastný kód, trochu ako podmienená časť príkazu if. Na strane kódu by to bolo v druhom stĺpci pre rozhodovacie uzly, ale namiesto hľadania konkrétnej podmienky na vykonanie (Is Ball Left Of Paddle) vyhodnotí podmienený výraz a podľa toho vráti hodnotu true alebo false. To sa vykonáva pomocou skriptovacieho jazyka Lua alebo Angelscript. Pomocou nich môže vývojár zobrať objekty vo svojej hre (loptu a pádlo) a vytvoriť premenné, ktoré budú dostupné v skripte (lopta.pozícia). Skriptovací jazyk je tiež jednoduchší ako C++. Nevyžaduje úplnú fázu kompilácie, takže je ideálny na rýchle nastavenie hernej logiky a umožňuje „nekóderom“ vytvárať potrebné funkcie sami.
Vo vyššie uvedenom príklade sa skriptovací jazyk používa iba na vyhodnotenie podmieneného výrazu, ale možno ho použiť aj na akcie. Napríklad údaje Move Paddle Right sa môžu stať príkazom skriptu (ball.position.x += 10). Aby bola akcia definovaná aj v skripte, bez nutnosti programovania Move Paddle Right.
Môžete ísť ešte ďalej a napísať celý rozhodovací strom v skriptovacom jazyku. Bude to kód vo forme pevne zakódovaných podmienených príkazov, ktoré sa však budú nachádzať v externých súboroch skriptov, to znamená, že ich možno zmeniť bez rekompilácie celého programu. Počas hry môžete často upravovať súbor skriptu, aby ste rýchlo otestovali rôzne reakcie AI.
Odozva udalosti
Vyššie uvedené príklady sú ideálne pre Pong. Neustále spúšťajú cyklus Zmysel/Mysli/Konaj a konajú na základe najnovšieho stavu sveta. No v zložitejších hrách treba reagovať na jednotlivé udalosti a nie všetko vyhodnocovať naraz. Pong je v tomto prípade už zlým príkladom. Vyberme si inú.
Predstavte si strieľačku, v ktorej sú nepriatelia nehybní, kým hráča nezistia, a potom konajú v závislosti od svojej „špecializácie“: niekto sa rozbehne, niekto zaútočí z diaľky. Stále ide o základný reaktívny systém – „ak je hráč spozorovaný, urob niečo“ – ale dá sa logicky rozdeliť na udalosť Videný hráč a Reakciu (vyberte odpoveď a spustite ju).
To nás privádza späť do cyklu Zmysel/Mysli/Konaj. Môžeme nakódovať časť Sense, ktorá skontroluje každý snímok, či AI vidí hráča. Ak nie, nič sa nestane, ale ak to uvidí, vytvorí sa udalosť Player Seen. Kód bude mať samostatnú časť, ktorá hovorí „keď nastane udalosť Player Seen, urob“, kde je odpoveď, ktorú potrebujete na riešenie častí Think and Act. Takto nastavíte reakcie na udalosť Player Seen: pre „rútiacu sa“ postavu - ChargeAndAttack a pre ostreľovača - HideAndSnipe. Tieto vzťahy je možné vytvoriť v dátovom súbore pre rýchlu úpravu bez nutnosti prekompilovania. Aj tu je možné použiť skriptovací jazyk.
Robiť ťažké rozhodnutia
Hoci sú jednoduché reakčné systémy veľmi výkonné, existuje veľa situácií, kedy nestačia. Niekedy je potrebné urobiť rôzne rozhodnutia na základe toho, čo agent momentálne robí, ale je ťažké si to predstaviť ako podmienku. Niekedy existuje príliš veľa podmienok na to, aby ich bolo možné efektívne reprezentovať v rozhodovacom strome alebo skripte. Niekedy je potrebné vopred posúdiť, ako sa situácia zmení, kým sa rozhodnete pre ďalší postup. Na vyriešenie týchto problémov sú potrebné sofistikovanejšie prístupy.
Konečný automat
Konečný automat alebo FSM (finite state machine) je spôsob, ako povedať, že náš agent je momentálne v jednom z niekoľkých možných stavov a že môže prechádzať z jedného stavu do druhého. Existuje určitý počet takýchto stavov - odtiaľ názov. Najlepším príkladom zo života je semafor. Na rôznych miestach sú rôzne sekvencie svetiel, ale princíp je rovnaký – každý stav niečo predstavuje (zastavenie, chôdza atď.). Semafor je v danom čase iba v jednom stave a pohybuje sa z jedného do druhého na základe jednoduchých pravidiel.
Je to podobný príbeh s NPC v hrách. Vezmime si napríklad strážcu s nasledujúcimi stavmi:
- Hliadkovanie.
- Útočenie.
- Na úteku.
A tieto podmienky na zmenu jeho stavu:
- Ak strážca vidí nepriateľa, zaútočí.
- Ak strážca zaútočí, ale nepriateľa už nevidí, vráti sa na hliadku.
- Ak strážca zaútočí, ale je ťažko zranený, utečie.
Môžete tiež písať if-príkazy s premennou stavu opatrovníka a rôznymi kontrolami: je v blízkosti nepriateľ, aká je úroveň zdravia NPC atď. Pridajme niekoľko ďalších stavov:
- Nečinnosť - medzi hliadkami.
- Hľadanie - keď zmizol spozorovaný nepriateľ.
- Hľadanie pomoci - keď je nepriateľ spozorovaný, ale je príliš silný na to, aby bojoval sám.
Výber pre každého z nich je obmedzený - napríklad strážca nepôjde hľadať skrytého nepriateľa, ak má nízke zdravie.
Koniec koncov, existuje obrovský zoznam „ak“ , To “ sa môže stať príliš ťažkopádnym, takže musíme formalizovať metódu, ktorá nám umožní mať na pamäti stavy a prechody medzi stavmi. Aby sme to urobili, berieme do úvahy všetky stavy a pod každý stav zapíšeme do zoznamu všetky prechody do iných stavov spolu s podmienkami, ktoré sú pre ne potrebné.
Toto je tabuľka prechodu stavu - komplexný spôsob reprezentácie FSM. Nakreslíme si diagram a získajme úplný prehľad o tom, ako sa mení správanie NPC.
Diagram odráža podstatu rozhodovania tohto agenta na základe aktuálnej situácie. Okrem toho každá šípka ukazuje prechod medzi stavmi, ak je podmienka vedľa nej pravdivá.
Pri každej aktualizácii skontrolujeme aktuálny stav agenta, prezrieme zoznam prechodov a ak sú splnené podmienky na prechod, nový stav akceptuje. Napríklad každý snímok skontroluje, či uplynul 10-sekundový časovač, a ak áno, potom strážnik prejde zo stavu nečinnosti do stavu hliadkovanie. Rovnakým spôsobom stav Útok kontroluje zdravie agenta – ak je nízke, prejde do stavu Útek.
Ide o spracovanie prechodov medzi stavmi, ale čo správanie spojené so samotnými stavmi? Pokiaľ ide o implementáciu skutočného správania pre konkrétny štát, zvyčajne existujú dva typy „háku“, kde priraďujeme akcie MFŠ:
- Akcie, ktoré pravidelne vykonávame pre aktuálny stav.
- Akcie, ktoré vykonávame pri prechode z jedného stavu do druhého.
Príklady pre prvý typ. Stav Hliadka presunie agenta po trase hliadky v každom rámci. Stav Útok sa pokúsi iniciovať útok na každý rámec alebo prechod do stavu, v ktorom je to možné.
Pre druhý typ zvážte prechod „ak je nepriateľ viditeľný a nepriateľ je príliš silný, prejdite do stavu Finding Help. Agent si musí vybrať, kam má vyhľadať pomoc, a uložiť tieto informácie, aby stav Finding Help vedel, kam sa obrátiť. Po nájdení pomoci sa agent vráti do stavu Útok. V tomto momente bude chcieť povedať spojencovi o hrozbe, takže môže nastať akcia NotifyFriendOfThreat.
Opäť sa na tento systém môžeme pozrieť optikou cyklu Zmysel/Mysli/Konaj. Zmysel je stelesnený v údajoch používaných logikou prechodu. Myslite - prechody dostupné v každom štáte. A Act sa vykonáva činnosťami vykonávanými pravidelne v rámci štátu alebo pri prechodoch medzi štátmi.
Niekedy môžu byť prechodné podmienky neustáleho prieskumu nákladné. Napríklad, ak každý agent vykonáva zložité výpočty v každom snímku, aby určil, či vidí nepriateľov a či dokáže prejsť zo stavu hliadkovanie do stavu útočenia, bude to vyžadovať veľa času procesora.
Dôležité zmeny v stave sveta si možno predstaviť ako udalosti, ktoré budú spracované tak, ako sa vyskytnú. Namiesto toho, aby FSM kontroloval prechodovú podmienku „vidí môj agent hráča?“ každý snímok, samostatný systém možno nakonfigurovať tak, aby kontroloval menej často (napr. 5-krát za sekundu). A výsledkom je, že keď kontrola prejde, vydá hráč Videný.
Toto sa odovzdá FSM, ktoré by teraz malo prejsť na podmienku prijatia udalosti Player Seen a zodpovedajúcim spôsobom reagovať. Výsledné správanie je rovnaké až na takmer nepostrehnuteľné oneskorenie pred reakciou. Ale výkon sa zlepšil v dôsledku oddelenia časti Sense do samostatnej časti programu.
Hierarchický konečný automat
Práca s veľkými FSM však nie je vždy pohodlná. Ak chceme stav útoku rozšíriť na oddelenie MeleeAttacking a RangedAttacking, budeme musieť zmeniť prechody zo všetkých ostatných stavov, ktoré vedú do stavu Attacking (súčasný a budúci).
Pravdepodobne ste si všimli, že v našom príklade je veľa duplicitných prechodov. Väčšina prechodov v stave nečinnosti je identická s prechodmi v stave hliadkovanie. Bolo by fajn, aby sme sa neopakovali, najmä ak pridáme viac podobných štátov. Dáva zmysel zoskupiť Idling a Parolling pod všeobecnú nálepku „nebojové“, kde je len jedna spoločná sada prechodov do bojových stavov. Ak o tomto označení uvažujeme ako o stave, potom sa nečinnosť a hliadka stanú podštátmi. Príklad použitia samostatnej tabuľky prechodov pre nový nebojový podštát:
Hlavné štáty:
Stav mimo boja:
A vo forme diagramu:
Je to rovnaký systém, ale s novým nebojovým stavom, ktorý zahŕňa Idling a Parolling. S každým stavom obsahujúcim FSM s podštátmi (a tieto podštáty zase obsahujú svoje vlastné FSM – a tak ďalej, ako dlho potrebujete), dostaneme Hierarchický konečný stroj alebo HFSM (hierarchický konečný stroj). Zoskupením nebojového stavu sme vystrihli kopu nadbytočných prechodov. To isté môžeme urobiť pre všetky nové štáty so spoločnými prechodmi. Napríklad, ak v budúcnosti rozšírime stav Útok na stavy Útok zblízka a Útok raketou, budú to podštáty, ktoré sa medzi sebou prechádzajú na základe vzdialenosti od nepriateľa a dostupnosti munície. Výsledkom je, že komplexné správanie a čiastkové správanie môžu byť reprezentované s minimom duplicitných prechodov.
Strom správania
S HFSM sa jednoduchým spôsobom vytvárajú zložité kombinácie správania. Je tu však mierny problém, že rozhodovanie formou prechodných pravidiel úzko súvisí so súčasným stavom. A v mnohých hrách je to presne to, čo je potrebné. A starostlivé používanie štátnej hierarchie môže znížiť počet opakovaní prechodu. Niekedy však potrebujete pravidlá, ktoré fungujú bez ohľadu na to, v akom štáte sa nachádzate, alebo ktoré platia takmer v akomkoľvek štáte. Napríklad, ak zdravie agenta klesne na 25 %, budete chcieť, aby utiekol bez ohľadu na to, či bol v boji, nečinnosti alebo rozprával – túto podmienku budete musieť pridať ku každému stavu. A ak chce váš dizajnér neskôr zmeniť nízky zdravotný prah z 25 % na 10 %, bude to musieť urobiť znova.
V ideálnom prípade si táto situácia vyžaduje systém, v ktorom sú rozhodnutia o tom, „v akom stave sa nachádzať“ mimo samotných štátov, aby sa zmeny vykonali iba na jednom mieste a nedotýkali sa podmienok prechodu. Tu sa objavujú stromy správania.
Existuje niekoľko spôsobov, ako ich implementovať, ale podstata je pre všetkých približne rovnaká a je podobná rozhodovaciemu stromu: algoritmus začína „koreňovým“ uzlom a strom obsahuje uzly, ktoré predstavujú buď rozhodnutia alebo akcie. Existuje však niekoľko kľúčových rozdielov:
- Uzly teraz vracajú jednu z troch hodnôt: Úspešné (ak je úloha dokončená), Neúspešná (ak sa nedá spustiť) alebo Spustená (ak stále beží a neexistuje konečný výsledok).
- Neexistujú žiadne ďalšie rozhodovacie uzly na výber medzi dvoma alternatívami. Namiesto toho sú to uzly Decorator, ktoré majú jeden podriadený uzol. Ak uspejú, vykonajú svoj jediný podriadený uzol.
- Uzly, ktoré vykonávajú akcie, vracajú hodnotu Beh, ktorá predstavuje vykonávané akcie.
Túto malú množinu uzlov je možné skombinovať a vytvoriť tak veľké množstvo komplexných správaní. Predstavme si strážcu HFSM z predchádzajúceho príkladu ako strom správania:
S touto štruktúrou by nemal byť zrejmý prechod od stavu nečinnosti/hliadky do stavu útočenia alebo akéhokoľvek iného stavu. Ak je nepriateľ viditeľný a zdravie postavy je nízke, vykonávanie sa zastaví v uzle Útek, bez ohľadu na to, ktorý uzol predtým vykonával – hliadkovanie, nečinnosť, útok alebo akýkoľvek iný.
Stromy správania sú zložité – existuje mnoho spôsobov, ako ich skladať, a nájsť správnu kombináciu dekoratérov a zložených uzlov môže byť náročné. Objavujú sa aj otázky, ako často strom kontrolovať – chceme prejsť každú jeho časť alebo až keď sa zmení jedna z podmienok? Ako ukladáme stav týkajúci sa uzlov – ako vieme, kedy sme boli 10 sekúnd nečinní, alebo ako vieme, ktoré uzly boli spustené naposledy, aby sme mohli sekvenciu správne spracovať?
To je dôvod, prečo existuje veľa implementácií. Napríklad, niektoré systémy nahradili dekoračné uzly inline dekorátormi. Prehodnocujú strom, keď sa zmenia podmienky dekoratéra, pomáhajú spájať uzly a poskytujú pravidelné aktualizácie.
Systém založený na pomôckach
Niektoré hry majú veľa rôznych mechaník. Je žiaduce, aby získali všetky výhody jednoduchých a všeobecných pravidiel prechodu, ale nie nevyhnutne vo forme úplného stromu správania. Namiesto jasného súboru možností alebo stromu možných akcií je jednoduchšie preskúmať všetky akcie a vybrať si tú, ktorá je momentálne najvhodnejšia.
Systém založený na pomôckach vám s tým pomôže. Ide o systém, v ktorom má agent rôzne akcie a vyberá si, ktoré z nich vykoná, na základe relatívnej užitočnosti každej z nich. Kde užitočnosť je ľubovoľná miera toho, aké dôležité alebo žiaduce je, aby agent vykonal túto akciu.
Vypočítanú užitočnosť akcie na základe aktuálneho stavu a prostredia môže agent kedykoľvek skontrolovať a vybrať najvhodnejší iný stav. Je to podobné ako pri FSM, s výnimkou prípadov, keď sú prechody určené odhadom pre každý potenciálny stav, vrátane súčasného. Upozorňujeme, že vyberáme najužitočnejšiu akciu, aby sme sa posunuli ďalej (alebo zostali, ak sme ju už dokončili). Pre väčšiu rozmanitosť by to mohol byť vyvážený, ale náhodný výber z malého zoznamu.
Systém priraďuje ľubovoľný rozsah úžitkových hodnôt – napríklad od 0 (úplne nežiaduce) do 100 (úplne žiaduce). Každá akcia má množstvo parametrov, ktoré ovplyvňujú výpočet tejto hodnoty. Vráťme sa k nášmu príkladu opatrovníka:
Prechody medzi akciami sú nejednoznačné – každý stav môže nasledovať po ktoromkoľvek inom. Priority akcií sa nachádzajú vo vrátených úžitkových hodnotách. Ak je nepriateľ viditeľný a ten je silný a zdravie postavy je nízke, potom Útek aj FindingHelp vrátia vysoké nenulové hodnoty. V tomto prípade bude FindingHelp vždy vyššia. Rovnako aj nebojové aktivity nikdy nevrátia viac ako 50, takže budú vždy nižšie ako bojové. Musíte to vziať do úvahy pri vytváraní akcií a výpočte ich užitočnosti.
V našom príklade akcie vracajú buď pevnú konštantnú hodnotu alebo jednu z dvoch pevných hodnôt. Realistickejší systém by vrátil odhad zo súvislého rozsahu hodnôt. Napríklad akcia Útek vráti vyššie úžitkové hodnoty, ak je zdravie agenta nízke, a akcia Útok vráti nižšie úžitkové hodnoty, ak je nepriateľ príliš silný. Z tohto dôvodu má akcia Útek prednosť pred útokom v každej situácii, keď má agent pocit, že nemá dostatok zdravia, aby porazil nepriateľa. To umožňuje uprednostniť akcie na základe ľubovoľného počtu kritérií, vďaka čomu je tento prístup flexibilnejší a variabilnejší ako strom správania alebo FSM.
Každá akcia má veľa podmienok pre výpočet programu. Môžu byť napísané v skriptovacom jazyku alebo ako séria matematických vzorcov. The Sims, ktorý simuluje každodennú rutinu postavy, pridáva ďalšiu vrstvu výpočtov – agent dostáva sériu „motivácií“, ktoré ovplyvňujú hodnotenie užitočnosti. Ak je postava hladná, bude časom ešte hladnejšia a úžitková hodnota akcie EatFood sa bude zvyšovať, kým ju postava nevykoná, čím sa zníži úroveň hladu a hodnota EatFood sa vráti na nulu.
Myšlienka výberu akcií na základe hodnotiaceho systému je pomerne jednoduchá, takže systém založený na pomôckach možno použiť ako súčasť rozhodovacích procesov AI, a nie ako ich úplnú náhradu. Rozhodovací strom môže požiadať o hodnotenie užitočnosti dvoch dcérskych uzlov a vybrať ten vyšší. Podobne strom správania môže mať zložený uzol Utility na vyhodnotenie užitočnosti akcií pri rozhodovaní o tom, ktoré dieťa sa má vykonať.
Pohyb a navigácia
V predchádzajúcich príkladoch sme mali plošinu, ktorú sme posúvali doľava alebo doprava, a stráž, ktorá hliadkovala alebo útočila. Ale ako presne zvládame pohyb agentov počas určitého časového obdobia? Ako nastavíme rýchlosť, ako sa vyhýbame prekážkam a ako si naplánujeme trasu, keď dostať sa do cieľa je náročnejšie ako len pohyb v priamom smere? Pozrime sa na to.
management
V počiatočnej fáze budeme predpokladať, že každý agent má hodnotu rýchlosti, ktorá zahŕňa, ako rýchlo sa pohybuje a akým smerom. Dá sa merať v metroch za sekundu, kilometroch za hodinu, pixeloch za sekundu atď. Keď si spomenieme na slučku Sense/Think/Act, môžeme si predstaviť, že časť Think vyberá rýchlosť a časť Act aplikuje túto rýchlosť na agenta. Hry majú zvyčajne fyzikálny systém, ktorý túto úlohu vykonáva za vás, pričom sa učí hodnotu rýchlosti každého objektu a upravuje ju. Preto môžete nechať AI s jednou úlohou - rozhodnúť, akú rýchlosť by mal mať agent. Ak viete, kde by mal byť agent, musíte ho posunúť správnym smerom nastavenou rýchlosťou. Veľmi triviálna rovnica:
požadované_cestovanie = destination_position – agent_position
Predstavte si 2D svet. Agent je v bode (-2,-2), cieľ je niekde na severovýchode v bode (30, 20) a požadovaná cesta, aby sa tam agent dostal, je (32, 22). Povedzme, že tieto polohy sú merané v metroch - ak vezmeme rýchlosť agenta na 5 metrov za sekundu, potom zmeníme náš vektor posunutia a dostaneme rýchlosť približne (4.12, 2.83). S týmito parametrami by agent dorazil na miesto určenia za takmer 8 sekúnd.
Hodnoty môžete kedykoľvek prepočítať. Ak by bol agent v polovici cesty k cieľu, pohyb by bol polovičný, ale keďže maximálna rýchlosť agenta je 5 m/s (rozhodli sme sa vyššie), rýchlosť bude rovnaká. Funguje to aj pre pohyblivé ciele, čo umožňuje agentovi vykonávať malé zmeny počas pohybu.
Chceme však viac variácií – napríklad pomalé zvyšovanie rýchlosti na simuláciu pohybu postavy zo státia do behu. To isté možno urobiť na konci pred zastavením. Tieto funkcie sú známe ako správanie pri riadení, z ktorých každá má špecifické názvy: Seek, Flee, Arrival, atď. Myšlienkou je, že akceleračné sily môžu byť aplikované na rýchlosť agenta na základe porovnania pozície agenta a aktuálnej rýchlosti s cieľom v s cieľom použiť rôzne metódy pohybu k cieľu.
Každé správanie má trochu iný účel. Vyhľadávanie a príchod sú spôsoby, ako presunúť agenta do cieľa. Vyhýbanie sa prekážkam a Separácia upravujú pohyb agenta tak, aby sa vyhýbal prekážkam na ceste k cieľu. Zosúladenie a súdržnosť udržujú agentov v pohybe spoločne. Akýkoľvek počet rôznych správaní pri riadení môže byť sčítaný, aby sa vytvoril jeden vektor dráhy, berúc do úvahy všetky faktory. Agent, ktorý používa správanie Príchod, Oddelenie a Vyhýbanie sa prekážkam, aby sa držal ďalej od stien a iných agentov. Tento prístup funguje dobre na otvorených miestach bez zbytočných detailov.
V ťažších podmienkach už horšie funguje pridávanie rôznych spôsobov správania – agent sa napríklad môže zaseknúť v stene kvôli konfliktu medzi Arrival a Obstacle Avoidance. Preto musíte zvážiť možnosti, ktoré sú zložitejšie ako jednoduché sčítanie všetkých hodnôt. Spôsob je takýto: namiesto sčítania výsledkov každého správania môžete zvážiť pohyb rôznymi smermi a vybrať si najlepšiu možnosť.
V zložitom prostredí so slepými uličkami a voľbami, ktorým smerom sa vydať, však budeme potrebovať niečo ešte pokročilejšie.
Hľadanie cesty
Správanie sa pri riadení je skvelé pre jednoduchý pohyb na otvorenom priestranstve (futbalové ihrisko alebo aréna), kde je cesta z bodu A do bodu B rovná cesta len s malými obchádzkami okolo prekážok. Pre zložité trasy potrebujeme pathfinding, čo je spôsob, ako objavovať svet a rozhodovať sa pre cestu cez neho.
Najjednoduchšie je použiť mriežku na každé políčko vedľa agenta a vyhodnotiť, ktorý z nich sa môže pohybovať. Ak je jeden z nich cieľom, choďte po trase z každého štvorca k predchádzajúcemu, kým sa nedostanete na začiatok. Toto je trasa. V opačnom prípade opakujte postup s ďalšími políčkami v okolí, kým nenájdete svoj cieľ alebo kým sa vám neminú všetky políčka (to znamená, že neexistuje žiadna možná trasa). Toto je to, čo je formálne známe ako Breadth-First Search alebo BFS (breadth-first search algorithm). Na každom kroku sa pozerá na všetky strany (preto do šírky, „šírky“). Priestor hľadania je ako vlnoplocha, ktorá sa pohybuje, kým nedosiahne požadované miesto – priestor hľadania sa každým krokom zväčšuje, až kým nie je zahrnutý koncový bod, potom ho možno vysledovať späť na začiatok.
V dôsledku toho dostanete zoznam štvorcov, pozdĺž ktorých je zostavená požadovaná trasa. Toto je cesta (teda hľadanie cesty) – zoznam miest, ktoré agent navštívi počas sledovania cieľa.
Vzhľadom na to, že poznáme polohu každého štvorca na svete, môžeme použiť riadiace správanie na pohyb po ceste – z uzla 1 do uzla 2, potom z uzla 2 do uzla 3 atď. Najjednoduchšou možnosťou je vydať sa smerom k stredu nasledujúceho štvorca, ale ešte lepšou možnosťou je zastaviť sa v strede okraja medzi aktuálnym a nasledujúcim štvorcom. Z tohto dôvodu bude agent schopný rezať zákruty na ostrých zákrutách.
Algoritmus BFS má aj nevýhody – skúma toľko štvorcov v „nesprávnom“ smere ako v „správnom“ smere. Tu vstupuje do hry zložitejší algoritmus nazývaný A* (A star). Funguje to rovnako, ale namiesto toho, aby slepo skúmal susedné štvorce (potom susedia susedov, potom susedia susedov susedov atď.), zhromažďuje uzly do zoznamu a triedi ich tak, aby nasledujúci uzol bol vždy takú, ktorá vedie najkratšou cestou. Uzly sa triedia na základe heuristiky, ktorá berie do úvahy dve veci – „náklady“ na hypotetickú trasu k požadovanému štvorcu (vrátane akýchkoľvek cestovných nákladov) a odhad vzdialenosti tohto štvorca od cieľa (skreslenie vyhľadávania v správny smer).
Tento príklad ukazuje, že agent skúma po jednom štvorci, pričom zakaždým vyberie susedný štvorec, ktorý je najsľubnejší. Výsledná cesta je rovnaká ako BFS, ale v procese sa zvažovalo menej štvorcov – čo má veľký vplyv na výkon hry.
Pohyb bez mriežky
Väčšina hier však nie je usporiadaná na mriežke a často je to nemožné bez obetovania realizmu. Kompromisy sú potrebné. Akú veľkosť by mali mať štvorce? Príliš veľké a nebudú schopné správne reprezentovať malé chodby alebo odbočky, príliš malé a bude tam príliš veľa polí na hľadanie, čo v konečnom dôsledku zaberie veľa času.
Prvá vec, ktorú treba pochopiť, je, že sieť nám dáva graf pripojených uzlov. Algoritmy A* a BFS v skutočnosti pracujú na grafoch a vôbec sa nestarajú o našu sieť. Uzly by sme mohli umiestniť kdekoľvek v hernom svete: pokiaľ existuje spojenie medzi akýmikoľvek dvoma pripojenými uzlami, ako aj medzi počiatočným a koncovým bodom a aspoň jedným z uzlov, algoritmus bude fungovať rovnako dobre ako predtým. Toto sa často nazýva systém trasových bodov, pretože každý uzol predstavuje významnú pozíciu vo svete, ktorá môže byť súčasťou ľubovoľného počtu hypotetických ciest.
Príklad 1: uzol v každom štvorci. Vyhľadávanie začína od uzla, kde sa nachádza agent, a končí v uzle požadovaného štvorca.
Príklad 2: Menšia množina uzlov (trasových bodov). Vyhľadávanie začína na námestí agenta, prechádza cez požadovaný počet uzlov a potom pokračuje do cieľa.
Ide o úplne flexibilný a výkonný systém. Ale pri rozhodovaní o tom, kde a ako umiestniť trasový bod, je potrebná určitá opatrnosť, inak agenti jednoducho neuvidia najbližší bod a nebudú môcť začať cestu. Bolo by jednoduchšie, keby sme mohli automaticky umiestňovať trasové body na základe geometrie sveta.
Tu sa zobrazí navigačná sieť alebo navmesh (navigačná sieť). Zvyčajne ide o 2D sieť trojuholníkov, ktorá je prekrytá geometriou sveta - všade tam, kde je agentovi dovolené chodiť. Každý z trojuholníkov v sieti sa stane uzlom v grafe a má až tri susedné trojuholníky, ktoré sa stanú susednými uzlami v grafe.
Tento obrázok je príkladom z enginu Unity - analyzoval geometriu vo svete a vytvoril navmesh (na snímke svetlomodrej farby). Každý polygón v navmesh je oblasť, kde agent môže stáť alebo sa pohybovať z jedného polygónu do druhého. V tomto príklade sú polygóny menšie ako poschodia, na ktorých sa nachádzajú - to sa robí preto, aby sa zohľadnila veľkosť agenta, ktorý bude presahovať jeho nominálnu polohu.
Môžeme hľadať cestu cez túto sieť, opäť pomocou algoritmu A*. Na svete tak získame takmer dokonalú trasu, ktorá zohľadňuje všetku geometriu a nevyžaduje zbytočné uzly a vytváranie waypointov.
Pathfinding je príliš široká téma, na ktorú nestačí jedna sekcia článku. Ak to chcete študovať podrobnejšie, pomôže vám to .
plánovanie
Pri hľadaní cesty sme sa naučili, že niekedy nestačí len vybrať smer a pohnúť sa – musíme si vybrať trasu a urobiť niekoľko odbočiek, aby sme sa dostali do požadovaného cieľa. Túto myšlienku môžeme zovšeobecniť: dosiahnutie cieľa nie je len ďalší krok, ale celá sekvencia, v ktorej sa niekedy musíte pozrieť dopredu o niekoľko krokov, aby ste zistili, čo by malo byť prvé. Toto sa nazýva plánovanie. Pathfinding možno považovať za jedno z niekoľkých rozšírení plánovania. Pokiaľ ide o náš cyklus Zmysel/Mysli/Konaj, toto je miesto, kde časť Mysli plánuje viaceré časti Aktov do budúcnosti.
Pozrime sa na príklad stolovej hry Magic: The Gathering. Najprv ideme s nasledujúcou sadou kariet v rukách:
- Swamp – dáva 1 čiernu manu (karta krajiny).
- Forest – dáva 1 zelenú manu (karta krajiny).
- Fugitive Wizard - Vyžaduje 1 modrú manu na privolanie.
- Elvish Mystic - Vyžaduje 1 zelenú manu na privolanie.
Zvyšné tri karty ignorujeme, aby sme to uľahčili. Podľa pravidiel môže hráč zahrať 1 kartu krajiny za kolo, môže túto kartu „ťuknutím“ extrahovať z nej manu a potom čarovať (vrátane privolania bytosti) podľa množstva many. V tejto situácii ľudský hráč vie, že má hrať Forest, ťuknúť na 1 zelenú manu a potom privolať Elvish Mystic. Ale ako na to môže herná AI prísť?
Jednoduché plánovanie
Triviálnym prístupom je skúšať každú akciu v poradí, kým nezostanú žiadne vhodné. Pri pohľade na karty AI vidí, čo môže Swamp hrať. A hrá to. Zostávajú v tomto kole ešte nejaké ďalšie akcie? Nemôže vyvolať ani Elvish Mystic ani Fugitive Wizard, pretože na ich privolanie potrebujú zelenú a modrú manu, zatiaľ čo Swamp poskytuje iba čiernu manu. A už nebude môcť hrať Forest, pretože už hral Swamp. Umelá inteligencia hry teda dodržiavala pravidlá, no robila to zle. Dá sa zlepšiť.
Plánovanie môže nájsť zoznam akcií, ktoré privedú hru do požadovaného stavu. Tak ako mal každý štvorec na ceste susedov (pri hľadaní cesty), každá akcia v pláne má tiež susedov alebo následníkov. Tieto akcie a následné akcie môžeme hľadať, až kým nedosiahneme želaný stav.
V našom príklade je želaným výsledkom „privolajte stvorenie, ak je to možné“. Na začiatku kola vidíme iba dve možné akcie, ktoré pravidlá hry umožňujú:
1. Zahrajte si Swamp (výsledok: Swamp v hre)
2. Hrať Forest (výsledok: Forest v hre)
Každá vykonaná akcia môže viesť k ďalším akciám a uzavrieť ďalšie, opäť v závislosti od pravidiel hry. Predstavte si, že sme hrali Swamp - toto odstráni Swamp ako ďalší krok (už sme to hrali) a tým sa odstráni aj Forest (pretože podľa pravidiel môžete hrať jednu kartu krajiny za kolo). Potom AI pridá ako ďalší krok získanie 1 čiernej many, pretože neexistujú žiadne iné možnosti. Ak pôjde dopredu a zvolí Tap the Swamp, dostane 1 jednotku čiernej many a nebude s ňou môcť nič robiť.
1. Zahrajte si Swamp (výsledok: Swamp v hre)
1.1 „Tap“ Swamp (výsledok: Swamp „tapped“, +1 jednotka čiernej many)
Nie sú k dispozícii žiadne akcie – END
2. Hrať Forest (výsledok: Forest v hre)
Zoznam akcií bol krátky, dostali sme sa do slepej uličky. Postup opakujeme pre ďalší krok. Hráme Forest, otvoríme akciu „získaj 1 zelenú manu“, ktorá zase otvorí tretiu akciu – privolaj Elvish Mystic.
1. Zahrajte si Swamp (výsledok: Swamp v hre)
1.1 „Tap“ Swamp (výsledok: Swamp „tapped“, +1 jednotka čiernej many)
Nie sú k dispozícii žiadne akcie – END
2. Hrať Forest (výsledok: Forest v hre)
2.1 „Tap“ Forest (výsledok: Forest je „ťapnutý“, +1 jednotka zelenej many)
2.1.1 Vyvolajte Elvish Mystic (výsledok: Elvish Mystic v hre, -1 zelená mana)
Nie sú k dispozícii žiadne akcie – END
Nakoniec sme preskúmali všetky možné akcie a našli plán, ktorý privolá stvorenie.
Toto je veľmi zjednodušený príklad. Je vhodné zvoliť si najlepší možný plán, a nie len akýkoľvek plán, ktorý spĺňa určité kritériá. Vo všeobecnosti je možné vyhodnotiť potenciálne plány na základe výsledku alebo celkového prínosu ich implementácie. Môžete si pripísať 1 bod za zahranie karty krajiny a 3 body za privolanie bytosti. Hra Swamp by bol 1 bodový plán. A hranie Forest → Tap the Forest → privolanie Elvish Mystic okamžite dá 4 body.
Takto funguje plánovanie v Magic: The Gathering, no rovnaká logika platí aj v iných situáciách. Napríklad pohyb pešiaka, aby sa uvoľnil priestor pre strelca na pohyb v šachu. Alebo sa schovajte za stenu a bezpečne strieľajte v XCOM, ako je tento. Vo všeobecnosti máte nápad.
Vylepšené plánovanie
Niekedy existuje príliš veľa potenciálnych akcií na zváženie všetkých možných možností. Vráťme sa k príkladu s Magic: The Gathering: povedzme, že v hre a vo vašej ruke je niekoľko kariet krajín a bytostí – počet možných kombinácií ťahov môže byť v desiatkach. Existuje niekoľko riešení problému.
Prvým spôsobom je spätné reťazenie. Namiesto skúšania všetkých kombinácií je lepšie začať s konečným výsledkom a pokúsiť sa nájsť priamu cestu. Namiesto toho, aby sme prešli od koreňa stromu ku konkrétnemu listu, postupujeme opačným smerom – od listu ku koreňu. Táto metóda je jednoduchšia a rýchlejšia.
Ak má nepriateľ 1 zdravie, môžete nájsť plán „deal 1 or more damage“. Aby ste to dosiahli, musíte splniť niekoľko podmienok:
1. Poškodenie môže spôsobiť kúzlo - musí byť v ruke.
2. Na zoslanie kúzla potrebujete manu.
3. Ak chcete získať manu, musíte zahrať kartu krajiny.
4. Ak chcete zahrať kartu krajiny, musíte ju mať v ruke.
Ďalším spôsobom je vyhľadávanie najskôr. Namiesto skúšania všetkých ciest si vyberáme to najvhodnejšie. Najčastejšie táto metóda poskytuje optimálny plán bez zbytočných nákladov na vyhľadávanie. A* je forma najlepšieho prvého hľadania – tým, že od začiatku preskúma najsľubnejšie cesty, už dokáže nájsť najlepšiu cestu bez toho, aby musel kontrolovať ďalšie možnosti.
Zaujímavou a čoraz populárnejšou možnosťou vyhľadávania na prvom mieste je Monte Carlo Tree Search. Namiesto hádania, ktoré plány sú lepšie ako ostatné pri výbere každej nasledujúcej akcie, algoritmus vyberá náhodných nástupcov v každom kroku až do konca (keď plán skončil víťazstvom alebo porážkou). Konečný výsledok sa potom použije na zvýšenie alebo zníženie hmotnosti predchádzajúcich možností. Opakovaním tohto procesu niekoľkokrát za sebou algoritmus poskytuje dobrý odhad toho, aký je najlepší ďalší ťah, aj keď sa situácia zmení (ak nepriateľ podnikne kroky na zasahovanie do hráča).
Žiadny príbeh o plánovaní v hrách by nebol úplný bez akčného plánovania zameraného na cieľ alebo GOAP (plánovanie akcií orientovaných na cieľ). Toto je široko používaná a diskutovaná metóda, ale okrem niekoľkých rozlišujúcich detailov je to v podstate metóda spätného reťazenia, o ktorej sme hovorili skôr. Ak bolo cieľom „zničiť hráča“ a hráč je za krytom, plán by mohol byť: zničiť granátom → získať ho → hodiť ho.
Zvyčajne existuje niekoľko cieľov, z ktorých každý má svoju prioritu. Ak nemožno splniť cieľ s najvyššou prioritou (žiadna kombinácia akcií nevytvorí plán „zabiť hráča“, pretože hráč nie je viditeľný), AI sa vráti k cieľom s nižšou prioritou.
Školenie a adaptácia
Už sme povedali, že herná AI zvyčajne nepoužíva strojové učenie, pretože nie je vhodné na správu agentov v reálnom čase. To však neznamená, že si z tejto oblasti nemôžete niečo požičať. Chceme súpera v strelcovi, od ktorého sa môžeme niečo naučiť. Zistite si napríklad najlepšie pozície na mape. Alebo súper v bojovej hre, ktorý by hráčovi blokoval často používané kombinované pohyby, čím by ho motivoval používať iné. Takže strojové učenie môže byť v takýchto situáciách celkom užitočné.
Štatistika a pravdepodobnosti
Skôr než sa pustíme do zložitých príkladov, pozrime sa, ako ďaleko môžeme zájsť vykonaním niekoľkých jednoduchých meraní a ich použitím pri rozhodovaní. Napríklad stratégia v reálnom čase – ako zistíme, či hráč dokáže zaútočiť v prvých minútach hry a akú obranu si proti tomu pripraviť? Môžeme študovať minulé skúsenosti hráča, aby sme pochopili, aké môžu byť budúce reakcie. Na začiatok nemáme také nespracované údaje, ale môžeme ich zbierať – zakaždým, keď AI hrá proti človeku, dokáže zaznamenať čas prvého útoku. Po niekoľkých sedeniach dostaneme priemer času, ktorý bude hráčovi v budúcnosti trvať, kým zaútočí.
Problém je aj s priemernými hodnotami: ak sa hráč 20-krát ponáhľal a 20-krát hral pomaly, požadované hodnoty budú niekde v strede a to nám neprinesie nič užitočné. Jedným z riešení je obmedzenie vstupných údajov – do úvahy sa môže brať posledných 20 kusov.
Podobný prístup sa používa pri odhadovaní pravdepodobnosti určitých akcií za predpokladu, že minulé preferencie hráča budú rovnaké aj v budúcnosti. Ak na nás hráč zaútočí päťkrát ohnivou guľou, dvakrát bleskom a raz zblízka, je zrejmé, že preferuje ohnivú guľu. Poďme extrapolovať a uvidíme pravdepodobnosť použitia rôznych zbraní: ohnivá guľa=62,5%, blesk=25% a boj na blízko=12,5%. Naša herná AI sa musí pripraviť na ochranu pred ohňom.
Ďalšou zaujímavou metódou je použitie klasifikátora Naive Bayes na štúdium veľkého množstva vstupných údajov a klasifikáciu situácie tak, aby AI reagovala požadovaným spôsobom. Bayesovské klasifikátory sú najznámejšie pre ich použitie v e-mailových spamových filtroch. Tam skúmajú slová, porovnávajú ich s tým, kde sa tieto slová vyskytli predtým (v spame alebo nie) a vyvodzujú závery o prichádzajúcich e-mailoch. To isté môžeme urobiť aj s menším počtom vstupov. Na základe všetkých užitočných informácií, ktoré AI vidí (napríklad aké nepriateľské jednotky sú vytvorené alebo aké kúzla používajú alebo aké technológie skúmali) a konečný výsledok (vojna alebo mier, zhon alebo obrana atď.) - zvolíme požadované správanie AI.
Všetky tieto tréningové metódy sú dostatočné, ale je vhodné ich použiť na základe testovacích údajov. Umelá inteligencia sa naučí prispôsobiť sa rôznym stratégiám, ktoré používali vaši hráči. Umelá inteligencia, ktorá sa po vydaní prispôsobí hráčovi, sa môže stať príliš predvídateľnou alebo príliš ťažko poraziteľnou.
Prispôsobenie založené na hodnote
Vzhľadom na obsah nášho herného sveta a pravidlá môžeme zmeniť množinu hodnôt, ktoré ovplyvňujú rozhodovanie, a nie len používať vstupné údaje. Robíme toto:
- Nechajte AI zbierať údaje o stave sveta a kľúčových udalostiach počas hry (ako je uvedené vyššie).
- Na základe týchto údajov zmeňme niekoľko dôležitých hodnôt.
- Naše rozhodnutia realizujeme na základe spracovania alebo vyhodnotenia týchto hodnôt.
Napríklad agent má na výber niekoľko miestností na mape strieľačiek z pohľadu prvej osoby. Každá izba má svoju hodnotu, ktorá určuje, nakoľko je žiaduce ju navštíviť. AI na základe hodnoty náhodne vyberie, do ktorej miestnosti pôjde. Agent si potom zapamätá, v ktorej miestnosti bol zabitý a zníži jej hodnotu (pravdepodobnosť, že sa tam vráti). Podobne pre opačnú situáciu - ak agent zničí veľa protivníkov, potom sa hodnota miestnosti zvýši.
Markov model
Čo keby sme zozbierané údaje použili na predpovede? Ak si zapamätáme každú miestnosť, v ktorej hráča vidíme na určitý čas, predpovedáme, do ktorej miestnosti môže hráč ísť. Sledovaním a zaznamenávaním pohybov hráča v miestnostiach (hodnotách) ich môžeme predpovedať.
Zoberme si tri miestnosti: červenú, zelenú a modrú. A tiež postrehy, ktoré sme zaznamenali počas sledovania hry:
Počet pozorovaní v každej miestnosti je takmer rovnaký - stále nevieme, kde urobiť dobré miesto na prepadnutie. Zbieranie štatistík komplikuje aj respawnovanie hráčov, ktorí sa objavujú rovnomerne po celej mape. Užitočné sú ale už údaje o ďalšej miestnosti, do ktorej vstúpia po zobrazení na mape.
Je vidieť, že zelená miestnosť hráčom vyhovuje – z červenej sa do nej presúva najviac ľudí, 50% z nich tam ostáva ďalej. Modrá izba naopak nie je populárna, takmer nikto do nej nechodí, a ak áno, nezostane dlho.
Údaje nám však hovoria niečo dôležitejšie – keď je hráč v modrej miestnosti, ďalšia miestnosť, v ktorej ho uvidíme, bude červená, nie zelená. Aj keď je zelená miestnosť obľúbenejšia ako červená, situácia sa zmení, ak je hráč v modrej miestnosti. Ďalší stav (t. j. miestnosť, do ktorej hráč pôjde) závisí od predchádzajúceho stavu (t. j. miestnosti, v ktorej sa hráč práve nachádza). Pretože skúmame závislosti, budeme robiť presnejšie predpovede, ako keby sme jednoducho počítali pozorovania nezávisle.
Predpovedanie budúceho stavu na základe údajov z minulého stavu sa nazýva Markovov model a takéto príklady (s miestnosťami) sa nazývajú Markovove reťazce. Pretože vzory predstavujú pravdepodobnosť zmien medzi po sebe nasledujúcimi stavmi, sú vizuálne zobrazené ako FSM s pravdepodobnosťou okolo každého prechodu. Predtým sme používali FSM na vyjadrenie behaviorálneho stavu, v ktorom sa agent nachádzal, ale tento koncept sa vzťahuje na akýkoľvek stav, či už je spojený s agentom alebo nie. V tomto prípade štáty predstavujú miestnosť, ktorú agent zaberá:
Toto je jednoduchý spôsob vyjadrenia relatívnej pravdepodobnosti zmien stavu, čo dáva AI určitú schopnosť predpovedať ďalší stav. Môžete predvídať niekoľko krokov dopredu.
Ak je hráč v zelenej miestnosti, je 50% šanca, že tam zostane, keď bude nabudúce pozorovaný. Aké sú však šance, že tam bude aj potom? Nielenže existuje šanca, že hráč zostal po dvoch pozorovaniach v zelenej miestnosti, ale je tu aj šanca, že odišiel a vrátil sa. Tu je nová tabuľka zohľadňujúca nové údaje:
Ukazuje, že šanca vidieť hráča v zelenej miestnosti po dvoch pozorovaniach sa bude rovnať 51% - 21%, že bude z červenej miestnosti, 5% z nich, že hráč navštívi modrú miestnosť medzi nimi a 25%, ktoré hráč neopustí, opustí zelenú miestnosť.
Tabuľka je jednoducho vizuálna pomôcka – postup vyžaduje iba vynásobenie pravdepodobnosti v každom kroku. To znamená, že sa môžete pozrieť do ďalekej budúcnosti s jedným upozornením: predpokladáme, že šanca vstúpiť do miestnosti úplne závisí od aktuálnej miestnosti. Hovorí sa tomu Markov Property – budúci stav závisí len od súčasnosti. Ale to nie je stopercentne presné. Hráči môžu meniť rozhodnutia v závislosti od iných faktorov: úroveň zdravia alebo množstvo munície. Keďže tieto hodnoty nezaznamenávame, naše predpovede budú menej presné.
N-gramov
A čo príklad bojovej hry a predpovedania kombo ťahov hráča? Rovnaký! Ale namiesto jedného stavu alebo udalosti budeme skúmať celé sekvencie, ktoré tvoria combo strike.
Jedným zo spôsobov, ako to urobiť, je uložiť každý vstup (napríklad Kick, Punch alebo Block) do vyrovnávacej pamäte a zapísať celú vyrovnávaciu pamäť ako udalosť. Takže hráč opakovane stláča Kick, Kick, Punch, aby použil útok SuperDeathFist, AI systém ukladá všetky vstupy do vyrovnávacej pamäte a pamätá si posledné tri použité v každom kroku.
(Tučné čiary sú, keď hráč spustí útok SuperDeathFist.)
AI uvidí všetky možnosti, keď hráč vyberie Kick, po ktorom nasleduje ďalší Kick, a potom si všimne, že ďalší vstup je vždy Punch. To umožní agentovi predpovedať kombinovaný pohyb SuperDeathFist a zablokovať ho, ak je to možné.
Tieto postupnosti udalostí sa nazývajú N-gramy, kde N je počet uložených prvkov. V predchádzajúcom príklade to bol 3-gram (trigram), čo znamená: prvé dva záznamy sa používajú na predpovedanie tretieho. Podľa toho v 5-grame prvé štyri položky predpovedajú piaty a tak ďalej.
Dizajnér musí starostlivo zvoliť veľkosť N-gramov. Menšie N vyžaduje menej pamäte, ale ukladá aj menej histórie. Napríklad 2-gramový (bigram) zaznamená Kick, Kick alebo Kick, Punch, ale nebude môcť uložiť Kick, Kick, Punch, takže AI nebude reagovať na kombináciu SuperDeathFist.
Na druhej strane, väčšie čísla vyžadujú viac pamäte a AI bude ťažšie trénovať, pretože bude oveľa viac možností. Ak by ste mali tri možné vstupy Kick, Punch alebo Block a použili by sme 10-gram, bolo by to asi 60 tisíc rôznych možností.
Model bigramu je jednoduchý Markovov reťazec – každý pár minulý stav/aktuálny stav je bigram a na základe prvého môžete predpovedať druhý stav. 3-gramové a väčšie N-gramy si môžeme predstaviť aj ako Markovove reťazce, kde všetky prvky (okrem posledného v N-grame) spolu tvoria prvý stav a posledný prvok druhý. Príklad bojovej hry ukazuje možnosť prechodu zo stavu Kick and Kick do stavu Kick and Punch. Spracovaním viacerých vstupných záznamov histórie ako jednej jednotky v podstate transformujeme vstupnú sekvenciu na časť celého stavu. To nám dáva Markovovu vlastnosť, ktorá nám umožňuje použiť Markovove reťazce na predpovedanie ďalšieho vstupu a hádanie, aký bude ďalší kombinovaný ťah.
Záver
Hovorili sme o najbežnejších nástrojoch a prístupoch vo vývoji umelej inteligencie. Pozreli sme sa aj na situácie, v ktorých ich treba použiť a kde sú obzvlášť užitočné.
To by malo stačiť na pochopenie základov hernej AI. Ale, samozrejme, to nie sú všetky metódy. Medzi menej populárne, ale nemenej účinné patria:
- optimalizačné algoritmy vrátane lezenia do kopca, klesania v gradiente a genetických algoritmov
- protistranné vyhľadávacie/plánovacie algoritmy (minimax a alfa-beta prerezávanie)
- klasifikačné metódy (perceptróny, neurónové siete a podporné vektorové stroje)
- systémy na vnímanie a pamäť spracovateľov
- architektonické prístupy k AI (hybridné systémy, architektúry podmnožín a iné spôsoby prekrývania systémov AI)
- animačné nástroje (plánovanie a koordinácia pohybu)
- výkonnostné faktory (úroveň detailov, kedykoľvek a algoritmy časového krájania)
Online zdroje na túto tému:
1. GameDev.net má a .
2. obsahuje množstvo prezentácií a článkov na širokú škálu tém súvisiacich s vývojom AI hier.
3. obsahuje témy zo samitu GDC AI, z ktorých mnohé sú dostupné zadarmo.
4. Užitočné materiály nájdete aj na webovej stránke .
5. Tommy Thompson, výskumník AI a vývojár hier, robí videá na YouTube s vysvetlením a štúdiom AI v komerčných hrách.
Knihy na túto tému:
1. Séria kníh Game AI Pro je zbierkou krátkych článkov, ktoré vysvetľujú, ako implementovať špecifické funkcie alebo ako riešiť konkrétne problémy.
2. Séria AI Game Programming Wisdom je predchodcom série Game AI Pro. Obsahuje staršie metódy, no takmer všetky sú aktuálne aj dnes.
3. je jedným zo základných textov pre každého, kto chce porozumieť všeobecnej oblasti umelej inteligencie. Toto nie je kniha o vývoji hier – učí základy AI.
Zdroj: hab.com