eské vysoké u ení technické v Praze Fakulta elektrotechnická
Semestrální projekt
Analýza um lé inteligence v ak ních po íta ových hrách a jeji implementace František Hruška Vedoucí práce: Ing. Petr Felkel, Ph.D.
Studijní program: Elektrotechnika a informatika strukturovaný bakalá ský Obor: Výpo etní technika
-1-
1. 2. 3.
4. 5. 6. 7. 8. 9.
10. 11.
12. 13.
14.
Úvod ..............................................................................................................................................3 1.1. Bot 3 AI ve hrách (historie)................................................................................................................................4 Prohledávání stavového prostoru (pathfinding) a waypointové sít .........................................................5 3.1. Neinformované metody prohledávání stavového prostoru 5 3.1.1. Breadth-First Search (BFS) 5 3.2. Informované metody prohledávání stavového prostoru 6 3.2.1. Algoritmus A-Star 6 3.2.2. Dijkstr v algoritmus 7 3.3. Waypointové sít ve hrách 8 3.3.1. Quake 3 8 3.3.1.1. Area Awareness System 8 3.3.1.2. Areas 8 3.3.1.3. Reachabilities 9 3.3.1.4. Princip algoritmu pro pathfinding v Quake 3 11 3.3.2. Counter-Strike 11 3.3.2.1. Waypointy a jejich tvo ení v CS 11 Finite State Machine (FSM).....................................................................................................................14 Fuzzy logika..............................................................................................................................................15 5.1. Využití fuzzy logiky 15 5.1.1. Botovo rozhodování pomocí fuzzy logiky 15 Neuronové sít ..........................................................................................................................................18 6.1. Chování bota 18 Expertní systémy.......................................................................................................................................19 Genetický algoritmus................................................................................................................................20 8.1. Struktura algoritmu expertního systému 20 8.2. Získávání zkušeností 20 Plánování...................................................................................................................................................21 9.1. Postup p i plánování 21 9.2. Plánování se zásobníkem cíl a systém STRIPS 21 9.3. Nelineární plánování 21 9.4. Hierarchické plánování 22 Entity.........................................................................................................................................................23 10.1. Entity a jejich používání v Q3 23 10.2. Entity a jejich používání v CS 23 Základní charaktery bot a akce jimi používané......................................................................................26 11.1. Charaktery bot 26 11.1.1. N které herní charakteristiky ovliv ující styl hraní bota v Q3 26 11.1.2. Charakteristiky bot v CS 26 11.2. Základní akce, které m že bot provád t 27 P ekážky a skláda ky................................................................................................................................28 12.1. ešení v Q3 28 12.2. Návrh ešení situace pomocí waypoint 29 Chat...........................................................................................................................................................30 13.1. Textové šablony 30 13.2. Eliza 30 13.3. Zahájení chatu 31 13.4. Odpov di 32 13.5. Random strings 32 13.6. D vody chatování 32 Zdroje........................................................................................................................................................34
-2-
1. Úvod Herní um lá inteligence (dále AI - Artificial Intelligence) je v sou asné dob jedním z nejbou liv ji se rozvíjejících odv tví interaktivního zábavního pr myslu. Svébytný obor, který vznikl z programování her a herního designu, se v posledních letech za íná uplat ovat dokonce i p i akademickém výzkumu um lé inteligence. Až do druhé poloviny 90. let byla um lá inteligence v po íta ových hrách považována za okrajovou záležitost; herní vývojá i m li v tu dobu jinou prioritu – dokonalejší a realisti t jší grafiku. To se projevilo nejen ve velmi malém podílu na výkonu procesoru, který m la herní AI k dispozici, ale také ve sp chu a nekoncep nosti, se kterými byla AI do her na poslední chvíli implementována. Situace se za ala m nit až s rozmachem grafických akcelerátor na sklonku 90. let, jejichž nasazení výrazn odleh ilo hlavnímu procesoru, a uvolnilo tak výkon pro algoritmy um lé inteligence. Standardizace 3D grafických rozhraní a licencování herních engin pak dále vyrovnaly vizuální úrove po íta ových her. Herní vývojá i si pomalu za ali uv domovat, že atraktivitu hry už nelze stav t pouze na realistické grafice, a zam ili svou pozornost i na um lou inteligenci. 1.1. Bot Inteligentní agent ve h e nahrazující lidského protihrá e. Dnešní boti již umí bojovat velmi dob e ale není prblém je odlišit od lidského hrá e. Boti se se vyskytují v ak ních hrách typu Quake, Half-Life, CounterStrike, F.E.A.R. a dalších hrách podobn ho typu.
-3-
2. AI ve hrách (historie) Volfenstein V roce 1993 vydala firma id Software prvni 3D First person shooter (FPS) hru. Hrá musel procházet bludišt a ob as narazil na nep ítele - bota. Ten, pokud ho spat il, hrá e sledoval. Pokud se ale hrá dostal mimo dohled bota, bot se vrátil zp t na své místo. Quake Hra vydaná v roce 1996 taktéž od id Software již nabízela pln 3D prost edí. Hrá tak dostal v tší volnost p i pohybu a akci. Um lá inteligence ale moc velký skok neud lala. Novinkou bylo, že nep ítel reagoval na zvuk. Unreal Tuto hru vydala firma EPIC v roce 1998. Byla to první hra s boty, kte í zastávaly lidskou roli v multiplayerové h e. Boti používali k orientaci waypointy r zn rozmíst né po map . Díky tomu si dokázali najít skrýš i n jakou efektivní zbra . Half-Life V roce 1998 vydala tehdy neznámá firma Valve hru Half-Life. V této h e stojíte proti dv ma typu nep átel. Mimozemš an m a armád . Skupinka nep átel je schopna spolupracovat. Nap íklad jedna skupinka spustí palbu a druhá se sou asn p esune na jiné místo, hrá e schovaného za bednou rychle vyženou granáty nebo ho obklí í. Ochranka (hrá v spojenec) také úto í na nep ítele. Je zde ale nebezpe í, že poraní hrá e i jinou spojeneckou postavu, která se mu vyskytne ve sm ru st elby. Ochranka také moc nedbá na sv j život a nikdy neutíká z boje. Unreal Tournament Stejn jako ve h e Unreal zde boti používají waypointy. Jsou schopn jší a lépe napodobují lidské chování. Jsou schopni hrát i r zné varianty hry jako nap íklad Capture the Flag, Assault a Domination.
-4-
3. Prohledáví stavového prostoru (pathfinding) a waypointové sít Bot musí p edevším být schopen najít cestu do místa kam se chce p esunout. Pro ešení tohoto problému se používá tzv metoda pathfindind, která je založena na algoritmu heuristického prohedávání grafu. Jedním z algoritm , který najde optimální, ili nejkratší cestu, je algoritmus A-Star (A*). Pro jeho efektivní nasazení je pot eba k dané úrovni nejd íve zkonstruovat tzv. naviga ní sí , tedy graf, který popisuje odkud kam je možno se v dané úrovní dostat.
Waypointy ve h e Half-life. Uzly sít reprezentují topologicky významné body místnosti, plné hrany pak možnost p ímého pohybu mezi nimi. (Zdroj: Valve Corporation). Naviga ní sí m že obsahovat i speciální vlastnosti uzl jako nap íklad, kde je vhodn se bránit, i kde íhat na protivníka atd. Nevýhodou této sít je neschopnost reagovat na dynamické zm ny prost edí jako jsou nap íklad zatarasení cesty, probourání st ny atd. Proto se dnes objevuje snaha tvo it tyto sít automaticky pomocí nástroj um lé inteligence, ale to je velmi nelehký úkol. 3.1. Neinformované metody prohledávání stavového prostoru Tyto metody nemají žádné informace, které by jim urychlily nalezení cesty k cílovému uzlu. Musí tedy systematicky procházet všechny uzly. Breadth-first search (BFS) – Prohledávání do ší ky Depth-first search (DFS) – Prohledávání do hloubky Depth-limited search (DLS) – Prohledávání do hloubky s omezením Iterative deepening search (IDS) – Iterativní prohledávání do hloubky Bidirectional search – Obousm rné prohledávání 3.1.1. Breadth-First Search (BFS) Na za átku algoritmus expanduje startovní uzel a umístí ho do seznamu CLOSED. Poté do seznamu OPEN p i adí všechny nov nalezené uzly. Ty postupn op t expanduje (nalezne všechny potomky aktuálního expandovaného uzlu, kte í nejsou v CLOSED. Nalezené potomky umístí do seznamu OPEN), a p edává je do CLOSED. Algoritmus je úplný a optimální pokud se optimalizuje hloubka. Pseudokód begin open := [Start] while (_open <> []) do begin
-5-
X := first(_open) open := open - [X] if X = GOAL then return(SUCCESS) else begin E := expand(X) open := E + open end end return(failure) end. znak <> znamená nerovno operátor - znamená odebrání prvku/prvk ze seznamu operátor + znamená p i azení prvku/prvk nakonec seznamu CLOSED a OPEN jsou pole. Funkce EXPAND expanduje uzly v OPEN 3.2. Informované metody Tyto metody mají informace o stavovém prostoru, které ji umož ují odhadnout vzdálenost cíle od aktuálního uzlu. To jim m že urychlit nalezení cesty k cíli. Odhad reprezentuje tzv. heuristická funkce h(n). ím má heuristická funkce nižší hodnotu, tím spíše povede ešení skrz uzel n. Heuristickou funkci dodává na základ znalostí lov k. ím lepší heuristika je k dispozici, tím rychleji a s menším zatížením pam ti dojde k nalezení ešení. Prohledávání do ší ky up ednost ující „slibné“ stavy Greedy search - „Hladové“ prohledávání A* search – Algoritmus A* Lokální metody prohledávání Hill-climbing – Horolezecký algoritmus Simulated annealing - Simulované ochlazování 3.2.2. Algoritmus A-Star A Star algoritmus je úplný, vždy najde nejkratší cestu k cíli pokud n jaká existuje. Algoritmus na za átku startovní uzel umístí do seznamu OPEN a expanduje ho. Do seznamu OPEN umístí i nov nalezené uzly. Te je se startovním uzlem hotov a umístí ho do CLOSED (Seznam již expandovaných uzl ). Nyní se p i adí hodnota každému uzlu podle toho jak moc dobrý k nalezení cesty k cíli se zdá. P i výb ru nejlepšího stavu pro expanzi pracuje algoritmus s t mito hodnotami. c(m,n) – cena p echodu ze stavu m do stavu n. g(m) – celková cena, sou et všech operátor aplikovaných z po áte ního stavu do stavu m. h(n) – reálná nebo odhadovaná celková cena, sou et všech operátor , které je pot eba aplikovat ze stavu n do cílového stavu. K výberu nejlepšího uzlu slouží funkce Best(open), která najde pomocí heurické funkce nejlepší uzel k expandování ze seznamu OPEN a ten pak expanduje. Takto pak celý algoritmus postupuje, než najde cílový stav. f(n;m) = c(m; n)+g(m)+h(n) protože g(n) = g(m)+c(m; n), lze napsat f(n) = g(n) + h(n), kde argument m již neovliv uje hodnotu funkce. Hodnotu heuristické funkce h(n) je t eba odhadnout. Chceme aby byl odhad co nejp esn jší, aby hodnota h(n) byla co nejblíže hodnot h*(n). Hodnotící funkce f(n) je odhadem p esných hodnot, které vrátí funkce f*(n) = g*(n)+h*(n) kde g(n) = g*(n) (ve v tšin p ípad ) Aby se algoritmus choval rozumn , tudíž aby našel jako první optimální ešení, musí platit: Pro každé n: h(n) < h*(n) Je-li to pravda, íkáme, že heuristická funkce je p ípustná. A* algoritmus má vždy heuristickou
-6-
funkci p ípustnou. A* algoritmus vždy najde optimální ešení. Heuristická funkce je monotónní (lokáln p ípustná) platí-li 1) pro každé n1, n2, kde n1 expanduje do n2: h(n1) - h(n2)<=cost(n1,n2) kde c(n1,n2) opravdová cena z n1 do n2. 2) h(goal) = 0. Každá monotónní heuristická funkce p ípustná. Pseudokód 1. begin 2. open := [Start], closed := [] 3. while (open <> []) do begin 4. X := BEST(open) 5. closed := closed + [X], open := open - [X] 6. if X = GOAL then return(SUCCESS) 7. else begin 8. E := expand(X) 9. E := E - closed 10. open := open + E 11. end 12. end 13. return(failure) 14. end. Zlepšení pam ové náro nosti algoritmu A Star: IDA* - iterative deepening A* algoritmus. Zachovává optimalitu. Pracuje stejn jako IDDFS algoritmus. Místo omezení hloubky prohledávání algoritmus omezuje prohledávané v tve odhadem minimální hodnoty ohodnocovací funkce f. algoritmus za íná s omezením prohledávání na l = h(n0) p i každém kroku je omezení l funkcí nejen g ale i h omezení l lze p i každé iteraci zvýšit o více než o 1 1. l = 1 2. prove A* s f < flimit 3. if ešení nalezeno konec jinak flimit = min f(n), where n pat í do OpenList a jdi na 2 3.2.2. Dijkstr v algoritmus Algoritmus sloužící k nalezení nejkratší cesty v grafu. Je kone ný (pro jakýkoliv kone ný vstup algoritmus skon í), protože v každém pr chodu cyklu se do množiny navštívených uzl p idá práv jeden uzel, pr chod cyklem je tedy nejvýše tolik, kolik má graf vrchol . Funguje nad hranov kladn ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno p evést). Algoritmus poprvé popsal nizozemský informatik Edsker Dijkstra Popis algoritmu: M jme graf G, v n mž hledáme nejkratší cestu. ekn me, že V je množina všech vrchol grafu G a množina E obsahuje všechny hrany grafu G. Algoritmus pracuje tak, že si pro každý vrchol v z V pamatuje délku nejkratší cesty, kterou se k n mu dá dostat. Ozna me tuto hodnotu jako d[v]. Na za átku mají všechny vrcholy v hodnotu d[v]= , krom po áte ního vrcholu s, který má d[s]=0. Nekone no symbolizuje, že neznáme cestu k vrcholu.
-7-
Dále si algoritmus udržuje množiny Z a N, kde Z obsahuje už navštívené vrcholy a N dosud nenavštívené. Algoritmus pracuje v cyklu tak dlouho, dokud N není prázdná. V každém pr chodu cyklu se p idá jeden vrchol vmin z N do Z, a to takový, který má nejmenší hodnotu d[v] ze všech vrchol v z N. Pro každý vrchol u, do kterého vede hrana (ozna me její délku jako l(vmin,u)) z vmin, se provede následující operace: pokud (d[vmin] + l(vmin,u)) < d[u], pak do d[u] p i a hodnotu d[vmin] + l(vmin,u), jinak neprovád j nic. Až algoritmus skon í, potom pro každý vrchol v z V je délka jeho nejkratší cesty od po áte ního vrcholu s uložena v d[v]. Pseudokód 1 2 3 4 5 6 7 8 9 10 11 12 13
function Dijkstra(E, V, s): for each vertex v in E: // Inicializace d[v] := infinity // Zatím neznámá vzdálenost z s do v p[v] := undefined d[s] := 0 // Vzdálenost z s do s N := E // Všechny dosud nenavštívené vrcholy while N is not empty: // Samotný algoritmus u := extract_min(N) // Vezm me "nejlepší" vrchol for each neighbor v of u: alt = d[u] + l(u, v) if alt < d[v] d[v] := alt p[v] := u www.wikipedie.cz
3.3. Waypointové sít ve hrách 3.3.1. Quake 3 Ve h e Quake 3 se nepoužívají standartní waypointy ale tzv. Areas (1.3.1.3) a Reachabilties (1.3.1.4.). 3.3.1.1. Area Awareness System Systém v Quake 3 poskytuje botovi informace o r zných ástech sv ta. To zahrnuje informace o navigaci, cestování a dalších entitách v herním sv te. Srdce AAS je speciální 3D reprezentace prost edí. Všechny informace poskytované botovi jsou spojeny s 3D reprezentací prost edí. AAS používá k pathfindingu a routingu 3D spojené kostry, nazvané oblasti (areas), se speciální vlastností: složitost navigace mezi dosažitelnými body (waypointy) ve stejné oblasti je minimální. To znamená, že bot v Quake 3 se m že pohybovat mezi dv ma body pohybem po p ímce. Samoz ejm jenom tato znalost pohybu a navigace nám nedává všechny informace pot ebné pro navigaci. Proto jsou zavedeny tzv. reachability (dosažitelnosti). Reachability je vytvo ena z jedné oblasti do jiné, pokud se hrá m že mezi oblastmi p esouvat. 3.3.1.2. Areas Ke spln ní podmínky jednoduchosti navigace pomocí AAS musí být oblasti vytvo ené s minimální naviga ní složitostí. Tu to vlastnost má konvexní prostor. Konvexní prostory neobsahují p ekážky, které mohou navigaci ztížit. Pokud hrá prochází prostorem, konvexnost tohoto prostoru nemusí být vždy zaru ena (oblast m že obsahovat nap íklad propast). Proto se nekonvexní oblasti asto d lí na více konvexních oblastí.
-8-
3.3.1.3. Reachabilities Bot pot ebuje v d t jak se cestovat z jedné oblasti do druhé a jestli je to v bec možné. Proto jsou v Q3 zavedeny tzv. reachabilities (dosažitelnosti). N kolik druh dosažitelností. - Plavání po p ímce - Ch ze po p ímce - Plazení po p ímce - Skok na p ekážku - Pád z okraje - Skok z vody - Skok Uvedu p íklad n kterých z nich. Plavání po p ímce Pokud hrá m že ze startovní oblasti p eplavat do druhé oblasti, je vytvo ena swimming dosažitelnost. Ch ze a plazení po p ímce Pokud hrá mezi startovní a cílovou oblastí m že p echázet (oblasti jsou spojeny podlahou a není mezi nimi žádná propast ani p ekážka zabra ující ch zi) je vytvo ena walk dosažitelnost. Obdobn pak pro plazení. Další dosažitelnosti Prostor m, po kterých se m že hrá pohybovat, íkejme ground faces (GF). Dosažitelnosti mohou být zjišt ny za pomoci okraj t chto ground faces. P es okraje GF, které nejsou spojeny s další GF v jiné oblasti je vytvo ena svislá rovina (vertical plane). Nyní se vyhledají okraje GF z jiné (cílové) oblasti, které mají stejnou svislou rovinu. Pokud se najde stejná svislá rovina, vypo ítá se jejich nejkratší vzdálenost. Okraj p es který byla vytvo ena rovina ozna íme E1 a nalezený okraj ozna me E2. Na obrázcích vidíme 3 r zné situace.
Ve všech t ech p ípadech je nejkratší vzdálenost mezi E1 a E2 menší než maximální výška kroku a voda je moc m lká na plavání a tak se m že vytvo it walk reachability. V p ípad , že hrana E2 je výš než je maximální výška kroku se zkontroluje, zda bot na hranu E2 nem že vysko it. Pokud je vzdálenost mezi E1 a E2 menší než výška skoku je vytvo ena jump onto barrier reachability.
-9-
Obrázky ukazují p ípady kdy je vytvo ena jump onto barrier reachability. Hrana E2 m že být samoz ejm i níže než E1. Jestliže je E2 níž než maximální výška kroku vztažená k E1, je vytvo ena walk reachability jak je vid t na obrázku “Step down“. Jestliže je E2 výš než maximální výška kroku vztažená k E1 je vytvo ena walk off ledge reachability jak je vid t na obrázku “Ledge“ a “Ledge into water“.
Výskok z vody Hrá je schopen vysko it z vody, jestliže není b eh p íliš vysoko. Na obrázcích se oblast A1 nachází ve vod a A2 je na souši i je jen m lce zatopená.
Hladina vody je zde po ítán jako plocha na které lze stát. Takže se berou op t hrany E1 a E2 a eší se jump nebo walk reachability.
- 10 -
Skok Pokud je mezi startovní oblastí A1 a cílovou A2 propast, je nutné vytvo it jump reachability. Vytvá í se tak, že se najdou dva nejbližší body obou oblastí a pokud jsou blíže než je maximální délka skoku, tak se jump reachability vytvo í. Pokud je propast p íliš úzká i se jeden okraj nachází níž než druhý tak je možné místo jump reachability vytvo it walk off ledge reachability. Nevýhoda této metody vytvá ení reachabilit je asová složitost, která je O(n^2) (n je po et oblastí). Je to dáno tím, že by se s jednou danou oblastní m ly testovat všechny ostatní. Našt stí tomu tak není. Jako p íklad uvedu jump reachability. Pokud vezmeme maximální výšku skoku a maximální délku skoku, tak n které vzdálené a nedosažitelné oblasti m žeme p edem vy adit. Dosažitelnosti spolu s oblastmi vytvá í graf herního prostoru. 3.3.1.4. Princip algoritmu pro pathfinding v Quake 3 Konven ní routing algoritmy: Standartn jsou používaná A Star a Dijkstra, ale ve velkých herních prost edích jako je Quake 3 jsou Dijskr v a A Star algoritmus p íliš pomalý. Multi-Level algorithm: Tento algoritmus hledá cestu stejn jako konven ní algoritmy pro pathfinding ale pracuje rychleji. Uchovává si totiž v pam ti cesty k významným bod m ve h e a doby cestování do cílové oblasti. 3.3.2. Counter-Strike 3.3.2.1 Waypointy a jejich tvo ení Ve h e Counter-Strike hrá m že také hrát proti bot m. V jedné z verzí bot pro Counter-Strike (CS), POD-Bot, se waypointy d laly ru n . Hrá byl vsazen do hry a pomocí konzole dával do hry waypointy. Šlo o jednoduché p íkazy typu “waypoint add“ (vyvolal menu pro výb r druhu waypointu a ten se po vybrání umístil na místo kde hrá kle el i stál), dále zde byl p íkaz „autowaypoint on“, který automaticky p idával waypointy všude kudy hrá prošel (waypointy m li jistou minimální vzdálenost od sebe a automaticky se spojovali ty nejbližší (pokud se náhodou nespojili existuje zde p íkaz addpathwaypoint cislo_waypointu)). Po t chto waypointech pak bot náhodn b hal. Aby bot neb hal po ád dokola v malých prostorách byly zde i d ležit jší waypointy, tzv terrorist/counter terrorist important waypoints, které sloužili pro p esun bot po map (Hierarchicky byly important waypointy nad normal waypointy). Bot se p esouval po map mezi important waypointy. Dále následovaly goal waypointy, které ozna ovaly cíl hry (položit bombu, osvobodit rukojmí, místo kam utéct), camp waypointy, jump waypoint, ladder waypoint a rescue waypoint (v p ípad osvobození rukojmích ozna oval místo kam je dovést). Jump waypoint Byl pokládán tak, že hrá zvolil v menu tento waypoint, rozb hl se a sko il. V okamžiku kdy vysko il se vytvo il první jump waypoint. Tento waypoint se pak ru n musel speciální p íkazem “addpathwaypoint cislo_waypointu“ spojit s normálním waypointem, který pak ozna oval cíl skoku.
- 11 -
Jump waypoint – ervená spojnice zna í jednosm rnou spojnici vedoucí ke vzdálenému waypointu. Ladder waypoint Hrá si stoupl elem k žeb íku a z menu položil tento waypoint. Poté vylezl po žeb íku a naho e položil druhý waypoint. Tyto waypointy pak spojil.
Ladder waypoint Camp waypoint Hrá si klekl a položil první waypoint campstart waypoint, který zna il první sm r pohledu. Poté (stále v pokleku na stejném míst ) pouze zm nil sm r pohledu a položil waypoint campend waypoint. V praxi to pak vypadalo tak, že bot si klekl a pozoroval okolí vždy v rozmezí, které mu hrá sm rem pohledu ur il.
- 12 -
erven vyšrafovaná ást zna í oblast, kterou bot pozoruje. Tento styl vytvá ení waypointového systému je propracovan jší ale na druhou stranu je asov náro n jší. Vytvo ení waypoint ve v tší map zabralo tak 3-4 hodiny.
- 13 -
4.Finite state machine (FSM) Finite state machine (FSM) je systém s ur itým po et stav . Jakýkoliv systém, který má limitovaný po et stav , m že být modelován jako FSM. FSM jsou asto používány k simulaci lidského chování a myšlení. Jsou zde i jiné systémy k této simulaci, ale jednoduchost FSM jej iní populární. P i modelování chování bota zahrnují stavy FSM momentální chování bota (útok,obrana, p ebíjení, krytí....) a zm ny stav jsou vyvolávány na základ momentální situace ve h e (po et HP bota, po et protivník , po et náboj ,...)
Pseudokód: "bot"
state1 go_to_goal(guard1){ if (player_is_spotted) goto state2 } state2 attack(bot, player) { if (bot_is_dead)) stop else if(player_is_dead) goto state 1 }
P íklad znázor uje situaci kdy bot jde za cílem mise a narazí na hrá e. V ten okamžik se p epne do stavu 2 a zaúto í. Pokud hrá e porazí, pokra uje dál. Složit jší FSM, kdy se bot nerozhoduje jen ANO/NE ale na základ svého stavu i stavu okolí se nazývá Fuzzy FM a k rozhodování používá fuzzy logiku. Viz další kapitola Fuzzy logic.
- 14 -
5.Fuzzy logika Fuzzy logika je “nadmnožinou“ klasické Booleanovské logiky. Vezm me si p íklad klasické logiky. Máme množinu element S a každému elementu z S je p i azena hodnota z množiny {0,1}. Podmnožina U z množiny S je definovaná jako všechny elementy z S s p i azenou hodnotou ‘1’. Pak hodnotu elementu x z U lze p esn ur it. Pak hodnota 1 íká, že prvek leží v U a hodnota 0 naopak, že prvek neleí v U. Obdobn u Fuzzy logiky. Máme množinu S ale nyní mají její elementy p i azeny hodnoty z intervalu [0,1]. Podmnožina U není v tomto p ípad striktn definovaná. M žeme ale ur it “jak moc” element z S pat í do fuzzy podmnožiny U. Hodnota ‘0’, ktera je p i azena elementu x z S íká, že prvek neleží v U a naopak hodnota ‘1’ vyjad uje, že element je v podmnožin U. Hodnoty mezi nulou a jedni kou vyjad ují “st ední stupe lenství” elementu v U. 5.1 Využití fuzzy logiky Boti mohou používat fuzzy logiku k vyjád ení jak moc cht jí mít nebo d lat ur ité v ci. K tomu slouží tzv. fuzzy hodnota. Platí následující závislost: ím vyšší hodnota je, tím vyšší je pravd podobnost, že bot provede akci k níž se hodnota vzathuje. Fuzzy relations mohou vyjad ovat vztahy mezi r znými stavy bota a jak moc si bot tento stav žádá. P íklad založený na tom, jakou zbra bot drží v ruce. Podle po tu náboj , kolik do ní má, se odvíjí i fuzzy hodnota. ím mén náboj , tím více bot chce získat další. Fuzzy hodnota m že být použita v FSM jako rozhodovací faktor p i zm n stav . 5.1.1 Botovo rozhodování pomocí fuzzy logiky V Q3 se bot rozhoduje na základ fuzzy logiky a fuzzy hodnot jednotlivých aspekt . Nepoužívají se neuronové sít (4). Reprezentace fuzzy logiky v Q3 je pomocí stromové architektury kde listy stromu obsahují ur ité fuzzy hodnoty. Jeden list obsahuje jednu hodnotu pro jedno kritérium. K implementaci se používá stromová struktura. P íklad interpretace fuzzy logiky (z Quake 3) weight "name" { switch( /*one of the criteria*/ ) { case /*smaller than a certain value*/: { switch( /*one of the criteria*/ ) { case /*smaller than a certain value*/: return /*a fuzzy value*/; case /*smaller than a certain value*/: return /*a fuzzy value*/; default: return /*a fuzzy value*/; } } case /*smaller than a certain value*/: return /*a fuzzy value*/; case /*smaller than a certain value*/: return /*a fuzzy value*/; default: return /*a fuzzy value*/; } } Je n kolik výhod používání stromové struktury. Struktura je lehce pochopitelná. Fuzzy hodnoty a vztahy mohou být lehce vydedukovány. Fuzzy relation mohou být lehce interpretovány pomocí logického rozhodování a p edvídání r zných situací. Stromová struktura je lehce modifikovatelná. Nevýhoda je, že struktura dosahuje velké velikosti p i zpracování n jaké t žké situace. Pro rozhodování má bot implementovanou tzv item weight. Pro item weight je používaná práv fuzzy logika a fuzzy hodnoty. Hodnota vyjad uje pravd podobnost použití p edm tu.
- 15 -
weight "holdable_teleporter" { switch(INVENTORY_TELEPORTER) { case 1: { switch(INVENTORY_MEDKIT) { case 1: return 60; default: return 0; } } default: return 0; } } V p íkladu se p i adí item weight pro teleportér. P ípad, kdy INVENTORY_TELEPORTER má hodnotu 1 znamená, že hrá vlastní teleportér. INVENTORY_MEDKIT s hodnotou 1 znamená, že hrá vlastní medkit atd. Hrá m že držet práv jeden p edm t v ruce.Pro každý p edm t má bot jistý fuzzy vztah a preferuje ten s v tší váhou. weight "Lightning Gun" { switch(INVENTORY_LIGHTNING) { case 1: return 0; default: { switch(ENEMY_HORIZONTAL_DIST) { case 768: { switch(INVENTORY_LIGHTNINGAMMO) { case 1: return 0; case 50: return 70; case 100: return 77; case 200: return 80; default: return 80; } } case 800: return 0; default: return 0; } } } } Pseudokód výše ukazuje pravd podobnost s jakou bot použije v boji lightning gun. INVENTORY_LIGHTNING je 1, když má bot u sebe lightning gun. ENEMY_HORIZONTAL_DISTANCE je typu variable, která zna í vzdálenost od nep ítele. INVENTORY_LIGHTNINGAMMO je také typu variable a ukazuje po et náboj do lightning gunu. Lightning gun je použit, pokud ho bot má a pokud je nep ítel v dosahu. Dosah je 768 jednotek. Na základ po tu náboj , které bot má bude bot více i mén preferovat tuto zbra . Podle vztah výše pak m že nakreslit graf závislosti fuzzy váhy lightning gunu.
- 16 -
Fuzzy vztahy jsou po ítány pro každou zbra a bot si vybere tu s nejv tší fuzzy hodnotou. Rozsah fuzzy hodnot nemusí být jen [0, 1]. M že být i jiný, ale smysl má jen tehdy, když jsou hodnoty všech p em t a stav ze stejného intervalu.
- 17 -
6.Neuronové sít Neuronová sí je jedním z výpo etních model používaných v um lé inteligenci. Jejím vzorem je chování odpovídajících biologických struktur. Skládají se z neuron , které si navzájem p edávají signály a transformují je pomocí funkce pro p enos k dalším neuron m. Užívají se pro rozpoznávání a kompresi obraz nebo zvuk , p edvídání vývoje asových ad, n kdy dokonce k filtrování spamu Neuronové sít se používají k ešení problém , které jsou p íliš složité pro konven ní technologie (Ty, které nemají algoritmické ešení anebo jejichž algoritmické ešení je p íliš složité). Obecn e eno neuronové sít se používají pro problémy, jež lov k dokáže vy ešit “hlavou“ ale nedokáže je vy ešit programov . 6.1. Chování bota Boti využívají neuronové sít k uložení a používání ur itých znalostí. Stejn jako fuzzy logika se neuronové sít mohou používat k vyjád ení jak moc chce bot provád t ur itou akci. Neuronové sít mohou být natrénovány ješt p ed vlastní hrou a boti pak jen používají znalosti z báze znalostí (knowledge base). Lze ale trénovat i b hem hry. Je to ale asov náro né a u ící schopnosti a kapacita pam ti jsou omezeny. Counter-Strike Jakmile se na etla poprvé mapa, vytvo il se v té samé složce jako soubor s waypointy soubor s koncovkou pxp, do kterého se zapisovali r zné situace, na které bot narazil. Nap íklad hrá kempuje za bednou a bot probíhá okolo (obrázek). Bot si poprvé hrá e nevšimne a b ží stále rovn . Hrá ho celkem snadno porazí. Tato situace se zapsala do souboru pxp, a když bot b žel okolo bedny v dalším kole, zkontroloval zda tam hrá není.
- 18 -
7. Expertní systémy Expertní systémy jsou systémy, které ukládají lidské zkušenosti získané z tréninku a cvi ení. Systém má t i d ležité aspekty. Znalost fakt , znalost vztah mezi fakty a heuristiku nebo výkonnou metodu pro ukládání a získávání t chto znalostí. Konstrukce expertních systému se nazývá Knowledge engineering. Knowledge inženýr získává znalosti od expert v daném oboru a p episuje je do expertního systému. Logické systémy p edstavují dobrý nástroj k reprezentování a dedukování znalostí v expertním systému. K implementaci expertního systému se používají Production rules. Production rules mají strukturu IF (condition) THEN (action). Podmínka je logické vyjád ení faktu z knowledge base. Akce pak vytvá í i ruší fakta a spouští ur ité sekvence. P íklad Production rules: IF the bot is fighting AND the bot is low on health AND the bot does not have a powerful weapon THEN retreat from the fight. M žeme zde použít fuzzy logiku a nap íklad p idat pravdivostní hodnotu výrazu “low on health“ založenou na zdraví, které bot práv má. Obdobn m žeme p idat pravdivostní hodnotu výrazu “bot does not have a powerful weapon“ odvozenou od druhu zbran a po tu náboj . Celou podmínku m žeme zkrátit nap íklad spojením výraz “low on health“ a “bot does not have a powerful weapon“ do nového výrazu “the bot is not fit enough to fight”. Podmínka pak bude vypadat takto: : IF the bot is in a fight AND the bot is not fit enough to fight THEN retreat from the fight. Expertní systémy jsou používány k implementaci rozhodování bota. O ekávané lidské chování je uloženo v bází znalostí (knowledge base). Production rules se používají k vytvo ení nových fakt nebo k vyvolání ur itých akcí.
- 19 -
8.Genetický algoritmus Genetický algoritmus (GA) je heuristický postup, který se snaží aplikací princip evolu ní biologie nalézt ešení složitých problém , pro které neexistuje použitelný exaktní algoritmus. Genetické algoritmy, resp. všechny postupy pat ící mezi tzv. evolu ní algoritmy používají techniky napodobující evolu ní procesy známé z biologie – d di nost, mutace, p irozený výb r a k ížení – pro “šlecht ní“ ešení zadané. Princip práce genetického algoritmu je postupná tvorba generací r zných ešení daného problému. P i ešení se uchovává tzv. populace, jejíž každý jedinec p edstavuje jedno ešení daného problému. Jak populace probíhá evolucí, ešení se zlepšují. Tradi n je ešení reprezentováno binárními ísly, nicmén používají se i jiné reprezentace (strom, pole, matice, …). Typicky je na za átku simulace (v první generaci) populace složena z naprosto náhodných len . V p echodu do nové generace je pro každého jedince spo tena tzv. fitness funkce, která vyjad uje kvalitu ešení reprezentovaného tímto jedincem. Podle této kvality jsou stochasticky vybráni jedinci, kte í jsou modifikováni (pomocí mutací a k ížení), ímž vznikne nová populace. Tento postup se iterativn opakuje, ímž se kvalita ešení v populaci postupn vylepšuje. Algoritmus se obvykle zastaví p i dosažení posta ující kvality ešení, p ípadn po p edem dané dob . 8.1. Struktura algoritmu expertního systému 1. 2. 3.
4. 5. 6.
(Inicializace) Vytvo nultou populaci (obvykle složenou z náhodn vygenerovaných jedinc ) (Za átek cyklu) Pomocí ur ité výb rové metody (zpravidla z ásti náhodné) vyber z populace n kolik jedinc s vysokou zdatností Z vybraných jedinc vygeneruj nové použitím následujících metod (operátor ), ímž vznikne další generace: o k ížení - „proho “ ásti n kolika jedinc mezi sebou o mutace - náhodn zm ást jedince o reprodukce - kopíruj jedince beze zm ny Vypo ti zdatnost t chto nových jedinc (Konec cyklu) Pokud není spln na zastavovací podmínka, tak pokra uj od bodu 2 (Konec algoritmu) Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje nejlepší nalezené ešení.
8.2. Získávání zkušeností GA m že být použit pro skupinu bot , kde každý je n jak odlišný. Proces promíchávání lepších bot do nových jedinc a jejich nahrazování nov vzniklými boty se používá k lepšímu vývoji bot . Quake 3 - Po ur itém ase se mezi boty a jejich score (po et zabití/po et úmrtní) vytvo í ur itá propast (nap íklad bot1 má score 32/5 a bot2 score 4/10). Proto slabí boti d dí n které vlastnosti od t ch lepších a to tak, že se vezmou hodnoty vlastností 2 dobrých bot , ty se zk íží a tyto hodnoty pak dostane špatný bot. Toto vede ke zlepšování herního stylu bot . Tento postup se neustále opakuje.
- 20 -
9. Plánování Plánování eší jak se bot dostane na ur ité místo i jak se zachová v dané situaci. Je to posloupnost akcí, která zaru í, že se bot dostane z po áte ního stavu do stavu koncového. Plánování v ak ních po íta ových hrách je celkem novinkou a p elomová hra v tomto oboru byla FEAR. 9.1. Postup p i plánování Vybrat nejlepší pravidlo p íštího kroku za pomoci heuristiky. Aplikovat toto pravidlo a vypo ítat nový stav. Zkontrolovat, zda nový stav není zárove cílový. Vylou it špatné cesty. 9.2. Plánování se zásobníkem cíl a systém STRIPS (Standford Research Institute Problem Solver) Tento systém umí najít rozdílnosti mezi stavy a generovat pravidla dalších krok . Stavy jsou v systému STRIPS interpretovány množinou formulí predikátové logiky. Každý operátor má t i ásti. Seznam PRECONDITION (podmínka použití operátoru), seznam DELETE (seznam formulí, které mají být vypušt ny) a seznam ADD (seznam formulí, které mají být p idány) Uživatel zadá jen startovní množinu formulí, cílovou formuli a seznam operátor . Pokud je cílová formule ve startovní množin , je úloha ešitelná. STRIPS systém je spíše používán k pochopení teorie plánování. Prakticky se moc nepoužívá. 9.3. Nelineární plánování Pomocí tohoto plánování lze pracovat na více problémech sou asn . První programy používající nelineární programy byli NOAH A NONLIN. Tyto programy používali techniku p ídavných omezení. Hlavní myšlenka byla tvorba hypotetického plánu, složeného z elementárních posloupností operátor , kdy jsou kladena ur itá omezení na jejich po adí, a argumenty operátor se váží na konkrétní hodnoty, resp. množiny hodnot. P i nelineárním plánování se používá n kolik heuristických pravidel (kroky). Základní heuristická pravidla používané p i nelineárním plánování: P idání kroku P edsunutí - provede se vazba jednoho kroku na jiný takovým zp sobem, aby v kone ném plánu p edcházel kroku jinému. P izp sobení – mezi dva kroky se vloží pomocný krok. Ten zabezpe í spln ní p edpoklad druhého kroku, které byly porušeny prvním krokem. P i azení - p i adí se hodnota n jaké prom nné k zajišt ní p edpoklad pro uskute n ní n jakého kroku. Inhibice - zábrana v p i azení n kterých hodnot ur ité prom nné. T chto p t pravidel je dosta ujících pro ešení ešitelné úlohy. Pro využití modifikace plánu se pak používá tento algoritmus: 1. Inicializovat množinu výrok V, které popisují cílový stav. 2. Vybrat z ní n který nespln ný výrok P a odstranit ho z množiny výrok V. 3. Splnit P použitím modifika ních operací (p idání kroku, p edsunutí, p izp sobení, p i azení a inhibice) 4. Prozkoumat všechny kroky plánu (i ty zavedené v bod 3) a zjistit, které z jejich p edpoklad nejsou spln ny. Posléze nespln né p edpoklady p idáme do množiny V. 5. Pokud ješt není množina V prázdná, pokra ujeme bodem 2. 6. Nyní již dokon íme plán p evedením áste ného uspo ádání krok na úpln uspo ádanou posloupnost krok a je-li pot eba, inicializujeme všechny prom nné.
- 21 -
9.4. Hierarchické plánování Používá se pro ešení složitých problém . Systém musí být schopný eliminovat n které detaily úlohy do té doby, dokud není nalezeno ešení vztahující se na hlavní otázky. Nejlepší ešení p edstavuje systém ABSTRIPS, který vytvá í tzv. úrovn abstrakce. Požadavky z nižších abstrakcí jsou ignorovány. Každý požadavek je ohodnocen d ležitostí. ABSTRIPS preferuje požadavky s nejvyšší d ležitostí, vytvo í plán a poté se p esune o úrove níže. Takto pokra uje až k úrovni s nejnižší d ležitostí. Toto plánování bylo pojmenováno prohledávání do délky.
- 22 -
10. Entity Entity jsou všechny objekty ve h e jako nap íklad hrá , p edm ty, pohybující se objekty atd. Hrá i bot je v tšinou musí použít k úsp šnému p ekonání p ekážky (nap dve í) i k dokon ení hry (nap rukojmí ve h e Counter-Strike) 10.1. Entity a jejich používání v Q3 Informace o t chto entitách obsahuje AAS. Informace jsou uloženy pro pot eby bota a jsou vždy spojeny s n jakou oblastí. Entity jsou spojeny s oblastmi pomocí dvoudimenzionálního spojovacího seznamu jak je vid t na obrázku. Spojnice ur uje v jaké oblasti se entita nachází.
Pomocí tohoto seznamu se bot snadno orientuje a dostává se k entitám v oblastech a naopak (dostane se k oblasti kde je entita) 10.2. Entity a jejich používání v Counter-Strike V CS jsou entity pro boty ozna eny waypointy. Entity bych zde rozd lil do dvou skupin. Rukojmí a tla ítka. Rukojmí jsou ozna eny goal waypointem, ke kterému se bot (terorista) snaží dostat. Tla ítka jsou v CS velmi vzácnou entitou a v manuálu pro POD-Bot (jeden z mnoha druhu bot a jeden z nejlepších) jsem o používání entit jako jsou tla ítka nenašel ani slovo. Rozhodl jsem se tedy vyzkoušet, jestli zde boti v bec dokáží tla ítka používat. Poda ilo se mi tla ítka najít pouze ve t ech mapách (cs_arabstreet, cs_office a de_prodigy). V map cs_arabstreet entita zhasínala sv tlo a v ostatních mapách otevírala dve e. V prvních dvou mapách nebyly tyto entity boty v bec používány. V map cs_arabstreet m lo nepoužívání entity celkem zna ný význam. Entita sloužila ke zhasínání sv tla, což p inášelo bot m výhodu, jelikož vid li i ve tm . V map de_prodigy sice byla tato entita používaná a to tak, že se sta ilo k tla ítku p iblížit a dve e se otev ely (p ed tla ítkem je na podlaze umíst na neviditelná plocha, které spouští sekvenci pro otev ení dve í). ešení pomocí waypoint jsem v tomto p ípad nezjistil, jelikož z blízkého waypointu vedla spojnice sm rem na entitu (a pravd podobn i na waypoint) ale spojnice vedla do zdi. Nezjistil jsem tedy jaký waypoint je cílem. Cílový waypoint jsem nenašel, ani když jsem použil p íkaz “waypoint on noclip“, který mi umožnil procházet skrz zdi do neherního prostoru. Jiné ešení by bylo umístit p ed entitu normální walk waypoint.
- 23 -
Spojnice “nikam“ v map de_prodigy. V map cs_office bylo tla ítko, ke kterému hrá i bot museli p ijít a použít klávesu “use“, která pak aktivovala sekvenci k otev ení dve í. Vytvo il jsem proto novou jednoduchou sí waypoint od spawnu (startovní místo) k tla ítku a p ed n j jsem umístil goal waypoint. Bot bez problému b žel k tla ítku, použil ho a prob hl dve mi až k rescue waypointu (musí v map být jinak se waypointy neuloží stejn jako important terrorist/counter terrorist waypointy).
Mé ešení pomocí goal waypointy v map cs_office. Poznámka: Waypointy jsem umístil jen pro counter-teroristy a tudíž jsem neo ekával v prostoru protivníka (teroristu), jenže jak jsem umístil v blízkosti tla ítka i important terrorist waypoint, n kte í protivníci se k n mu dostali. Odpozoroval jsem, že ikdyž nemá bot okolo sebe normální walk waypointy (zelené) je schopen se dostat ke svému important waypointu ale jen je-li cesta k n mu p ímá. Na obrázku je znázorn na cesta ze spawnu k important waypointu bez walk waypoint .
Pohyb podél st ny v p ípad bota ze spawnu 1 je dán tím, že se p i pohybu eší zvláš sm r podle osy Y a podle osy X. V tomto p ípad se však bot pohybuje pouze ve sm ru X, protože ve sm ru Y mu v tom brání p ekážka. Ve druhém p ípad se bot k cíli nedostane protože uvízne v míst kde se nem že pohybovat ani sm rem X (-X) ani Y sm rem k cíli.
- 24 -
Záv r: Na modelováním situace v cs_office jsem došel k záv ru, že používání entit v CS lze za ídit pomocí waypoint a není tedy pot eba uchovávat speciální seznam entit jako je tomu v Q3.
- 25 -
11. Základní charaktery bot a akce používané boty Hrá obvykle hru ovládá pomocí klávesnice (pohyb, zm na zbraní, používání p edm t , st elba,...) a myši (st elba, sm r pohledu,...). Bot všechny tyto v ci ovládá pomocí programu. Zde však nastává problém. Teoreticky nap íklad hrá m že m nit sm r pohledu libovoln velkou rychlostí. V praxi je však omezen reakcí sval na rukou. Taktéž lidské reakce zpožd né. Myš má také svoje limity. Bot tyto omezení nemá a aby se bot chováním co nejvíce p iblížil lov ku, je nutné je implementovat. K vy ešení tohoto problému mají boti nastavené charakteristiky, které ovliv ují rychlost reakce, zm ny úhlu pohledu atd. 11.1. Charaktery bot Aby hra byla zábavn jší je ve hrách více druh bot s r znými charakteristikami, kte í hrají každý svým stylem. Každý druh bota má jiné herní vlastnosti (neherní vlastnosti jako nap íklad barva vlas se do charakteristiky nepo ítají). ím více vlastností bot má, tím je mén p edvídatelný. Avšak mnoho vlastností spolu souvisí a jiné si zase mohou odporovat. Jako p íklad m žeme uvést charakteristiky “jumper“ a “croucher“. Tyto vlastnosti vyjad ují pravd podobnost s jakou bot p i souboji bude skákat i se kr it aby se vyhnul projektil m, ale nem že d lat ob akce najednou. Pokud bychom nastavili jumper na vysokou úrove neznamená to ale, že bot bude celou dobu skákat. Je tu malá pravd podobnost, že se skr í. Charakteristiky by též m ly být nastaveny rozumn . Nap íklad vlastnost “camper“ nastavená na maximální hodnotu zp sobí, že bot bude v tšinu asu sed t n kde za bednou a nehne se z místa. 11.1.1. N které herní charakteristiky ovliv ující styl hraní bota v Q3 Attacking – ur uje jak dob e bot úto í > 0.0 & < 0.2 = bot se p i útoku nehýbe >= 0.2 & < 0.4 = hýbe se jen dop edu a dozadu >= 0.4 & < 1.0 = pohybuje se v kruzích > 0.7 & < 1.0 = pohybuje se náhodn > 0.3 & < 1.0 = st ílí po nep íteli a kryje se View Factor – rychlost zm ny úhlu pohledu Reaction Time – spožd ní botovi reakce Aim Accuracy – p esnost p i st elb nabývající hodnot v intervalu 0 (nep esný) až 1 (vždy zasáhne nep ítele) Aim Skill – jak dob e bot mí í > 0.0 & < 0.9 = mí ení je ovlivn no pohybem > 0.4 & <= 0.8 = mí í na pohyblivý cíl > 0.8 & <= 1.0 = zam ova p esn kopíruje nep ítel v pohyb > 0.6 & <= 1.0 = st íli výbošné náboje i okolo nep ítele (výbuch ho zraní) > 0.5 & <= 1.0 = st elba i když hrá e nevidí (ale o ekává ho) Croucher – tendence se kr it Jumper – tendence skákat Walker – tendence chodit pomaleji a nehlu n Aggresion – agresivita Self Preservation – sebezáchova Vengefulness – tendence se pomstít Camper – tendence kempovat Alertness – pozornost Fire Throttle – tendence neustálého st ílení místo st ílení po jednom náboji (p estávka mezi jednotlivými výst ely zp sobuje lepší p esnost) 11.1.2. Charakteristiky bot v CS V Pod-Bot jsou základní t i druhy bot . Agresivní (P*D), který si ned lá starosti s tím že vydává hluk a v bec se nekryje, Defenzivní (P0B), který zase ast ji kempí, chodí potichu a p i p est elkách se drží v ústraní. Poslední typ je normální (POD), který kombinuje vlastnosti obou p edchozích typ . Dále se dají n které vlastnosti nastavit v konfigura ním souboru Podbot.cfg. Uvedu p íklady.
- 26 -
pb_minbotskill (value) – nastaví minimální skill bot v rozmezí 1-100 (defaultní hodnota je 1) pb_maxbotskill (value) – nastaví maximální skill bot v rozmezí 1-100 pb_shootthruwalls (1|0) – tato hodnota ur uje zda boti st ílí skrz zdi a bedny (v tšina st n a p edm t je ve h e pr st elná) – defaultní hodnota je 1 (bot ur í sm r st elby podle hluku vydávané nep ítelem) pb_maxcamptime (value) – hodnota vyjad uje maximální dobu kempení bot Pozn. V nov jších verzích (1.6 a Source) se vlastnosti bot ur ují zvolením obtížnosti hry (easy, normal, hard a expert). Zde uvedené p íklady chování a reakcí bot jsou mnou odpozorované. Easy – Bot má pomalé reakce, p i st elb v tšinou stojí, st ílí bez prodlevy a málokdy se trefí do stojícího nep ítele Normal – Reakce jsou rychlejší (zpožd ní je cca 1 vte ina), p i palb stojí i kle í, v tšinou st ílí bez prodlevy, stojícího nep ítele zasáhne, s pohybujícím má problémy. Hard – Velmi rychlá reakce, p i palb v tšinou kle í, ale pokud je nep ítel p íliš blízko, krouží okolo n j, mezi výst ely asto nechává asovou prodlevu (lepší p esnost), trefí i pohybující se cíl. Expert – Okamžitá reakce, p i st elb b há a snaží se vyhnout kulkám, kryje se, mezi výst ely nechává asovou prodlevu, trefí i pohybující se ter . 11.2. Základní akce, které m že bot provád t – v závorkách uvedeny rozdíly mezi Q3 a CS Attack – zaúto í na protihrá e Use – použije n jakou entitu Respawn – po smrti se bot p esune na startovní místo (V Q3 se respawne náhodn na map a respawn je ihned po smrti, v CS je naopak respawn umíst n v jedné oblasti a nastane až na konci kola (spln n cíl mapy i zem ou všichni hrá i z jedné strany)) Jump – bot vysko í Crouch – bot se skr í Move Forward – bot se za ne pohybovat vp ed ve sm ru, kterým se kouká Move Back – bot se za ne pohybovat v opa ném sm ru než p i Move Forward Move Up – p i plavání za ne bot plavat nahoru Move Back – p i plavání za ne bot plavat sm rem dol Move Left – bot se pohybuje úkroky doleva Move Right – bot se pohybuje úkroky doprava Talk – bat napíše n co do chatu. (V Q3 se bot p i této akci nehýbe zatímco v CS bot chatuje jen když zem e) Walk – bot neb ží ale jde Gesture – p i užití této akce bot provede n jakou speciální animaci svého modelu (V CS tato akce není) Move – tato akce má dva parametry – rychlost a sm r. Když bot provádí tuto akce tak se pohne jistým sm rem a rychlostí View – zm ní úhel pohledu Select Weapon – bot si vybere zbra , kterou bude používat (V Q3 se zbran jen sbírají a hrá /bot tak m že mít všechny zbran zatímco v CS se zbran kupují a m žete mít u sebe jen n ž, secondary weapon (pistole) a primary weapon (ú inn jší zbra ). Bot se tedy rozhoduje jakou zbra koupit a p ípadn jestli zbra vyhodit, sebrat i vym nit za jinou ze zem .) Say – bot slovn zhodnotí situaci ve h e. Say Team – to samé jako say, ale ekne to jen hrá m svého teamu.
- 27 -
12. P ekážky a skláda ky Ve hrách se ob as vyskytují r zné p ekážky (dve e) i skláda ky (tla ítko otvírající dve e). 12.1.
ešení v Quake 3
Na obrázku je znázorn na situace, kdy se bot ( ervená krychli ka) snaží dostat p edm t (modrá krychli ka). B1, b2, b3 a b4 jsou m íže, t1 je tla ítko, které lze spustit výst elem do n j a t2 až t8 jsou standartní tla ítka. T2 a t6 otvírají b1, t1 a t5 otvírají b4, t3 a t7 otvírají b2 a t4 a t8 otvírají b3. M íže z stávají otev eny po dobu 4 sekund. Spína a m íže, které otvírá jsou programov spojeny a bot je schopen tuto spojnici nalézt. V p ípad že jsou m íže sou ástí AAS, bot si uv domuje existenci m íží a jde rovnou k tla ítku, to spustí a pokra uje dál. Pokud ale m íže nejsou sou ástí AAS, bot nejprve jde a narazí do nich. Poté zjistí informaci o tla ítku, které m íže otevírá, a jde ho nalézt a spustit. Bot bude ešit hádanku takto. P jde k p edm tu, který chce získat ale narazí do m íží. Zjistí, že m íže otevírá tla ítko t3 a tuto informaci si uloží do pam ti. Získá informace o tla ítku t3 a vydá se za ním. Op t ale narazí do m íží. Op t vyhledá informace o tla ítku, které je otevírá a jde k n mu. Takto pokra uje až k tla ítku t1 (všechny informace o tla ítkách a m ížích ukládá) a spustí ho. Ví, že to otev e m íže b1, kde je další tla ítko. Takhle pak te z pam ti postupn ostatní informace až se dostane k cíli. Tento zp sob ale nevypadá p íliš inteligentn . eší se to tedy tak, že bot má informace o skládance v pam ti už p edem. Poté m že situaci dokonale p edvídat a jde rovnou za cílem.
- 28 -
12.2. Návrh ešení situace pomocí waypoint
Na obrázku je m j návrh na ešení hádanky pomocí waypoint . Shot waypoint má podobnou strukturu jako camp waypoint s tím rozdílem, že se p i pokládání udává jen jeden waypoint a ten zna í sm r st elby. Goal waypointy bot prochází podle íselného po adí. Aby bot stihl projít do další místnosti, byla by pot eba podmínka typu “bot_puzzle“ if (current_node == goal 2 && there_are_no_enemies(enemy) go_to_waypoint (goal3); else if (there_are_no_enemies(enemy)) go_to_waypoint(goal2); else attack(enemy);
- 29 -
13. Chat B hem hry ob as bot n co “ ekne“ do chatu nebo p ímo do hry reaguje na zm nu prost edí. Reakce na zm nu situace jsou asto jen slovní spojení a jejich použití a implementace není složité. P íklad, kdy bot zahlédne nep ítele: “Enemy spotted“ if (bot_is_in_good_condition(bot_name,bot_health) ) say(enemy_spotted); else say(taking_fire_need_assistance); V chatu se naopak vyskytují celé v ty a ty na sebe navazují. Implementace chatu je o mnoho obtížn jší. Bot musí zpráv rozum t a adekvátn na ni odpov d t. K tomu se používají hlavn synonyma. Pomocí synonym si bot p evede v tu na základní tvar (první synonyma v listu). Ty jsou uloženy v n jakém textovém souboru ve formátu context flag { [("word", X), ("a synonym of word", Y), ...] ... } X a Y mají hodnoty v intervalu od 0 do 1. Nula znamená, že bot p i vytvá ení zprávy nikdy toto synonymum nepoužije. CONTEXT_NEARBYITEM { [("Heavy Armor", 0), ("red armor", 0), ("Heavy Armour", 0), ("red armour", 0), ("ra", 0)] } CONTEXT_NORMAL { [("do not", 1), ("don' t", 1), ("dont", 0)] [("checkpoint", 1), ("check-point", 1), ("cp", 0)] } 13.1. Textové šablony P i skládání zprávy bot používá šablony v t. Šablona obsahuje fixní a prom nné stringy, které se odd lují árkami. Nap íklad “You are“, 0 , “don’t you think?“ kde na míst 0 m že být více druh slov. Znak | íká, že na míst fixního stringu m že být práv jedna možnost. P íklad “I am“, “team“|“squad“|““,“leader.“ Výsledkem pak m žou být v ty „I am team leader.“, „I am squad leader.“ a „I am leader.“. 13.2. Eliza Na odpov di ostatním hrá m bot používá tzv. reply chats. Funguje to podobn jako Eliza chat program. Tento program vyvinul Joseph Weizenbaum a simuluje rozhovor mezi psychiatrem a pacientem Je to jeden z prvních po íta ových program simulace konverzace. Program hraje roli psychiatra a lov k roli pacienta. Eliza má pouze omezené znalosti. Je schopna bavit se jen o cca 200 tématech. Její pam není velká a neuchovává tedy mnoho informací, které jí lov k sd lí. P esto je tento program vyjíme ný, protože Eliza má jakousi osobnost. Jedním ze základních trik , který Eliza používá je mapování slov. Nap íklad „My“ mapuje na „Your“ nebo „Me“ na „You“. Dále, když uživatel použije podstatné jméno X ve v t , Eliza vše p ed X vynechá. Nap íklad „I need X“ Eliza zpracuje jako "What would it mean to you if you got some X?" a nezáleží na tom zda X je pomoc, jídlo, pití i jiné podstatné jméno. V tšina odpov dí je tohoto typu.
- 30 -
Dnešní podobné programy jsou komplexn jší a umí reagovat na 40 000 témat. Jako p íklad uvedu program A.L.I.C.E a GOD. K chatování bot ve h e však posta í menší množství témat k hovoru. P íklad rozhovoru mezi Elizou (R) a lov kem (C) C: Well, my boyfriend made me come here. R: Your boyfriend made you come here. C: I am unhappy. R: Do you think coming here will help you not to be unhappy? C: I need some help, that much seems certain. R: What would it mean to you if you got some help? C: Perhaps I could learn to get along with my mother. R: Tell me more about your family. C: You are like my father in some ways. R: What resemblance do you see? C: My father is afraid of everybody. R: What else comes to mind when you think of your father. C: Bullies. R: Does that have anything to with the fact that your boyfriend made you come here? 13.3. Zahájení chatu Ob as bot písemn zhodnotí herní situaci. Nap íklad, když zem e ekne: „You are good shooter.“ A ob as dokonce i odpoví na jednoduchou v tu jako nap íklad, když se napíše „You are good.“, bot m že odpov d t n co ve smyslu „I am not that good.“. Zahájení chatu Každý bot má nadefinovaný seznam úvodních v t v chatu. chat
{ type "type name" { "initial chat message"; "another initial chat message"; ... } type "type name" { } ... }
13.4. Odpov di Boti mívají nadefinované stejné odpov di. Kdyby m l každý charakter nadefinované jiné odpov di, jejich po et by musel být neskute n velký aby dohromady v chatu dávaly smysl. Každá odpov má klí e, prioritu a pár možných text odpov dí. [key1, key2, ...] = priority { "reply chat message"; "another reply chat message"; ... } Klí e:
- 31 -
Name – klí je true, když je jméno bota nalezeno ve zpráv . Female – true, když je bot ženského pohlaví. Male – true, když je bot mužského pohlaví. It – true, když bot není ani muž ani žena (Jde nap íklad o robota). <"",""> - true, když se jméno bota vyskytuje v seznamu. "" – true, když je text v uvozovkách obsažen i ve v t , na kterou odpovídá. ( ) – true, když v ta na kterou odpovídá, odpovídá šablon v závorkách. . P íklad: [("I' m not ", 0)] = 4 { "yes you are ", 0; } Prioritní hodnota (4) je vztažená i k prioritním hodnotám ostatních odpov dí. Bot vyhodnotí klí e aby zjistil, zda m že odpov d t na n jakou ze zpráv. Klí e mohou být uvozovány znaky & a !. Znak & znamená, že klí je true a !, že false. ["hate you", !"not"] = 7 { "why do you hate me"; "there' s no reason for you to hate me"; } V ta kterou bot ekl, je „I Hate you.“ 13.5. Random strings Random strings jsou používaný jak p i zahajování chatu tak i p i odpov dích. P ináší do chatu variabilnost. Slova jsou ukládány tímto zp sobem. rndname = {"first random string"; "second random string"; ...} a používají se takto “part of message“, rndname, “part of message“; P íklady random string : ferrari = {"F40"; "F50"} BMW = {"BMW Z3"; "BMW Z8"} cars = {ferrari; BMW; "F1 Mc Laren"} 13.6. D vody chatování Bot se rozhoduje, jakou v tu napsat, pomocí následujícího pseudokódu. if environmental change then if bot wants to chat then choose initial chat use random strings in chat message replace synonyms in chat message to add variation output chat message endif endif
- 32 -
Pojem environmental change obsahuje t eba situaci., kdy bot za íná nebo kon í se hrou, když vyhraje/ prohraje, hra se mu líbí atd. Bot se také rozhoduje, zda je vhodná situace k chatování a na jakou v tu p ípadn odpov d t. V Q3 bot p i chatování stojí a tak hodnotí herní situaci, zda je vhodn jší psát a nebo nap íklad úto it. V CS bot chatuje pouze, když je poražen a eká na respawn. Pseudokód vyjad uje rozhodování bota, na kterou v tu odpov d t. Nap ed se bot snaží porozum t zpráv srovnáním synonym a hledáním šablon. Jestliže nalezne šablonu, tak odpoví. Pokud ale bot zpráv od hrá e nerozumí (bot botovi by m l rozum t, protože všichni používají stejné šablony), napíše zprávu podobnou t m, které používá Eliza (Tell me more..., What is your problem?, Why do you say it?, .....) if bot receives a message then replace synonyms in the message interpret message using match templates if match is found then perform action else if messages is a chat message from another player then if bot wants to reply to this message then find a reply chat use random strings in chat message replace synonyms in chat message to add variation output chat message endif endif endif endif
- 33 -
14. Použité zdroje [1] Um lá inteligence, Hashim Habiballa, Ostrava, 2004 [2] Artificial Intelligence in Games http://aigamedev.com/ [3] Game AI in Delta3D http://www.nps.navy.mil/cs/cjdarken/cjdarken-cig07-final-v2.pdf [4] Science world www.scienceworld.cz [5] AI Depot http://ai-depot.com/ [6] The Quake 3 Arena Bot http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf [7] Dokumentace k programu POD-Bot [8] GameAI http://www.gameai.com/ [9] POD-Bot v2.0 – recenze http://games.tiscali.cz/specials/cspodbot20/index.asp [10] Homepage ELIZA chat bot http://www.alicebot.org/anatomy.html [11] Chat s ELIZA botem http://nlp-addiction.com/eliza/ [12] Chat s ALICE botem http://www.pandorabots.com/pandora/talk?botid=f5d922d97e345aa1 [13] Chat s GOD botem http://alicebot.org/igod/ [14] Internetová encyklopedie Wikipedie http://cs.wikipedia.org/
- 34 -
