Umělá inteligence v počítačových hrách aneb Myslí ta hra skutečně sama?  

Umělá inteligence doprovází hry od nepaměti. Představuje významnou část gameplaye neustále motivující hráče k tomu, aby postupoval kupředu. Ať už tedy při hraní porážíte hordu nepřátel, řešíte logické hádanky či stavíte železnici propojující průmyslová centra virtuálního světa, máte co dočinění s právě s umělou inteligencí.

Jak se ale vlastně taková herní AI (Artificial Intelligence) realizuje? A jedná se o skutečnou inteligenci, ač umělou? Pojďme na následujících řádcích společně shrnout různé formy a typy AI používané v počítačových hrách.

Co je to vlastně AI?

Pro umělou inteligenci doposud neexistuje obecně přijímaná definice, jedná se spíše o volné sdružení různorodých teorií a technik. Jeden z jejích průkopníků, Marvin Minsky, ji kdysi definoval jako vědu o vytváření systémů, které budou při plnění úkolu volit takový postup, který bychom považovali za projev inteligence, kdyby jej prováděl člověk.

Tato definice se však týká obecného pojetí a v oblasti her vesměs AI žádné jasně vymezené hranice nemá – většinou se pod tímto pojmem skrývá jakákoli část programu, která řídí chování herních systémů, ať už je to algoritmus neuronových sítí, genetický algoritmus nebo jen obyčejný skript.

Hra jako simulátor

Abychom pochopili podstatu AI, musíme si nejprve uvědomit, čím se počítačové hry liší od tradičních aplikací. Toto odlišení není jednoduché a zabývá se jím interdisciplinární vědní obor ludologie. Hlavní rozdíl tkví v tom, že hry jsou simulátory – ať už mluvíme o deskových hrách, karetních hrách, RPG adventurách či strategiích – a v každé hře existuje jakýsi model herního světa se svými vlastními pravidly a zákonitostmi. Každá herní entita, která se v tomto světě vyskytuje, se na základě znalosti těchto pravidel postupně dopracovává ke svému cíli.

Setkáváme se zde s různými typy herní inteligence – od tzv. NPC (Non-playable character), které simulují chování reálné postavy, až po autonomní systémy zajišťující chod herního světa jako celku. Na tyto systémy a objekty pak mohou být aplikovány rozličné metodiky z oblasti umělé inteligence, např. teorie autonomních agentů pro definici chování v herním prostředí, hledání cest na mapě, prohledávání stavového prostoru pro optimalizaci strategického rozhodování apod.

Teď už ale k jednotlivým možnostem a typům AI.

Řízení pomocí skriptů

Nejjednodušším typem herního AI je sada několika skriptů řídících celý herní svět, který je dostatečně jednoduchý na to, aby hráč nic nepoznal. Příkladem budiž tradiční hra Pac-Man – jedinou AI jsou zde duchové, kteří se Pac-Mana snaží chytit. Bez výrazného dopadu na herní zážitek můžeme jejich pohyb nastavit jako zcela náhodný nebo řízený primitivní heuristikou. Stejně tak můžeme skriptem řídit chování statických objektů, které jen přepínají animaci na základě několika málo stavů, náhodné procházky nepřátel v arkádách atd.

Pro zajímavost: duchové ve hře Pac-Man se ve skutečnosti řídí poměrně komplexními pravidly, viz http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior.

void update(delta, absolute) {  
 if(rand() > 0.5) goToLeft();  
 else goToRight();  
 if(rand() > 0.5) switchState();  
}

Příklad skriptu

Řízení pomocí systému pravidel (Rule-based systems)

Tato technika je jedna z nejstarších, používala se především pro definici chování dynamických objektů v arkádách. Hodí se do situací, kdy máme malý počet stavů, ale složitější řetězec podmínek. Tento řetězec pak vede ke konkrétnímu skriptu, který se spustí. Implementaci můžeme provést pomocí dvourozměrné tabulky, kde v posledním sloupci budeme mít příslušnou akci a v ostatních sloupcích podmínky, za které bude daná akce vykonána.

Jako příklad můžeme uvést rozhodovací algoritmus jednoduché strategie, kdy v případě nedostatku surovin má nejvyšší prioritu zvýšení jejich těžby. Pokud má naopak hráč dostatek surovin i energie, začne se teprve starat o jednotky a po nashromáždění dostatečného množství jednotek zaútočí.

Tabulka systému pravidel

Stavový automat (Finite State Machine)

Stavový automat se používá pro implementaci tzv. if-this-then-that procesu. Herní entita se nachází v jednom z předem definovaných stavů a po spuštění určité akce dojde k jeho změně. Každý stav pak může být reprezentován skriptem či dokonce dalším stavovým automatem a celý model tak lze libovolně škálovat.

FSM je možno modelovat orientovaným grafem, kde každý uzel představuje jeden stav a hrany pak reprezentují události, které stav přepínají. Vhodný je především pro statické objekty, které nemají příliš mnoho stavů a přechody nejsou nijak komplikované, jak ukazuje následující příklad se stavovým automatem dveří.

Pro případy, kdy se může entita nacházet ve více stavech najednou, se používají hierarchické stavové automaty – každý stav v sobě může obsahovat podstavy a jeden FSM se tak může nacházet vícekrát v několika stavech hierarchického FSM.

Stavové automaty jsou jednoduché a snadné pro ladění, nicméně je zde nebezpečí exponenciálního nárůstu akcí v případě, kdy budeme přidávat stavy, do kterých je možno se dostat z jakéhokoli jiného stavu.

Case-based řízení

Tato metodika v sobě zahrnuje poměrně pestrou škálu typů AI – od strojového učení až po plánovací mechanismy a rozpoznávání. Používají se v ní také bayesovské modely a statistické algoritmy. Základním prvkem je dvojice případ-řešení. Každou herní situaci je možno reprezentovat jako jeden případ, ke kterému AI musí najít řešení. Nalezená řešení jsou uchovávána v databázi řešených problémů, kterou je možno využít pro vyhledávání již existujících řešení.

Case-based řízení se nepoužívá pro definici chování NPC, ale složitějších systémů, ze kterých pak mohou být jednotlivým NPC posílány pokyny. Typickým žánrem pro využití této metodiky jsou budovatelské strategie a žánr RTS obecně. Výhodou je zde mnohem delší čas, který má AI k dispozici pro strategické rozhodování (typicky několik minut). AI hráč zde vybuduje např. plán pro výstavbu základny a průběžně kontroluje, zda byla očekávání naplněna. Pokud naplněna nebyla, provede analýzu a pokusí se detekovat příčinu. Obvykle se zde používá bayesovský model herního světa, který na rozdíl od toho skutečného neobsahuje všechna herní pravidla a výsledné rozhodování se tak provádí na základě pravděpodobnosti a odhadu.

Bayesovský model se také používá při analýze skill-tree či budovatelských grafů, které například určují, jakou budovu je potřeba nejprve postavit, aby bylo možno začít vyrábět kýžené typy jednotek.

Goal-driven behavior

Zatímco stavový automat definuje chování herních entit na základě stavů, goal-driven behavior používá kompozici tzv. úkolů. Z hlediska objektové metodiky se podobá návrhovému vzoru Composite.

Každý úkol může být buďto atomický nebo složený – atomické určují jednu konkrétní akci (např. jdi sbírat suroviny). Složený úkol je možno nazvat plánem, který v sobě sdružuje jednotlivé podúkoly. Skládáním pak vzniká strom, kde úkoly tvoří listy.

Každý plán lze rozdělit na podúkoly a ty pak na triviální úkoly. Podle typu rozdělujeme plány na sekvenční (pokud není podúkol splněn, není splněn plán) a selekční (pokud je splněn alespoň jeden podúkol, je splněn i plán).

Výhoda této metodiky spočívá v možnosti vytvářet různé úrovně abstrakce – vyšší úroveň stromu je abstraktnější a může být modelována obecně, zatímco na nižších úrovních se už nachází konkrétní plán pro danou jednotku – například můžeme definovat obecný úkol „vyrazit dveře“, přičemž konkrétní způsob, jakým budou dveře vyraženy, bude záviset na okolnostech (a náladě AI hráče).

Behaviorální stromy

Tato metodika vznikla teprve na začátku 21. století jako obecný model pro navrhování software pomocí funkčních bloků a poprvé byla implementována ve hře Halo2. Jedná se o jednu z nejoblíbenějších AI metodik a mnoho herních enginů nabízí rozličné vizuální nástroje pro vytváření těchto stromů propojováním dílčích bloků. Díky vizuální reprezentaci je pak poměrně snadné udržovat i stromy obrovských rozměrů.

Behaviorální strom reprezentuje mozek NPC jednotky, který řídí vykonávání jednotlivých akcí i reakci na vnější impulzy. Listy tohoto stromu reprezentují dílčí akci a vnitřní uzly pak rozhodovací mechanismus – může se jednat o kontrolu podmínky, iterátor (smyčku), vyčkávání atd.

Následující příklad ukazuje možnou podobu behaviorálního stromu mravence. Černé šipky vyznačují směr průchodu stromu a zelené šipky pořadí selektorů – pokud jde například mravenec do báze, musí se nejprve otočit směrem k bázi a teprve poté se spustí pohyb kupředu.

Fuzzy množiny

Teorie fuzzy množin je hojně využívána ve výše zmíněných rozhodovacích metodikách. Jedná se o množiny prvků, jejichž příslušnost k dané množině je dána pravděpodobností. Tohoto faktu se využívá k potlačení ostrých přechodů v rozhodovacích podmínkách.

U příkladu s mravencem máme podmínku, že se má mravenec vrátit do báze v případě, že jeho zdraví dosáhne hodnoty menší než 30. V takovém případě by se vždy obrátil směrem do báze, pokud by zdraví kleslo pod tuto hodnotu. Aplikací fuzzy logiky bychom tuto podmínku mohli transformovat na podmínku „je-li hodnota zdraví nízká, vrať se do báze“. Díky neostrému přechodu mezi jednotlivými stavy se pak počítačový hráč bude chovat o něco realističtěji, neboť na stejnou situaci může podruhé reagovat odlišně.

Prohledávací algoritmy

V každé hře můžeme definovat něco, čemu se říká stavový prostor. Z technického hlediska se jedná o množinu stavů a akcí, které určují přechody mezi jednotlivými stavy. Například u deskové hry šachy je stavovým prostorem celá šachovnice, stavem může být konkrétní rozestavění všech figurek (a informace udávající, kdo je na tahu), přechodem mezi stavy budiž tah figurkou, množina akcí určuje pro každou jednotku, kam může hrát.

Pro šachy, kde je stavový prostor relativně malý, existuje celá řada prohledávacích algoritmů, které dokážou najít optimální či téměř optimální tah pro každý stav hry (Minimax, Megamax). K prohledávání prostoru používají různé heuristiky, které určují, zda je ten či onen tah lepší či horší.

Kromě šachů existují také deskové hry, jejichž stavový prostor je příliš velký na to, aby mohl být prozkoumáván systematicky – např. populární hra go. Zde se používají algoritmy založené na náhodném prohledávání (např. MonteCarlo Tree Search) – jsou složitější, obtížně se konfigurují a obvykle je jejich implementace psána na míru konkrétní hře.

V případě složitějších her jako jsou realtime strategie je situace ještě horší – stavový prostor dosahuje enormních rozměrů a tato metodika zde selhává. Je třeba si uvědomit, že k aktualizaci modelu hry běžící v reálném čase dochází v řádu několika desítek za sekundu. Každá herní entita má přidělený nějaký výpočetní čas, který využívá k vyhodnocení vlastní situace a provedení příslušných kroků k realizaci vlastních cílů.

O možnostech aplikace obecných rozhodovacích algoritmů do strategií byla sepsána celá řada článků, např. tento, který rozebírá možnosti aplikace Monte-Carlo plánování do hry Starcraft pro mikromanagement jednotek při soubojích. Výše zmíněný problém je zde vyřešen abstrahováním stavového prostoru hry na únosnější velikost. Ačkoliv navržený algoritmus dokázal téměř vždy porazit původní AI, příliš nízká rychlost simulace znemožňovala praktické použití. Jakmile navíc do souboje vstoupila další jednotka, bylo nutno spustit celý algoritmus znovu.

Obecné prohledávací algoritmy představují v oblasti rozhodovacích problémů jeden z nejtěžších kalibrů. Díky své složitosti a náročnosti na výkon však jejich primární doménou nadále zůstávají deskové hry.

A závěr(?)

Metodik na implementaci umělé inteligence existuje celá řada a každá složitější hra si nutně vyžádá, aby byla zvolená metodika přiohnuta na míru této hře. Univerzální řešení neexistuje, stejně jako neexistuje univerzální engine, který by pokryl celé spektrum herních žánrů.

Zatímco herní grafika urazila za posledních 10 let obrovský krok kupředu, pokrok ve vývoji AI tak markantní není. Přispívá k tomu mimo jiné fakt, že problémová doména je pro každou hru dost specifická a dochází tak k neustálému znovuobjevování kola.

Dá se říct, že AI má spolu s grafickým zpracováním největší dopad na herní zážitek – ovšem přesto bývá tento prvek často opomíjen. Příkladem na závěr budiž seznam nejhorších AI v moderních hrách.