Optimal winning strategies.

Author: Garikai Campbell [ profile | email ]

Despite the fact that no one is able to describe winning strategies for Hex(n) when n is large, one can still ask about optimal winning strategies. Here, we examine two possible measures of optimal winning strategies. In particular, we ask the following two questions:

Question 1: What is the shortest path with which player one can guarantee a win?

Question 2: What is the minimal number of moves player one must make to guarantee a win?

On Minimal Path Length winning strategies

To address the first question, we let Hex(n,l) denote 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. For example, the winning path in Figure 1 would constitute a win for blue in Hex(4,7) but not in Hex(4,5).

Figure 1. A 4 x 4 board containing a winning path for blue in Hex(4,7) but not in Hex(4,5).

Furthermore, if Figure 1 represents the state of the board during a Hex(4,5) game, play would continue since the Hex(4) winning path is not with a path of length less than or equal to 5 and since blue still has a chance of winning with such a path. However, since it is red's move next, the game should conclude in a draw on the very next turn. This illustrates that Hex(n,l) can end in a tie for some values of n and l, but note that because player one has a winning strategy for Hex(n), the second player can never have a winning strategy for Hex(n,l).

Now suppose we define (n) to be

(n) = min {l | player one has a winning strategy for Hex(n,l)}.

Question 1 is then equivalent to:

Question 3: What is the value of

(n)?

Unfortunately, for n large, computing (n) is almost certainly more difficult than finding a winning strategy. Therefore, instead of trying to calculate the value of (n) precisely, one can ask for bounds on (n). This task also proves to be quite challenging. In particular, it is trivial to see that (n) satisfies n≤ (n) ≤ n²/2 and (n)=n for n<4, but significantly improving these bounds appears to be far from trivial. In Minimal path length winning strategies, we prove:

Theorem 4:

(n)>n for all n≥ 4.

Note that it was known [GM3] as early as 1959 that

(4)≤ 5 and that

(5) ≤ 7. Together with the theorem, this implies that

(4)=5 and 6 ≤

(5) ≤ 7. It has also been known since that time that all but four opening moves for the first player result in a loss for that player in a game of Hex(4). (The proof of the theorem above and this figure outline all possible second player winning strategies for Hex(4).)

On Minimal Play winning strategies

Turning our attention to Question 2, we define the game Hex_d(n) to be the game of Hex(n) with the added constraint that player one must win by playing at most d counters and define

(n) to be

(n) = min { d | player one can guarantee a win at Hex_d(n) }.

Therefore, Question 2 is equivalent to:

Question 5: What is the value of

(n)?

This question is related to a more common measure called the depth of a game—the minimal number of total moves (made by both players) necessary to guarantee a win. The depth of Hex(n) is then 2(n)-1. As in the case for (n), it appears that (in general) computing (n) precisely is intractable. Therefore, one can again ask for the best possible nontrivial bounds on (n). We clearly have that (n) ≥ (n), but we can in fact say a bit more. In Minimal Play winning strategies, we prove:

Theorem 6: For all n,

(n) ≥ n+

n/4

Where to go from here?

Back to: Homepage for this topic [Abstract, ToC, References].
Who wins at Hex: A non-constructive answer.
How to win at Hex: the general story.
Minimal path length winning strategies.
Minimal play winning strategies.
Conjectures on 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.