Jeffrey Lagarias and Daniel Sleator. Who Wins Misère Hex appears as a chapter in The Mathemagician and Pied Puzzler: A Collection in Tribute to Martin Gardner. Elwyn Berlekamp and Tom Rodgers Ed., A, K. Peters, 1999
In Hex two players alternate placing black and white stones in the hexagons of a N x N rhombus-shaped board. White's goal is to form a path of white stones that connect the top and the bottom sides of the rhombus. Black's goal is to do the same with the left and right sides of the rhombus. When the board is filled with stones, there is a unique winner. A simple non-constructive proof shows that there is a winning strategy for the first player in Hex.Misère Hex is played just like Hex, except that the player forming a connecting path is the loser. We give a non-constructive proof that the first player has a winning strategy when N is even, and the 2nd player has a winning strategy when N is odd. More generally we prove that the losing player can force the board to be completely filled with stones before the game ends.
The following description resulted from an email exchange I had with a reader who found the proof confusing. I include it here in the hopes that it will help others. This should be read in the context of the fourth paragraph on page 239.Forbidden Cell Lemma: Suppose m(L)>0. Let player A be following the winning strategy, and player B be the other player. There can never be, at any point in the game, a forbidden cell for A -- that is an empty cell which if filled with an A-stone would cause A to lose immediately. Proof: Suppose at some point there were a forbidden cell. Then A's strategy thereafter cannot require A to move there. B likewise can avoid moving there, because since m(L)>0, there are always at least two choices for B, and B can simply choose not to move there. B ends up losing the game. In the final position B has lost, and the forbidden cell is empty. Adding an A-stone to the forbidden cell cannot change the outcome, because both players cannot lose. Therefore the forbidden cell was not forbidden after all. Q.E.D. Now we proceed to replace the argument in paragraph 4 on page 239. Assumptions at this point: P is the 2nd player. Q is the first player. There is a winning strategy L for P. m(L)>0. Under these assumptions, we'll give a winning strategy for Q. The real and imaginary games are described in the paper. We know that Q wins the imaginary game -- because Q is following L^R, the winning strategy in that game. All we have to show is that Q does not lose the real game at some point by virtue of having an extra stone in that game. (The real game can be obtained at any time from the imaginary game by adding a Q stone to it.) Let's apply the Forbidden Cell Lemma to the imaginary game. (Q is the winning player following the winning strategy in that game.) By the lemma, adding an extra Q stone to the position at any time cannot cause Q to lose immediately. (Recall that the real game is obtained from the imaginary game by adding a Q stone to it.) This proves that Q cannot ever lose the real game. Eventually P loses the imaginary game. Because his stones are the same in the real game, he also has lost the real game. Q.E.D. Note that we are using the property that when the board is filled with stones there is a unique winner. (Call this the unique winner property) It's used in the proof of the Forbidden Cell Lemma. (The monotonicity property in the paper depends on this too.) Also, notice how the proof breaks down if m(L)=0. In this case the extra Q stone in the real game could cause Q to prematurely lose that game. Only by virtue of m(L)>0 do we know that the extra Q stone cannot cause Q to lose the real game.