MATEMATICKÁ TEORIE ROZHODOVÁNÍ

VYSOKÁ ŠKOLA FINANČNÍ A SPRÁVNÍ, o.p.s.

MATEMATICKÁ TEORIE ROZHODOVÁNÍ Podklady k soustředění č. 1 Řešení úloh

1. dílčí téma: Řešení úloh ve stavovém prostoru Počáteční období výzkumu v oblasti umělé inteligence (50. a 60. léta) bylo charakterizováno představou, že několik jednoduchých ale mocných technik umožní vytvářet inteligentní „všeřešící“ programy. Používané techniky byly založeny na vnitřním (strojovém) modelu světa a na schopnosti vytvářet v tomto modelu plán pro řešení dané úlohy. Model světa byl obvykle založen na stavovém prostoru.

1.1 Základní definice Def. 1.1: Stavový prostor Sp = (S, Φ) je dvojce tvořená 1. množinou stavů S = {s} 2. množinou operátorů (přechodů mezi stavy) Φ = {φ} sk = φki(si) (sk se nazývá následník, si se nazývá předchůdce) Příkladem stavového prostoru jsou možná rozložení disků u hlavolamu „Hanojské věže“. Tento hlavolam je tvořen třemi tyčkami, na kterých je navlečeno několik různě velikých disků. Jeden stav tohoto prostoru je vidět na Obr. 1. Velikost stavového prostoru tohoto hlavolamu samozřejmě záleží na počtu disků, pro n disků je to 3n (každý z n disků může být na jedné ze tří tyček), pro tři disky je stavový prostor znázorněn na Obr. 2. Použitý formalismus kóduje pozicí velikost disku (první zleva je největší disk) a číslem tyčky (1 je levá krajní tyčka).

Obr. 1 Hanojské věže (stav (112))

1


Obr. 2 Stavový prostor hanojských věží

Operátory se odvodí na základě pravidla, že se postupně přesouvají disky mezi tyčkami, přičemž: 1. může se přesouvat vždy jeden disk, 2. větší disk se nemůže položit na menší. Celkem je k dispozici 6 operátorů: φ12, φ13, φ21, φ23, φ31, φ32, kde φki znamená přesuň volný disk z k na i. Jiným příkladem je rozložení osmi číslic v mřížce 3x3 u hlavolamu „lišák“ (Obr. 3). Tento stavový prostor obsahuje 9! = 362880 stavů.

2 8 3 1 6 4 7 _ 5 Obr. 3 Lišák

V tomto stavovém prostoru jsou definovány 4 operátory: •

φ1: když _ není v horním řádku, přesuň _ nahoru

•

φ2 když _ není v dolním řádku, přesuň _ dolů

•

φ3: když _ není v levém sloupci, přesuň _ vlevo

•

φ4: když _ není v pravém sloupci, přesuň _ vpravo

Def. 1.2: Úloha ve stavovém prostoru (Sp, s0, G) je definována jako stavový prostor, tj. 1. množina stavů S = {s} 2. množina přechodů mezi stavy Φ = {φ} plus

2


3. počáteční stav s0 4. množina koncových stavů G = {g} V případě Hanojské věže je počáteční stav na Obr. 4 a (jediný) koncový stav na

Obr. 5.

Obr. 5 Hanojské věže - koncový stav

Obr. 4 Hanojské věže - počáteční stav

V případě lišáka je počátečním stavem libovolné uspořádání číslic a jediným koncovým stavem stav z Obr. 6.

1 2 3 8 _ 4 7 6 5 Obr. 6 Lišák - koncový stav

V případě, že pomocí stavového prostoru chceme reprezentovat šachy, bude počátečním stavem výchozí rozložení figurek na šachovnici a množinou koncových stavů např. všechny pozice, ve kterých bílý dává mat. Velikost stavového prostoru je asi 35100 (průměrně 35 možností v každém tahu, průměrná délka partie 50 tahů). Def. 1.3: Řešení úlohy ve stavovém prostoru je nalezení posloupnosti operátorů φ1 φ2… φd takových, že s1 = φ1(s0) s2 = φ2(s1) s3 = φ3(s3) ... g = φd(sd-1) neboli nalezení cesty z počátečního stavu s0 do některého z koncových stavů g (d je délka cesty).

Def. 1.4: Řídící strategie je algoritmus, který v každém kroku volí vhodný operátor:

3

•

musí vést k prohledávání (musí zabraňovat cyklům)

•

musí být systematické


Def. 1.5: Strom řešení úlohy je grafová reprezentace procesu hledání řešení kde uzly odpovídají stavům a hrany odpovídají přechodům mezi stavy daným aplikací operátorů. Ve chvíli, kdy pro nějaký stav je použitelných více operátorů se stává klíčovou otázka, který operátor zvolit. Pro volbu prvního operátoru v případě hanojských věží ukazuje příslušný podstrom Obr. 7, pro volbu prvního operátoru v případě hlavolamu lišák ukazuje příslušný podstrom Obr. 8. Volba operátoru pro daný stav může být založena na myšlence postupně zkusit aplikovat všechny použitelné operátory, může být založena na nějakém kritériu, které hodnotí vhodnost jednotlivých operátorů, nebo může být volba operátoru náhodná.

Obr. 7 První krok Hanojské věže

Obr. 8 První krok lišák

1.2 Prohledávání stavového prostoru Metody prohledávání lze dělit do tří základních skupin:

4


•

slepé - úplné prohledávání nevyužívající žádné dodatečné informace – zde postupně aplikujeme všechny použitelné operátory,

•

heuristické - úplné nebo částečné prohledávání využívající hodnocení zvolené cesty – zde operátory vybíráme na základě nějakého kritéria,

•

náhodné – zde volíme operátory náhodně.

Systematické (nenáhodné) strategie (resp.algoritmy) jsou založeny na expanzi (rozvinutí) daného stavu (uzlu). Rozvinutím uzlu se myslí aplikace všech použitelných operátorů; získáme tak všechny následníky daného uzlu. Algoritmy obvykle využívají dva seznamy: seznam rozvinutých uzlů ROZVIN a seznam nerozvinutých uzlů NEROZVIN.

Slepé prohledávání do šířky Při prohledávání do šířky jsou následníci vybíráni pro expanzi ze seznamu typu fronta (Obr. 9). Postupně procházíme strom řešení po vrstvách a prohledáme všechny uzly, které mají menší hloubku než je hloubka koncového stavu. Každý uzel přitom navštívíme nejvýše jednou. Schematicky je tento způsob znázorněn na Obr. 10, postup algoritmu pak na Obr. 11. Při tomto způsobu prohledávání máme jistotu, že vždy nalezneme optimální řešení (koncový stav s nejmenší hloubkou).

Obr. 9 Algoritmus prohledávání do šířky

5


Obr. 10 Schéma prohledávání do šířky

krok 1 2 3 4 Konec

NEROZVIN A B, C C, D, E D, E, F, G, H

ROZVIN Ø A A, B A, B, C

Obr. 11 Postup algoritmu „do šířky“

Obr. 12 Lišák - prohledávání do šířky (převzato z Chyba! Nenalezen zdroj odkazů.)

6


Slepé prohledávání do hloubky Při prohledávání do hloubky jsou následníci vybíráni pro expanzi ze seznamu typu zásobník (Obr. 13). Na rozdíl od prohledávání do šířky můžeme některými uzly procházet vícekrát, neboť se často musíme navracet (tzv. backtracking). Schematicky je tento způsob znázorněn na Obr. 14 , postup algoritmu na Obr. 15. Při tomto způsobu prohledávání nemusíme nalézt optimální řešení (koncový stav s nejmenší hloubkou) a dokonce žádné řešení (pokud má stavový prostor nekonečnou větev, do které „zabloudíme“). Pro úlohy s konečným stavovým prostorem a s jedním koncovým stavem ale nalezneme stejné řešení jako při prohledávání do šířky.

Obr. 13 Algoritmus prohledávání do hloubky

Obr. 14 Schéma prohledávání do hloubky

7


krok 1 2 3 4 5 6 7 8 Konec

NEROZVIN A B, C D, E, C I, J, E, C J, E, C E, C C F, G, H

ROZVIN Ø A A, B A, B, D A, B, D, I A, B, D, I, J A, B, D, I, J, E A, B, D, I, J, E, C

Obr. 15 Postup algoritmu "do hloubky"

Všimněme si, že pokud bychom při slepém prohledávání do hloubky místo „první zleva“, tak jak je znázorněno na Obr. 14 zvolili strategii „první zprava“, Nalezli bychom koncový stav podstatně rychleji (Obr. 16).

krok 1 2 3 Konec

NEROZVIN A C, B H, G, F, B

ROZVIN Ø A A, C

Obr. 16 Postup algoritmu "do hloubky" – zprava

Heuristické prohledávání Heuristické prohledávání je založeno na kritériu (heuristice), které umožňuje posoudit vhodnost použití jednotlivých operátorů aplikovatelných na daný stav. Vhodnost operátoru můžeme intuitivně chápat jako to, do jaké míry nás použití operátoru přiblíží ke koncovému stavu (řešení úlohy). Def. 1.6: Heuristická funkce je funkce, která každému stavu s přiřadí číslo, vyjadřující jeho kvalitu z hlediska řešení úlohy. Vhodnost operátoru (a tedy kvalita příslušného následníka) může být v dané úloze definována různě. Různé podoby kritéria samozřejmě ovlivní volbu operátorů a tím i dobu (počet kroků) potřebných k nalezení řešení. Vraťme se k hlavolamu lišák (Obr. 8), kde můžeme jako možné heuristiky uvažovat např.: H1: počet chybně umístěných číslic, H2: Manhattan vzdálenost od koncového stavu. Význam první heuristiky je zřejmý. Druhá heuristika vyjadřuje, kolik tahů (ve směru vodorovném resp. svislém) je každá chybně umístěná číslice vzdálena od své správné pozice. Podíváme-li se na volbu operátoru pro první tah dle Obr. 8, pak kvalitu stavů 1 až 4 pro obě heuristiky vidíme v Tab. 1. Obě heuristiky vyhodnotí jako nejlepší tah 1 → 3. Pro druhý tah už budou „doporučení“ obou heuristik odlišná (Tab. 2). Zatímco heuristika H1 vyhodnotí jako stejně kvalitní tahy 3 → 6 i 3 → 7 (a měli bychom tedy uvažovat obě možnosti), heuristika H2 vyhodnotí jako nejlepší tah 3 → 7, což je tah, skutečně vedoucí nejrychleji k řešení úlohy.

8


H1 H2

stav 1 4 5

stav 2 5 6

stav 3 3 4

stav 4 5 6

Tab. 1 Lišák - heuristiky pro první tah

stav 3 stav 6 stav 7 stav 8 3 H1 3 3 4 4 H2 5 3 5 Tab. 2 Lišák - heuristiky pro druhý tah

Gradientní prohledávání (hill climbing) Heuristické prohledávání do hloubky, kde heuristikou je odhad vzdálenosti ke koncovému stavu. Následníky rozvinutého uzlu nejprve uspořádáme dle heuristiky a pak zařadíme do zásobníku.

Obr. 17 Gradientní prohledávání

Lokální varianta tohoto algoritmu je založena na tom, že pro daný stav volíme dle heuristiky nejlepšího následníka a pracujeme pouze s ním. Seznam NEROZVIN je tedy jednoprvkový. Tato varianta tedy hledá „pouze“ lepší uzel, než je ten současný. To může způsobit řadu problémů:

9


•

uváznutí v lokálním extrému (žádný následník není lepší než rozvíjený uzel, který ale nepředstavuje řešení problému),

•

problém plošiny (rozvíjený uzel i jeho následníci jsou stejně kvalitní – není tedy jasné kterým směrem postupovat).

Problém uváznutí v lokálním extrému ilustruje na příkladě hlavolamu lišák Obr. 19. Žádný z následníků uvedeného stavu není ve smyslu heuristiky H1 lepší. Prohledávání by tedy skončilo.

Obr. 18 Lokální varianta gradientního prohledávání

a 2 b 8 _ 4 c 6 d Obr. 19 Lokální extrém hlavolamu lišák

10


2. dílčí téma: Teorie her Základy matematické teorie her položili v první pol. 20. století John von Neumann a Oskar Morgernstern. Teorie her je disciplína aplikované matematiky, která analyzuje široké spektrum konfliktních rozhodovacích situací, které mohou nastat kdekoliv, kde dochází ke střetu zájmů. Herněteoretické modely se pak snaží tyto konfliktní situace nejen analyzovat, ale sestavením matematického modelu daného konfliktu a pomocí výpočtů se snaží nalézt co nejlepší strategie pro konkrétní účastníky takových konfliktů. Teorie her se uplatňuje v mnoha oblastech lidské činnosti od ekonomie, přes politologii až například po sociologii a biologii.

2.1 Základní pojmy Základem většiny matematických modelů z oblasti teorie her je předpoklad racionality. Očekáváme, že každý hráč se chová tak, aby maximalizoval svůj zisk (výhru). To znamená, že: o

hráč si na základě stabilních preferencí stanovuje cíle a volí si strategie k co možná nejefektivnějšímu dosažení těchto cílů.

o

hráč je konfrontován s určitým počtem situací a dokáže si je seřadit podle svých preferencí od nejvýhodnější po nejméně výhodnou.

Toto seřazení musí být úplné, tj. musí pokrývat všechny situace, a tranzitivní, tj. pokud dá hráč přednost situaci A před situací B a situaci B před situací C, musí dát přednost situaci A před situací C. Na základě preferencí situací je odvozena užitková funkce (utility function) hráče. Jediným cílem hráče je potom maximalizace hodnoty užitkové funkce. Předpoklad racionality (každého hráče) je to, co odlišuje teorii her (a příslušné strategie) od teorie rozhodování. Jsou ale i pojetí, která chápou teorii rozhodování (popsanou v předcházející kapitole) jako speciální typ her, kdy jeden z hráčů je “příroda”, pro kterou předpoklad racionality neplatí. Budeme-li hledat analogii s teorií rozhodování, pak hráči jsou účastnící rozhodovacího problému, strategie jsou rozhodnutí a hodnoty užitkové funkce (výhry, výplaty) jsou důsledky rozhodnutí.

Typy her Hry (a jejich modely) můžeme posuzovat z celé řady hledisek. Jsou to •

počet hráčů – obvykle předpokládáme konečný počet hráčů; nejmenší možný počet je 2 a to budou hry na které se dále zaměříme (příkladem mohou být šachy, dáma, piškvorky, ale i bilaterální politická vyjednávání),

•

počet strategií – může být konečný i nekonečný; nás budou zajímat hry s konečným počtem strategií (šachy, dáma, piškvorky). U nekonečných strategií hraje roli i načasování jednotlivých „tahů“,

•

typ výhry – rozlišují se tzv. hry s konstantním součtem a hry s nekonstantním součtem; pro hry s konstantním součtem platí, že pro každou volbu strategií je součet výplatních funkcí (výher) všech hráčů konstantní speciálním případem her s konstantním součtem jsou hry s nulovým součtem, při kterých to, co jeden hráč vyhraje musí druhý hráč (v případě her o dvou hráčích) prohrát – příkladem jsou šachy, piškvorky apod. U her s nenulovým součtem zisk jednoho hráče nemusí pro jiného hráče nutně znamenat ztrátu (vězňovo dilema i různá vyjednávání).

•

11

počet tahů – hry strategické předpokládají, že hráči provedou jeden tah (rozhodnutí) současně (např. kámen-nůžky-papír nebo vězňovo dilema), hry tahové jsou založeny na sekvenci tahů, při kterých se hráči střídají (šachy, piškvorky)


•

dostupná informace – hry s úplnou informací (např. šachy) a hry s neúplnou informací (např. poker); v hrách s úplnými informacemi má každý hráč k dispozici stejné informace týkající se hry jako všichni ostatní.

•

spolupráce – u kooperativních hrách mohou hráči vytvářet koalice případně se mezi sebou domlouvat, u nekooperativních hrách to možné není

Ne všechny kombinace jednotlivých hledisek mohou nastat: každá hra dvou hráčů s konstantním součtem je nekooperativní – pro takovou hru se někdy používá termín antagonistická hra.

Hra v normálním tvaru Def. 3.7 Hra v normálním tvaru je definována množinou

{Q, X 1 ,..., X n , u1 ( x1 ,...x n ),..., u n ( x1 ,..., x n )} kde Q = {1,…,n} jsou hráči, množiny X1,…,Xn jsou množiny strategií a ui(x1,…,xn) jsou výhry hráče i pro jednotlivé strategie. Hra v normálním tvaru je obvykle znázorněna pomocí matice. Hru pro dva hráče vidíme na Obr. 20. Zde hráč číslo 1 vybírá ze strategií s1,…,sk a hráč číslo 2 vybírá ze strategií t1,…,tl. Předpokládejme, že se jedná o hru s nulovým součtem, v takové hře u1(si, tj) = -u2(si, tj) a proto stačí zapisovat jen hodnotu užitkové funkce (výhry) pro jednoho hráče.

hráč 2

hráč 1

t1 t 2 s1 ⎛ u11 u12 ⎜ s 2 ⎜ u 21 u 22 ⎜ ⎜ s k ⎜⎝ u k1 u k 2

tl … u1t ⎞ ⎟ … u 2t ⎟ ⎟ … ⎟ … u kl ⎟⎠

Obr. 20 Hra pro dva hráče v normálním tvaru.

Příklad hry kámen-nůžky-papír je na Obr. 21

hráč 2 K

hráč 1

N

P

K ⎛ 0 1 − 1⎞ ⎟ ⎜ N ⎜ −1 0 1 ⎟ P ⎜⎝ 1 − 1 0 ⎟⎠

Obr. 21 Hra kámen-nůžky-papír v normálním tvaru

Hra v explicitním tvaru Explicitní tvar hry bývá používána k formalizaci her, ve kterých hraje roli pořadí tahů. Hry jsou reprezentovány jako stromy (viz obrázek vlevo). Každý uzel zde reprezentuje místo, ve kterém některý z hráčů vybírá tah, každá hrana odpovídá možnému tahu.

12


Příklad 3.1: Tic-Tac-Toe (neboli americké piškvorky) se hrají na čtvercové síti 3x3 políčka. První z hráčů maluje křížky, druhý maluje kolečka. Hráči se střídají a vyhraje ten, komu se podaří umístit tři své symboly do řádku, do sloupce nebo na diagonálu. Hrubý odhad počtu pozic vychází z toho, že v každém z 9 polí může být o, x, nebo mezera, tedy 39 = 19683. Podobně hrubý odhad počtu různých partií vychází z toho, že první tah může být do některého z 9 polí, druhý tah do některého z 8 polí atd, tedy 9! = 362880 (Obr. 22). Hrací pole je ale symetrické a ne všechny možné kombinace symbolů je přípustná (např. devět ¨x¨). Je tedy 26830 různých partií (web).

Obr. 22 Tic-tac-toe bez uvažování symetrie

2.2 Optimální strategie Antagonistické hry Cílem každého racionálního hráče je vyhrát, jinými slovy maximalizovat svoji výhru. Zabývejme se pouze strategiemi antagonistických her dvou hráčů, které jsou zapsány v normálním tvaru (viz Obr. 20). Uvedený zápis vyjadřuje hodnoty výher (výplat) hráče č. 1. Tento hráč volí mezi svými strategiemi (řádky i matice u(si,tj)) tak, aby jeho výhra byla maximální. Přitom ví, že jeho protihráč, hráč č. 2 bude své strategie volit tak, aby výhru hráče č. 1 minimalizoval. Hráč č. 1 tedy volí takovou strategii s*, pro který minimální hodnota jeho výhry (v rámci tohoto řádku) bude ze všech řádků maximální: s* = maxi minj u(si,tj) Hráč. č. 2 postupuje analogicky. Mezi svými strategiemi (sloupci j matice u(si,tj)) volí tu strategii t*, pro kterou maximální hodnota jeho prohry (v rámci tohoto sloupce) bude ze všech sloupců minimální. t* = minj maxi u(si,tj)

13


Def. 3.2: Nechť u(s*,t*) = maxi minj u(si,tj) = minj maxi u(si,tj) Potom u(s*,t*) se nazývá sedlový bod matice a představuje tzv. cenu hry. Dvojce strategií (s*,t*) se nazývá rovnovážný bod. Teorie her se snaží nalézt v každé hře rovnovážný bod, v němž hráči volí takové strategie, že žádný z nich nemá důvod svou strategii změnit za předpokladu, že nikdo z ostatních svou strategii nezmění. Pokud rovnovážný bod existuje, optimální strategie obou hráčů se nazývají ryzí strategie. Příklad: Pro hru v normálním tvaru uvedenou na Obr. 23 má rovnovážný bod podobu (s2, t1). Pro prvního hráče je totiž min u(s1,tj) = 2 a min u(s2, tj) = 3 a tedy max min u(s,t) = u(s2, t1) což odpovídá strategii s2. Pro druhého hráče je pak max u(si, t1) = 3 a max u(si, t2) = 4 a tedy min max u(s,t) = u(s2, t1) což odpovídá strategii t1.

hráč 2 t1 t2 hráč 1

s1 ⎛ 2 3 ⎞ ⎜ ⎟ s 2 ⎜⎝ 3 4 ⎟⎠

Obr. 23 Příklad hry v normálním tvaru

Ne vždy ale rovnovážný bod a tedy ryzí strategie existuje. Uvažujme hru znázorněnou maticí z Obr. 24. Hráč č. 1 zvolí strategii s2, neboť pro ní je minj uij největší (je to prvek u21=7). Hráč č. 2 zvolí strategii t1, neboť pro ní je maxi uij nejmenší (je to prvek u21=9). Obě hodnoty se ale od sebe liší. Tato hra nemá rovnovážný bod a proto pro ní neexistuje ryzí strategie.

hráč 2 t1 t2 hráč 1

s1 ⎛11 5 ⎞ ⎜ ⎟ s 2 ⎜⎝ 7 9 ⎟⎠

Obr. 24 Hra bez sedlového bodu

Def. 3.3: Nechť máme maticovou hru popsanou maticí z Obr. 20. Nechť

p1 + p 2 +

+ p k = 1 a zároveň pi > 0

q1 + q 2 +

+ ql = 1 a zároveň qi > 0

Pak hru s výplatní funkcí k

l

π (p, q) = ∑∑ pi u ij q j i =1 j =1

nazveme smíšeným rozšířením původní hry. Stručně řečeno, smíšené rozšíření (a smíšené strategie) znamená, že každý z hráčů vybírá ze svých strategií s určitou pravděpodobností. Smíšenou strategii jednotlivých hráčů můžeme hledat jako extrém výplatní funkce, tedy jako hodnoty p a q pro které π(p, q) bude maximální (minimální). Ve výše uvedené hře tedy

14


π(p, q) = 11p1q1 + 5 p1(1- q1) + 7 q1(1- p1) + 9(1- p1) (1- q1) = 8 p1q1 – 4 p1 – 2 q1 + 9 z toho

∂π ( p, q ) = 8q1 − 4 = 0 a tedy q1 = 1/2 p1

∂π ( p, q) = 8 p1 − 2 = 0 a tedy p1 = 1/4 q1 Hráč č. 1 tedy volí strategii (1/4, 3/4) a hráč č. 2 volí strategii (1/2, 1/2). Pro tyto strategie je cena hry π(p, q) maximální a rovná se 8. Podobně nemá ryzí strategii ani hra kámen-nůžky-papír. Smíšená strategie pro oba hráče je (1/3, 1/3, 1/3).

Neantagonistické hry V případě neantagonistických her nejde výhra jednoho hráče na úkor hráčů ostatních. Hráči se o svých strategiích mohou (kooperativní hry) či nemohou (nekooperativní hry) domlouvat. Ukážeme se příklady hodnocení strategií her obou typů. Budeme opět uvažovat jen hry dvou hráčů, kterou můžeme tentokrát znázornit pomocí dvojmatice výplat (Obr. 25). Hodnota uij odpovídá výplatě prvního hráče v případě strategií si (první hráč) a tj (druhý hráč), hodnota vij odpovídá výplatě druhého hráče v případě strategií si (první hráč) a tj (druhý hráč). hráč 2

hráč 1

t1 t2 s1 ⎛ (u11 , v11 ) (u12 , v12 ) ⎜ s 2 ⎜ (u 21 , v21 ) (u 22 , v22 ) ⎜ ⎜ s k ⎜⎝ (u k1 , vk1 ) (u k 2 , vk 2 )

… … … …

tl (u1t , v1t ) ⎞ ⎟ (u 2t , v2t ) ⎟ ⎟ ⎟ (u kl , vkl ) ⎟⎠

Obr. 25 Dvojmaticová hra Def. 3.4: Dvojice strategií (s*, t*) se nazývá rovnovážný bod, právě když u(s,t*) < u(s*,t*) pro všechna s v(s*,t) < v(s*,t*) pro všechna t Věta 3.3: Nechť rovnovážnému bodu odpovídá prvek (uij,vij). Potom uij = maxk ukj vij = maxk vik Příklad: vězňovo dilema Vězňovo dilema patří k nejznámějším příkladům nekooperativních her. Dva vězni jsou obviněni ze stejného trestného činu. Pokud se oba přiznají (P), budou oba odsouzeni na 5 let (přiznání je polehčující okolnost). Pokud budou oba zapírat (Z), budou oba odsouzeni za menší delikt na 1 rok. Pokud se přizná jen jeden, bude v roli korunního svědka osvobozen, ale druhý obviněný bude odsouzen na 10 let. Příslušný zápis této hry v normálním tvaru je na Obr. 26. Čísla v dvojmatici udávají výši trestu. Cílem „hráčů“ je tuto hodnotu minimalizovat, neboli zvolit strategii, pro kterou bude maximální výše trestu (pro možné strategie spoluobviněného) minimální. Tedy

15


vězeň č. 1

s* = mini maxj uij

vězeň č. 2

t* = minj maxi vij

Z toho vychází rovnovážná strategie (s*, t*) = (přiznat, přiznat). Pohledem na dvojmatici ovšem zjistíme, že vhodnější (z hlediska výše trestu) by byla strategie (zapírat, zapírat), neboť v tomto případě by výše trestu pro oba byla nižší – proto název hry „dilema“. Žádný z obviněných totiž neví, zda jeho komplic nepodlehne pokušení přiznat se a vyváznout bez trestu. vězeň 2 P Z vězeň 1

Z ⎛ (1,1) (10,0) ⎞ ⎜ ⎟ P ⎜⎝ (0,10) (5,5) ⎟⎠

Obr. 26 Vězňovo dilema

Příklad: manželská domluva Manželé řeší otázku, jak strávit večer. Manžel by chtěl jít na fotbal, manželka preferuje divadlo. Večer však chtějí strávit společně. Tuto „hru“ můžeme znázornit maticí uvedenou na Obr. 27. manželka fotbal divadlo manžel

fotbal ⎛ (2,1) (0,0) ⎞ ⎜ ⎟ divadlo ⎜⎝ (0,0) (1,2) ⎟⎠

Obr. 27 Manželská domluva

Tato hra má dvě ryzí strategie v rovnovážných bodech (fotbal, fotbal) a (divadlo, divadlo). Platí totiž, že prvek (2,1) představuje maximum v prvním řádku i prvním sloupci a prvek (1,2) představuje maximum ve druhém řádku i druhém sloupci. Hra má i jednu smíšenou strategii.

2.3 Hledání vhodné strategie Minimaxová strategie

Za předpokladu racionality protihráče volím takový tah, aby následný nejlepší tah protihráče byl z mého pohledu nejméně nebezpečný. Minimaxovou strategii mohu hledat na základě zápisu hry v rozvinutém tvaru. Tento zápis je tvořen stromem, kde každému uzlu přiřadíme hodnoty na základě hodnot výher (hodnot funkce u) v podstromu daného uzlu. Jednotlivé uzly stromu se dělí do MAX úrovní (uzly se sudou hloubkou) a MIN úrovní (uzly s lichou hloubkou). Na každé MAX úrovni vybírá první hráč tah, který maximalizuje hodnotu určitého kritéria, na každé MIN úrovni vybírá druhý hráč tah, který minimalizuje hodnotu tohoto kritéria. (kritériu hodnotí tahy z pohledu prvního hráče). Tímto kritériem je tzv. MINIMAX hodnota:

pro n listový uzel ⎧ u (n) ⎪ MINIMAX (n) = ⎨max s MINMAX ( s ) pro n je MAX uzel ⎪ min MINMAX ( s ) pro n je MIN uzel s ⎩ kde s jsou všichni následníci uzlu n. Ohodnocování uzlů probíhá od spodu - od listů reprezentujících koncovou situaci hry směrem ke kořeni. Příklad takto ohodnoceného stromu vidíme na Obr. 28. Je zřejmé, že první hráč zvolí tah odpovídající první větvi zleva.

16


Obr. 28 Volba strategie dle minimaxu

Aplikace minimaxového přístupu předpokládá, že známe celý strom řešení. V reálných hrách to může být nepřekonatelný problém. Jak již bylo zmíněno, hra tic-tac-toe má 26830 různých partií, strom řešení pro šachy pak může mít okolo 35100 uzlů (průměrný počet větvení 35, průměrná délka partie 50 tahů). Navíc, časová náročnost algoritmu O(bd), tedy exponenciální podle hloubky prohledávání (a paměťová náročnost je O(bd) – jde totiž o prohledávání do hloubky). Řešením je: • omezit hloubku prohledávání • pracovat pouze s odhady místo s přesnými hodnotami užitku pro jednotlivé uzly Příklad: Tic-Tac-Toe. Obr. 29 ukazuje volbu prvního tahu s využitím minimaxu pro hru tic-tac-toe. Kritérium, kterým se hodnotí jednotlivé uzly je počet možných vítězných pozic X minus počet možných vítězných pozic O.

Obr. 29 Tic-tac-toe volba prvního tahu dle minimaxu

17

MATEMATICKÁ TEORIE ROZHODOVÁNÍ

Recommend Documents