How to win at Hex: the general story.

Author: Garikai Campbell [ profile | email ]

One can prove that the first player can always win at Hex(n) for any n, but unfortunately the only known proof for general n is non-constructive. For small n, it is easy to work out a first player winning strategy. Figure 1 below illustrates how to win at Hex(4) and Hex(5), for example.

Figure 1. One possible strategy for winning at Hex(4) and Hex(5). The blue counter represents blue's first move. In each diagram, blue can force a win through that first move and through one of the dotted paths (by playing in a particular choice of the positions marked with a small red dot).

In fact, for all n< 7, Jack van Rijswijck [VJ1] has worked out not only all the winning first moves in Hex(n), but also how many moves it takes to win if both players are playing optimally, according to at least one definition of optimal play. Figure 4 illustrates one second player winning strategy when the first player does not play in one of the four winning opening moves. This strategy also illustrates the use of The Intersection Lemma.

For n=6, strategies begin to be challenging to describe, and for n≥ 7, the story is much more complicated. Jing Yang was first to find winning strategies for Hex(7) [YJ1],[YJ2] and seems to be the only person to have found winning strategies for Hex(8) and Hex(9) [YJ3].

We note that Hex can also be played on asymmetric, m x n, m ≠ n, boards as well. However, in this case, the player with the smaller side can always win and a winning strategy is quite easy to describe (see [GM3], for example).

Conventions and general theorems on how to win

We begin by establishing some conventions and proving a proposition central to Hex strategy.

We will reference a tile on the Hex board by an ordered pair indicating the tile's row number and column number as demonstrated in Figure 2 below.

Figure 2. The red counter is in tile [3,1], while the blue counter is in tile [4,3].

We formally define a path to be an ordered set of adjacent tiles, denoted P=. (Note that the length of the path P is m.) A path will be called complete if all of the tiles in the path are occupied by one player's counters and incomplete otherwise. To be clear, an incomplete path may contain tiles that are occupied by both players (in which case, the path can never be completed) or contain only tiles that are either unoccupied or occupied by one player's counters.

Now, suppose that during a game of Hex(n,l), it is blue's turn, but placement of a red counter in tile [b,r] would guarantee a win for red through the path P₁ or P₂ and placement of a red counter in tile [b',r'] would guarantee a win for red through the path Q₁ or Q₂. If R is the set of tiles

R =

then the only way blue can retain a chance at winning is by placing a counter in one of the tiles in R. For example, suppose we are faced with the board in Figure 3 during a game of Hex(4,4). If we let [b,r]=[3,2], [b',r']=[3,3], P₁ = {{ [1,4],[2,3],[3,2],[4,1] }}, P₂ ={{ [1,4],[2,3],[3,2],[4,2] }}, Q₁ = {{ [1,4],[2,3],[3,3],[4,2] }} and Q₂ = {{ [1,4],[2,3],[3,3],[4,3] }}, then we have precisely the condition described above.

Figure 3. Red is guaranteed a win in this game of Hex(4,4) if a blue counter is not placed in tile [4,2] on the next turn.

The principle above generalizes to the following:

The Intersection Lemma: Let n and l be fixed positive integers. Let T₁ and T₂ denote distinct sets of tiles or red edges. Suppose that during a game of Hex(n,l),

is a set of unoccupied tiles such that, given the current state of the Hex board, we have for each i, 1≤ i ≤ k:

is a set of incomplete paths from T₁ to T₂;
placement of a red counter in tile [b_i,r_i] S guarantees that red can complete one of the paths in the set .

Let R be the set of tiles defined by:

R =

If on the next turn, a blue counter is not placed in one of the tiles in R, then red can guarantee completing one of the paths P_ij connecting T₁ and T₂.

A Second Player winning strategy for Hex(4) (when the first player doesn't play correctly)

If the first player does not first play in a tile along the central axis (positions [i,j] with i+j=5) in Hex(4), then the second player can win. For example, if blue opens with a move in [4,2], then red can win by following the strategy outlined in the figure below.

Figure 4. A partial game tree showing that red can win in Hex(4) if blue first plays in [4,2].

Note that the two branches are sufficient because of The Intersection Lemma.

Where to go from here?

Back to: Homepage for this topic [Abstract, ToC, References].
A brief history of Hex.
Who wins at Hex: A non-constructive answer.
Optimal winning strategies.

References

[GM3] Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, volume 1, chapter: The Game of Hex, pages 73 — 83. Simon and Schuster, New York, NY, 1959.
[VJ1] Jack van Rijswijck, Hex opening theory.
[YJ1] Jin Yang, Simon Liao and Mirek Pawlak. A decomposition method for finding solution in game Hex 7x7. In International Conference on Application and Development of Computer Games in the 21^st Century, pages 96 — 111, November, 2001.
[YJ2] Jin Yang, Simon Liao and Mirek Pawlak. Another solution for Hex 7x7. Technical Reoprt, University of Manitoba, 2002.
[YJ3] Jin Yang. Jing Yang's Homepage.