General Information
This course will present a number of combinatorial games and puzzles, focusing on those for which there exists mathematical techniques for solving them. (See the list of topics below for more information.)
Class meetings are on Tuesday and Thursday from 3:00 to 4:20 in Porter Hall 225B. The instructors are Danny Sleator and Alan Frieze.
The class mailing address is sleator+games@cs.cmu.edu. Here is the list.
Grading
The grading for the class will be based on a Midterm Exam, on a project, and on a final exam. (The weekly recommended homework problems will not count toward your grade. See the problems below.) Students have the option of doing a project, or taking the final exam, or both (only one will be counted toward your grade however). If you intend to do a project, you should submit a one-page project proposal describing the work you intend to do.
Important Dates
- Midterm Exam: October 23 in class
- Project proposals due: October 27
- Final Exam: December 11
Topics Covered
- Aug 28: Impartial Games (like Nim) [Ferguson Part I, PDF]. [Sleator's notes, txt].
- Aug 30: Sums of games (Sprague-Grundy Theory) [Ferguson Part I, PDF]. [Sleator's notes, txt].
- Sept 4: Dots and Boxes (Pick up handout outside of room 4116) Also, if you have access to a windows machine, you can play Smart Dots, © 1991 by Charles Timmerman, Symantec, Inc. In particular, try to win the 3x5 game against it in "grandmaster mode". It can be done using the tricks in the notes.
- Sept 6: Discussion of homework assignment 1
- Sept 11: no class
- Sept 13: Computer Analysis of Sprouts [Paper, ps]
- Sept 18-20: The Erdos Selfridge game (handout outside of 4116)
- Sept 25-27: Spencer's Tenure Game [PS]
- Oct 2-9: Positional Games (tick-tack-toe esque games) (Beck's Book)
- Oct 11: Discussion of homework 3.
- Oct 16-18: John Conway's Theory of Combinatorial Games [Sleator's notes, PDF] Get the handout "What is a Game" by Richard Guy, outside 4116 Wean Hall. This material is also "covered" in "On Numbers and Games" by Conway and "Winning Ways" by Berelekamp, Guy, and Conway.
- Oct 23: Midterm exam
- Oct 25: Geography
- Oct 30: More Geography (Handout: Undirected Edge Geography, by Fraenkel, Scheinerman and Ullman)
- Nov 1: One-Dimensional Peg Solitare [Moore and Epstein paper [PS]. Additional notes for the lecture by A. Frieze [PS]
- Nov 6: Two person zero sum games [Ferguson Part II, PDF]
- Nov 8: Bimatrix games, Nash Equilibria [Ferguson Part III, PDF]
- Nov 13: The Game of Hex and the Brouwer Fixed-Point Theorem [PDF] (a paper by David Gale from the 1979 American Mathematical Monthly)
- Nov 15: Strategies for the Shannon Switching Game [Notes by Richard Mansfield, PDF]
- Nov 20: The 15-puzzle and generalizations [Article from the American Math Monthly, PDF]
- Nov 22: Who wins Misere Hex? [Proof by Lagarias and Sleator, PDF]
- Nov 27: Permutation puzzles, and a Discussion of Homework 4
- Nov 29: Algorithms for solving permutation groups (Furst et. al. handout)
- Dec 4: How to simulate dice with coins. (Although not the definitive source, this paper defines the problem and lists references: PS)
- Dec 6: Impartial (Green) Hackenbush [Notes by A. N. Walker, PDF]
- Dec 11: Final Exam
Lecture Notes: Here's a directory containing all the lecture notes we've accumulated.
Optional Homework Assignments:
We recommend that you do these assignments and turn them in. This will help you learn the material, and engage in class discussions about the problems. We'll do quick checks of your solutions, but not nuanced grading.
- Assignment 1 Due September 6.
- Assignment 2 Due September 25.
- Assignment 3 Due October 11.
- Assignment 4 Due November 27.
Related Links:
- David Epstein's Combinatorial Game Theory page.
- Selected Bibliography of Combinatorial Games by Aviezri Fraenkel [ps]
Daniel Sleator Last modified: Tue Mar 25 18:31:15 EDT 2008