Hex theory

From HexWiki
Revision as of 21:33, 3 December 2008 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

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:

  • 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.

Complexity

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

Solving Hex

See also

Open problems

External links