Rozšířená forma

Rozšířená forma hry (explicitní forma hry, hry v rozvinutém tvaru, hry v explicitním tvaru) je disciplína z oboru teorie her, která se soustřeďuje na tzv. tahové hry.

Základní typy her z oboru teorie her (např. hra v normálním tvaru, hra s konstantním součtem, hra s nekonstantním součtem a další) popisují konfliktní situaci pomocí matice a předpokládají, že hráči se rozhodují o volbě herní strategie ve stejný časový okamžik. Rozhodnutí jednoho hráče potom nemůže ovlivnit volbu druhého hráče, protože svou strategii realizují současně.

Rozšířená forma hry naopak předpokládá, že hráči rozhodují konfliktní situaci po tazích, tedy jeden po druhém. Rozhodnutí jednoho hráče o volbě jeho strategie ovlivňují předchozí tahy ostatních hráčů. Celá hra je procesem sekvence rozhodnutí jednotlivých hráčů.^[1]

Grafická reprezentace rozšířené formy hry

Protože zachycení tahové hry v matici by bylo velmi obtížné, používá se k reprezentaci her v rozvinutém tvaru množina uzlů a hran, neboli graf. Jedná se o typ grafu strom, proto se grafické znázornění hry označuje pojmem „strom hry“.^[1]

Strom – nejdůležitější vlastnosti pro rozšířenou formu hry

Strom je souvislý a acyklický graf a jedním počátečním uzlem a několika koncovými uzly.^[1][2]
Graf je souvislý, pokud mezi dvěma různými uzly existuje cesta, která tyto dva uzly spojuje.^[2]
Graf je acyklický, pokud v něm neexistuje cyklus, tedy pokud neexistuje uzavřená cesta mezi různými uzly.^[2]

Počáteční uzel stromu nese označení kořen, v celém grafu je jenom jeden a určuje výchozí bod hry. Například ve hře dáma by se jednalo o počáteční rozestavení kamenů na šachovnici.
Koncové uzly představují možné konce hry, což jsou stavy, do kterých se hra může v závislosti na volbě strategií jednotlivých hráčů dostat a kterými končí.
Ostatní uzly grafu jsou tak zvané rozhodovací uzly, neboli uzly, ve kterých se hráči rozhodují, jakou strategií zvolí v právě probíhajícím kole.

Řešení hry v rozvinutém tvaru

Pro řešení hry v rozvinutém tvaru jsou zásadní dva pojmy – zpětná indukce a podhra.

Podhra

Každá hra v rozvinutém tvaru se může rozložit na tzv. podhry, neboli části původní hry, které jsou sami o sobě také hrami a pro něž hledáme nejlepší řešení. Analyzujeme postupně jednotlivé podhry a jejich řešením se na konci dostaneme k výsledku celé tahové hry.^[1]

Zpětná indukce

Hru v rozvinutém tvaru neřešíme běžným způsobem od počátku stromu – kořene ke koncovým uzlům, ale opačným způsobem. Vycházíme z koncového uzlu a snažíme se najít optimální řešení podhry. Když jej nalezneme, stává se koncovým uzlem toto řešení a přecházíme do další podhry, kde porovnáváme toto řešení s dalšími koncovými uzly. Tímto způsobem projdeme všechny podhry, nalezneme jejich nejlepší řešení a postupně se dostaneme až k výchozímu uzlu – kořenu stromu. Tím nalezneme řešení celé hry.^[1]

Vycházíme z předpokladu, že racionální hráč volí při svém rozhodování pro něj nejlepší možnou strategii. Při hledání optimálního řešení podhry hledáme tzv. dokonalou rovnováhu podhry pro všechny rozhodovací situace.

Dokonalá rovnováha podhry

Dokonalá rovnováha podhry ukazuje, kterou strategii by měli hráči hrát v jednotlivých rozhodovacích uzlech, aby pro ně tato strategie byla optimální a také, do kterých uzlů by se racionální hráči vůbec neměli dostat. Optimální strategie je taková, která hráči přináší nejvyšší výhru (užitek).^[3]

Postup tvorby stromu hry

Způsob tvorby stromu zachycuje následující příklad. Jedná se o hru „Stonožka“. Příklad vychází z publikace Úvod do teorie her^[3]. Hru hrají dva hráči a snaží se maximalizovat svou výhru. Hráč, který je na tahu může buď přijmout výhru, která na něj připadá a zakončit tak hru, nebo může chtít ve hře pokračovat a tím zdvojnásobit možnou výhru pro oba hráče. Pokud se rozhodne pro variantu pokračování, jednotlivé výše výher se otočí – výhra prvního hráče se stane výhrou druhého hráče a naopak. Takto hráči postupují až do konce hry, který v tomto případě nastává po předem určeném počtu kol. V příkladu je počet kol stanoven na 5. Strom hry zobrazuje obrázek 1.

Vlevo je uveden hráč, který provádí rozhodnutí, jednotlivé uzly přestavují kořen, rozhodovací a koncové uzly. V prvním kole se hráč 1 rozhoduje, jestli výhru přijme, nebo zvolí, aby hra pokračovala. Pokud vybere pokračování, přichází na řadu hráč 2, ten opět volí mezi vybráním výhry a pokračováním. Obdobným způsobem hra pokračuje až do posledního kola.

Postup řešení hry v rozvinutém tvaru

Pro možnost nalezení optimální strategie je nutné ke každému uzlu doplnit užitek, který by z něj hráč měl, pokud by jej zvolil. V této fázi se užitek doplňuje pouze do koncových uzlů. Užitek vyplývá z následujícího zadání. V prvním kole by hráč 1 získal výhru 3 jednotky užitku (např. Kč) a hráč 2 výhru 1 jednotku užitku, pokud by se rozhodl pro možnost Přijmout. Pokud ne, výhra by se změnila na 2 jednotky užitku pro hráče 1 a 6 jednotek užitku pro hráče 2 – zdvojnásobení a otočení výhry. Takto by hra pokračovala až do posledního pátého kola. Situaci ukazuje obrázek 2. Užitek prvního hráče je první číslo, užitek druhého hráče druhé – znázorňuje schéma:

Pomocí zpětné indukce lze zjistit optimální strategie obou hráčů. Začínáme od posledního rozhodovacího uzlu a postupujeme směrem ke kořenu. Posledním rozhodovacím uzlem je uzel, v němž se rozhoduje hráč 1 mezi možnosti Přijmout výhru 48 nebo Pokračovat. Protože se jedná o poslední kolo hry, ví, že hráč 2 nemůže vybrat jinou možnost, než přijmout a proto by hráč 1 získal výhru pouze 32. Možnost Přijmout je pro něj výhodnější a proto volí výhru 48. Do rozhodovacího uzlu vepisujeme výhru 48;16, uzel se stává koncovým a přesouváme se k dalšímu rozhodovacímu uzlu v pořadí, kterým je uzel, kde hráč 2 volí mezi výhrou 24 (Přijmout) a výhrou 16 (Pokračovat), kterou jsme zjistili z řešení předchozí podhry. Vybírá možnost Přijmout a do rozhodovacího uzlu vepisujeme hodnotu 8;24. Zjišťujeme výsledky podher až ke kořeni, kde dojdeme k celkovému výsledku hry. Pokud označíme spojnice mezi uzly tak, jak se hráči rozhodovali, získáme dokonalou rovnováhu podhry. Výsledek ukazuje obrázek 3.

Dokonalou rovnováhu podhry označují tučně znázorněné spojnice mezi uzly. Z řešení vyplývá, že racionální hráč by měl ke konci hry dojít hned v prvním kole a to přijetím výhry 3;1. K dalším rozhodnutím by vůbec nemělo dojít. Paradoxně hra ukazuje, že i když by hráči mohli získat mnohem vyšší výhru, racionální strategií je ukončit hru hned na počátku.

Příklady her v rozvinutém tvaru

Jako příklady her v rozvinutém tvaru se uvádí klasické salónní hry, například už dříve zmíněná dáma nebo šachy a dále také hry typu Ruská ruleta a podobně.

Ruská ruleta

Ruská ruleta představuje jeden z typických příkladů rozšířené formy hry. Hra předpokládá dva hráče, šestiranný revolver, jeden náboj a dvě strategie – střílet, vzdát se. Pokud se hráč vzdá, okamžitě prohrává hru. Pokud střílí, má dvě možnosti – buď přežije, nebo zemře. Pokud přežije, přichází na řadu druhý hráč a má opět volbu mezi možností vzdát se a střílet. Na rozdíl od předchozího příkladu „Stonožky“, v Ruské ruletě není užitek hráčů vyjádřen penězi, ale pouze jejich vlastním pocitem, který budou mít při jednotlivých výsledcích prohra, výhra, smrt. Podle výše užitku se může řešení hry a optimální strategie měnit. Pro řešení předpokládejme užitky v tabulce.

Řešení zobrazuje obrázek 4. Kromě prvků představených v předchozím příkladu obsahuje strom hry i tzv. náhodnou složku při volbě strategie střílet. Pokud hráč zvolí tuto strategii, je pravděpodobnost p, že zemře a p-1, že přežije. Pravděpodobnost je uvedena na hranách grafu. Náhodnou složku představují uzly, kde nedochází k rozhodování hráčů, ale k rozhodování náhody.

Označíme-li

• užitek náležící náhodné složce ${\displaystyle (U_{1};U_{2})}$, kde ${\displaystyle U_{1}}$ je užitek hráče 1 a ${\displaystyle U_{2}}$ užitek hráče 2,
• pravděpodobnosti stavů, které mohou nastat ${\displaystyle p_{1}}$ a ${\displaystyle p_{2}}$, přičemž musí platit ${\displaystyle p_{1}+p_{2}=1}$,
• užitky nastalých stavů ${\displaystyle (U_{11};U_{12})}$ pro první stav a ${\displaystyle (U_{21};U_{22})}$ pro druhý stav,

můžeme výpočet definovat následovně:

Tento vzorec platí, pokud uvažujeme, že náhodná složka vybírá mezi dvěma výslednými stavy. Nechť n = {1,2,…, n} je množina možných výsledných stavů, potom lze vyjádřit výpočet užitků náhodné složky pro dva hráče takto:

Nechť počet hráčů je m={1,2,…, m} a množina výsledných stavů n={1,2,…, n}, potom zřejmě platí:

za podmínky

Z obrázku vyplývá, že při výše zadaných užitcích budou hráči volit strategii střílet až do konce hry. Ve chvíli, kdy bylo z revolveru již 5krát vystřeleno a oba hráči dosud žijí, je 100% pravděpodobnost, že šestý výstřel znamená pro hráče, který je na tahu, smrt. Protože pro hráče 2 (hráč na tahu) znamená smrt i prohra stejný užitek, vybírá mezi možnostmi náhodně – obě jsou stejně pravděpodobné. Pokud by mu přinášela větší užitek možnost smrt, volil by smrt, pokud prohra, volil by prohru.

Salónní hry

Hry v rozvinutém tvaru se využívají pro matematický rozbor salónních her, jako například dříve zmíněná dáma, šachy, poker, kostky, hra NIM a podobně.

Terminologie teorie her uvádí dva termíny důležité pro hry v rozvinutém tvaru – hra s dokonalou informací a hra s nedokonalou informací.

Hra s dokonalou informací

Je taková hra, kde zná každý hráč po celou dobu stav, ve kterém se hra nachází a zároveň zná strategie své i svého protihráče. Příkladem může být například dáma, kde oba hráči znají aktuální pozici kamenů na šachovnici i všechny možné tahy, které může protihráč zahrát.^[4]

Hra s nedokonalou informací

Je taková hra, kde nedokáže přesně určit, ve které pozici se hra nachází. Hra s nedokonalou informací jsou například karetní hry, kde hráč nemůže přesně vědět, jaké karty drží jeho protihráč.^[4]

Konečná hra

Hra se označuje za konečnou, pokud má konečný počet tahů a v každém tahu může hráč volit z konečného počtu strategií.^[4]

Při znalosti předchozích pojmů lze formulovat (a dokázat) následující větu:

Z definice vyplývá řešení následujících příkladů. Příklady vycházejí z publikace Úvod do teorie her^[4].

Příklady salónních her

NIM

Hra NIM je hra pro libovolný počet hráčů. Hráči postupně, po tazích, odebírají herní kameny (např. sirky) z několika hromádek a to tak, že musí vzít vždy minimálně jeden kámen. Maximální množství odebraných kamenů není omezeno, musí však být splněna podmínka, že hráč, který je na tahu a kameny odebírá, smí odebírat pouze z jedné hromádky. Hráč, který odebere poslední kámen, prohrál. Příklad uvažuje hru typu 2x2, tedy dva hráče a dvě hromádky, v každé z nich dva kameny. Strom hry, společně s řešením hry, znázorňuje obrázek 5.

Na hře NIM je dobře vidět, že výsledek hry v rozšířeném tvaru můžeme znát ještě před samotným začátkem hry. Při hře NIM 2x2 je před započetím hry oběma hráčům jasné, že pokud se budou chovat racionálně, hru vždy vyhraje hráč 2. Hráč 1 vždy prohraje. Prvním tahem může rozhodnout o tom, kterým ze dvou způsobů chce prohrát. Nikdy však nemůže vyhrát, pokud některý z hráčů neudělá chybu. Hra NIM 2x2 má dvě ryzí strategie.

Šachy

Šachy jsou v principu stejná hra jako hra NIM. Ještě před samotným začátkem hry je teoreticky možné vypočítat, kdo hru vyhraje. Vzhledem k tomu, že už po prvním tahu obou hráčů může na šachovnici nastat 400 možných kombinací figur (400 uzlů) a počet kombinací se s každým dalším tahem zvyšuje, je výpočetní složitost úlohy natolik vysoká, že nelze sestavit úplný strom hry a pomocí zpětné indukce zjistit řešení hry. Protože jsou šachy konečná hra s dokonalou informací, můžeme s určitostí říct, že hra má řešení. Toto řešení ještě nikdy nebylo spočítáno, ale lze s jistotou tvrdit, že platí jedna ze tří variant^[5]:

1. Bílý má vítěznou strategii
2. Černý má vítěznou strategii
3. Hra končí remízou

Na principu tvorby stromu hry je založena logika počítačových her šachy, kde jedním hráčem je počítač a druhým člověk. Počítač se po každém soupeřově tahu snaží vypočítat nejlepší možné řešení pomocí sestavování stromu hry. Z důvodu nedostatečné časové i výpočetní kapacity počítače nesestavují celý strom, ale vždy jen jeho část a v té hledají optimální strategii. Počítačový výpočet optimální strategie může být modifikován například tak, že počítače přiřadí každé figuře určitou hodnotu podle toho, jaký má vliv na další vývoj hry. Poté se snaží najít nejlepší možnou strategii v části stromu v závislosti na výši hodnot figur.

Konflikt dvou firem

Hra v rozvinutém tvaru, stejně tak, jako ostatní hry z oboru teorie her, nemusí hledat řešení pouze v případě opravdových her, jako Ruská ruleta, NIM, šachy a podobně. Teorii lze použít i při řešení ekonomického problému. Představme si situaci, kdy na trhu již operují určité firmy a další firmy zvažují vstup na tento trh. Pro zjednodušení budeme předpokládat jednu stávající firmu (Firma 1) a jednu novou (Firma 2). Užitky obou firem jsou uvedeny níže.

Firma 1 ví, že vstup na trh zvažuje nová firma a rozhoduje se, zda zvolit pasivní nebo aktivní strategii. Pasivní strategie znamená, že firma 1 nebude proti vstupu firmy 2 nijak bojovat a přijde tak o část svého zisku. Aktivní strategie naopak znamená, že se firma 1 rozhodne pro boj proti vstupu druhé firmy na trh. Tento boj představuje pro firmu 1 určité náklady, které sníží její výsledný užitek. Firma 2 se rozhoduje, jestli vstoupit nebo nevstoupit na trh a zvažuje při tom i rizika spojená s bojem firmy 1, která by v případě vstupu firmy 2 snížila její výsledný užitek.

V této hře hraje důležitou roli posloupnost rozhodnutí (tahů) firem – která firma učiní rozhodnutí první a která ji bude následovat. Existují tři možné situace:

• Obě firmy se rozhodují současně – jedná se o hru v normálním tvaru, a proto se bude řešit pomocí matice jako hra s nekonstantním součtem.
  Nashovou rovnováhou a tedy optimální strategií v této hře je žádná akce firmy 1 a vstup firmy 2.

• Firma 1 se rozhoduje první – hra v rozvinutém tvaru zobrazená pomocí stromu hry.
  Dokonalou rovnováhu hry označují tučné spojnice. Firma 1 začne bojovat a firma 2 na trh nevstoupí. Optimální strategie pro prvního hráče je boj, pro druhého hráče žádná akce.

• Firma 2 se rozhoduje první – hra v rozvinutém tvaru zobrazená pomocí stromu hry
  Pokud první tah učiní firma 2, optimální strategie hry bude vstup firmy 2 na trh a žádná akce firmy 1. Dokonalá rovnováha je opět vyznačena tučně.

Příklad ukazuje, že výsledek hry a volba strategií záleží na pořadí, ve kterém hráči provádí své tahy.

Reference

Literatura

• [Dlouhý, 2009] DLOUHÝ, Martin; FIALA, Petr. Úvod do teorie her. 2.přepracované vydání. Vysoká škola ekonomická v Praze : Nakladatelství Oeconomica, 2009. 120 s. ISBN 978-80-245-1609-7.
• [Fiala, 2002] FIALA, Petr. Řízení projektů. 1. vydání. Praha : Ediční oddělení VŠE Praha, 2002. 176 s. ISBN 80-245-0448-0.

Související články

• Teorie her
• Strategie (teorie her)
• Nashova rovnováha
• Strom (graf)