Difference between revisions of "Hex theory"

From HexWiki
Jump to: navigation, search
m (Copied/adapted page from http://hexwiki.tk)
(14 intermediate revisions by 8 users not shown)
Line 1: Line 1:
Unlike many other games, it is possible to say certain things about [[Hex]], with absolute certainty. While, for example, 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 argument can show that the [[second player]] certainly does not have a winning strategy from the [[starting position]] (when the [[Swap rule|swap option]] is not used). Whether this makes Hex a better game is of course debatable, but many find this attribute charming.
+
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:
  
* The game can not end in a [[draw]]. ([http://www.cs.ualberta.ca/~javhar/hex/hex-nodraw.html Proofs] on Javhar's page)
+
== Winning Strategy ==
* The [[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]] ==
 +
 +
* 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 the [[virtual connection]]s is PSPACE-complete. Reference [http://www.fmi.uni-stuttgart.de/szs/publications/info/kiefersn.Kie03.shtml here]
 +
 +
== 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]]

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:

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