Logo ČVUT
Loading...
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025
Faculties | School elective courses | ECTS courses catalogue | Settings | Česká verze
Welcome page > Faculty of Information Technology > Department of Theoretical Computer Science > Combinatorial Theories of Games

Combinatorial Theories of Games

The course is not on the list Without time-table
Code Completion Credits Range Language
NI-KTH Z,ZK 4 2P+1C Czech
Course guarantor:
Lecturer:
Tutor:
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:
Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-10-11
Copyright © Jiří Kosek, 2010–2022 | Copyright © ČVUT, 2010–2022
Hosted by Výpočetní a informační centrum ČVUT
Send your questions and comments to HelpDesk ČVUT or to spravcekos@cvut.cz
For updated information see http://bilakniha.cvut.cz/en/predmet6290706.html