Feature Column from the AMS

Combinatorial Games (Part II): Different Moves for Left and Right

2. Hex

Let us consider the game of Hex, which was invented by John Nash (1928- ) in 1948 independent of Piet Hein (1905-1996) who had also invented it in 1942 (and who is perhaps better known for his soma cube and super ellipse). The game became well known when Martin Gardner wrote about it in one of his Mathematical Games columns which appeared in Scientific American. Hex is played on a "rhombus" shaped board of hexagons. One pair of sides of the rhombus is associated with player Left and the other pair of sides with player Right. The players alternate playing white stones (Right) and black stones (Left) on the board. A 5 x 5 hex board is shown below:

The first player to make a chain of stones connecting that player's sides of the board wins. The diagram below shows a win for Right because there is a chain of white stones between the edges of the board associated with white.

This raises the following interesting question: When the board is filled with stones, must there be a chain of stones for one of the players? It turns out that the answer is yes. Thus, it is not possible for a game of Hex to end in a draw, that is, result in a position at the end of the game where neither player has won. The result follows from ideas in topology related to the Brauer fixed point theorem! You can try playing Hex here, but note the restriction, not in the usual rules, that one can not play in the center hexagon on this particular board!

Hex is an intriguing game, because although we know that there is a way for the first player to play the game which will guarantee a win, no one knows how to instruct the first player as to how to play to achieve this win. This fact with regard to Hex seems to have been established by John Nash, using an idea which has come to be known as "strategy stealing." Suppose that there is a winning strategy for the second player. What this means is that the second player has a way of winning, whatever the first player's first move. So, imagine the first player makes an arbitrary move and the second player responds by making move M. The first player pretends the board is empty and puts a stone in the (reflected) position corresponding to move M. The game proceeds with the first player imitating the second player's purported winning strategy. If this strategy requires that the first player put a stone where one of his/her stones already appears, then he/she can make any move, which can never do harm, only further contribute to forming a chain. Thus, the first player can win. This contradiction means that the assumption that the second player has a winning strategy can not be valid. This existence proof really is not of value in practical play because no one knows how the first player should play so as to guarantee the win that is known to exist!

Anatol Beck (University of Wisconsin) considered this intriguing variant of Hex: If the first player is known to have an advantage, perhaps it would be "fair" to allow the second player to specify a first move for the first player to make the game more "fair." Beck proved that if the second player chooses the cell to force the first player to move to, then the "forced" win is transferred to the second player. However, again, there is no known set of instructions which informs the second player how to achieve this forced win (for large boards)! The difficulty of determining a winning strategy for Hex is related to the fact that finding such a strategy is known to be P-Space Complete, which means that finding a solution which uses only a polynomial amount of space for keeping track of the solution is not likely.

Since the first player always wins in standard-play Hex, it is tempting to believe that in misère Hex (misère meaning that if you can not move you win) the second player always has a winning way to play. A recent result of Jeffrey Lagarias and Danny Sleator shows that this is not the case, thereby furthermore illustrating the unintuitive way that the misère version of the game compares with the standard play for that game.

Theorem:

The first player to move has a winning strategy for playing misère Hex on an n x n board when n is even and the second player to move has a winning strategy for playing misère Hex on an n x n board when n is odd.

The game of Hex has many relatives. Hex can be thought of as a special case of game on a graph known as the Shannon Switching game.