Metody generování strategií pro stochastické hry s nulovým součtem

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE Fakulta elektrotechnická Katedra kybernetiky

Metody generování strategií pro stochastické hry s nulovým součtem

Bakalářská práce

Studijní program: Otevřená informatika (bakalářský) Studijní obor: Informatika a počítačové vědy Vedoucí práce: Mgr. Branislav Bošanský, Ph.D.

Marek Kryška

Praha 2015

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra kybernetiky

ZADÁNÍ BAKALÁŘSKÉ PRÁCE Student:

Marek K r y š k a

Studijní program:

Otevřená informatika (bakalářský)

Obor:

Informatika a počítačové vědy

Název tématu:

Metody generování strategií pro stochastické hry s nulovým součtem

Pokyny pro vypracování: Dvouhráčové nekonečné stochastické hry, ve kterých jsou ohodnocení pouze v terminálních stavech, jsou důležitou třídou her s řadou potenciálních aplikací. Bohužel v současnosti neexistují efektivní a v praxi použitelné algoritmy pro výpočet optimálních strategií pro tuto třídu her. Standardní algoritmy, které využívají iterativní výpočet hodnot/strategií, mohou v nejhorším případě potřebovat až dvojitě exponenciální počet iterací. Cílem studenta je proto (1) prozkoumat možnosti využití inkrementálního rozšiřovaní prostoru strategií pro řešení stochastických her a adaptace přístupů úspěšných v konečných hrách, (2) experimentálně porovnat nově navržené algoritmy se standardními algoritmy pro řešení nekonečných stochastických modelů na sadě konkrétních her. Seznam odborné literatury: [1] Kristoffer Arnsfelt Hansen, Rasmus IbsenJensen, and Peter Bro Miltersen. "The complexity of solving reachability games using value and strategy iteration." Computer Science–Theory and Applications. Springer Berlin Heidelberg, 2011. 7790. [2] Branislav Bosansky, Viliam Lisy, Jiri Cermak, Roman Vitek, and Michal Pechoucek: Using Doubleoracle Method and Serialized AlphaBeta Search for Pruning in Simultaneous Moves Games. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). 2013. [3] Yoav Shoham, and Kevin LeytonBrown. Multiagent systems: Algorithmic, gametheoretic, and logical foundations. Cambridge University Press, 2009. Vedoucí bakalářské práce: Mgr. Branislav Bošanský, Ph.D. Platnost zadání: do konce letního semestru 2015/2016

L.S.

doc. Dr. Ing. Jan Kybic vedoucí katedry

prof. Ing. Pavel Ripka, CSc. děkan V Praze dne 14. 1. 2015

Prohl´ aˇ sen´ı autora pr´ ace Prohlaˇsuji, ˇze jsem pˇredloˇzenou pr´aci vypracoval samostatnˇe a ˇze jsem uvedl veˇsker´e pouˇzit´e informaˇcn´ı zdroje v souladu s Metodick´ ym pokynem o dodrˇzov´an´ı etick´ ych princip˚ u pˇri pˇr´ıpravˇe vysokoˇskolsk´ ych z´avˇereˇcn´ ych prac´ı. V Praze dne: . . . . . . . . . .

........................ Podpis autora pr´ace

Podˇ ekov´ an´ı Dˇekuji Mgr. Branislavu Boˇsansk´emu, Ph.D za jeho aktivn´ı pomoc a ˇzeleznou trpˇelivost pˇri tvorbˇe t´eto bakal´aˇrsk´e pr´ace. Jeho veden´ı a pˇripom´ınky mi velmi usnadnily jej´ı pˇr´ıpravu.

Abstrakt Teorie her se v dneˇsn´ı dobˇe prom´ıt´a do st´al´e vˇetˇs´ıho poˇctu discipl´ın. Lze jej´ı pomoc´ı ˇreˇsit jak samotn´e spoleˇcensk´e hry, od n´ıˇz je n´azev teorie her odvozen, tak pˇredevˇs´ım ekonomick´e, hospod´aˇrsk´e nebo vojensk´e c´ıle. Problematika zasahuje do kaˇzd´eho rozhodovac´ıho procesu, kde se u ´ˇcastn´ıci snaˇz´ı nˇejak predikovat chov´ an´ı ostatn´ıch vliv˚ u - jin´ ych hr´aˇc˚ u a maximalizovat uˇzitek sv˚ uj nebo nˇejak´e skupiny. Ovˇsem mnoh´e pˇreveden´ı re´aln´ ych pˇr´ıpad˚ u do matematick´eho modelu a pˇr´ıpadn´ ych dalˇs´ıch speci´ aln´ıch forem teorie her s sebou nese spoustu probl´em˚ u. Kromˇe neuchopitelnosti skuteˇcn´eho svˇeta do koneˇcn´eho poˇctu akc´ı a stav˚ u je to hlavnˇe probl´em rozs´ ahlosti a velikosti dat. S rostouc´ı velikost´ı hry roste i ˇcas jej´ıho zpracov´ an´ı, coˇz m˚ uˇze b´ yt kritick´e, pokud n´am z´aleˇz´ı na pˇresn´em v´ ysledku v re´ aln´em ˇcase. Kl´ıˇ cov´ a slova stochastick´ a nekoneˇcn´ a hra, Nashovo eqilibrium, hodnota hry, iteraˇcn´ı algoritmus

Abstract Game Theory is today reflected in a growing number of disciplines. With it we can solved the classic board games from which exists the current name of the game theory, but mainly economic, military or economic targets. The issue affects every decision-making process, where participants try to somehow predict the behavior of other influences - other players and maximize some profit. However, many real cases carries in a mathematical model or any other special forms of game theory a lot of problems. In addition to the difficult transfer of the real world into a finite number of events and conditions, it is mainly a problem of the breadth and size of data. With the growing size of the game grows the time of processing, which is critical if we depend on accurate results in real time. Keywords stochastic infinite game, Nash equlibrium, game value, iteration algorithm

Obsah ´ 1 Uvod

1

2 Teorie her 2.1 Hr´ aˇc . . . . . . . . . . . . . . . . . . . . . . 2.2 Stav hry . . . . . . . . . . . . . . . . . . . . 2.3 Hra . . . . . . . . . . . . . . . . . . . . . . . 2.4 Hra v norm´ aln´ı formˇe . . . . . . . . . . . . 2.5 Determinismus a stochasticita . . . . . . . . 2.6 Utilita . . . . . . . . . . . . . . . . . . . . . 2.7 Strategie . . . . . . . . . . . . . . . . . . . . 2.7.1 Strategie pro hry v norm´aln´ı formˇe . 2.7.2 Strategie pro stochastick´e hry . . . . 2.7.3 Nejlepˇs´ı reakce - optim´aln´ı strategie 2.8 Nashovo equlibrium . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

2 2 2 2 4 4 4 4 4 5 5 5

3 Iteraˇ cn´ı algoritmy, v´ ypoˇ cet strategi´ı a hodnota hry 3.1 Line´ arn´ı program pro optim´aln´ı strategie . . . . . . . 3.1.1 Pˇr´ıklad v´ ypoˇctu hodnoty hry a strategi´ı . . . . 3.2 Iterace hodnoty . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Pˇr´ıklad iterace hodnoty . . . . . . . . . . . . . 3.3 Iterace strategie . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Pˇr´ıklad iterace strategie . . . . . . . . . . . . . 3.4 Double Oracle . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Pˇr´ıklad Double Oracle algoritmu . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

6 7 8 9 9 11 11 14 14

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

4 Iteraˇ cn´ı algoritmy ve stochastick´ ych hr´ ach v nekoneˇ cnˇ e kroc´ıch 4.1 Anal´ yza probl´emu . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Algoritmus rozˇsiˇrov´ an´ı podhry . . . . . . . . . . . . . . . . . . . 4.2.1 Pˇr´ıklad na deterministick´e hˇre . . . . . . . . . . . . . . .

16 17 17 18

5 Popis experiment˚ u s v´ ysledky 5.1 Generov´ an´ı n´ ahodn´ ych her . . . . . . 5.2 Mˇeˇren´ı na konkr´etn´ıch pˇr´ıkladech . . . 5.2.1 Pˇr´ıklad na deterministick´e hˇre 5.2.2 Pˇr´ıklad na stochastick´e hˇre . . 5.3 Mˇeˇren´ı na vˇetˇs´ı sadˇe dat . . . . . . . .

21 21 22 22 23 24

6 Z´ avˇ er

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

27

Kapitola 1

´ Uvod Vypoˇcten´ı Nashova equliberia v nekoneˇcn´e stochastick´e hˇre tvoˇr´ı v teorii her velmi obt´ıˇznˇe ˇreˇsiteln´ y probl´em. Nejlepˇs´ı algoritmy pro jeho vyˇreˇsen´ı dok´azaly konvergovat pouze za omezen´ ych podm´ınek a na mal´ ych datech. Potenci´ al vyuˇzit´ı tohoto typu hry je ovˇsem obrovsk´ y. Napˇr´ıklad patrolov´an´ı hl´ıdek, tj. hra obr´ anc˚ uau ´toˇcn´ık˚ u, kdy nem´ame jasn´ y zaˇc´atek nebo konec hry, coˇz m˚ uˇze b´ yt napˇr´ıklad ochrana server˚ u pˇred hackersk´ ym u ´tokem nebo re´aln´e lodˇe hl´ıdkuj´ıc´ı pˇred pir´ aty. Stejnˇe tak to mohou b´ yt klasick´e stoln´ı hry, kter´e standardnˇe pracuj´ı s velkou sadou dat. Jak n´am mnoh´e pokusy ukazuj´ı, daˇr´ı se obˇcas vyˇreˇsit stochastickou hru, napˇr´ıklad algoritmus pro pˇribliˇzn´e ˇreˇsen´ı strategi´ı equlibria k tˇr´ıhr´ aˇcov´emu Texas hold’em [11]. Zaj´ımaj´ı n´ as pˇredevˇs´ım takov´e hry, kter´e maj´ı sv´e utility v termin´aln´ıch stavech. To nˇekdy vede k tomu, ˇze hodnota equliberia m˚ uˇze d´ıky vnitˇrn´ım cykl˚ um hry konvergovat velmi pomalu. V t´eto pr´ aci se pokus´ım uk´ azat, zda existuje nˇejak´a moˇznost, jak zmenˇsit prostor hry a t´ım pomoci k rychlejˇs´ı konvergenci iteraˇcn´ıch algoritm˚ u. Nejprve zavedu potˇrebn´e definice z teorie her, abych mohl uk´azat nejzn´amˇejˇs´ı algoritmy pro ˇreˇsen´ı Nashova equlibria. V dalˇs´ıch kapitol´ach zavedu nov´ y algoritmus, vych´ azej´ıc´ı z principu Double Oracle [10] algoritmu a provedu s n´ım experimenty na vlastn´ı sadˇe nagenerovan´ ych her.

1

Kapitola 2

Teorie her Pro zaˇc´ atek je tˇreba definovat z´akladn´ı pojmy teorie her z [3], pˇredevˇs´ım pak jistou podmnoˇzinu tohoto rozs´ahl´eho oboru, kterou budeme v dalˇs´ıch ˇc´ast´ech pr´ ace pouˇz´ıvat. Pro naˇse u ´ˇcely se budeme zab´ yvat striktn´ı podmnoˇzinou her a to takov´ ych, kter´ a jsou v s nulov´ ym souˇctem, jsou stochastick´e [4], nekoneˇcn´e (budeme je zapisovat do soutavy matic) a maj´ı pouze dva hr´aˇce.

2.1

Hr´ aˇ c

Hr´ aˇc je entita, kter´ a rozhoduje jak´e akce ve hˇre bude hr´at. U hr´aˇce je d˚ uleˇzit´a jeho racion´ alnost, tj. jak´ ym zp˚ usobem akce vol´ı, pˇr´ıpadnˇe podle jak´ ych strategi´ı. Jakoˇzto racion´ aln´ıho hr´ aˇce definujeme takov´eho, kter´ y vol´ı akce strategi´ı tak, aby maximalizoval sv˚ uj zisk. V tomto textu ho budeme znaˇcit jako Hr´ aˇc i, kde i je index hr´aˇce.

2.2

Stav hry

Je urˇcit´ a situace ve hˇre. Hr´ aˇci v n´ı vyberou sv´e akce a pot´e se podle zahran´ ych akc´ı hra pˇresouv´ a do dalˇs´ıho stavu. Speci´aln´ımi stavy ve hˇre jsou stavy koncov´e, resp. termin´ aln´ı. To jsou stavy ve kter´ ych hra konˇc´ı, kdy se nelze dostat do ˇz´ adn´eho dalˇs´ıho stavu a hr´ aˇci z´ısk´avaj´ı nˇejakou v´ yhru danou utilitn´ı funkc´ı. Ostatn´ım stav˚ um ˇr´ık´ ame pˇrechodn´e a slouˇz´ı k pˇrechodu do jin´ ych pˇredchodn´ ych nebo koncov´ ych stav˚ u. Dalˇs´ım speci´aln´ım stavem je stav poˇc´ateˇcn´ı, kde hra zaˇc´ın´ a. V tomto textu budeme stav hry reprezentovat jako matici, kde kaˇzd´e pol´ıˇcko ud´ av´ a kombinaci dvou akc´ı jednotliv´ ych hr´aˇc˚ u. V´ıce v kapitole 3 a na Obr´ azku 3.2.

2.3

Hra

Je soubor pravidel a podm´ınek, za jak´ ych mohou jednotliv´ı hr´aˇci volit akce a v jak´em poˇrad´ı, kter´e pak vedou k nˇejak´emu v´ ysledku. Hru lze zapsat jak maticovˇe, tak i formou stromu, kde kaˇzd´ y uzel (v matici jej´ı jedna hrana) pˇriˇrazuje dan´emu hr´ aˇci jeho akce.

2

U her v naˇsem pˇr´ıpadˇe pˇredpokl´ad´ame, ˇze kaˇzd´ y vyplacen´ y zisk za dohr´an´ı hry jendomu hr´ aˇci je na u ´kor ostatn´ıch hr´aˇc˚ u. To znamen´a, ˇze pˇri zahr´an´ı vˇsech strategi´ı vˇsech hr´ aˇc˚ u d´ av´ a suma vyplacen´ ych v´ yher dohromady nulu. Takov´e hry definujeme jako hry s nulov´ym souˇctem. Pro ilustraci je na Obr´ azku 2.1 uvedena hra s nulov´ ym souˇctem, kde po dohr´ an´ı prvn´ı akce hr´ aˇci okamˇzitˇe dost´avaj´ı hodnotu utility. Graf zn´azorˇ nuje vˇsechny moˇznosti, jak mohou hr´aˇci sv´e akce volit. B´ıl´a pole urˇcuj´ı, kter´a akce byla zvolena.

-1,1

0,0

-2,2

-4,4

-1,1

0,0

-1,1

0,0

-1,1

0,0

-1,1

0,0

-2,2

-4,4

-2,2

-4,4

-2,2

-4,4

-2,2

-4,4

Obr´ azek 2.1: Pˇr´ıklad hry s nulov´ ym souˇctem ve formˇe grafu Tato hra je pˇreveden´ a do maticov´e formy na Obr´ azku 2.2. Dimenze matice pˇriˇrazuje hr´ aˇc˚ um poˇcet jejich akc´ı, tady konkr´etnˇe pro Hr´aˇce 1 akce ai,j a Hr´aˇci 2 bi,j .

Hra: 1

b1,1

b1,2

a1,1

-1,1

0,0

a1,2

-2,2

-4,4

Obr´ azek 2.2: Pˇr´ıklad hry s nulov´ ym souˇctem v maticov´e formˇe Zde naz´ yv´ ame matici hrou. Je to speci´aln´ı pˇr´ıpad pro jednostavovou hru. Jako hru vˇsak budeme d´ ale v textu reprezentovat soustavu matic. Tedy jedna matice znaˇc´ı stav hry.

3

2.4

Hra v norm´ aln´ı formˇ e

Nejˇcastˇejˇs´ım vyj´ adˇren´ım hry je hra v tzv. norm´alov´e formˇe. Jde o pˇresn´ y popis uzavˇren´e mnoˇziny vˇsech akc´ı pro kaˇzd´eho hr´aˇce hry. U hry v norm´aln´ım tvaru se pˇredpokl´ ad´ a, ˇze hr´ aˇci vol´ı sv´e akce z´aroveˇ n a nemaj´ı pˇrehled o taz´ıch protihr´aˇc˚ u [3]. Definice 1 Koneˇcn´ a n-hr´ aˇcov´ a hra A je v norm´ aln´ı formˇe, tj. trojice (N, A, u) pokud: • N je koneˇcn´ a mnoˇzina n-hr´ aˇc˚ u, idexovan´e i = {1, 2, ..., n} • A = A1 × ... × An , Ai je koneˇcn´ a mnoˇzina akc´ı dostupn´ych pro hr´ aˇce i • u = u1 × ... × un , kde ui 7→ < je utilitn´ı (v´yplatn´ı) funkce pro hr´ aˇce i Definice 2 Stochastickou n-hr´ aˇcovou hru A naz´yv´ ame nekoneˇcnou, jestliˇze nem´ ame zaruˇcenou konvergenci strategi´ı vˇsech hr´ aˇc˚ u v re´ aln´em ˇcase. To znamen´ a, ˇze hra je sice pops´ana koneˇcnˇe mnoho stavy, ale jejich vz´ajemn´e propojen´ı m˚ uˇze vytv´ aˇret cykly a t´ım zvyˇsovat ˇcasovou sloˇzitost ˇreˇsen´ı hry. [4] Pro generov´ an´ı nekoneˇcn´e hry m˚ uˇzeme vyuˇz´ıt napˇr´ıklad koneˇcn´y automat.

2.5

Determinismus a stochasticita

Pojmem stochasticita (n´ ahodnost) resp. stochastick´a hra rozum´ıme hru takovou, kde figuruje prvek n´ ahody. Kaˇzd´ y souhrn akc´ı vede na pravdˇepodobnostn´ı rozloˇzen´ı moˇzn´ ych n´ asledn´ ych c´ıl˚ u (stav˚ u). V teorii her naz´ yv´ame stochastick´e hry ˇcasto hrami nekoneˇcn´ ymi se stochastick´ ymi pˇrechody [6]. Naopak determinismus (pˇredurˇcenost), pˇr´ıpadnˇe deterministick´a hra, je hra takov´ a, kde souhrn akc´ı vˇsech hr´aˇc˚ u vede pˇresnˇe k jednomu stavu ve hˇre. Deterministick´ a hra je tedy v podstatˇe hra stochastick´a, kde v´ıme se stoprocentn´ı pravdˇepodobnost´ı n´ avaznost stav˚ u.

2.6

Utilita

Utilita neboli zisk ohodnocuje danou hru. M˚ uˇze b´ yt z´ısk´av´ana jak po jednotliv´ ych kolech, tak po dohr´ an´ı cel´e hry. Nejˇcastˇeji se reprezentuje formou tzv. v´yplatn´ı matice. Ta urˇcuje, jakou hodnotu dan´ y hr´aˇc pro pˇr´ısluˇsn´e kolo z´ısk´a. Druh´ ym zp˚ usobem je reprezentace formou utilitn´ı funkce, kter´a kaˇzd´e kombinac´ı akc´ı pˇriˇrazuje hodnotu v´ yhry. Podle tˇechto hodnot pak hr´aˇc tvoˇr´ı svou strategii, aby takov´ yto zisk maximalizoval. V naˇsem pˇr´ıpadˇe budeme uvaˇzovat, ˇze zisk je pouze v koncov´ ych stavech. Jelikoˇz se jedn´ a o hry s nulov´ ym souˇctem, hodnota v´ yhry jednoho hr´aˇce se bude rovnat ztr´ atˇe hr´ aˇce poraˇzen´eho.

2.7 2.7.1

Strategie Strategie pro hry v norm´ aln´ı formˇ e

Strategie definuje akce, kter´e hr´aˇc zvol´ı pro stav hry. Pokud hr´aˇc vol´ı pouze jednu akci pro kaˇzd´ y stav, ˇr´ık´ a se se takov´e startegii ryz´ı startegie. Jestliˇze jsou akce 4

n´ ahodn´e (podle nˇejak´e distribuce pravdˇepodobnosti), naz´ yv´ame takovou startegii sm´ıˇsenou startegi´ı. Mnoˇzinˇe strategi´ı pˇres vˇsechny akce ˇr´ık´ame profil dan´e strategie. Strategie m˚ uˇze b´ yt zaloˇzen´a na r˚ uzn´ ych pˇredpovˇed´ıch. Ty urˇcujeme podle toho, jak budou protihr´ aˇci hr´at, coˇz m˚ uˇze z´aviset na nˇejak´e vnˇejˇs´ı informaci nebo rozhodnut´ı hr´ aˇc˚ u v pˇredchoz´ıch kolech hry (minulost hry)[3].

2.7.2

Strategie pro stochastick´ e hry

Strategie pro stochastick´e hry je tedy strategi´ı sm´ıˇsenou. M˚ uˇzeme ji reprezentovat jako vektor ˇc´ısel mezi 0 aˇz 1 o velikosti poˇctu akc´ı pro danou hern´ı matici. Obecnˇe ji definujeme jako: Definice 3 Necht’ je mnoˇzna (N, A, u) hra v norm´ aln´ı formˇe a pro kaˇzdou mnoˇzinu X necht’ je Π(X) mnoˇzina vˇsech pravdˇepodobnostn´ıch rozloˇzen´ı nad mnoˇzinou X. Pak mnoˇzina sm´ıˇsen´ych strategi´ı pro hr´ aˇce i je Si = Π(Ai ). Definice 4 Stochastickou strategi´ı jednoho hr´ aˇce mysl´ıme mnoˇzinu sm´ıˇsen´ych strategi´ı {s1i , s2i , ..., ski }, kde i je index hr´ aˇce a k je poˇcet stav˚ u hry.

2.7.3

Nejlepˇ s´ı reakce - optim´ aln´ı strategie

Pokud v´ıme, jak´e akce budou protihr´aˇci volit (napˇr´ıklad pˇredpokl´ad´ame, ˇze jsou plnˇe inteligentn´ı a hraj´ı sv´e optim´aln´ı strategie), jsme schopni dopoˇc´ıtat ryz´ı strategii takovou, ˇze maximalizuje prospˇech pˇri takto zahran´ ych profilech strategi´ı. Takov´ a strategie se naz´ yv´a nejlepˇs´ı reakc´ı na mnoˇzinu strategi´ı protihr´aˇc˚ u [9].

2.8

Nashovo equlibrium

Mnoˇzinu strategi´ı naz´ yv´ ame Nashov´ ym equlibriem, [9] pokud kaˇzd´a strategie πi je nejlepˇs´ı moˇznou reakc´ı na vˇsechny strategie πj , kde i, j jsou indexy hr´aˇc˚ u, N je jejich poˇcet a plat´ı j 6= i, j, i ∈ {1, 2, .., N }. V naˇsem pˇr´ıpadˇe dvou protihr´aˇc˚ u je N = 2. Strategie kaˇzd´eho hr´aˇce je tedy nejlepˇs´ı moˇznou reakc´ı na vˇsechny ostatn´ı strategie zbyl´ ych hr´ aˇc˚ u, tud´ıˇz kaˇzd´ y hr´aˇc hraje svoji optim´aln´ı strategii. Oˇcek´ avan´ y zisk prvn´ıho hr´ aˇce se naz´ yv´a hodnota hry a znaˇc´ıme ji ν ∗ . Aˇckoliv m˚ uˇze na jedn´e hˇre existovat v´ıce Nashov´ ych equlibri´ı, hodnota hry pro tento optim´ aln´ı pˇr´ıpad z˚ ust´ av´ a pokaˇzd´e stejn´a (toto n´am zaruˇcuje pˇredpoklad, ˇze se pohybujeme ve hr´ ach s nulov´ ym souˇctem).

5

Kapitola 3

Iteraˇ cn´ı algoritmy, v´ ypoˇ cet strategi´ı a hodnota hry V t´eto sekci si zavedeme dva nejzn´amˇejˇs´ı algoritmy pro v´ ypoˇcet hodnoty hry ν ∗ a hodnot strategi´ı [6] [5] Nashova equlibria. Pro n´azornost zav´ad´ıme n´ahodnˇe vygenerovanou hru, na kter´e si uk´aˇzeme, jak algoritmy funguj´ı. Definice 5 Mˇejme hru zadanou tak, ˇze m´ a pouze deterministick´e pˇrechody mezi stavy, dva hr´ aˇce a velikost o N stavech. Pˇridejme ke hˇre dalˇs´ı dva termin´ aln´ı stavy: Stav 0 a Stav N+1, kde N+1 stav urˇcuje v´yhru prvn´ıho hr´ aˇce a stav 0 v´yhru druh´eho hr´ aˇce. Uvaˇzujme konkr´etnˇe zadanou hru z Obr´ azku 3.1. K ohodnocen´ı termin´aln´ıch stav˚ u zvol´ıme vhodnou konstantu, tedy v naˇsem pˇr´ıpadˇe budou v´ ysledky z intervalu <0,1>. Zbyl´e stavy, jeˇz nemaj´ı zapsanou ˇz´adnou hodnotu, jsou pˇrechodn´e do stavu, kam smˇeˇruje ˇsipka. Hr´aˇc 1 vol´ı ˇr´adkov´e akce a Hr´aˇc 2 vol´ı akce sloupcov´e. Hr´ aˇc 1 m´ a tedy u prvn´ıho stavu k dispozici tˇri akce a Hr´aˇc 2 m´a napˇr´ıklad u druh´eho stavu k dispozici akce ˇctyˇri.

1

0

Obr´azek 3.1: Schema hry Pokud tˇreba Hr´ aˇc 1 zvol´ı v prvn´ı stavu svoj´ı druhou akci a Hr´aˇc 2 zvol´ı akci prvn´ı, pˇrechod ze stavu jedna je zpˇet do stejn´eho stavu. Kdyby ale Hr´aˇc 1 zvolil svoj´ı prvn´ı akci ve stavu jedna, dostali bychom se do termin´aln´ıho stavu, hra by skonˇcila a Hr´ aˇc 1 by vyhr´ al hru. Takto hr´aˇci vol´ı sv´e akce, aby maximalizovali ˇsanci probojovat se ke sv´ ym termin´aln´ım c´ıl˚ um skrze vˇsechny stavy hry.

6

Pro pˇrehlednost budeme hru zapisovat maticemi pˇrechodu z Obr´ azek 3.2, kde hodnota buˇ nky matice urˇcuje stav, do kter´eho se hr´aˇci pˇri zahr´an´ı pˇr´ısluˇsn´ ych akc´ı dostanou. Hodnoty utilit koncov´ ych stav˚ u zvol´ıme u2 = 0 a u1 = 1, ale aby nedoˇslo z´ amˇenˇe za pˇrechod, do matice je nep´ıˇseme.

1 2 2

0

3

3 2

u2

1

3

1

2

u1 2

3

0

3

1

2

0

Obr´ azek 3.2: Hra pˇrepsan´a na matici pˇrechodu

3.1

Line´ arn´ı program pro optim´ aln´ı strategie

Nashovo equlibrium jsme schopni naj´ıt pomoc´ı n´asleduj´ıc´ıho line´arn´ıho programu [7]. Ten vych´ az´ı z line´ arn´ıch program˚ u pro jednotliv´e hr´aˇce, kde se oba hr´ aˇci Ni , kde i ∈ {1, 2} snaˇz´ı maximalizovat svoj´ı hodnotu hry Ui∗ . Jelikoˇz se pohybujeme ve hr´ ach s nulov´ ym souˇctem, v´ıme U1∗ = −U2∗ . Prvn´ı hr´aˇc se tedy ∗ snaˇz´ı maximalizovat U1 pˇres vˇsechny akce a stretegii protihr´aˇce a druh´ y hr´aˇc usiluje o tot´eˇz s v´ yjimkou toto, ˇze U1∗ minimalizuje. Pokud line´arn´ı programy obou hr´ aˇc˚ u spoj´ıme do jednoho, dost´av´ame: Definice 6 Line´ arn´ı program pro optim´ aln´ı strategie obou hr´ aˇc˚ u je [3]: minimalizace U1∗ za podm´ınek X

u1 (aj1 , ak2 ) · sk2 + r1j = U1∗

∀j ∈A1

k ∈A2

X

sk2 = 1

k ∈A2 sk2 ≥ 0 r1j ≥ 0

∀k ∈A2 ∀j ∈A1

7

3.1.1

Pˇ r´ıklad v´ ypoˇ ctu hodnoty hry a strategi´ı

Pro v´ ypoˇcet hodnoty hry, potaˇzmo strategi´ı jednotliv´ ych hr´aˇc˚ u, bychom potˇrebovali zn´ at ohodnocen´ı jednotliv´ ych akc´ı ve stavech hry. To se d´a vypoˇc´ıtat z hodnotov´e iterace. To jak funguje si uk´aˇzeme pozdˇeji, proto si vyp˚ ujˇc´ıme tˇret´ı iteraci tohoto algoritmu, abychom na nˇem demonstrovali n´ aˇs line´ arn´ı program. M´ ame tedy stavy hry po tˇret´ım bˇehu programu pro hodnotovou iteraci z Obr´ azku 3.2 ohodnocen´e takto:

1 2 0

0.0

1.0

3 0.0

0

0.5

1.0

0.5

0.0

1 0.0

1.0

0.0

1.0

0.5

0.0

0.0

Obr´ azek 3.3: Hodnota vektoru stav˚ u pˇri tˇret´ı iteraci algoritmu Value Iteration Stav 1 Dosazen´ım do definice dost´ av´ ame soustavu rovnic s podm´ınkou: min U1∗ 0.0 · s02 + 1.0 · s12 + r10 = U1∗ 0.5 · s02 + 0.0 · s12 + r11 = U1∗ 1.0 · s02 + 0.0 · s12 + r12 = U1∗ , kde suma sk2 sˇc´ıt´ a do jedniˇcky a spolu se slackov´ ymi promˇenn´ ymi r1j jsou rovny nebo vˇetˇs´ı nule. Po vyˇreˇsen´ı dost´ av´ ame: U1∗ = 0.5 s2 = [0.5, 0.5] a snadno pak dopoˇc´ıt´ ame strategii prvn´ıho hr´aˇce: s1 = [0.5, 0.0, 0.5] Tento pˇr´ıklad stavu je jednoduch´ y, lze ho vyˇreˇsit i u ´vahou. Pokud se pod´ıv´ame na akce, kter´e m˚ uˇze zvolit sloupcov´ y hr´aˇc (tj. Hr´ aˇc 2 v naˇsem znaˇcen´ı), je vidˇet, ˇzˇe v obou sloupc´ıch se objevuje v´ıtˇezn´a hodnota pro oba hr´aˇce. Sloupcov´ y hr´aˇc nem˚ uˇze zablokovat ˇr´ adkov´emu hr´aˇci pˇrechod, kde se vyskytuje hodnota 1.0. Je mu tedy jedno, kterou akci zvol´ı, protoˇze v obou sloupc´ıch je jeho v´ıtˇezn´a hodnota 0.0. Stejnˇe tak hr´ aˇc ˇr´ adkov´ y (tj. Hr´ aˇc 1 ) vyb´ır´a mezi prvn´ı a posledn´ı akc´ı. Proto maj´ı pro tyto ˇr´ adky a sloupce jejich strategie hodnotu 0.5. Z toho vypl´ yv´ a i hodnota hry U1∗ = 0.5.

8

Stav 2 Analogicky bychom mohli dosadit do rovnic. Kdyˇz se ale pozornˇe na hru pod´ıv´ame, je zˇrejm´e, ˇze pokud sloupcov´ y hr´aˇc zvol´ı svou prvn´ı akci (pˇresun do sv´eho v´ yhern´ıho termin´ aln´ıho stavu), m´a v´ yhru jistou, at’ ˇr´adkov´ y hr´aˇc hraje jakoukoliv strategii. Proto hodnota hry bude U1∗ = 0.0, sloupcov´ y hr´aˇc bude hr´at ryz´ı strategii s2 = [1.0, 0.0, 0.0, 0.0] a na strategii ˇr´adkov´eho hr´aˇce nez´aleˇz´ı pro v´ ypoˇcet hodnoty hry.

3.2

Iterace hodnoty

Prvn´ı z iteraˇcn´ıch algoritm˚ u, nazvan´ y iterace hodnoty, pracuje na myˇslence ohodnocov´ an´ı v´ ysledku kaˇzd´ ych dvojic akc´ı podle hodnot hry stavu, do kter´eho podle zvolen´ ych akc´ı se hr´ aˇci dostanou. Iterativn´ı je tento algoritmus, jelikoˇz opakovanˇe propoˇc´ıt´ av´ a hodnoty jednotliv´ ych stav˚ u hry a konˇc´ı, aˇz pokud v´ ysledky dvou po sobˇe jdouc´ıch iterac´ı maj´ı rozd´ıl menˇs´ı, neˇz je ukonˇcovac´ı podm´ınka ε = poˇzadovan´ a pˇresnost [8]. Data: Ukonˇcovac´ı podm´ınka pˇresnosti Result: Hodnota hry 1 t := 0; 0 0 2 v := (0, ..., 0, 1) ; // kde vektor v je indexov´ an 0, 1, ...,N, N+1 3 while |vt − vt−1 | > ε do 4 t := t+1; 5 v0t := 0; t 6 vN +1 := 1; 7 for j ∈ {1, 2, .., N }do 8 vjt := val(Aj (v t−1 )); Algorithm 1: Iterace hodnoty [1] t−1 Funkc´ı val(Aj (v )) rozum´ıme v´ ypoˇcet hodnoty hry. Aj zde reprezentuje mnoˇzinu akc´ı pro j-t´ y stav hry A. Pot´e, co je spoˇctena hodnota hry pro vˇsechny stavy, kaˇzd´ a matice stav˚ u ohodnot´ı sv´e akce pˇr´ısluˇsnou hodnotou hry stavu, do kter´eho pˇrech´ az´ı. Toto ohodnocen´ı je pak jeˇstˇe pˇren´asobeno pravdˇepodobnost´ı, jeˇz urˇcuje, zda se do stavu v˚ ubec dostane. V n´ıˇze uveden´ ych pˇr´ıkladech zavedeme ve stavech hry n´asleduj´ıc´ı znaˇcen´ı: Hodnota v poli matice je hodnota utility a spodn´ı index je stav do kter´eho se hr´ aˇci po zahr´ an´ı pˇr´ısluˇsn´ ych akc´ı dostanou.

3.2.1

Pˇ r´ıklad iterace hodnoty

V pseudok´ odu algoritmu vid´ıme, ˇze vektor v 0 m´a d´elku rovnu poˇctu stav˚ u hry. Hodnoty jednotliv´ ych vi0 urˇcuj´ı hodnotu hry dan´eho stavu, tedy prvn´ı a posledn´ı ˇc´ıslo vektoru v 0 urˇcuje hodnotu hry termin´aln´ıch stav˚ u. To je trivi´alnˇe hodnota termin´ aln´ıch stav˚ u. Ostatn´ım stav˚ um nastav´ıme implicitnˇe nuly. Kaˇzd´ y z prvk˚ u vektoru je vlastnˇe jedna matice. Termin´aln´ı stavy maj´ı rozmˇer 1x1 a ostatn´ı pˇrechodn´e podle naˇseho pˇr´ıkladu 3x2 a 2x4. Zvol´ıme ukonˇcovac´ı podm´ınku napˇr´ıklad takto: ε = 0.01, t´ım v praxi ˇr´ık´ame, ˇze n´am z´aleˇz´ı pouze na prvn´ıch dvou desetinn´ ych m´ıstech v´ ysledku.

9

v 1 = (0.0, 0.0, 0.0, 1.0) 1 2 0

0.02

0.03

3 0.02

0

0.01

0.03

0.00

0.01

0.02

1 0.02

0.03

0.03

0.01

0.02

0.00

Obr´ azek 3.4: Algoritmus iterace hodnoty, t = 1 Zaˇc´ın´ ame iterovat. Za kaˇzdou pozici vektoru vit , kde t je poˇc´ıtadlo iterace, postupnˇe poˇc´ıt´ ame hodnotu hry dan´eho stavu podle line´arn´ıho programu. Pot´e pˇriˇrazujeme hodnoty her k jednotliv´ ym akc´ım. v 2 = (0.0, 0.5, 0.0, 1.0) 1 2 0 0

0.02

1.03

0.01

3 0.02

1.03

0.00

0.01

0.02

1.03

0.01

0.02

0.02

1.03

1

0.00

Obr´ azek 3.5: Algoritmus iterace hodnoty, t = 2 Algoritmus tak vlastnˇe propisuje hodnoty ”od konce grafu”. V prvn´ı iteraci se objev´ı pouze hodnoty u stav˚ u pˇrechodn´ ych k stav˚ um termin´aln´ım a aˇz pozdˇeji se prop´ıˇs´ı i hodnoty d´ al, podle toho jak jsou nav´azan´e pˇrechody mezi stavy. v 3 = (0.0, 0.5, 0.0, 1.0) 1 2 0

0.02

1.03

3 0.02

0

0.51

0.00

0.51

0.02

1 0.02

1.03

1.03 1.03

0.51

0.02

0.00

Obr´ azek 3.6: Algoritmus iterace hodnoty, t = 3 10

Vid´ıme, ˇze tento pˇr´ıklad je skuteˇcnˇe trivi´aln´ı. Algoritmus skonˇc´ı po pouh´ ych tˇrech iterac´ıch. Ukonˇcovac´ı konstanta ε = 0.01, tedy byla dokonce nadsazen´a. Jak´ akoliv na zaˇc´ atku zadan´ a vyˇsˇs´ı pˇresnost v´ ysledek neovlivn´ı, protoˇze dalˇs´ı iterace nemˇen´ı hodnoty her pro jednotliv´e stavy. Hodnota hry je U1∗ = 0.5.

3.3

Iterace strategie

Druh´ y z iteraˇcn´ıch algoritm˚ u, tedy iterace strategi´ı, je vlastnˇe rozˇs´ıˇren´ım hodnotov´e iterace. Znovu tu postupnˇe dopoˇc´ıt´av´ame hodnoty her a pˇriˇrazujeme utility dan´ ym kombinac´ım akc´ı. Z´ aroveˇ n se vˇsak kontroluje, jestli neexistuje pro hr´aˇce lepˇs´ı tzv. optim´ aln´ı strategie. Z iterace hodnoty zjist´ıme strategie pro stavy hry (pˇren´ asoben´e souˇcasn´ ymi strategiemi hr´aˇc˚ u) a podle nich optimalizujeme (pokud to jde) iterovan´e startegie. Iterace strategie zpravidla konverguje velmi rychle na mal´ ych datech. Naopak na vˇetˇs´ıch hr´ ach je rychlost konvergence v´ yraznˇe pomalejˇs´ı neˇz u iterace hodnoty. To je zapˇr´ıˇcinˇeno t´ım, ˇze se mus´ı vyˇreˇsit velk´ y prostor line´arn´ıch rovnic. Algoritmus ukonˇcujeme (stejnˇe jako u hodnotov´e iterace), pokud rozd´ıl ohodnocen´ ych stav˚ u u dvou po sobˇe jdouc´ıch iterac´ı je menˇs´ı neˇz podm´ınka pˇresnosti ε [8].

1 2 3 4 5 6 7 8 9 10 11 12

Data: Ukonˇcovac´ı podm´ınka pˇresnosti Result: Optim´ aln´ı strategie hr´aˇc˚ u hry t := 1; s11 := poˇc´ ateˇcn´ı strategie pro Hr´aˇce 1; while true do st2 :=optim´ aln´ı strategie na st1 ; for i ∈{0, 1, 2,..,N, N+1}do vit := µi (st1 , st2 ); t := t+1; for i ∈ {1, 2, .., N }do if val(Ai (v t−1 )) > v t−1 then st1,i := maxmin(Ai (v t−1 )); else xt1,i := xt−1 1,i ;

13

Algorithm 2: Iterace strategie [1] Funkce poˇc´ıt´ a n´ asobek strategi´ı st1 a st2 v˚ uˇci dan´emu ohodnocen´ı stavu, tedy jednoltliv´ ym pˇrechod˚ um d´av´a pravdˇepodobnost, ˇze se uskuteˇcn´ı. Procedura maxmin(Ai (v t−1 )) pˇriˇrazuje Hr´aˇci 1 jeho maximalizuj´ıc´ı strategii vypoˇctenou z line´ arn´ıcho programu. µi (st1 , st2 )

3.3.1

Pˇ r´ıklad iterace strategie

Inicializujeme si vektor v 0 stejnˇe jako u iterace strategie. Akce, kter´e vedou rovnou k termin´ aln´ım stav˚ um, dostanou pˇr´ısluˇsnou utilitu. D´ale je potˇreba nastavit si profily strategi´ı jednotliv´ ych hr´aˇc˚ u. Hr´aˇci 1 nastav´ıme libovolnou poˇc´ ateˇcn´ı strategii a Hr´ aˇce 2 nech´ame spoˇc´ıtat hodnotu nejlepˇs´ı reakce na strategii ˇr´ adkov´eho hr´ aˇce. Hr´ aˇc 1 zde zaˇc´ın´a s ryz´ı strategi´ı pro prvn´ı akci. Pro srovn´ an´ı s hodnotovou iterac´ı vol´ıme ε = 0.01. 11

Stav Stav Stav Stav

1: 1: 2: 2:

s11 s12 s11 s12

= = = =

[1.0, [1.0, [1.0, [1.0,

0.0, 0.0] 0.0] 0.0] 0.0, 0.0, 0.0]

1 2 0

0.02

0

0.03

0.01

3 0.02

0.03

0.00

0.01

0.02

0.03

0.01

0.02

0.02

0.03

1

0.00

Obr´ azek 3.7: Algoritmus iterace strategie, t = 1

Stav Stav Stav Stav

1: 1: 2: 2:

s21 s22 s21 s22

= = = =

[1.0, [1.0, [1.0, [1.0,

0.0, 0.0] 0.0] 0.0] 0.0, 0.0, 0.0]

1 2 0

0.02

1.03

3 0.02

0

0.01

0.00

0.01

0.02

1 0.02

1.03

1.03 1.03

0.01

0.02

0.00

Obr´ azek 3.8: Algoritmus iterace strategie, t = 2 Algoritmus pot´e podle takto dan´ ych strategi´ı pˇrepoˇc´ıt´a hodnoty pro vˇsechny akce ve stavech hry a udˇel´ a z nich sumu µi (st1 , st2 ). Tu pak porovn´av´a s hodnotou hry vypoˇctenou line´ arn´ım programem. Pokud je hodnota hry vyˇsˇs´ı neˇz avaj´ıc´ı strategie Hr´aˇce 1 strategi´ı z line´arn´ıho programu. µi (st1 , st2 ), nahrad´ı se st´ Stav Stav Stav Stav

1: 1: 2: 2:

s31 s32 s31 s32

= = = =

[0.5, [1.0, [1.0, [1.0,

0.0, 0.5] 0.0] 0.0] 0.0, 0.0, 0.0]

12

Vid´ıme, ˇze strategie Hr´ aˇce 1 se jiˇz pˇrizp˚ usobila nov´emu ohodnocen´ı akc´ı prvn´ıho stavu. To je d´ ano t´ım, ˇze hodnota funkce:   0.0 1.0     1.0 µi (s21 , s32 ) = 1.0 0.0 0.0 · 0.0 0.0 · =0 0.0 1.0 0.0 Ovˇsem hodnota hry prvn´ıho stavu je 0.5, coˇz je lepˇs´ı hodnota neˇz 0. Vezmeme strategii z line´ arn´ıho programu a dostaneme [0.5, 0.0, 0.5], jakoˇzto novou startegii s31 pro Hr´ aˇce 1. 1 2 0.02

0 0

1.03

0.51

3 0.02

1.03

0.00

0.51

0.02

1.03

0.51

0.02

0.02

1.03

1

0.00

Obr´ azek 3.9: Algoritmus iterace strategie, t = 3 A stejnˇe tak na zmˇenu strategie Hr´aˇce 2 zareagoval Hr´aˇc 1. Jiˇz ted’ vid´ıme, ˇze n´ asleduj´ıc´ı iterace bude posledn´ı, protoˇze se hodnoty matic shoduj´ı s ohodnocen´ımi posledn´ı iterace hodnotov´eho algoritmu. Stav Stav Stav Stav

1: 1: 2: 2:

s41 s42 s41 s42

= = = =

[0.5, [1.0, [1.0, [1.0,

0.0, 0.5] 0.0] 0.0] 0.0, 0.0, 0.0]

1 2 0

0.02

1.03

0

0.51

0.02

3 0.02

1.03

0.51 1

0.02 1.03

0.00

1.03

0.51

0.02

0.00

Obr´ azek 3.10: Algoritmus iterace strategie, t = 4 Hodnota hry je po ˇctyˇrech iterac´ıch U1∗ = 0.5, tedy zkonvergovala ke stejn´e hodnotˇe hry jako u hodnotov´e iterace.

13

3.4

Double Oracle

Do tˇretice si zavedeme Double Oracle algoritmus, jehoˇz myˇslenky a principy d´ ale vyuˇzijeme pro ˇreˇsen´ı probl´emu rozˇsiˇrov´an´ı matic stav˚ u [2] [10]. Algoritmus pracuje na myˇslence postupn´eho pˇrid´av´an´ı akc´ı, kter´e mohou ovlivnit hru. Vezmeme stav, kter´ y m´a ohodnocen´e kombinace akc´ı nˇejakou utilitn´ı funkc´ı. Zaˇc´ın´ ame s malou podmnoˇzinou akc´ı. Na ni vypoˇc´ıt´ame hodnoty Nashova equlibria, tj. jejich optim´ aln´ı strategie. Pak kaˇzd´emu hr´aˇci na tuto startegii nech´ ame prov´est nejlepˇs´ı reakci ve formˇe ryz´ı strategie. Akce, kter´e hr´aˇci zvolili pˇrid´ ame do mnoˇziny a tento proces opakujeme, dokud uˇz nelze do mnoˇziny ˇz´ adn´e akce pˇrid´ avat. Dalˇs´ı akce se nepˇridaj´ı, jelikoˇz rozˇs´ıˇren´ı mnoˇziny akc´ı jednoho hr´ aˇce nezmˇen´ı optim´ aln´ı strategii druh´eho hr´aˇce, tedy tato akce nijak neovlivˇ nuje hodnotu Nashova equlibria. T´ımto zp˚ usobem se zbav´ıme akc´ı, o kter´ ych v´ıme, ˇze hodnotu hry nezmˇen´ı, tedy ˇz´adn´ y z hr´aˇc˚ u by ji nikdy pˇri souˇcasn´em stavu hry nehr´ al.

1 2

3 4 5

6

ˇ ast hry tj. jej´ı podhra := subGame Data: C´ Result: Maxim´ aln´ı podhra takov´a, ˇze v n´ı hr´aˇci maj´ı sv´e akce postaˇcujic´ı k optim´aln´ı strategii subGame := matice z´ akladn´ı podhry ze vstupu; NE := mnoˇzina strategi´ı pro vˇsechny hr´aˇce na omezen´e hˇre -¿ vypoˇcteno z line´ arn´ıho programu; while true do if bestResponse(N E) ∈ subGame then break ; // pokud uˇ z podhra obsahuje vˇ sechny akce postaˇ cujic´ ı k optim´ aln´ ı strategii update(subGame) ; // pˇ rid´ an´ ı nov´ ych ˇ r´ adk˚ u a sloupc˚ u do hern´ ı matice podle novˇ e spoˇ c´ ıtan´ e optim´ aln´ ı strategie Algorithm 3: Double oracle algoritmus

3.4.1

Pˇ r´ıklad Double Oracle algoritmu

Pro v´ ypoˇcet pˇr´ıkladu si vyp˚ ujˇc´ıme Stav 1 ze tˇret´ı iterace hodnoty z Obr´ azku 3.6. Jako prvn´ı provedeme inicializaci algoritmu, tedy zvol´ıme podmnoˇzinu akc´ı. Abychom se pokusili co nejv´ıce stav oˇrezat, nech´ame obˇema hr´aˇc˚ um pouze jednu a to prvn´ı akci v prvn´ım ˇr´ adku a sloupci. Tato hra m´a trivi´aln´ı v´ ysledek optim´ aln´ıch strategi´ı. Iterace 1 Optim´ aln´ı strategie Hr´ aˇ ce 1 s1 = [1] Optim´ aln´ı strategie Hr´ aˇ ce 2 s2 = [1] Nejlepˇ s´ı reakce Hr´ aˇ ce 2 na Hr´ aˇ ce 1 br1 = [1, 0] Nejlepˇ s´ı reakce Hr´ aˇ ce 1 na Hr´ aˇ ce 2 br2 = [0, 0, 1] Hr´ aˇci 2 zcela vyhovuje v´ ybˇer utility rovn´e nule a jeho nejlepˇs´ı reakce se t´ım nemˇen´ı. Hr´ aˇc 1 vˇsak radˇeji zvol´ı svou tˇret´ı akci s utilitou rovnou jedn´e, aby t´ım zv´ yˇsil hodnotu hry.

14

Iterace 2 Optim´ aln´ı strategie Hr´ aˇ ce 1 s1 = [1] Optim´ aln´ı strategie Hr´ aˇ ce 2 s2 = [0, 1] Nejlepˇ s´ı reakce Hr´ aˇ ce 2 na Hr´ aˇ ce 1 br1 = [0, 1] Nejlepˇ s´ı reakce Hr´ aˇ ce 1 na Hr´ aˇ ce 2 br2 = [0, 0, 1] Iterace 3 Optim´ aln´ı strategie Hr´ aˇ ce 1 s1 = [0.5, 0.5] Optim´ aln´ı strategie Hr´ aˇ ce 2 s2 = [0.5, 0.5] Nejlepˇ s´ı reakce Hr´ aˇ ce 2 na Hr´ aˇ ce 1 br1 = [1, 0] Nejlepˇ s´ı reakce Hr´ aˇ ce 1 na Hr´ aˇ ce 2 br2 = [1, 0, 0] Tento selektivn´ı postup n´ am na tomto jednoduch´em stavu demonstroval to, co bylo zˇrejm´e jiˇz v iteraci hodnoty. Druh´a akce ˇr´adkov´eho hr´aˇce matice nese pˇrebyteˇcnou informaci o Stavu 1, tedy pro naˇse u ´ˇcely nen´ı potˇrebn´a k nalezen´ı optim´ aln´ı strategie.

Iterace 2

Iterace 1 0.0

1.0

0.5

0.0

1.0

0.0

=⇒

0.0

1.0

0.5

0.0

1.0

0.0

Iterace 3

=⇒

0.0

1.0

0.5

0.0

1.0

0.0

Obr´ azek 3.11: Algoritmus Double Oracle na Stavu 1 z Obr´azku 3.8

15

Kapitola 4

Iteraˇ cn´ı algoritmy ve stochastick´ ych hr´ ach v nekoneˇ cnˇ e kroc´ıch Pˇredpokl´ adejme, ˇze m´ ame algoritmy optim´alnˇe naprogramovan´e a k v´ ypoˇct˚ um pouˇz´ıv´ ame v´ ykonn´ y poˇc´ıtaˇc. Jedin´ y parametr, se kter´ ym m˚ uˇzeme h´ ybat, je ukonˇcovac´ı podm´ınka. U t´e vˇsak poˇzadujeme, co nejvyˇsˇs´ı pˇresnost, tedy co nejmenˇs´ı rozd´ıl ve zkonvergovan´ ych hodnot´ach hry nebo startegie dvou po sobˇe jdouc´ıch iterac´ıch. Závislost doby konvergence na velikosti hry pro podmínku 1e05

Doba iterace hodnoty a strategie [minuty]

40 Pro det = 0.2 Pro det = 0.6 Pro det = 1.0

35 30 25 20 15 10 5 0

0

50

100

150

Velikost hry [akce]

Obr´ azek 4.1: Graf z´ avislosti velikosti hry na ˇcase konvergence obou iteraˇc´ıch algoritm˚ u pˇri fixn´ı pˇresnosti 1 · 10−5

16

4.1

Anal´ yza probl´ emu

Jedn´ım ze zp˚ usob˚ u vedouc´ıch ke zrychlen´ı ˇreˇsen´ı stochastick´ ych nekoneˇcn´ ych her je oˇrez´ an´ı poˇctu stav˚ u a akc´ı tak, abychom neztratili d˚ uleˇzitou informaci o hˇre. V podstatˇe chceme vyuˇz´ıt principu Double Oracle algoritmu na vˇsechny hern´ı stavy. Jenˇze v pˇr´ıkladu ze sekce 3.4.1 jsme pˇredpokl´adali znalost ohodnocen´ı akc´ı. Ve skuteˇcnosti tyto zkonvergovan´e hodnoty zn´ame aˇz po dokonˇcen´ı bˇehu iterativn´ıch algoritm˚ u. R´ adi bychom tedy od nˇejak´e mal´e podmnoˇzny akc´ı a stav˚ u rozˇsiˇrovali hru tak, aby pˇridan´e akce (pˇr´ıpadn´e pˇrechody na nov´e stavy) mˇely smysl. Pˇredpokl´ ad´ ame, ˇze mal´a ˇc´ast hry (podhra) zkonverguje k hodnot´am hry velmi rychle. Pokud do mnoˇziny akc´ı podhry pˇrid´ame akci a hodnota hry se nezmˇen´ı, z´ısk´ ame t´ım informaci o tom, ˇze tato akce nemˇen´ı hodnotu optim´aln´ı strategie obou hr´ aˇc˚ u. Naopak je ˇz´adouc´ı pˇridat vˇsechny stavy, kter´e hodnotu hry vylepˇs´ı. Takov´e akce maj´ı pro hru v´ yznam a vylepˇsuj´ı startegie hr´aˇc˚ u.

4.2

Algoritmus rozˇ siˇ rov´ an´ı podhry

Jak jsme jiˇz zm´ınili v u ´vodu kapitoly, je tˇreba nejdˇr´ıve sestavit nˇejakou malou podhru, kter´ a m´ a smysl. To jest takov´a mnoˇzina stav˚ u a akc´ı, ˇze se hr´aˇci dok´aˇz´ı dostat od poˇc´ ateˇcn´ıho stavu ke stavu termin´aln´ımu. Toto je probl´em hled´an´ı cesty v grafu, kter´ y vyˇreˇs´ıme procedurou init(). Pokud takov´a cesta neexistuje, pak hru nem´ a smysl osek´ avat, protoˇze neobsahuje cesty k termin´aln´ım stav˚ um. Tedy pouze cykl´ı mezi pˇrechodn´ ymi stavy. Pro splnˇen´ı podm´ınky staˇc´ı nal´ezt alespoˇ n jednu cestu k termin´ aln´ımu stavu ze vˇsech moˇzn´ ych ve hˇre. D´ ale budeme potˇrebovat frontu akc´ı Q. Pro tu plat´ı, ˇze neobsahuje mnoˇzinu akc´ı A∗ (definujeme ji jako akce, kter´e uˇz byly do podhry pˇrid´any). Pro subGame tedy plat´ı A∗ ∈ / Q. T´ım ˇr´ık´ ame jen, ˇze pˇrid´av´ame stavy, kter´e jeˇstˇe podhra neobsahuje. Ve chv´ıli, kdy je pˇrid´an stav, provedeme kontrolu, zda se zmˇenila hodnota iteraˇcn´ıho algoritmu. Pokud ano, aktualizujeme funkc´ı dosaˇziteln´eStavy() pˇrechod do novˇe dostupn´ ych stav˚ u. Pomoc´ı t´eto funkce ovˇeˇr´ıme, jestli existuje z nˇejak´e novˇe pˇridan´e akce cesta do stav˚ u, kter´e nejsou v podhˇre. V pˇr´ıpadˇe rozˇs´ıˇren´ı o nov´ y stav se pˇrid´ av´a prvn´ı akce pro oba dva hr´aˇce. Jestliˇze vˇsechny pˇridan´e akce nezmˇen´ı hodnotu hry, algoritmus ukonˇcujeme.

17

1 2 3 4 5 6 7 8 9 10 11

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Data: G = Hra, e = Ukonˇcovac´ı podm´ınka pro iteraˇcn´ı algoritmy Result: Podhra vstupu se stejnou hodnotou hry if init(G) existuje? then subGame = init(G); else return ”Podhra nem´ a ˇreˇsen´ı”; Necht’ Q je fronta; Necht’ S jsou stavy, kter´e podhra obsahuje; gameV alue0 = iterativn´ıAlgoritmus(subGame, e); t := 1; sameQ := true; while true do if Q.vyjmi je pr´ azdn´ a? then // jestliˇ ze fronta Q neobsahuje ˇ z´ adn´ e dalˇ s´ ı akce ke zpracov´ an´ ı Q.pˇridej(akce ∈ / subGame); if existuje dostupn´y stav X z mnoˇziny stav˚ u S then Q.pˇridej(akce ∈ X); if sameQ == false then break ; // tzn. pokud se ˇ z´ adn´ a z akc´ ı nepˇ ridala else sameQ = false a := Q.vyjmi; subGame.pˇridej(a); if iterativn´ıAlgoritmus(subGame, e) = gameV aluet then subGame.vyjmi(a); else S.pˇridej(dosaˇziteln´eStavy(subGame)); sameQ = true; t := t+1; gameV aluet := iterativn´ıAlgoritmus(subGame, e); Algorithm 4: Rozˇsiˇrov´an´ı podhry

V Double Oracle jsme vyuˇz´ıvali nejlepˇs´ı reakci hr´aˇc˚ u, abychom urˇcili, kter´e akce do hern´ıch stav˚ u pˇrid´ avat. Tato odpovˇed’ donutila hr´aˇce zmˇenit svoj´ı strategii v pˇr´ıpadˇe, ˇze existovala lepˇs´ı varianta. Jestliˇze jeden z hr´aˇc˚ u zmˇenil svoj´ı strategii, znamen´ a to zmˇenu hodnoty hry v dan´em stavu. Tuto vlastnost vyuˇz´ıv´ame pr´avˇe v algoritmu rozˇsiˇrov´ an´ı podher.

4.2.1

Pˇ r´ıklad na deterministick´ e hˇ re

Pro demonstraci algoritmu vyuˇzijeme n´aˇs zn´am´ y pˇr´ıklad z tˇret´ı kapitoly. Nejprve si inicializujeme nˇejakou cestu z poˇc´ateˇcn´ıho do termin´aln´ıho stavu. Hodnoty v matic´ıch odpov´ıdaj´ı stavu, do kter´eho se z dan´eho pole dostaneme.

18

Necht’ stav 0 a 3 je termin´ aln´ı a pˇrechody matic jsou ohodnoceny poˇradov´ym ˇc´ıslem stavu, pak dost´ av´ ame podhru o velikosti Ω = 2:

Stav 1 Stav 2 2 1 3

3 2

3

0

1

2

3

1

2

2 0

Obr´ azek 4.2: Incializace podhry hry z Obr´azku 3.2 Je zˇrejm´e, ˇze takov´ ychto poˇc´ateˇcn´ıch podher m˚ uˇzeme naj´ıt v´ıce. Napˇr´ıklad druh´ a akce sloupcov´eho hr´ aˇce spolu s tˇret´ı akc´ı ˇr´adkov´eho hr´aˇce daj´ı podhru jen o velikost Ω = 1. Obecnˇe plat´ı, ˇze ˇc´ım menˇs´ı matice stav˚ u vezmeme na zaˇc´atku, t´ım l´epe. Sestav´ıme si tedy frontu v poˇrad´ı, jak jdou akce postupnˇe ve stavech po ˇr´adc´ıch. Oznaˇc´ıme si jej´ı prvky trojˇc´ısl´ım ve form´atu: [Poˇrad´ı stavu hry, Index hr´ aˇce, Poˇrad´ı akce hr´ aˇce]. Q = {[112], [113], [121], [212], [221], [223], [224]} Prvn´ı ˇctyˇri akce hru neovlivn´ı a nenut´ı ˇz´adn´eho z hr´aˇc˚ u zmˇenit strategii. Aˇz p´ at´ y prvek fronty (prvn´ı akce Hr´aˇce 2 ve druh´em stavu) umoˇzn´ı Hr´aˇci 2 hr´at ˇ y a sedm´ ryz´ı strategii s22 = [1, 0], ˇc´ımˇz zmˇen´ı hodnotu hry z 1 na 0. Sest´ y prvek strategie nemˇen´ı. Napln´ıme tedy znovu frontu: Q = {[112], [113], [121], [212], [223], [224]} Hr´ aˇci 1 se pˇrid´ a tˇret´ı akce v prvn´ım stavu, hodnota hry je pak 1. Q = {[112], [121], [212], [223], [224]} Zde se pˇrid´ a druh´ a akce Hr´ aˇce 2 ze stavu dva. Algoritmus vyzkouˇs´ı zbyl´e prvky fronty. Pot´e ji znovu napln´ı a zkontroluje, ˇze jiˇz ˇz´adn´a akce startegie hr´aˇc˚ u nemˇen´ı a program se ukonˇc´ı.

19

Stav 1 Stav 2 2

3

1

2

3

2

3

0

1

2

3

1

2

0

Obr´ azek 4.3: V´ ysledn´a rozˇs´ıˇren´a podhra z Obr´azku 4.2 Vid´ıme, ˇze hra se rozˇs´ıˇrila pˇresnˇe podle myˇslenky Double Oracle algoritmu. Stav 1 odpov´ıd´ a ˇreˇsen´ı pˇr´ıkladu z Obr´ azku 3.11 a o Stavu 2 jiˇz z Pˇr´ıkladu 2 ze sekce 3.1.1 v´ıme, ˇze Hr´ aˇc 2 bude pokaˇzd´e hr´at ryz´ı strategii. Tedy pouze svou prvn´ı akci a t´ım p´ adem se d´ a cel´a matice zkr´atit pouze na prvn´ı pˇrechod. T´ımto jsme ale i zjistili, ˇze by se volbou pr´avˇe v´ yˇse zmiˇ novan´eho pˇrechodu na termin´ aln´ı stav 0 podhra zmenˇsila z Ω = 6 na Ω = 5. K lepˇs´ımu vyb´ır´an´ı poˇc´ ateˇcn´ı podhry by tedy byla vhodn´a heurestika, kter´a by byla schopn´a efektivnˇe odhadnout cestu k termin´aln´ımu stavu, jenˇz m´a nejvyˇsˇs´ı pravdˇepodobnost u ´ˇcasti ve fin´ aln´ı rozˇs´ıˇren´e podhˇre.

20

Kapitola 5

Popis experiment˚ us v´ ysledky Testy probˇehly na m´em vlastn´ım naprogramovan´em prostˇred´ı v programovac´ım jazyce Java s vyuˇzit´ım knihovny CPLEX, se kterou jsem poˇc´ıtal line´arn´ı program pro zjiˇstˇen´ı Nashova equlibria a hodnoty hry. Ke generov´an´ı testovac´ıch dat jsem vyuˇzil sv´eho gener´ atoru n´ahodn´ ych her, na nˇemˇz byly vytvoˇreny sady dat pro r˚ uzn´e stupnˇe stochasticity her.

5.1

Generov´ an´ı n´ ahodn´ ych her

Pro testov´ an´ı na algoritmu rozˇsiˇrov´an´ı podhry bylo potˇreba vytvoˇrit gener´ator her, abychom mohli prov´est mˇeˇren´ı na signifikantn´ı a rozliˇsn´e mnoˇzinˇe her. Hry generujeme, protoˇze neexistuje ˇz´adn´a knihovna her nebo tomu podobn´ y gener´ ator. Definice 7 Necht’ hpi je poˇcet akc´ı pro hr´ aˇce p ve stavu i, pak Ω je velikost hry a definujeme ji n´ asledovnˇe: l X h1i · h2i Ω= i=1

Definice 8 Zavedeme si parametr det, kter´y n´ am bude urˇcovat m´ıru deterministiˇcnosti, resp. stochasticity pˇrechod˚ u mezi stavy hern´ı matice. Parametr det l X nab´yv´ a hodnot z < 0.0, 1.0 >, kde det · h1i + h2i je maxim´ aln´ı poˇcet stav˚ u, do i=1

kter´ych se m˚ uˇzeme z dan´eho pˇrechodu dostat. Na Obr´ azku 4.1 jsme vidˇeli, ˇze ˇcas k vyˇreˇsen´ı programu roste i s t´ım, jak je hra stochastick´ a.

21

Zadefinujme si gen(n, h, l, seed, det) jako funkci, kter´a vrac´ı hru jako pole stav˚ u, pak plat´ı, ˇze: • n je poˇcet poˇzadovan´ ych nagenerovan´ ych n´ahodn´ ych her • h je maxim´ aln´ı velikost hrany matice stavu, tj. maxim´aln´ı poˇcet akc´ı pro hr´ aˇce u jednoho stavu hry • l je maxim´ aln´ı poˇcet stav˚ u hry • seed je unik´ atn´ı kl´ıˇc ke kaˇzd´e nagenerovan´e hˇre • det je parametr stochasticity pˇrechod˚ u mezi stavy hry Gener´ ator tedy pˇrijme na vstupu parametry hry a generuje z nich hry takov´e, ˇze vstup n´ am urˇcuje maxim´aln´ı hodnoty dan´ ych specifikac´ı hry jako je tˇreba nejvˇetˇs´ı moˇzn´ a ˇs´ıˇrka stavu apod. Nejdˇr´ıve se vygeneruj´ı velikosti stav˚ u, pot´e se postupnˇe vytv´aˇr´ı pˇrechody pro r˚ uzn´e kombinace akc´ı a podle parametru det, jak jiˇz bylo pops´ano v jeho definici, se pro kaˇzd´ y takov´ y pˇrechod nastav´ı pravdˇepodobnostn´ı rozloˇzen´ı. Pravdˇepodobnost, ˇze dvˇema akc´ım bude pˇridˇelen pˇrechod na jin´ y stav, je d´ana rovnomˇern´ym rozdˇelen´ım. To n´ am maximalizuje ˇsanci, ˇze bude existovat do kaˇzd´eho stavu alespoˇ n jeden pˇrechod a ˇze do vˇetˇs´ıch matic bude takov´ ych pˇrechod˚ u v´ıce.

5.2

Mˇ eˇ ren´ı na konkr´ etn´ıch pˇ r´ıkladech

Zaj´ım´ a n´ as, jak vypad´ a pr˚ ubˇeh algoritmu, co se t´ yˇce hodnoty hry. Jak se mˇen´ı v ˇcase a z´ aroveˇ n, jak oˇrez´ av´ a hry na nˇejak´em vˇetˇs´ım vzorku dat.

5.2.1

Pˇ r´ıklad na deterministick´ e hˇ re Konvergence podhry Iterace strategie 1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

Hodnota hry

Hodnota hry

Konvergence podhry Iterace hodnoty 1

0.5 0.4

0.5 0.4

0.3

0.3

0.2

0.2

0.1 0

0.1

Reálná hodnota hry Hodnota iterace podhry 0

5

10 Iterace

15

0

20

Reálná hodnota hry Hodnota iterace podhry 0

5

10 Iterace

15

20

Obr´ azek 5.1: Konvergence algoritmu rozˇsiˇrov´an´ı podher na pˇr´ıkladˇe ze sekce 4.2.1 22

Na Obr´ azku 5.1 m˚ uˇzeme vidˇet, jak se mˇen´ı hodnota hry po jednotliv´ ych iterac´ıch. Skoky znamenaj´ı pˇrid´ an´ı stavu, kter´ y tuto hodnotu ovlivˇ nuje. V tomto konkr´etn´ım pˇr´ıpadˇe to bude pr´avˇe podmatice ze Stavu 1, kter´a neprve pˇrilepˇs´ı Hr´ aˇci 2, pot´e se vr´ at´ı ve prospˇech Hr´aˇce 1, aˇz se dopln´ı na ˇctvercovou ”jednotkovou”podmatici s hodnotou hry 0.5. V m´ıstech graf˚ u, kde je hodnota konstantn´ı, prob´ıhalo pˇrid´ av´ an´ı akc´ı, kter´e hodnotu Nashova equlibria nemˇen´ı. I na d´elce jednotliv´ ych rovn´ ych u ´sek˚ u m˚ uˇzeme pozorovat poˇcet nepˇridan´ ych dostupn´ ych akc´ı. Pro oba iteraˇcn´ı algoritmy prob´ıhalo pˇrid´av´an´ı akc´ı stejnˇe. Algoritmis tak dok´ azal hru zjednoduˇsit zhruba o 43% jej´ı p˚ uvodn´ı velikosti.

5.2.2

Pˇ r´ıklad na stochastick´ e hˇ re

Uv´ ad´ıme dalˇs´ı pˇr´ıklad, tektokr´at na stochastick´e nekoneˇcn´e hˇre. Hra byla vytvoˇrena gener´ atorem jako gen(1, 4, l0, 218, 0.25). Pro sloˇzitost hry uv´ad´ıme pouze jej´ı rozmˇery. D´ıky tomu, ˇze je hra stochastick´a, m˚ uˇze obsahovat cykly, kter´e bychom r´ adi zjednoduˇsili (v tomto pˇr´ıpadˇe tomu tak skuteˇcnˇe je). Zjednoduˇ sen´ a hra Stav 1 = 4x1 Stav 2 = 0x0 Stav 3 = 2x2 Stav 4 = 2x2 Stav 5 = 2x2 Stav 6 = 0x0 Stav 7 = 1x1 Stav 8 = 3x3 Stav 9 = 2x2 Stav 10 = 1x1

Vygenerovan´ a hra Stav 1 = 4x3 Stav 2 = 2x2 Stav 3 = 2x3 Stav 4 = 2x2 Stav 5 = 2x3 Stav 6 = 3x3 Stav 7 = 2x2 Stav 8 = 3x4 Stav 9 = 2x2 Stav 10 = 2x2

Konvergence podhry pro Iterace hodnoty Konvergence podhry pro Iterace strategie Reálná hodnota hry Hodnota iterace podhry

0.2

0.15 Hodnota hry

Hodnota hry

0.15

0.1

0.05

0

Reálná hodnota hry Hodnota iterace podhry

0.2

0.1

0.05

0

20 Iterace

0

40

0

20

40 Iterace

60

Obr´ azek 5.2: Konvergence algoritmu rozˇsiˇrov´an´ı podher na vygenerovan´en pˇr´ıkladˇe nekoneˇcn´e stochastick´e hry

23

Vid´ıme, ˇze ve hˇre jsme objevili dokonce stavy, kter´e jsou nedosaˇziteln´e (0x0). Pak jsou zde stavy, jeˇz dosaˇziteln´e jsou, ale vytv´aˇrej´ı pouze pˇrechodnou cestu (1x1). V neposledn´ı ˇradˇe jsou pak zjednoduˇseny stavy, kter´e neovlivˇ nuj´ı rozhodov´ an´ı hr´ aˇc˚ u. T´ımto jsme hru zmenˇsili zhruba o polovinu (rozd´ıl pr˚ ubˇehu zjednoduˇsen´ı pro oba iteraˇcn´ı algoritmy vysvˇetl´ıme pozdˇeji) a jak vid´ıme na rozmˇerech, v´ yraznˇe jsme usnadnili v´ ypoˇcet strategie hr´aˇc˚ u.

5.3

Mˇ eˇ ren´ı na vˇ etˇ s´ı sadˇ e dat

N´ıˇze uveden´e v´ ysledky testov´ an´ı probˇehly na hr´ach do velikosti 5 × 5, do poˇctu stav˚ u 5, za ukonˇcovac´ı podm´ınky ε = 0.001 a hodnoty kl´ıˇce 160. Jelikoˇz k mˇeˇren´ım pouˇz´ıv´ ame n´ ahodn´ y gener´ator, m˚ uˇzeme pˇredpokl´adat, ˇze rozmˇernˇejˇs´ı matice s vˇetˇs´ım poˇctem stav˚ u budou m´ıt podobn´e n´ahodn´e rozloˇzen´ı pˇrechod˚ u a tedy bude hra podobnou mˇerou obsahovat cykly. U nˇekter´ ych z n´ıˇze uveden´ ych graf˚ u nab´ yv´a obˇcas hodnota procentu´aln´ıho zmenˇsen´ı hry velikosti nula. To znamen´a, ˇze tyto hry nebyly v˚ ubec nijak zjednoduˇseny. Jsou bud’ d´ılem n´ ahody nagenerov´any tak mal´e, ˇze nemohou b´ yt zmenˇseny (zpravidla jsou to hry o jednom stavu), anebo hry tak dobˇre vytvoˇren´e, ˇze po permutaci ˇr´ adk˚ u a sloupc˚ u u vˇsech stav˚ u zjist´ıme, ˇze na diagon´ale matic jsou pˇrechody do termin´aln´ıch stav˚ u. N´ıˇze uveden´e grafy nenesou ˇz´ adnou z´avislot os na sobˇe. Osa x ud´av´a rozd´ıln´a na sobˇe nez´ avisl´ a mˇeˇren´ı a grafy jsou zde pro porovn´an´ı. Ud´avaj´ı, jak se mˇen´ı zmenˇsen´ı her v procentech v z´ avislosti na paramentru det pˇri statistick´em vzorku 100 her. Ty byly na ose x seˇrazeny podle absolutn´ıho rozd´ıl˚ u zmenˇsen´ı velikosti stavov´ ych matic obou iteraˇcn´ıch algoritm˚ u. Na z´akladˇe toho m˚ uˇzeme demonstrovat, jak moc se v´ ysledky oˇrez´an´ı liˇs´ı i mezi hodnotov´ ym a strategick´ ym algoritmem.

Rozdíl hry pro det = 0.0

Strední hodnota 100

100 Pro iteraci hodnoty Pro iteraci strategie

Rozdíl v procentech

90

90

80

80

70

70

60

60

50

50

40

40

30

30

20

20

10

10

0

0

20

40

60

80

100

0

0 1 2 3

Hra

Obr´ azek 5.3: Graf porovn´ avaj´ıc´ı procentu´aln´ı zmenˇsen´ı hern´ıch matic na vzorku n´ ahodn´ ych her pˇri det = 0.0

24

Na grafu pro ˇcistˇe deterministickou hru vid´ıme, ˇze p˚ umˇern´eho zlepˇsen´ı (tedy zmenˇsen´ı velikosti p˚ uvodn´ı hry) m˚ uˇzeme dos´ahnout u obou iteraˇcn´ıch algoritm˚ u zhruba stejnˇe. Zhruba o 66.1 ± 2.2% a pro oba algoritmy stejnˇe (liˇs´ı se jen o desetinu procenta a odchylka o setinu). Rozdíl hry pro det = 0.5

Strední hodnota 100

90 Pro iteraci hodnoty Pro iteraci strategie

80

90 80

Rozdíl v procentech

70

70

60

60 50 50 40 40 30

30

20

20

10 0

10 0

20

40

60

80

100

0

0 1 2 3

Hra

Obr´ azek 5.4: Graf porovn´ avaj´ıc´ı procentu´aln´ı zmenˇsen´ı hern´ıch matic na vzorku n´ ahodn´ ych her pˇri det = 0.5 U her pˇri det = 0.5 bylo na stejn´em vzorku pr˚ umˇern´e zlepˇsen´ı u iterace hodnoty o 23.8 ± 1.6% a u strategie 34.1 ± 2.0%. Pˇri det = 1.0 bylo pr˚ umˇern´e zlepˇsen´ı u iterace hodnoty o 23.4 ± 1.8% a u strategie 34.4 ± 1.8%.

Rozdíl hry pro det = 1.0

Strední hodnota 100

100 Pro iteraci hodnoty Pro iteraci strategie

Rozdíl v procentech

90

90

80

80

70

70

60

60

50

50

40

40

30

30

20

20

10

10

0

0

20

40

60

80

100

0

0 1 2 3

Hra

Obr´ azek 5.5: Graf porovn´ avaj´ıc´ı procentu´aln´ı zmenˇsen´ı hern´ıch matic na vzorku n´ ahodn´ ych her pˇri det = 1.0

25

Prumerna hodnota rozdílu pro algoritmus hodnoty a strategie 65 Stredni hodnota iterace hodnoty Stredni hodnota iterace strategie

60

Rozdíl v procentech

55 50 45 40 35 30 25 20

0

0.2 0.4 0.6 0.8 Míra stochasticity akcí podle parametru det

1

Obr´ azek 5.6: Graf z´ avislosti pr˚ umˇern´eho zmenˇsen´ı hry na parametru det M˚ uˇzeme si vˇsimnout, ˇze u iterace strategie kles´a procentn´ı zmenˇsen´ı her v z´ avislosti na parametru det pomaleji, neˇz je to u iterace hodnoty. Po d˚ ukladn´em prozkoum´ an´ı vkl´ ad´ an´ı akc´ı a bˇehu algoritmu jsem zjitil, ˇze je to d´ano ztr´atou informace d´ıky nedostateˇcn´e pˇresnosti datov´eho typu double. Stane se pak to, ˇze algoritmus rozˇs´ıˇr´ı stav o dalˇs´ı akce, i kdyˇz jde o chybu v nepˇresnosti typu double. Toto se dˇeje pˇredevˇs´ım ve hr´ ach se stavem(vy), obsahuj´ıc´ım takovou kombinaci pˇrechod˚ u na termin´ aln´ı stav nˇejak´eho hr´aˇce, ˇze se hodnota hry tohoto stavu bl´ıˇz´ı bud’to 0 nebo 1. Jelikoˇz je tento stav zacyklen´ y s´am do sebe, algoritmu pak staˇc´ı pˇridat odkaz na jin´ y stav s malou hodnotou utility a vznik´a t´ım chyba zaokrouhlen´ı. Toto m˚ uˇze i stavy, ve v´ yjimeˇcn´ ych pˇr´ıpadech - kdy hra splˇ nuje v´ yˇse uveden´e pˇredpoklady, rozˇs´ıˇrit na jejich plnou velikost. Zvaˇzoval jsem pouˇzit´ı pˇresnˇejˇs´ıch typ˚ u jako napˇr. bigdecimal, ale jelikoˇz jde o objekty a bylo by potˇreba v dan´em typu uchov´avat hodnotu hry a strategie, tedy nejpouˇz´ıvanˇejˇs´ı promˇenn´e v algoritmech, nakonec jsem toto ˇreˇsen´ı zam´ıtl.

26

Kapitola 6

Z´ avˇ er Pˇredmˇetem t´eto pr´ ace bylo prozkoumat, zda jde hru zjednoduˇsit, abychom usp´ıˇsili konvergenci iteraˇcn´ıch algoritm˚ u. Zjistil jsem, ˇze postupn´e rozˇsiˇrov´an´ı podhry skuteˇcnˇe dok´ aˇze akce her podstatnˇe oˇrezat. Jenˇze s rostouc´ım poˇctem akc´ı se m˚ uˇze st´at, ˇze hodnota hry uˇz d´avno konvergovala k optimu, ale algoritmus jeˇstˇe st´ale zkouˇs´ı pˇrid´avat akce. Stejnˇe tak se m˚ uˇze st´ at, ˇze pˇri opakovan´em pˇrid´ av´an´ı akc´ı do fronty, ze kter´e postupnˇe vylepˇsujeme podhru, se n´ am st´ ale vrac´ı akce, jeˇz hodnotu hry nikdy nezmˇen´ı. V pr´ aci jsem se t´ımto probl´emem nezab´ yval, ale zp˚ usob stavˇen´ı fronty m˚ uˇze b´ yt dalˇs´ı faktor k urychlen´ı algoritmu k rozˇsiˇrov´an´ı podhry. Napˇr´ıklad opakovanˇe pˇrid´ avan´e akce, kter´e po nˇekolik iterac´ı st´ale nemˇen´ı hodnotu hry, je moˇzn´e oklasifikovat niˇzˇs´ı prioritou neˇz akce neprozkouman´e. Tedy naj´ıt vhodnou heuristiku, jak vyb´ırat, kter´ ymi akcemi hru rozˇsiˇrovat. Ku ´spoˇre ˇcasu n´ am re´ alnˇe ale algoritmus nepomohl. Je tu ovˇsem potenci´al pro zrychlen´ı algoritmu rozˇsiˇrov´ an´ı podhry a to nejen v optimalizaci v´ yˇse uveden´eho pseudoalgoritmu, ale pˇredevˇs´ım v lepˇs´ı volbˇe rychlejˇs´ıho programovac´ıho jazyka. To by pomohlo i s dalˇs´ım probl´emem, kter´ y se vyskytoval v jazyce Java. Nedostateˇcn´ a pˇresnost datov´ ych typ˚ u a objektov´ y model jazyka byl, co se t´ yˇce rychlosti bˇehu algoritmu, sp´ıˇse na ˇskodu. Stochastick´e nekoneˇcn´e hry maj´ı v souˇcasn´e dobˇe ˇsirok´e vyuˇzit´ı a je proto ˇz´ adouc´ı pˇri hled´ an´ı optim´ aln´ıch strategi´ı tento proces usp´ıˇsit. Vhodn´e osek´av´an´ı akc´ı hr´ aˇc˚ u se zd´ a b´ yt jako jedno z moˇzn´ ych vylepˇsen´ı.

27

Literatura [1]

Kristoffer Arnsfelt Hansen, Rasmus IbsenJensen, and Peter Bro Miltersen: The complexity of solving reachability games using value and strategy iteration. Computer Science-Theory and Applications, Springer Berlin Heidelberg, 2011. 7790.

[2]

ˇ Branislav Boˇsansk´ y, Viliam Lis´ y, Jiˇr´ı Cerm´ ak, Roman V´ıtek, a Michal Pˇechouˇcek: Using Doubleoracle Method and Serialized AlphaBeta Search for Pruning in Simultaneous Moves Games. In Proceedings of the 23rd International Joint Conference on Artificial Inteligence (IJCAI), 2013.

[3]

Yoav Shoham, and Kevin LeytonBrown: Multiagent systems: Algorithmic, gametheoretic, and logical foundations. Cambridge University Press, 2009. http://www.masfoundations.org/mas.pdf

[4]

Anton´ın Kuˇcera: Stochastick´e hry dvou hr´ aˇc˚ u. Druh´e setk´ an´ı Praˇzsk´eho informatick´eho semin´aˇre, 2014. http://www.praguecomputerscience.cz/index.php?l=cz&p=2

[5]

Everett, H: Recursive games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games Vol. III. Annals of Mathematical Studies, vol. 39, Princeton University Press, Princeton, 1957.

[6]

Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences, U.S.A. 39, 1953.

[7]

Howard, R.: Dynamic Programming and Markov Processes. MIT Press, Cambridge, 1960.

[8]

Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13. 1993.

[9]

Nash, J.: Equilibrium points in n-person games, Proceedings of the National Academy of Sciences USA, 36, 1950. Reprinted in H. Kuhn (Ed.), Classics in Game Theory, Princeton, NJ: Princeton University Press, 1997 .

[10]

H. B. McMahan, G. J. Gordon, and A. Blum: Planning in the Presence of Cost Functions Controlled by an Adversary. In ICML, pages 536–543, 2003.

[11]

S. Ganzfried and T. Sandholm: Computing an approximate jam/fold equilibrium for 3-agent no-limit Texas hold’em tournaments, AAMAS, 2008.