Na CD Chipu 6/2001 je offline www stránka vývojářského týmu freeware her jménem FuzzyLogic. Tam jsem si přečetl zajímavý článek. Z textu vyplývá, že ho napsal v roce 1998 nějaký student ČVUT. Myslím, že zaujme i vás, čtenáře magazínu, jehož hlavní náplní jsou počítačové hry.
-----------------------------------------------------
Umělá inteligence v počítačových hrách
Vynechány jsou pasáže vysvětlující rozdíly mezi typy jednotlivých her a další elementária, která jsem si ale v původní práci nemohl dovolit vypustit, protože překvapivě mnoho :) lidí nad třicet let ani přibližně netuší, co to je RPG. Dále jsem vynechal Creatures a Daggerfall (Velmi rozsáhlé virtuální světy), které jsou zde v samostatných článcích.
Práce je méně detailní než jsem plánoval - je to způsoběno značným nedostatkem času - pamatujme, že prakticky každá hra je hodna tak 1/2 ročního studia! Další informace budou doplňovány průběžně.
-----------------------------------------------------
Vliv počítačových her na rozvoj výpočetní techniky
Počítačové hry vyvolaly v počítačovém světě už několik revolucí. Jen příkladem jmenujme:
* Domácí počítače. Hnacím motorem u malých osmibitových domácích počítačů osmdesátých let - Sinclair ZX Spectrum, Commodore 64, Atari 800XL a pod. bylo neskutečné množství her. Masové rozšíření výpočetní techniky dalo prostor pro první generaci uživatelů a programátorů, kteří považují výpočetní techniku za zcela normální součást běžného života.
* Podpora pro 2D grafiku. Právě hry si vynutily rychlé čipy s podporou spritů, rafinovaných manipulací s barvami a vůbec akcelerace dvourozměrné grafiky. Zvláště původní Amigy ve své době naprosto excelovaly. Dnes je 2D grafika motivována jak hrami (nedostatečná průchodnost ISA sběrnice pro rychlou herní grafiku byla motivací pro vznik VL-Busu a přechod na PCI sběrnici). S potřebou výkonné grafiky souvisí i vznik standardu MMX.
* Podpora tvorby hudby a zvuků. První pořádnou podporu pro syntézu hudby měl Commodore 64. Teprve s postupem času se hudba dostala v podobě AdLibu i na PC - a motivací byly zase právě požadavky tvůrců her. Dnes tyto požadavky vedou k možnosti syntézy plně 3D zvukové scény, což umožňují moderní 3D zvukové karty jako Monster Sound 3D. Standard MMX byl zamýšlen i pro zpracování hudby, ale dnes trend jednoznačně vede k samostatným hardwarovým řešením.
* 3D vizualizační technologie. Pro exkluzivní konstrukční programy je v podstatě jedno, jak dlouho se bude počítat frame scény. Obrovská expanze 3D technologií se datuje zhruba k vydání DOOMu, který vyvolal ohromné snažení jak tvůrců 3D vizualizačního software, tak i výrobců hardware; hardwarový boom dnes nabírá velké obrátky. Dnešek je charakterizován jak souboji výrobců 3D akcelerátorů a zaměřením výrobců na 3D hraní. To vede k vývoji mnoha různorodých architektur speciálních procesorů a efektivních 3D algoritmů. 3D technologie ve svých důsledcích vede k tlaku na vývoj AGP.
* "Reálná" umělá inteligence a prostředky pro dynamické generování světů. V opravdu nejposlednější době se zájem obrací i k umělé inteligenci. Počítačoví oponenti jsou dokonale vykreslení, realisticky hluční a s využitím motion-capture neskutečně rozpohybovaní. Dnes je na pořadu dne přirozenost jejich chování a inteligence, doposud poměrně zanedbávaná a nahrazovaná jejich množstvím.
* Vliv na vývoj operačních systémů. Hry mají nezanedbatelný vliv i na vývoj operačních systémů, neboť bývají často nejnáročnějšími aplikacemi své doby pro danou platformu pravděpodobně s výjimkou grafických a DTP programů. Ze strany výrobců her je tlak na podporu rychlé grafiky, rychlé manipulace s pamětí, bezpečných operačních systémů apod. Hry měly přímý vliv na vznik standardu DirectX ve Windows a v poslední době i inkorporace standardů Direct3D a OpenGL do Windows.
Obecně lze říci, že nejlepší tituly své doby zhruba ukazují nejvyšší možnou úroveň dosažitelné "reálné" softwarové technologie. "Reálností" je zde míněna "implementovatelnost na nenákladném hardwaru a všeobecná dostupnost", nikoliv tedy například speciální programy na superpočítačích. Obvykle se za hranici všeobecně dostupné hardwarové sestavy považuje základní cena pod 1000 USD (bez monitoru a rozšiřujícího vybavení).
Na okraj je třeba poznamenat, že vývoj AI pro hry je dnes jednou z nejlépe placených prací v rámci vývoje moderních her a zkušený AI vývojář pobírá plat vyšší než kupříkladu zkušený programátor pro vývoj 3D engines. Rozhodně tedy nejde z hlediska vývojářů o druhořadou nebo okrajovou záležitost.
Projekt Game AI-Tech
Projekt Game AI-Tech slouží k propagaci umělé inteligence prostřednictvím her. Sledujeme-li vývoj v posledním roce, je třeba podtrhnout výrazný příklon k vylepšování umělé inteligence. Průměrný podíl strojového času věnovaného umělé inteligenci vzrostl podle Stevena Woodcocka z méně než jednoho procenta na více než 30%. V téže době se objevila snaha vývojářů o "skutečnou AI ve hrách", tedy odstranění už nedostatečných jednoduchých algoritmů výkonnou a efektivní AI [Woodcock 1998].
Analyzujeme-li dynamický růst zájmu o problematiku aplikace inteligentních agentů do spotřební elektroniky a počítačových her, je až překvapivé, s jakou pomalostí a nezájmem reaguje vysoké školství a základní výzkum na nově vznikající společenskou poptávku. Požadavky aplikace umělé inteligence v oblasti her a spotřební elektroniky vyžadují rychlé a spolehlivé algoritmy. Oblast zvláště adaptivních agentů není dostatečně prozkoumána z hlediska praktického využití a vývojáři her v podstatě provádějí svůj vlastní výzkum. Nejasnost principů, o které je možné spolehlivě opřít herní umělou inteligenci aniž by hrozilo riziko nějakého typu kolapsu u masově prodávaného produktu se projevila na vývoji v minulém roce, kdy se experimentálně zkoušely všechny možné algoritmy. Nepochopitelnost averzivního postoje vůči hrám dobře ilustruje následující příběh: Před pouhými dvěma roky jsme byli na přednáškách z počítačové grafiky na VŠE instruováni, že "hrami se zabývat nebudeme". V témže kursu jsme se seznámili s novinkou zaváděnou pro workstations - OpenGL standardem. Dnes OpenGL masově proniká na stolní PC, ale není to způsobeno žádnou "seriózní aplikací", ale právě příchodem nových 3D herních titulů, z nichž pravděpodobně prvním byl GLQuake.
Problematika her přitom zajímá většinu teenagerské populace a mnoho z nich může přivést k problematice moderních softwarových technologií a moderních technologií vůbec. Vzhledem k absenci seriózního zájmu o tuto problematiku jsem se rozhodl zahájit projekt, jehož smyslem je právě pohled do "kuchyně tvorby AI her". Tento projekt byl zahájen 1.11.1997 jako "non-commercial non-profit" projekt v rámci akademického prostředí a do 12.1.1998 veden v rámci ÚIVT ČAV. Pro nezájem ze strany vedení ústavu byla tato činnost v rámci ústavu ukončena a od 12.1.1998 jde o moji proprietární aktivitu na komerčním diskovém prostoru.
Základní okruhy herních problémů, týkající se umělé inteligence
Klasické problémy zahrnují:
* algoritmy hledání nejkratší nebo nejoptimálnější cesty ve statickém nebo dynamicky se měnícím prostředí
* pravidlové systémy rozhodování
* elementární učení se z minulosti (eliminace minulých chyb)
* prohledávání stavových prostorů
Nověji se objevují další problémy:
* adaptivní počítačoví protivníci v oblasti strategií
* adaptivní počítačoví protivníci v oblasti akčních her (realtimové enginy)
* vytváření "umělé přirozenosti" prostředí (hráč vnímá svět hry jako přirozený)
* poloexperimentální zkoumání možností technologií AI
Trendy v implementaci metod umělé inteligence v počítačových hrách
Sledujeme-li vývoj implementace metod umělé inteligence ve hrách, je vidět několik trendů. Při jejich sledování narážíme na obtíž - hry jsou komerčními produkty firem, které většinou nezveřejňují principy jimi publikovaných her a to hlavně u úspěšných titulů. Tituly neúspěšné bývají naproti tomu obohaceny občas klamavými informacemi (např. se dosti často udává "neuronový oponent") ačkoliv se ve fázi finálního testování ukážou významné problémy se stabilitou adaptivního oponenta a aby bylo zabráněno naprostému fiasku je adaptivní oponent nahrazen klasickou optimalizací, obohacenou například modelováním náhodných odchylek.
Pevně naprogramované chování
Nejjednodušší variantou je pevně naprogramovaný oponent tvořený sekvenční sadou podmínek, což přináší četné nevýhody jako například stereotypii a nemožnost dosažení některých řešení. Zvláště druhý problém se ukázal jako fatální, protože u komplexních her často nastávají autory neočekávané situace. Zatímco šachy jsou hrou relativně "triviální", neboť je k dispozici úplná informace, šachovnice je diskrétní, konečná a "velmi malá", u mnoha her je prostor (v obecnosti) spojitý, rozsáhlý a často vytvářený jinou osobou než vytvářela algoritmus oponenta. To vede k množství speciálních případů, kdy algoritmus selže a počítačem řízené monstrum se zasekne nebo zacyklí v nějaké herní prostoře či situaci a nemůže se dostat ven. Zatímco stereotypní chování oponentů je pokládáno hráči za "nepříjemnost", zasekávání se je pokládáno přímo za chybu. Je ale jasné, že se u pevně zapsaných podmínek jen s krajní obtíží ošetřují všechny možné případy.
Jako příklad je možné uvést pověstnou chybu v Duně 2: Harvester (kombajn) určený pro těžbu koření které je třeba pro získávání prostředků se dokázal bránit útoku pěchoty tak, že se zachoval jako "pásové vozidlo" a útočící pěšáky přejel. Algoritmus AI zajišťoval výrobu nových harvesterů v případě jejich zničení, ale v případě, že se harvester přepnul do režimu "pásového vozidla", chyběla podmínka pro opětovné zahájení těžby. Lidská strategie pak spočívala v tom, že člověk nechal zaútočit pěchotou na všechny harvestery, tak, aby nebyly zničeny. Kombajny přejely útočníky a přestaly těžit, ale AI nenechala ani vyrobit nové, takže se jí přísun prostředků zastavil.
O něco lepším řešením se ukázaly pravidlové systémy, které mohou být simulovány i v pevně vytvořeném kódu tak, že algoritmus prohledá všechny alternativy, přidělí jim míry uspokojivosti a z nich nakonec vybere optimální. To do značné míry eliminuje nedostatky prosté sekvence podmínek, ale chování oponentů je stále vnímáno jako stereotypní, neboť ve stejné situaci počítač vybírá stejné řešení. Tento nedostatek byl následně odstraňován vnesením nederminismu, kdy počítač náhodně volí mezi přibližně stejně výhodnými alternativami. Výsledek je percipován jako mnohem živější a metoda je hojně užívána.
Optimalizační metody
Velmi důležité jsou optimalizační metody, které slouží k řešení mnoha významných okruhů problémů jako:
* Hledání nejkratší nebo optimální cesty a to i v situaci, kdy se graf možných cest dynamicky mění v průběhu času.
* Optimální alokaci zdrojů, výroby nových jednotek.
* Určení optimální struktury útoku - hledání specifikace, která jednotka vlastní zaútočí na kterou jednotku nepřátelskou a v jakém pořadí.
* Hledání optimální prostorové konfigurace jednotek a základen tak, aby bylo riziko při napadení minimální při největším palebném pokrytí co do plochy nebo intenzity.
* Hledání strategických bodů na mapě - kde vede mnoho důležitých cest, kde jsou zdroje surovin a zdroje pro výrobu jednotek.
Je patrné, že se ve hrách řeší podobné okruhy problémů jako v reálném světě, např. můžeme uvést problematiku pokrývání plochy chráněného území protiletadlovými bateriemi se specifickými vlastnostmi a dosahem. Rozdíl vidíme jen ve složitosti problému - u her je do značné míry zajištěna konstantnost vlastností a při optimalizaci se uvažuje méně kritérií.
Absence kvalitního optimalizačního algoritmu může vést k velmi nedobrým herním výsledkům. Jako příklad jmenujme Transport Tycoon, což je simulace dopravní společnosti. Přesto, že právě doprava a logistika představují jednu z velmi významných oblastí, kde jsou masově aplikovány optimalizační algoritmy, autor naprosto nezvládl algoritmy pro řízení vláčků. "Jízdní řád" není optimalizován globálně, ale lokálně, tj. pohybuje se ve směru vektoru tvořeného rozdílem X,Y koordinátů výchozí a cílové stanice. Vlastní cestu po kolejích hledá v omezeném okně a pokud ji nenajde, backtrackuje zpět. Každý vlak navíc optimalizuje nezávisle. Katastroficky to dopadá na tratích s bohatým větvením a hustým provozem, zvláště v případě zapnutí simulace poruch. Vlaky se klidně zamotají nebo úplně ucpou nějakou křižovatku a pro hráče je velmi obtížné problém vyřešit i ručně. Vzhledem k tomu, že hráč je odměňován za rychlost dopravy na jednotku množství, může při troše nepozornosti přijít při růstu rozsahu hry o mnoho prostředků. Hráči proto raději staví speciální tratě pro každý vlak. Na druhou stranu je jasné, že jde o NP-úplný problém a vzhledem k tomu, že hráč může dynamicky stavět a bourat tratě, příp. mohou být blokovány porouchaným vlakem, jde o značně netriviální problém. V Transport Tycoonovi DeLuxe byl problém částečně řešen implementací jednosměrných semaforů, tím je problém převáděn na složitost návrhu tratě.
Fuzzy algoritmy
Ve stejné době se začaly zavádět fuzzy algoritmy pro rozhodování, zvláště u her s neúplnou informací (např. s "fog-of-war" na mapě). Zavedení "fog-of-war" přináší pro umělou inteligenci značné potíže, protože je nutné přijít s algoritmy, které odhadují ve velmi nejisté a proměnlivé situaci. Zde již opouštíme pole algoritmů klasických znalostních systémů, které při vyhodnocování informaci spíše sbírají a nebo dokážou navíc minimalizovat počet nutných dotazů.
Příkladem uveďme situaci ideově vycházející z Duny 2, kdy počítač s omezeným okruhem viditelnosti po mapě odpálí raketu do základny lidského hráče: Raketa při dopadu něco zničí ale je jen velmi obtížné odhadnout co bylo vlastně zničeno. AI mohla nasbírat za pomoci průzkumných jednotek informace o tvaru a částečně i struktuře lidské základny, ale pokud nemá AI podvádět, po úspěšném zásahu je tato informace znehodnocena a panuje nejistota, jakým způsobem byl člověk oslaben. Raketa mohla úplně minout a újma na bojeschopnosti člověka je pak rovna nule. Předchozí stav sil se nezměnil. Mohla zasáhnout obranný perimetr a to znamená, že by AI měla zahájit neprodlený útok a snažit se maximálně vytěžit z oslabené obrany. Také mohla zasáhnout nějakou kritickou budovu (např. stavební centrum) a tímto úspěšným zásahem počítač v podstatě vyhrál. V takové situaci není třeba spěchat, protože člověk může jen doufat v to, že se mu podaří nějakým způsobem zničit základnu počítače. Je výhodné proto přejít do strategické defenzívy. Jak je patrno, situace se může zcela fundamentálně zvrátit. Zdá se, že ideální je provést průzkum poškození nepřátelské základny, ale je třeba mít na paměti, že i v případě vyřazení kritických budov může být defenzívní perimetr nepoškozen a průnik průzkumníků může být nemožný! Navíc není možné ztrácet příliš mnoho času, který by nepřítel mohl využít k opravám a regeneraci sil.
Je patrné, že inferenční systém operuje v podmínkách značné nejistoty a aplikace fuzzy algoritmů je zcela na místě. Jednotlivé jednotky vcházející do kontaktu s nepřítelem přinášejí parciální poznatky, které je možné převádět na informaci s nejistotou, kde lze informaci ohodnocovat např. podle poměru známé a neznámé plochy nepřátelské základny.
Speciální problém představuje fakt, že hráči realtime strategií (jako je uváděná Duna 2) jsou navyklí na to, že počítač používá triviální optimalizaci a útočí pouze frontálně. Proto přizpůsobují tvar svého obranného perimetru právě pro odražení frontálního útoku a usuzovat z velmi silné obrany v jednom pásmu na stav v neznámých oblastech je hrubě zavádějící.
Fuzzy algoritmy jsou výhodné proto, že ve většině her existuje množství kauzálních a známých pravidel a panuje nejistota pouze v tom, jakým způsobem se hráč zachová a jakou strategii zvolí. Nemá smysl nasazovat adaptivního oponenta tam, kde jsou známy efektivní strategie a je třeba pouze podle projevů oponenta zjistit, jakou si vybral. V rámci fuzzy algoritmů se také lépe tvoří interní model constraints, pokud jsou constraints definovány kauzálními vztahy.
Pokud například algoritmus ví, jaké surovinové zdroje má člověk na svém kusu mapy, může spočítat odhady jednotek, které může vyrobit. Dobrý algoritmus je například tento:
* vezmeme nejvyšší odhad zdrojů z části mapy, která je pod kontrolou oponenta
* odečteme zdroje za nezbytně nutně vyrobené budovy
* v průběhu bojů nebo průzkumu evidujeme pozorované nepřátelské jednotky a jejich technologickou úroveň a odečítáme od odhadovaného zbytku surovin
Z toho získáme "výrobní contraints" a v kterémkoliv okamžiku lze spočítat významné koeficienty:
* Horní odhad času dokončení těžby. Většina hráčů zahajuje útok v okamžiku, kdy mají maximální útočnou sílu, která je definována buď maximálním povoleným počtem jednotek nebo právě surovinovými limity.
* Horní odhad úderné síly při útoku zbraní s optimálním indexem cena/účinek. V podstatě odhad nejvyšší možné úderné síly při hromadném útoku.
* Horní odhad úderné síly při útoku zbraní s nejdelším dostřelem. Důležitý pro případ, kdy se hráč rozhodne pro taktiku pomalé likvidace z nejvyšší možné vzdálenosti.
* Horní odhad úderné síly při útoku zbraní s největší pohyblivostí. Pro případ nasazení mobilní taktiky hit-and-run.
* Horní odhad úderné síly při útoku zbraní s nejvyšší odolností. Odhad pro získání informace o nejvyšším čase potřebném k likvidaci hromadného úderu.
* Horní odhad úderné síly při útoku zbraní s největší ničivou silou. Odhad pro získání informace o největší možné palebné síle, které mohou být exponovány vlastní jednotky.
* Horní odhad úderné síly při útoku letectvem. Speciální případ boje, který vyžaduje speciální obranná zařízení.
Odhady se obvykle značně liší, ve většině her mají nejlepší vlastnosti v daném směru různé typy zbraní. Hráč většinou využívá zbraňový mix, ale taktiky "důraz na zbraň s nejdelším dostřelem" nebo "důraz na zbraň s optimálním poměrem cena/výkon" nejsou neobvyklé. Odhady lze získat v libovolném okamžiku a jsou determinovány objektivními okolnostmi, tj. nezávislé na strategii hráče. Představují mez jeho možností v daných směrech a velmi vhodně se doplňují při inferenci nad neurčitými informacemi z bojiště. Vzhledem k tomu, že většina hráčů má své oblíbené zbraně, je možné constraints model použít jako dobré vodítko jak pro odhad množství, tak i nezbytného času pro výrobu.
Fuzzy algoritmy jsou dobře kombinovatelné s constraints, je možné je využít pro práci s rozhodovacími stromy a to i v případě, kdy jsou u rozhodovacích stromů adaptivně modifikovány váhy. Představují velmi spolehlivý a efektivní nástroj, který netrpí řadou problémů které nalézáme u neuronových sítí. Umožňují jemné vyladění obtížnosti oponenta a nehrozí, že by se adaptivní změnou vah rozhodovacích stromů oponent nějak výrazně vymkl ze zamýšleného obtížnostního pásma (ať už odučením se klíčové strategii nebo jinou hrubou chybou či naopak přílišným zdokonalením se nebo objevením nepředpokládané "superoptimální" strategie). Postrádají naproti tomu možnost nalézání zcela nových, neočekávaných strategií.