Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2020/2021

Combinatorial Theories of Games

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
NI-KTH Z,ZK 4 2P+1C Czech
Lecturer:
Tomáš Valla (guarantor)
Tutor:
Jan Matyáš Křišťan
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:
Time-table for winter semester 2020/2021:
Time-table is not available yet
Time-table for summer semester 2020/2021:
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
roomT9:343
Valla T.
11:00–12:30
(lecture parallel1)
Dejvice
NBFIT učebna
roomT9:343
Křišťan J.
12:45–14:15
(lecture parallel1
parallel nr.101)

Dejvice
NBFIT učebna
Fri
Thu
Fri
The course is a part of the following study plans:
Data valid to 2021-04-10
For updated information see http://bilakniha.cvut.cz/en/predmet6290706.html