Combinatorial Theories of Games
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| NI-KTH | Z,ZK | 4 | 2P+1C | Czech |
- Course guarantor:
- Tomáš Valla
- Lecturer:
- Tomáš Valla
- Tutor:
- Jan Pokorný
- Supervisor:
- Department of Theoretical Computer Science
- Synopsis:
-
Traditional game theory is a branch of mathematics, which has broad applications in economy, biology, politics and computer science. This theory studies the behaviour of agents (players) of a certain competitive process by designinng a mathematical model and investigating the strategies. The traditional task of classical game theory is to find the equilibria, which are the states of the game where no player wants to deviate from his strategy.
Historically, the second big development in game theory of two-player full-information combinatorial games, was by Conway, Berlekamp and Guy. They developed a theory, originally used for solving end-games in Go, into a full fledged field. The idea is to evaluate games such that otherwise incompatible games can be added, that is, played simultaneously. This led to the algrebraic approach to study combinatorial games.
The third most important step is the work of Beck, who established the theory of positional games (like tic-tac-toe and hex). In analysis of these game, one cannot escape the brute-force traversal of the game tree, which is no efficient. Beck introduced the „false probabilistic method“, which aims to tackhle this problem.
In this course we build the foundation of the theory of combinatorial and positional games.
We focus on theoretical analysis of games and building the theory, not on the programming aspects of game solving algorithms. The course requires independent work, ability to mathematically analyse, think and proof.
The course is also suitable for bachelors student in the third year, who attended introduction to graph theory, as well as for PhD students looking for research topics.
- Requirements:
-
* do not fear the mathematics :)
* basics in graph theory, combinatorics and algebra
- Syllabus of lectures:
-
1) introduction to combinatorial games
2) formal definition of combinatorial games, game classes, strategy theorem
3) comparing games, game algebra (addition, negation, isomorphism)
4) no-number games, adding numbers
5) simplicity rule, dominating and reversible moves
6) infisitemal games, thermographs
7) strong and weak positinal games, strategy stealing, general tic-tac-toe
8) Hall theorem, pairing draw, resource counting
9) Erdös-Selfridge theorem, applications
10) ramsey games, other game versions
- Syllabus of tutorials:
-
Tutorials designed for deeper understanding the theory presented in the course and for analysis of simpler games.
- Study Objective:
-
To:
* introduce the algebraic combinatorial game theory due to Conway
* introduce the positional game theory due to Beck
* learn how to apply the theory to analyse several simpler games
- Study materials:
-
Berlekamp, Conway, Guy: Winning Ways
J. Beck: Combinatorial Games, Tic-Tac-Toe Theory
Conway: On Numbers and Games
Albert, Nowakowski, Wolfe: Lessons in Play
Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory
- Note:
-
This course is presented in Czech.
- Time-table for winter semester 2024/2025:
- Time-table is not available yet
- Time-table for summer semester 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri - The course is a part of the following study plans:
-
- Master specialization Computer Security, in Czech, 2020 (elective course)
- Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
- Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
- Master specialization Management Informatics, in Czech, 2020 (elective course)
- Master specialization Software Engineering, in Czech, 2020 (elective course)
- Master specialization System Programming, in Czech, version from 2020 (elective course)
- Master specialization Web Engineering, in Czech, 2020 (elective course)
- Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
- Master specialization Computer Science, in Czech, 2020 (elective course)
- Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
- Study plan for Ukrainian refugees (elective course)
- Master specialization System Programming, in Czech, version from 2023 (elective course)
- Master specialization Computer Science, in Czech, 2023 (elective course)