Teorie her
Úloha 1: Reklamní strategie
Dvě firmy, Firma X a Firma Y, se rozhodují, jakou reklamní strategii zvolí pro propagaci svého produktu. Každá firma má tři možnosti: Televize (T), Internet (I) nebo Billboardy (B). Výplatní matice ukazuje zisky (v milionech korun) pro každou kombinaci strategií.
Firma Y: T | Firma Y: I | Firma Y: B | |
Firma X: T | (4, 3) | (2, 5) | (3, 4) |
Firma X: I | (5, 2) | (3, 3) | (4, 6) |
Firma X: B | (3, 4) | (6, 4) | (2, 2) |
Když tedy např. Firma X zvolí propagaci pomocí internetu a Firma Y pomocí televize, pak Firma X bude mít zisk 5 milionů Kč a Firma Y 2 miliony Kč.
- Jaká jsou zde Nashova equilibria?
- Najděte Paretovsky optimální akční profily.
- Odstraňte z tabulky striktně dominované strategie.
Úloha 2: Rozhodování v investicích
Dva hráči, Investor A a Investor B, se rozhodují, do kterých projektů investují své prostředky. Každý hráč má na výběr ze tří projektů: Projekt X, Projekt Y a Projekt Z. Každý projekt má různé výnosy a rizika, která ovlivňují konečný zisk.
Každý hráč si vybere jeden projekt, do kterého investuje. Výnosy z projektů jsou ovlivněny rozhodnutím obou hráčů. Cílem je maximalizovat svůj zisk (uvedený v statisících Kč).
Investor B: X | Investor B: Y | Investor B: Z | |
Investor A: X | (3, 3) | (2, 4) | (1, 5) |
Investor A: Y | (4, 2) | (5, 5) | (3, 3) |
Investor A: Z | (5, 1) | (3, 3) | (4, 4) |
- Jaká jsou zde Nashova equilibria?
- Najděte Paretovsky optimální akční profily.
- Odstraňte z tabulky striktně dominované strategie.
Úloha 3: Strategická hra Hex
Hex je strategická desková hra pro dva hráče, kde cílem je propojit protilehlé strany hrací desky pomocí svých kamenů. Hra se hraje na šestiúhelníkové mřížce, obvykle o velikosti 11x11, ale mohou být použity i jiné velikosti. Zde budeme uvažovat mřížku 7x7.
- Vytvořte pro tuto hru herní strom.
- Úlohu řešte pomocí algoritmu Minimax
- Kdo vyhraje při perfektní hře?
- Úlohu řeště pomocí alfa-beta prořezávání
- Jak se zmenšil počet expandovaných uzlů?
Úloha 4: Hra 2048 VI.
V této úloze budeme 2048 chápat jako zero-sum hru dvou hráčů, kde hráč 1 vyhraje, pokud dosáhne dílku 2048 a hráč 2 vyhraje, pokud při svém tahu nebude mít, kam umístit nový dílek.
- Úlohu řešte pomocí algoritmu Minimax
- Kdo vyhraje při perfektní hře?
- Úlohu řeště pomocí alfa-beta prořezávání
- Jak se zmenšil počet expandovaných uzlů?
Úloha 5: Strategická hra Mlýn
Hra Mlýn, známá také jako Nine Men’s Morris, je strategická desková hra pro dva hráče, která pochází z období kolem roku 1400 př. n. l. Hraje se na speciální desce s 24 průsečíky, kde každý hráč má devět kamenů.
- Vytvořte pro tuto hru herní strom.
- Úlohu řešte pomocí algoritmu Minimax
- Kdo vyhraje při perfektní hře?
- Úlohu řeště pomocí alfa-beta prořezávání
- Jak se zmenšil počet expandovaných uzlů?