A board that cannot be drawn

The board game Hex was invented by Piet Hein in Denmark in 1942 and again, independently, by John Nash at Princeton in 1948. It is played on a rhombus of hexagons, usually eleven on a side. Two players take turns to colour a cell. One tries to build a chain joining the top and bottom edges; the other tries to join left and right. There are no captures, and a cell, once coloured, stays that way.

Nash’s first observation, made while he was a graduate student, was that Hex cannot end in a draw. Fill in the whole board, however randomly, and one colour must have a chain. And it is impossible that both do. That statement is a theorem of plane topology in disguise, and it can be tested on small boards without much difficulty. In 1979 David Gale, who had played the game as a student with Nash, published a short paper showing that the no-draw theorem and Brouwer’s fixed-point theorem are equivalent, with each giving the other by a simple construction. So a board game holds one of the central theorems of topology, in a form that can be proved by a child walking along the edges of the cells.

All the colourings of a small board #

Exactly one colour wins on any full board. Testing it exhaustively is easy on small boards. For size $n$ there are $2^{n^2}$ colourings, and a search of connected components decides each. At the small sizes that can be enumerated, the result is always the same.

Of course the theorem must hold on all of those, or the game would be a different game. What this shows is that the statement is not just approximately true, or usually true. There are no exceptions among the 65,536 colourings of the four-by-four board, and half have each colour winning. The half is simple: reflecting the board in a diagonal swaps the two sets of sides, and swapping the colours as well turns a board into another board with the opposite winner.

The reason both cannot win is geometric. A chain joining top to bottom separates left from right, and it does so because of the Jordan curve theorem applied to a path on the board. Hexagons help here. Three hexagons meet at each corner, not four. On a board of squares, two diagonal chains can cross at a corner without sharing a cell. A curve of pixels needs two kinds of touching for exactly this reason. The hexagonal lattice has only one kind of touching, and so a chain of one colour really blocks the other.

A walk that cannot get stuck #

The reason neither can fail to win has a very pretty proof. Treat the top and bottom edges as coloured with the first colour, and the left and right edges with the second. Start at the top-left corner of the board, between the top edge (first colour) and the left edge (second colour). Now walk along the edges of the hexagons, keeping the first colour on the left and the second on the right.

At each corner of a hexagon three cells meet. The walk has come in along an edge between two of them, one of each colour, and the third cell ahead is one colour or the other. If it is the first colour then the walk bears right, and if it is the second it bears left. Either way, it goes on between a cell of each colour. So the next edge is forced, and the rule works in reverse too. Each corner of the mesh that the walk visits has exactly one edge in and one edge out. So the walk cannot return to a place it has been, except by retracing itself, and it cannot stop in the middle of the board. Therefore it must leave the board at another of its four corners, and in this case it must be a place where the colours on the two sides match the rule.

Only two corners qualify. If it ends at the top right, the second colour has been on its right all the way from the left edge to the right edge, so the cells along that side form a chain of the second colour, and that colour wins. If it ends at the bottom left, the first colour’s cells run from top to bottom. The figure’s walk takes 113 steps on the nine-by-nine board. Tested on many random boards, the end of the walk always agrees with the actual winner.

This is exactly the argument of Sperner’s lemma, with doors being the edges separating two colours and each room having at most two doors. It is one of those arguments that seems to need no mathematics, and yet it has a deep consequence: each step is forced in both directions, so a path that enters must eventually leave. The whole of the topology is the fact that three cells meet at a corner.

From a board to a fixed point #

Gale’s translation is a matter of small steps. Let $f$ be a continuous map from the unit square to itself. Choose a large $n$ and lay a board over the square. Colour each cell by comparing how far $f$ moves its centre in each direction: first colour if the vertical move is at least as large as the horizontal, second if the horizontal is larger.

Now suppose every point moves by at least some $\varepsilon$. Then in a cell of the first colour, the vertical move is at least $\varepsilon$, either up or down. Divide those into two kinds. A chain of the first colour runs from the bottom to the top of the square. At the bottom edge, nothing can move down out of the square; at the top, nothing can move up. So along the chain the vertical move starts upward and ends downward, and somewhere along it two adjacent cells have opposite signs of vertical move, each at least $\varepsilon$. For a fine enough board that violates continuity, since nearby points should not move in such different ways. So a contradiction follows, unless some cell moves by less than $\varepsilon$. That holds for every $\varepsilon$, and by compactness there is a point that does not move. That is Brouwer’s theorem for the square. The figure illustrates the map used here, and the point it marks moves by less than a thousandth on a finer grid.

The argument runs backwards as well. Assume Brouwer’s theorem and suppose a colouring had no winner. Then a continuous map can be built that moves every point in a direction read off from the colouring, with no fixed point. So each theorem implies the other. A proof of the fixed-point theorem, which usually needs homology, has been reduced to a walk.

This is also algorithmically useful, in a limited way. It gives one way to search for a fixed point: walk the boundary. What it costs to find the point that stays put shows that any such method has to take a number of evaluations exponential in the number of digits, in general. That is reflected here in the length of the walk, which can be a sizeable fraction of the cells on the board. And the map that offers a choice leads from the same theorem to Nash’s equilibrium, through Kakutani. So the man who noticed that Hex could not be drawn later used the corresponding fixed-point theorem to prove the existence of his equilibrium. Papadimitriou’s complexity class PPAD is defined by this very kind of walk, with each step forced and no way of shortcutting it.

Which boards keep the theorem #

The theorem depends on the shape of the board, as Brouwer’s depends on the shape of the disc. A fixed point can escape from a shape with a hole: a rotation of an annulus moves every point. A Hex board shows the same sensitivity directly. Roll the rhombus into a cylinder, gluing left to right. One player tries to join top to bottom, and the other tries to go around the cylinder in a closed loop. Exactly one of these still happens on a full board. The argument is a separation again: a closed loop around the cylinder separates the top from the bottom, and if no chain gets through, the boundary of what can be reached from the top is such a loop. So a cylinder has a theorem, though a different one.

Glue the other pair of sides as well, to make a torus, and it falls apart. A band around the torus in one direction no longer separates anything, since there is a way round in the other direction. The two colours can each have a closed loop of the same kind, running side by side, so “exactly one colour wins” has no meaning, and it is possible to colour a torus so that both colours have long loops and neither has the loop the other side would need. Hexagons still meet in threes, and the walk between the colours is still forced, but it can now close up on itself and return to its start without ever ending at a corner. That is precisely what Sperner’s lemma needs and does not have: an outside to walk out to. So the same local rule produces a global theorem only on a board that has the topology of a disc. The torus also has continuous maps with no fixed point, namely its rotations, and the two facts are one fact.

The first player wins, somehow #

Nash also gave the most famous non-constructive argument in game theory. Since the game cannot be drawn, one player must have a winning strategy. Suppose it were the second player. Then the first player could steal it: make an arbitrary first move, then pretend to be the second player, following the winning strategy. An extra cell of one’s own colour can never hurt, in a game where cells only help. If the strategy ever calls for the cell already taken, make another arbitrary move. That gives the first player a win, a contradiction. So the first player has a winning strategy on every board.

It says nothing about what the strategy is. So what can be computed?

Searching a small board completely is possible with a table of positions. The two-by-two board has two winning openings out of four. The three-by-three board has five of nine, and the four-by-four board has exactly four, those on the short diagonal, from a search over 612,569 positions up to the board’s own symmetry. It is not obvious that a move in the very centre is sometimes no better than one elsewhere. As the board grows, openings near the short diagonal are generally the strong ones and those near the acute corners are weak. Computer programs using a strong theory of connection have solved all openings up to a size of nine by nine and many of the ten by ten, and in practice the eleven-by-eleven board is unsolved. Stefan Reisch proved in 1981 that deciding who wins a general Hex position is PSPACE-complete, so there is no reason to expect a neat strategy to exist.

The first player’s advantage is so great that serious play uses the swap rule: after the first move, the second player may choose to take over that move and play on as if they had made it. This turns the theorem around, since the first player must now choose a move that is neither too strong nor too weak. Then it’s a fair contest, and the strategy-stealing argument gives a win to the second player instead. An impossibility proof gives no help at the board at all.

Claude Shannon built a machine that played Hex in the 1950s, using a network of resistors and measuring voltages to pick the cell at a saddle of the field. That is a surprisingly good heuristic, and it has been a common ingredient in strong programs since. Electrical resistance measures how many separate paths connect the two sides, and Hex is largely a matter of having more than one way to connect. It is a practical reading of the same idea behind Kirchhoff’s analysis of a graph’s spanning trees.

Random boards at the critical point #

Turn away from strategy and consider a random board, with half the cells of each colour. The no-draw theorem then has a surprising implication for probability. By symmetry, each colour has a chance of exactly a half of winning, on any size of board. That means the chance of a left–right chain of the second colour is exactly one half at every scale, however large. This is what being at a critical point means for the percolation model on the triangular lattice, in which each site is open with chance $p$. Above the critical point a long chain would exist with chance nearly 1, and below with chance nearly nothing. So $p_c = 1/2$ exactly, and this was proved by Harry Kesten in 1980 for the bond version on the square lattice and by others on the triangular lattice, with the self-matching property of hexagons playing the central role.

The chain length grows faster than the board size. In the figure, the average shortest winning chain grows from 5.3 at size 5 to 204.7 at size 140. The slope on a logarithmic plot is about 1.11. Computations have put the shortest-path exponent for critical percolation near 1.13, and the value here, from only a few hundred boards at each size and with no careful extrapolation, is close to that. It has no known exact value.

The exact theory here is one of the great results of the past twenty-five years. Stanislav Smirnov proved in 2001 that on this lattice the chance of a chain between two boundary arcs has a conformally invariant limit, as John Cardy had predicted by physical arguments. It was the first proof of such invariance for a lattice model. A key step in it uses precisely the walk with one colour on each side, whose scaling limit Oded Schramm had shown must be an SLE curve. The curves of the figures, the boundaries between colours, become in the limit a random fractal of dimension $7/4$. And all of that is a property of this particular lattice, where three cells meet at each corner. Those proofs have not been extended to the square lattice, where this walk is not forced.

Small boards tested, large boards quoted #

The no-draw theorem was tested exhaustively for boards up to four by four, and the proof above covers all sizes. The walk was run on many random boards, and each time it ended at the winner’s corner. The openings of small boards were solved exactly, and the solver identified the short diagonal as the set of winning first moves on the four-by-four board. The statements about larger boards, including the sizes solved by programs, are quoted from the literature, and no attempt was made to reproduce them.

The fixed point of the figure is computed for one smooth map, and a fine-grid search was used to report the small value, rather than the Hex-based construction. The figure is an illustration of the colouring, and the reduction to a chain is the argument in the text. The chain-length exponent is a slope from a small simulation at twelve sizes, and it should not be read as an estimate with any precision. The statements about percolation, Cardy’s formula, Smirnov’s theorem and SLE are all quoted.

Still open: a formula for the first move #

Is there any explicit winning strategy for Hex on a general $n \times n$ board? Nash’s proof shows that one exists, and PSPACE-completeness of general positions does not settle the question for an empty board, since an empty board is a very particular position. No pattern has been found in the winning first moves that holds beyond the small sizes solved. Whether the centre cell always wins is a natural conjecture, and it holds as far as anyone has computed, but it has no proof.

Then there is a more mathematical question. In what other settings does a theorem of this form hold? Gale himself gave a version in $d$ dimensions: a $d$-dimensional board with $d$ colours has exactly one winning colour in the analogous sense, and it is equivalent to Brouwer in $d$ dimensions. Whether the game is interesting in three dimensions, and whether strategy-stealing gives anything more specific there, has hardly been looked at. The same goes for the analogous statements on other kinds of tessellation that are not self-matching, where the no-draw theorem must be replaced by something else, and in those settings the critical probabilities are mostly not known exactly either.

Three cells at every corner #

A filled Hex board has one winner because walking between the colours is forced at every step: three cells meet at each corner, so there is one way in and one way out. The walk must end at a corner, and which corner reveals a chain along its side. That same walk proves Sperner’s lemma, and a colouring by which coordinate moves most turns a map of the square into a board, so the no-draw theorem and Brouwer’s theorem are the same statement in different clothes. Every board up to four by four has been tested in full, 65,536 colourings on the largest. On a random board the same fact forces criticality at one half.

And the game is unsolved. A theorem as non-constructive as stealing a strategy says the first player wins, and it stays silent about how. The players of the game have to find out each time.