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.
Read more about this topic: Hex (board Game)
Famous quotes containing the words theory and/or proofs:
“The weakness of the man who, when his theory works out into a flagrant contradiction of the facts, concludes “So much the worse for the facts: let them be altered,” instead of “So much the worse for my theory.””
—George Bernard Shaw (1856–1950)
“Would you convey my compliments to the purist who reads your proofs and tell him or her that I write in a sort of broken-down patois which is something like the way a Swiss waiter talks, and that when I split an infinitive, God damn it, I split it so it will stay split, and when I interrupt the velvety smoothness of my more or less literate syntax with a few sudden words of bar- room vernacular, that is done with the eyes wide open and the mind relaxed but attentive.”
—Raymond Chandler (1888–1959)