Algoritmická teorie her a poker - NOPT055

• Anglický název: Algorithmic game theory and poker
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2015 do 2015
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: Mgr. Martin Schmid, Ph.D.; Mgr. Matej Moravčík, Ph.D.; prof. Mgr. Milan Hladík, Ph.D.
• Kategorizace předmětu: Informatika > Optimalizace

Anotace

čeština

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (06.05.2014)

Posluchač se seznámí s nejdůležitějšími koncepty teorie her. Získá potřebný teoretický základ pro pochopení state-of-the-art algoritmů pro řešení her s neúplnou informací, jako jsou například karetní hry. Dále se kurz soustředí na karetní hry, konkrétně Poker. Studenti pochopí fungování nejlepších Pokerových programů na světě, včetně jejich slabin a předností. Díky kurzu získají studenti také představu o aplikacích matematické optimalizace. Pro bližší pochopení zde prezentovaných aplikací je vhodné absolvovat pokročilejší přednášky z optimalizace.

angličtina

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (06.05.2014)

The most important concepts of the game theory are introduced. Students will learn the theory to understand how the state-of-the art algorithms for the games with imperfect information, such as card games. Later, the course focuses on these games, such as Poker. Students will understand how the best Poker programs in the world work, including the strong and weak parts. The course also shows the application of math optimization and suggests another classes for better understanding of the concepts involved.

Literatura

čeština

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (06.05.2014)

[1] Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007.

[2] http://poker.cs.ualberta.ca/publications.html

[3] Martin Schmid: Game Theory and Poker, diplomová práce, MFF UK, 2013.

Sylabus

čeština

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (06.05.2014)

1) Formální modely teorie her, reprezentace strategií

• maticové hry

• spojité hry

• stochastické hry

• extensive form hry

2) Nashovo equilibrium 1

• optimalita strategie

• vztah optimality a best response

3) Nashovo equilibrium 2

• existence či neexistence

• spojité případy

4) Složitostní třídy

• polynomiální případy

• PPAD, NP

5) Poker 1

• seznámení s hrou

• formalizace pokeru v rámci modelů teorie her

• malé karetní hry a jejich řešení

6) Poker 2

• push-fold hra dvou hráčů

• matematický model push-fold turnaje

7) Regret

• představení a formalizace

• regret matching

• CFR

• Monte carlo CFR

• princip samplování

• různé samplingy

8) Herní abstrakce

• bezeztrátové abstrakce

• imperfect recall abstrakce

• overfitting

9) Pokerové abstrakce

• karetní abstrakce

• sázkové abstrakce

10) Annual Computer Poker Competition

• soutěž a soutěžící

angličtina

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (06.05.2014)

1) Game theory models, strategies

• matrix games

• continuous games

• stochastic game

• extensive form games

2) Nash equilibrium 1

• optimality

• optimality vs best response

3) Nash equilibrium 2

• Existence/non existence

4) Complexity

• Polynomial cases

• PPAD, NP

5) Poker 1

• Game introduction

• Formalization of Poker

• Simple poker-like games

6) Poker 2

• Heads up push-fold game

• Tournaments

7) Regret

• Introduction

• Regret matching

• CFR

• Monte carlo CFR

• Sampling principle

• Sampling variants

8) Game abstractions

• Lossless abstractions

• Imperfect recall abstractions

• Overfitting

9) Poker abstractions

• Card abstractions

• Betting abstractions

10) Annual Computer Poker Competition