home | topics | authors | contact

Minimal path length winning strategies.

Author: Garikai Campbell [ profile | email ]
Recall that we define (n) to be
(n) = min {l | player one has a winning strategy for Hex(n,l)},
where Hex(n,l) denotes the game of Hex(n) with the added constraint that player one wins only by constructing a path of length less than or equal to l. Here, we prove by induction on n that
Theorem 1: For all n≥ 4, (n)>n.

The basis step is long and involves several cases. Therefore, we present the proof of the induction step first.

Induction step

We define the n2 tiles, [i,j], on the (n+1) x (n+1) Hex board with i>1 and j<n+1 to be the standard n x n sub-board. The standard 4 x 4 sub-board is shown in Figure 1 below.

Figure 1. The 16 tiles of the standard 4 x 4 sub-board are marked green.

Theorem 2: If (n) > n, then (n+1) > n+1.
Proof: All Hex(n+1,n+1) winning paths for blue must either
  1. contain a Hex(n,n) winning path for blue through the standard n x n sub-board; or
  2. contain both [1,n] and [1, (n+1)].
We assume (n)>n and so red can prevent a winning Hex(n,n) path for blue on the standard n x n sub-board. Whenever blue plays on the sub-board, red can play according to the win-preventing strategy for Hex(n,n). Whenever blue first plays outside of the sub-board, red can play in one of the unoccupied tiles [1,n] or [1,n+1], thereby preventing any paths that must contain both. This then prevents a win for blue in Hex(n+1,n+1).

This, together with the basis step, proves Theorem 1. Together with this figure, we also (trivially) get the following two corollaries:

Corollary 3: (4)=5
Corollary 4: 6 ≤(5) ≤ 7

Basis step

NOTE: this has yet to be converted over completely and so looks a mess, but hopefully you get the idea.

First, observe that the Hex board has rotational symmetry and hence there are only n2/2 truly distinct first moves.

Figure 2. Tiles of the same color are equivalent first moves because of the rotational symmetry that exists in the board.

We now prove:

Theorem 5: (4)>4.
Proof: We divide the proof into cases based on where blue's first counter is placed. The set of distinct first moves (modulo symmetry) can be organized into four categories. These categories are shown in Figure 3 below.

Figure 3. Four categories of distinct first moves (modulo the existing rotational symmetry).

Category I:
Suppose blue is allowed to place counters in all the tiles of category I. Red can then move in position [2,3] as shown below: \begin{center} \includegraphics[width=2.5in]{low-hex4-5-1.jpg} \begin{quote} Figure 4. If blue places counters in all of the tiles in category I, red can respond by placing a counter in [2,3] and win at Hex(4). \end{quote} \end{center} Figure 4 also illustrates that once red makes this move:
  1. blue cannot then prevent a connection between this counter and the top red edge and
  2. if a red counter is placed in
    [3,2]:
    blue cannot prevent a connection between [2,3] and the bottom red edge through one of the paths: \[ P_1=\langle [2,3], [3,2], [4,1] \rangle \mbox{ or } P_2=\langle [2,3], [3,2], [4,2] \rangle. \]
    [3,4]:
    blue cannot prevent a connection between [2,3] and the bottom red edge though one of the paths: \[ \begin{array}{c} Q_1=\langle [2,3], [2,4], [3,4], [4,4] \rangle, \ \ Q_2=\langle [2,3], [2,4], [3,4], [4,3] \rangle, \\ Q_3=\langle [2,3], [3,3], [3,4], [4,4] \rangle \ \ \mbox{ or }\ \ Q_4=\langle [2,3], [3,3], [3,4], [4,3] \rangle. \end{array} \]
Therefore, by proposition~\ref{stop}, blue cannot prevent a connection between the top red edge and the bottom red edge through tile [2,3]. This proves that red can win at Hex(4) with blue opening in category I and hence, blue cannot win at Hex(4,4) with such a first move.

Note that since [3,3] is adjacent to [4,3], the path Q_4 above could have been replaced by Q_4' = \langle [2,3], [3,3], [4,3]\rangle. This situation occurs often in subsequent arguments, but we make the choice of writing the longer path to make it easier to produce figures which agree with the written paths.

Category II:
If blue first places a counter in [4,2], then red can place a counter in [4,1]. This immediately eliminates the possibility of any winning path of length 4 for blue containing a tile in positions [4,j], 1\leq j \leq 4. \begin{center} \includegraphics[width=2.75in]{low-hex4-off-1.jpg} \begin{quote} Figure 12. Blue's move, [4,2], red's response in tile, [4,1], and the resulting constriction of the board. \end{quote} \end{center}

Therefore, if red can create a path from the top red edge to any of the tiles in position [4,j], 1\leq j\leq 4, then blue cannot win with this opening move. This is equivalent to playing Hex on an (n-1) x n board (in this case with n=4) with red, the second player, having the smaller edge. As mentioned earlier, a second player winning strategy is known~\cite{MG2} for such asymmetric boards. Figure 13 below describes this strategy for the 3 x 4 board. In the figure, red need only play in the same color tile as blue.

\begin{center} \includegraphics[width=2.75in]{low-hex4-off-2.jpg} \begin{quote} Figure 13. Assuming play made as shown in Figure 12, no tile in the bottom row can be used by blue in a winning path for Hex(4,4). But then, if red plays in the same color tile as blue in the resulting 3 x 4 sub-board, red can prevent a win for blue. (Tiles [i,j] and [i',j'] in the 3 x 4 sub-board are colored the same if and only if i+j+i'+j'=9 and i-j-i'+j'=1.) \end{quote} \end{center}

This rules out blue being able to win by first moving in category II.

This is the only other first move (modulo symmetry) for blue which admits a second player winning strategy in Hex(4). The strategy outlined above is not sufficient to guarantee a win for red in Hex(4), but such a strategy is given in the appendix below.
Category III:
If blue first places a counter in tile [4,1], then red can respond by placing a counter in tile [3,2]. Now, if a red counter is placed in tile [2,1], then blue cannot prevent a connection between [3,2] and the top red edge through one of the paths: \[ \begin{array}{c} P_1 = \langle [3,2],[3,1],[2,1],[1,1] \rangle, \ \ P_2 = \langle [3,2],[2,2],[2,1],[1,1] \rangle, \ \ \\ P_3 = \langle [3,2],[3,1],[2,1],[1,2] \rangle \ \ \mbox{ or } \ \ P_4 = \langle [3,2],[2,2],[2,1],[1,2] \rangle. \end{array} \] Similarly, if a red counter is placed in tile [2,3], then blue cannot prevent a connection between [3,2] and the top red edge through one of the paths: \[ \begin{array}{c} Q_1 = \langle [3,2],[2,3],[1,3] \rangle\ \ \mbox{ or } \ \ Q_2 = \langle [3,2],[2,3],[1,4] \rangle. \end{array} \] \begin{center} \includegraphics[width=2.85in]{low-hex4-corner-1.jpg} \begin{quote} Figure 14. Blue's first move, [4,1], and red's response, [3,2], illustrating that red can guarantee a connection between [3,2] and the top red edge. \end{quote} \end{center}

Therefore, by proposition~\ref{stop}, blue cannot prevent a connection between [3,2] and the top red edge. This implies that in order for blue to create a winning path of length 4, it must contain the tile [4,1] and tiles from the set \{[4,2], [4,3], [4,4], [3,3], [3,4], [2,4]\}. Hence, if blue's second move is not [4,2], then red can move there and prevent a win for blue. Consequently, blue's second move must be to place a counter in [4,2]. \begin{center} \includegraphics[width=2.5in]{low-hex4-corner-2.jpg} \begin{quote} Figure 15. Blue's second move, [4,2], and red's response, [3,4], illustrating that red can prevent a win for blue. \end{quote} \end{center}

But then, red can prevent the creation of a blue path of length 4 containing [4,1] by placing a counter in [3,4] as shown above.

Category IV:
If blue first plays in position [3,2], red must respond by playing in tile [2,4]. Now, the board divides into three parts as shown in Figure 16. \begin{center} \includegraphics[width=2.5in]{low-hex4-best-1.jpg} \begin{quote} Figure 16. Blue's first move, [3,2], red's response, [2,4], and the resulting division of the board. \end{quote} \end{center}

The only way blue can win with a path of length 4 that ends in tile [3,4] or tile [4,4] is through tiles [i,j], i>2 (tiles marked purple or gray). The only way blue can win with a path of length 4 that ends in tile [1,4] is through tiles [i,j], i<3 or j=1 (tiles marked brown or gray). We now group tile [3,1] with the tiles [i,j], i<3 and call this group of tiles, group I. We exclude the tile [3,1] from the group of tiles [i,j], i>2 and call the resulting group of tiles, group II. This allows us to divide red's strategy for preventing blue from winning at Hex(4,4) into two distinct parts. Each time blue plays in one group of the board, red responds by playing in that same group as described below. Since a play by blue in [4,1] potentially effects the construction of a path through group I, we assume that blue has played in [4,1] when we outline red's groups I strategy. Likewise, since a play by blue in [3,1] potentially effects the construction of a path through group II, we assume that blue has played in [3,1] when we outline red's group II strategy.

Group I strategy:
If red places a counter in tile [1,4], then clearly blue could not complete a path using tiles only from group I. Therefore, blue must place a counter in that tile. Red must then respond by placing a counter in tile [2,3] as shown below. \begin{center} \includegraphics[width=2.5in]{low-hex4-best-1-a1.jpg} \begin{quote} Figure 17. Blue's first move, [1,4], in the set of group I tiles and red's response, [2,3]. \end{quote} \end{center}

It is clear that blue must place a counter in tile [1,3] and that red must then place a counter in tile [2,1] as shown in Figure 18. \begin{center} \includegraphics[width=2.5in]{low-hex4-best-1-a2.jpg} \begin{quote} Figure 18. Blue's second move, [1,3] in the set of group I tiles and red's response, [2,1]. \end{quote} \end{center}

Now, blue cannot prevent red from creating a path from tile [2,1] to the top red edge, nor from tile [2,1] to either tile [2,2] or tile [3,1]. But then blue cannot create a path of length 4 through the tiles in group I. Therefore, blue cannot create a path of length 4 containing tile [1,4].

Group II strategy:
If red places a counter in tile [3,3], then red can guarantee a path from [2,4] to the bottom red edge through the path P_1=\langle [2,4], [3,3], [4,2]\rangle or P_2 = \langle [2,4], [3,3], [4,3]\rangle. Similarly, if red places a counter in tile [3,4], then red can guarantee a path from [2,4] to the bottom red edge through the path Q_1=\langle [2,4], [3,4], [4,3]\rangle or Q_2 = \langle [2,4], [3,4], [4,4]\rangle. These paths are illustrated in Figure 19 below. \begin{center} \includegraphics[width=2.5in]{low-hex4-best-1-b1.jpg} \begin{quote} Figure 19. The paths which force the play of blue in tile [4,3]. \end{quote} \end{center}

If red creates such a path, then blue cannot create a winning path through the group II tiles. Therefore, by proposition~\ref{stop}, blue must place a counter in tile [4,3]. Then red can respond by placing a counter in tile [3,3] leaving the board in the state below. \begin{center} \includegraphics[width=2.5in]{low-hex4-best-1-b2.jpg} \begin{quote} Figure 20. Blue's first move, [4,3] in the set of group II tiles and red's response, [3,3]. \end{quote} \end{center}

But now, the only way blue can create a winning path is through paths containing both tiles [4,1] and [4,2]. After, blue's next turn, one of these must be left unoccupied and red can simply play in this unoccupied tile. Therefore, blue cannot create a winning path through the group II tiles and hence cannot create a winning path that contains the tiles [3,4] or [4,4]. This completes the proof that an opening play in tile [3,2] does not lead to a win for blue and so completes the proof that the first player has no winning strategy in Hex(4,4).

Where to go from here?

References

  • [PC1] Carl Pomerance, personal communication.
Back to Top
home | topics | authors | contact