MIT Combinatorics Seminar

Misere quotients for impartial games

Aaron Siegel  (Institute for Advanced Study)

Friday, April 13, 2007    4:15 pm    Room 2-136


In 1935, T. R. Dawson, the prolific composer of fairy chess problems, invented a little game now known as Dawson's Chess, involving only pawns on a 3xN chessboard. He invested considerable effort trying to find a perfect winning strategy, but was ultimately unsuccessful.

We now know that much of Dawson's difficulty arose from the winning condition he imposed on the game: whoever makes the last move loses. This is known as the misere play condition. The normal-play counterpart of Dawson's Chess---in which the player who makes the last move wins---was solved in 1956, but the original misere-play formulation remains an open problem, after more than seventy years.

This is no accident: games with the misere play condition tend to be vastly more difficult than games with the normal play condition (even when the rules are otherwise identical). As a result, many authors have dismissed the misere theory as essentially intractable.

However, a recent breakthrough, due to Thane Plambeck, has sparked renewed interest. Plambeck showed that much of the misere-play theory for a specific game G can be localized to a certain commutative monoid, the misere quotient of G. I will describe Plambeck's construction, and show how the misere quotient contains exactly enough information to recover a perfect winning strategy for G. Then I'll present misere quotients for several previously unsolved games and discuss what little we know about the general structure theory of misere quotients. Finally, I'll (hopefully) shed some light on just why no one has yet solved Dawson's Chess.