Hex (board Game) - Theory and Proofs

Theory and Proofs

Hex is a connection game, and can be classified as a Maker-Breaker game, a particular type of positional game.

John Nash proved in 1952 that a game of Hex cannot end in a tie, and that for a symmetric board there exists a winning strategy for the player who makes the first move (by the strategy-stealing argument). However, the argument is non-constructive: it only shows the existence of a winning strategy, without describing it explicitly. Finding an explicit strategy has been the main subject of research since then.

An explicit winning strategy with a pairing argument exists on non-symmetrical n×m boards, which leaves only symmetrical n×n boards as the center of interest.

In 1981, Stefan Reisch proved that generalized Hex on a n×n board is PSPACE-complete. In the computational complexity theory, it is widely conjectured that PSPACE-complete problems cannot be solved with efficient (polynomial) algorithms. This result limits the efficiency of the best possible algorithms when considering boards of arbitrary size, but it doesn't rule out the possibility of computing explicit strategies on small boards of a given size.

In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7×7. They extended the method to the 8×8 and 9×9 boards in 2003.

In 2009, Philip Henderson, Broderick Arneson and Ryan B. Hayward completed the analysis of the 8×8 board with a computer search, solving all the possible openings. The same team has solved most 9×9 openings, but some of them are still unknown.

The determinacy of Hex has other mathematical consequences: it can be used to prove the two-dimensional Brouwer fixed point theorem, as David Gale showed in 1979, and the determinacy of higher-dimensional variants proves the fixed-point theorem in general.