Hex Can't End in a Draw

The game of Hex has been invented in 1942 by Piet Hein, reinvented in 1948 by John Nash, got its name in 1952 from a commercial distribution by Parker Brothers, and has been popularized by Martin Gardner in 1957.

The game is played on a diamond shaped board with hexagonal cells and two pairs of opposite sides painted in two distinct colors, say, red and blue. Two players take turns putting chips down, one chip per a cell. One player plays with red chips, the other with blue chips. The goal of the "red chip" player is to connect the two red sides of the board with an uninterrupted chain of red chips. The other player pursues a similar goal with regard to the blue color.

Much is known about the game, even a winning strategy for small -- up to 9×9 -- boards. Simple as the game appears, no winning strategy has been discovered for bigger boards. The most important fact known about the game is that, unlike some other games, it can't end in a draw. One of the players is bound to win. In fact the first player can force a win. This was shown by John Nash in 1949 by what since became known as the strategy stealing argument.

The argument goes as follows. Assume there is a winning strategy for the second player. We are then going to show that the first player can utilize this same strategy to win the game. To make this work, the first player makes a very first move and, in a sense, forgets about it. He imagines now being a second player and, as such, playing the winning strategy on the board with an extra chip of his color. Note that the extra chip can do no harm to this player. If, in time, the winning strategy requires placing a chip in a cell occupied by the extra chip, the player puts a chip randomly elsewhere, and thinks of the latter as the (new) extra chip. Impersonating his rival and playing the latter's winning strategy will lead the first player to victory. Contradiction.

Thus in the game of Hex, the first player has an advantage. Different stratagems have been devised to minimize this advantage [Gardner, Browne]. However, it must be said, that the game is sufficiently complicated for a novice to make use of this advantage. A good second player will have no difficulty to consistently thrush a game opening novice. Do try playing the game. On- and offline games are freely available. Just search the web.

The goal of this page is to discuss the aforementioned fact: Hex can't end in a draw. If it could, it would be possible to fill out the board without there being a game resolving chain of either color. You can experiment with the applet below to convince yourself that there is always a game winning chain. (You can click on a cell to modify the color of the chip it contains.)

Along with the hexagonal board, the applet also allows experimenting with a similar game on a square board. This affords three distinct variants depending on the notion of connectedness that make two (now square) cells adjacent.

The diagram depicts the cells adjacent to the central square in gray. The variants based on the 4- and 8-connectedness do not lead to interesting games. In the 4c (for shortness) game, the draw is possible; in the 8c variant, the chains of different colors can cross without blocking each other.

The 6c variant is equivalent to playing the game on the standard hexagonal board. It is more convenient for arithmetization and subsequent analysis and programming of the game. Historically, this is exactly the variant John Nash came up with.

(The 4- and 8-square grids still provide some entertainment. Looking at the board that contains no 4-chain or two crossing 8-chains, can you tell at a glance how many clicks will it take to get a single winning chain of a selected color?)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Discussion

Let's then prove that Hex can't end in a draw. The result is not trivial. David Gale has even shown that the fact that Hex can't end in a draw is equivalent to Brouwer's Fixed Point theorem.

There is a proof by induction (D. Berman, Math. Magazine, Vol. 49, No. 2 (March, 1976), pp. 85-86), a proof based on a similar property of the Game of Y, and combinatorial topological proofs. Of the latter, there is quite a sample. Two short publications appeared in Math. Magazine as a readers' response to Berman's article (Vol. 49, No.3, p. 156). I quote them verbatim, with one modification. Following Berman, the authors fill the board with white and black hexagons, which I mechanically replaced with red and blue colors.

A letter by Paul B. Johnson, UCLA.

The article "Hex Must Have a Winner -- An Inductive Proof" (this Magazine, March 1976, pp. 85-86) reminded me of a topological proof which is perhaps somewhat shorter.

To fix our ideas, suppose blue wishes to connect the left and right sides of the board, and red wishes to connect the top and bottom. Let B be the set of blue hexagons connected to the left side. Clearly B either contains a blue hexagon on the right side or it does not. If it does, then blue has completed a chain. A chain connecting the two sides blocks red, who could not also have a chain without some hexagon being both blue and red. But, if B does not contain a hexagon on the right side of the board, the hexagons connected to B on the right are all red, are connected, and form a chain from top to bottom. Hence red won.

A letter by Daniel Zwillinger, MIT

I was appalled by the complexity of the 'simple' proof that Hex must have a winner. Here is a much simpler proof that I was told many years ago.

Imagine the playing board for the game of Hex to be made out of paper. Whenever red moves, he colors the hexagon of his choice red. Whenever blue moves, he cuts out the hexagon of his choice. Repeat this until no one can move any more.

Pick up the playing board in your hands, holding the two 'red' edges. Pull your hands apart. Either the paper stops you, in which case there must be a path of red squares and so red wins; or nothing stops you, in which case there is a 'path' of cut out squares between the top and the bottom of the board, and so blue wins.

Clearly, one of the two must occur; and so someone must win.

A similar argument has been used by Averbach and Chein (pp. 223-224):

... we must first see that the game cannot be drawn. Suppose a draw were possible, yielding a board that is completely filled, but no one has won. Imagine taking a pair of scissors and cutting out all cells on which a blue marker is found. Since red has not won, the board must separate into pieces so that no one piece contains cells from both the bottom and top of the board (otherwise the piece would contain a winning path for red.) Therefore, there must be a series of cuts that completely separates the top of the board from the bottom. These cuts must go from the left side of the board to the right side, and hence contain a winning path for blue.

In a lengthy discussion at the sci.math newsgroup a proof was offered by Brian Chandler that would probably make a math teacher gasp:

Imagine the board tipped up, so player A goes from top to bottom, player B from left to right. Suppose the board is actually two sheets of clear plastic, and two players have "stones" of white sugar (A) and red granite (B), and moreover these stones "plug" the hexagon cells (in the obvious way).

Now pour water in at the top. Either it dissolves through the sugar and reaches the bottom, in which case A has a path, or it doesn't, in which case there must be a continuous boundary of impervious granite, and B has a path.

(Does this help? I think it does (slightly) use some facts about the behaviour of liquids to help the imagination along.)

In a reply to Brian Jonathan Welton showed what is wrong with this kind of plausible reasoning (if something is to good to be true, it probably is):

Neither of the proofs (which are basically the same) posted so far is correct. Both would apparently conclude that a winning path would be formed on a squared board, whereas this is not the case - a squared board could end in a draw.

Later in the discussion, Arthur J. O'Dwyer came to Brian's defence:

Brian's proof assumes that the reader knows what a hexagon is; how many sides it has; and how it differs from a square. I don't see what you're objecting to.

... it *does* make use of the specific topology of the Hex board. If it didn't, then (as you noted) it would prove a falsehood. Since it does not prove a falsehood (which is impossible; falsehoods cannot be proven), it must use the topology of the board. Q.E.D.

The two proofs below appear to elaborate on the above reasoning. One by Anatole Beck [Beck, pp. 330-338], the other by David Gale [Gale, pp. 820-822]. Beck makes a reference to the profound Jordan Curve Theorem, which Gale shows to be unnecessary. I'll present a combination of the two.

Thus we assume that the board is completely covered with red and blue chips but there is no winning chain of either color. This assumption will lead to a contradiction.

Let D be a collection of all the red chips which can be joined by a chain to the left red edge of the board. D cannot be empty; for then all the cells adjacent to the left red edge must be blue. Such cells would form a blue chain joining the two blue edges of the board in contradiction with our assumption. Thus D is not empty.

Let D₀ be a collection of all the cells adjacent to D or to the left red edge of the board. D₀ consists entirely of blue chips; a red chip would have been included in D. As Beck puts it, "Now it is easy to see, but not so easy to prove, that D₀ contains" a winning blue chain. Some 6 pages later half a page prior to invoking the Jordan Curve Theorem he writes

At this point, I would like to be able to say that it is obvious that ... . It is so clear visually that I am tempted not even to mention that it requires a proof. One technique for disposing of such a problem is to make the assertion and precede it by the words "It is obvious that ..." This technique was forever ruined for me by my professor in college, a man of impeccable honesty and keen perception, who observed that the operational definition of "obvious" was "difficult or impossible to prove." I shall digress here to remark that in the intervening years, I have found it wise counsel when looking for the flaw in an argument, whether mathematical, political, economic, etc., to look first and hardest in the neighborhood of the word "obvious."

Now I shall quote from Gale's, making adjustments for the difference in notations and position of the board. (Gale considers a graph with vertices at the corners of all the board cells and the edges a set of all the sides of the cells. He then adds four vertices at the corners of the board u (left), u' (right), v (top), v' (bottom). These are not shown in the applet.)

We consider the edge graph G of the Hex board to which additional edges ending in vertices u, u', v, v' have been added to separate the four boundary regions. We now present an algorithm for finding a winning set on the completely marked board. We shall make a tour along G, starting with the vertex u and following the simple rule of always proceeding along an edge which is the common boundary of a red cell and a blue cell. Note that the edge at u has this property since it separates two regions of different color. The key observation is that this touring rule determines a unique path; for supposes one has proceeded along some edge e and arrived at a vertex w. Two of the three cells incident to w are those of which e is the common boundary, hence one contains red, the other blue chip. The third cell incident to w may contain either red or blue chip, but in either case there is exactly one edge e' which satisfies the touring rule.

... The proof depends now on the fact that our touring rule guarantees that we will never revisit any vertex. On the other hand, since there are only a finite number of vertices on the graph, the tour must terminate; but the only possible terminals are the vertices u', v, and v'... Now notice that each of these three vertices is incident to at least one of the right board regions. If, say, the terminal vertex is incident to the right red region, then the red player has a winning set; for clearly the set of red cells which are incident to our edge tour is a connected set and meets both red edges of the board.

Before concluding the section we wish to point out that the crucial feature of our algorithm is the italicized statement in the above paragraph which guarantees that the procedure cannot "cycle." In fact, the result which is the basis for all "fixed-point-chasing" algorithms is the following obvious fact from the graph theory:

Graph Lemma. A (finite) graph whose vertices have degree at most two is the union of disjoint subgraphs, each of which is either (I) an isolated vertex, (ii) a simple cycle, (iii) a simple path.

We will not insulted our reader's intelligence by presenting a proof of this simple fact but suggest that they take a few minutes to see how it goes. Induction on the number of edges is recommended. The connection with the Hex algorithm should be clear. If we consider only subgraph G' of G that separates cells with chips of different colors, then clearly the hypothesis of the Graph Lemma is satisfied and the conclusion shows that the component of G starting from u must end up of one of the other add-on vertices u', v, or, v'.

Let me only add that the path generated by Gale's algorithm is a part of the common border between Beck's D and D₀ collections.

Remark

A more recent theory of hypergraphs also applies to the game of Hex.

References

B. Averbach and O. Chein, Problem Solving Through Recreational Mathematics, Dover, 2000 from 1980 original
A. Beck, M.N. Bleicher, D. W. Crowe, Excursions into Mathematics, A K Peters, 2000
C. Browne, HEX Strategy, A K Peters, 2000
D. Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, Am Math Monthly, vol. 86, no, 10 (Dec., 1979), 818-827
M. Gardner, Hexaflexagons and Other Mathematical Diversions, The University of Chicago Press, 1988

The Hex and Y Games

71536574