Combinatorial games

Timetable

Thursdays 13:30-15:15, starting from 19th October

 room A2-24 (in the building of the Faculty of Mathematics and CS)

Module aim (aims)

The aim of the course is to discover some mathematics behind playing games. We will see why it is hard to write a computer program which  analyses all possible positions in games like chess. During the course a student will meet games in a few branches of mathematics, for example in graph theory. Basic general methods of finding a good strategy will be presented. We will consider games with no chance moves (no randomness, no dice rolling).  

Pre-requisites in terms of knowledge, skills and social competences (where relevant)

Prior basic experience in combinatorics is helpful, but not not required.

Syllabus

1. Logic warm-up. "for every ...",  "there exists...", checking if a statement is false or true.
Game examples: chess, Tic-Tac-Toe, HEX, other combinatorial games. Human intuitisions about strategies. Naive methods of finding good strategies.

 2. How to check that our strategy is good. Game tree, backward analysis. Winning and non-losing strategies. Strategy stealing argument, pairing strategy.

3. Play to get as much as possible: Games with the score. Min-max theorem for deterministic games.

4. Graphs in games, games on graphs. Coloring games and Ramsey theory, Shannon switching game.

5. NIM games. What we get based on the intuition. What we get if we apply a tool called the theory of nimbers.

6. If time permits: HEX -- history, analysis, hints for your play. HEX tournament.

Forms of Assessment

Written exam at the end of the course. Student activity during the classes may increase her/his grade. 

Reading list

Elwyn Berlekamp, John Conway, Richard Guy "Winning Ways for Your Mathematical Play", vol.1,2,3,4, A K Peters Ltd.