Hex: a game with no middle ground

A game can be easy to explain and hard to play. Hex needs only two colours and a board of hexagons: take turns claiming cells, and connect your two sides before your opponent connects theirs.

But there is a surprise hiding in the board. In tic-tac-toe, both players can block each other. In Hex, a draw is impossible. Even a board filled carelessly, with no strategy at all, must contain a winner.

Let’s play first, then find out what makes that promise unavoidable.

Two colours, two crossings

Our board is a rhombus made from hexagonal cells. Red aims from top to bottom; Blue aims from left to right.

Red moves first. Players alternate, placing one stone of their colour in an empty cell.
A placed stone stays there. There are no captures, and occupied cells cannot be played again.
Two stones are connected when their cells share a side. An interior cell has six neighbours.
Win as soon as a chain of your stones reaches both of your marked sides. The chain may turn, branch, or take a long detour.

The four corner cells touch both of their adjacent sides. A red stone in a corner can touch a red goal side; a blue stone there can touch a blue goal side. A corner does not join the players’ chains together.

These are the rules described on Chris Sangwin’s Hex page. There is also an optional swap rule: after seeing the opening stone, the second player may take the first player’s colour and sides, leaving the opening stone in place; the original first player then plays the other colour. This makes an overpowering opening less attractive. We leave swapping off in the practice games below, so you can concentrate on connections.

Try to make a crossing

Start on the 5 × 5 board. Click an empty cell to place your stone; the computer replies automatically. Red and Blue are also marked R and B, so the board can be read without relying on colour. A dashed line appears along a winning chain.

The computer always plays on Hard. It takes an immediate win, blocks an immediate losing threat, and otherwise searches many simulated continuations. Keep two possible routes alive and see how it responds. Its search is limited, so it is a practice opponent rather than a perfect player.

Choose Play first to open as Red, or Play second to let the computer open and play as Blue. Move to 7 × 7 when you want more room. Undo your turn takes back your move and the computer’s reply, letting you compare another idea.

A bridge is a promise

An unbroken chain is easy to see. A potential connection can be stronger than it looks.

For a concrete example, imagine Red stones at row 2, column 3 and row 3, column 4. They do not share a side, but they have two common neighbours: row 2, column 4 and row 3, column 3. If both are empty, Blue can occupy one and Red can answer in the other, joining the two stones.

This is a bridge. It is not yet a completed connection, and other threats may prevent you from answering. But it offers two ways across a gap instead of one. Try making one, then see whether you can preserve it when the computer attacks one of its connecting cells.

As you play, pause at a few moves:

Is this stone extending my route, blocking theirs, or doing both?
If they take the cell I need next, do I have another way around?
Am I defending an area that no longer helps me reach my sides?

The first question hints at the theorem. In Hex, a sufficiently complete barrier is itself a crossing.

Can we manufacture a draw?

Forget turn-taking for a moment. Fill every cell either Red or Blue, however you like. Perhaps a balanced pattern will stop both players. Perhaps a tangle of small islands will do it.

The next board lets you try. Click cells to change their colour. Shuffle colours makes another fully coloured board. Before tracing anything, predict the winner.

These colourings need not be reachable by alternating play, and they may contain a connection that would have ended a real game earlier. That is deliberate: we are testing a stronger claim, about every full two-colouring of the board.

A coastline detective story

Imagine the Red cells are land and the Blue cells are water. Give the outside of the board four coloured shores as well: Red above and below, Blue on the left and right. At each corner, a little boundary stub separates its two outside shores.

Our detective starts on the top-left stub, between the red top shore and the blue left shore. The only instruction is:

Walk along cell edges that have Red on one side and Blue on the other.

The detective does not get to choose a route. The board chooses it.

Why the walk cannot get stuck

At a junction, three regions meet. If all three have the same colour, no coastline passes through. Otherwise, two have one colour and the third has the other: exactly two edges separate different colours. Arrive along one, and exactly one remains to continue along. The outside shores give the same rule at boundary junctions.

Thus a coastline cannot branch or end inside the board. The four outside stubs are its only possible endpoints.

Could our detective walk forever around an island? Closed coastlines can exist, but this walk cannot join one. In the graph of coastline edges, every ordinary vertex has degree two, and each outside endpoint has degree one. A component containing an endpoint is a path, not a cycle: entering a cycle from elsewhere would require a junction with three coastline edges. Since the graph is finite, the path must reach another outside stub.

Why an exit gives a winner

Now watch the cells along either side of the walk. At each junction, the region of a given colour either stays the same or changes to a region sharing an edge with it. So the Red regions beside the walk form a connected set, and so do the Blue regions, including their outside shores.

At the start, those sets touch the red top and blue left shores. At every other possible exit, at least one reaches its opposite shore:

Exit	What the coastline has connected
Top-right	Blue’s left and right shores.
Bottom-left	Red’s top and bottom shores.
Bottom-right	Both pairs of shores would be connected.

A connection between opposite outside shores contains a chain of actual cells between the corresponding board edges. We have found a winner. No full colouring can stop both players. The editable board highlights a winning chain beside the completed walk.

There is one further fact: the bottom-right exit cannot actually occur. A top-to-bottom Red chain and a left-to-right Blue chain would have to cross inside the rhombus. Drawing each chain through its cell centres makes this precise: the adjacency edges form a planar triangular grid, so a crossing would require a shared cell. A cell cannot have both colours. Hence a full board has exactly one winner.

The coastline construction is an elementary interface proof; David Gale presents it in The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly 86 (1979), 818–827. The crucial local feature is that only three regions meet at a hexagonal junction. Four squares can meet in an alternating pattern, giving a four-way junction and breaking this argument.

From a full board to a finished game

The proof used a completely filled board. A real game usually ends earlier. Why does the proof still rule out a draw?

Each move fills a new cell, so a game on an n × n board has at most n² placement moves. If neither player has won, another empty cell can be played. If all cells have been played, the coastline proof guarantees that somebody has connected their sides. A game cannot run out of legal moves with no winner.

An unfinished position with no connection is therefore not a draw; it is simply still in progress.

Try the experiment once more. Make a board where Red seems completely blocked. Then trace the coastline and follow Blue’s chain. The obstruction you built for one colour has become the route for the other.

Why the first player can force a win

On an n × n board without the swap rule, the first player has a winning strategy. Here is Nash’s strategy-stealing argument.

A finite game with perfect information, no chance, and no draws gives one player a forced win under perfect play. Suppose it is the second player.

Let the first player place an arbitrary stone, then imagine it is absent. After the opponent replies, pretend to be the second player and follow that supposedly winning strategy. Reflecting the board exchanges the two connection goals, so the strategy applies to the first player’s colour too.

The extra stone cannot hurt: another friendly stone never destroys a connection. If the borrowed strategy asks for that occupied cell, count it as played in the imagined game and place a new extra stone in any empty cell. Continue; every opponent move stays legal in the imagined game. The stolen strategy must therefore win, contradicting the assumed second-player guarantee.

So the first player can force a win. The proof does not tell us how. Its arbitrary opening occurs inside a contradiction; it does not show that every opening wins.

See Bert Enderton’s explanation of this nonconstructive proof.