MCS-344 Game Analysis, Spring 2003
Throughout the twentieth century, games have been used effectively to
popularize mathematics thanks to the efforts of authors such as Martin
Gardner, John Conway and Raymond Smullyan. Combinatorial game theory
is a rich and approachable unified theory, bridging recreational and
abstract mathematics, bringing fun to fundamentals. Unlike classical
game theory, the field of combinatorial game theory analyzes
two-player games of complete information where players take turns.
The prerequisites for the course are MCS-236,
MCS-220, or permission of instructor.
All office, phone and schedule information will be maintained on my
web page. I'll try to keep it updated with any
temporary changes to my schedule as well. 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.
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/344/.
Texts and references
Our required texts are:
Here are a few other references I recommend, and I have copies in my
office which I can loan you:
GONC and MGONC are compendiums of research results based on two
conferences held at MSRI (Mathematical Sciences Research Institute) in
Berkeley. ONAG predates WW and shows how games are a natural
generalization of transfinite mathematics.
Lastly, the following program is a toolkit you'll use to analyze games:
Students are encouraged to discuss the course, including issues raised
by the assignments. However, the solutions to homework assignments
should be individual original work unless otherwise specified. If an
assignment makes you realize you don't understand the material, ask a
fellow student a question designed to improve your understanding,
not one designed to get the assignment done. To do otherwise
is to cheat yourself out of understanding, as well as to be intolerably
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. Each citation should be specific: Do not merely
say, ``I worked with so-and-so on this homework set.'' Each problem
should have specific information spelling out the nature of the
collaboration, such as, ``On problem #3, so-and-so helped me to find
an algebra mistake.''
Assignments and Grading
If you get 80% or more of the points, you will earn an A, 75% for an
A-, 70% for a B+ and down by 5 percentage points each to the lowest
passing grade of 35% for a D. There is no curve. However, I reserve
the right to subjectively adjust your final grade. Please see me if
you have any question how you stand.
- (40%) A homework set is due every week or two. I may give exams in lieu
of homework sets about mid-year and toward the end of the year.
- (40%) A portfolio is due on Friday, May 16, consisting of problems
composed by you.
- (20%) Each student (or, with permission, pair of students) will give a
presentation on a combinatorial games research paper.
I expect each student to be actively engaged in the course. Late
assignments are not acceptable. Failure to start an assignment until
it's nearly due is also unacceptable. If you expect to need extra
time to complete an assignment, you should be able to articulate what
about the assignment is challenging (or what about your schedule is
problematic) at least a few days before the assignment is due.
Each student will compose problems and include them in a portfolio.
Every few weeks I'll collect your portfolios, at which time there
should be at least one additional problem in your portfolio until the
portfolio is complete. 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
Each problem should just be a game position. The goal is to figure
who should win and what the winning move(s) are. Solving one of
your problems should require knowledge of some mathematical theorem(s),
usually ones covered in the book. A particularly good problem might
require knowledge of a theorem you've discovered, or one which you
found in the literature.
- Dots & Boxes
- Clobber or Hackenbush
- Another game of your choosing from Winning Ways, from
class or from the literature.
- A combinatorial game invented by you. You'll describe the
rules, and propose a problem.
One of the five portfolio problems should be designed specifically
to stump me. If it's not a game covered in the course, you'll tell
me the rules to the 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.
Each student (or, if you prefer, pair of students) is expected to
report on a recent research topic in combinatorial game theory
not covered in the course. Two excellent references from which to
find research results are [GONC] and [MGONC].
The presentation should use Powerpoint and it should be polished and
clear. The talk should last from 15-30 minutes, and you should be
prepared to field questions. I hope that some students will want to
give their presentation early in the course so we can space the talks
out over the semester.
For content, I'll be looking for two elements in your talk:
- A description of research results as presented in one or two
- Some very minor extension or application of the research results
not mentioned in the paper. You could, for instance, design a
combinatorial game problem (as in the portfolio) which requires
techniques from the paper to solve.