Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025
NOTICE: Study plans for the following academic year are available.

Combinatorial Theories of Games

Display time-table
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
roomTH:A-1247
Valla T.
14:30–16:00
(lecture parallel1)
Thákurova 7 (budova FSv)
roomTH:A-1247
Pokorný J.
16:15–17:45
(lecture parallel1
parallel nr.101)

Thákurova 7 (budova FSv)
Thu
Fri
The course is a part of the following study plans:
Data valid to 2025-03-12
For updated information see http://bilakniha.cvut.cz/en/predmet6290706.html