AI TESTER
Uživatelská příručka
AI Tester 1.1 AI Tester Server 0.9
(C) 2010 Tomáš Hubík
Obsah Obsah
2
1 Úvod
4
2 AI Tester
5
2.1
Herní 2.1.1 2.1.2 2.1.3 2.1.4
prostředí . . . Hrací pole . . Typy jednotek Akce ve hře . Pravidla hry .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
5 5 7 8 9
2.2
Parametry a nastavení platformy 2.2.1 parameters.ait . . . . . . . 2.2.2 unit types.ait . . . . . . . 2.2.3 Bonusy . . . . . . . . . . . 2.2.4 Herní plán . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
10 10 12 12 13
2.3
Ovládání . . . . . . . . 2.3.1 Local Game . . 2.3.2 Network Game 2.3.3 Replay . . . . . 2.3.4 Test Algorithms 2.3.5 About Qt . . . 2.3.6 About . . . . . 2.3.7 Exit . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
14 14 20 22 23 25 25 25
2.4
Algoritmy umělé inteligence . . . . . . . . . . . . . . . . . .
25
. . . . . . . .
. . . . .
. . . . . . . .
. . . . .
. . . . . . . .
2
. . . . .
. . . . . . . .
. . . . .
. . . . . . . .
. . . . . . . .
2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6 2.4.7
Herní stav . . . . . . . . . . Vytváření nového algoritmu Reflex algorithm . . . . . . Search algorithm . . . . . . Search algorithm MT . . . . Monte Carlo algorithm . . . Monte Carlo algorithm MT
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
3 AI Tester Server 3.1
Ovládání . . . . . . 3.1.1 Start Server 3.1.2 About Qt . 3.1.3 About . . . 3.1.4 Exit . . . .
25 27 29 29 29 29 29 30
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
4 Zdrojové kódy
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
30 30 31 31 31 34
3
Kapitola 1 Úvod Platforma je učena pro testování jednotlivých algoritmů a metod přístupu k implementaci umělé inteligence. Hra, na které se testuje, je inspirována běžnými strategickými tahovými hrami. Pravidla jsou co nejjednodušší, aby zbytečně nezatěžovala implementaci jednotlivých algoritmů nepotřebnými detaily. Zároveň jsou pravidla dostatečně složitá, aby se na nich daly demonstrovat výhody a nevýhody jednotlivých algoritmů v různých situacích. Mimo to je možné hru hrát v několika módech. • Člověk vs. Člověk • Člověk vs. Algoritmus • Algoritmus vs. Algoritmus A pak ještě všechny tyto kombinace přes síťové rozhraní s pomocí aplikace AI Tester Sever.
4
Kapitola 2 AI Tester AI Tester je klient a hlavní část této platformy. Obsahuje veškerou herní logiku a je to plně autonomní jednotka schopná fungovat bez serveru (s výjimkou síťové hry). Nyní si popíšeme prostředí a pravidla hry.
2.1
Herní prostředí
Herní prostředí se skládá z hracího pole a objektů na něm. Existují dva druhy objektů — jednotky a bonusy. Každý objekt má na mapě své místo, které nesdílí s žádným jiným objektem. Hráč pak může ovládat své jednotky podobně, jako by ovládal figurky v šachách. Jednota je tedy jediná entita, se kterou může ve hře hráč manipulovat a tvořit tak herní strategii.
2.1.1
Hrací pole
Hrací pole je tvořené dvourozměrnou mapou, která reprezentuje terén. Celá je rozdělena na dlaždice umístěné do čtvercové sítě. Každý objekt ve hře je na právě jedné dlaždici herního pole. Existují tři druhy dlaždic: Země Země je jediný druh dlaždic, na kterém se mohou vyskytovat objekty. Můžeme se po ní pohybovat i střílet. Tento typ dlaždic se dále dělí na deset druhů podle ceny pohybu po nich. Na mapě je znázorněna zelenou barvou, a čím dražší je po dlaždici pohyb, tím je odstín zelené tmavší.
5
Voda Tento druh dlaždic slouží pouze jako překážka pro pohyb. Nemohou se na ní ani vyskytovat žádné objekty. Střelba je ovšem přes vodu možná a na mapě je znázorněna modrou barvou. Zeď Zeď je překážka. Nelze přes ni ani střílet, ani chodit a ani se na ní nemohou vyskytovat žádné objekty. Na mapě je tento druh dlaždice znázorněn hnědou barvou. Obrázek 2.1 ukazuje příklad hracího pole s jednotkami.
Obrázek 2.1: Ukázka hracího pole s jednotkami
6
2.1.2
Typy jednotek
Zde si popíšeme typy objektů, se kterými se můžeme ve hře setkat. Unit Prvním objektem je objekt typu unit, neboli jednotka. Je to objekt, který se používá ve hře k boji. Každá jednotka má svého majitele a ten ji ovládá. Jednotka se může po mapě pohybovat nebo střílet na ostatní nepřátelské jednotky. Jednotky mají množství parametrů, kterými se liší: Cena Počet bodů, který musí hráč zaplatit při zakoupení této jednotky. Dostřel Počet políček, jak daleko jednotka dostřelí. Vzdálenost se počítá jako úhlopříčka čtyřúhelníku se svislými a vodorovnými stranami určeného dvěma body — útočící jednotkou a jednotkou, na kterou je útočeno. Zdraví Počet bodů zdraví nám určuje kondici jednotky. Každý typ jednotky má různou počáteční hodnotu tohoto parametru a tato hodnota se zmenšuje s každým zásahem od nepřátelské jednotky. Když tento parametr klesne na nulu, jednotka je zničena a odstraněna z mapy. Štít Tento parametr určuje odolnost jednotky před zásahy nepřítelem. Čím větší je to číslo, tím je jednotka odolnější. Při zásahu nepřítelem se od celkového počtu bodů zdraví, který by měl jednotce ubrat, odečte právě tato hodnota, a až výsledný počet se skutečně odečte. Ovšem nejmenší počet bodů, který zásah může ubrat, je jeden bod. Tedy, i kdyby po odečtení štítu vyšlo záporné číslo, bude jednotce ubrán od zdraví jeden bod. Štít se v průběhu hry nijak nemění (s výjimkou změny nějakým bonusem, kdyby takový existoval). Zbraň Parametr „zbraň” určuje, kolik by jednotka ubrala jiné jednotce bodů ze zraví, kdyby ji zasáhla a zasažená jednotka by neměla žádný štít. Cena pohybu Počet akčních bodů, který hráče stojí posunout jednotkou o jedno políčko, na kterém je pohyb nejlevnější. Tedy cena pohybu po prvním typu země.
7
Cena střelby Počet akčních bodů, který hráče stojí jeden výstřel s jednotkou. Cena je stálá bez ohledu na vzdálenost cíle. Bonus Dalším typem objektu je bonus. Je to speciální typ objektu, který nějakým způsobem ovlivní buď jednotku, nebo celého hráče. Aktivuje se vstoupením jednotky na políčko s bonusem. Bonusy jsou statické, nemohou se pohybovat. Po aktivaci se uplatní jejich efekt, a pak bonus zaniká. Ve hře je pouze jeden implementovaný bonus, a to First Aid Kit, tedy lékárnička, která jednotce, jež ji aktivovala, přidá 50 bodů ke zdraví.
2.1.3
Akce ve hře
Ve hře je 6 možných akcí, které může hráč vykonávat. Tři jsou pro část hry, kde se kupují jednotky a tři pro bojovou část (části jsou podrobněji popsány v kapitole 2.1.4). Nákup jednotek Nákup První možná akce, kterou může hráč ve hře udělat je tato. Nakupují a umisťují se s ní jednotky, které si hráč vybírá z předem daného seznamu všech jednotek. Prodej Další akcí je prodej jednotek. Tato akce prodá danou jednotku, tedy odstraní ji z mapy, a vrátí hráči počet bodů odpovídající její hodnotě. Používá se v případě, že se v průběhu kupování jednotek hráč spletl, nebo si rozmyslel strategii. Konec nákupu Tato akce se použije, když má hráč již jednotky nakoupené, rozmístěné a připravené k boji. Po provedení této akce jde na řadu s nákupem následující hráč. Až poslední hráč nakoupí jednotky, hra přechází do bojové části. Bojová část Pohyb Příkaz pohyb slouží k přemístění jednotky z jednoho místa na druhé.
8
Útok Tato akce se používá, když chce hráč zaútočit svojí jednotkou na nějakou nepřátelskou jednotku. Konec tahu Poslední akce ukončuje hráčův tah. Když hráč již nechce dělat žádná další rozhodnutí, nebo na ně nemá dostatečný počet akčních bodů, použije tento příkaz.
2.1.4
Pravidla hry
Hra má poměrně jednoduchá pravidla. Jedná se o hru 2 až 9 hráčů, kde hraje každý proti každému. Celá hra se dělí na dvě části. První je výběr a nákup jednotek, druhá je pak samotná bojová část. Každá z těchto částí má jiná pravidla. V každé části hry se hráči střídají postupně a v jednu chvíli může hrát pouze jeden. Části hry mezi začátkem a koncem hry jednoho hráče říkáme tah. Nákup jednotek Nákup jednotek probíhá jednoduše. Každá jednotka má svoji cenu a většinou lepší jednotka je dražší. Každý hráč na začátku dostane určitý počet bodů, za které si vybere jednotky. Hráči mají na mapě svá políčka, na která zakoupené jednotky umístí. Žádní dva hráči nesdílí stejné políčko, umístění takových políček je součástí mapy a jsou na ni vázána. V průběhu nákupu jednotek vidí každý hráč políčka všech hráčů. Tedy kromě svých i ta, na která budou moci umístit své jednotky ostatní hráči, ale žádný hráč v této fázi nevidí, jaké jednotky kdo koupil a kam je umístil. Bojová část Tato část je hlavní částí celé platformy. Každý hráč má již své jednotky nakoupené a umístěné na hracím poli. Na hracím poli taktéž mohou být i bonusy. Celá hra se dělí na tahy, kdy v jednom tahu hraje pouze jeden hráč. Každý má veškeré informace o celém dění na hracím poli, včetně všech jednotek a jejich parametrů. Na začátku každého tahu dostane každý hráč akční body, které může utratit v průběhu tahu za jednotlivé akce. Hráč může dělat pouze ty akce, na které má dostatek bodů. Útočit může hráč pouze na nepřátelské jednotky. Vlastní jednotky tedy zničit nemůže. Při střelbě nesmí být v dráze žádná zeď, ani jakákoliv jiná jednotka. Vyhodnocení trajektorie střely probíhá pomocí spojnice útočníka 9
a cíle, přičemž spojnice nesmí procházet skrz žádnou zeď, nebo jednotku. Není možné střílet ani mezi zdmi, které se dotýkají pouze rohem, protože dráha letu se vyhodnocuje jako spojitá plocha, kde se políčka trajektorie musí dotýkat celou stranou. Pohyb je umožněn do čtyř stran – nahoru, dolu, doleva a doprava, přičemž není omezen pouze pohybem o jedno políčko, ale může jít i o několik políček najednou, kde výsledný stav je stejný, jako kdyby se pohyb složil z jednotlivých kroků. V případě, že je na cestě cizí jednotka, nelze jít přes ni — musí se obejít. Aplikace se sama stará o hledání nejkratší cesty mezi dvěma body, přičemž respektuje daná pravidla. V případě, že je na cestě bonus, nebude pouhým průchodem aktivován. K jeho aktivaci je třeba se na něm zastavit. Vyhrává hráč, který jako první zničí všechny jednotky všech ostatních hráčů. Obecná pravidla Žádný hráč nemůže vlastnit více jednotek, než kolik by si dokázal koupit. Dále se počet jednotek, které vlastní jeden hráč, dá omezit pomocí parametrů.
2.2
Parametry a nastavení platformy
Celá platforma se dá z velké části nastavovat pomocí dvou externích souborů s parametry a typy jednotek. Jedná se o soubory parameters.ait a unit types.ait.
2.2.1
parameters.ait
V tomto souboru jsou uloženy parametry platformy včetně parametrů všech algoritmů umělé inteligence a jsou automaticky načteny při spuštění programu. Komentář se v souboru označuje znakem ’#’ na začátku řádku. Dále jsou řádky s jednotlivými parametry ve tvaru: „
”, kde hodnota parametru je celé číslo. Výjimku tvoří kategorie pro parametry umělé inteligence. Zde je tvar řádku následující: „AI
10
(ALGORITMU)> ” a hodnota parametru je zde číslo reálné. Při chybě načítání parametrů bude uživatel upozorněn chybovou hláškou a aplikace se ukončí. Parametry jsou v souboru rozděleny do čtyř kategorií. AI Tato kategorie se dělí ještě na další podkategorie. Podkategorii GENERAL, kde jsou parametry společné pro všechny algoritmy umělé inteligence a spadá sem například parametr na určení zpoždění v milisekundách mezi dvěma akcemi hráče s umělou inteligencí v automatickém módu (ai delay), testovací vzdálenost dostřelu (test range), která se používá v pomocných výpočtech pro umělou inteligenci a nakonec skupina parametrů dávající různou váhu jednotlivým složkám rovnice při výpočtu hodnocení jednotlivých herních stavů (viz. 2.4.1). Pak jsou zde podkategorie pro každý algoritmus, ale jejich obsah si popíšeme až u jednotlivých algoritmů v kapitole 2.4. Při vytvoření nového algoritmu je tedy třeba všechny parametry, kterými se má algoritmus konfigurovat, uvést do této kategorie. Platforma si je sama při spuštění načte. GAME V této kategorii jsou parametry týkající se herního jádra. Je tu parametr MAX PL omezující maximální počet hráčů. Maximální hodnota tohoto parametru je 9 a minimální je 2. Přičemž je třeba, aby pro určitou hodnotu parametru bylo vytvořeno příslušné množství ikon reprezentujících jednotky jednotlivých hráčů. Tedy například pro hodnotu 5 je třeba pro každý typ jednotky vytvořit 5 ikon. Dále je tu parametr MAX UNITS omezující maximální počet jednotek, který může jeden hráč vlastnit. Poslední dva parametry nazvané START MONEY a START TIME určují počet bodů, který každý hráč dostane pro nákup jednotek, a nakonec počet akčních bodů pro jednotlivé tahy hry. GUI Tyto parametry se týkají grafického rozhraní platformy a v současnosti jsou zde pouze dva parametry, a to šířka dlaždice (ICON W ) a výška dlaždice (ICON H ), reprezentující rozměry jednoho políčka mapy v grafickém rozhraní. NETWORK Poslední kategorie parametrů se týká nastavení síťového rozhraní. Do této kategorie zatím nezapadá žádný parametr a je zde z důvodu možnosti rozšíření, například o počet opakovaných pokusů pro připojení k serveru a tak dále. 11
2.2.2
unit types.ait
Zde jsou uloženy všechny typy jednotek. Každá jednotka zde má definován svůj název a dále všechny své parametry, jako je cena, dostřel, zdraví, štít, zbraň, cena pohybu a cena střelby. Nakonec tu jsou parametry důležité pro grafické rozhraní. Název souboru s ikonou jednotky pro jednotlivé hráče ve formátu gif, a jako poslední zde je název souboru obsahující zvuk střelby ve formátu wav. Komentář se v souboru opět označuje znakem ’#’ na začátku řádku. Dále jsou řádky s jednotlivými definicemi jednotek a mají tento tvar: „ <ŠTÍT> ”, kde jméno je řetězec v uvozovkách, další parametry jsou celá čísla a parametry určující ikony jsou názvy souborů s danou ikonou bez mezer, přičemž aktivní ikona znamená ikonu jednotky, na kterou bylo kliknuto, a tedy hráč s ní chce hrát nebo si jen zobrazit její informace. Ostatní ikony jsou normální. Zvuk je také název souboru se zvukem bez mezer. Zde jsem popsal aktuální situaci pro hru s podporou tří hráčů. Pro podporu více hráčů je třeba nadefinovat další ikony a vložit příslušnou barvu s jejím názvem do zdrojového kódu (viz. programátorská dokumentace). Přidání nebo změna jednotek je tedy velmi snadná. Stačí vložit další řádek do tohoto souboru, kde nadefinujeme název jednotky, její parametry a názvy souborů s ikonami a zvukem, vytvoříme ikony a platforma si při spuštění vše načte. Do zdrojového kódu tedy není nutné vůbec zasahovat. Při chybě načítání parametrů bude uživatel upozorněn chybovou hláškou a aplikace se ukončí.
2.2.3
Bonusy
Přidání bonusu probíhá již zásahem do zdrojového kódu. Nový bonus vytváří jako potomek třídy bonus s reimplementovanou funkcí effect(unit *u ), která určuje, co bude daný bonus dělat. Prototyp bonusu se do mapy vkládá v konstruktoru a pro každý nový bonus je třeba ho sem přidat manuálně. Více informací je uvedeno v programátorské dokumentaci.
12
2.2.4
Herní plán
Herní plán je také načítán z externích souborů. Zde jsou dva druhy těchto souborů. První nese příponu „.map” a obsahuje informace o terénu. Druhým souborem je soubor s příponou „.obj” a nese případné informace o rozmístění objektů na mapě. Pro hru je vyžadován pouze soubor s terénem. Soubor s objekty není povinný. Terén Soubor s informacemi o terénu má jednoduchý formát. Na prvním řádku jsou dvě čísla oddělená bílým znakem reprezentující rozměry mapy. Na dalších řádkách je pak uložena informace o terénu, přičemž každý řádek reprezentuje řádek dlaždic terénu a každý sloupec reprezentuje sloupec dlaždic terénu. Výsledkem je tedy matice celých čísel. Země Země je reprezentována čísly 10, 20, 30, 40, 50, 60, 70, 80, 90 a 100. Čím větší číslo je, tím dražší je po dané dlaždici pohyb. Dále je na místě jednotek číslo určující, jaký hráč může na dané políčko umístit svoji jednotku. Například první hráč by měl políčko kódované číslem 11 pro nejlevnější terén. Voda Vodu reprezentuje číslo 10000. Zeď Zeď je reprezentována číslem 20000. Pro jednodušší práci s tímto souborem je vytvořen jednoduchý editor ve formátu XLSX, který po vložení obsahu mapy ze souboru .map mapu pěkně zobrazí a umožňuje ji tedy lépe vytvářet. Zpět do souboru se mapa dostane opět normálním zkopírováním obsahu buněk. Objekty Tento soubor opět podporuje komentáře, kde komentář je identifikován znakem ’#’ na začátku řádku. Další řádky obsahují již informace o rozmístění objektů na herním plánu. Řádek s jednotkami je ve tvaru: „UNIT ”. Název je řetězec v uvozovkách shodující se s názvem nějaké jednotky v souboru unit types.ait, ostatní jsou již celá čísla a ID vlastnícího hráče je pořadí hráče, kde hráči se číslují od 0. Řádek s bonusy vypadá podobně a je ve tvaru: 13
„BONUS ”. Název zde musí odpovídat nějakému bonusu definovanému v mapě s prototypy bonusů (viz. programátorská dokumentace).
2.3
Ovládání
Po spuštění aplikace se zobrazí hlavní menu s tlačítky a konzole, která je zde pouze jako výstupní zdroj informací o načítání souborů, průběhu výpočtů algoritmů a tak dále. Hlavní menu (obr. 2.2) obsahuje následující tlačítka: • [Local Game] • [Network Game] • [Replay] • [Test Algorithms] • [About Qt] • [About] • [Exit]
2.3.1
Local Game
Tímto tlačítkem se zahajuje nastavování lokální hry. Nastavení hry Objeví se okno s textovými poli (obr. 2.3), kam se vyplní jméno, vybere se typ hráče, a v případě počítačového hráče se vybere i algoritmus. Když uživatel nevyplní jméno, vygeneruje se jméno podle pořadí hráče. Po přidání hráče se informace o něm zobrazí v dolní části okna. V dalším poli se vybírá soubor s terénem. Tlačítko [. . .] otevře dialog na vybrání souboru. Tlačítkem [Load] se mapa načte. Poté, co je načten terén, je možné načíst i soubor s objekty, který se načítá stejným způsobem, jako terén. Spustit hru je možné poté, co jsou přidány alespoň dva hráči a načten terén. 14
Obrázek 2.2: Hlavní menu klienta
Kupování jednotek V této fázi hry jednotliví hráči nakoupí své jednotky. Všichni se vystřídají postupně podle pořadí, v jakém se do hry přidali. V případě, že je na řadě počítačový hráč, je zobrazena pouze hláška, že nakupuje jednotky. V případě, že je na řadě člověk, zobrazí se celé hrací pole (obr. 2.4), kde jsou vidět případné načtené jednotky vlastněné tímto hráčem a místa, kam jednotliví hráči mohou umisťovat nakoupené jednotky. Nad hracím polem jsou také zobrazeny zbývající body k nakupování jednotek. Na pravé straně je seznam aktuálně vlastněných jednotek. Pod mapou je zobrazen seznam všech jednotek, které je možné koupit se všemi jejich parametry. Pro koupení jednotky je třeba kliknout na tlačítko [Buy] u dané jednotky a pak na mapě na políčko, které barevně souhlasí s barvou hráče, kliknout levým tlačítkem. Tím se na dané místo jednotka umístí. Pravým kliknutím na jednotku aktuálního hráče se jednotka prodá. Pro ukončení nákupu je v pravém horním rohu umístěno tlačítko [NEXT], kterým se dostane na řadu další hráč. Poté, co všichni hráči dokončí nakupování jednotek, se spustí bojová část hry.
15
Obrázek 2.3: Nastavení lokální hry
Bojová část hry Bojová část hry je hlavní částí. Zde je opět zobrazen herní plán (obr. 2.5), kde jsou tentokrát vidět již všechny jednotky a bonusy. Nad mapou jsou zbývající akční body a napravo je seznam jednotek vlastněných jednotlivými hráči. Pod mapou jsou informace o aktuálně aktivní jednotce a pod nimi několik tlačítek na zobrazování pomocných map. Tlačítka na zobrazování pomocných map. Tato tlačítka se používají hlavně pro analýzu chování umělé inteligence a nejsou primárně určeny pro použití ve standardní hře a jejímu usnadnění. Show estimated map places Mapa hodnotící políčko z hlediska možnosti boje. Každé políčko obsahuje číslo vyjadřující počet jiných políček, ze kterých se dá na dané políčko dostřelit, s dosahem uvedeným v souboru s parametry platformy. Uvažují se pouze políčka, na kterých by se mohla nějaká jednotka potenciálně vyskytovat. Zároveň ale také vyja16
Obrázek 2.4: Kupování jednotek
dřuje, na kolik políček se dá z daného dostřelit, protože když já mohu být zasažen z nějaké vzdálenosti a místa, tak také mohu se stejným dosahem — až na výjimky, jako je střelba přes roh zdi — na dané místo dostřelit. Tato mapa je tedy nezávislá na konkrétním umístění objektů na herním plánu a závisí pouze na terénu, konkrétně tedy pouze na
17
překážkách v něm. Show dangerous map places Tato mapa znázorňuje reálnou nebezpečnost míst na mapě vzhledem k aktuálnímu hráči. Každé políčko tedy obsahuje maximální zranění, které by mohla dostat od nepřátel jednotka jedním výstřelem, která by zde stála a neměla žádný štít. Show possible dangerous map places Zde je situace podobná jako u [Show dangerous map places] s tím rozdílem, že zde neuvažujeme existenci ostatních jednotek jako překážek. To má tu výhodu, že odhalíme nebezpečí v případě, že by měl protivník několik jednotek, které by se vzájemně kryly a stačilo by s první uhnout, aby na nás měl dostřel. Show attackable map places Tato mapa hodnotí hru z ofenzivní stránky, a na rozdíl od [Show dangerous map places], zde každé políčko zobrazuje maximální zranění, které by mohla dostat nepřátelská jednotka od aktuálního hráče jedním výstřelem, která by zde stála a neměla žádný štít. Show map places where to attack from Zde je mapa hodnocena opět z ofenzivního hlediska a jedno políčko vyjadřuje počet nepřátelských jednotek, které by z daného políčka bylo možné aktuálně aktivní jednotkou zasáhnout. Tato mapa nám tedy ukazuje, kam se s danou jednotkou musíme dostat, aby bylo možné zaútočit na nepřítele. Show game state score Toto tlačítko ukáže pouze ohodnocení aktuálního herního stavu. Na pravém horním rohu je tlačítko [Save objects] na uložení rozmístění jednotek na herním plánu. Pak dvě tlačítka na ovládání umělé inteligence. Tlačítko [AI Continue]/[AI Pause], které pozastavují hru umělé inteligence. Při pozastavení hry se může její průběh krokovat tlačítkem [Next command]. V případě, že hra není pozastavená, příkazy umělé inteligence jsou prováděny v intervalu nastaveném v parametrech, což je čas v milisekundách. Tato tlačítka jsou použitelná mimo umělou inteligenci i pro replaye (viz. 2.3.3). Poslední tlačítko v řadě je [NEXT], které ukončuje tah aktuálního hráče, pokud je hráč člověk. Umělá inteligence si tah ukončí sama. Celá hra se opět ovládá pomocí myši. Pravým kliknutím myši na jednotku se jednotka aktivuje, což se projeví změnou její ikonky a výpisem 18
jejich informací pod mapou. Pravým kliknutím na jiné políčko, než jednotku, se aktivní jednotka deaktivuje. Levým tlačítkem se dávají příkazy aktuálně aktivní jednotce. Kliknutím na políčko, kde není jednotka, se generuje příkaz pro pohyb. Kliknutím na jednotku se generuje příkaz pro útok. V případě, že je nějaká jednotka aktivovaná, tak najetí myší na políčko, kam je možný pohyb, se zobrazí nejkratší cesta na dané políčko s cenou pohybu na něj. V případě najetí na jednotku se zobrazí přerušovaná čára symbolizující možnost útoku na danou jednotku, pokud to pravidla dovolují. V případě, že jsou všechny jednotky nějakého hráče zničeny, je tento hráč vynechán ze střídání a hrají již pouze zbylí hráči. Hra končí ve chvíli, kdy zůstane ve hře poslední hráč. Poté se zobrazí dialogové okno informující o konci hry.
Obrázek 2.5: Bojová část hry
Konec hry Dialogové okno informující o konci hry obsahuje jméno a pořadí vítězného hráče a pak několik tlačítek (obr. 2.6). Show statistics Toto tlačítko zobrazuje okno s grafy časů potřebných na 19
jedno rozhodnutí u jednotlivých hráčů s umělou inteligencí. V grafu je znázorněn i průměrný čas jednoho rozhodnutí. Export statistics data Toto tlačítko exportuje naměřené časy potřebné na jedno rozhodnutí u jednotlivých hráčů s umělou inteligencí do textového souboru. Show progress graph Zde se zobrazí graf s průběhem celé hry. Je zde zobrazeno ohodnocení herních stavů po každém tahu vůči každému hráči. Slouží na porovnávání kvality taktik jednotlivých hráčů a potažmo algoritmů umělé inteligence. Export progress data Toto tlačítko exportuje hodnocení stavů z průběhu celé hry do textového souboru. Save starting objects Tímto tlačítkem se uloží objekty, se kterými hráči začali hrát danou hru těsně před nakupovací fází. Save commands Toto tlačítko spolu s předchozím slouží k uložení příkazů každého hráče z průběhu hry. Poté je možné ještě se souborem s terénem a souborem s objekty celou hru znovu přehrát (viz. 2.3.3). New game Spustí novou hru se stejnými hráči, stejným terénem a stejnými objekty od fáze nákupu. Exit to main menu Ukončí hru a zobrazí hlavní menu. Exit Ukončí aplikaci.
2.3.2
Network Game
Tímto tlačítkem se zobrazí okno s nastavováním síťové hry. Nastavení hry Objeví se okno s textovými poli (obr. 2.7), kam se vyplní jméno, vybere se typ hráče a v případě počítačového hráče se vybere i algoritmus. Když uživatel nevyplní jméno, vygeneruje se. V dalším poli se vybírá IP adresa serveru, na kterém běží AI Tester Server a port, na kterém naslouchá příchozím spojením. Tlačítkem [Connect] 20
Obrázek 2.6: Konec hry
se klient pokusí připojit k serveru. Aktuální průběh spojení je zobrazován v dolní části okna. V případě výskytu chyby je uživatel informován dialogovým oknem s chybovou hláškou. Hra se spustí poté, co jsou všichni klienti připojeni. Začíná se opět nakupovací fází.
Obrázek 2.7: Nastavení síťové hry
21
Kupování jednotek V této fázi hry jednotliví hráči nakoupí své jednotky. Všichni se vystřídají postupně podle pořadí, v jakém se do hry přidali. V případě, že je na řadě počítačový hráč nebo síťový hráč, je zobrazena pouze hláška, že nakupuje jednotky. V případě, že je na řadě člověk, prostředí vypadá totožně s prostředím v případě lokální hry (viz. 2.3.1). Bojová část hry Tato část je u síťové hry stejná s lokální. Tlačítko [NEXT] lze použít pouze v případě, že hraje lokální lidský hráč. Po skončení hry se zobrazí opět dialogové okno upozorňující o jeho konci. Konec hry Toto dialogové okno je totožné s oknem pro lokální hru (viz. 2.3.1), pouze tlačítko [New game] zobrazí zpět okno s nastavením síťové hry a hráči se musí opět připojit k serveru.
2.3.3
Replay
Tímto tlačítkem se spouští přehrávání odehrané hry, například z důvodu analýzy. Nejprve se zobrazí okno pro nastavení přehrávání. Nastavení replaye V tomto okně (obr. 2.8) jsou tři textová pole. Do prvního se vloží název souboru s uloženými příkazy, do druhého soubor s terénem a do třetího soubor s rozmístěním objektů. Jsou zde opět tlačítka [. . .], která otevírají dialog na vybrání souboru. Tlačítky [Load] se jednotlivé soubory načítají. Stisknutím tlačítka [NEXT] se spouští replay. Replay Zde se přeskočí nakupovací část hry. Jednotky se nakoupí „tiše”, protože by průběh této části hry stejně nebyl zajímavý. Začíná se tedy bojovou částí hry. Tato část hry je včetně konce totožná s lokální hrou, ve které by hráli pouze hráči řízení počítačem (viz. 2.3.1 a 2.3.1). Pouze v dialogovém okně 22
Obrázek 2.8: Nastavení přehrávání hry
informujícím o konci hry není možné uložit objekty a příkazy, protože to nemá smysl a ze stejného důvodu nelze spustit nová hra.
2.3.4
Test Algorithms
Tato část platformy slouží k testování algoritmů a nezobrazuje průběh hry. Nejprve se zobrazí opět okno s nastavením hry. Nastaveni hry Nastavení hry je zde totožné s nastavením lokální hry (viz. 2.3.1), ale jdou přidávat pouze hráči řízení počítačem. Stiskem tlačítka start začne simulace. Toto okno ukazuje obrázek číslo 2.9. Simulace hry Průběh je zobrazován pouze prostřednictvím konzolového okna (obr. 2.10). Grafické znázornění mapy zde není k dispozici. Na konci testování je zobrazeno dialogové okno s informacemi o konci hry.
23
Obrázek 2.9: Nastavení testovací hry
Obrázek 2.10: Konzole ukazující průběh testování algoritmů
24
Konec hry Toto okno je totožné jako v případě lokální hry (viz. 2.3.1), ale tlačítko [New game] zde zobrazí opět nastavování testovací hry, protože pouštět hru znovu by zřejmě nemělo smysl.
2.3.5
About Qt
Zobrazí okno s informacemi o použitém frameworku Qt.
2.3.6
About
Zobrazí okno s informacemi o aplikaci.
2.3.7
Exit
Ukončí aplikaci.
2.4
Algoritmy umělé inteligence
V této kapitole si popíšeme, jak vytvořit nový algoritmus pro testovací platformu, a pak také nastavení jednotlivých ukázkových algoritmů, které jsou v platformě již implementované. Nejprve popíši základní pojem, který je v aplikaci v souvislosti s umělou inteligencí používán. Jedná se o pojem herní stav.
2.4.1
Herní stav
Herní stav je struktura, ve které jsou obsaženy veškeré informace určující stav hry v daném časovém okamžiku. Mimo tyto informace může ještě obsahovat pomocné mapy analyzující herní plán z různých pohledů a podle různých kritérií. Tyto mapy mají stejnou velikost jako původní herní plán. Herní stav tedy obsahuje celý herní plán s informacemi o terénu a objektech, seznam všech hráčů a jejich jednotek, číslo aktuálního hráče a také ohodnocení stavu vůči aktuálnímu hráči. K výpočtu ohodnocení herního stavu je potřeba několik pomocných map analyzujících herní stav. Herní stav je také struktura, kterou dostane každý algoritmus ve svém tahu, a na jeho základě pak vygeneruje akce, které se mají v daném tahu 25
provést. Tuto strukturu je také možné klonovat a v rámci algoritmu dále měnit a využívat, protože struktury v ní obsažené jsou pak zcela nezávislé na zbytku platformy. V platformě je tento objekt pojmenován jako game state. Dále je poskytován objekt ai game state, který obsahuje normální herní stav a je ještě obohacen o informaci, jakým příkazem se do daného stavu došlo. Tato třída najde své využití hlavně pro potřeby stavění rozhodovacích stromů. Bližší informace k jednotlivým strukturám jsou k dispozici v programátorské dokumentaci. Ohodnocení herního stavu Ohodnocení herního stavu se skládá ze tří složek. První složka hodnotí velikost armád – army balance, druhá zranitelnost armády – army vulnerability a třetí její umístění vůči ostatním armádám – army distances. Každé složce se dá nastavit váha pomocí parametrů z mapy ai parameters v kategorii „GENERAL”. Parametr nastavující váhu složce army balance nese název „army balance coef ”, pro složku army distances se parametr jmenuje „army distances coef ” a pro poslední složku, army vulnerability, to je „army vulnerability coef ”. Výsledné ohodnocení je pak army balance, od kterého se odečte složka army vulnerability a army distances, vše vynásobené koeficienty určující váhu složek. Pokud nastavíme nějakou váhu složky na nulu, nebude se tato složka vůbec počítat. To je výhodné například při přehrávání her, kde můžeme vypustit složku hodnotící vzdálenost armád, protože je její vliv pouze marginální a pouze by zpomalovala výpočet. Nyní si popíšeme, co jednotlivé složky znamenají. army balance Tato složka je založena na porovnávání předpokládané škody, kterou je aktuální hráč schopen nepřátelům způsobit a pak předpokládané průměrné výdrže armády nepřátel. Předpokládaná škoda se počítá pomocí průměrná síly útoku a odhadovaného počtu zbývajících kol ve hře. Průměrná síla útoku zahrnuje i cenu výstřelu a je to součet tolika sil jednoho výstřelu, kolikrát je schopna daná jednotka v jednom tahu vystřelit. Odhadovaný počet zbývajících kol ve hře vychází z odolnosti armády aktuálního hráče, a průměrné síly nepřátelských armád. Předpokládaná výdrž armády se vypočítá jako součet výdrží jednotlivých
26
jednotek. Výdrž zahrnuje aktuální zdraví a štíty všech jednotek. Výsledná složka se spočítá jako rozdíl předpokládané škody, kterou je aktuální hráč schopen způsobit a průměrné výdrže armády nepřátel. Průměrné výdrže a síly nám zde dávají lepší odraz reality a reflektují aspekt, že ve hře hrají všichni proti všem. Ve výsledku nám tato složka bude i určovat, jakého nepřítele je vhodné ničit a tedy bude simulovat vytváření spojenectví mezi slabými armádami. Vezměme si příklad, kde proti sobě hrají dvě slabé a jedna silná armáda. Z pohledu slabé armády bude druhá slabá armáda snižovat průměrnou sílu a výdrž nepřátel. Pokud by tedy slabá armáda zničila druhou slabou, paradoxně si pohorší, protože nyní budou průměrné výdrže a síly mnohem větší. Proto při použití této ohodnocovací funkce v prohledávacím algoritmu způsobí, že hra bude vypadat jako kdyby se obě slabé armády spojily proti silné. Spojenectví bude trvat až do vyrovnání sil. army vulnerability Touto složkou je vyjádřeno průměrné nebezpečí na jednotku, ve kterém celá armáda je. Využívá se zde pomocné struktury dangerous places z herního stavu. Průměr nám zde opět dává takovou vlastnost, že u velké armády jedna jednotka v nebezpečí nevadí, ale jak se armáda zmenšuje, tím více se snaží skrývat před nepřítelem. army distances Poslední složka vyjadřuje průměrnou vzdálenost všech jednotek od místa, ze kterého může daná jednotka útočit na nepřítele. Zde se využívá pomocné struktury range places z herního stavu. Tato složka je zde z důvodu, aby se armády snažili k sobě přibližovat a bojovat. Má za úkol pouze rozlišovat mezi dvěma stavy, kde jsou na tom armády stejně co do velikosti a proto má na výsledné skóre pouze minimální vliv.
2.4.2
Vytváření nového algoritmu
Nový algoritmus lze vytvořit jednoduše. Veškeré potřebné funkce a třídy jsou uvedeny v hlavičkovém souboru ai.h. Stačí pouze udělat potomka třídy algorithm a v něm implementovat dvě základní funkce, a to get buy commands( const game state* gs ) a get commands( const game state* gs ), kde každá 27
funkce dostane jako svůj parametr aktuální herní stav. Vzhledem k takto udělanému návrhu je možné aplikace psát také vícevláknově bez nějakých omezení. Takovým příkladem jsou algoritmy Search algorithm MT (2.4.5) a Monte Carlo algorithm MT (2.4.7). Algoritmus generuje příkazy do seznamu s názvem commands, který je součástí třídy algorithm, ve formátu textového řetězce. Příkazů sloužících k ovládání hry je šest: BUY u x y Tento příkaz je používán pro nákup jednotek v nakupovací části hry a má tři parametry: u je identifikační číslo jednotky k nákupu z komponenty prototypes a x a y jsou souřadnice, kam se zakoupená jednotka má umístit. Po přijetí tohoto příkazu je zavolána metoda buy unit( unit* u, unsigned int x, unsigned int y ) na aktuálním hráči, která jednotku koupí. SEL u Příkaz používaný pro prodávání již nakoupených jednotek. Jediný parametr u určuje identifikační číslo jednotky, která se má prodat, ale nyní již ne v komponentě prototypes, ale v rámci jednotek aktuálního hráče. Přijetím tohoto příkazu je, obdobně jako v případě nákupu, zavolána funkce sell unit( unsigned int u ) na aktuálním hráči. END Tento příkaz je používán pro signalizaci, že hráč dokončil nakupovací fázi hry. Tím je zavolána funkce end buy(), která inicializuje nakupovací fázi u následujícího hráče nebo, pokud již všichni hráči tuto fázi absolvovali, začne bojovou fázi příkazem start game(), která opět provede veškeré inicializace včetně změny grafického rozhraní. MOV u x y Pohyb jednotek je reprezentován tímto příkazem, který má tři parametry: u je identifikační číslo jednotky v rámci hráče a x a y jsou souřadnice, kam se jednotka má pohnout. ATT u x y Toto je zpráva pro útok a má také tři parametry: u je opět identifikační číslo jednotky v rámci hráče, ale x a y jsou nyní souřadnice, kam má jednotka daná identifikačním číslem útočit. NXT Tento příkaz signalizuje, že aktuální hráč ukončil svůj tah. Tím se zavolá funkce next turn(), která inicializuje další tah pro následujícího hráče. Více informací o uvedených metodách je uvedeno v programátorské dokumentaci. 28
Uživatel má k implementaci algoritmu k dispozici řadu funkcí pro simulování jednotlivých tahů na fiktivním herním stavu a testování proveditelnosti těchto tahů, aniž by je musel skutečně provést. Všechny tyto funkce jsou uzavřeny do jmenného prostoru ai support computations. Minimální kostra algoritmu pro jednoduché vytvoření nového se jmenuje stub algorithm, jeho zdrojové kódy jsou v souborech ai stub alg.h a ai stub alg.cpp. Podrobněji je tento algoritmus popsán v programátorské dokumentaci.
2.4.3
Reflex algorithm
Tento algoritmus nemá žádné parametry.
2.4.4
Search algorithm
Tento algoritmus má v parametrech sekci „SEARCH”, kde se nastavuje parametr „depth”, což je hloubka prohledávání.
2.4.5
Search algorithm MT
Sekce v parametrech náležící tomuto algoritmu nese jméno „SEARCH MT”. Podobně, jako u jednovláknové verze, i zde je parametr „depth”, omezující hloubku prohledávání.
2.4.6
Monte Carlo algorithm
Parametry pro tento algoritmus jsou uloženy v sekci „MONTE CARLO”. Parametr omezující hloubku prohledávání nese jméno „depth”, počet expandovaných dětí každého stavu do hloubky 1 je uložen ve „width plans”, ve větších hloubkách je to „width”. Koeficient znevýhodňující stavy, kde končí tah, se jmenuje „nxt coef ”, koeficient preferující dobré stavy a znevýhodňující špatné je „pref coef ” a nakonec koeficient omezující náhodnost výběru stavu se jmenuje „rand coef ”.
2.4.7
Monte Carlo algorithm MT
Parametry, které tento algoritmus využívá, jsou stejné jako u jednovláknové verze (viz. 2.4.6). Zde jsou uloženy v sekci „MONTE CARLO MT”.
29
Kapitola 3 AI Tester Server AI Tester Server umožňuje hru více hráčů přes síťové rozhraní.
3.1
Ovládání
Po spuštění aplikace se zobrazí hlavní menu s tlačítky a konzole, která je zde pouze jako výstupní zdroj informací o načítání souborů, průběhu síťové komunikace a tak dále. Hlavní menu (obr. 3.1) obsahuje následující tlačítka: • [Start Server] • [About Qt] • [About] • [Exit]
3.1.1
Start Server
Tímto tlačítkem se spouští server. Nejprve se ale zobrazí okno s nastavením hry a serveru. Nastavení serveru Okno s nastavením serveru (obr. 3.2) obsahuje textové pole, do kterého se vyplní port, na kterém má server naslouchat, dále je zde nabídka pro 30
Obrázek 3.1: Hlavní menu serveru
nastavení počtu hráčů do síťové hry a nakonec načítání terénu a objektů, které funguje stejně jako u klienta v lokální hře (viz. 2.3.1). Server lze spustit tlačítkem [LISTEN] v pravém horním rohu okna poté, co je načten terén. Po zapnutí serveru se zobrazí okno s informacemi o připojených klientech. Naslouchací mód Nahoře je zobrazen stav serveru, pod ním jsou bloky zobrazující informace o připojených klientech. Server se restartuje tlačítkem [Restart server], které pošle všem klientů upozornění, odpojí je a restartuje server, ke kterému se mohou opět připojovat noví klienti. V případě odpojení připojeného klienta se server automaticky do 2 sekund restartuje, aby mohl navázat nová spojení. Obrázek tohoto okna má číslo 3.3.
3.1.2
About Qt
Zobrazí okno s informacemi o použitém frameworku Qt.
3.1.3
About
Zobrazí okno s informacemi o aplikaci.
3.1.4
Exit
Ukončí aplikaci.
31
Obrázek 3.2: Nastavení síťové hry
32
Obrázek 3.3: Naslouchací mód serveru
33
Kapitola 4 Zdrojové kódy Vzhledem k použití opensource verze platformy Qt, jsou zdrojové kódy celé aplikace publikovány pod licencí GNU General Public License verze 3.0. Domovská stránka projektu je umístěna na Google Code pod adresou http://code.google.com/p/ai-tester/. Zde je také k dispozici repositář s aktuální verzí zdrojových kódů, které je možné stáhnout pomocí příkazu svn checkout http://ai-tester.googlecode.com/svn/trunk/. V sekci Downloads jsou umístěny soubory s programátorskou a uživatelskou dokumentací a instalátor aplikace pro systém Windows.
34
