Difference between revisions of "Hex theory"
From HexWiki
(reorganised: heading + inner links + external link + complexity + TODO) |
(→Complexity: added about the virtual connections being PSPACE complete) |
||
| Line 14: | Line 14: | ||
* The decision problem associated to generalised Hex is '''PSPACE-complete'''. | * The decision problem associated to generalised Hex is '''PSPACE-complete'''. | ||
* The detection of [[dominated cell]]s is NP-complete. ('''To be checked''' then sourced) | * The detection of [[dominated cell]]s is NP-complete. ('''To be checked''' then sourced) | ||
| + | * The detection of the [[virtual connection]]s is PSPACE-complete. Reference [http://www.fmi.uni-stuttgart.de/szs/publications/info/kiefersn.Kie03.shtml here] | ||
== Solving Hex == | == Solving Hex == | ||
Revision as of 22:15, 26 February 2009
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)
- The detection of the virtual connections is PSPACE-complete. Reference here
Solving Hex
- Hex has been solved on small boards.
- The game can not end in a draw. (Proofs on Javhar's page)
See also
External links
- Thomas Maarup masters thesis
