Why the first player wins at Hex

Question

Hex is played on a rhombus-shaped board of hexagonal cells. One player, Red, owns two opposite sides and tries to connect them with an unbroken chain of red stones; Blue owns the other two sides and tries to connect those with blue stones. Players alternate placing one stone of their colour on any empty cell.

Take two facts as given: (1) when the board is full, exactly one player has a connecting chain, so the game can never be drawn; (2) having an extra stone of your own colour on the board can never make your position worse.

Prove that the first player has a winning strategy. Does the proof tell you what that strategy is?

Accepted Answer

The first player has a winning strategy. The proof is by "strategy stealing" and gives no hint of what the strategy actually is. The argument. Because the game cannot be drawn and is finite, one of the two players has a winning strategy (a rule that wins against every possible sequence of opposing moves). Suppose it is the second player. The first player, Red, then does the following. Red places an arbitrary first stone somewhere, and from then on ignores it, playing as though Red were the second player following the second player's winning strategy in response to Blue's moves. Whenever that …

Why the first player wins at Hex

Your answer

Discussion

Learn the concepts

Related questions