In 1948, in the common room of the Princeton mathematics building, where professors and students played chess and Go in the afternoons, John Nash presented a new game. The board is a rhombus covered with hexagonal cells, like a honeycomb. Two players, red and blue, take turns placing pieces, one at a time, on empty cells. The pieces never move. Red wants to form a chain of red pieces joining the top edge to the bottom one; blue, a blue chain joining the left edge to the right one.

His colleagues called the game “Nash”. He did not know that the Dane Piet Hein had invented it in 1942, under the name Polygon. In 1952 the company Parker Brothers released it under the name that stuck: Hex.

A 7 by 7 Hex board. Red has won: a chain of red cells, highlighted in yellow, joins the top and bottom edges.
A 7 by 7 Hex board. Red has won: a chain of red cells, highlighted in yellow, joins the top and bottom edges.Illustration by Euler’s Eyes

There is never a draw

The first surprising property: in Hex, a full board always has a winner. It is impossible to fill every cell without someone having formed their chain.

The intuition is this: to stop red from crossing from top to bottom, blue needs a “barrier” that cuts the board from side to side. And a barrier of blue cells going from one side to the other is exactly a winning blue chain. If red has not won, it is because blue has blocked red, and blocking is winning.

This depends on the cells being hexagons. On a board of squares, like a chessboard, two cells can touch only at a corner, and two paths of different colours can cross diagonally without either being completed. With hexagons, three cells meet at each vertex, and such a crossing is impossible. In 1979 the mathematician David Gale showed that the fact that Hex has no draws is equivalent to the Brouwer fixed-point theorem, the same kind of result that Nash would use for the equilibrium of games.

Strategy stealing

The second property is stranger still. Nash proved that the first player has a winning strategy: playing perfectly, they always win. But the proof does not say what that strategy is. The argument, known as strategy stealing, goes like this:

  1. The game is finite and has no draws. So one of the two players has a winning strategy: a rule that says what to play in each situation and guarantees victory against any defence.
  2. Suppose, for contradiction, that the player with the winning strategy is the second one.
  3. Then the first player can “steal” it. They make any first move and then pretend to be the second player, ignoring their extra piece and following the second player’s winning strategy.
  4. If at some point the strategy says to play on the cell where the extra piece already is, they simply play on any other cell, and that new piece becomes the extra piece.
  5. An extra piece on the board never hurts in Hex. So the first player, following the stolen strategy, wins.
  6. But this contradicts the assumption that the second player had a winning strategy. Hence the player with the winning strategy is the first one.
$$\boxed{\text{In Hex, the first player can always win.}}$$

It is an existence proof: it guarantees that the strategy exists, but does not show it. For boards up to 9 by 9, computers have found explicit winning strategies. For the standard 11 by 11 board, nobody knows what it is.

Exercise: on a 1 by 1 Hex board and on a 2 by 2 one, how does the first player win?

On the 1 by 1 board, the single cell touches all four edges: the first player wins with the first move. On the 2 by 2 board, if red moves first, the winning move is on one of the two cells at the obtuse corners of the rhombus: each of them touches both cells of the other row, and blue can occupy only one. On the next move, red completes the chain.

Exercise: does the strategy-stealing argument work for tic-tac-toe? And for chess?

In tic-tac-toe an extra piece also never hurts, and the argument shows that the second player cannot have a winning strategy. But tic-tac-toe can end in a draw, and with perfect play it does: the argument only guarantees that the first player does not lose. In chess the argument fails at the very start: an extra piece can hurt, because sometimes being obliged to move is a disadvantage, the so-called zugzwang.

Sources: David Gale, “The game of Hex and the Brouwer fixed-point theorem”, The American Mathematical Monthly 86 (1979) · Martin Gardner, “The game of Hex”, in Hexaflexagons and Other Mathematical Diversions (Chicago, 1988) · Sylvia Nasar, A Beautiful Mind (Simon & Schuster, 1998), ch. 11.

All topics on John Nash · ← The life of John Nash · The Nash equilibrium: nobody does better alone →

Image credits.