Hex against the computer

Play Hex online against the computer: connect your two sides of the board. There are no draws, and your side is proven to win — go find how. Free.

Rules and origins

Hex is a game with one of the shortest rule sets ever written and one of the longest histories of resisting computers.

The board is a rhombus of hexagons, 7×7 here. You play red and connect the top side to the bottom; the computer plays blue and connects the left side to the right. Players alternate, and the first move is always yours. A stone goes on any empty cell and then never moves and is never captured. Whoever first links his two sides with an unbroken chain of his own stones wins; the corner cells belong to both sides at once.

The game was invented twice. In 1942 the Dane Piet Hein published it in the newspaper Politiken under the name Polygon; in 1948 John Nash rediscovered it independently at Princeton, where it was simply called Nash. From 1952 Parker Brothers sold it as Hex, and that name stuck. The classic board is 11×11; 7×7 is the junior size, on which the whole mechanism already works at full strength.

Serious play uses the pie rule: the second player may take the first player's opening move for himself, which forces a deliberately modest start. This page does not use it — a simplification, and, as explained below, one that is entirely in your favour.

Two theorems

A draw is impossible. However the board is filled, exactly one player ends up connected. It sounds obvious and is not: in 1979 David Gale showed the statement is equivalent to Brouwer's fixed-point theorem, one of the central facts of topology. A game of Hex cannot end in nothing.

The first player has a winning strategy. Nash's 1949 proof is the strategy-stealing argument: if the second player could win, the first could make an arbitrary move and then play the second player's winning strategy — an extra stone in Hex never hurts. Contradiction, so the first player wins.

That proof has the property this page is built around: it is not constructive. It is known THAT the win exists; WHAT it looks like does not follow from the proof at all. Explicit strategies have been found by computers only for small boards: 7×7 is solved, and partial results reach roughly 10×10. For the tournament sizes 11×11 and 13×13 the winning strategy is still unknown to anyone.

An honest admission

The machine on this page does not know the winning strategy. More than that: we gave you the first move and removed the pie rule, which means we seated you in a provably winning position. By the theory you should never lose a single game — ever, against any play.

And yet the machine will beat most visitors. The gap between "a win exists" and "you can find it" is the whole plot of this page. The theorem hands you the victory; it does nothing to help you find it among tens of thousands of continuations.

The statistics under the board are therefore biased in your favour on purpose: every game starts from a position you have — on paper — already won. Whatever you lose, you lose not to the position but to the search.

How the machine looks for a move

By search with alpha-beta pruning, as in chess programs, but with an evaluation built for Hex. A position is judged by connectivity: for each side the shortest path is computed with Dijkstra's algorithm, where an own stone costs nothing to cross, an empty cell costs one move, and an enemy stone is impassable. The score is the difference of the two paths: whoever's path is shorter is closer to winning. Bridges get special treatment — pairs of own stones with two shared empty neighbours: such a link cannot be cut by a single move, and the machine counts it as nearly finished.

The levels differ in depth. Normal looks one move ahead and picks at random among the three best cells. Hard honestly searches two plies. Expert deepens as long as it fits into roughly a second and answers with the best move of the last completed depth.

In Hex, humans held their own against programs longer than in almost any classic game: connectivity refuses to decompose into the terms a search knows how to add up. Strong programs only appeared in the 2000s, with Monte-Carlo methods, and machines pulled decisively ahead in the neural-network era. What you are playing here is search plus connectivity: enough to punish inaccuracies, and not enough to know what the theorem knows.

Where to go from here