Algorithms for learning in simple and complex games
Code  Completion  Credits  Range  Language 

01ALUC  Z  1  1  Czech 
 Course guarantor:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

The goal of this series of lectures is to get form the very basics of game theory and machine learning all the way to solid understanding of the algorithm used in DeepStack. We will explain how games can be formally modeled, what are meaningful definitions of optimal strategies in games and what is Nash equilibrium in particular. Afterwards, we will focus on simple learning mechanisms in repeated decisionmaking problems called multiarmed bandit problems. We will show basic properties of learning in these models and then investigate what happens if these algorithms are run against each other in a game. This will form the bases of an algorithm for computing Nash equilibria in simple zerosum games, which can be extended to Counterfactual Regret Minimization (CFR) in extensive form games. Next, we will explain why it is complicated to decompose extensive form game to independent parts and how CFRD can solve this problem under certain conditions. Finally, we will briefly introduce deep neural networks and combine all the introduced components to the first algorithm that was able to beat professional poker players.
 Requirements:
 Syllabus of lectures:
 Syllabus of tutorials:
 Study Objective:

Acquired knowledge: Students will learn the basic concepts of game theory. They will acquire the theoretical foundation for understanding the stateofart algorithms for solving the games with incomplete information, like card games.
Acquired skills: Modeling problems from game theory and proposing algorithms of artificial intelligence for their solution.
 Study materials:

Compulsory literature:
M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, M. Bowling, DeepStack: Expertlevel artificial intelligence in headsup nolimit poker, Science, Vol. 356, Issue 6337, pp. 508513 (2017)
Optional literature:
J. Nash, Equilibrium points in nperson games, Proceedings of the national academy of sciences 36.1, pp. 4849 (1950)
N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans: