Algoritmy učení v jednoduchých a složitých hrách

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Cílem série přednášek je cesta od základů teorie her a strojového učení až k pochopení nedávno vyvinutého algoritmu DeepStack. Vysvětlíme, jak mohou hry být modelovány, jaké jsou rozumné definice optimálních strategií a co je Nashovo ekvilibrium. Poté se zaměříme na jednoduché učební postupy v problémech s opakovaným rozhodováním zvanými multi-armed bandit problems. Ukážeme základní vlastnosti učení v těchto modelech a poté se budeme zabývat tím, co se stane, pokud jsou tyto algoritmy spuštěny ve hře proti sobě. To bude základ algoritmu pro výpočet Nashova ekvilibria ve hrách s nulovým součtem, který pak bude rozšířen na Counterfactual Regret Minimization (CFR) pro hry s rozšířenou formou (extensive form games). Dále vysvětlíme, proč je obtížné rozložit hru s rozšířenou formou na nezávislé části a za jakých podmínek může CFR-D vyřešit tento problém. Závěrem stručně představíme hluboké neuronové sítě a zkombinujeme všechny probrané mechanismy do prvního algoritmu, který byl schopen porazit profesionální hráče pokru.

Požadavky:

Osnova přednášek:

Osnova cvičení:

Cíle studia:

Znalosti: 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.

Schopnosti: Modelování problémů z teorie her a tvorba algoritmů umělé inteligence na jejich řešení.

Studijní materiály:

Povinná literatura:

M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, M. Bowling, DeepStack: Expert-level artificial intelligence in heads-up no-limit poker, Science, Vol. 356, Issue 6337, pp. 508-513 (2017)

Doporučená literatura:

J. Nash, Equilibrium points in n-person games, Proceedings of the national academy of sciences 36.1, pp. 48-49 (1950)

N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: