FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

Teorie her

Zpět na výběr úloh

Ú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: TFirma Y: IFirma 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č.

  1. Jaká jsou zde Nashova equilibria?
  2. Najděte Paretovsky optimální akční profily.
  3. 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: XInvestor B: YInvestor 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)
  1. Jaká jsou zde Nashova equilibria?
  2. Najděte Paretovsky optimální akční profily.
  3. 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.

  1. Vytvořte pro tuto hru herní strom.
  2. Úlohu řešte pomocí algoritmu Minimax
    • Kdo vyhraje při perfektní hře?
  3. Ú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.

  1. Úlohu řešte pomocí algoritmu Minimax
    • Kdo vyhraje při perfektní hře?
  2. Ú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ů.

  1. Vytvořte pro tuto hru herní strom.
  2. Úlohu řešte pomocí algoritmu Minimax
    • Kdo vyhraje při perfektní hře?
  3. Úlohu řeště pomocí alfa-beta prořezávání
    • Jak se zmenšil počet expandovaných uzlů?