Hex no draws, a solver that knows

Take turns placing stones. Red moves first and wins by joining the top and bottom edges with a chain of red cells; Blue wins by joining left and right. A full board always has exactly one winner, so Hex can never be drawn. With hints on, every empty cell carries the solver's verdict for the player to move: green wins, red loses, and ? ran over the search budget.

board rule first move hints

first moves that win for Red

wins loses not solved · a red outline would mark a cell that disagrees with Fig. 2 of Hayward et al. (2003)

misère Hex: first moves that win

How the solver works

Hex has no draws, so a position's whole value is one bit: can the player to move force a win? The solver is a plain depth-first search over that bit with a transposition table, and a board that is the same after a 180° turn shares one entry. Each colour is kept as one small integer per row, so "which empty cells would finish a chain" takes two flood fills and a few shifts.

Two cheap rules do most of the pruning. If the opponent has two cells that would each finish their chain, you have lost: you can block only one. And if the opponent has a cell that would leave two such cells, you must answer inside that threat: on the cell itself or on one of the two it would create. A move anywhere else changes nothing there, and you can never finish first, because your chain would have to cross theirs. Every threat cuts the list of candidate moves, often to one or two cells.

The opening chart

The first-move results were computed under Node, one opening at a time, and compared cell by cell with Figure 2 of Hayward, Björnsson, Johanson, Kan, Po and van Rijswijck, Solving 7×7 Hex (Advances in Computer Games, 2004). The paper's first player is White and its boards are drawn as diamonds, so the figure was rotated onto this board before comparing. In misère Hex the player who joins their own sides loses; Lagarias and Sleator proved the first player then wins exactly when the board size is even.