Difference between revisions of "Hex theory"

From HexWiki
Jump to: navigation, search
(Added some PSPACE-completeness proofs.)
m (Winning strategy for non-square boards: typo)
 
(22 intermediate revisions by 3 users not shown)
Line 1: Line 1:
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.
+
Unlike many other games, some things can be said 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:
+
This page discusses some of the known properties of Hex.
 +
 
 +
== No draw ==
 +
 
 +
''Main article: [[Draw]].''
 +
 
 +
When a Hex board has been completely filled with stones, one and only one player has connected their edges. The proof idea is quite simple. On a full Hex board, consider the set ''A'' of all red cells that are connected to Red's top edge. If this set contains a cell on Red's bottom edge, then Red is the winner. Otherwise, Blue has a winning path by going along the boundary of ''A''.
 +
 
 +
Links to more detailed proofs are on [[Jack van Rijswijck|Javhar]]'s page [http://javhar1.googlepages.com/hexcannotendinadraw "Hex cannot end in a draw"].
  
 
== Winning Strategy ==
 
== Winning Strategy ==
Line 9: Line 17:
 
* On non-square boards, i.e., boards of size ''n''×''m'', where ''n''≠''m'', the player with the shorter distance to cover has a [[winning strategy]] regardless of who starts.
 
* On non-square boards, i.e., boards of size ''n''×''m'', where ''n''≠''m'', the player with the shorter distance to cover has a [[winning strategy]] regardless of who starts.
  
These first and third statements are proved below. The second statement is a simply consequence of the swap rule: since Hex has no draws, each move is either winning or losing. If the opening move would be winning without the swap rule, the second player swaps and inherits the win. If the opening move would be losing, the second player declines to swap and goes on to win. Thus, the second player can always win.
+
The first and third of these statements are proved below. The second statement is a simple consequence of the swap rule: since Hex has no draws, each move is either winning or losing. If the first player's opening move would be winning without the swap rule, the second player swaps and inherits the win. If the opening move would be losing, the second player declines to swap and goes on to win. Thus, the second player can always win.
  
=== No winning strategy for Blue ===
+
=== Winning strategy for Red ===
  
In [http://en.wikipedia.org/wiki/Chess chess], while nobody seriously believes that black has a [[winning strategy]], nobody has been able to disprove it. On the other hand, in Hex, a simple strategy-stealing argument shows that the [[Blue (player)|second player]] cannot have a [[winning strategy]], and therefore the [[Red (player)|first player]] must have one.
+
In [http://en.wikipedia.org/wiki/Chess chess], while nobody seriously believes that Black (the second player) has a [[winning strategy]], nobody has been able to disprove it. On the other hand, in Hex, a simple strategy-stealing argument shows that the second player cannot have a [[winning strategy]], and therefore the first player must have one.
  
In fact, we can prove a more general statement: for boards of size ''n''×''n'', any position that is symmetric (i.e., invariant by reflection about the short or long diagonal and inverting the color of the pieces) is a winning position for the next player to move under optimal play. This follows from the fact that Hex is a monotone game: a position with additional pieces of a player's color is always at least as good for that player as the position without the additional pieces. If "passing" were allowed, it would therefore never be to a player's advantage to pass. If the second player to move had a winning strategy for a symmetric position, then the first player to move could simply steal that strategy by passing and therefore themselves becoming the second player to move. Since passing does not help the player, they also have a winning strategy without passing, contradicting the assumption that the other player was winning.
+
In fact, we can prove a more general statement: for boards of size ''n''×''n'', any position that is symmetric (i.e., invariant under reflection about the short or long diagonal and inverting the color of the pieces) is a winning position for the next player to move under optimal play. This follows from the fact that Hex is a monotone game: a position with additional pieces of a player's color is always at least as good for that player as the position without the additional pieces. If [[passing]] were allowed, it would therefore never be to a player's advantage to pass. If the second player to move had a winning strategy for a symmetric position, then the first player to move could simply steal that strategy by passing and therefore themselves becoming the second player to move. Since passing does not help the player, they also have a winning strategy without passing, contradicting the assumption that the other player was winning.
  
 
=== Winning strategy for non-square boards ===
 
=== Winning strategy for non-square boards ===
  
Consider a board of size ''(n+1)'' × ''n''.
+
Consider a board of size ''n'' × ''(n+1)''.
In this case, Blue has a shorter distance to cover than Red. Blue has the following second-player [[winning strategy]]. Divide the board into two triangles as shown.
+
In this case, Blue has a shorter distance to cover than Red. Divide the board into two triangles as shown.
 +
<hexboard size="6x5"
 +
  coords="none"
 +
  contents="S red:all blue:area(a6,e6,e2)
 +
            E 1:a1 2:b1 3:c1 4:d1 5:e1 6:a2 7:b2 8:c2 9:d2 10:a3 11:b3 12:c3 13:a4 14:b4 15:a5
 +
            E 1:e6 2:e5 3:e4 4:e3 5:e2 6:d6 7:d5 8:d4 9:d3 10:c6 11:c5 12:c4 13:b6 14:b5 15:a6"
 +
  />
 +
Consider the following [[pairing strategy]] for Blue: whenever Red plays in a numbered cell, Blue responds by playing in the other cell of the same number. After filling all of the cells in this way, Red cannot have a winning path. To see why, assume, for the sake of contradiction, that Red has a winning path. Consider a shortest such winning path from the top to the bottom edge, and consider the first point where the path crosses the boundary between the pink and blue triangles, for example as shown here:
 +
<hexboard size="6x5"
 +
  coords="none"
 +
  contents="S red:all blue:area(a6,e6,e2)
 +
            E 1:a1 2:b1 3:c1 4:d1 5:e1 6:a2 7:b2 8:c2 9:d2 10:a3 11:b3 12:c3 13:a4 14:b4 15:a5
 +
            E 1:e6 2:e5 3:e4 4:e3 5:e2 6:d6 7:d5 8:d4 9:d3 10:c6 11:c5 12:c4 13:b6 14:b5 15:a6
 +
            R 3:c1 8:c2 11:b3 14:b4 12:c4"
 +
  />
 +
Note that the crossing must happen in the horizontal direction, since any two cells straddling the boundary in the diagonal direction have the same number and therefore cannot both be occupied by Red.
 +
Since the red 14 is connected to the top by a red path within the pink triangle, by symmetry, the blue 14 is connected to the right by a blue path within the blue triangle:
 +
<hexboard size="6x5"
 +
  coords="none"
 +
  contents="S red:all blue:area(a6,e6,e2)
 +
            E 1:a1 2:b1 3:c1 4:d1 5:e1 6:a2 7:b2 8:c2 9:d2 10:a3 11:b3 12:c3 13:a4 14:b4 15:a5
 +
            E 1:e6 2:e5 3:e4 4:e3 5:e2 6:d6 7:d5 8:d4 9:d3 10:c6 11:c5 12:c4 13:b6 14:b5 15:a6
 +
            R 3:c1 8:c2 11:b3 14:b4 12:c4
 +
            B 3:e4 8:d4 11:c5 14:b5"
 +
  />
 +
This cuts off 12 from the bottom. Indeed, the potential connection from 12 to the bottom cannot cross the path of blue stones from 14 to the right. It also cannot cross the path of red stones from 14 to the top (because then the red path would cross itself, contradicting our assumption that it was shortest). Therefore, the red path is "trapped" in the upper right area, showing that there can be no winning path for Red. It follows that Blue's pairing strategy is a winning strategy.
  
[[Image: Non-square.png]]
+
Since Blue has a second-player winning strategy, it follows that Blue also has a first-player winning strategy, because an additional move at the beginning cannot hurt Blue.
  
Now whenever Red plays in the yellow triangle, Blue responds by playing in the cell of the same number in the green triangle, and vice versa. After filling all of the cells in this way, Red cannot have a winning path, for consider the bottom-most green cell that is adjacent to the yellow triangle and that is connected to Red's top edge. Then by symmetry, Blue has a connection from the same-numbered cell in the yellow triangle to Blue's right edge, blocking any possible connection by Red to the bottom edge.
+
An analogous strategy works for all boards of size ''n''×''m'' with ''n'' > ''m''. If the difference between ''n'' and ''m'' is greater than 1, Blue can simply ignore the additional rows, say at the bottom of the board, i.e., pretend that they have already been filled with red stones. If Red moves in the ignored area, Blue can [[passing|pass]] (or in case passing is not permitted, Blue can move anywhere).
 
+
An analogous strategy works for all boards of size ''n''×''m'' with ''n'' > ''m''. If the difference between ''n'' and ''m'' is greater than 1, Blue can simply ignore the additional rows, say at the bottom of the board, i.e., pretend that they have already been filled with Red pieces. If Red moves in the ignored area, Blue can play anywhere. If Blue's strategy later requires moving in a cell where Blue has already moved, Blue can again just move anywhere.
+
 
+
Since we showed that Blue has a second-player winning strategy, it follows that Blue also has a first-player winning strategy, since the additional move cannot hurt Blue.
+
  
 
For symmetric reasons, Red has a winning strategy when ''n'' < ''m''.
 
For symmetric reasons, Red has a winning strategy when ''n'' < ''m''.
  
== No draw ==
+
See [[parallelogram boards]] for an analysis of how much head start the player with the larger distance needs to win, for different non-square boards.
 
+
If a Hex board is full then there is one and only one player connecting their edges. See also [[draw]]. The proof idea is quite simple. On a full Hex board, consider the set ''A'' of all red cells that are connected to Red's top edge. If this set contains a cell on Red's bottom edge, then Red is the winner. Otherwise, Blue has a winning path by going along the boundary of ''A''.
+
 
+
Links to more detailed proofs are on [[Jack van Rijswijck|Javhar]]'s page [http://javhar1.googlepages.com/hexcannotendinadraw "Hex cannot end in a draw"].
+
  
 
== Complexity ==
 
== Complexity ==
Line 44: Line 69:
 
Several other related decision problems are also PSPACE-complete. For example:
 
Several other related decision problems are also PSPACE-complete. For example:
  
* The detection of [[virtual connection]]s is PSPACE-complete. Clearly, this problem is in PSPACE, since one can detect a virtual connection by exploring every possible sequence of moves within the given carrier set. The fact that it is PSPACE-hard follows from the PSPACE-hardness of detecting a winning position, since a board position is winning (for the second player) if and only if it is a virtual connection between the player's two edges.
+
* The detection of [[virtual connection]]s is PSPACE-complete. Clearly, this problem is in PSPACE, since one can decide the validity of a virtual connection by exploring every possible sequence of moves within the given carrier set. The fact that it is PSPACE-hard follows from the PSPACE-hardness of detecting a winning position, since a board position is winning (for the second player) if and only if it gives a virtual connection between the player's two edges.
 +
 
 +
* <p>The detection of [[dominated cell]]s is PSPACE-complete. More specifically, given a board size, a position on that board, a player to move, and two empty cells X and Y, the problem of deciding whether X dominates Y is PSPACE-complete. To see why it is in PSPACE, note that it is sufficient to check for each of X and Y whether it is a winning move for the player in question. X dominates Y if and only if X is a winning move or Y is not a winning move. For PSPACE-hardness, consider the following position on a board of size (''n''+2)×(''n''+2), where the cells marked "*" denote some arbitrary position of an ''n''×''n'' board:</p><p><hexboard size="6x6" contents="R c2 d2 e2 f2 a2 a3 a4 a5 a6 B a1 d1 e1 f1 b2 b3 b4 b5 b6 E *:c3 *:c4 *:c5 *:c6 *:d3 *:d4 *:d5 *:d6 *:e3 *:e4 *:e5 *:e6 *:f3 *:f4 *:f5 *:f6"/></p><p>For Red, the move at b1 is clearly winning, whereas the move at c1 is winning if and only if Red has a first-player win in the game marked "*". Therefore, b1 dominates c1. Moreover, c1 dominates b1 if and only if Red has a first-player winning strategy for "*". Moreover, b1 ''strictly'' dominates c1 if and only if Red has no such strategy. Since answering the latter question on the ''n''×''n'' board is PSPACE-hard, it follows that both domination and strict domination are PSPACE-hard problems.</p>
 +
 
 +
There are some computational problems in Hex that are easier than PSPACE.  
  
* <p>The detection of [[dominated cell]]s is PSPACE-complete. To see why it is in PSPACE, note that to determine whether one move dominates another, it is sufficient to make each move and to calculate whether the resulting position is winning. For PSPACE-hardness, consider the following position on a board of size (''n''+2)×(''n''+2), where the cells marked "*" denote some arbitrary position of an ''n''×''n'' board:</p><p><hexboard size="6x6" contents="R c2 d2 e2 f2 a2 a3 a4 a5 a6 B a1 d1 e1 f1 b2 b3 b4 b5 b6 E *:c3 *:c4 *:c5 *:c6 *:d3 *:d4 *:d5 *:d6 *:e3 *:e4 *:e5 *:e6 *:f3 *:f4 *:f5 *:f6"/></p><p>For Red, the move at b1 is clearly winning, whereas the move at b2 is winning if and only if Red has a first-player win in the game marked "*". Therefore, b1 dominates b2. Moreover, b2 dominates b1 if and only if Red has a first-player winning strategy for "*". Moreover, b1 ''strictly'' dominates b2 if and only if Red has no such strategy. Since answering this question on the ''n''×''n'' board is PSPACE-hard, it follows that both domination and strict domination are PSPACE-hard problems.</p>
+
* The problem of deciding whether a given cell is [[dead cell|dead]] is in co-NP. Equivalently, the problem of deciding whether a given cell is [[dead cell|alive]] is in NP.  This is because an empty cell is alive if and only if it belongs to some minimal winning path, relative to the given board position. Given such a path, it is checkable in polynomial time whether it is winning and minimal. [https://webdocs.cs.ualberta.ca/~hayward/papers/bergeParis.pdf Björnsson et al.] showed that recognizing alive nodes is NP-complete in the [[Shannon game]], a generalization of Hex. It is not known whether recognizing alive cells in Hex is also NP-complete or whether it is easier.
  
 
== Solving Hex ==
 
== Solving Hex ==
  
 
* Hex has been solved on [[small boards]].
 
* 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 ==
Line 61: Line 89:
 
* Stefan Reisch. [http://academic.timwylie.com/17CSCI4341/hex_acta.pdf Hex is PSPACE-complete], 1979.
 
* Stefan Reisch. [http://academic.timwylie.com/17CSCI4341/hex_acta.pdf Hex is PSPACE-complete], 1979.
 
* Stefan Kiefer. [https://web.archive.org/web/20070625134953/http://www.fmi.uni-stuttgart.de/szs/publications/info/kiefersn.Kie03.shtml Die Menge der virtuellen Verbindungen im Spiel Hex ist PSPACE-vollständig]. Studienarbeit Nr. 1887, Universität Stuttgart, Juli 2003. In German.  
 
* Stefan Kiefer. [https://web.archive.org/web/20070625134953/http://www.fmi.uni-stuttgart.de/szs/publications/info/kiefersn.Kie03.shtml Die Menge der virtuellen Verbindungen im Spiel Hex ist PSPACE-vollständig]. Studienarbeit Nr. 1887, Universität Stuttgart, Juli 2003. In German.  
* Thomas Maarup. [http://maarup.net/thomas/hex/ Hex]. Master's thesis, 2005.
+
* Thomas Maarup. [https://web.archive.org/web/20221014000841/https://maarup.net/thomas/hex/ Hex]. Master's thesis, 2005.
 +
* Yngvi Björnsson, Ryan Hayward, Michael Johanson, Jack Van Rijswijck. [https://webdocs.cs.ualberta.ca/~hayward/papers/bergeParis.pdf Dead cell analysis in Hex and the Shannon game]. Trends in Mathematics, pp.45–59, 2006.
  
 
[[category:Theory]]
 
[[category:Theory]]

Latest revision as of 21:23, 6 June 2024

Unlike many other games, some things can be said about Hex with absolute certainty. Whether this makes Hex a better game is of course debatable, but many find this attribute charming.

This page discusses some of the known properties of Hex.

No draw

Main article: Draw.

When a Hex board has been completely filled with stones, one and only one player has connected their edges. The proof idea is quite simple. On a full Hex board, consider the set A of all red cells that are connected to Red's top edge. If this set contains a cell on Red's bottom edge, then Red is the winner. Otherwise, Blue has a winning path by going along the boundary of A.

Links to more detailed proofs are on Javhar's page "Hex cannot end in a draw".

Winning Strategy

The first and third of these statements are proved below. The second statement is a simple consequence of the swap rule: since Hex has no draws, each move is either winning or losing. If the first player's opening move would be winning without the swap rule, the second player swaps and inherits the win. If the opening move would be losing, the second player declines to swap and goes on to win. Thus, the second player can always win.

Winning strategy for Red

In chess, while nobody seriously believes that Black (the second player) has a winning strategy, nobody has been able to disprove it. On the other hand, in Hex, a simple strategy-stealing argument shows that the second player cannot have a winning strategy, and therefore the first player must have one.

In fact, we can prove a more general statement: for boards of size n×n, any position that is symmetric (i.e., invariant under reflection about the short or long diagonal and inverting the color of the pieces) is a winning position for the next player to move under optimal play. This follows from the fact that Hex is a monotone game: a position with additional pieces of a player's color is always at least as good for that player as the position without the additional pieces. If passing were allowed, it would therefore never be to a player's advantage to pass. If the second player to move had a winning strategy for a symmetric position, then the first player to move could simply steal that strategy by passing and therefore themselves becoming the second player to move. Since passing does not help the player, they also have a winning strategy without passing, contradicting the assumption that the other player was winning.

Winning strategy for non-square boards

Consider a board of size n × (n+1). In this case, Blue has a shorter distance to cover than Red. Divide the board into two triangles as shown.

123456789510111294131412831514117215131061

Consider the following pairing strategy for Blue: whenever Red plays in a numbered cell, Blue responds by playing in the other cell of the same number. After filling all of the cells in this way, Red cannot have a winning path. To see why, assume, for the sake of contradiction, that Red has a winning path. Consider a shortest such winning path from the top to the bottom edge, and consider the first point where the path crosses the boundary between the pink and blue triangles, for example as shown here:

123456789510111294131412831514117215131061

Note that the crossing must happen in the horizontal direction, since any two cells straddling the boundary in the diagonal direction have the same number and therefore cannot both be occupied by Red. Since the red 14 is connected to the top by a red path within the pink triangle, by symmetry, the blue 14 is connected to the right by a blue path within the blue triangle:

123456789510111294131412831514117215131061

This cuts off 12 from the bottom. Indeed, the potential connection from 12 to the bottom cannot cross the path of blue stones from 14 to the right. It also cannot cross the path of red stones from 14 to the top (because then the red path would cross itself, contradicting our assumption that it was shortest). Therefore, the red path is "trapped" in the upper right area, showing that there can be no winning path for Red. It follows that Blue's pairing strategy is a winning strategy.

Since Blue has a second-player winning strategy, it follows that Blue also has a first-player winning strategy, because an additional move at the beginning cannot hurt Blue.

An analogous strategy works for all boards of size n×m with n > m. If the difference between n and m is greater than 1, Blue can simply ignore the additional rows, say at the bottom of the board, i.e., pretend that they have already been filled with red stones. If Red moves in the ignored area, Blue can pass (or in case passing is not permitted, Blue can move anywhere).

For symmetric reasons, Red has a winning strategy when n < m.

See parallelogram boards for an analysis of how much head start the player with the larger distance needs to win, for different non-square boards.

Complexity

  • The problem of determining the winner of a given Hex position (on a board of size n×n) is PSPACE-complete. The fact that it is a member of PSPACE is not surprising, because one can decide the winner by simply exploring the entire game tree, i.e., by playing every possible sequence of moves, which takes only a polynomial amount of memory. The fact that this decision problem is PSPACE-hard was first proved by Stefan Reisch in 1979.

Several other related decision problems are also PSPACE-complete. For example:

  • The detection of virtual connections is PSPACE-complete. Clearly, this problem is in PSPACE, since one can decide the validity of a virtual connection by exploring every possible sequence of moves within the given carrier set. The fact that it is PSPACE-hard follows from the PSPACE-hardness of detecting a winning position, since a board position is winning (for the second player) if and only if it gives a virtual connection between the player's two edges.
  • The detection of dominated cells is PSPACE-complete. More specifically, given a board size, a position on that board, a player to move, and two empty cells X and Y, the problem of deciding whether X dominates Y is PSPACE-complete. To see why it is in PSPACE, note that it is sufficient to check for each of X and Y whether it is a winning move for the player in question. X dominates Y if and only if X is a winning move or Y is not a winning move. For PSPACE-hardness, consider the following position on a board of size (n+2)×(n+2), where the cells marked "*" denote some arbitrary position of an n×n board:

    abcdef123456

    For Red, the move at b1 is clearly winning, whereas the move at c1 is winning if and only if Red has a first-player win in the game marked "*". Therefore, b1 dominates c1. Moreover, c1 dominates b1 if and only if Red has a first-player winning strategy for "*". Moreover, b1 strictly dominates c1 if and only if Red has no such strategy. Since answering the latter question on the n×n board is PSPACE-hard, it follows that both domination and strict domination are PSPACE-hard problems.

There are some computational problems in Hex that are easier than PSPACE.

  • The problem of deciding whether a given cell is dead is in co-NP. Equivalently, the problem of deciding whether a given cell is alive is in NP. This is because an empty cell is alive if and only if it belongs to some minimal winning path, relative to the given board position. Given such a path, it is checkable in polynomial time whether it is winning and minimal. Björnsson et al. showed that recognizing alive nodes is NP-complete in the Shannon game, a generalization of Hex. It is not known whether recognizing alive cells in Hex is also NP-complete or whether it is easier.

Solving Hex

See also

Open problems

External links