The game of Hex was first described to public by polymath Piet Hein in 1942 under the name Polygon.
Principal idea
Piet Hein followed several principles to design the new game:
Fair: means both player shall have equal chance to win.
Progressive: game positions do not reappear.
Final: guarantee to have limited number of moves to end.
Comprehensible rules: beginners should be able to know how to play quickly.
Strategic: must be versatile in its possibilities for combination.
Decisive: never end with a draw.
First design
Piet Hein’s initial idea was a game in a quadrilateral board, where two players (like two groups of armies in battle field) each is assigned two opposite sides. Player alternately places their stones at square cells in the board. Player who joins its two sides by a line wins the game. Indeed, on a planar graph, the underlying topological property of Hex is also the basis of the four color theorem, which was proven in 1976. Piet Hein initially considered a board with square cells, but one could quickly realize that in such a game, undesired situation could happen,
Instead of square cells, in 1942, Piet Hein finished the game after seeing that the mutual-blocking problem can be solved if they are replaced with hexagonal cells. He chose 11x11 diamond board shape, and the design is complete.
Middle picture from: https://en.wikipedia.org/wiki/Hex_(board_game)
Reinvention by John Nash
Six years later, in 1948, John Nash at Princeton reinvented the game with the grid format where stones are placed at intersections, similar to the game of Go. David Gale soon converted it into a more natural hexagonal style.
Nash then proved by strategy stealing argument that, from the empty board, there exists a first player winning strategy. Yet theoretic value for each individual opening is unknown. As such, a swap rule is introduced, which says the second player has the option to steal the first player’s first move at the second player’s first turn (equivalent to swap colors).
Playing Hex is hard
Hex has extremely simple rules, but this does not make the game simple to play! Just watch a few games played by two strong computer Hex players, can you follow the strategies?
Visit Prof. Ryan Hayward’s homepage for more about the game of Hex.
Complexity aspects of Hex
Solving arbitrary Hex position is PSPACE-complete, since Hex is equivalent to Quantified SAT.
QSAT is a fundamental problem that is believed to be harder than NP-complete.
Computing Nash-equilibrium in general two-player zero-sum game is PPAD-complete
Mathematical aspects of Hex
Artificial Intelligence in Hex
Solving Hex
Playing Hex