eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra kybernetiky
Diplomová práce
Porovnávání metod prohledávání s pro°ezáváním u extenzivních her se simultánními tahy
Roman Vítek
Vedoucí práce:
Mgr. Branislav Bo²anský
Studijní program: Otev°ená informatika, Magisterský
Obor: Um¥lá inteligence
3. ledna 2013
iv
Pod¥kování Cht¥l bych zde pod¥kovat vedoucímu své práce, panu Mgr. Branislavu Bo²anskému za trp¥livost a podporu, které mi v¥noval b¥hem práce na tomto projektu a také za ochotu s jakou mi pomáhal postupovat dál a °e²it nastalé problémy.
Abstract This work provides description and comparison of a few algorithms and their variations which should make the computation faster in a certain way. It is achieved by shortening of the computation by skipping states which are assessed as worthless for the nal result. There are three algorithms presented in this work. The rst one is called Minimax and it is one of the basic algorithms in the game theory. The way of pruning in this algorithm is based on not visiting the nodes which are no longer useful during evaluation. These nodes are recognized by the values gained earlier. The second algorithm in this work is MonteCarlo Tree Search which represents the only stochastic algorithm. Its pruning is stochastic and it prunes the nodes that seem inconvenient. The last and the most important algorithm presented in this work is the Linear program which evaluates mixed strategies in Nash Equilibria. The extension of this algorithm is based on the progressive addition of actions done by both players to the computing. The evaluation of the linear program can this way nish before all of the available actions are added. This algorithm is called Double oracle and there is also presented one more extension of it in this work. It is based on modi cation of algorithm by selecting actions to the evaluation during Double oracle and it is based on the result estimation done by Minimax algorithm. In this work you can nd comparison of the performance, e ciency and required resources of these algorithms.
Abstrakt Tato práce poskytuje popis a porovnání n¥kolika algoritm· a jejich variant, které mají za úkol n¥jakým zp·sobem urychlit výpo£et. Toho dosahují zkrácením výpo£tu o procházení
vi
vii
n¥kterých stav·, které uznají jako zbyte£né nav²t¥vovat a prohledávat. Jsou zde p°edstaveny celkem t°i algoritmy. Prvním z nich je Minimax, který je jeden ze základních algoritm· teorie her. Zp·sob pro°ezávání v tomto algoritmu je zaloºen na neprocházení uzl·, které je v rámci výpo£tu jiº zbyte£né nav²t¥vovat. Ty pozná podle d°íve získaných hodnot. Druhým a jediným stochastickým algoritmem v této práci je Monte-Carlo Tree Search. Jeho pro°ezávání je také stochastické a vy°azuje uzly, které vypadají nevýhodn¥. Posledním a nejd·leºit¥j²ím algoritmem této práce je Lineární program, který po£ítá smí²ené strategie v Nashov¥ ekvilibriu. Roz²í°ení tohoto algoritmu je zaloºeno na postupném skládání lineárního programu a postupného p°idávání jednotlivých akcí obou hr᣷. Takto m·ºe skon£it výpo£et d°íve neº p°idáme v²echny akce. Tento algoritmus se jmenuje Double oracle a v této práci je p°edstaveno je²t¥ jedno moºné roz²í°ení. To je zaloºené na úprav¥ algoritmu, který vybírá akce p°idávané do výpo£tu a je postaveno na odhadování výsledku pomocí algoritmu Minimax. V této práci lze najít porovnání výkonu p°i h°e mezi sebou a porovnání pot°ebných zdroj·.
Obsah 1 Úvod
1
2 Teorie her
3
2.1
Zero-sum game
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
Hra v normální form¥
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.3
Hra v extenzivní form¥ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3 Známé algoritmy 3.1
3.2
3
5
Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1
Minimax se simultánními tahy
3.1.2
Alpha-beta
3.1.3
Alpha-beta ve stage minimaxu
5
. . . . . . . . . . . . . . . . . . . . . .
7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
. . . . . . . . . . . . . . . . . . . . .
10
Monte-Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2.1
Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2.2
Expanze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2.3
Simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2.4
Zp¥tná propagace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.5
Známá pro°ezávání v MCTS . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.5.1
Progressive unprunning
. . . . . . . . . . . . . . . . . . . . .
12
3.2.5.2
Postupné odebírání
. . . . . . . . . . . . . . . . . . . . . . .
12
4 Lineární program
13
4.1
Nashovo Ekvilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.2
Ryzí strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.3
Smí²ená strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.4
Tvorba lineárního programu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.5
Double oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.5.1
Best response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.5.2
Odhad pomocí minimaxu
. . . . . . . . . . . . . . . . . . . . . . . . .
16
4.5.3
Od°ezávání b¥hem odhadu
. . . . . . . . . . . . . . . . . . . . . . . .
16
5 Hra Planet Wars
18
5.1
O h°e
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
5.2
Zdroj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
viii
ix
OBSAH
6 Implementace 6.1
21
Spou²t¥ní programu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6.1.1
Simulátor
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6.1.2
Experimentátor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6.2
Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.3
Generování akcí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.4
Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.5
Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.6
Planet Wars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.2.1
6.6.1
Planet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
6.6.2
Fleet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
6.6.3
Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
6.6.4
6.6.4.1
. . . . . . . . . . . . . . . . . . . . . .
25
6.7
Implementace bot· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.8
Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.8.1
Stage Minimax
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.8.2
Alpha-beta
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.9
Výpo£et hodnoty hry
MCTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.10 Cplex
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28 29
6.11 Double oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
6.12 Double oracle s pro°ezáváním
31
. . . . . . . . . . . . . . . . . . . . . . . . . . .
7 Experimenty
33
7.1
Porovnání serializovaného minimaxu a lineárního programu
7.2
Hra proti jednoduchému soupe°i
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
33 36
7.3
Lineární program a jeho verze . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
7.4
Závislost po°adí vygenerovaných akcí . . . . . . . . . . . . . . . . . . . . . . .
41
7.5
Turnaj mezi boty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
8 Záv¥r
44
9 Seznam pouºitých zkratek
47
10 Obsah p°iloºeného CD
48
Seznam obrázk· 3.1
Pln¥ expandovaný strom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3.2
Expandování stromu p°i h°e tic-tac-toe . . . . . . . . . . . . . . . . . . . . . .
7
3.3
Stage vytvo°ená pro výpo£et minimaxu z obrázku 3.1 . . . . . . . . . . . . . .
8
3.4
Pr·b¥h algoritmu MCTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
5.1
Ukázka vizualizátoru a mapy se 7 planetami . . . . . . . . . . . . . . . . . . .
19
5.2
Ukázka vizualizátoru a mapy s 11 planetami . . . . . . . . . . . . . . . . . . .
20
7.1
Porovnání £asové sloºitosti Minimaxu a lineárního programu . . . . . . . . . .
34
7.2
Porovnání po£tu vytvo°ených uzl· Minimaxu a lineárního programu
. . . . .
34
7.3
Porovnání £asové sloºitosti Minimaxu a lineárního programu . . . . . . . . . .
35
7.4
Porovnání po£tu vytvo°ených uzl· Minimaxu a lineárního programu
. . . . .
35
7.5
Porovnání £asové sloºitosti v závislosti na po£tu planet . . . . . . . . . . . . .
37
7.6
Porovnání po£tu vytvo°ených uzl· v závislosti na po£tu planet
37
7.7
Porovnání £asové sloºitosti lineárního programu . . . . . . . . . . . . . . . . .
39
7.8
Porovnání po£tu vytvo°ených uzl·
40
7.9
Porovnání £asové sloºitosti lineárního programu . . . . . . . . . . . . . . . . .
7.10 Porovnání po£tu vytvo°ených uzl·
. . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.11 Porovnání £asové sloºitosti uzl· b¥hem turnaje
40 41
. . . . . . . . . . . . . . . . .
42
7.12 Porovnání po£tu vytvo°ených uzl· b¥hem turnaje . . . . . . . . . . . . . . . .
43
x
Seznam tabulek 4.1
Tabulka s hodnotami pro výpo£et lineárního programu . . . . . . . . . . . . .
15
7.1
Výsledky turnaje mezi boty
42
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
Kapitola 1
Úvod Tato práce zkoumá a porovnává n¥kolik algoritm· pro °e²ení extenzivních her. Na v²echny zkoumané algoritmy je aplikován n¥jaký zp·sob pro°ezávání a následn¥ je prozkoumána jeho efektivita a p°ínos. Zkoumané algoritmy v této práci jsou celkem t°i. Prvním z nich je algoritmus Minimax. Je to velice základní deterministický algoritmus pro °e²ení her. P°es jednoduchou logiku a jednoduchost na implementaci je pom¥rn¥ silný ve velkém mnoºství her. Jeho síla je v tom, ºe uvaºuje v²echny moºné herní situace, které mohou nastat a z tah·, které m·ºe zahrát, tak vybere ten, který je pro n¥j nejvýhodn¥j²í, resp. tah, který je pro n¥j nejmén¥ nevýhodný. Jeho síla je ale také jeho slabinou, protoºe uvaºování v²ech moºností, v jaké se hra m·ºe vyvinout, zabere hodn¥ £asu a pam¥ti. Tuto slabinu v n¥kterých p°ípadech dokáºe více nebo mén¥ potla£it pro°ezávání Alphabeta. Tato modi kace algoritmu Minimax má stejné výsledky, dojde ke stejným záv¥r·m, ale kompletní prohledávání m·ºe zna£n¥ zredukovat. K pro°ezávání v tomto algoritmu dochází na základ¥ hodnot z jiº prohledaných £ástí stavového prostoru. Druhým algoritmem, který je zde zkoumán, je algoritmus Monte-Carlo Tree Search. Tento algoritmus je stochastický a jeho teorie i implementace je celkov¥ o n¥co sloºit¥j²í neº u Minimaxu. Monte-Carlo prohledává v podstat¥ stejný strom jako Minimax. Protoºe ale Minimax není u v¥t²iny her ani zdaleka schopen prohledat celý stavový prostor a nechává se prohledávat pouze do n¥jaké hloubky, algoritmus Monte-Carlo získává výhodu v tom, ºe je schopen prohledat £ásti stavového prostoru do v¥t²í hloubky a lépe tak najít lep²í akci. Ale i zde
1
funguje teorie tzv. "no free lunch" , která °íká, ºe jakákoliv výhoda v jednom sm¥ru musí být zaplacena nevýhodou ve sm¥ru jiném. Nevýhodou tedy je, ºe prohledávání se soust°edí na tahy, které vypadají výhodn¥, coº vzhledem ke stochastickému p°ístupu m·ºe znamenat, ºe p°ehlédne n¥jakou dobrou akci. Druhou nevýhodou je nutnost nechat b¥ºet algoritmus co nejdéle, aby byl schopen dostate£n¥ prohledat stavový prostor a na²el n¥jaký "chytrý"tah. Pro°ezávání v tomto algoritmu má snahu výpo£et urychlit a zredukovat po£et iterací, které se v¥nují ²patným tah·m. Na základ¥ vypo£ítaných ohodnocení jednotlivých akcí se po ur£itém po£tu pr·chod· zamykají £ásti stromu. Dále se pak nenav²t¥vují a místo nich se prohledávají ostatní nezamknuté £ásti. Nevýhodou ale je, ºe m·ºeme zamknout dobrou akci a tím výpo£et usm¥rnit ²patným sm¥rem.
1
p°eklad: ádný ob¥d není zadarmo.
1
KAPITOLA 1.
ÚVOD
2
Posledním algoritmem v této práci je výpo£et lineárního programu. Tento algoritmus hledá smí²ené strategie, pro které platí Nashovo ekvilibrium, podle kterých pak ur£íme tah, který daný hrᣠud¥lá. Teoreticky by m¥l hrát lépe neº Minimax ve hrách se simultánními tahy, protoºe s nimi p°ímo dokáºe po£ítat, kdeºto pro Minimax musíme takovou hru serializovat. V této práci jsem aplikoval dv¥ metody pro°ezávání na lineární program. První metodou je algoritmus Double oracle p°evzatý z jiných prací. Po£ítá lineární program zp·sobem, který ve výsledku nemusí po£ítat se v²emi moºnými stavy. P°idává tahy obou hr᣷ do výpo£tu postupn¥, dokud n¥který z hr᣷ najde lep²í tah na základ¥ p°edchozího výpo£tu. Sice tedy vypo£ítává lineární program vícekrát, ale pokud se v kone£ném výsledku projeví pouze zlomek celkového mnoºství stav·, tak na tom algoritmus vyd¥lá. Druhou metodou je modi kace Double Oraclu o dal²í pro°ezávání. Toto roz²í°ení vzniklo v pr·b¥hu této práce. Základní varianta tohoto algoritmu po£ítá v kaºdé iteraci nejlep²í reakci obou hr᣷ a hledá, zda je pot°eba p°idat n¥jakou dal²í akci do výpo£tu. Hodnoty akcí spou²tí rekurzivní výpo£ty. My²lenkou úpravy je, ºe pokud budeme mít dobrý odhad, tak m·ºeme p°esko£it ²patnou akci a tím i zdlouhavý rekurzivní výpo£et. Aby byl odhad korektní a nebyla moºnost, ºe od°ízneme dobrou akci, byl pouºit k odhadování Minimax na serializovanou hru tak, ºe odhad je optimistický a nikdy nem·ºe být hor²í neº reálná hodnota hry. V²echny tyto algoritmy byly otestovány a porovnány mezi sebou na domén¥ hry Planet Wars. Tato hra byla p°edstavena b¥hem jednoho Google AI Challange a byla ur£ena na sout¥º mezi po£íta£ovými hrá£i. Je to hra se simultánními tahy a pom¥rn¥ velkým v¥tvícím faktorem, takºe se pro°ezávání stavového prostoru algoritm· m·ºe po°ádn¥ ukázat. Jak jednotlivé algoritmy a jejich modi kace dopadly se dozvíte dále. Následuje bliº²í teoretický popis v²ech algoritm·, popis hry Planet Wars a informace o celé implementaci. Na záv¥r jsou pak provedeny experimenty.
Kapitola 2
Teorie her Teorie her je obor, ve kterém se zkoumají kon iktní situace a hledá pokud moºno optimální strategii p°i jejich °e²ení. Kon ikt nastává mezi dv¥ma a více agenty a typickým zástupcem jsou práv¥ hry. Nap°íklad ²achy jsou typická situace, kde se dva agenti (hrá£i) snaºí porazit toho druhého. Kaºdý agent vybírá, jakou akci chce ud¥lat (jakou tah chce zahrát) a kaºdá akce má n¥jaký dopad na kone£ný výsledek kon iktu. Aby bylo moºné n¥jakým zp·sobem ur£it, která akce je lep²í, udává se pro kaºdého hrá£e funkce, která udává jeho zisk na základ¥ provedených akcí.
2.1
Zero-sum game
Pokud platí, ºe zisk jednoho hrá£e se rovná ztrát¥ druhého, jedná se o hru s nulovým sou£tem, neboli "zero-sum". Jako p°íklad op¥t m·ºeme pouºit ²achy, kde zisk jednoho hrá£e znamená, ºe p°ipravil soupe°e o n¥jakou guru. Coº se na zisku druhého hrá£e promítne jeho sníºením a to o stejnou hodnotu, jako si první hrᣠpolep²il - o hodnotu sebrané gury. V takovém p°ípad¥ m·ºeme místo zisku obou hr᣷ udávat hodnotu hry a nechat se snaºit jednoho hrá£e, aby tato hodnota byla co nejvy²²í, a druhého, aby byla co nejmen²í.
2.2
Hra v normální form¥
Pro zapsání her existují dva zp·soby. Prvním zp·sobem je takzvaná normální forma, kdy je celá hra reprezentována tabulkou. Tahy jednoho hrá£e jsou reprezentovány sloupci, tahy druhého °ádky a kaºdá bu¬ka obsahuje hodnotu hry. Kdyº oba dva hrá£i zvolí sv·j tah (tedy vyberou jeden °ádek a jeden sloupec), tak hodnotu hry de nuje jejich pr·se£ík. Takto se reprezentují hry, ve kterých oba dva hrá£i hrají sou£asn¥.
2.3
Hra v extenzivní form¥
Druhým zp·sobem je reprezentace hry v podob¥ stromu. Kaºdý uzel stromu reprezentuje rozhodování jednoho z hr᣷. Hrá£i se zpravidla v tazích st°ídají a rozhodují se v závislosti na p°edchozích tazích. Hodnotu hry pak najdeme v listových uzlech stromu. Pokud tedy
3
KAPITOLA 2.
TEORIE HER
4
necháme postupn¥ hrá£e vybírat jejich akce, postupujeme stromem dol· od ko°ene a kdyº dorazíme do listu, zjistíme jak hra dopadla. V této práci jsem pouºil pro testování zero-sum hru se simultánními tahy. Proto pouºívám oba dva zp·soby reprezentace, resp. kaºdý uzel tvo°í tabulka, ale protoºe prohledávám hru o n¥kolik tah· dop°edu, tak vzniká celý strom.
Kapitola 3
Známé algoritmy 3.1
Minimax
Minimax [9], n¥kdy také ozna£ovaný jako Maximin, je jedním z nejzákladn¥j²ích algoritm· v herní teorii. Principiáln¥ jednoduchým zp·sobem dokáºe vybrat tah, kterým minimalizuje svou ztrátu. Algoritmus funguje tak, ºe z po£áte£ního stavu expanduje v²echny stavy, které mohou následovat, tj. jeden nový stav pro kaºdou akci, kterou m·ºe hrᣠna tahu ud¥lat. Takto rekurzivn¥ pokra£uje dokud nedorazí do terminálního stavu, tj. stav, ve kterém nastane konec hry. Nap°íklad v ²achu je to bu¤ chvíle, kdy jeden z hr᣷ dal druhému mat nebo se hra dostala do patového konce.
Obrázek 3.1: Pln¥ expandovaný strom
Na obrázku 3.1 je ukázáno, jakým zp·sobem probíhá výpo£et Minimaxu. Z horního ko°enového uzlu m·ºe první, maximalizující, hrᣠud¥lat t°i tahy. Na kaºdý tento tah m·ºe jeho soupe°, minimalizující hrá£, ud¥lat op¥t 3 tahy. Tím vznikne ve t°etí vrstv¥ 9 uzl·. Ve
5
KAPITOLA 3.
ZNÁMÉ ALGORITMY
6
druhé vrstv¥ vybírá tahy minimalizující hrá£, na kaºdý tah z první vrstvy tedy vybere sv·j tah, který vede na co nejmen²í hodnotu hry. V první vrstv¥ pak maximalizující hrᣠz t¥chto hodnot vybere tu nejv¥t²í a tím zárove¬ vybírá akci, kterou chce hrát. Z terminálního stavu pak vrátí hodnotu s jakou hra skon£ila. V nejjednodu²²ím p°ípad¥ to je maximální hodnota hry, pokud vyhraje jeden hrᣠa minimální hodnota hry v opa£ném p°ípad¥. Ve sloºit¥j²ích p°ípadech jsou to pak hodnoty mezi nimi. Pro neterminální stav pak vezme hodnoty, které se mu vrátí z rekurze a vybere jednu z nich podle hrá£e, který je zrovna na tahu. Pro maximalizujícího hrá£e vybere nejvy²²í hodnotu a pro minimalizujícího tu nejniº²í. Pro ilustraci je zde p°iloºen pseudokód minimaxu:
1 double minimax(node, depth, player){ 2 if (node is a terminal node or depth <= 0){ 3 return the heuristic value of node 4 } 5 if (player == minPlayer) { 6 value <- +infinity 7 for (each child of node){ 8 value <- Min(value, minimax(child, depth-1, not(player))) 9 } 10 } 11 else if(player == maxPlayer){ 12 value <- -infinity 13 for (each child of node){ 14 value <- Max(value, minimax(child, depth-1, not(player))) 15 } 16 } 17 return value 18 } Nejv¥t²í problém tohoto algoritmu je jeho £asová náro£nost. Protoºe se strom expandovaných uzl· v¥tví podle po£tu akcí jednotlivých hr᣷, tak p°i sloºit¥j²ích hrách, kde je velké mnoºství moºností, jak mohou hrá£i táhnout, rapidn¥ nar·stá mnoºství procházených uzl·. I v jednoduché h°e pi²kvorek na poli 3x3, známé jako tic-tac-toe, m·ºe v prvním tahu hrᣠtáhnout 9ti r·znými tahy, viz obrázek 3.2 [5]. Druhý hrᣠm·ºe pak reagovat 8mi tahy (jedno pole uº je zabrané) a první hrᣠop¥t m·ºe zahrát 7 r·zných tah·. P°i t°etím tahu se tedy dostaneme na 502 r·zných moºností, jak m·ºe herní plocha vypadat. Expandovaný strom k této h°e je vid¥t na obrázku. Pokud spo£ítáme celkový po£et stav·, dostaneme se k 1 milionu stav·. To není tolik, abychom to nemohli spo£ítat, ale je to pom¥rn¥ velké mnoºství stav· na tak jednoduchou hru [5]. Ve sloºit¥j²ích hrách za£íná být tato náro£nost problémem jak £asovým, tak pam¥´ovým. To se dá °e²it nap°íklad zadáním maximální hloubky prohledávání a v této hloubce ozna£it kaºdý stav jako terminální. V tom p°ípad¥ ale nastává problém, jakou hodnotu hry vrátit zp¥t. Na konci hry je to jednoduché v¥t²inou hra kon£í výhrou jednoho z hr᣷, p°ípadn¥ se je²t¥ zahrnuje remíza. V rozehrané h°e ale záleºí, jakým zp·sobem vypo£ítáme hodnotu hry.
KAPITOLA 3.
ZNÁMÉ ALGORITMY
7
Obrázek 3.2: Expandování stromu p°i h°e tic-tac-toe
Do hodnoty hry m·ºeme po£ítat r·zné v¥ci a také jim dát r·zné váhy. Nap°íklad v ²achové h°e je nejjednodu²²í ur£it hodnotu hry podle pom¥ru po£tu gur obou hr᣷. Tím m·ºeme ur£it výhodu jednoho hrá£e oproti druhému. Nicmén¥ v ²achu je kaºdá gura jinak silná a £ist¥ po£et gur obou hr᣷ tak nejspí²e nedá spolehlivý odhad. M·ºeme tedy p°i°adit kaºdé gu°e n¥jakou hodnotu a spo£ítat, kolik má kaºdý hrᣠbod· a porovnat tyto hodnoty. Tento p°ístup uº dává spolehliv¥j²í odhad, ale po°ád nebere v úvahu postavení gur na hrací plo²e, které také m·ºe hrát velkou roli. Ur£it tedy hodnotu rozehrané hry není snadný úkol.
3.1.1
Minimax se simultánními tahy
Pokud chceme pouºít Minimax pro hru se simultánními tahy, tj. hru, ve které oba hrá£i hrají ve stejnou dobu, musíme algoritmus upravit. M·ºeme celou hru serializovat a expandovat jednotlivé vrstvy stejn¥ jako p°i st°ídání tah·. V tom p°ípad¥ záleºí na tom, kterého hrá£e necháme hrát jako prvního. Hrá£, který hraje jako druhý má v tu chvíli výhodu, ºe m·ºe reagovat na tah soupe°e. Kdyº chceme pouºít Minimax, aby nám ur£il tah, který má hrᣠhrát, tak výb¥r prvního hrá£e p°i serializaci hraje d·leºitou roli. Pokud necháme na²eho hrá£e za£ínat, °íkáme, ºe hraje pesimisticky. Tím, ºe ho necháme hrát prvního, po£ítáme s tím, ºe soupe° bude znát jeho tah d°ív, neº sám bude hrát. Tak reaguje na tahy na²eho hrá£e a tím pro nás vzniká hor²í situace. Pokud necháme na²eho hrá£e hrát druhého, jedná se o optimistickou variantu algoritmu, protoºe m·ºeme reagovat na tah soupe°e my a tím pádem máme výhodu. Dal²í moºností, jak serializovat výpo£et Minimaxu, je upravit algoritmus tak, ºe v kaºdé vrstv¥ budeme expandovat podle tah· obou hr᣷. Tím nám místo n¥kolika nových stav· vznikne celá tabulka, tzv. stage. Jeden rozm¥r ur£ují tahy jednoho hrá£e a druhý rozm¥r tahy druhého hrá£e. V této reprezentaci musíme upravit i výpo£et tah·, které oba hrá£i vyberou. V kaºdém stavu první rekurzivn¥ spo£ítáme v²echny hodnoty v tabulce a poté hledáme hodnotu, která bude tento stav reprezentovat. Na obrázku 3.3 je vid¥t stejná hra, jako je znázorn¥na vý²e na obrázku 3.1. ádky ur£uje maximalizující hrᣠa sloupce hrᣠminimalizující. Maximalizující hrᣠvybere v kaºdém °ádku minimální hodnotu, tedy jak p°edpokládá, ºe by mohl hrát soupe°. Z t¥chto hodnot pak vybere maximální, tedy tu hodnotu, která mu p°inese nejv¥t²í uºitek. Obrácen¥ pak
KAPITOLA 3.
ZNÁMÉ ALGORITMY
8
Obrázek 3.3: Stage vytvo°ená pro výpo£et minimaxu z obrázku 3.1
druhý hrᣠvybere z kaºdého sloupce maximální hodnot a z t¥ch pak pro sebe vybere op¥t tu nejlep²í, v tomto p°ípad¥ minimální. Vybrané tahy obou hr᣷ pak ur£í hodnotu hry v tomto uzlu. V p°íklad na obrázku oba dva volí sv·j druhý tah a tím u£í hodnotu hry 6. V tomto p°ípad¥ oba hrá£i samostatn¥ zvolí stejnou výslednou hodnotu, ale toto nemusí platit vºdy. Pokud chceme po£ítat opravdu se simultánními tahy, musíme sáhnout k výpo£tu lineárního programu, který je popsán níºe. Ten na rozdíl od Minimaxu vypo£ítá smí²ené Nashovo ekvilibrium, které existuje vºdy a reprezentuje hodnotu hry.
3.1.2
Alpha-beta
Alpha-beta [9] je zp·sob pro°ezávání v algoritmu Minimax. Dokáºe zna£n¥ zredukovat prohledávané stavy a tím i pomoct zmen²it nároky na pam¥´ a £as. Toto roz²í°ení v podstat¥ prohlubuje základní my²lenku Minimaxu a postupuje s ní o krok dál. Minimax p°i tahu kaºdého hrá£e vybírá vºdy nejvýhodn¥j²í tah z hodnot, které má k dispozici. B¥hem prohledávání uº ale víme, jaká je dosavadní nejlep²í hodnota. Z t¥chto hodnot pak m·ºeme usoudit, ºe lep²í tah uº nemá smysl hledat, protoºe pokud by takový tah existoval, soupe° nám ho nedovolí zahrát. P°i výpo£tu Alpha-bety p°edáváme do rekurze o dv¥ hodnoty víc neº p°i klasickém Minimaxu. Tyto hodnoty ozna£ujeme jako alpha a beta a reprezentují dosavadní nejlep²í hodnotu pro oba hrá£e. Hodnota alpha je nejlep²í hodnotou maximalizujícího hrá£e. Pokud nenajdeme ºádnou lep²í hodnotu, tak hrᣠzvolí akci s hodnotou alpha. Hodnota beta je pak nejlep²í hodnota minimalizujícího hrá£e, tedy zatím nejlep²í akce tohoto hrá£e má hodnotu beta.
KAPITOLA 3.
ZNÁMÉ ALGORITMY
9
P°i startu celého algoritmu nastavíme alphu na nejniº²í moºnou hodnotu prom¥nné a betu na nejvy²²í a to z toho d·vodu, aby kaºdá nalezená akce m¥la pro hrá£e lep²í hodnotu neº tuto po£áte£ní. Tím docílíme toho, ºe vybere hodnotu první akce p°i výpo£tu a dále jí pak zlep²uje. Pak v kaºdém uzlu, kde hraje maximalizující hrᣠpracujeme s hodnotou alpha. P°i volání rekurze si zapamatujeme vrácenou hodnotu pouze ve chvíli, kdy je v¥t²í neº aktuální alpha a zárove¬ na tuto hodnotu alphu nastavíme (takºe p°i volání dal²í rekurze bude p°edávaná alpha hodnota v¥t²í neº v p°edchozích voláních, £ímº zp°ís¬ujeme dal²í prohledávání). Zárove¬ p°i kaºdé zm¥n¥ alpha hodnoty porovnáme alphu s betou. Pokud je alpha v¥t²í neº beta, m·ºeme s jistotou °íct, ºe dal²í prohledávání nep°inese lep²í výsledek, protoºe soupe° v tahu p°ed námi rad¥ji zvolí tah, který má hodnotu hry beta. Ukon£íme v aktuálním uzlu prohledávání a vrátíme zp¥t hodnotu alpha. V kaºdém uzlu, kde táhne minimalizující hrá£, to funguje p°esn¥ naopak. Kaºdou hodnotu vrácenou z rekurze uloºíme jako hodnotu beta, pokud je men²í neº aktuální hodnota bety (takºe v dal²ích voláních rekurze p°edáváme jiº upravenou betu a tím zp°ís¬ujeme dal²í prohledávání). Pokaºdé je²t¥ porovnáme hodnoty alpha a beta a pokud je beta men²í neº alpha, tak kon£íme v tomto uzlu s prohledáváním a vrátíme zp¥t hodnotu beta. M·ºeme totiº s jistotou °íct, ºe uº pro tohoto hrá£e nenajdeme lep²í tah. Pokud bychom na²li tah s lep²í hodnotou (v tomto p°ípad¥ men²í), tak v p°edchozím tahu soupe° vybere jiný tah. Dal²í hledání je tedy zbyte£né. Pro lep²í p°edstavu je zde uveden pseudokód tohoto algoritmu:
1 double alphabeta(node, depth, alpha, beta, player){ 2 if (node is a terminal node or depth <= 0){ 3 return the heuristic value of node 4 } 5 if (maxPlayer) { 6 for (each child of node){ 7 alpha <- Max(alpha, minimax(child, depth-1, alpha, beta, not(player))) 8 //alpha cut-off 9 if (beta <= alpha){ 10 break 11 } 12 } 13 return alpha 14 } 15 else{ 16 for (each child of node){ 17 beta <- Max(beta, minimax(child, depth-1, alpha, beta, not(player))) 18 //beta cut-off 19 if (beta <= alpha){ 20 break 21 } 22 } 23 retun beta 24 } 25 }
KAPITOLA 3.
10
ZNÁMÉ ALGORITMY
Vzhledem k tomu, ºe se nejedná o ºádný odhad, ale p°i pro°ezávání máme jistotu, ºe lep²í tah nenajdeme, vrací tento algoritmus stejné výsledky jako základní verze, ale je ve v¥t²in¥ p°ípad· rychlej²í a pam¥´ov¥ mén¥ náro£ný. Pokud by nastala situace, ºe neu°ízneme ºádný nebo velmi málo uzl·, bude naopak takto upravený algoritmus pomalej²í kv·li kontrolám hodnot alpha a beta.
3.1.3
Alpha-beta ve stage minimaxu
Pokud aplikujeme Alpha-beta pro°ezávání na stage Minimax, tak m·ºeme postupovat podobn¥ jako p°i klasickém pouºití Alpha-bety. Pro°ezáváme pak bu¤ °ádky nebo sloupce podle toho, od jakého hrá£e chceme získat jeho tah. Pouze musíme dát pozor na nastavování hodnot alpha a beta a musíme celou tabulku projít dvakrát. Jednou pro maximalizujícího hrá£e a jednou pro minimalizujícího. Jednou tedy procházíme tabulku po sloupcích a pokud se zk°íºí hodnoty alpha a beta, p°ejdeme rovnou do dal²ího sloupce. P°i pr·chodu °ádk· pak v p°ípad¥ zk°íºení hodnot p°ejdeme na dal²í °ádek. P°i p°echodu na dal²í iteraci, a´ uº °ádku nebo sloupce, musíme upravit jednu z hodnot - alphu nebo betu - na p·vodní p°edanou hodnotu z vy²²í vrstvy stromu.
3.2
Monte-Carlo Tree Search
Monte-Carlo Tree Search, dále jen MCTS, je stromová metoda pro hledání optimálních rozhodnutí pro problémy v um¥lé inteligenci, typicky plánování nebo kombinatorické hry. MCTS musí mít ur£enou podobu jednoho uzlu a jakým zp·sobem se z n¥j vytvá°í potomci. Na za£átku b¥hu dostane první uzel reprezentující aktuální stav sv¥ta a dále funguje ve £ty°ech krocích 3.4 [6]:
•
Selekce
•
Expanze
•
Simulace
•
Zp¥tná propagace
Po dosaºení ukon£ující podmínky vrátí algoritmus tah, který povaºuje za nejlep²í, to znamená ten, který má nejlep²í pr·m¥rnou hodnotu hry. MCTS má n¥kolik výhod i nevýhod. Velkou výhodou je, ºe výsledek m·ºeme znát kdykoliv chceme. Ve chvíli, kdy zastavíme algoritmus, tak nám vºdy dá vybranou akci podle aktuálních hodnot. Nicmén¥ velkou nevýhodou m·ºe být práv¥ soust°ed¥ní procházení na slibné uzly. "This is quite a serious disadvantage.
αβ
searchers are from the nature of the
Minimax algorithm extremely good at revealing tactical shots. On the other hand, UCT tree search might simply overlook a deeper tactical combination because it doesn't allocate enough resources to a seemingly unyielding move near the root."[10]
1
1 P°eklad: Toto je pom¥rn¥ závaºná nevýhoda. αβ prohledáva£e jsou z jejich podstaty minimaxu extrémn¥ dobré v nalézání výhodné taktiky. Na druhou stranu 'UCT tree search' m·ºe jednodu²e "p°ehlédnout"hlub²í taktickou kombinaci, protoºe nev¥nuje dostatek zdroj· zdánliv¥ nevýhodnému tahu blízko ko°ene.
KAPITOLA 3.
11
ZNÁMÉ ALGORITMY
Obrázek 3.4: Pr·b¥h algoritmu MCTS
3.2.1
Selekce
B¥hem selekce vybere algoritmus jeden z list· stromu podle zadaného vzorce. Vzorec bere v úvahu hodnoty her jednotlivých potomk· a kolikrát byl který z nich nav²tíven. Pom¥rem mezi t¥mito parametry se nastavuje míra s jakou algoritmus zkoumá nové nebo málo zmapované v¥tve oproti jiº ²ir²ím v¥tvím se slibnými výsledky. Prochází p°es jednotlivé vrstvy stromu od ko°enu a v kaºdém uzlu postupuje níº p°es potomka vybraného tímto vzorcem. P°i implementaci tohoto algoritmu jsem pouºil následující vzorec p°i výpo£tu selekce p°evzatý z [2]:
s
vi + C ∗ kde
vi
ln N , ni
je odhadovaná hodnota daného potomka,
nav²tíven a
N
ni
(3.1)
je po£et, kolikrát byl tento potomek
je celkový po£et nav²tívení uzlu, ve kterém toto po£ítáme. C je konstanta,
kterou ovliv¬ujeme pom¥r mezi zp°es¬ováním výsledku ve více nav²t¥vovaných uzlech a mezi zkoumáním hor²ích, málo nav²tívených uzl·.
3.2.2
Expanze
Vybraný list stromu se následn¥ roz²í°í do dal²í vrstvy o nové potomky. K tomu slouºí zadaná funkce a pro teoretický popis MCTS nemá vliv. Kaºdému potomkovi je nastavena n¥jaká základní hodnota hry, která je vy²²í neº hodnoty získávané hrou. Tím dochází k tomu, ºe neº za£ne MCTS prohlubovat výpo£et z jednoho uzlu níºe, musí vyzkou²et jednou v²echny jeho potomky a aº poté vybere n¥který z nich podruhé.
3.2.3
Simulace
Z nov¥ vytvo°ených potomk· je jeden vybrán a z n¥j je spu²t¥na simulace hry, která vrátí o£ekávaný výsledek hry, nejlépe odehráním hry do terminálního stavu. Simulace by m¥la probíhat náhodným výb¥rem tah· obou hr᣷, aby se b¥hem v²ech simulací pokryl co nejv¥t²í prostor moºných pr·b¥h· hry.
KAPITOLA 3.
3.2.4
ZNÁMÉ ALGORITMY
12
Zp¥tná propagace
Výsledek ze simulace se uloºí do uzlu, ze kterého se simulace spustila, a následn¥ i do v²ech p°edch·dc· aº ke ko°enu stromu.
3.2.5
Známá pro°ezávání v MCTS
V¥t²ina jiº d°íve aplikovaných pro°ezávání v MCTS fungují na dvou principech: na postupném p°idávání nebo odebírání akcí, resp. potomk·, v uzlech. Ob¥ metody mají r·zné variace, ale li²í se spí²e v detailech, kdy a na které uzly pro°ezání aplikovat.
3.2.5.1 Progressive unprunning Tato metoda je zástupcem principu p°idávání akcí a funguje tak, ºe první zablokuje n¥které potomky v uzlu [4]. K zablokování potomk· m·ºe dojít ihned po jejich vytvo°ení vyuºitím n¥jakého heuristického odhadu kvality potomk· nebo po n¥kolika pr·chodech daným uzlem, kdy uº máme n¥jaké výsledky ze simulací. Zablokované uzly se v následujících iteracích nesmí prozkoumávat a tím pádem ani expandovat. Pozd¥ji v²ak n¥které uzly znovu otev°eme a dovolíme algoritmu dále expandovat strom skrze tyto uzly. Pokud tedy nav²tívíme uzel pouze n¥kolikrát, volíme generování men²ího stromu a pokud algoritmus tento uzel nav²tíví mnohokrát, dovolíme mu prohledat tímto sm¥rem v¥t²í £ást stromu. K pro°ezání dochází po n¥kolika pr·chodech. Po£et pr·chod· pot°ebných k pro°ezání je ur£en prom¥nnou ozna£ovanou jako treshold.
3.2.5.2 Postupné odebírání V této metod¥ za£ínáme s moºností zkoumat v²echny potomky v uzlu, ale po ur£itém mnoºství jich £ást zablokujeme, p°ípadn¥ blokování probíhá postupn¥. Ob¥ tyto metody mohou pouºívat r·zné zp·soby, jak ur£it uzly pro zablokování a kdy je ozna£it. Jako nejjednodu²²í se nabízí blokovat uzly ihned po jednom pr·chodu v²emi potomky na základ¥ vrácených hodnost nebo na základ¥ heuristické funkce. Nicmén¥ tímto zp·sobem bychom si mohli od°íznout potomky, kte°í by se pozd¥ji ukázali lep²í a hodni dal²ího zkoumání. M·ºeme tedy uzly zamykat postupn¥, pokud se ukáºe jejich hodnota i po ur£itém po£tu iterací znateln¥ hor²í neº v¥t²ina ostatních.
Kapitola 4
Lineární program V pr·b¥hu této práce vznikla modi kace algoritmu Double oracle zaloºená na pro°ezávání výpo£tu. Základem tohoto algoritmu je lineární program, dále jen LP, který se dá samotný vyuºít pro výpo£et herní strategie. Kdyº známe hodnoty jednotlivých tah·, které m·ºeme zahrát, lze vytvo°it rovnice lineárního programu tak, ºe nám spo£ítá hodnotu hry a smí²ené strategie obou hr᣷, které jsou v Nashov¥ ekvilibriu.
4.1
Nashovo Ekvilibrium
Nashovo ekvilibrium [7] je rovnováºný stav hry, kdy kaºdý hrᣠmá vybranou svou strategii a za p°edpokladu, ºe strategie ostatních hr᣷ jsou napevno dané (nezm¥ní se), nechce svou strategii zm¥nit. Jinými slovy je to nejlep²í odpov¥¤ na strategie ostatních. Pokud toto platí o v²ech hrá£ích, jedná se o Nashovo ekvilibrium.
4.2
Ryzí strategie
Ryzí strategie je strategie, která uvaºuje pouze jednu akci s pravd¥podobností v¥t²í neº nula. Pokud nastane rovnováºný stav a p°itom kaºdý hrᣠmá zvolenou £ist¥ jednu akci, jedná se o tzv. ryzí Nashovo ekvilibrium. Tento stav nemusí existovat v kaºdé h°e.
4.3
Smí²ená strategie
Smí²ená strategie je taková, která uvaºuje ve strategii více neº jednu akci s pravd¥podobností v¥t²í neº nula. M·ºe tedy obsahovat n¥kolik akcí, kaºdou hranou s r·znou pravd¥podobností. Op¥t lze najít vyváºený stav t¥chto strategií mezi v²emi zú£astn¥nými hrá£i. Na rozdíl od ryzího Nashova ekvilibria lze toto najít v kaºdé h°e de nované maticí. Nap°íklad p°i h°e kámen-n·ºky-papír je nejlep²í strategií volit kaºdý symbol se stejnou pravd¥podobností, tj. 1/3.
13
KAPITOLA 4.
4.4
14
LINEÁRNÍ PROGRAM
Tvorba lineárního programu
K vytvo°ení LP m·ºeme pouºít stage se zobrazením simultánních tah·. Ta je vid¥t nap°íklad na obrázku 3.3. Vzhledem k tomu, ºe algoritmus Double oracle po£ítá se strategiemi obou hr᣷, pot°ebujeme z výsledku lineárního programu získat pravd¥podobnostní rozloºení akcí obou hr᣷. To m·ºeme získat pomocí duálních prom¥nných, které umoº¬ují po výpo£tu pravd¥podobnostního rozloºení získat i hodnoty pro druhého hrá£e. LP se skládá z n¥kolika blok· rovnic [11]. První jsou rovnice, které postihují hodnoty ve stage. Za kaºdý tah, který m·ºe soupe° ud¥lat, budeme mít jednu rovnici. Tato rovnice se skládá ze sou£tu prom¥nných Kaºdé
xi
xi ,
kde kaºdá prom¥nná
je je²t¥ vynásobeno hodnotou hry
související s daným
x
values,
x
zastupuje jednu hrá£ovu akci.
kterou ve stagi de nuje hrá£ova akce
a soupe°ova akce de novaná rovnicí. V²echny tyto rovnice jsou pak
poloºeny rovno nebo v¥t²í dal²í prom¥nné, kterou ozna£uji
v.
Toto platí pouze v p°ípad¥, ºe
tvo°íme LP pro maximalizujícího hrá£e, v p°ípad¥ minimalizujícího hrá£e poloºíme rovnice rovné nebo men²í
v.
Obecn¥ tedy rovnice popisující stage vypadají pro maximalizujícího
hrá£e takto:
x1 ∗ values11 + x2 ∗ values21 + ... + xi ∗ valuesi1 ≥ v, x1 ∗ values12 + x2 ∗ values22 + ... + xi ∗ valuesi2 ≥ v, ... x1 ∗ values1j + x2 ∗ values2j + ... + xi ∗ valuesij ≥ v, kde
i
je po£et akcí maximalizujícího hrá£e a
j
je po£et akcí jeho soupe°e.
v bude na konci výpo£tu hodnota hry a uvedené rovnice mají za úkol rozloºit jednotlivých tah· tak, aby v bylo co nejv¥t²í, resp. co nejmen²í. Protoºe prom¥nné xi
V prom¥nné podíl
zastupují pravd¥podobnost hraní akcí, musíme p°idat pro kaºdou prom¥nnou rovnici, která °íká, ºe tato prom¥nná musí být nezáporná hodnota.
xi ≥ 0 Poslední rovnicí pak musíme °íct, ºe sou£et t¥chto pravd¥podobností musí být 1.
x1 + x2 + ... + xi = 1 Nakonec uº se jen musí speci kovat, jestli chceme prom¥nnou
v
maximalizovat nebo
minimalizovat. Vytvo°ení lineárního programu je²t¥ ukáºi na p°íkladu. V tabulce 7.1 jsou vid¥t hodnoty stage, kterou pouºiju pro vytvo°ených rovnic lineárního programu. Kaºdý sloupec reprezentuje jeden tah, který m·ºe ud¥lat maximalizující hrᣠa kaºdý °ádek reprezentuje jeden tah minimalizujícího hrá£e. Tabulka pak ukazuje hodnotu, kterou bude mít hra, pokud hrá£i zahrají p°íslu²né tahy. Následují rovnice vytvo°ené z této tabulky. První dv¥ rovnice mají za úkol donutit lineární program rozpo£ítat pravd¥podobnostní rozloºení akcí
xi
tak, aby mohlo být
tím souvisí poslední rovnice, která °íká, ºe chceme prom¥nnou
v
v
co nejv¥t²í. S
maximalizovat. Tato pro-
m¥nná reprezentuje hodnotu hry v tomto uzlu. Chceme tedy, aby lineární program dosadil za
KAPITOLA 4.
15
LINEÁRNÍ PROGRAM
Min/ Max 1 2 3 1 8 2 1 2 7 6 12 Tabulka 4.1: Tabulka s hodnotami pro výpo£et lineárního programu
prom¥nné
xi
tak, aby byla hodnota co nejv¥t²í. Pro minimalizujícího hrá£e bychom prom¥n-
nou v minimalizovali. Zbylé rovnice, tj. rovnice 2.3 aº 2.6, pouze omezují hodnoty, kterých m·ºou prom¥nné
xi
nabývat. Vzhledem k tomu, ºe mají reprezentovat pravd¥podobnost,
musí dohromady být rovné 1 a ºádná nesmí být záporná.
4.5
8x1 + 2x2 + x3 ≥ v
(4.1)
7x1 + 6x2 + 12x3 ≥ v
(4.2)
x1 ≥ 0
(4.3)
x2 ≥ 0
(4.4)
x3 ≥ 0
(4.5)
x1 + x2 + x3 = 1
(4.6)
maximalize(v)
(4.7)
Double oracle
Tento algoritmus funguje na principu postupného p°idávání tah· obou hr᣷ do výpo£tu lineárního programu. Na za£átku výpo£tu pro kaºdý stav vezmeme pouze jednu akci kaºdého hrá£e. Tím nám vznikne jednoduchý lineární program, ze kterého vyjde pravd¥podobnostní rozloºení 1 pro ob¥ akce. Poté kaºdý hrᣠp°idá k výpo£tu jednu akci, o které si myslí, ºe pro n¥j zlep²í podmínky. Vybrané akci pro p°idání do výpo£tu °íkáme best response, coº v p°ekladu znamená nejlep²í odpov¥¤. Best response pro kaºdého hrá£e najdeme tak, ºe zkusíme spo£ítat hodnotu hry za stávajícího pravd¥podobnostního rozloºení tah· protihrá£e a p°i pouºití ostatních na²ich akcí. Pokud ºádná nová akce hodnotu nezlep²í, ºádnou akci do výpo£tu nep°idá. S nov¥ p°idanými akcemi vytvo°íme znovu lineární program podle návodu vý²e a získáme nové pravd¥podobností rozloºení akcí obou hr᣷. Výpo£et kon£í ve chvíli, kdy ani jeden hrᣠnechce p°idat novou akci. M·ºeme vrátit hodnotu hru nebo pravd¥podobností rozloºení tah·. Tímto zp·sobem musíme pustit lineární program víckrát, i kdyº bychom se v²emi hodnotami mohli spustit pouze jeden úplný výpo£et. Nicmén¥ takto v¥t²inou skon£í
KAPITOLA 4.
16
LINEÁRNÍ PROGRAM
výpo£et d°íve neº doplníme celý lineární program a nejnáro£n¥j²í na celém výpo£tu jsou rekurzivní volání do v¥t²ích hloubek, které pot°ebujeme kv·li získání hodnot her do stage tabulky. Ve výsledku tedy po£ítáme lineární program víckrát, ale v¥t²inou u²et°íme £as. [8]
4.5.1
Best response
Algoritmus best response má za úkol z pravd¥podobnostního rozloºení akcí soupe°e a hodnot her pro v²echny moºné kombinace akcí obou hr᣷ vybrat jednu svou akci, která má nejlep²í výsledek. Výsledná hodnota je sou£et díl£ích hodnot pro kaºdou soupe°ovu akci. Díl£í hodnoty jsou produktem pravd¥podobnosti akce soupe°e a hodnotou hry pro danou kombinaci na²í a soupe°ovi akce.
hi =
n X
HodnotaHry(i, j) ∗ xj
(4.8)
j=0 Rovnice 2.8 ukazuje, jak vypadá výpo£et best response akce. Prom¥nná hodnotu jedné akce, prom¥nné
i
a
j
hi
reprezentuje
reprezentují tahy obou hr᣷. Postupn¥ tuto rovnici
spo£ítáme pro v²echny akce hrá£e a vybereme z nich tu nejlep²í, pro maximalizujícího hrá£e s maximální hodnotou
h,
pro minimalizujícího hrá£e s minimální hodnotou. Hodnota akce
je sumou hodnot her, vºdy korespondující s vybranými akcemi obou hr᣷. Kaºdá hodnota hry je navíc vynásobena pravd¥podobností, s jakou soupe° p°íslu²nou akci zahraje. Výhodou p°i výpo£tu je, ºe pro akce, které soupe° hraje s pravd¥podobností 0, nepot°ebujeme znát hodnotu hry a do rekurzivního výpo£tu posíláme pouze stavy, které je²t¥ neznáme a které nutn¥ pot°ebujeme pro výpo£et.
4.5.2
Odhad pomocí minimaxu
Pro zrychlení výpo£tu best response je moºné pouºít odhadování neznámých výsledk·, protoºe rekurzivní výpo£ty pomocí lineárního programu trvají déle. První se musí odhadnout hodnota nové akce a pokud je odhad hor²í neº dosud nejlep²í akce, která je v rámci best response nalezena, tak je zbyte£né po£ítat p°esnou hodnotu. Pokud by byl odhad hor²í neº p°esná hodnota, mohl by být od°íznut výpo£et vedoucí k lep²í akci. Proto je nutné mít odhad optimistický, který zaru£í, ºe od°íznutá hodnota nemohla být lep²í. Vzhledem k tomu, ºe je to hra se simultánními tahy a kaºdý stav je reprezentován pomocí stage, je moºné pro odhad pouºít serializovaný Minimax, který vrací optimistickou hodnotu. Tento algoritmus je popsaný vý²e.
4.5.3
Od°ezávání b¥hem odhadu
Pokud je b¥hem po£ítání odhadu pouºit upravený Minimax o Alpha-beta pro°ezávání, lze p°edat algoritmu na za£átku rovnou n¥jaké podmínky na výsledek a to tak, ºe je spu²t¥na Alpha-beta s nulovým oknem (alpha a beta nastavené na stejnou hodnotu). Pokud p°i prohledávání dojde k alpha £i beta pro°íznutí, vrátí nalezenou hodnotu, v opa£ném p°ípad¥ vrátí zadanou hodnotu. Tím se odhalí, zda m·ºe mít tato akce lep²í hodnotu neº aktuáln¥ vybraná best response. Moºnost tohoto od°ezání plyne z výpo£tu pro hodnotu akce.
KAPITOLA 4.
LINEÁRNÍ PROGRAM
17
Z rovnice 2.8 je vid¥t, ºe se postupn¥ s£ítají hodnoty her vynásobené pravd¥podobností s jakou se k té hodnot¥ hra dostane (tj. pravd¥podobností se kterou bude soupe° hrát korespondující akci). P°i výpo£tu se tedy m·ºe postupn¥ spo£ítat, kolik je pot°ebná hodnota hry pro dané akce, aby byla lep²í neº dosavadní best response. Za hodnoty her, které je²t¥ nejsou spo£ítané je nutné dosadit maximální moºnou hodnotu. Dá se tedy p°edpokládat ºe pro°ezávání bude tím efektivn¥j²í, £ím více akcí soupe° má ve své strategii a s postupujícím výpo£tem.
Kapitola 5
Hra Planet Wars 5.1
O h°e
Planet Wars je strategická hra pro dva hrá£e, která se odehrává ve vesmíru. Kaºdý hrᣠmoºnost posílat lod¥ ze svých planet na ostatní. Na za£átku má kaºdý hrᣠk dispozici jednu planetu s ur£itým po£tem lodí, pozd¥ji m·ºe mít planet víc. Kaºdá planeta je de nována n¥kolika parametry, kterými jsou: produkce, poloha, aktuální po£et lodí a vlastník. Produkce udává, kolik planet kaºdé kolo p°ibude lodí, ale pouze pokud planetu ovládá n¥který z hr᣷. Neutrálním planetám tedy lod¥ nep°ibývají. Poloha je ur£ena dv¥ma sou°adnicemi, hra probíhá ve dvou rozm¥rech. Vlastník planety m·ºe být n¥který z hr᣷ nebo m·ºe být planeta neutrální. Pomocí sou°adnic jednotlivých planet se dá spo£ítat, jak dlouho lod¥ z jedné planety na druhou poletí. Spo£tená vzdálenost mezi planetami se diskretizuje na po£et tah·. V jednom kole m·ºe kaºdý hrᣠvyslat libovolné mnoºství letek, ale nesmí nikdy poslat více lodí neº má na planetách. Pro kaºdou letku musí ur£it startovní planetu, cílovou planetu a po£et lodí, které chce vyslat. P°i potvrzení svého tahu se p°epo£te letová doba v²ech letek a do pam¥ti se uloºí, kolik kol jim bude trvat, neº dorazí do cíle. Hra kon£í ve chvíli, kdy jeden z hr᣷ nemá ºádnou planetu ani letku nebo po 1000. kole hry. V prvním p°ípad¥ vyhrává hrá£, který je²t¥ planetu nebo letku má. V druhém p°ípad¥ se spo£ítají lod¥ obou hr᣷ na planetách a v letkách a vyhrává ten, který má lodí víc. Pro velké mnoºství moºností, jak by mohli oba hrá£i hrát, jsem pravidla pro své pot°eby mírn¥ zjednodu²il. V kaºdém kole dovolím hr᣷m vyslat pouze jednu letku a tím se rapidn¥ sníºí branching faktor hry. P°esto z·stane hodn¥ veliký, jak je vid¥t pozd¥ji b¥hem experiment·.
5.2
Zdroj
Tento typ hry je pom¥rn¥ známý a roz²í°ený, existuje velké mnoºství verzí této hry, p°edev²ím ve form¥ ashových her na internetu. Pro tuto práci byla vybrána práv¥ hra Planet Wars, která byla na podzim roku 2010 tématem Google AI Challange [3]. Výhodou je, ºe podle pravidel hry bylo moºné napsat vlastní simulátor a kontrolovat tak pr·b¥h celé hry a mohly být snadno vytvo°ené vlastní mapy s mén¥ planetami (mapy jsou uloºeny v textových
18
KAPITOLA 5.
HRA PLANET WARS
19
souborech). P·vodní pravidla dovolují maximáln¥ 1 vte°inu na odpov¥¤, coº nebylo vzhledem k testování £asové sloºitosti vhodné. Pln¥ vyuºit mohl být vizualizátor hry dostupný ke staºení. Ten také p°ijímá textový vstup a není problém p°i výpo£tu ve vlastním simulátoru vygenerovat výstup, který m·ºe být p°ehrán v tomto vizualizátoru a lze tak zobrazit p°íslu²nou hru. Tento výstup musí být v textovém formátu, kde kaºdý tah je odd¥lený st°edníkem. V rámci kaºdého tahu musí být seznam v²ech planet, jejich majitelé a kolik je na nich lodí. Rozmíst¥ní planet je na za£átku celého souboru a protoºe se v rámci hry nem¥ní, sta£í tato informace pouze jednou. V kaºdém tahu pak musí být i vý£et jednotlivých letek, koho lod¥ jsou a jak jsou daleko na své cest¥ a kolik lodí letí.
Obrázek 5.1: Ukázka vizualizátoru a mapy se 7 planetami
Na obrázku vizualizátoru 5.1 je vid¥t ukázka ze hry na map¥ se sedmi planetami. Konkrétn¥ tato situace je ze hry LP bota proti expandujícímu botovi. LP bot má v této h°e £ervenou barvu. ísla na planetách jsou po£ty lodí, které na planetách jsou, barevná £ísla v prostoru mezi planetami jsou letky pat°ící hrá£i s p°íslu²nou barvou. Sm¥r, kterým lod¥ letí není vid¥t, ani cílová planeta. Sm¥r je poznat p°i krokování hry, kdy jsou £ísla v kaºdém kroku posunuty blíº ke svému cíli. V situaci na obrázku letí v²echny lod¥ na planetu vpravo naho°e. Dal²í obrázek 5.2 pak ukazuje mapu s jedenácti planetami. Op¥t je to rozehraná hra mezi LP botem a expandujícím botem. ervenou barvu má zase LP bot a je to situace ke konci hry. Jak je vid¥t, je zde situace mnohem nep°ehledn¥j²í. Nap°íklad hodn¥ zelených lodí na levé stran¥ mapy mí°í na planetu, která je úpln¥ vlevo. Na té planet¥ je nyní pom¥rn¥ hodn¥ lodí a letí na ní £ervené posily, takºe aº dorazí zelené lod¥, tak nebudou mít dostate£nou sílu
KAPITOLA 5.
HRA PLANET WARS
Obrázek 5.2: Ukázka vizualizátoru a mapy s 11 planetami
na dobytí této planety.
20
Kapitola 6
Implementace Celá implementace programu se skládá z n¥kolika £ástí. První velkou £ástí jsou dv¥ t°ídy, které tvo°í kostru programu. Jedná se o Simulátor a Experimentátor. První zmín¥ná t°ída obsluhuje simulace her, Pomocí dvou bot· a zadaného stavu hry odehraje celou hru do terminálního stavu a vrátí výsledek. Druhá zmín¥ná t°ída pak obsluhuje nejd·leºit¥j²í £ást vybírá boty, na£ítá mapy a p°es Simulátor spou²tí jednotlivé bitvy. Dal²í velkou £ástí je reprezentace sv¥ta Planet Wars rozd¥lená do n¥kolika t°íd. Poslední v¥t²í £ástí jsou samostatné t°ídy reprezentující jednotlivé boty.
6.1 6.1.1
Spou²t¥ní programu Simulátor
Simulátor spojuje dohromady t°ídy vytvo°ené k reprezentaci sv¥ta a vyuºívá jich k simulaci celé hry mezi dv¥ma boty a je sou£ástí Experimentátoru. Simulátor dostává jako argument stav hry a dva boty, kte°í mají mezi sebou odehrát hru. Pak v cyklu vºdy na kaºdého bota zavolá metodu pro získání jeho tahu a ob¥ akce aplikuje na stav hry. Nakonec na stav zavolá metodu, která posune stav sv¥ta do dal²ího kroku. Simulace kon£í ve chvíli, kdy ve h°e prob¥hl maximální po£et tah·, který je nastaven na 1000 krok· nebo dokud jeden z hr᣷ nevyhrál, coº nastane ve chvíli, kdy jeden hrᣠnemá ºádnou planetu ani ºádnou letku. Toto si hlídá t°ída State a sta£í se jí zeptat. Pokud vít¥z neexistuje po 1000 krocích hry, hra se zastaví a vít¥z je ur£en podle pom¥ru lodí obou hr᣷. Navíc p°i kaºdém volání výpo£tu bota m¥°í £as, který daný bot pot°ebuje k vyhodnocení jeho akce. Tento £as ukládá do pam¥ti, kde na konci programu najdeme celkový £as kaºdého bota, který pot°eboval celkem k výpo£tu v²ech tah· p°i v²ech hrách. Vyd¥lením této hodnoty po£tem tah·, které daný bot ud¥lal, lze získat pr·m¥rnou hodnotu jednoho výpo£tu.
6.1.2
Experimentátor
Tato t°ída spou²tí hry mezi boty a ukládá statistiky zápas·. Spou²tí se metodou, která jako argument p°ijímá po£et zápas· mezi kaºdými dv¥ma boty. Dále vytvo°í pole bot·, které má mezi sebou porovnat a spustí samotný experiment. Ten probíhá tak, ºe postupn¥ spou²tí
21
KAPITOLA 6.
IMPLEMENTACE
22
zápasy kaºdého bota s kaºdým. Mezi dv¥ma boty pak prob¥hne zadaný po£et zápas·. Dále je moºné nastavit r·zné mapy pro kaºdou hru a vyzkou²et tak protivníky v r·zných situacích. V t°íd¥ lze také najít dv¥ funkce pro export stavu a tah· hry do textového souboru, který lze následn¥ otev°ít ve vizualizátoru a podívat se tak na hru v gra cké podob¥.
6.2 6.2.1
Node Úvod
T°ída Node má reprezentovat jeden uzel v algoritmech pro výpo£et tah· bot·. Tento uzel má jednak v sob¥ uloºen stav hry, ale i mnoho dal²ích parametr· a metod. Obsahuje vý£et jednotlivých akcí, které mohou oba dva hrá£i za daného stavu hry ud¥lat. Pro algoritmus MCTS si zde pamatuje po£ty pouºití kaºdého hrá£ova moºného tahu. Tato hodnota je v MCTS pot°eba k ur£ování akce, kterou aplikuje hrᣠv kaºdém cyklu algoritmu. Dále je tu kv·li stejnému výpo£tu uloºena hodnota ozna£ující kvalitu kaºdé akce. Jsou zde uloºeny identi kátory akcí, které pouºily oba dva hrá£i v minulém kole, a odkaz na v²echny uzly, které jsou potomky tohoto. Zárove¬ také obsahuje odkaz na rodi£e tohoto uzlu, ko°enový uzel pak má na tomto míst¥ nulovou hodnotu.
6.3
Generování akcí
V této t°íd¥ se generují akce obou hr᣷, které jsou pak pouºity p°i výpo£tech jednotlivých algoritm·. V pr·b¥hu implementace vznikly dva p°ístupy ke generování akcí. První metoda generuje v²echny moºné akce obou hr᣷ v rámci planet. Po£et vyslaných lodí vypo£ítá podle obou planet, jak startovní, tak cílové. Akce jsou generovány na základ¥ stavu hry. Vytvo°í je pro oba hrá£e a uloºí do svých prom¥nných. Akce pro jednoho hrá£e jsou vytvo°eny následujícím zp·sobem. První si uloºí do seznamu v²echny planety generovaného hrá£e. Pro kaºdou planetu pak vytvo°í akce takové, ºe zdrojová planeta pro letku je aktuální planeta a cílové planety budou postupn¥ v²echny ostatní ve h°e. Pokud má tedy hrᣠ3 planety z celkového po£tu 8 planet, pak tímto zp·sobem vytvo°í 3x7, tedy 21, akcí. Kaºdá akce v²ak má mít je²t¥ parametr, kolik lodí tímto sm¥rem posíláme. V tomto p°ípad¥ je to bu¤ tolik lodí, kolik je aktuáln¥ pot°eba k obsazení cílové planety tedy pokud je na cílové planet¥ 10 lodí, sta£í jich poslat 11 a poslední p°eºiv²í kosmická lo¤ obsadí planetu. Pokud je cílová planeta soupe°ova, pot°ebuje je²t¥ o n¥co více lodí a to o tolik, kolik stihne vyprodukovat tato planeta lodí za dobu, neº tam hrá£ova letka doletí. Pokud nemá planeta dostatek lodí na to poslat pot°ebné mnoºství nebo je planeta stejného hrá£e, je v letce poslána polovina lodí z mnoºství, které je na planet¥. Nakonec je vytvo°ena je²t¥ jedna akce navíc a to prázdná akce, protoºe není nutnost poslat letku v kaºdém kole. Pokud se akce generovali v rámci výpo£tu MCTS, tak po jejich vytvo°ení metoda inicializuje potomky a p°edá jim upravené stavy hry s aplikovanými p°íslu²nými akcemi obou hr᣷. Potomk· bude produkt po£tu akcí obou hr᣷, tedy pokud kaºdý hrᣠmá k dispozici 20 akcí, tak potomk· bude 20*20, tedy 400. Kvalitativní hodnota akcí je pak nastavena na nejvy²²í moºnou hodnotu hru s náhodným p°ídavkem. D·vody pro toto nastavení jsou popsány v teorii algoritmu. Ve zkratce lze °íct, ºe maximální hodnota hry je zde kv·li
KAPITOLA 6.
IMPLEMENTACE
23
p°ednostnímu prozkoumání kaºdé akce p°ed op¥tovným pr·chodem n¥které z akcí. Náhodná p°idaná hodnota je zde kv·li tomu, aby se v kaºdé vrstv¥ vybíraly generované akce v r·zném po°adí, tedy aby se v kaºdé vrstv¥ generovaného stromu první neprocházela první akce v poli, coº je v tomto p°ípad¥ prázdná akce (hrᣠneposílá ºádnou letku). Dal²ím p°ístupem ke generování akcí je od°íznout n¥které z akcí jiº ve fázi jejich generování. Tato metoda se v mnohém podobá p°edchozí popsané. Její smysl je ale v tom, ºe na rozdíl od p°edchozí metody generuje men²í mnoºství akcí pro hrá£e. To je pot°eba kv·li tomu, ºe na v¥t²ích mapách, °ádov¥ 20 planet, m·ºe mít b¥hem pár kol kaºdý hrᣠkolem 5ti planet. P°edchozí metoda v tomto p°ípad¥ kaºdému hrá£i vygeneruje skoro 100 moºných akcí a to znamená 10000 potomk·. Pokud budeme zkou²et strom prohledávat hloub¥ji, brzy budou pam¥´ové nároky p°íli² velké pro v¥t²inu po£íta£·. Tato metoda tedy vezme pouze £ást hrá£ových planet, £ást soupe°ových a £ást neutrálních a vytvo°í akce pouze v tomto zredukovaném sv¥t¥. Kaºdá vybraná mnoºina planet je vytvo°ena tak, ºe n¥kolik planet se vybere podle n¥jakého kritéria a zbytek doplníme náhodn¥ vybranými planetami, aby se v pr·b¥hu n¥kolika kol m¥ly ²anci ukázat ve výb¥ru v²echny planety. Kritérii pro výb¥r planet jsou pak po£ty lodí. Do hrá£ových planet vybereme planety s nejvíce lod¥mi, tedy nejsiln¥j²í planety. Z neutrálních a soupe°ových pak naopak vybíráme nejslab²í planety, tedy s nejmén¥ lod¥mi.
6.4
Fitness
Dále pak v této t°íd¥ musí být metoda pro p°epo£ítání kvalitativní hodnotu daných akcí podle výsledku ze simulace hry p°i jejich zahrání. Jako parametry dostává identi kátor akcí obou hr᣷, které má upravit a výsledek simulace. Z výsledku, dosavadní kvality akce a celkového po£tu pokus· hrát tuto akci spo£ítá novou kvalitu. Tato funkce se uplatní p°i výpo£tu algoritmu MCTS.
6.5
Selekce
Poslední metodou, op¥t vyuºitelnou v algoritmu MCTS, je metoda pro vybrání potomka pro dal²í zkoumání. Tato metoda dostává jako argument stav hry. Nepot°ebuje ho k výpo£tu, ale aplikuje na n¥j vybrané akce obou hr᣷. Akce jsou vybírány podle kvalitativní hodnoty akcí, vybrané akce jsou aplikovány na p°edaný stav hry a metoda vrací svého potomka s vybranými aplikovanými akcemi.
6.6
Planet Wars
Implementace sv¥ta Planet Wars se skládá z t°íd reprezentujících planetu, letku, akci a stav sv¥ta a tvo°í tak kompletní reprezentaci celého sv¥ta. Podrobn¥ji jsou tyto t°ídy popsány níºe.
KAPITOLA 6.
6.6.1
IMPLEMENTACE
24
Planet
Tato t°ída reprezentuje jednu planetu ve sv¥t¥ Planet Wars. Nejd·leºit¥j²ími atributy jsou £íslo planety, majitel planety, po£et lodí p°ítomných na planet¥ a kolik planeta vyprodukuje lodí za jeden herní tah. Tato t°ída obsluhuje tyto události:
•
Posun planety v £ase o jeden tah dál, tzn. na planetu p°idá lod¥ podle její produkce.
•
Odeslání lodí z planety, resp. jejich ode£tení, kdyº hrᣠz planety vy²le letku.
•
P°ijímání lodí, které p°ilétají na planetu v£etn¥ vy°e²ení p°ípadných boj· a dal²ích p°ípad·, které mohou nastat po p°íletu lodí na planetu.
•
Vy°e²it nejd·leºit¥j²í d¥ní na planet¥ bitvy. Podle majitele planety, lodí na planet¥, lodí úto£ících na planetu (lod¥ mají jiného majitele neº planeta) a lodí letících planet¥ na pomoc (lod¥ mají stejného majitele jako planeta a p°ilet¥ly z jiné planety) ur£it, kdo je nový majitel planety (pokud se zm¥nil) a kolik na ní bude ve výsledku lodí. P°ed koncem kaºdého tahu by se m¥la tato metoda zavolat na kaºdé planet¥, na kterou p°ilet¥la n¥jaká letka.
6.6.2
Fleet
Tato t°ída reprezentuje letky lodí, které letí mezi planetami. Obsahuje informace o majiteli a po£tu lodí, z které a na kterou planetu letí a jak daleko jsou na své cest¥. V této t°íd¥ jsou metody pro práci s letkou a musí obslouºit následující situace:
•
Ud¥lat jeden tah s letkou, tzn. posunout jí o jeden krok blíºe k jejímu cíli. V d·sledku to znamená, ºe zmen²í po£et tah· pot°ebných do cíle o jedna.
•
Kontrola, zda letka dorazila do cíle. Tato metoda pouze vrátí boolean prom¥nou, zda uº letka dosáhla svého cíle nebo ne.
6.6.3
Action
Tato t°ída reprezentuje akce, které se dají provést ve sv¥t¥ Planet Wars. Kaºdá akce je p°íkaz k vyslání n¥jakého po£tu lodí z planety na planetu. Tedy informace, které jsou obsaºeny v této t°íd¥ jsou po£áte£ní a cílová planeta a po£et lodí, které chce hrᣠmezi t¥mito planetami poslat. Kaºdý hrᣠm·ºe posílat lod¥ pouze ze svých planet. Tato t°ída nemá ºádné speciální metody, pouze konstruktor, getry na v²echny parametry a metodu pro tisk akce do konzole.
6.6.4
State
Tato t°ída reprezentuje celý sv¥t Planet Wars. Obsahuje v²echny planety a letky. Udrºuje p°ehled o tom, jaké planety má který hrá£, a o vzdálenostech mezi planetami. Dále je zde uloºeno £íslo tahu a obsahuje parametr, který ur£uje jak velkou m¥rou se promítá produkce planet obou hr᣷ do hodnoty hry. M¥la by mít tyto metody:
KAPITOLA 6.
•
IMPLEMENTACE
25
Metodu, která má za úkol posunout v²e ve h°e o jeden tah dop°edu. Ud¥lá tedy tah se v²emi planetami a letkami. Pokud letka dorazila do cíle, tak na planetu ur£ené cílem letky tuto letku umístí.
•
Metodu, která akci jednoho z hr᣷ aplikuje na stav hry. Planet¥, ur£enou akcí, °ekne, ºe z ní byly poslány lod¥. Pak podle akce vytvo°í novou letku (t°ída Fleet) a uloºí si jí do seznamu.
•
Metodu, která vrátí £íslo hrá£e, který vyhrál, pokud v dané chvíli je n¥jaký vít¥z. Ten je vrácen touto metodou pouze ve chvíli, kdy jeden hrᣠvyhraje p°ed vypr²ením £asového limitu hry. To znamená, ºe n¥jaký hrᣠzlikvidoval toho druhého. Pokud ºádný vít¥z je²t¥ není, vrátí metoda £íslo 0.
6.6.4.1 Výpo£et hodnoty hry Tato t°ída obsahuje n¥kolik metod pro výpo£et hodnoty hry. První metoda po£ítá hodnotu hry pouze jako pom¥r lodí obou hr᣷ v aktuálním stavu. Je to jednoduché porovnání a ºádným zp·sobem nerozli²í hodnotu na základ¥ práv¥ odehraných akcí. Druhá metoda bere tohle v úvahu a neº vrátí pom¥r lodí obou hr᣷, tak odehraje n¥kolik dal²ích kol, dokud nedorazí v²echny letky na cílové planety. Tato kola v²ak b¥ºí pouze naprázdno, tzn. ºe hrá£i neposílají dal²í lod¥. Tento jednoduchý p°ístup má dát moºnost uvaºovat bot·m do budoucna. Nicmén¥ tento zp·sob výpo£tu hodnoty hry se ukázal jako ²patný, protoºe p°i dobývání planety hrᣠztratí n¥jaké lod¥ a z tohoto pohledu byla letka, která dorazila do cíle p°ed výpo£tem pom¥ru lodí, zna£n¥ nevýhodná. Zap°í£inila totiº úbytek lodí hrá£e a tím se projevila negativn¥ ve spo£tené hodnot¥ hry. P°edev²ím se negativní d·sledek projeví na poslední vyslané letce, coº je poslední akce, kterou hrᣠud¥lal a tím pádem by m¥la reprezentovat hodnotu této akce. Poslední metoda p°ijímá parametr, který udává, kolik kol má je²t¥ ub¥hnout, neº vypo£ítá hodnotu hry. Na rozdíl od p°edchozí metody lze nastavit tak, aby se projevily i nov¥ získané planety. Je pot°eba v²ak nastavit rozumn¥ po£et kol k odehrání p°ed výpo£tem hodnoty hry. Pokud se nastaví p°íli² malá hodnota, neprojeví se v²echny letky na cest¥ a nastane stejný efekt jako v první variant¥. Pokud bude po£et kol moc velký, zvy²ujeme d·raz na získávání planet a lehce idealizujeme celý herní sv¥t, protoºe o planetu m·ºeme p°ijít po útoku druhého hrá£e nebo skon£í hra a hodnota je pak p°íli² optimistická. Pokud úto£í hrᣠna neutrální planetu, pak je samotný útok nevýhodný (p°ijde o lod¥ p°i boji), ale získá produkci, která mu vrátí ztracené lod¥ za n¥jaký £as. V pr·m¥ru hlídá planety tolik lodí, kolik jich daná planeta vyprodukuje za 10 kol, takºe aby se projevilo zabrání neutrální planety jako výhodné, musí se odehrát více kol neº kolik bude trvat v²em letkám docestovat. Ukázalo se výhodné nastavit po£et kol na 15 plus nejdel²í vzdálenost mezi planetami. Je to £íslo, které dostate£n¥ zvýhodní zabírání planet a zárove¬ nedonutí bota zaúto£it na planetu s velkou ochrankou a zanedbatelnou produkcí. V p°ípad¥ zabrání soupe°ovi planety se akce projeví mnohem rychleji, protoºe soupe° p°i obran¥ planety p°ijde o stejný po£et lodí jako ztratíme útokem, produkce lodí se tedy projeví hned dvojnásobným efektem nám produkce p°ibude a soupe° jí ztratí.
KAPITOLA 6.
6.7
IMPLEMENTACE
26
Implementace bot·
Kv·li snadnému spou²t¥ní her mezi r·znými boty bylo pot°eba zavést jednotnou podobu v²ech bot·. Je zde tedy pro simulace zavedena abstraktní t°ída bota SimulatorBotAbstract. Kaºdá t°ída implementující abstraktní t°ídu musí obsahovat tyto funkce:
•
chooseAction(state, player)
Tato metoda dostane aktuální stav hry a hrá£e, který má zvolit sv·j tah. Má spustit výpo£et p°íslu²ného bota a vrátit akci, kterou chce zahrát.
•
getName()
Tato metoda má vrátit °et¥zec se jménem bota, které se pouºije jako identi kátor p°i simulacích.
•
metoda getNodesGenerated()
Tato metoda má po výpo£tu vrátit, kolik uzl· se stavem hry bylo vygenerováno botem p°i výpo£tu jeho tahu. Po£et vygenerovaných uzl· je pouºit jako jeden z parametr·, které sleduji p°i experimentech.
Kaºdý algoritmus má pak vytvo°enou svou t°ídu bota, která spustí p°íslu²ný algoritmus se správnými hodnotami.
6.8
Minimax
Tato t°ída má dv¥ d·leºité metody. První z nich spou²tí výpo£et algoritmu Minimax a druhá spou²tí Minimax s p°idaným Alpha-beta pro°ezáváním.
6.8.1
Stage Minimax
Na rozdíl od klasické podoby minimaxu popsané v 3.1 musel být algoritmus upraven. Pro implementaci Minimaxu na hodnotách ve form¥ stage je pozm¥n¥n následujícím zp·sobem.
1 double stageMM(node, d){ 2 if (node is a terminal node or d <= 0){ 3 return the heuristic value of node 4 } 5 maxValue = -infinity 6 for (each action of maxPlayer){ 7 minValue <- +infinity 8 for (each action of minPlayer){ 9 minValue <- Min(minVal, stageMM(child[maxPlAct,minPlAct],d-1)) 10 } 11 maxValue <- max(maxValue, minValue) 12 } 13 return maxValue 14 }
KAPITOLA 6.
IMPLEMENTACE
27
V pseudokódu je ukázané, jak získat hodnotu z pohledu maximalizujícího hrá£e. Pokud je pot°eba získat akci, kterou p°íslu²ný hrᣠchce zahrát podle Minimaxu, tak se musí b¥hem výpo£tu ukládat nejen nejlep²í hodnota, ale také akce, která tuto hodnotu m¥la. V p°ípad¥, ºe hraje minimalizující hrá£, je nutné pouºít upravený kód, který provede výpo£et pro minimální hodnotu. Metoda pro výpo£et Minimaxu p°ebírá stav hry, ze kterého má za£ít výpo£et, maximální hloubku prohledávání a pro kterého hrá£e má najít akci, kterou by m¥l hrát. Tato metoda na za£átku nechá první vygenerovat akce obou hr᣷. Pak v cyklu postupn¥ aplikuje akce obou hr᣷ na aktuální stav a spou²tí rekurzivní výpo£et, který kon£í p°i dosaºení maximální dovolené hloubky prohledávání. Výpo£et probíhá pro v²echny moºné kombinace v²ech akcí obou hr᣷ a na konci vrátí akci, která má ze v²ech akcí zvoleného hrá£e nejlep²í výsledky. To znamená, ºe se vrátila pro tuto akci nejlep²í hodnota hry (pro maximalizujícího hrá£e to bude nejvy²²í). Pokud je výpo£et v rekurzi, nevrací akci, ale hodnotu hry, kterou získal aplikováním t¥ch akcí obou hr᣷, které pro kaºdého hrá£e mají nejlep²í hodnotu.
6.8.2
Alpha-beta
Metoda pro spou²t¥ní výpo£tu Alpha-bety funguje velice podobn¥ jako u Minimaxu. Jsou tu pouze p°idány podmínky pro pro°ezání výpo£tu a p°íslu²né prom¥nné k tomuto ú£elu. Pro lep²í vysv¥tlení je níºe uveden pseudokód upravené verze pro pr·chod stage.
1 double stageAB(node, d, alpha, beta){ 2 if (node is a terminal node or depth <= 0){ 3 return the heuristic value of node 4 } 5 for (each action of maxPlayer){ 6 b <- beta 7 for (each action of minPlayer){ 8 b <- Min (b, stageAB(child[maxPlAct,minPlAct],d-1, alpha, beta)) 9 if(b <= alpha){ 10 break 11 } 12 } 13 alpha <- max(alpha, b) 14 } 15 return alpha 16 } Pro výpo£et na hodnotách ve stage je pot°eba celý algoritmus upravit. Zm¥na oproti klasické verzi je ud¥lána podobn¥ jako zm¥na z klasického Minimaxu na pr·chod stagí. A stejn¥ jako pro upravený Minimax i zde platí, ºe pseudokód zachycuje princip pouze pro maximalizujícího hrá£e a kdyº je pot°eba získat akci, kterou chce hrát minimalizující hrá£, musí být algoritmus p°íslu²ným zp·sobem upraven.
KAPITOLA 6.
6.9
IMPLEMENTACE
28
MCTS
Tato t°ída obsahuje metody pot°ebné pro výpo£et algoritmu MCTS a získání výsledku, kterým je akce, kterou by m¥l hrát dotázaný hrá£. D·leºité £ásti této t°ídy korespondují se základními £ástmi algoritmu MCTS popsaného v kapitole 3.2.
•
Selekce
Tato £ást spou²tí rekurzivní pr·chod jiº vytvo°eným stromem uzl· dokud nedojde do jeho listu. Rekurzivní výpo£et dostává jako parametr uzel, ze kterého se má zano°ovat dál. Na za£átku je tedy spou²t¥n na ko°enový uzel a zárove¬ je stranou uloºen stav hry, který bude pozd¥ji pouºit pro vytvo°ení nových uzl· a simulaci hry. V kaºdém volání metody najde nejlep²ího potomka aktuálního uzlu a na n¥j poté spou²tí rekurzi. Nejlep²ího potomka získá z t°ídy Node. Vrátí nejen nejlep²ího potomka, ale také na p°edaný stav hry aplikuje vybrané akce vedoucí do p°íslu²ného potomka. Tím pádem na konci rekurze v listu stromu bude aktuální stav hry korespondovat s pr·chodem stromu a v²emi akcemi, které do listového uzlu vedou.
•
Expandování
Tato £ást vytvo°í potomky daného uzlu podle stavu hry, který byl získán v pr·b¥hu selekce. Vygenerování potomk· zaji²´uje op¥t t°ída Node. Zavolá tedy p°íslu²nou metodu a p°edá stav hry získaný v pr·b¥hu selekce.
•
Simulace hry
Tato £ást pracuje se stavem hry získaným selekcí a pouze spustí náhodný simulátor (simulátor pouºívající náhodn¥ hrající hrá£e) a vrátí získanou hodnotu hru. Ideální by bylo, aby simulátor odehrál hru aº do terminálního stavu. Tedy do stavu, kdy vyhraje jeden z hr᣷ nebo vypr²í po£et kol. Vzhledem k náhodnému odehrávání se i na malé map¥ bude v¥t²inou kon£it vypr²ením dostupných kol. Podle pravidel p°evzatých ze zdroje je po£et kol k odehrání 1000 a v takovém p°ípad¥ simulace v rámci MCTS zaberou p°íli² £asu. Bylo pot°eba tedy po£et kol sníºit tak, aby jich nebylo moc kv·li £asové náro£nosti a zárove¬ ani málo kv·li dostate£né heuristice. ím mén¥ kol bude simulátor odehrávat, tím více se bude MCTS chovat podle spo£ítané heuristiky a náhodné tahy ztrácí na váze a tím i opakované spou²t¥ní simulace. Ve výsledku se vyplatilo nechat simulátor odehrávat zhruba 70 kol. Simulace probíhají rychle a zárove¬ se projeví hraní náhodných tah·.
•
Zp¥tná propagace
Tato £ást dostane hodnotu hry a uzel, ze kterého má propagovat hodnotu zp¥t po stromu nahoru. První v zadaném uzlu zvedne po£ítadlo po£tu aplikování akcí prvního i druhého hrá£e o jedna. Pak v daném uzlu nechá p°epo£ítat kvalitu t¥chto akcí. Pokud není aktuální uzel ko°enem stromu, propaguje tento výsledek na rodi£e op¥tovným pr·chodem této £ásti a p°edáním rodi£e aktuálního uzlu,
KAPITOLA 6.
IMPLEMENTACE
29
stejné hodnoty hry a identi kátory akcí obou hr᣷. Ty jsou pot°eba, aby rodi£ovský uzel v¥d¥l, kterou akci má p°epo£ítat. V²echny tyto hodnoty jsou uloºeny v samotném uzlu.
Hlavní metoda této t°ídy zaji²´uje celý výpo£et algoritmu MCTS s pouºitím vý²e popsaných £ástí. Jako argumenty dostává po£et simulací, které má provést, £as, do kterého musí výpo£et skon£it, a hrá£e, pro kterého má získat jeho akci. Tato metoda spou²tí ve smy£ce selekci listového uzlu, vytvo°ení jeho potomk·, simulaci hry a propagování výsledku simulace zp¥t ke ko°enu. Smy£ka skon£í ve chvíli, kdy je dosaºen zadaný po£et simulací nebo do²el £as ur£ený k výpo£tu. Jakmile výpo£et skon£í, metoda vrátí zp¥t akci s aktuáln¥ nejlep²í hodnotou pro daného hrá£e.
6.10
Cplex
CPLEX je pomocná knihovna od IBM umoº¬ující výpo£et lineárního programu [1]. T°ída Cplex v mém programu vyuºívá tuto knihovnu od IBM a zprost°edkovává výpo£ty, které pot°ebuji k lineárnímu programu. Pro výpo£et jsou zde dv¥ d·leºité metody. Jedná se o metody pro výpo£et pravd¥podobnostního rozloºení tah· obou hr᣷, pro kaºdého hrá£e jedna. Ob¥ metody jsou prakticky totoºné. Jedna z nich ale vytvá°í lineární program z °ádk· a vrací pravd¥podobnostní rozd¥lení pro prvního hrá£e a druhá metoda vytvá°í lineární program ze sloupc· a vrací pravd¥podobnostní rozd¥lení pro akce druhého hrá£e. P°ed zavoláním t¥chto metod je pot°eba první nastavit tabulku výsledk·, resp. hodnot her, ze kterých má lineární program spo£ítat pravd¥podobnostní rozloºení akcí daného hrá£e. Dále dostává tato metoda jako argument ozna£ení, jaké akce obou hr᣷ má k výpo£tu pouºít. Tato konstrukce je zde z d·vodu pouºití algoritmu Double oracle. V pr·b¥hu výpo£tu postupn¥ p°idávají oba hrá£i r·zné akce a proto je p°edem de novaná tabulka o velikosti v²ech akcí obou hr᣷ a ozna£ují se akce, které jsou zahrnuty do výpo£tu. Metody vytvo°í ze zadaných informací lineární program podle návodu v 4.4. Vytvo°í p°es knihovnu CPLEX pot°ebné rovnice, spustí výpo£et a vrátí výsledky jednotlivých prom¥nných lineárního programu v poli. Toto pole tedy obsahuje pravd¥podobnostní rozloºení akcí obou hr᣷. Dále si uloºí samotnou hodnotu hry, kterou je moºné získat, pokud je pot°eba. Nap°íklad p°i výpo£tu v niº²ích hloubkách se vrací pouze tato hodnota a pravd¥podobnosti akcí obou hr᣷ jsou bezp°edm¥tné.
6.11
Double oracle
Tato t°ída reprezentuje po£íta£ového hrá£e, který vybírá své tahy podle výpo£tu lineárního programu. Algoritmus Double oracle p°ijímá v argumentu stav hry, maximální hloubku prohledávání a £íslo hrá£e, pro kterého chceme získat jeho tah. První si nechá vygenerovat v²echny akce pro oba hrá£e. Poté spustí rekurzivní výpo£et pro první akce obou hr᣷ jako základ pro výpo£et Double oracle. Výpo£et Double oracle tedy za£íná s jednou akcí kaºdého hrá£e a vºdy t¥mi prvními akcemi. Poté v cyklu vypo£ítá lineární program pomocí t°ídy Cplex a pomocí p°edchozích metod najde pro kaºdého hrá£e akci best response. Tyto akce
KAPITOLA 6.
IMPLEMENTACE
30
jsou p°idány do výpo£tu a znovu prob¥hne lineární program a ur£ení nových pravd¥podobnostních rozd¥lení. Pokud se ºádné nové akce nep°idávají, výpo£et kon£í a hodnota hry pro tento stav je rovna hodnot¥ hry pro aktuální lineární program. Tato hodnota je tedy vrácena ven z rekurze, pokud je to hlavní metoda prohledávaní, vrátí akci pro daného hrá£e. Akce je vybrána s ²ancí podle pravd¥podobnostní rozd¥lení akcí. P°i rekurzivním zano°ení pak vrací pouze spo£tenou hodnotu hry. Pro lep²í p°edstavení tohoto algoritmu zde uvádím jeho pseudokód.
1 double doubleOracle(node, depth, player){ 2 if (node is a terminal node or depth <= 0){ 3 return the heuristic value of node 4 } 5 values[0,0] <- doubleOracle(node, depth-1) 6 addActionsToComputing(0,0) 7 do{ 8 val, minProbabilities, maxProbabilities <- solveLp(values) 9 minNewAction <- bestResponse(values, minProbabilities) 10 maxNewAction <- bestResponse(values, maxProbabilities) 11 newActionsAdded <- false 12 if(not(actionUsed[minNewAction])){ 13 actionUsed[minNewAction] <- true 14 addActionToComputing(minPlayer, minNewAction) 15 newActionsAdded <- true 16 } 17 18 if(not(actionUsed[maxNewAction])){ 19 actionUsed[maxNewAction] <- true 20 addActionToComputing(maxPlayer, maxNewAction) 21 newActionsAdded <- true 22 } 23 }while(newActionsAdded) 24 return val 25 } Pouºitá metoda bestResponse má za úkol najít pro daného hrá£e akci s nejvy²²í hodnotou, tedy nejlep²í reakci (v angli£tin¥ best response) na aktuální pravd¥podobnostní rozloºení soupe°ových akcí. Tato metoda pro kaºdou hrá£ovu akci zkusí vypo£ítat odhad pomocí p°edchozí metody a pokud se tato akce ukáºe jako nad¥jná, resp. její odhadovaná hodnota je v¥t²í neº dosavadní nejlep²í, spustí p°esný výpo£et hodnoty. Pokud i tato hodnota je lep²í, uloºí ji spolu s identi kátorem akce. Její pseudokód vypadá takto:
1 integer bestResponse(values, probabilities, player){ 2 value <- -infinity 3 for(each action of player){ 4 value <- Max(value, actionValue(action, enemyProbabilities, player)) 5 }
KAPITOLA 6.
6 7 }
IMPLEMENTACE
31
return bestAction
Metoda actionValue funguje tak, ºe pro akci, jejíº identi kátor p°ebírá v argumentu, vypo£ítá její aktuální hodnotu. Tedy z aktuálního pravd¥podobnostního rozd¥lení a získaných hodnot her vypo£ítá celkovou hodnotu akce. Zadaná akce ur£í pro daného hrá£e sloupec, resp. °ádek v tabulce a tím pádem existuje pro kaºdou akci n¥kolik hodnot her získaných rekurzivním voláním. Hodnota akce je sou£et t¥chto hodnot vynásobených pravd¥podobnostmi p°íslu²ných akcí soupe°e. Zárove¬ uvaºuje pouze soupe°ovi akce, které p°idal do výpo£tu. Pokud n¥které hodnoty her chybí, získá je spu²t¥ním rekurzivního výpo£tu. Pseudokód této metody vypadá takto:
1 actionValue(action, enemyProbabilities, player){ 2 value <- 0 3 for(each enemy action){ 4 value <- value + gameValue(action, enemyAct)*enemyProb[enemyAct] 5 } 6 return value 7 } Metoda gameValue má za úkol vrátit hodnotu hry pro dané akce obou hr᣷. Není zde volání rekurzivního výpo£tu p°ímo, protoºe n¥které hodnoty jsou pravd¥podobn¥ známé z p°edchozích iterací celého algoritmu. Pokud je hodnota jiº spo£tená, tak jí jenom vrátí z pam¥ti. V opa£ném p°ípad¥ spustí rekurzivní výpo£et Double oracle.
6.12
Double oracle s pro°ezáváním
V této práci vznikla úprava metody pro výb¥r best response akce v rámci algoritmu Double oracle. asov¥ nejnáro£n¥j²ím výpo£tem v rámci Double oracle je jeho rekurzivní volání p°i hledání best response akce, kde je pot°eba znát více hodnot neº pro výpo£et lineárního programu. Kaºdý hrᣠzkou²í na soupe°ovu strategii aplikovat akce, které zatím do výpo£tu nep°idal a tím pádem pot°ebuje znát hodnoty t¥chto her. My²lenkou této úpravy je tedy odstranit zbyte£ná rekurzivní volání Double oracle. Best response je vºdy jen jedna a pokud se vybírá z v¥t²ího mnoºství akcí, tak v¥t²ina akcí má ve výsledku mnohem hor²í hodnotu neº práv¥ vybraná best response. Pokud získáme odhad hodnoty z rekurze a tento odhad bude hor²í neº dosavadní vybraná best response, nemusí být rekurze spu²t¥na. Aby mohl být odhad pouºit takovýmto zp·sobem, musí být vºdy stejný nebo lep²í v porovnání s reálným výsledkem rekurze. To nám ºádný heuristická rovnice nem·ºe zaru£it. K tomuto ú£elu m·ºe být pouºit minimax aplikovaný na serializovanou verzi hry. Hloubka prohledávání musí být nastavena stejn¥ jako by se jednalo o rekurzi Double oracle, protoºe je pot°eba, aby oba algoritmy po£ítali se stejnými hodnotami. Pokud bude hrᣠvybírající best response hrát v serializované variant¥ jako druhý, bude se jednat o optimistickou variantu minimaxu. Pokud bude existovat ryzí Nashovo ekvilibrium, tak bude výsledek minimaxu stejný jako by vypo£ítal Double oracle a pokud existovat nebude, tak najde hodnotu lep²í.
KAPITOLA 6.
IMPLEMENTACE
32
Tím je tedy zaru£eno, ºe vynechání rekurze na základ¥ tohoto odhadu neod°ízne výpo£et akce, která by mohla být ozna£ena jako best response. Výpo£et minimaxu je rychlej²í neº výpo£et Double oracle, ale jeho výpo£et nenahrazuje. Pokud odhad ukáºe, ºe akce by mohla být lep²í neº dosavadní best response, musí být spu²t¥na i rekurze. Ve chvíli, kdy budou odhady obsahovat lep²í hodnoty nebo budou akce se°azeny tak, ºe kaºdá dal²í bude lep²í neº ta p°edchozí, algoritmus se tímto zpomalí, protoºe pro kaºdou akci bude spou²t¥t oba dva výpo£ty. Teoreticky by toto ale nem¥lo nastávat moc £asto. Dále je p°iloºen pseudokód upravené verze hledání best response.
1 integer bestResponseWithCutOff(values, probabilities, player){ 2 value <- -infinity 3 for(each action of player){ 4 if(value > estimationValue(action, enemyProbabilities, player)){ 5 continue 6 } 7 value <- Max(value, actionValue(action, enemyProbabilities, player)) 8 } 9 return bestAction 10 }
Kapitola 7
Experimenty V²echny experimenty jsem pou²t¥l s dostupnou pam¥tí 1GB a procesoru s výpo£etní frekvencí 2,4 GHz.
7.1
Porovnání serializovaného minimaxu a lineárního programu
Jako první jsou porovnané algoritmy LP, Minimax a Alpha-beta v závislosti na tom, do jaké hloubky jsou pu²t¥ny. Pro porovnání algoritm· do co nejv¥t²í hloubky v rozumném £ase byla zvolena men²í mapu, na které nedochází k tak velkému v¥tvícímu faktoru. Mapa se 4 planetami je pom¥rn¥ jednoduchá a p°i hrách LP proti Minimaxu dochází k tomu, ºe oba hrá£i £ekají a nic ned¥lají. Ve chvíli, kdy n¥jaký hrᣠud¥lá první tah a ztratí lod¥ v boji s neutrální planetou, tak druhý hrᣠm·ºe zahrát tak, aby vºdy vyhrál. Jako testovací mapy byly vybrány mapy se 4 a se 7 planetami. Dále byl pro v²echny algoritmy vybrán stejný, jednoduchý soupe°, kterým se stal expandující bot. Ten funguje na principu, ºe vybere svou nejsiln¥j²í planetu a cizí nejslab²í a po²le letku mezi nimi. Na t¥chto testech by m¥lo být vid¥t, jak velkou roli hraje v¥tvící faktor p°i výpo£tech na domén¥ Planet Wars a jak jsou schopné si tyto algoritmy s výpo£ty poradit. D·leºitým záv¥rem by také m¥lo být zji²t¥ní, na jakou hloubku nastavit prohledávání v rámci nadcházejícího turnaje. Z tabulek a graf· je vid¥t, jak Alpha-beta zrychluje výpo£et oproti Minimaxu. Logicky se rozdíl mezi ob¥ma algoritmy zv¥t²uje v závislosti na hloubce prohledávání. P°i prohledávání do hloubky 1 projdou oba dva algoritmy stejné uzly, pro°ezávání za£ne mít efekt aº od hloubky 2 a více. V¥t²í rozdíl mezi výkonem obou algoritm· si m·ºeme v²imnout aº v hloubce 4, na men²í map¥ se £ty°mi planetami dokonce aº v hloubce 5. Bohuºel p°i v¥t²í hloubce a zvlá²t¥ na map¥ se sedmi planetami trval výpo£et pom¥rn¥ dlouho a tak jsou hodnoty spí²e jen orienta£ní. Nenechal jsem totiº uhrát algoritmy celou hru, ale pouze n¥kolik tah·. V p°ípad¥ v¥t²í mapy a prohledávání do hloubky 5 jsem je nechal zahrát pouze první tah. Výsledné pr·m¥rné hodnoty by tedy byly je²t¥ v¥t²í, nejspí² i °ádov¥, protoºe takto po£ítaly algoritmy s výchozím stavem hry, kde kaºdý hrᣠmá pouze jednu planetu a stavový prostor pro tento tah je citeln¥ men²í neº v rozehrané h°e. Dále je vid¥t, ºe LP prohledává dokonce mnohem mén¥ uzl· neº Alpha-beta, coº je díky vyuºití Double oracle a pro°ezávání na základ¥ odhadu p°i výb¥ru best response akcí. Nicmén¥ kv·li výpo£t·m lineárního programu a odhad·m pomocí Minimaxu pot°ebuje na
33
KAPITOLA 7.
EXPERIMENTY
34
Obrázek 7.1: Porovnání £asové sloºitosti Minimaxu a lineárního programu
Obrázek 7.2: Porovnání po£tu vytvo°ených uzl· Minimaxu a lineárního programu
malých hloubkách prohledávání více £asu neº oba dal²í algoritmy. Od hloubky 3 a více se £asová závislost oto£í a LP za£ne být i rychlej²í, p°estoºe spou²tí výpo£ty lineárního programu a Minimaxu. Ve výsledku je tedy algoritmus LP ve v¥t²ích hloubkách výkonn¥j²í. Na map¥ se sedmi planetami byl LP schopen uhrát celou hru v rozumném £ase, na rozdíl od Minimaxu. Zárove¬ pozd¥ji zjistíme, ºe p°i vzájemných hrách m¥l i nejlep²í úsp¥chy a ostatní algoritmy ho nebyly v¥t²inou schopné porazit. Zajímavým poznatkem p°i t¥chto experimentech také bylo to, ºe algoritmy hrají r·zn¥ dob°e p°i r·zné hloubce prohledávání. To je pom¥rn¥ logické, ale zajímavé na testování bylo
KAPITOLA 7.
EXPERIMENTY
35
Obrázek 7.3: Porovnání £asové sloºitosti Minimaxu a lineárního programu
Obrázek 7.4: Porovnání po£tu vytvo°ených uzl· Minimaxu a lineárního programu
to, ºe p°i v¥t²í hloubce prohledávání m·ºe hrát algoritmus na pohled h·°e. "Nejh·°e"se v²em algoritm·m na map¥ se sedmi planetami proti expand botovi da°ilo p°i prohledávání do hloubky 3, protoºe pot°ebovali nejvíce tah·, aby soupe°e porazili. LP algoritmus vyhrál po 32 tazích, zatímco v hloubce 1 vyhrál v 17 tahu a v hloubce 4 dokonce jiº v 11. Pro Minimax toto platilo je²t¥ o n¥co víc, protoºe na v²ech testovaných hloubkách vyhrál do 20 tahu, ale p°i hloubce prohledávání 3 vyhrál aº v 52 tahu. Ukázalo se tedy, ºe zvý²ení hloubky prohledávání není v tomto p°ípad¥ vºdy p°ínosem. Nicmén¥ to nemusí znamenat, ºe opravdu hráli h·°e, spí²e hráli více takticky a byli by schopné porazit o n¥co t¥º²ího
KAPITOLA 7.
EXPERIMENTY
36
soupe°e. Na druhou stranu m·ºe nastat situace, kde Minimax £i LP spo£tou nejvýhodn¥j²í akci, kterou soupe° jiº nem·ºe zvrátit, ale ten ud¥lá tah, který v·bec nebyl p°i výpo£tech uvaºován. Tím tedy nastává p°i h°e situace, kdy jeden z testovaných bot· vy²le na poslední soupe°ovu planetu ur£itý po£et lodí s tím, ºe soupe°e tímto porazí. Protoºe soupe° m·ºe poslat lod¥ z té planety kamkoliv, ale ºádnou z cizích planet neporazí. Nicmén¥ expand bot nepo²le lod¥ podle pravidel generování akcí, které pouºívají "chyt°í"boti, ale po²le v²echny planety na práv¥ oslabenou cizí planetu a oba hrá£i tak jednu planetu ztratí a zárove¬ kaºdý jednu získá. Takto se chvíli p°etahují o dv¥ planety neº Minimax získá dostate£nou po£etní p°evahu lodí na v²ech planetách, protoºe má více planet a tím pádem v¥t²í produkci lodí.
7.2
Hra proti jednoduchému soupe°i
Jako dal²í experiment byl spu²t¥n kaºdý z vý²e uvedených algoritm· op¥t proti jednoduchému soupe°i, kterým z·stal expand bot. Tyto experimenty m¥ly za úkol porovnat jejich funk£nost a sloºitost výpo£tu proti stejnému jednoduchému soupe°i na r·zn¥ velkých mapách. Pro toto testování byly pouºity následující mapy:
•
malá mapa se 4 planetami, symetricky uspo°ádaná
•
malá mapa se 4 planetami, nesymetrická
•
st°ední mapa se 7 planetami
•
st°ední mapa s 11 planetami
•
velká mapa s 20 a více planetami
Pro testování byly vybrány algoritmy tak, aby byly zastoupené v²echny typy z této práce, tedy:
•
MCTS
•
LP
•
Alphabeta
Z graf· 7.5 a 7.6 je vid¥t, ºe velikost mapy dramaticky zvy²uje sloºitost celé hry a jejího výpo£tu. Jediný algoritmus, u kterého není nár·st sloºitosti tak velký je MCTS. To je z toho d·vodu, ºe jako jediný má problémy s pam¥tí. Tento algoritmus si totiº drºí v pam¥ti celý expandovaný strom, kdeºto Minimax i LP expandují strom pouze pomocí rekurze a jakmile se z rekurze vrátí, není pot°eba dále drºet nav²tívené uzly v pam¥ti. Souvisí s tím i men²í £asové nároky p°i v¥t²ích mapách, protoºe MCTS v¥t²inou dojde pam¥´ d°íve, neº je dosaºeno ideálního po£tu iterací. Na velkých mapách je to také jediný z testovaných algoritm·, který prohrává s expandujícím botem. Hodnoty pro Monte-Carlo jsou zpr·m¥rované ze 30 her na kaºdé map¥, vºdy po 15 hrách se stejnou startovní pozicí a dal²ích 15 her s prohozenými startovními planetami. Ostatní algoritmy b¥ºeli se stejným rozloºením pouze jednou, protoºe
KAPITOLA 7.
EXPERIMENTY
37
Obrázek 7.5: Porovnání £asové sloºitosti v závislosti na po£tu planet
Obrázek 7.6: Porovnání po£tu vytvo°ených uzl· v závislosti na po£tu planet
Minimax a tím pádem i Alpha-beta hrají deterministicky, stejn¥ tak expandující bot. Tím pádem by více odehraných her se stejným po£áte£ním rozestavením nep°ineslo ºádné nové poznatky. LP bot teoreticky nehraje deterministicky, protoºe hraje podle vypo£ítané smí²ené strategie, coº je pravd¥podobnostní rozd¥lení akcí. Nicmén¥ na domén¥ Planet Wars hraje dost £asto deterministicky, alespo¬ co se zápas· proti expand botovi tý£e. V¥t²inou má jedna akce lep²í výsledky neº ostatní akce nehled¥ na to, jakou akci zvolí soupe°. Proto taková akce bude vybrána se stoprocentní pravd¥podobností. Na men²ích mapách jsem nechal hrát LP bota stejným zp·sobem jako MCTS, 30 zápas· na kaºdé map¥. Na dvou nejv¥t²ích mapách
KAPITOLA 7.
EXPERIMENTY
38
jsem musel pouºít data pouze z jedné hry, aby testování skon£ilo v rozumném £ase. Nejhor²ích výsledk· proti expandujícímu botovi dosáhl algoritmus MCTS. Na vin¥ op¥t bude veliká pam¥´ová náro£nost. Monte-Carlo by m¥l vrátit dobrý výsledek aº ve chvíli, kdy dosáhne dostate£ného mnoºství iterací. Aby se dalo mnoºství iterací povaºovat za dostate£né, muselo by dosahovat n¥kolik sto tisíc pr·chod·, v tomto p°ípad¥, s velkým v¥tvícím faktorem, by moºná bylo ideální dosáhnout n¥kolika stovek tisíc iterací. Bohuºel p°i testech s pam¥tí 1GB jsem byl schopen dosáhnout bezpe£n¥ pouze n¥kolika málo desetitisíc iterací neº byla pam¥´ zapln¥na a to pouze na men²ích mapách. Na velkých mapách se kv·li v¥tvícímu faktoru, který dosahuje i n¥kolika tisíc potomk· z jednoho uzlu, dostane s po£tem iterací p°ed napln¥ním pam¥ti na n¥kolik desítek. A to není dostate£né pro jakékoliv rozhodnutí dal²ího tahu, protoºe s v¥tvením n¥kolik tisíc stav· z jednoho uzlu to znamená, ºe se moc hluboko v prohledávání nedostane, natoº ke spu²t¥ní rozumného po£tu iterací v jednom uzlu. To samé platí o pouºití progressive unpruning v rámci Monte-Carla. Tato metoda pro°ezání pot°ebuje také v¥t²í po£et iterací. Musí získat ohodnocení v²ech akcí, aby po od°íznutí v¥t²iny akcí z·staly n¥jaké dobré akce a naopak, opravdu ²patné akce zmizely. P°i dal²ích iteracích se pak mají postupn¥ akce vracet zpátky do výpo£etního procesu p°i v¥t²í £etnosti nav²t¥vování daného uzlu. P°i malém po£tu iterací, kterému se v tomto p°ípad¥ Monte-Carlu dostalo, naopak progressive unpruning zhor²uje kvalitu výpo£tu, protoºe £asto nedostane ºádný uzel k dispozici dostate£ný po£et nav²tívení, aby pro°íznutí prob¥hlo a pokud necháme men²í nároky na po£et nav²tívení, tak se p°i pro°ezávání od°íznou v podstat¥ náhodné akce. Z tohoto d·vodu se £asto takto upravený algoritmus rozhoduje h·°e neº p·vodní, protoºe lep²í akce mohou být od°íznuté a nep°ístupn¥ k dal²ímu pr·chodu, který by ukázal, ºe jsou ve skute£nosti lep²í. P°i porovnání výsledk· algoritm· LP a Minimaxu je vid¥t, ºe LP má del²í výpo£etní £as zhruba o jeden °ád, p°estoºe vytvo°í mnohem mén¥ uzl·. V¥t²í výpo£etní £as je zp·soben výpo£ty lineárního programu a výpo£ty Minimaxu, které jsou provád¥ny opakovan¥ v kaºdém uzlu. Mnohem men²í po£et vytvo°ených uzl· souvisí s algoritmem Double oracle a pro°ezáváním akcí, které je nutné nav²tívit p°i výpo£tu. Teoreticky by v²ak m¥l mít lineární program výhodu v tom, ºe je schopen zahrnout do své strategie více akcí a lépe ohodnotit stavy her v niº²ích vrstvách stromu. Nicmén¥, jak je zmín¥no vý²e, na domén¥ Planet Wars se £asto najde akce, která je p°i jakékoli akci soupe°e lep²í neº v²echny ostatní akce. V takovém p°ípad¥ hraje stejnou akci i Minimax a p°itom pot°ebuje mén¥ výpo£etního £asu. Lépe by m¥ly být vid¥t rozdíly p°i vzájemných hrách algoritm·. Je moºné, ºe LP bot vybírá stejné akce jako Minimax pouze kv·li tomu, ºe hraje proti jednoduchému soupe°i, takºe se hra nedostane do stavu, kdy se vyplatí hledání smí²ené strategie.
7.3
Lineární program a jeho verze
Tento experiment m¥l za úkol porovnat základní variantu lineárního programu, algoritmus Double oracle a jeho upravenou verzi, která byla vytvo°ena v rámci této práce. Porovnání probíhá ve stejném duchu jako porovnání Minimaxu a lineárního programu v sekci 7.1. Porovnal jsem tyto algoritmy na dvou r·zných mapách, první na map¥ se £ty°mi planetami a po té na map¥ se sedmi planetami. Na obou mapách hrály v²echny algoritmy proti stejnému soupe°i, kterým je stále expandující bot. Zárove¬ jsem pou²t¥l kaºdý algoritmus s r·znými
KAPITOLA 7.
EXPERIMENTY
39
hloubkami prohledávání a porovnával jsem, jak dlouho jim trvá výpo£et jednoho tahu a kolik p°i tom vytvo°í nových uzl·. Pro hloubky prohledávání 4 a více platí stejný p°ístup jako p°i zkoumání Minimaxu. I tady byl problém spo£ítat celou hru pro v¥t²í hloubky a proto jsem nechal v²echny algoritmy po£ítat pouze n¥kolik tah·. Výsledek je tedy spí²e orienta£ní, ale pro vzájemné porovnání nám sta£í. Dále tedy porovnávám tyto algoritmy:
•
Pure LP - základní varianta lineárního programu
•
Double oracle - algoritmus double oracle vyuºívající lineární program
•
LP - upravený lineární program z této práce
Obrázek 7.7: Porovnání £asové sloºitosti lineárního programu
Na map¥ se £ty°mi planetami 7.7 je vid¥t, ºe co se tý£e £asu, tak se na malých hloubkách prohledávání drºí algoritmus LP p°ibliºn¥ na stejné hladin¥ jako Pure LP. Double oracle oproti tomu zvládá po£ítat o n¥co rychleji. P°i v¥t²ích hloubkách pak LP klesne na úrove¬ Double oraclu a p°i nejvy²²í testované hloubce zvládne jeden tah spo£ítat dokonce rychleji. Co se tý£e vygenerovaných uzl· 7.8, tak LP je celou dobu nejníºe. Nejvy²²í rozdíl je v²ak mezi Pure LP a Double oracle. Algoritmus vytvo°ený b¥hem této práce za£ne mít výrazn¥j²í výhodu aº od hloubky 4 a vý². P°estoºe vytvo°í mén¥ uzl·, tak £asov¥ nemá tak velkou rezervu oproti Double oracle. Pro°ezané v¥tve stromu a tedy i p°esko£ené rekurzivní výpo£ty jsou v podstat¥ vym¥n¥né za odhady pomocí Minimaxu. Jeho výpo£et tedy taky n¥co trvá, ale celkov¥ je LP o n¥co málo rychlej²í neº ob¥ dal²í verze lineárního programu. P°i h°e se sedmi planetami vypadají grafy (7.9 a 7.10) podobn¥ jako p°i h°e se £ty°mi planetami, s tím rozdílem, ºe LP te¤ vytvo°í °ádov¥ mén¥ uzl· neº Double oracle. Lze tedy p°edpokládat, ºe tento rozdíl se dále bude zv¥t²ovat na v¥t²ích mapách a ºe tedy bude
KAPITOLA 7.
EXPERIMENTY
40
Obrázek 7.8: Porovnání po£tu vytvo°ených uzl·
Obrázek 7.9: Porovnání £asové sloºitosti lineárního programu
výhodn¥j²í jej pouºít p°i hrách s v¥t²ím v¥tvícím faktorem. Dokud je v¥tvící faktor relativn¥ malý, tak pro°ezávání na základ¥ odhad· není tak ú£inné co se tý£e redukce £asu. Výpo£et odhadu není triviální a k p°ípadnému od°íznutí nedochází tak £asto a od°íznuté £ásti nejsou tak velké.
KAPITOLA 7.
EXPERIMENTY
41
Obrázek 7.10: Porovnání po£tu vytvo°ených uzl·
7.4
Závislost po°adí vygenerovaných akcí
Dal²ím zajímavým experimentem bylo vyzkou²et r·zné po°adí vygenerovaných akcí. V²echny algoritmy preferují akce s men²ím po°adovým £íslem v p°ípad¥, ºe více akcí má stejnou hodnotu. Jak se ale p°i h°e ukáºe, akce v¥t²inou stejnou hodnotu nemají a n¥které p°eci jen fungují lépe £i h·°e. Zpo£átku byla na prvním míst¥ prázdná akce, tedy akce, kdy hrᣠned¥lá nic. Ob£as se tak stalo, ºe n¥který z algoritm· p°i jasném vít¥zství zvolil vy£kávání a hru tak neúm¥rn¥ prodluºoval. Dal²ím postupem byla zm¥na po°adí akcí tak, ºe na první pozici byla umíst¥na n¥jaká agresivní akce, tedy vyslání svých lodí proti soupe°ov¥ planet¥. Toto po°adí akcí zabránilo zastavení bota b¥hem jasné výhry, kdy místo zni£ení soupe°e vy£kává bez £innosti. V n¥kterých situacích mu to ale naopak u²kodilo. N¥které situace lépe °e²ilo vy£kávání neº útok na soupe°e, protoºe tím si pak bot oslabil svou planetu a soupe° mohl se tak mohl st¥hovat mezi oslabenými planetami, viz poslední odstavec kapitoly 7.1.
7.5
Turnaj mezi boty
Jako poslední experiment byly spu²t¥ny nejlep²í verze v²ech t°í zkoumaných algoritm· proti sob¥. V tomto experimentu se m¥lo ukázat, který z algoritm· má navrch nebo zda jsou n¥které z nich srovnateln¥ dobré. Na základ¥ p°edchozích experiment· byla nastavena u algoritm· Minimax a LP maximální hloubka prohledávání na 2, aby testy m¥ly ²anci dob¥hnout v rozumném £ase. MCTS z·stalo omezené pouze pam¥tí 1GB. Algoritmus LP podle p°edchozích test· bude nejspí²e na této hloubce pot°ebovat o n¥co del²í £as na výpo£et, ale základem bylo porovnat Minimax a LP na stejné hloubce. Tyto bitvy prob¥hly na mapách se sedmi a jedenácti planetami, kde uº mohou algoritmy n¥jakým zp·sobem taktizovat, ale zárove¬ nejsou mapy tak velké, aby výpo£et jednoho tahu trval n¥kolik hodin. Výsledky na obou typech map byly nakonec totoºné, takºe demonstruji
KAPITOLA 7.
42
EXPERIMENTY
pouze zápasy z v¥t²ích map, kde bude více vid¥t rozdíl mezi pot°ebnými zdroji algoritm·. Následuje tabulka výsledk· z turnaje, vºdy dva boti mezi sebou hráli 10 zápas·, na jedné map¥ se pak vyst°ídali na obou startovních pozicích. X
MCTS Alphabeta LP
MCTS Alphabeta
LP
X
0 : 5
0 : 5
5 : 0
X
1 : 4
5 : 0
5 : 0
X
Tabulka 7.1: Výsledky turnaje mezi boty Mapy mají ozna£ené startovní pozice £ísly 1 a 2. ádek ozna£uje hrá£e za£ínajícího na startovní pozici 1 a sloupec na pozici 2. Algoritmus LP byl nejúsp¥²n¥j²í, porazil v podstat¥ v²echny, pouze na jedné map¥ p°i jednom startovním rozloºení byl schopen algoritmus Alphabeta vyhrát nad LP. Zajímavé je, ºe v ostatních p°ípadech se mu to nikdy nepovedlo, ale v tomto konkrétním p°ípad¥ se mu da°ilo i po opakovaném spu²t¥ní LP porazit. Vysv¥tluji si to tím, ºe generované akce jsou se°azeny podle identi kátor· planet a tak Alpha-beta m·ºe v kaºdém rozloºení startovních pozic volit akce na stejnou planetu, ale v jednom základním postavení je od ní dále neº v druhém. Cílová planeta je stejná z toho d·vodu, ºe vybírá sice hodnotu s nejlep²í hodnotou, ale pokud má více akcí nejlep²í hodnotu, tak zvolí první nalezenou. Maximální hloubka prohledávání 2 není tak velká, takºe m·ºe tento p°ípad nastat relativn¥ snadno. Algoritmus MCTS pak nevyhrál ani jeden zápas, je ale moºné, ºe zv¥t²ení dostupné pam¥ti, p°ípadn¥ jiný vzorec pro selekci a jiné nastavení parametr·, by mu mohlo prosp¥t a hrál by lépe.
Obrázek 7.11: Porovnání £asové sloºitosti uzl· b¥hem turnaje
Z graf· 7.11 a 7.12 je vid¥t, ºe algoritmy Alpha-beta a MCTS spot°ebovali p°ibliºn¥ stejn¥ £asu zatímco LP po£ítal tahy asi desetkrát déle. Sice byl nejúsp¥²n¥j²í, ale otázkou
KAPITOLA 7.
EXPERIMENTY
43
Obrázek 7.12: Porovnání po£tu vytvo°ených uzl· b¥hem turnaje
je, zda je to dostate£ný p°ínos vzhledem k dob¥ výpo£tu. Zkusil jsem je²t¥ nastavit hloubku prohledávání LP na 1 a porovnat ho s Alpha-betou. V takovém nastavení spot°eboval LP £asu desetkrát mén¥. Jenºe Alpha-beta v tu chvíli má výhodu prohledávání do v¥t²í hloubky a v tu chvíli nebyl algoritmus LP schopen vyhrát. Z p°edchozích experiment· tedy vychází, ºe pouºití algoritmu LP se i s dopln¥ním o Double oracle a jeho pro°ezávání aplikované v této práci vyplatí aº ve v¥t²ích hloubkách, °ádov¥ od hloubky 4 a více. Bohuºel spustit výpo£et hry obou algoritm· na takovou hloubku je v mém p°ípad¥ nerealizovatelné a tak z·stane pouze u domn¥nek na základ¥ získaných údaj·. Faktem je, ºe LP hraje nejlépe a má potenciál být rychlej²í a tím pádem výhodn¥j²í neº samotný Double oracle.
Kapitola 8
Záv¥r Provedené experimenty poskytují dostatek dat pro p°edstavu, jak ú£inné jsou zde pouºité metody pro°ezávání na h°e se simultánními tahy a velkým v¥tvícím faktorem. Z výsledk· m·ºeme usoudit, ºe v této h°e a za daných podmínek byl schopen nejvíce vyhrávat algoritmus LP. Na druhou stranu spot°eboval na hru nejvíce £asu, moºná aº neúm¥rn¥ k £asu, který pot°ebovali ostatní algoritmy. M·ºeme tedy °íct, ºe pokud budeme prohledávat stavový prostor do stejné hloubky, tak algoritmus LP porazí algoritmus Minimax. Co se tý£e Minimaxu, tak tento algoritmus dokáºe hrát pom¥rn¥ úsp¥²n¥. Pokud prohledává do v¥t²í hloubky neº LP, alespo¬ o 1, tak ho bez problém· poráºí. Samotný algoritmus je ²patný v tom, ºe je moc náro£ný na výpo£et z hlediska £asu. Expandování celého stavového prostoru je p°i hrách s velkým v¥tvícím faktorem velice náro£né. Jak je vid¥t v této práci, jednoduché pro°ezávání Alpha-beta je schopné tento algoritmus velice zrychlit. Sice toto zrychlení není garantované, ale ve v¥t²in¥ p°ípadech k n¥mu dochází. Na h°e Planet Wars, která se hodn¥ v¥tví, bylo pro°ezávání pom¥rn¥ úsp¥²né a algoritmus zrychlilo n¥kolikrát. Na druhou stranu, co pomáhalo k úsp¥chu algoritmu Alpha-beta, tak u²kodilo algoritmu MCTS. Tento algoritmus dokáºe v ur£itých p°ípadech hrát pom¥rn¥ úsp¥²n¥. Nikoliv ale na h°e s tak velkým v¥tvícím faktorem jako mají Planet Wars a s nedostatkem pam¥ti pro expandování v¥t²í £ásti stromu. Pro°ezávání aplikované na tento algoritmus také nebylo moc úsp¥²né a dokonce algoritmu i u²kodilo. Vzhledem k tomu, ºe k úsp¥²nému pro°ezávání je pot°eba dosáhnout dostate£ného mnoºství iterací a MCTS m¥l problémy s pam¥tí, pro°ezávání nejspí² od°ezávalo v¥tve, které naopak m¥ly ve výpo£tu z·stat. Tím negativn¥ ovlivnil výsledky algoritmu. Posledním a nejúsp¥²n¥j²ím byl algoritmus LP. Dokázal porazit v²echny ostatní algoritmy, ale výpo£et mu zabral více £asu. Algoritmus MCTS nebylo t¥ºké porazit, ale Alphabetu zvládl porazit v drtivé v¥t²in¥ her p°i stejné hloubce prohledávání. Pokud ale sníºíme spot°ebu £asu algoritmu LP, resp. sníºíme hloubku prohledávání, není pak schopen Minimax porazit. Co se tý£e pro°ezávání, tak algoritmus Double oracle, který funguje na principu p°idávání akcí do výpo£tu, je ve výsledku mnohem rychlej²í neº klasický lineární program, p°estoºe ho spou²tí víckrát. Roz²í°ení algoritmu Double oracle, prezentované v této práci, pak výpo£et je²t¥ urychlí, ale p°i výpo£tu do v¥t²ích hloubek. Na malých hloubkách je toto roz²í°ení dokonce o n¥co pomalej²í kv·li volání algoritmu Minimax pro odhadování výsledných hodnot. P°i experimentech do hloubky dv¥ by tedy nejspí²e fungoval rychleji samotný Double oracle neº pouºitá
44
KAPITOLA 8.
ZÁV
R
45
roz²í°ená verze. P°esto si myslím, ºe by tato cesta mohla být p°ínosem, protoºe bychom v¥t²inou cht¥li prohledávat hru do co nejv¥t²í hloubky a v tom p°ípad¥ je tato varianta mén¥ náro£n¥j²í na £as i na pam¥´.
Literatura [1] http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. [2] http://mcts.ai/?q=mcts. [3] http://planetwars.aichallenge.org/. [4] Bruno
Bouzy.
PROGRESSIVE
STRATEGIES
FOR
MONTE-CARLO
TREE
SEARCH. 2008. [5] Glenn Strong. The Minimax Algorithm. 2011. [6] Guillaume M. Chaslot, Mark H. Winands, and H. Jaap Herik.
Parallel montecarlo
tree search. CG '08: Proceedings of the 6th international conference on Computers and Games. 2008, , 21, s. 62.
[7] John Forbes Nash. Equilibrium points in n-person games. 1949. [8] Manish Jain, Dmytro Korzhyky, Ond°ej Van¥k, Vincent Conitzery, Michal P¥chou£ek, Milind Tambe. A Double Oracle Algorithm for Zero-Sum Security Games on Graphs. [9] Stuart Russell, Peter Norvig. Arti cial Intelligence: A Modern Approach (Third edition). 2010, s. 163170. [10] Tomá² Kozelek. MCTS methods in the game of Arimaa. 2009. [11] Yoav
Shoham,
Kevin
Leyton-Brown.
Multiagent
Theoretic, and Logical Foundations. 2008, s. 2933.
46
Systems:
Algorithmic,
Game-
Kapitola 9
Seznam pouºitých zkratek MCTS LP
Monte-Carlo Tree Search
Lineární program
47
Kapitola 10
Obsah p°iloºeného CD •
readme.txt - Návod na spu²t¥ní a obsluhu programu
•
text.pdf - Elektronická verze tohoto textu
•
testovaciData - Sloºka s testovacími daty - je zde vizualizátor, mapy a dal²í
•
zdrojaky.zip - Zdrojové kódy programu
48
