This course will present a number of combinatorial games and puzzles, focusing on those for which there exist mathematical techniques for solving them. (See the list of topics below for more information.)

Class meetings are on Tuesday and Thursday from 1:30 to 2:50 in Wean 4615A. The instructors are Danny Sleator and Alan Frieze

There is a class mailing list that will be used sprodically.
The address is *sleator+games@cs.cmu.edu*.

There is a blackboard site for this class, but it will be used only for recording of grades.

The grading for the class will be based on Homeowrks, a Midterm Exam, on a project, and on a final exam. Class participation is 15%, Homework is 30%, Midterm exam is 20% and the final/Project is 35%. 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.

- Midterm Exam: Due Thursday March 22nd in class
- Project proposals due: Thursday March 24th
- Final Exam: (We may not have a final)

Here are some topics that will probably be covered. Look for more details here later. Also see the web page for the previous incarnation of this course.

- Jan 11, Jan 13, Jan 18, Jan 20

Read: Basic Combinatorial Games -- updated February 8 (ps)

Also read sections 1 through 5 of Ferguson Part I (below).

Topics: Combinatorial Games, Sums of Games, Nim, Geography, Tic Tac Toe and Extensions

Notes on take away games by Brian Thompson and Steven Kieffer - Jan 25, Jan 27: Welter's game, animating functions, etc. Chapter 13 from ONAG and 472-480 from Winning Ways
- Feb 3, Theory of Combinatorial Games (Partizan games) notes
- Feb 8, Shannon Switching Game (See Basic Notes above).
- Feb 10, CG theory continued. Winning Ways Chapter 1 Winning Ways Chapter 2
- Feb 15, Computer Analysis of Sprouts ps
- Feb 17, Wythoff's Nim PDF
- Feb 22, Green Hackenbush Notes of A. N. Walker
- March 1-3, algorithms for permutation groups (Paper by Furst, et. al.)
- March 15-17, Two person zero sum games

See Ferguson's chapter below, and Alan Frieze's zero-sum-games lecture notes

Alan Frieze's duality lecture notes - March 22, Bimatrix games, Nash Equilibria (see last two pages of zero-sum lecture notes above)
- March 24, Midterm Exam discussion
- March 29, Poker --- Andrew Gilpin (the talk was emailed to you)
- March 31, April 5, Selfish Routing Roughgarden-Tardos paper Roughgarden Talk Frieze Slides
- April 7, The Hex Theorem, 1st player wins Hex, Who Wins Misere Hex, Mudcrack Y, and the Mudcrack Y Theorem
- April 12, Richman Games
- April 14th
- April 19th
- April 21st Coin Weighing Problems: coins, coins2, coincompet.pdf, maacoins.pdf
- ------------------Not Covered----------------------------
- More combinatorial game theory Winning Ways Chapter 3

Homework 1 Due January 20th in class.

Homework 2 Due February 4 in Wean 4128.

Homework 3 Due March 3 in class.

The exam is due Tuesday March 22, 2005, in class Here are the instructions:

Do any four of the five problems. Please work alone. Please do not consult any material outside of that supplied in the class. Please feel free to contact the instructors for clarification.

The following books have been put on reserve in the Engineering Library:

*Winning Ways Volume 1 -- Games in General*by Berlekamp, Conway, and Guy*Games of No Chance*Edited by R. J. Nowakowski.*More Games of No Chance*Edited by R. J. Nowakowski.*On Numbers and Games*by John H. Conway*Mathematical Go, Chilling Gets the Last Point*by Elwyn Berlekamp and David Wolfe

The following is the table of contents of Thomas Ferguson's on-line book on Game Theory. The entire text is available in PDF format in the links below.

- Introduction
- Part I: Impartial Combinatorial Games.
- Take-Away Games.
- The Game of Nim.
- Graph Games.
- Sums of Games.
- Coin Turning Games.
- Green Hackenbush.

- Part II: Two-person Zero-Sum Games.
- The Strategic Form of a Game.
- Matrix Games. Domination.
- The Principle of Indifference.
- Solving Finite Games.
- The Extensive Form of a Game.
- Recursive and Stochastic Games.

- Part III: Two-Person General-Sum Games.
- Bimatrix Games. Nash Equilibrium.
- The Noncooperative Theory. Safety Levels.
- Models of Duopoly.
- Cooperative Games.

- Part IV: Games in Coalitional Form.
- Many-Person TU Games.
- Imputations and the Core.
- The Shapley Value.
- The Nucleolus.

- Appendix.
- Utility Theory.
- Contraction Maps and Fixed Points.
- Existence of Equilibria in Finite Games.

David Epstein's Combinatorial Game Theory page.

Thane Plambeck's pages studies Misere games

Mathematical Games Home Page

Danny Sleator Last modified: Sat Apr 23 17:11:55 2005