Hex: a game with no middle ground
Build a connection, challenge the computer, and walk a coastline to discover why Hex can never end in a draw.
In Hex, two players take turns placing a stone in an empty hexagonal cell. Red connects the two red sides of the board; Blue connects the two blue sides. Stones connect through cells sharing an edge, and placed stones stay put. The first crossing wins.
Could both players block one another so completely that neither wins? Hex has no draws, even when a full board is coloured without any strategy. We will look for the mechanism behind that claim.
Connections and barriers
Explore the game below, including its Settings and Info panels. Red moves first; the practice game omits the optional swap rule. Corner cells belong to both adjacent sides, and count toward the goals of whichever colour occupies them. These conventions follow Chris Sangwin’s Hex rules.
Find your way across
A useful pattern is a bridge: two friendly stones that do not touch but share two empty neighboring cells. If the opponent takes one connecting cell, you can answer in the other. It is a potential connection rather than a completed chain; another threat might prevent your reply.
As you play, look for moves that extend your route while obstructing the opponent’s. That overlap between connection and defence hints at the no-draw result. The computer is a practice opponent with limited search; beating it or losing to it does not settle the general question.
Try to block both colours
Set turn-taking aside. Fill every cell Red or Blue, however you like. Can a collection of islands stop both crossings? Before following the coastline, predict which colour wins.
Walk the coastline
At the startEvery cell belongs to Red or Blue, shown by its stone. Click a cell to change its colour, then follow the boundary from Start at the top. The small outside stubs separate the four coloured shores.
The coastline cannot branch, stop inside, or get trapped in a loop. It leads to a winning chain.
Info
Click a coloured cell to switch its colour. Next step walks one coastline edge; Trace whole coast finishes it. Undo restores the previous board or step.
Walk the coastline examines arbitrary full colourings. They need not be reachable by alternating play, and a real game might have ended before such a board was filled. The stronger claim is that every full colouring contains a crossing.
A boundary that must go somewhere
Think of Red as land and Blue as water. The outside has four coloured shores: Red at upper-right and lower-left, Blue at upper-left and lower-right. The small corner stubs separate adjacent shores.
Start at the top stub, between the red upper-right shore and the blue upper-left shore. Follow edges with Red on one side and Blue on the other. The significant question is whether this walk can get stuck, branch, or loop forever.
At each ordinary junction, three regions meet. If they all have one colour, no coastline passes through. Otherwise, two are one colour and the third is the other: exactly two edges separate unlike colours. Arriving along one leaves precisely one continuation. The outside shores obey the same rule at boundary junctions.
Consequently, ordinary coastline vertices have degree two; only the four outside endpoints have degree one. A component containing an endpoint is a path, not a cycle. Joining a closed loop would require a third edge at a junction. Since the graph is finite, our walk must finish at another outside stub.
The exit reveals a crossing
Along each side of the walk, consecutive regions of a given colour either coincide or share an edge. The Red regions beside the walk therefore form a connected set, and so do the Blue regions, including their outside shores.
At the start, these sets touch the red upper-right and blue upper-left shores. Exiting at the left brings Red to its opposite shore; exiting at the right does the same for Blue. A bottom exit would connect both pairs. Every possible exit therefore produces at least one crossing of actual board cells. A full colouring cannot block both players.
Could both colours win? Their goal sides alternate around the rhombus, so two such crossings would have to intersect. Draw each chain through its cell centres. The adjacency edges form a planar triangular grid; an intersection would require a shared cell, which cannot have both colours. Thus the bottom exit is impossible, and a full board has exactly one winner.
The coastline experiment highlights a winning chain beside the completed walk. Its local continuation rule explains the result: three regions meet at a hexagonal junction. Four alternating squares could create a four-way junction instead, breaking this argument.
This is the interface proof presented by David Gale in The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly 86 (1979), 818–827.
A real game fills a new cell on every move. If no crossing has yet formed, an empty cell remains; once the board is full, the proof guarantees a winner. A game therefore cannot run out of moves with neither player connected.
A winning strategy without a recipe
The no-draw result leads to a second question: which player can force a win under perfect play? On an n × n board without the swap rule, the first player can. Nash’s strategy-stealing argument shows why.
A finite game with perfect information, no chance, and no draws gives one player a winning strategy. Suppose it were the second player.
The first player places an arbitrary extra stone, then imagines it absent. After the opponent’s reply, they borrow the supposed second-player strategy. Reflecting the square board exchanges the connection goals, allowing that strategy to serve the first player’s colour.
An extra friendly stone cannot destroy a connection. If the borrowed strategy requests a cell already occupied by an extra stone, count that stone as the prescribed move in the imagined game and place a new extra stone in any empty cell. The real position continues to contain every friendly stone required by the imagined strategy, and every opponent move remains legal there. If the real game ends sooner, the extra stones can only help the borrowed crossing.
The first player would win using this supposedly second-player strategy, contradicting its guarantee. Therefore the first player has a winning strategy.
The argument proves existence without finding the moves. Its arbitrary opening is part of a contradiction; it does not show that every opening wins. See Bert Enderton’s account for the same argument and further questions about Hex.