Difference between revisions of "Hex theory"
(→Complexity: added about the virtual connections being PSPACE complete) |
|||
| Line 4: | Line 4: | ||
== Winning Strategy == | == Winning Strategy == | ||
| − | |||
| − | |||
* When the [[Swap rule|swap option]] is not used, the [[Red (player)|first player]] has a winning strategy. | * 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. | * 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 [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]]: | ||
| + | |||
| + | === No draw === | ||
| + | |||
| + | If a Hex board is full then there is one and only one player connecting their edges. See [[draw]]. | ||
== [[Complexity]] == | == [[Complexity]] == | ||
Revision as of 17:27, 22 March 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:
Contents
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
- 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
