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.
• hra - je každá konfliktní situace.
• hráč - účastník hry, který svým chováním může ovlivnit její výsledek; hráč může být buď racionální (usiluje o optimální výsledek hry) nebo indiferentní (výsledek hry je mu lhostejný)
• strategie - předpis, kterým je určena jedna alternativa chování hráče při hře
• optimální strategie – hráčem zvolená alternativa, která je pro něj nejvýhodnější
• prostor strategií – seznam všech možných alternativ, které jsou hráči dostupné
• výplata hráče - kvantitativně vyjádřený výsledek hry, posuzovaný z hlediska uvažovaného hráče (kladná hodnota - užitek, záporná hodnota - prohra)
• výplatní funkce hráče - předpis pro výplatu v závislosti na zvolené strategii
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 (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í).
• 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.
Všichni hráči se rozhodují najednou (současně).
Hra v normálním tvaru je definována množinou
{Q,X1,…,Xn,u1(x1,…,xn),…,un(x1,…,xn)}
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. 1. 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.
Obrázek SEQ Obrázek \* ARABIC 1 - Hra pro dva hráče v normálním tvaru
Explicitní tvar hry bývá používán k formalizaci her, ve kterých hraje roli pořadí tahů. Hráči se rozhodují postupně – nejprve se rozhodne a jedná (udělá tah) nějaký hráč, potom se rozhodne a jedná další hráč. Hry jsou reprezentovány jako stromy. 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.
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. 1). 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)
Definice: 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.
Minimax je algoritmus, používaný pro hraní strategických her mezi dvěma a více hráči. Principem algoritmu je procházení stromu hry a minimalizace maximálních možných ztrát. Typickým úkolem je nalézt nejlepší tah v dané pozici.
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:
kde s jsou všichni následníci uzlu n.
Ohodnocování uzlů probíhá odspodu - od listů reprezentujících koncovou situaci hry směrem ke kořeni.
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. 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
Pseudokód
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val);
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val);
return bestValue
(* Inicializační volání pro hráč maximalizujícího tah *)
minimax(origin, depth, TRUE)
Metody (algoritmy), které vedou k tomu, že se prohledává pouze část stromu, se nazývají metody prořezávání. Říkáme, že se neperspektivní větev stromu stavového prostoru odřízne a neprohledává se. Prořezávání není nijak vázané na minimaxovou metodu prohledávání, ale dá se na ní poměrně snadno ukázat. Jednou z nejjednodušších metod prořezávání je α-β prořezávání (alfa-beta prořezávání, Alpha-beta pruning).
Do minimaxové metody zavedeme dvě proměnné: α a β. Proměnná α představuje maximální dosažitelné hodnocení maximalizujícího hráče – tedy nejvyšší hodnotu. Proměnná β představuje maximální dosažitelné hodnocení minimalizujícího hráče – tedy nejnižší (nejzápornější) hodnotu. Slovo dosažitelné je zde velmi důležité. Stále platí předpoklad minimaxové metody, že se protihráč bude snažit vyhrát. Předpokládáme tedy, že bude vybírat tahy, které jsou pro něj nejvýhodnější a naopak pro nás jsou nejméně výhodné. Tahy, které protihráč pravděpodobně neprovede, tedy musíme považovat za nedosažitelné.
Hodnota α se počítá na maximalizující úrovni jako maximum z hodnocení potomků aktuálního stavu a hodnoty α z nadřazené úrovně. Na minimalizující úrovni se hodnota α nijak nemění. Analogicky, hodnota β se počítá jako minimum z hodnocení potomků a z hodnoty β předané z nadřazené úrovně. Hodnoty α a β tedy nejsou globální maxima/minima hodnocení, ale probublávají mezi jednotlivými částmi stromu. K odříznutí části stromu může dojít na kterékoliv z úrovní v okamžiku, kdy je splněna podmínka α ≥ β . Na maximalizující úrovni lze tuto podmínku interpretovat tak, že jsme právě dosáhli tahu (s hodnocením α), který je pro soupeře více nevýhodný (je větší jak β). Soupeř bude táhnout tak, aby se do aktuální větve stromu nedostal, a tedy nemá smysl ji dále prozkoumávat.
Pseudokód
function alphabeta(node, depth, α, β, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
for each child of node
α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
if β ≤ α
break (* β cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
if β ≤ α
break (* α cut-off *)
return β
(*Inicializační volání*)
alphabeta(origin, depth, -∞, +∞, TRUE)