home | topics | authors | contact

Who wins at Hex? A non-constructive answer.

Author: Garikai Campbell [ profile | email ]
Hein and Nash each proved independently that Hex cannot end in a tie and moreover, that there exists a first player winning strategy. There are several proofs of each of these facts. (See for example, [GD1], [GM3] or [SI1].) A particularly interesting fact, proved by David Gale [GD1] in 1979, is that the inability of Hex to end in a draw is equivalent to the Brouwer fixed point theorem.

Hex cannot end in a tie.

The proof we give below follows the ideas of a proof given by Jack van Rijswijck [VJ1].
Theorem: The Game of Hex cannot end in a tie.
Proof: This is the proof of this theorem......blah blah blah...... blah blah blah .... .

There exists a first player winning strategy.

Hex is an example of a two player, perfect information, symmetric game. This means that at any point in the game, each of the two players know all that there is to know and all moves available to one player would be available to the other player if it were his or her turn. It is also a game in which no "extra play" can ever be a disadvantage. All such games are susceptible to a strategy stealing argument. The proof below illustrates the ideas of strategy stealing.

Theorem: For any n, there exists a winning strategy for the first player in Hex(n).
Proof: As proved above, the game must end with a win for one of the players. Suppose the second player (red) has a winning strategy described by S.

But then, the first player (blue) could go anywhere and thereafter play according to red's winning strategy. More specifically, blue can label the first move X, ignore that first move, "pretend" that red's first move is in fact the first move of the game and respond as red would. If at any point in the game, blue should move in the position labelled X, then blue moves anywhere else, labels that move X and continues in the same way, following red's strategy. In particular, the extra play by blue never hurts and this effectively "steals" red's winning strategy.

But then this contradicts that the second player has a winning strategy. Therefore, the first player has a winning strategy.

It is important to note that this is not a constructive argument— based on this argument, you cannot say what the first player winning strategy is. For small n, it is a simple matter to work out first player winning strategies for Hex(n), but as n grows, this task quickly becomes quite difficult. For more on actual strategies, see How to win at Hex: the general story.
Back to Top

Where to go from here?

References

Back to Top
home | topics | authors | contact