Difference between revisions of "Hex theory"
From HexWiki
m (added cat. theory) |
(reorganised: heading + inner links + external link + complexity + TODO) |
||
| Line 1: | Line 1: | ||
| − | Unlike many other games, it is possible to say certain things about [[Hex]], with absolute certainty. | + | Unlike many other games, it is possible to say certain things about '''[[Hex]]''', with absolute certainty. Whether this makes Hex a [[why did you start playing Hex|better game]] is of course debatable, but many find this attribute charming. |
The most important properties of Hex are the following: | The most important properties of Hex are the following: | ||
| − | + | == Winning Strategy == | |
| − | * | + | |
| − | * When playing with the | + | While nobody seriously believes that black has a winning strategy in [http://en.wikipedia.org/wiki/Chess chess], nobody has been able to prove that such a strategy doesn't exist. In Hex, on the other hand, a simple [[strategy-stealing argument|argument]] can show that the [[Blue (player)|second player]] certainly does not have a '''[[winning strategy]]''' from the [[starting position]]: |
| + | |||
| + | * When the [[Swap rule|swap option]] is not used, the [[Red (player)|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 cell]]s is NP-complete. ('''To be checked''' then sourced) | ||
| + | |||
| + | == Solving Hex == | ||
| + | |||
| + | * Hex has been solved on [[small boards]]. | ||
| + | * The game can not end in a [[draw]]. ([http://javhar1.googlepages.com/hexcannotendinadraw Proofs] on [[Jack van Rijswijck|Javhar]]'s page) | ||
== See also == | == See also == | ||
[[Open problems]] | [[Open problems]] | ||
| + | |||
| + | == External links == | ||
| + | |||
| + | * [[Thomas Maarup]] masters [http://maarup.net/thomas/hex/ thesis] | ||
[[category:Theory]] | [[category:Theory]] | ||
Revision as of 21:33, 3 December 2008
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
- 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
