MCS-344 Game Analysis, Spring 2003

Overview

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.

Reaching me

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: 

   ~wolfe/bin/games

Honor

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 dishonorable.

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.

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.

Portfolio

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
  1. Domineering
  2. Dots & Boxes
  3. Clobber or Hackenbush
  4. Another game of your choosing from Winning Ways, from class or from the literature.
  5. A combinatorial game invented by you. You'll describe the rules, and propose a problem.
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.

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.

Powerpoint Presentation

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:

  1. A description of research results as presented in one or two published papers.
  2. 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.