Hex theory

From HexWiki
Revision as of 17:27, 22 March 2009 by Halladba (Talk | contribs)

Jump to: navigation, search

Unlike many other games, it is possible to say certain things about Hex, with absolute certainty. Whether this makes Hex a better game is of course debatable, but many find this attribute charming.

The most important properties of Hex are the following:

Winning Strategy

  • When the swap option is not used, the first player has a winning strategy.
  • When playing with the swap option, the second player has a winning strategy.

These two statements come from the fact that without swap, Blue has no winning strategy and from the fact that draws are impossible in Hex.

No winning strategy for Blue

While nobody seriously believes that black has a winning strategy in chess, nobody has been able to prove that such a strategy doesn't exist. In Hex, on the other hand, a simple argument can show that the second player certainly does not have a winning strategy from the starting position:

No draw

If a Hex board is full then there is one and only one player connecting their edges. See draw.

Complexity

  • The decision problem associated to generalised Hex is PSPACE-complete.
  • The detection of dominated cells is NP-complete. (To be checked then sourced)
  • The detection of the virtual connections is PSPACE-complete. Reference here

Solving Hex

See also

Open problems

External links