home | topics | authors | contact

Conjectures on optimal winning strategies.

Author: Garikai Campbell [ profile | email ]
Recall that we define
(n) = min {l | player one has a winning strategy for Hex(n,l)}
and
(n) = min { d | player one can guarantee a win at Hexd(n) },
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 and Hexd(n) denotes the game of Hex(n) with the added constraint that player one must win by playing at most d counters.

We now state a few conjectures and pose a few challenges to the interested reader. First, after playing Hex(n) for various n, it seems to be the case that opening in tile [n/2, n/2] (or equivalently [n/2, n/2]) is the strongest opening move. In particular, we conjecture:

Conjecture 1: If '(n) equals the minimum l such that player one can guarantee a win in Hex(n,l) with an opening move in tile [n/2, n/2], then '(n)=(n).

Playing Hex(5) and Hex(6) (especially with the conjecture above in mind) we believe:

Conjecture 2: (5)=7 and (6)=9.

It is within reason to expect to resolve this conjecture by an argument similar to the one demonstrating that (4)>4 presented below. This is particularly true for showing (5)>6. Consider for example that this figure (right) implies that 4 of the 13 possible opening moves (modulo rotational symmetry) in Hex(5) admit a player two winning strategy. This leaves only 9 opening moves to consider, some of which are equally easy to dispose of. It would seem an ideal challenge for the committed student to try to dispose of these remaining opening moves. The case for (6) is of course more complicated, but again, perhaps not impossible by the methods employed here. In this case, more so than in the n=5 case, it might be more reasonable to write a computer program that helps in the endeavor. We similarly conjecture that:

Conjecture 3: (5)=7 and (6)=9.

As a result of this theorem, we have:

Theorem 4: (n)-n =.

Moreover, it seems reasonable to believe that both (n) and (n) are strictly increasing. More directly, it seems highly unlikely that player one can guarantee a win in Hex(n+1) with a path of length equal to (n) or by playing at most (n) counters. We have, however, been unsuccessful at proving:

Conjecture 5: For all n, (n+1) > (n) and (n+1)>(n).

One could imagine trying to prove this by induction. One approach would be to divide the board in the way described in the proof of this theorem. Unfortunately, this does not work as is evidenced by the fact that player one can guarantee a win with a path of length 4 on a 6 x 4 board (where player one has the shorter distance to span). In fact, we suspect that player one may be able to guarantee a win on an n x k board with a path of length k whenever n is sufficiently large. Similarly, we suspect that player one may be able to guarantee a win on an n x k board using at most (k) counters, where (k)<(k), whenever n is sufficiently large. (We remark that we owe thanks to the referee for pointing out a flaw in an argument which professed to prove that player one required at least (k) counters to guarantee a win on an n x k board.)

Alternatively, one could try to prove the conjecture above by induction using the standard n x n sub-board in much the way that this theorem is proved. In particular, in the case of (n), observe that in a game of Hex(n+1), we can prevent all winning paths on the standard n x n sub-board of length (n)-1 (by definition of (n)). Therefore, a minimal winning path in Hex(n+1) would necessarily have to contain tiles outside the standard n x n sub-board. But now, it seems plausible that player two could stop player one's paths that utilize these tiles that could be part of a minimal length winning path. However, all attempts to prove this have been unsuccessful.

Despite our inability to prove this conjecture and in light of Theorem 4 above, we suspect that perhaps (n)- n also tends to infinity as n tends to infinity. Much less clear is whether or not (n)/n or even (n+1)- (n) tends to infinity as n tends to infinity. It is similarly unclear which of these, if any, hold for (n). Finally, we ask one last question for which we have no reasonable conjecture. Namely, what is the growth rate of (n) relative to the growth rate of (n). These questions are summarized in the following (challenge) question:

Question 6: What are the following limits:
  1. (n)-n, (n)/n and (n+1)-(n);
  2. (n)/n and (n+1)-(n);
  3. (n)-(n) and (n)/(n)?

Where to go from here?

References

Back to Top
home | topics | authors | contact