Narazil jsem na zajímavý materiál o umělé inteligenci ve hrách. S vysvětlením základních věcí o AI na jednoduchých příkladech a uvnitř je mnoho užitečných nástrojů a metod pro její pohodlný vývoj a návrh. Jak, kde a kdy je použít, je tam také.
Většina příkladů je napsána v pseudokódu, takže nejsou potřeba žádné pokročilé znalosti programování. Pod řezem je 35 listů textu s obrázky a gify, tak se připravte.
UPD. Omlouvám se, ale tento článek o Habrém jsem již přeložil sám . Jeho verzi si můžete přečíst , ale z nějakého důvodu mě článek minul (použil jsem vyhledávání, ale něco se pokazilo). A protože píšu na blog věnovaný vývoji her, rozhodl jsem se svou verzi překladu nechat pro předplatitele (některé body jsou naformátovány jinak, některé byly na radu vývojářů záměrně vynechány).
Co je AI?
Herní umělá inteligence se zaměřuje na to, jaké akce by měl objekt provádět na základě podmínek, ve kterých se nachází. To se běžně označuje jako správa „inteligentního agenta“, kde agentem je hráčská postava, vozidlo, bot nebo někdy něco abstraktnějšího: celá skupina entit nebo dokonce civilizace. V každém případě jde o věc, která musí vidět své prostředí, rozhodovat se na jeho základě a jednat v souladu s ním. Tomu se říká cyklus Smysl/Mysli/Jednej:
- Smysl: Agent nachází nebo přijímá informace o věcech ve svém prostředí, které mohou ovlivnit jeho chování (hrozby v okolí, předměty ke sběru, zajímavá místa k prozkoumání).
- Přemýšlejte: Agent se rozhodne, jak zareaguje (zváží, zda je dostatečně bezpečné sbírat předměty, nebo zda by měl nejprve bojovat/skrýt se).
- Akt: agent provede akce k provedení předchozího rozhodnutí (začne se pohybovat směrem k nepříteli nebo objektu).
- ...nyní se situace vlivem jednání postav změnila, takže cyklus se opakuje s novými daty.
AI má tendenci se soustředit na část smyčky Sense. Autonomní auta například pořizují snímky silnice, kombinují je s radarovými a lidarovými daty a interpretují je. To se obvykle provádí strojovým učením, které zpracovává příchozí data a dává jim význam, získává sémantické informace jako „20 yardů před vámi je další auto“. Jedná se o tzv. klasifikační problémy.
Hry nepotřebují složitý systém k získávání informací, protože většina dat je již jejich nedílnou součástí. Není třeba spouštět algoritmy pro rozpoznávání obrazu, abyste zjistili, zda je před námi nepřítel – hra již zná a dodává informace přímo do rozhodovacího procesu. Část cyklu Sense je proto často mnohem jednodušší než část Mysli a jednej.
Omezení herní umělé inteligence
AI má řadu omezení, která je třeba dodržovat:
- AI není třeba trénovat předem, jako by to byl algoritmus strojového učení. Nemá smysl psát neuronovou síť během vývoje, aby sledovala desítky tisíc hráčů a naučila se, jak nejlépe proti nim hrát. Proč? Protože hra nevyšla a nejsou tam žádní hráči.
- Hra by měla být zábavná a náročná, takže agenti by neměli najít ten nejlepší přístup proti lidem.
- Agenti musí vypadat realisticky, aby měli hráči pocit, že hrají proti skutečným lidem. Program AlphaGo předčil lidi, ale zvolené kroky byly velmi vzdálené tradičnímu chápání hry. Pokud hra simuluje lidského protivníka, tento pocit by neměl existovat. Algoritmus je třeba změnit tak, aby dělal přijatelná rozhodnutí spíše než ideální.
- AI musí fungovat v reálném čase. To znamená, že algoritmus nemůže monopolizovat využití CPU po dlouhou dobu k rozhodování. I 10 milisekund je příliš dlouhá doba, protože většina her potřebuje pouze 16 až 33 milisekund k provedení veškerého zpracování a přechodu na další grafický snímek.
- V ideálním případě by alespoň část systému měla být řízena daty, aby nekódující uživatelé mohli provádět změny a úpravy rychleji.
Podívejme se na přístupy umělé inteligence, které pokrývají celý cyklus Smysl/Přemýšlej/Jednej.
Činění základních rozhodnutí
Začněme tou nejjednodušší hrou - Pong. Cíl: posuňte pádlo tak, aby se míček od něj odrážel, místo aby kolem něj proletěl. Je to jako tenis, kde prohrajete, když netrefíte míček. Zde má AI poměrně snadný úkol – rozhodnout, kterým směrem platformu přesunout.
Podmíněné výroky
Pro AI in Pong je nejzřejmějším řešením vždy se pokusit umístit platformu pod míč.
Jednoduchý algoritmus pro to, napsaný v pseudokódu:
každý snímek/aktualizace, když hra běží:
pokud je míč nalevo od pádla:
posuňte pádlo doleva
jinak, pokud je míč napravo od pádla:
posuňte pádlo doprava
Pokud se platforma pohybuje rychlostí míče, pak je to ideální algoritmus pro AI v Pong. Není třeba nic komplikovat, pokud není tolik dat a možných akcí pro agenta.
Tento přístup je tak jednoduchý, že celý cyklus Smysl/Přemýšlení/Jednání je sotva patrný. Ale je tam:
- Část Sense je ve dvou příkazech if. Hra ví, kde je míč a kde je platforma, takže AI hledá tyto informace.
- Část Think je také zahrnuta ve dvou příkazech if. Ztělesňují dvě řešení, která se v tomto případě vzájemně vylučují. V důsledku toho je vybrána jedna ze tří akcí - posuňte plošinu doleva, posuňte ji doprava nebo nedělejte nic, pokud je již správně umístěna.
- Část Act se nachází v příkazech Move Paddle Left a Move Paddle Right. V závislosti na herním designu mohou platformu pohybovat okamžitě nebo určitou rychlostí.
Takové přístupy se nazývají reaktivní – existuje jednoduchá sada pravidel (v tomto případě příkazů v kódu), která reagují na aktuální stav světa a zasahují.
Rozhodovací strom
Příklad Pong je ve skutečnosti ekvivalentní formálnímu konceptu AI zvanému rozhodovací strom. Algoritmus tím prochází, aby dosáhl „listu“ – rozhodnutí o tom, jakou akci podnikne.
Udělejme blokové schéma rozhodovacího stromu pro algoritmus naší platformy:
Každá část stromu se nazývá uzel – AI k popisu takových struktur používá teorii grafů. Existují dva typy uzlů:
- Rozhodovací uzly: volba mezi dvěma alternativami na základě testování nějaké podmínky, kde každá alternativa je reprezentována jako samostatný uzel.
- Koncové uzly: Akce, která se má provést a která představuje konečné rozhodnutí.
Algoritmus začíná od prvního uzlu („kořen“ stromu). Buď se rozhodne, ke kterému podřízenému uzlu přejít, nebo provede akci uloženou v uzlu a ukončí se.
Jaká je výhoda toho, že rozhodovací strom vykonává stejnou práci jako příkazy if v předchozí části? Existuje zde obecný systém, kde každé rozhodnutí má pouze jednu podmínku a dva možné výsledky. To vývojářům umožňuje vytvářet AI z dat představujících rozhodnutí ve stromu, aniž by je musel napevno kódovat. Pojďme si to představit ve formě tabulky:
Na straně kódu získáte systém pro čtení řetězců. Vytvořte uzel pro každý z nich, propojte rozhodovací logiku na základě druhého sloupce a podřízené uzly na základě třetího a čtvrtého sloupce. Stále musíte naprogramovat podmínky a akce, ale nyní bude struktura hry složitější. Zde přidáte další rozhodnutí a akce a poté přizpůsobíte celou AI jednoduchou úpravou textového souboru s definicí stromu. Poté přenesete soubor hernímu návrháři, který může změnit chování bez překompilování hry nebo změny kódu.
Rozhodovací stromy jsou velmi užitečné, když jsou sestavovány automaticky z velké sady příkladů (například pomocí algoritmu ID3). To z nich dělá efektivní a vysoce výkonný nástroj pro klasifikaci situací na základě získaných dat. My však jdeme za rámec jednoduchého systému pro výběr akcí agentů.
Scénáře
Analyzovali jsme systém rozhodovacího stromu, který používal předem vytvořené podmínky a akce. Osoba, která navrhuje AI, si může uspořádat strom, jak chce, ale stále se musí spolehnout na kodéra, který to všechno naprogramoval. Co kdybychom mohli dát designérovi nástroje k vytváření vlastních podmínek nebo akcí?
Aby programátor nemusel psát kód pro podmínky Is Ball Left Of Paddle a Is Ball Right Of Paddle, může si vytvořit systém, ve kterém bude konstruktér zapisovat podmínky pro kontrolu těchto hodnot. Potom budou data rozhodovacího stromu vypadat takto:
To je v podstatě stejné jako v první tabulce, ale řešení v sobě mají svůj vlastní kód, trochu jako podmíněná část příkazu if. Na straně kódu by to bylo ve druhém sloupci pro rozhodovací uzly, ale místo hledání konkrétní podmínky k provedení (Is Ball Left Of Paddle) vyhodnotí podmíněný výraz a podle toho vrátí hodnotu true nebo false. To se provádí pomocí skriptovacího jazyka Lua nebo Angelscript. Pomocí nich může vývojář vzít objekty ve své hře (míč a pádlo) a vytvořit proměnné, které budou dostupné ve skriptu (ball.position). Skriptovací jazyk je také jednodušší než C++. Nevyžaduje úplnou fázi kompilace, takže je ideální pro rychlé přizpůsobení herní logiky a umožňuje „nekodérům“ vytvářet potřebné funkce sami.
Ve výše uvedeném příkladu je skriptovací jazyk použit pouze k vyhodnocení podmíněného výrazu, ale lze jej použít i pro akce. Například data Move Paddle Right by se mohla stát příkazem skriptu (ball.position.x += 10). Aby byla akce definována i ve skriptu, bez nutnosti programování Move Paddle Right.
Můžete jít ještě dále a napsat celý rozhodovací strom ve skriptovacím jazyce. Bude se jednat o kód ve formě pevně zakódovaných podmíněných příkazů, které však budou umístěny v externích souborech skriptů, to znamená, že je lze změnit bez překompilování celého programu. Během hraní můžete často upravovat soubor skriptu a rychle otestovat různé reakce umělé inteligence.
Odezva na událost
Výše uvedené příklady jsou pro Pong perfektní. Neustále provádějí cyklus Smysl/Mysli/Jednej a jednají na základě nejnovějšího stavu světa. Ve složitějších hrách je ale potřeba reagovat na jednotlivé události, a ne vše vyhodnocovat najednou. Pong je v tomto případě již špatný příklad. Vyberme si jiný.
Představte si střílečku, ve které jsou nepřátelé nehybní, dokud hráče neodhalí, poté jednají v závislosti na své „specializaci“: někdo poběží „spěchat“, někdo zaútočí z dálky. Stále se jedná o základní reaktivní systém – „pokud je hráč spatřen, něco udělejte“ – ale lze jej logicky rozdělit na událost Player Seen a Reaction (vyberte odpověď a spusťte ji).
To nás přivádí zpět do cyklu Smysl/Mysli/Jednej. Můžeme nakódovat část Sense, která zkontroluje každý snímek, zda AI vidí hráče. Pokud ne, nic se nestane, ale pokud uvidí, vytvoří se událost Player Seen. Kód bude mít samostatnou sekci, která říká „když dojde k události Player Seen, udělej“, kde je odpověď, kterou potřebujete k řešení částí Think and Act. Nastavíte tak reakce na událost Player Seen: pro „spěchající“ postavu – ChargeAndAttack a pro snipera – HideAndSnipe. Tyto vztahy lze vytvořit v datovém souboru pro rychlé úpravy bez nutnosti překompilování. I zde lze použít skriptovací jazyk.
Dělat obtížná rozhodnutí
Přestože jsou jednoduché reakční systémy velmi výkonné, existuje mnoho situací, kdy nestačí. Někdy je potřeba činit různá rozhodnutí podle toho, co agent právě dělá, ale je těžké si to představit jako podmínku. Někdy je podmínek příliš mnoho na to, aby je bylo možné efektivně reprezentovat v rozhodovacím stromu nebo skriptu. Někdy je potřeba předem posoudit, jak se situace změní, než se rozhodnete pro další postup. K řešení těchto problémů jsou zapotřebí sofistikovanější přístupy.
Konečný automat
Konečný automat neboli FSM (finite state machine) je způsob, jak říci, že náš agent je aktuálně v jednom z několika možných stavů a že může přecházet z jednoho stavu do druhého. Existuje určitý počet takových stavů - odtud název. Nejlepším příkladem ze života je semafor. Na různých místech jsou různé sekvence světel, ale princip je stejný – každý stav něco představuje (zastav se, jdi atd.). Semafor je v každém okamžiku pouze v jednom stavu a pohybuje se z jednoho do druhého na základě jednoduchých pravidel.
Je to podobný příběh s NPC ve hrách. Vezměme si například stráž s následujícími stavy:
- Hlídkování.
- Útočící.
- Na útěku.
A tyto podmínky pro změnu jeho stavu:
- Pokud strážný uvidí nepřítele, zaútočí.
- Pokud strážný zaútočí, ale nepřítele již nevidí, vrátí se na hlídku.
- Pokud strážce zaútočí, ale je těžce zraněn, uteče.
Můžete také psát if-příkazy s proměnnou stavu strážce a různými kontrolami: je poblíž nepřítel, jaká je úroveň zdraví NPC atd. Přidejme ještě pár stavů:
- Nečinnost - mezi hlídkami.
- Hledání - když zpozorovaný nepřítel zmizel.
- Hledání pomoci – když je zpozorován nepřítel, ale je příliš silný na to, aby bojoval sám.
Výběr pro každého z nich je omezený - například strážce nepůjde hledat skrytého nepřítele, pokud má nízké zdraví.
Koneckonců, existuje obrovský seznam „kdyby“ , Že “ se může stát příliš těžkopádným, takže musíme formalizovat metodu, která nám umožní mít na paměti stavy a přechody mezi stavy. K tomu bereme v úvahu všechny stavy a pod každý stav zapisujeme do seznamu všechny přechody do jiných stavů spolu s podmínkami pro ně nezbytnými.
Toto je tabulka přechodu stavu - komplexní způsob reprezentace FSM. Pojďme si nakreslit diagram a získat kompletní přehled o tom, jak se mění chování NPC.
Diagram odráží podstatu rozhodování tohoto agenta na základě aktuální situace. Navíc každá šipka ukazuje přechod mezi stavy, pokud je podmínka vedle ní pravdivá.
Při každé aktualizaci zkontrolujeme aktuální stav agenta, prohlédneme si seznam přechodů a pokud jsou splněny podmínky přechodu, přijme nový stav. Každý snímek například zkontroluje, zda nevypršel 10sekundový časovač, a pokud ano, strážný přejde ze stavu nečinnosti do stavu hlídání. Stejně tak stav Útočící kontroluje zdraví agenta – pokud je nízké, pak přechází do stavu Útěk.
Jedná se o manipulaci s přechody mezi stavy, ale co chování spojené se samotnými stavy? Pokud jde o implementaci skutečného chování pro konkrétní stav, obvykle existují dva typy „háku“, kde přiřazujeme akce FSM:
- Akce, které pravidelně provádíme pro aktuální stav.
- Akce, které provádíme při přechodu z jednoho stavu do druhého.
Příklady pro první typ. Stav hlídkování přesune agenta po trase hlídky v každém snímku. Stav Útok se pokusí zahájit útok na každý snímek nebo přechod do stavu, kdy je to možné.
U druhého typu zvažte přechod „pokud je nepřítel viditelný a nepřítel je příliš silný, přejděte do stavu Finding Help. Agent si musí vybrat, kam se obrátit pro pomoc, a uložit tyto informace, aby stav Finding Help věděl, kam se obrátit. Jakmile je nalezena pomoc, agent se vrátí do stavu Útočení. V tuto chvíli bude chtít o hrozbě říci spojenci, takže může dojít k akci NotifyFriendOfThreat.
Opět se na tento systém můžeme podívat optikou cyklu Sense/Think/Act. Smysl je ztělesněn v datech používaných logikou přechodu. Think - přechody dostupné v každém stavu. A Act se provádí akcemi prováděnými periodicky v rámci státu nebo při přechodech mezi státy.
Někdy mohou být podmínky přechodu neustálého dotazování nákladné. Pokud například každý agent provádí složité výpočty v každém snímku, aby zjistil, zda vidí nepřátele a zda dokáže přejít ze stavu hlídkování do stavu útočení, zabere to spoustu času CPU.
Důležité změny ve stavu světa lze považovat za události, které budou zpracovávány tak, jak k nim dojde. Místo toho, aby FSM kontroloval přechodovou podmínku „vidí můj agent hráče?“ každý snímek, lze samostatný systém nakonfigurovat tak, aby kontroloval méně často (např. 5krát za sekundu). A výsledkem je vydání Player Seen, když kontrola projde.
To je předáno FSM, které by nyní mělo přejít na podmínku přijetí události Player Seen a odpovídajícím způsobem reagovat. Výsledné chování je stejné až na téměř neznatelné zpoždění před reakcí. Ale výkon se zlepšil v důsledku oddělení části Sense do samostatné části programu.
Hierarchický konečný automat
Práce s velkými FSM však není vždy pohodlná. Pokud chceme rozšířit stav útoku na oddělení MeleeAttacking a RangedAttacking, budeme muset změnit přechody ze všech ostatních stavů, které vedou ke stavu Attacking (aktuální a budoucí).
Pravděpodobně jste si všimli, že v našem příkladu je mnoho duplicitních přechodů. Většina přechodů ve stavu nečinnosti je shodná s přechody ve stavu hlídání. Bylo by fajn se neopakovat, zvlášť když přidáme více podobných stavů. Má smysl seskupovat Idling a Parolling pod obecnou nálepku „nebojové“, kde existuje pouze jedna společná sada přechodů do bojových stavů. Pokud si toto označení představíme jako stav, pak se Idling a Patrolling stanou podstavy. Příklad použití samostatné přechodové tabulky pro nový nebojový podstát:
Hlavní státy:
Stav mimo boj:
A ve formě diagramu:
Je to stejný systém, ale s novým nebojovým stavem, který zahrnuje Idling a Patrolling. S každým stavem obsahujícím FSM s dílčími stavy (a tyto dílčí stavy zase obsahující své vlastní FSM - a tak dále, jak dlouho budete potřebovat), dostaneme Hierarchický konečný stavový stroj neboli HFSM (hierarchický konečný stavový stroj). Seskupením nebojového stavu jsme odstranili spoustu nadbytečných přechodů. Totéž můžeme udělat pro všechny nové stavy se společnými přechody. Pokud například v budoucnu rozšíříme stav Útok na stavy Útok zblízka a Útok raketou, budou to podstáty, které mezi sebou přecházejí na základě vzdálenosti k nepříteli a dostupnosti munice. Výsledkem je, že komplexní chování a dílčí chování lze reprezentovat s minimem duplicitních přechodů.
Strom chování
S HFSM se jednoduchým způsobem vytvářejí složité kombinace chování. Mírný problém však spočívá v tom, že rozhodování formou přechodových pravidel úzce souvisí se současným stavem. A v mnoha hrách je to přesně to, co je potřeba. A pečlivé používání hierarchie stavů může snížit počet opakování přechodu. Někdy ale potřebujete pravidla, která fungují bez ohledu na to, v jakém stavu se nacházíte, nebo která platí téměř v jakémkoli státě. Pokud například zdraví agenta klesne na 25 %, budete chtít, aby utekl bez ohledu na to, zda byl v boji, nečinnosti nebo mluvil – tuto podmínku budete muset přidat ke každému stavu. A pokud bude chtít váš návrhář později změnit práh nízkého zdraví z 25 % na 10 %, bude to muset být provedeno znovu.
V ideálním případě tato situace vyžaduje systém, ve kterém jsou rozhodnutí o tom, „v jakém stavu se nacházet“, mimo státy samotné, aby se změny prováděly pouze na jednom místě a nedotýkaly se přechodových podmínek. Zde se objevují stromy chování.
Existuje několik způsobů, jak je implementovat, ale podstata je pro všechny zhruba stejná a je podobná rozhodovacímu stromu: algoritmus začíná „kořenovým“ uzlem a strom obsahuje uzly, které představují buď rozhodnutí, nebo akce. Existuje však několik klíčových rozdílů:
- Uzly nyní vracejí jednu ze tří hodnot: Úspěšná (pokud je úloha dokončena), Neúspěšná (pokud ji nelze spustit) nebo Spuštěná (pokud stále běží a neexistuje žádný konečný výsledek).
- Neexistují žádné další rozhodovací uzly, které by si mohly vybrat mezi dvěma alternativami. Místo toho jsou to uzly Decorator, které mají jeden podřízený uzel. Pokud uspějí, spustí svůj jediný podřízený uzel.
- Uzly, které provádějí akce, vracejí hodnotu Spuštění, která představuje prováděné akce.
Tato malá sada uzlů může být kombinována za účelem vytvoření velkého množství komplexních chování. Představme si strážce HFSM z předchozího příkladu jako strom chování:
S touto strukturou by neměl být žádný zřejmý přechod ze stavu nečinnosti/hlídkování do stavu útočícího nebo jakéhokoli jiného stavu. Pokud je nepřítel viditelný a zdraví postavy je nízké, provádění se zastaví v uzlu Útěk, bez ohledu na to, který uzel předtím prováděl – Hlídka, Volno, Útok nebo jakýkoli jiný.
Stromy chování jsou složité – existuje mnoho způsobů, jak je skládat, a nalezení správné kombinace dekorátorů a složených uzlů může být náročné. Objevují se i otázky, jak často strom kontrolovat – chceme projít každou jeho část nebo až když se změní jedna z podmínek? Jak uložíme stav týkající se uzlů – jak poznáme, že jsme byli 10 sekund nečinní, nebo jak poznáme, které uzly byly naposledy spuštěny, abychom mohli sekvenci správně zpracovat?
To je důvod, proč existuje mnoho implementací. Některé systémy například nahradily dekorační uzly za vložené dekorátory. Přehodnocují strom, když se změní podmínky dekoratérů, pomáhají spojovat uzly a poskytují pravidelné aktualizace.
Obslužný systém
Některé hry mají mnoho různých mechanik. Je žádoucí, aby získali všechny výhody jednoduchých a obecných pravidel přechodu, ale ne nutně ve formě úplného stromu chování. Namísto jasného souboru možností nebo stromu možných akcí je snazší prozkoumat všechny akce a vybrat si v danou chvíli tu nejvhodnější.
Systém založený na nástroji pomůže právě s tím. Jedná se o systém, kde agent má různé akce a vybírá si, které z nich provede, na základě relativní užitečnosti každé z nich. Kde užitečnost je libovolné měřítko toho, jak důležité nebo žádoucí je, aby agent provedl tuto akci.
Vypočtenou užitečnost akce na základě aktuálního stavu a prostředí může agent kdykoli zkontrolovat a vybrat nejvhodnější jiný stav. To je podobné jako u FSM, kromě případů, kdy jsou přechody určeny odhadem pro každý potenciální stav, včetně toho současného. Vezměte prosím na vědomí, že vybíráme nejužitečnější akci, kterou postoupíme (nebo zůstaneme, pokud jsme ji již dokončili). Pro větší rozmanitost by to mohl být vyvážený, ale náhodný výběr z malého seznamu.
Systém přiděluje libovolný rozsah užitných hodnot – například od 0 (zcela nežádoucí) do 100 (zcela žádoucí). Každá akce má řadu parametrů, které ovlivňují výpočet této hodnoty. Vraťme se k našemu příkladu opatrovníka:
Přechody mezi akcemi jsou nejednoznačné – každý stav může následovat po jakémkoli jiném. Priority akcí se nacházejí ve vrácených hodnotách užitku. Pokud je nepřítel viditelný a tento nepřítel je silný a zdraví postavy je nízké, pak Útěk i FindingHelp vrátí vysoké nenulové hodnoty. V tomto případě bude FindingHelp vždy vyšší. Stejně tak nebojové aktivity nikdy nevrátí více než 50, takže budou vždy nižší než bojové. Musíte to vzít v úvahu při vytváření akcí a výpočtu jejich užitečnosti.
V našem příkladu akce vrací buď pevnou konstantní hodnotu, nebo jednu ze dvou pevných hodnot. Realističtější systém by vrátil odhad ze souvislého rozsahu hodnot. Například akce Útěk vrátí vyšší užitné hodnoty, pokud je zdraví agenta nízké, a akce Útok vrátí nižší užitné hodnoty, pokud je nepřítel příliš silný. Z tohoto důvodu má akce Útěk přednost před útokem v každé situaci, kdy má agent pocit, že nemá dostatek zdraví, aby porazil nepřítele. To umožňuje upřednostňovat akce na základě libovolného počtu kritérií, díky čemuž je tento přístup flexibilnější a variabilnější než strom chování nebo FSM.
Každá akce má mnoho podmínek pro výpočet programu. Mohou být napsány ve skriptovacím jazyce nebo jako série matematických vzorců. The Sims, který simuluje každodenní rutinu postavy, přidává další vrstvu výpočtů – agent dostává řadu „motivací“, které ovlivňují hodnocení užitečnosti. Pokud má postava hlad, bude časem ještě hladovější a užitná hodnota akce EatFood se bude zvyšovat, dokud ji postava neprovede, sníží úroveň hladu a vrátí hodnotu EatFood na nulu.
Myšlenka výběru akcí na základě systému hodnocení je poměrně jednoduchá, takže systém založený na nástroji lze použít jako součást rozhodovacích procesů AI, spíše než jako jejich úplnou náhradu. Rozhodovací strom může požádat o hodnocení užitečnosti dvou podřízených uzlů a vybrat ten vyšší. Podobně může mít strom chování složený uzel Utility pro vyhodnocení užitečnosti akcí při rozhodování o tom, který potomek se má provést.
Pohyb a navigace
V předchozích příkladech jsme měli plošinu, kterou jsme pohybovali doleva nebo doprava, a stráž, která hlídkovala nebo útočila. Ale jak přesně zacházíme s pohybem agentů po určitou dobu? Jak nastavíme rychlost, jak se vyhýbáme překážkám a jak naplánujeme trasu, když je cesta do cíle obtížnější než jen pohyb po přímce? Podívejme se na to.
Управление
V počáteční fázi budeme předpokládat, že každý agent má hodnotu rychlosti, která zahrnuje, jak rychle se pohybuje a jakým směrem. Lze ji měřit v metrech za sekundu, kilometrech za hodinu, pixelech za sekundu atd. Když si vzpomeneme na smyčku Sense/Think/Act, můžeme si představit, že část Think vybírá rychlost a část Act aplikuje tuto rychlost na agenta. Hry mají obvykle fyzikální systém, který tento úkol provede za vás, naučí se hodnotu rychlosti každého objektu a upraví ji. Proto můžete nechat AI s jedním úkolem - rozhodnout, jakou rychlost by měl agent mít. Pokud víte, kde by měl být agent, musíte ho posunout správným směrem nastavenou rychlostí. Velmi triviální rovnice:
požadované_cestování = destination_position – pozice agenta
Představte si 2D svět. Agent je v bodě (-2,-2), cíl je někde na severovýchodě v bodě (30, 20) a požadovaná cesta, aby se tam agent dostal, je (32, 22). Řekněme, že tyto pozice jsou měřeny v metrech – pokud vezmeme rychlost agenta na 5 metrů za sekundu, pak zmenšíme náš vektor posunutí a dostaneme rychlost přibližně (4.12, 2.83). S těmito parametry by agent dorazil na místo určení za téměř 8 sekund.
Hodnoty můžete kdykoli přepočítat. Pokud by byl agent v polovině cesty k cíli, pohyb by byl poloviční délky, ale protože maximální rychlost agenta je 5 m/s (rozhodli jsme se výše), rychlost bude stejná. To funguje také pro pohyblivé cíle, což agentovi umožňuje provádět během pohybu malé změny.
Chceme ale více variací – například pomalé zvyšování rychlosti, abychom simulovali pohyb postavy ze stoje do běhu. Totéž lze provést na konci před zastavením. Tyto funkce jsou známé jako chování řízení, z nichž každé má specifické názvy: Seek, Flee, Arrival atd. Myšlenka je taková, že zrychlovací síly lze aplikovat na rychlost agenta na základě porovnání pozice agenta a aktuální rychlosti s cílem v za účelem použití různých metod pohybu k cíli.
Každé chování má trochu jiný účel. Seek a Arrival jsou způsoby, jak přesunout agenta do cíle. Vyhýbání se překážkám a Separace upravují pohyb agenta tak, aby se vyhýbal překážkám na cestě k cíli. Zarovnání a soudržnost udržují agenty v pohybu společně. Jakýkoli počet různých chování řízení lze sečíst a vytvořit jediný vektor dráhy, který bere v úvahu všechny faktory. Agent, který používá chování Arrival, Separation a Obstacle Avoidance, aby se držel dál od zdí a jiných agentů. Tento přístup funguje dobře na otevřených místech bez zbytečných detailů.
V těžších podmínkách funguje přidávání různých chování hůře – agent se například může zaseknout ve zdi kvůli konfliktu mezi Arrival a Obstacle Avoidance. Proto je třeba zvážit možnosti, které jsou složitější než pouhé sčítání všech hodnot. Způsob je takový: místo sčítání výsledků každého chování můžete zvážit pohyb v různých směrech a vybrat nejlepší možnost.
Ve složitém prostředí se slepými uličkami a volbami, kterou cestou se vydat, však budeme potřebovat něco ještě pokročilejšího.
Hledání cesty
Chování řízení je skvělé pro jednoduchý pohyb na otevřeném prostranství (fotbalové hřiště nebo aréna), kde se z bodu A do bodu B dostanete po přímé cestě s pouze malými objížďkami kolem překážek. U složitých tras potřebujeme pathfinding, což je způsob, jak prozkoumávat svět a rozhodnout se pro cestu přes něj.
Nejjednodušší je použít mřížku na každé políčko vedle agenta a vyhodnotit, kdo z nich se může pohybovat. Pokud je jeden z nich cílem, postupujte po trase z každého čtverce k předchozímu, dokud nedojdete na začátek. Toto je trasa. V opačném případě opakujte proces s okolními dalšími čtverci, dokud nenajdete svůj cíl nebo dokud vám nedojdou políčka (to znamená, že neexistuje žádná možná trasa). To je to, co je formálně známé jako Breadth-First Search nebo BFS (breadth-first search algorithm). Na každém kroku se rozhlíží na všechny strany (proto do šířky, „šířky“). Vyhledávací prostor je jako vlnoplocha, která se pohybuje, dokud nedosáhne požadovaného místa – vyhledávací prostor se každým krokem rozšiřuje, dokud není zahrnut koncový bod, poté jej lze vysledovat zpět na začátek.
V důsledku toho obdržíte seznam čtverců, podél kterých se sestavuje požadovaná trasa. Toto je cesta (proto pathfinding) – seznam míst, která agent navštíví, když bude sledovat cíl.
Vzhledem k tomu, že známe polohu každého čtverce na světě, můžeme použít chování řízení k pohybu po cestě – z uzlu 1 do uzlu 2, poté z uzlu 2 do uzlu 3 atd. Nejjednodušší možností je zamířit ke středu dalšího čtverce, ale ještě lepší možností je zastavit se uprostřed okraje mezi aktuálním a dalším čtvercem. Díky tomu bude agent schopen řezat zatáčky v ostrých zatáčkách.
Algoritmus BFS má také nevýhody – zkoumá tolik čtverců ve „špatném“ směru jako ve „správném“ směru. Zde vstupuje do hry složitější algoritmus zvaný A* (A hvězda). Funguje to stejně, ale místo slepého zkoumání sousedních čtverců (pak sousedů sousedů, pak sousedů sousedů sousedů atd.), shromažďuje uzly do seznamu a třídí je tak, aby další zkoumaný uzel byl vždy která vede nejkratší cestou. Uzly se třídí na základě heuristiky, která bere v úvahu dvě věci – „náklady“ na hypotetickou trasu k požadovanému čtverci (včetně případných cestovních nákladů) a odhad, jak daleko je tento čtverec od cíle (zkreslení vyhledávání v správný směr).
Tento příklad ukazuje, že agent prozkoumává jeden čtverec po druhém a pokaždé vybere sousední, které je nejslibnější. Výsledná cesta je stejná jako u BFS, ale v procesu bylo uvažováno méně čtverců – což má velký vliv na výkon hry.
Pohyb bez mřížky
Většina her ale není rozmístěna na mřížce a často je to nemožné bez obětování realismu. Kompromisy jsou potřeba. Jakou velikost mají mít čtverce? Příliš velké a nebudou schopny správně reprezentovat malé chodby nebo odbočky, příliš malé a bude příliš mnoho polí na hledání, což v konečném důsledku zabere spoustu času.
První věc, kterou je třeba pochopit, je, že síť nám poskytuje graf připojených uzlů. Algoritmy A* a BFS ve skutečnosti pracují na grafech a vůbec se nestarají o naši síť. Uzly bychom mohli umístit kamkoli v herním světě: pokud existuje spojení mezi libovolnými dvěma připojenými uzly, stejně jako mezi počátečním a koncovým bodem a alespoň jedním z uzlů, bude algoritmus fungovat stejně dobře jako dříve. To se často nazývá systém navigačních bodů, protože každý uzel představuje významnou pozici na světě, která může být součástí libovolného počtu hypotetických cest.
Příklad 1: uzel v každém čtverci. Hledání začíná od uzlu, kde se nachází agent, a končí v uzlu požadovaného čtverce.
Příklad 2: Menší sada uzlů (traťových bodů). Hledání začíná na čtverci agenta, prochází požadovaným počtem uzlů a poté pokračuje k cíli.
Jedná se o zcela flexibilní a výkonný systém. Ale při rozhodování, kam a jak umístit navigační bod, je potřeba jistá opatrnost, jinak agenti jednoduše neuvidí nejbližší bod a nebudou schopni zahájit cestu. Bylo by jednodušší, kdybychom mohli automaticky umisťovat trasové body na základě geometrie světa.
Zde se objeví navigační síť nebo navmesh (navigační síť). Obvykle se jedná o 2D síť trojúhelníků, která je překryta geometrií světa - ať už agent může chodit. Každý z trojúhelníků v síti se stane uzlem v grafu a má až tři sousední trojúhelníky, které se stanou sousedními uzly v grafu.
Tento obrázek je příkladem z Unity enginu - analyzoval geometrii ve světě a vytvořil navmesh (na snímku obrazovky ve světle modré barvě). Každý polygon v navmesh je oblast, kde agent může stát nebo se pohybovat z jednoho polygonu do druhého. V tomto příkladu jsou polygony menší než podlahy, na kterých jsou umístěny - to je provedeno proto, aby byla zohledněna velikost agenta, který bude přesahovat jeho nominální polohu.
Můžeme hledat cestu skrz tuto síť, opět pomocí algoritmu A*. Na světě tak získáme téměř dokonalou trasu, která zohledňuje veškerou geometrii a nevyžaduje zbytečné uzly a vytváření průjezdních bodů.
Pathfinding je příliš široké téma, na které nestačí jedna sekce článku. Pokud si to chcete prostudovat podrobněji, pomůže vám toto .
Plánování
Při hledání cesty jsme se naučili, že někdy nestačí jen vybrat směr a pohybovat se – musíme si vybrat trasu a udělat pár odboček, abychom se dostali do požadovaného cíle. Tuto myšlenku můžeme zobecnit: dosažení cíle není jen dalším krokem, ale celou sekvencí, kdy se někdy musíte podívat dopředu o několik kroků, abyste zjistili, co by měl být první. Tomu se říká plánování. Pathfinding lze považovat za jedno z několika rozšíření plánování. Pokud jde o náš cyklus Sense/Think/Act, zde část Think plánuje několik částí Act pro budoucnost.
Podívejme se na příklad deskové hry Magic: The Gathering. Nejprve jdeme s následující sadou karet v rukou:
- Swamp – Dává 1 černou manu (karta země).
- Forest – dává 1 zelenou manu (karta země).
- Fugitive Wizard - Vyžaduje 1 modrou manu k vyvolání.
- Elvish Mystic - Vyžaduje 1 zelenou manu k vyvolání.
Zbývající tři karty ignorujeme, aby to bylo jednodušší. Podle pravidel smí hráč za tah zahrát 1 kartu země, může na tuto kartu „klepnout“ a extrahovat z ní manu a poté kouzlit (včetně přivolání bytosti) podle množství many. V této situaci lidský hráč ví, že má hrát Forest, tapnout 1 zelenou manu a poté přivolat Elvish Mystic. Ale jak na to může herní AI přijít?
Snadné plánování
Triviální přístup je zkoušet postupně každou akci, dokud nezůstane žádná vhodná. Při pohledu na karty AI vidí, co může Swamp hrát. A hraje to. Zbývají v tomto kole ještě nějaké další akce? Nemůže vyvolat ani Elvish Mystic nebo Fugitive Wizard, protože k jejich vyvolání potřebují zelenou a modrou manu, zatímco Swamp poskytuje pouze černou manu. A už nebude moci hrát Forest, protože už hrál Swamp. Umělá inteligence hry tedy dodržovala pravidla, ale dělala to špatně. Dá se zlepšit.
Plánování může najít seznam akcí, které přivedou hru do požadovaného stavu. Stejně jako každé pole na cestě mělo sousedy (při hledání cesty), každá akce v plánu má také sousedy nebo následníky. Tyto akce a následné akce můžeme hledat, dokud nedosáhneme požadovaného stavu.
V našem příkladu je požadovaným výsledkem „vyvolat stvoření, pokud je to možné“. Na začátku tahu vidíme pouze dvě možné akce povolené pravidly hry:
1. Zahrajte si Swamp (výsledek: Swamp ve hře)
2. Zahrajte si Forest (výsledek: Forest ve hře)
Každá provedená akce může vést k dalším akcím a uzavřít další, opět v závislosti na pravidlech hry. Představte si, že jsme hráli Swamp - tím se odstraní Swamp jako další krok (už jsme to hráli) a tím se odstraní i Forest (protože podle pravidel můžete zahrát jednu kartu země za kolo). Poté AI přidá jako další krok získání 1 černé many, protože neexistují žádné další možnosti. Pokud půjde dopředu a zvolí Tap the Swamp, obdrží 1 jednotku černé many a nebude s ní moci nic dělat.
1. Zahrajte si Swamp (výsledek: Swamp ve hře)
1.1 „Tap“ Swamp (výsledek: Swamp „tapped“, +1 jednotka černé many)
Nejsou k dispozici žádné akce – END
2. Zahrajte si Forest (výsledek: Forest ve hře)
Výčet akcí byl krátký, dostali jsme se do slepé uličky. Postup opakujeme pro další krok. Hrajeme Forest, otevřeme akci „získej 1 zelenou manu“, která zase otevře třetí akci – vyvolání Elvish Mystic.
1. Zahrajte si Swamp (výsledek: Swamp ve hře)
1.1 „Tap“ Swamp (výsledek: Swamp „tapped“, +1 jednotka černé many)
Nejsou k dispozici žádné akce – END
2. Zahrajte si Forest (výsledek: Forest ve hře)
2.1 „Tap“ Forest (výsledek: Forest je „tapnutý“, +1 jednotka zelené many)
2.1.1 Vyvolání Elvish Mystic (výsledek: Elvish Mystic ve hře, -1 zelená mana)
Nejsou k dispozici žádné akce – END
Nakonec jsme prozkoumali všechny možné akce a našli plán, který stvoření vyvolá.
Toto je velmi zjednodušený příklad. Je vhodné zvolit nejlepší možný plán, spíše než jakýkoli plán, který splňuje některá kritéria. Obecně je možné vyhodnotit potenciální plány na základě výsledku nebo celkového přínosu jejich realizace. Můžete si připsat 1 bod za zahrání karty země a 3 body za vyvolání bytosti. Hrát Swamp by byl 1 bodový plán. A hraní Forest → Tap the Forest → vyvolání Elvish Mystic okamžitě dá 4 body.
Takhle funguje plánování v Magic: The Gathering, ale stejná logika platí i v jiných situacích. Například pohyb pěšce, aby se uvolnil prostor pro střelce, aby se mohl pohybovat v šachu. Nebo se skryjte za zdí a bezpečně střílejte v XCOM, jako je tento. Obecně získáte představu.
Vylepšené plánování
Někdy existuje příliš mnoho potenciálních akcí, než aby bylo možné zvážit všechny možné možnosti. Vraťme se k příkladu s Magic: The Gathering: řekněme, že ve hře a ve vaší ruce je několik karet zemí a bytostí – počet možných kombinací tahů může být v desítkách. Existuje několik řešení problému.
První metodou je zpětné řetězení. Místo zkoušení všech kombinací je lepší začít s konečným výsledkem a pokusit se najít přímou cestu. Místo toho, abychom šli od kořene stromu ke konkrétnímu listu, postupujeme opačným směrem – od listu ke kořenu. Tato metoda je jednodušší a rychlejší.
Pokud má nepřítel 1 zdraví, můžete najít plán „udělte 1 nebo více poškození“. Aby toho bylo dosaženo, musí být splněno několik podmínek:
1. Poškození může způsobit kouzlo - musí být v ruce.
2. K seslání kouzla potřebujete manu.
3. Abyste získali manu, musíte zahrát kartu země.
4. Chcete-li zahrát kartu země, musíte ji mít v ruce.
Dalším způsobem je nejlepší-první vyhledávání. Místo abychom vyzkoušeli všechny cesty, vybereme tu nejvhodnější. Nejčastěji tato metoda poskytuje optimální plán bez zbytečných nákladů na hledání. A* je forma best first search – tím, že od začátku prozkoumá ty nejslibnější cesty, už dokáže najít tu nejlepší cestu, aniž by musel kontrolovat další možnosti.
Zajímavou a stále populárnější možností vyhledávání na prvním místě je Monte Carlo Tree Search. Namísto hádání, které plány jsou lepší než ostatní při výběru každé následující akce, algoritmus vybírá náhodné následníky v každém kroku, dokud nedosáhne konce (když plán skončil vítězstvím nebo porážkou). Konečný výsledek se pak použije ke zvýšení nebo snížení váhy předchozích možností. Opakováním tohoto procesu několikrát za sebou poskytuje algoritmus dobrý odhad toho, jaký je nejlepší další tah, i když se situace změní (pokud nepřítel zasáhne, aby hráče rušil).
Žádný příběh o plánování ve hrách by nebyl úplný bez Goal-Oriented Action Planning nebo GOAP (goal-oriented action planning). Toto je široce používaná a diskutovaná metoda, ale kromě několika rozlišujících detailů je to v podstatě metoda zpětného řetězení, o které jsme hovořili dříve. Pokud bylo cílem „zničit hráče“ a hráč je za krytem, plán by mohl být: zničit granátem → získat ho → hodit.
Obvykle existuje několik cílů, z nichž každý má svou vlastní prioritu. Pokud nelze splnit cíl s nejvyšší prioritou (žádná kombinace akcí nevytváří plán „zabij hráče“, protože hráč není viditelný), AI se vrátí k cílům s nižší prioritou.
Školení a adaptace
Už jsme si řekli, že herní AI obvykle nepoužívá strojové učení, protože není vhodné pro správu agentů v reálném čase. To ale neznamená, že si z této oblasti nemůžete něco půjčit. Chceme soupeře ve střelci, od kterého se můžeme něco naučit. Zjistěte si například nejlepší pozice na mapě. Nebo soupeř v bojové hře, který by blokoval hráčovy často používané kombo pohyby a motivoval ho k používání jiných. Takže strojové učení může být v takových situacích docela užitečné.
Statistiky a pravděpodobnosti
Než se pustíme do složitých příkladů, podívejme se, jak daleko můžeme zajít, když provedeme několik jednoduchých měření a použijeme je k rozhodování. Například strategie v reálném čase – jak zjistíme, zda hráč může zahájit útok v prvních minutách hry a jakou obranu si proti tomu připravit? Můžeme studovat minulé zkušenosti hráče, abychom pochopili, jaké mohou být budoucí reakce. Pro začátek taková nezpracovaná data nemáme, ale můžeme je sbírat – pokaždé, když AI hraje proti člověku, dokáže zaznamenat čas prvního útoku. Po několika sezeních získáme průměr času, který bude hráči v budoucnu trvat, než zaútočí.
Problém je také s průměrnými hodnotami: pokud hráč spěchal 20krát a hrál pomalu 20krát, požadované hodnoty budou někde uprostřed, a to nám nepřinese nic užitečného. Jedním z řešení je omezení vstupních dat – lze vzít v úvahu posledních 20 kusů.
Podobný přístup se používá při odhadování pravděpodobnosti určitých akcí za předpokladu, že minulé preference hráče budou v budoucnu stejné. Pokud na nás hráč zaútočí pětkrát ohnivou koulí, dvakrát bleskem a jednou zblízka, je zřejmé, že preferuje ohnivou kouli. Pojďme extrapolovat a uvidíme pravděpodobnost použití různých zbraní: ohnivá koule=62,5 %, blesk=25 % a boj zblízka=12,5 %. Naše herní umělá inteligence se musí připravit, aby se ochránila před ohněm.
Další zajímavou metodou je použití Naive Bayes Classifier ke studiu velkého množství vstupních dat a klasifikaci situace tak, aby AI reagovala požadovaným způsobem. Bayesovské klasifikátory jsou nejlépe známé pro své použití v e-mailových spamových filtrech. Tam slova zkoumají, porovnávají je s tím, kde se tato slova objevila dříve (ve spamu nebo ne) a vyvozují závěry o příchozích e-mailech. Totéž můžeme udělat i s menším počtem vstupů. Na základě všech užitečných informací, které AI vidí (například jaké nepřátelské jednotky jsou vytvořeny nebo jaká kouzla používají nebo jaké technologie zkoumali), a konečný výsledek (válka nebo mír, spěch nebo obrana atd.) - zvolíme požadované chování AI.
Všechny tyto tréninkové metody jsou dostatečné, ale je vhodné je používat na základě testovacích dat. Umělá inteligence se naučí přizpůsobovat různým strategiím, které vaši hráči používají. Umělá inteligence, která se po vydání přizpůsobí hráči, se může stát příliš předvídatelnou nebo příliš těžko porazitelnou.
Přizpůsobení na základě hodnoty
Vzhledem k obsahu našeho herního světa a pravidlům můžeme změnit sadu hodnot, které ovlivňují rozhodování, spíše než jen používat vstupní data. Děláme toto:
- Nechte AI sbírat data o stavu světa a klíčových událostech během hry (jak je uvedeno výše).
- Pojďme změnit několik důležitých hodnot na základě těchto dat.
- Na základě zpracování nebo vyhodnocení těchto hodnot realizujeme svá rozhodnutí.
Například agent má na výběr z několika místností na mapě stříleček z pohledu první osoby. Každý pokoj má svou hodnotu, která určuje, jak žádoucí je ho navštívit. Umělá inteligence náhodně vybere, do které místnosti půjde na základě hodnoty. Agent si pak zapamatuje, ve které místnosti byl zabit a sníží její hodnotu (pravděpodobnost, že se tam vrátí). Podobně pro obrácenou situaci – pokud agent zničí mnoho protivníků, pak se hodnota místnosti zvyšuje.
Markovův model
Co kdybychom shromážděná data použili k předpovědím? Pokud si pamatujeme každou místnost, ve které hráče vidíme, po určitou dobu, předpovíme, do které místnosti by hráč mohl jít. Sledováním a zaznamenáváním pohybů hráče napříč místnostmi (hodnotami) je můžeme předvídat.
Vezměme si tři místnosti: červenou, zelenou a modrou. A také postřehy, které jsme zaznamenali při sledování hry:
Počet pozorování v každé místnosti je téměř stejný - stále nevíme, kde udělat dobré místo pro přepadení. Sbírání statistik komplikuje i respawnování hráčů, kteří se objevují rovnoměrně po celé mapě. Už se ale hodí údaje o další místnosti, do které vstupují poté, co se objeví na mapě.
Je vidět, že zelená místnost hráčům vyhovuje - z červené místnosti se do ní přesune nejvíce lidí, z nichž 50 % tam zůstává dále. Modrý pokoj naopak není oblíbený, skoro nikdo do něj nechodí, a pokud ano, nezůstane tam dlouho.
Data nám ale říkají něco důležitějšího – když je hráč v modré místnosti, další místnost, ve které ho uvidíme, bude červená, nikoli zelená. I když je zelená místnost oblíbenější než červená, situace se změní, pokud je hráč v modré místnosti. Další stav (tj. místnost, do které hráč půjde) závisí na předchozím stavu (tj. místnosti, ve které se hráč právě nachází). Protože zkoumáme závislosti, budeme dělat přesnější předpovědi, než kdybychom jednoduše počítali pozorování nezávisle.
Předpovídání budoucího stavu na základě dat z minulého stavu se nazývá Markovův model a takové příklady (s místnostmi) se nazývají Markovovy řetězce. Protože vzory představují pravděpodobnost změn mezi po sobě jdoucími stavy, jsou vizuálně zobrazeny jako FSM s pravděpodobností kolem každého přechodu. Dříve jsme používali FSM k reprezentaci behaviorálního stavu, ve kterém se agent nacházel, ale tento koncept se vztahuje na jakýkoli stav, ať už je s agentem spojen nebo ne. V tomto případě stavy představují místnost, kterou agent obývá:
Toto je jednoduchý způsob, jak znázornit relativní pravděpodobnost změn stavu, což dává AI určitou schopnost předvídat další stav. Můžete předvídat několik kroků dopředu.
Pokud je hráč v zelené místnosti, je 50% šance, že tam zůstane, až bude příště pozorován. Jaká je ale šance, že tam bude i poté? Nejen, že existuje šance, že hráč po dvou pozorováních zůstal v zelené místnosti, ale je také šance, že odešel a vrátil se. Zde je nová tabulka zohledňující nová data:
Ukazuje, že šance vidět hráče v zelené místnosti po dvou pozorováních se bude rovnat 51% - 21%, že bude z červené místnosti, 5% z nich, že hráč navštíví modrou místnost mezi nimi, a 25%, které hráč neopustí, opustí zelenou místnost.
Tabulka je jednoduše vizuální nástroj – postup vyžaduje pouze násobení pravděpodobností v každém kroku. To znamená, že se můžete podívat daleko do budoucnosti s jednou výhradou: předpokládáme, že šance na vstup do místnosti zcela závisí na aktuální místnosti. Říká se tomu Markov Property - budoucí stav závisí pouze na současnosti. To ale není stoprocentně přesné. Hráči mohou měnit rozhodnutí v závislosti na dalších faktorech: úrovni zdraví nebo množství munice. Protože tyto hodnoty nezaznamenáváme, naše předpovědi budou méně přesné.
N-gramů
A co příklad bojové hry a předpovídání kombo tahů hráče? Stejný! Ale místo jednoho stavu nebo události budeme zkoumat celé sekvence, které tvoří combo strike.
Jedním ze způsobů, jak toho dosáhnout, je uložit každý vstup (jako Kick, Punch nebo Block) do vyrovnávací paměti a zapsat celou vyrovnávací paměť jako událost. Hráč tedy opakovaně mačká Kick, Kick, Punch, aby použil útok SuperDeathFist, AI systém ukládá všechny vstupy do vyrovnávací paměti a pamatuje si poslední tři použité v každém kroku.
(Tučné čáry jsou, když hráč zahájí útok SuperDeathFist.)
Umělá inteligence uvidí všechny možnosti, když hráč vybere Kick, následovaný dalším Kickem, a pak si všimne, že dalším vstupem je vždy Punch. To agentovi umožní předvídat kombinovaný pohyb SuperDeathFist a zablokovat jej, pokud je to možné.
Tyto sekvence událostí se nazývají N-gramy, kde N je počet uložených prvků. V předchozím příkladu to byly 3 gramy (trigram), což znamená: první dva záznamy se používají k predikci třetího. V souladu s tím v 5-gramu první čtyři položky předpovídají pátou a tak dále.
Návrhář musí pečlivě zvolit velikost N-gramů. Menší N vyžaduje méně paměti, ale také ukládá méně historie. Například 2 gramy (bigram) zaznamenají Kick, Kick nebo Kick, Punch, ale nebude možné uložit Kick, Kick, Punch, takže AI nebude reagovat na kombinaci SuperDeathFist.
Na druhou stranu, větší čísla vyžadují více paměti a AI bude obtížnější trénovat, protože bude mnohem více možností. Pokud byste měli tři možné vstupy Kick, Punch nebo Block a my bychom použili 10 gramů, bylo by to asi 60 tisíc různých možností.
Model bigramu je jednoduchý Markovův řetězec – každý pár minulý stav/aktuální stav je bigram a na základě prvního můžete předpovědět druhý stav. 3-gramové a větší N-gramy lze také považovat za Markovovy řetězce, kde všechny prvky (kromě posledního v N-gramu) společně tvoří první stav a poslední prvek druhý. Příklad bojové hry ukazuje možnost přechodu ze stavu Kick and Kick do stavu Kick and Punch. Tím, že zacházíme s více vstupy historie jako s jednou jednotkou, v podstatě transformujeme vstupní sekvenci na část celého stavu. To nám dává Markovovu vlastnost, která nám umožňuje používat Markovovy řetězce k predikci dalšího vstupu a uhodnutí, jaký bude další kombinovaný tah.
Závěr
Povídali jsme si o nejběžnějších nástrojích a přístupech ve vývoji umělé inteligence. Podívali jsme se také na situace, ve kterých je potřeba je použít a kde jsou obzvlášť užitečné.
To by mělo stačit k pochopení základů herní umělé inteligence. Ale to samozřejmě nejsou všechny metody. Mezi méně oblíbené, ale neméně účinné patří:
- optimalizačních algoritmů včetně lezení do kopce, gradientního klesání a genetických algoritmů
- protivné vyhledávací/plánovací algoritmy (minimax a alfa-beta prořezávání)
- klasifikační metody (perceptrony, neuronové sítě a podpůrné vektorové stroje)
- systémy pro vnímání a paměť zpracovatelských agentů
- architektonické přístupy k AI (hybridní systémy, architektury podmnožin a další způsoby překrývání systémů AI)
- animační nástroje (plánování a koordinace pohybu)
- výkonnostní faktory (úroveň detailů, kdykoli a algoritmy zkrácení času)
Internetové zdroje na toto téma:
1. GameDev.net má a .
2. obsahuje mnoho prezentací a článků na širokou škálu témat souvisejících s vývojem herní umělé inteligence.
3. obsahuje témata ze summitu GDC AI Summit, z nichž mnohé jsou k dispozici zdarma.
4. Užitečné materiály lze nalézt také na webových stránkách .
5. Tommy Thompson, výzkumník AI a vývojář her, natáčí videa na YouTube s výkladem a studiem AI v komerčních hrách.
Související knihy:
1. Série knih Game AI Pro je sbírka krátkých článků, které vysvětlují, jak implementovat konkrétní funkce nebo jak řešit konkrétní problémy.
2. Série AI Game Programming Wisdom je předchůdcem série Game AI Pro. Obsahuje starší metody, ale téměř všechny jsou aktuální i dnes.
3. je jedním ze základních textů pro každého, kdo chce porozumět obecné oblasti umělé inteligence. Toto není kniha o vývoji her – učí základy umělé inteligence.
Zdroj: www.habr.com