MC19: Winning Mathematical Plays (J-term 1998)

Overview

We will study the mathematics of games or, combinatorial game theory, according to Chapters 1-8 of Volume I of Winning Ways and chapter 16 from volume 2 and supplementary readings. We will use this theory to find explicit winning strategies for many positions in a wide variety of playable games, including Hackenbush, Domineering, Nim, Dots-and-Boxes and Go.

Opportunities for future undergraduate research in combinatorial game theory will be discussed.

Prerequisites

High school algebra. Some understanding of recursive procedures (in programming) or proofs by induction (in mathematics).

Reaching me

In short, if my office door is open you are welcome; if I'm busy, we'll set up an appointment. Email and phone calls work, too.

World Wide Web

All course handouts will be available through my World Wide Web page, and some supplementary materials such as code to use as a starting point in assignments may be available there as well. The URL for this course is http://www.gac.edu/~wolfe/J-term/games-98.

Text and references

Our text for the course, Berlekamp, Conway, Guy, Winning Ways / for your mathematical plays, a superbly written book. We will cover Chapters 1-8 of Volume I and Chapter 16 of Volume II. We will also cover additional topics as time permits.

You may also wish to borrow a copy of my book, Mathematical Go, which has many of the mathematical facts presented in WW condensed into one chapter.

You will want to place the line


alias games ~wolfe/bin-`platform`/games

in your .cshrc file so that you can run my games program from any platform.

Honor

Collaborative work is highly encouraged in this course. However, write up solutions to homework assignments on your own, without reference to other students' solutions. You should also reference those students you worked with on a problem.

Any cheating may lead to failure in the course and notification of the Dean. This includes copying anyone else's work, deliberately facilitating copying and failing to give credit for solutions not discovered on your own. Failure to cite a source (written or verbal) on any component of the course is considered cheating.

Deliverables

A homework set is due most days.
A portfolio is due on Friday, January 30, consisting of problems composed by you. Each Monday I'll collect your portfolios, and you should have at least one additional problem in your portfolio. You may also recompose old problems to increase your grade. At the end of the course your portfolio should contain:
- A composed problem, and solution, from each of
  - Hackenbush
  - Dots & Boxes
  - Domineering
  - Another game of your choosing from Winning Ways, from class or from the literature.
  - A combinatorial game invented by you.
  Each problem should just be a game position. The goal is to figure who should win and what the winning move(s) are.
- One additional combinatorial game problem you design to stump me. You will tell me the rules to a combinatorial game at least two days before you try to stump me. (It could be a game from the book or one you invent.) You will present me with the problem and I will get about 10 minutes to think about the problem; I may choose to use the computer during this 10 minutes. (In general, I don't expect to think that long, nor do I expect to use the computer unless I suspect you have used it when composing the problem.) I will choose Left or Right, or 1st or 2nd, and you'll choose the other and then we'll play.
I may give exams on Friday, January 16 and Friday, January 30.

Grade

I expect that each of the three components in the deliverables will count equally; we'll discuss the specifics of your grade as the course progresses. If you have any concerns, please feel free to bring them up during the class. For problems in your portfolio, the following will serve as a rule of thumb for grading: If you prove a small theorem or have some original insight or the problem challenged me, you'll earn an A. A problem which requires understanding of non-trivial theorems from the book will typically earn at least a B.