Hex theory - Revision history

Alcalyn: /* Winning strategy for non-square boards */ typo

2024-06-06T21:23:51Z

‎Winning strategy for non-square boards: typo

Selinger: /* External links */ Fixed Maarup's link

2024-05-14T02:23:10Z

‎External links: Fixed Maarup's link

Selinger: /* No winning strategy for Blue */ Renamed as: Winning strategy for Red

2024-04-26T02:19:12Z

‎No winning strategy for Blue: Renamed as: Winning strategy for Red

Selinger: Fixed convention.

2023-01-25T14:43:02Z

Fixed convention.

Selinger: /* Winning strategy for non-square boards */ More copy-editing.

2022-07-10T21:04:44Z

‎Winning strategy for non-square boards: More copy-editing.

Selinger: /* Winning strategy for non-square boards */ Replaced the proof by an easier one (and using less jargon).

2022-07-10T16:07:15Z

‎Winning strategy for non-square boards: Replaced the proof by an easier one (and using less jargon).

Selinger: Some copy-editing.

2022-07-10T15:39:53Z

Some copy-editing.

Selinger: /* Winning strategy for non-square boards */ Replaced the proof by a more concise one.

2021-02-02T01:32:57Z

‎Winning strategy for non-square boards: Replaced the proof by a more concise one.

Tompo1: /* Winning strategy for non-square boards */

2021-01-23T12:09:14Z

‎Winning strategy for non-square boards

Tompo1: /* Winning strategy for non-square boards */ Fixed proof error - connection symmetry is only for groups within one of the triangles

2021-01-22T19:45:50Z

‎Winning strategy for non-square boards: Fixed proof error - connection symmetry is only for groups within one of the triangles

@@ Line 35: / Line 35: @@
              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 Bluej: 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:
+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"

@@ Line 89: / Line 89: @@
 * 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.
-* 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]]

@@ Line 19: / Line 19: @@
 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 (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.

@@ Line 27: / Line 27: @@
 === 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. Divide the board into two triangles as shown.
 <hexboard size="6x5"

@@ Line 28: / Line 28: @@
 Consider a board of size ''(n+1)'' × ''n''.
-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"
@@ Line 36: / Line 35: @@
              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 Bluej: 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:
-Now 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"
@@ Line 55: / Line 53: @@
              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.
+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.
-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).
+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.
-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.
+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).
 For symmetric reasons, Red has a winning strategy when ''n'' < ''m''.
-See [[parallelogram boards]] for an analysis of how much headstart the player with the larger distance needs to win, for different non-square boards.
+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 ==

@@ 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.
 == 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.
-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 ===
-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 ===
@@ Line 48: / Line 56: @@
 See [[parallelogram boards]] for an analysis of how much headstart the player with the larger distance needs to win, for different non-square boards.
 == Complexity ==

@@ Line 23: / Line 23: @@
 <hexboard size="6x5"
    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
@@ Line 28: / Line 29: @@
    />
-Now whenever Red plays in the red triangle, Blue responds by playing in the cell of the same number in the blue triangle, and vice versa. After filling all of the cells in this way, Red cannot have a winning path as outlined below.
+Now whenever Red plays in the pink triangle, Blue responds by playing in the cell of the same number in the blue triangle, and vice versa. 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. Let the "top component" be the set of all cells in the pink triangle that are occupied by a red stone and connected, by a path ''entirely within the pink triangle'', to the top edge. Let the "pink diagonal" be the set of pink cells that are adjacent to the blue triangle. It is easy to see that there exists some cell on the pink diagonal that belongs to the top component (for example, consider the first time Red's winning path, starting from the top edge, leaves the pink triangle). Let ''X'' be the bottom-most cell on the pink diagonal that belongs to the top component. Let ''Y'' be the cell immediately below and to the right of ''X''. Note that the cells ''X'' and ''Y'' are labelled with the same number, so ''Y'' is occupied by a blue stone. Since ''X'' is connected to the top edge by a path of red stones entirely within the pink triangle, by symmetry, ''Y'' is connected to the right edge by a path of blue stones entirely within the blue triangle. We consider two cases. If ''X'' is the bottom-most cell of the pink triangle, then ''Y'' touches the left edge. This gives a winning path for Blue, contradicting the existence of a winning path for Red. Otherwise, let ''Z'' be the cell immediately below and to the left of ''X''. Since ''X'' was the bottom-most cell of the top component on the pink diagonal, ''Z'' must be occupied by a blue stone, and must be connected, by a path entirely within the pink triangle, to the left edge (for example, such a path can be constructed by following along the perimeter of the top component). Since ''Y'' is connected to the right edge, ''Z'' is connected to the left edge, and ''Y'' and ''Z'' are adjacent to each other, this gives a winning path for Blue, contradicting the existence of a winning path for Red and finishing the proof.
-−
-Assume for a contradiction that Red does have a winning path, then let R be a minimal subset of the Red piece positions that connects the Red edges (i.e. no subset of R connects the Red edges) and set all other cells to Blue.  It can be shown that R is a chain of connected cells ''{r(1),r(2),...,r(k)}'' with ''r(1)'' on the top row, ''r(k)'' on the bottom row and ''r(i)'' adjacent to ''r(i+1)'' for ''0<i<k''.
-−
-Let ''r(j)'' be the first cell of this chain in the blue triangle above, then ''r(j-1)'' is in the red triangle and must be in the 9 o'clock direction from ''r(j)'' because the cell in the 11 o'clock direction has the same number label as ''r(j)'', and so must be Blue.
-−
-<hexboard size="3x2"
-  coords="none"
-  edges="none"
-  visible="area(b1,a2,a3,b2)"
-  contents="R arrow(12):a2 j:b2 B j:b1 arrow(2):a3 S red:(b1 a2) blue:(b2 a3) "/>
-−
-Now ''{r(1),r(2),...,r(j-1)}'' lies entirely within the red triangle, and so the cells in the blue triangle with corresponding labels ''{b(1),b(2),...,b(j-1)}'' must all be Blue and form a connected chain from the right edge to ''b(j-1)'' since the adjacency relationships are the same within the 2 triangles, and so ''{r(1),r(2),...,r(j-1),b(j-1),b(j-2),...,b(2),b(1)}'' forms a connected chain from the top edge to the right edge.  Notice that ''{r(j),r(j+1),...,r(k)}'' cannot contain any of the cells ''{r(1),r(2),...,r(j-1)}'' by minimality of R (so intuitively ''r(j)'' is cut off from bottom edge giving a contradiction as we shall show). Also ''r(1)'' is the only Red cell on the top row, by minimality of R, so if we set the cells ''{r(1),r(2),...,r(j-1)}'' to Blue, this produces a chain of Blue pieces entirely within the red triangle connecting ''r(j-1)'' to the left edge via ''{r(1),r(2),...,r(j-1)}'' and the top row, and does not alter the  Red chain ''{r(j),r(j+1),...,r(k)}'', which is assumed to connect ''r(j)'' to the bottom edge.
 <hexboard size="6x5"
    coords="none"
    contents="S red:all blue:area(a6,e6,e2)
-             B arrow(8):c3 arrow(2):c4
+             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
-             R arrow(6):d3 "
+            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
    />
 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 [[passing|pass]] (or in case passing is not permitted, Blue can move anywhere).

@@ Line 40: / Line 40: @@
    contents="R arrow(12):a2 j:b2 B j:b1 arrow(2):a3 S red:(b1 a2) blue:(b2 a3) "/>
-Now ''{r(1),r(2),...,r(j-1)}'' lies entirely within the red triangle, and so the cells in the blue triangle with corresponding labels ''{b(1),b(2),...,b(j-1)}'' must all be Blue and form a connected chain from the right edge to ''b(j-1)'' since the adjacency relationships are the same within the 2 triangles, and so ''{r(1),r(2),...,r(j-1),b(j-1),b(j-2),...,b(2),b(1)}'' forms a connected chain from the top edge to the right edge.  Notice that ''{r(j),r(j+1),...,r(k)}'' cannot contain any of the cells ''{b(1),b(2),...,b(j-1)}'' because they are Blue, or the cells ''{r(1),r(2),...,r(j-1)}'' by minimality of R, and so cannot connect ''r(j)'' to the bottom edge (although this may be difficult to prove).
+Now ''{r(1),r(2),...,r(j-1)}'' lies entirely within the red triangle, and so the cells in the blue triangle with corresponding labels ''{b(1),b(2),...,b(j-1)}'' must all be Blue and form a connected chain from the right edge to ''b(j-1)'' since the adjacency relationships are the same within the 2 triangles, and so ''{r(1),r(2),...,r(j-1),b(j-1),b(j-2),...,b(2),b(1)}'' forms a connected chain from the top edge to the right edge.  Notice that ''{r(j),r(j+1),...,r(k)}'' cannot contain any of the cells ''{r(1),r(2),...,r(j-1)}'' by minimality of R (so intuitively ''r(j)'' is cut off from bottom edge giving a contradiction as we shall show). Also ''r(1)'' is the only Red cell on the top row, by minimality of R, so if we set the cells ''{r(1),r(2),...,r(j-1)}'' to Blue, this produces a chain of Blue pieces entirely within the red triangle connecting ''r(j-1)'' to the left edge via ''{r(1),r(2),...,r(j-1)}'' and the top row, and does not alter the  Red chain ''{r(j),r(j+1),...,r(k)}'', which is assumed to connect ''r(j)'' to the bottom edge.
-Alternatively, (in a similar manner to the Gayle proof of no draws) we can consider the directed boundary between cells containing Red and Blue pieces beginning at the boundary between ''r(j-1)'' and ''b(j-1)'' (the arrowed pieces in the diagram) in the direction away from ''r(j)''.  The cells to the left bank of this directed boundary are all connected to ''b(j-1)'' and hence to the right edge.  The cells to the right bank of this directed boundary are ''{r(j-1),r(j-2),...}'', which are all within the red triangle.  If this directed boundary meets the left edge, this gives a connection from ''b(j-1)'' to the left edge, otherwise the directed boundary meets the top edge, and this gives a connection from ''b(j-1)'' to the cell on the top row to the immediate left of ''r(1)''.  However ''r(1)'' is the only Red cell on the top row, by minimality of R, so the Blue cell to its left, and hence also ''b(j-1)'', is connected to the left edge, giving the required contradiction.
+<hexboard size="6x5"
 This shows that Red cannot have a winning path, so Blue must have a winning path. ∎