|Module title||Combinatorial games|
|Module lecturer||dr hab. Małgorzata Bednarska-Bzdęga|
|Lecturer position||prof. UAM|
|Faculty||Faculty of Mathematics and Computer Science|
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.
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.
Elwyn Berlekamp, John Conway, Richard Guy "Winning Ways for Your Mathematical Play", vol.1,2,3,4, A K Peters Ltd.