Hlavní strana -> Extra -> Umělá inteligence v počítačových hrách

Umělá inteligence v počítačových hrách

Počítačové hry představují v mnoha směrech špičku v oblasti software. Ke koupi opravdu dobrého počítače existují tři motivy: špičkové vědeckotechnické výpočty a simulace, nová verze textového editoru od Microsoftu a - samozřejmě - počítačové hry. V oblasti 3D grafiky jde asi o zcela absolutní hi-tech, výborné jsou i technologie zpracování zvuku. Zatímco se výrobci předhánějí v plynulejší, barevnější a i jinak úžasnější grafice, občas staví trochu na okraj zájmu vlastní děj a počítačovou inteligenci. Leč lkaní nad povětšinou nevalnou úrovní příběhů ponechám jiným, neboť dnešní povídání bude o umělé inteligenci ve hrách.

O umělých lidech a jiných obludách snili lidé od dávnověku, ale vlastní technologie nabrala rozjezd až koncem druhé světové války. Tehdy se vědci začali zabývat počítači, genetickým inženýrstvím, atomovou pumou a jinými prostředky pro zajištění světlých zítřků. První hrou, kterou se začali kybernetičtí vědci zabývat, byly šachy. Čert ví proč - v té době bylo hraní šachů považováno za záležitost superiorní inteligence, za něco hodně lidského - možný důvod je ale ten, že tehdy ještě neexistoval DOOM. Se šachy to nebyla úplně šťastná ruka, protože to je sice hra složitá, ale přece jenom pouze deterministická a s konečně velkým stavovým prostorem, což znamená, že je i hloupý algoritmus na opravdu velmi rychlém počítači dokáže hrát dobře. Totiž: počet všech možností, ve kterých se na čtverečkovaném bitevním poli mohou objevit figurky, je konečný a počet všech možných tahů také. Teoreticky stačí prozkoumat všechny možnosti a vybrat nejlepší tah. Naštěstí - pro umělou inteligneci naneštěstí - je ale těchto kombinací příliš mnoho, a tak vědci vybádali mnoho teorií, jak hrát šachy dobře i s mnohem menším výpočetním výkonem. A také, jak hrát hry nedeterministické (ty, u nichž není výsledek tahu předem jasný, ale je v něm obsažena náhoda) a hry, kdy počítač nemá k dispozici úplnou informaci o protivníkovi a musí hádat.

Protože se z ne úplně jasných důvodů nemají přiliš rádi lidé zabývající se umělou inteligencí s lidmi zabývajícími se počítačovou grafikou, byla inteligence ve hrách - pokud ovšem nešlo o hry vysloveně strategické - často zanedbávána. Teprve v poslední době se začalo blýskat na lepší časy. Mnoho týmů začalo ohlašovat použití lepších uměle inteligentních technologií v připravovaných titulech jako například v Conquest Earth. Za změnou postojů je více událostí, mezi nimiž je nutné zdůraznit vydání mého ne-až-tak-oblíbence Quaka, který s sebou přinesl Quake C a možnost relativně snadného přeprogramování vlastností objektů ve hře. Více autorů poté zkusilo naprogramovat umělé spolu/protihráče, kteří mají podobné vlastnosti jako vaše postava. Jmenují se bots (boti) a zaujali dostatek výrobců her, takže se objevili i v dalších nových titulech.

Způsobů, jak vytvořit umělou inteligenci ve hrách, je přehršel. Tož to neprotahujme a hrr na ně.

1. Předprogramované chování

Program není nic jiného než sled příkazů, které jdou za sebou a počítač je jenom slepě vykonává. Předprogramované chování je nejjednodušší - počítač nemá nejen žádnou volbu akcí, ale dokonce se často ani nemůže změnit pořadí podmínek, které testuje, takže se počítačem ovládané jednotky chovají šablonovitě a stupidně. Na druhou stranu je to nejjednodušší způsob, jak počítačové chování naprogramovat, a proto je používáno velmi často. Aby se jednotky nechovaly pořád úplně stejně, bývají programy často obohaceny o náhodný prvek - když si počítač neumí vybrat z možností, prostě si hodí kostkou. V rámci předprogramovaného chování se objevuje několik metod, které činí chování paňáců smysluplnější a nezávislejší na původní představě autorů. Často se používají optimalizační metody, které počítají, která herní strategie je nejvýhodnější. Je použita například pro řízení pohybů vozidel ve Steel Panthers - vozidla hledají takovou cestu terénem, po které se dostanou k cíli nejrychleji. Také se používá v Trasport Tycoonovi, kdy počítačoví oponenti hledají na výnos nejvýhodnější dopravní cesty. Optimalizační metody můžou počítat i možné cíle pro útok (na jaké jednotky a v jakém pořadí útočit, kde začít těžit a podobně). Samy o sobě nejsou příliš chytré, ale v čase, který vy potřebujete pro kliknutí na položku v menu, je počítač schopen prokalkulovat tisíce možností a zvlášť situaci,kdy je jednotek příliš mnoho, mu dávaji velkou výhodu.

Na variabilitě hrám velmi přidávají rámce(frames), což jsou sice obyčejné prográmky, ale každý objekt (obluda, tank) je vykonává nezávisle na ostatních. Každý potvor má "horizont pohledu" a vykonává akce podle toho, co "vidí". Vtrhne-li kupříkladu nepřítel do vesnice, nastává v místě útoku pozvolna se šířící zmatek, ale na druhé straně vísky je klid. Nad rámci jednotlivých potvorů jsou vyšší rámce, například taktický (koordinuje útočící svaz) nebo ekonomický (koordinuje výrobu a stavění). Tento hierarchický systém se nejenom lépe programuje, ale v akci vypadá také mnohem přirozeněji.

Největší nevýhoda pevných programů je v tom, že se u složitých her prakticky není možné připravit na všechny varianty chování. A už vůbec ne bez chyb.

2. Pravidlové systémy

Pravidlové systémy jsou podobné programům s jednou výjimkou: Pravidla jsou oddělena od programu, který je zpracovává a počítač si může vybírat podle situace. Nejdřív si prohlédne mapu a projde databázi - nakonec si vybere nejlépe odpovídající pravidlo. Pravidlový systém má tu výhodu, že může být otevřený a počítač se i během hraní může učit nové znalosti, které si přidává do databáze, Další výhoda je v tom, že systém může snadno měnit aktivaci pravidel - může mít jednu sadu "útočných" a jinou "obranných" pro tytéž jednotky. Pak pro něj stačí při přechodu do útoku udělat "Cvak" a všichni panáci se chovají jinak.

3. Imprintovaná (vtištěná) inteligence

V mnoha hrách je počítačová inteligence vytvářena nejen pravidly nebo programem, ale také vhodným upravením prostředí hry. Asi nejextrémnějším příkladem mohou být logické hry nebo adventury, ve kterých počítač nemá žádnou vlastní inteligenci, a přesto se těžce moříte. Všechny rébusy a hádanky byly vytvořeny člověkem - autorem, v podstatě tedy nesoupeříte s inteligencí počítače, ale inteligencí tvůrce hry. Samozřejmě můžete namítnout, že tady vlastně o žádnou počítačovou inteligenci nejde. Ale jak jsem uvedl, byl to jen mezní případ. Častější je kombinace pravidlového systému s doplňky: počítačová inteligence je hloupější, než by bylo vhodné, a take je posilněna "náhodnými okolnostmi", jako že má počítač všechny důležité suroviny po ruce, má předem založené základny na nejvýhodnějších místech, terén vyhovuje jeho způsobu boje a podobně, zatímco vaše jednotky jsou - jako na potvoru- zašité v tom nejhorším kusu mapy. Dále může být počítačův kůs mapy vytvořentak, aby se mu co nejlíp stavěly cesty, jeho jednotky se pohybovaly optimálně a podobně. Počítač sám o sobě "nepodvádí", to mu jenom trochu pomohl jeho papínek autor.

4. Prohledávání stavového prostoru

V některých hrách může být počítač proklatě silný. Povětšinou jde o hry, které mají jasně stanovená (deterministická) pravidla, pevně daný výchozí stav a/nebo pevně dané podmínky pro vítězství. Příkladem mohou být šachy nebo řešení Rubikovy kostky. V libovolném okamžiku máte jenom omezený počet způsobů, jak táhnout, panáci nebo kostky jsou rozmístěni zcela jednoznačně a dají se také jednoznačně popsat. Takovému popisu se říká stav. Jednotlivé stavy hry jsou pospojovány proveditelnými tahy a vytvářejí tak síťovou strukturu, které se říká stavový prostor. U každého stavu hry je možné určit, zda je dostažitelný z výchozího stavu - tak například situace, kdy jsou na šachovnici bílí pinčlíci pěkně v řadě za sebou ze strany bílého směrem k černému, je nedosažitelná. Nu a pokud má nějaká hra takovéhle pěkné vlastnosti, je možné poštvat počítač, aby pěkně rychle zkoumal všechny možnosti a táhl tou nejlepší. Teoreticky by nemělo být možné v podobných hrách nad počítačem vyhrát, kdyby stavové prostory nebyly tak příšerně veliké. Určitě znáte historku s indickým mudrcem, ktery požadoval po šáhovi za vynalezení šachů drobnou odměnu: na první políčko jedno zrnko rýže, na druhé dvakrát tolik - dvě, na třetí čtyři a tak dál. V principu maličkost, až na to, že těch zrnek by muselo být 2^64, tj. něco pod 2*10^19, čili šlo by o zásoby pro hladovějící Afriku. Podobným způsobem roste rychle i velikost stavového prostoru při prohledávání do větších vzdáleností od momentálního stavu. Jen málo šachových počítačů si může dovolit zkoumat všechny možné pozice až na 9 tahů dopředu jako Deep Blue fimry IBM. Deep Blue, který porazil v květnu Garryho Kasparova, má ovšem paralelní architekturu se 500 speciálními procesory, které mu umožňují výkon 400 miliónů analyzovaných pozic za sekundu. Díky nim mu stačí na oněch devět tahů dopředu pouze necelé tři minuty, zatímco nadupané Pentium potřebuje více než 5 hodin.

Protože ale lidé myslí jinak - nezkoumají všechny možnosti, ale intuitivně odhadují a plánují na velmi mnoho tahů dopředu - musí být i šachový počítač obohacený od další informace, jako například záznamy her velmistrů, které mu umožňují odhadovat sílu jednotlivých stylů her a zaměřit se na silné tahy, zvláště na analýzu otevření. Deep Blue má databázi celkem 600 000 her. Teprve takový drtivý výkon dokázal porazit šachového velmistra v sérii dvou výher jedné prohry a tří remíz. S růstem rychlosli procesorů a kvalitou software lze očekávat, že se herní schopnosti šachových superpočítačů ještě zlepší - ovšem vzhledem k tomu, že výpočetní nároky rostou exponenciálně, nebudou pokroky až tak rychlé jako dosud.

Největší umění u systémů s prohledáváním stavového prostoru je právě ve znalostech, kdy lze slepé hledání ušetřit. Ohromnou spoustu času totiž počítač ztrácí v prohledávání úplně zbytečných variant nebo v opakovaném zkoumání podobných situací. Aby se práce zrychlila, používají se speciální funkce zvané estimátory("odhadovače"), které si tipnou, zda se další hledání vyplatí a nebo ne. Estimátory musí být sestaveny pro každý problém zvlášť a na jejich správné funkci závisí dobý výsledek celého programu. Jejich tvorba je tak trochu věda a trochu umění. Například u šachových programů představují estimátory prakticky jediný rozdíl mezi špatným a dobrým programem.

5. Adaptivní systémy

Adaptivní (učící se) systém je schopen získávat znalosti a schopnosti za chodu programu. Do dnešní doby bylo vytvořeno (nebo je vytvářeno) jen málo her, které používají tuto hi-tech technologii. Zjednodušeně řečeno jde o systém, který se dokáže poučit ze svých porážek a vítězství, dokáže z nich těžit informace, které mu pomáhají být lepší. Tak trochu herní můra - několikrát vyhrajete - a ejhle! Počítač se poučil a staré triky na něj nezabírají! Je třeba vymyslet něco nového. Jste pod kontrolou počítačového systému - odkouká od vás vše, co je dobré, i čemu by se měl vyhýbat. Jak to dělá?

Postup je z hlediska hráče jednoduchý: zkušení pařiči hrají svého multiplayer Quaka nebo Dooma a počítač si zaznamenává, co kdy který hráč provedl, kdy vystřelil, jakou zbraní, kdy pro změnu ne, kdy si sebral lékárničku a kdy se schoval. To všechno posuzuje v kontextu - jaký byl protivník, čím byl vyzbrojený, jaký byl stav vlastního zdraví a podobně. Potom všechno pečlivě analyzuje a vybírá si ty herní strategie, které vedly k vítězství a vyhýbá se těm, které skončily porážkou. Poměrně záhy pak přijde na to, že se při zranění vyplatí běžet pro lékárničku a při větším počtu nepřátel použít raketomet. I když přírůstek znalostí může vypadat zanedbatelně, nesmíte zapomínat na nepříjemný fakt, že je počítač ve vydávání rozkazů nepoměrně rychlejší. V okamžiku, kdy mu v realtimeové strategii předvedete obchvat a současný útok několika skupin na základnu, máte prakticky smůlu: on to provede taky, ale zatímco budete horko těžko stíhat vydávat rozkazy, počítačoví bojovníci budou bravurně útočit ze všech stran. Právě proto je při návrhu adaptivního systému třeba myslet i na to, že se počítačový oponent může vypracovat až do frtustrující dokonalosti a hlídat, aby nebyl "příliš dobrý".

Jsou tři hlavní způsoby, jak se počítač může za běhu hry učit a každý z nich má svoje výhody a nevýhody. První z nich je tak zvaný knowledge mining, neboli těžba znalostí. Knowledge mining technologie spolupracuje s pravidlovým systémem, kterému dodává nová pravidla pro chování. Je vhodný hlavně pro strategické hry - počítač doluje nová pravidla pro úspěšné hraní ze záznamu hry a přidává je k těm, které už znal, a naopak se zbavuje pravidel, které jsou jenom na obtíž. Pro knowledge mining je podstatné, že výsledkem učení jsou pravidla a při hraní příliš nezáleží na rychlosti reakce, takže si počítač může vybírat. Druhý způsob se jmenuje casebased reasoning, usuzování na základě případů. Počítač si při něm ukládá do paměti situace a jejich řešení. Tato metoda je dosti stará, její první výskyt v logické hře jsem viděl už v roce 1984. Hra si do paměti ukládala všechny průběhy partií, které počítač prohrál a nikdy neopakovala staré chyby. Casebased reasoning je ještě náročnější než knowledge mining, protože musí mít dost času na probírání se databází jednotlivých ukázek - a databáze může zahrnovat i tisíce případů. Z důvodu náročnosti se taky hodí spíš pro strategické hry. Jeho hlavní výhoda oproti knowledge miningu je v tom, že zatímco knowledge mining odvozuje obecné a často používané zásady (například, že s ostřelovaným harvesterem jdeme směrem k raketovým věžím, aby vetřelce rozšmelcovaly), casebased reasoning si pamatuje všechny možné případy a postřehne třebas i jen jednou použitý trik, a je ho proto schopen ve vhodné situaci nasadit.

Nejrychlejší způsob jsou neuronové sítě(neural networks), u kterých je spíše náročné jejich učení než usuzování ve hře. Neuronové sítě se skládají z matematických neuronů, které simulují schopnosti lidského mozku, hlavně učení. Ve fázi uční vznikají mezi umělými neurony nové spoje, ale nemění se počet vlastních prvků - na rozdíl od předchozích metod, jejich báze při učení beznadějně bobtnají a snižují rychlost usuzování. V rychlosti vlastního hraní pak není žádný rozdíl mezi sítí naučenou a nenaučenou, a je proto ideální pro akční hry. Na druhou stranu mívají neuronové sítě tendenci ke špatnému učení a mohou si chvílemi počínat dost zvláštně a nelogicky. Jejich síla roste s opakováním, a když se síť dobře "vychodí", nedá vám žádnou šanci.

6. Podfuk

Podfuk je celkem často používaný nástroj umělé inteligence. Jde o to, že je dost obtížné vytvářet si například odhad možných skrytých nepřátelských formací. Nu a v paměti je máme přece uložené, ne? Tak do nich trošku, trošičku nakoukneme... Zatímco vy nepřítele nevidíte, on vás ano. V mírnějších podobách se podfuk objevuje v "poněkud naboostovaných" vlastnostech nepřátel, kteří lépe vidí, vyrábějí levněji nebo zadarmo. V okamžiku, kdy se to počítači hodí, na vás sešle nějakou tu katastrofu a podobně. Zatímco u předpřipravených krajin a továren jde o pomoc do začátku, tady je podvádění vysloveně součástí strategie hraní. A to nemáme rádi!

Jakkoliv by se mohlo zdát, že navrhnout perfektního oponenta není vlastně žádný problém, nenechte se mást. Je to problém. Všechny popsané technologie jsou dost jednoúčelové, asi jako kostky Lega. A aby mohl vzniknout vynikající a vybalancovaný oponent, je nutné je pečlivě zkombinovat a sestavit do jedinečného celku. A to je umění. Už mnohokrát jsme s neradosti recenzovali hry, u kterých se autoři dušovali, že jsou "nejlepší", "neporazitelné" a podobně. Bohužel je velmi snadné něco opomenout nebo naopak přehnat. Oponent, který s ledovým klidem projede vedle vašeho harvesteru, je stejně zranitelný jako ten, který se po něm bezhlavě vrhá za každou cenu.

A až vám počítačový oponent natrhne ucho, neberte to tak vážně jako Kasparov poté, co prohrál s Deep Blue 2,5 - 3,5 počítačový oponent si z vás - na rozdíl od kamarádů - dělat legraci nebude. Prohra? Výhra? Vždyť je mu to vlastně jedno.

Michal "CyberWolf" Rybka

Programování v C | CZ 175/477 | Mapa stránek
Bc. Petr Klimánek, student Ostravské univerzity v Ostravě