Who Wins Misère Hex

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

Full Text (PDF)

Abstract

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.

Comments

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.

Daniel Sleator: Email, Home Page, Papers
Last modified: Wed Nov 1 19:16:59 EST 2006