Course Content
1. Combinatorial Games: Recreational games such as Chess, Checkers, Tic Tac Toe, Hex and Go motivate an axiomatization of game rules with perfect information. Examples of such rulesets with appealing mathematical structures are Nim, Wythoff Nim, Fibonacci Nim, Subtraction games, Hackenbush, Amazons, Konane, Clobber, Domineering and Toppling Dominoes. We will play some such games before plunging into the more theoretical parts.
2 Impartial Games and Perfect Play Outcomes: Normal play convention is last move wins. 2 players have the same options; the position space can be partitioned into two outcome classes: Previous- or Next- player win.
3. Sprague Grundy Theory: Every impartial normal play game is equivalent with a nim heap.
4. Partizan Games: Players have different sets of options. Four partially ordered Outcome classes, player Previous, Next, Left or Right wins.
5. Game Comparison: The set of all games together with defined game addition is a partially ordered group. This induces an abstract notion of game comparison, and a fundamental theorem gives an efficient play-comparison test.
6. Game Reduction: Domination and Reversibility reduce games to unique canonical forms.
7. Game Values: Games values are surreal numbers, switches, infinitesimals, dyadic rationals and more.
8. Game Approximations: Temperature theory, reduced canonical form, atomic weights
9. Other Play Conventions: misere play, scoring play, auction play, etc.
10. Reinforcement Learning and Combinatorial Games. We discuss a simple AI-approach to learn winning moves in a combinatorial game.
Reference
- Combinatorial Game Theory: A. N. Siegel, 2013, AMS Publ.
- On Numbers and Games: J. H. Conway, 1976, Academic Press
- Winning Ways for Your Mathematical Plays: E. Berlekamp, J. H. Conway, R. K. Guy ,1982, CRC
- Lessons in Play: M. H. Albert, R. J. Nowakowski, D. Wolfe, 2007, World Scientific