Optimal Play in Hex on Finite and Infinite Boards

Abstract

The game of Hex is one of the most celebrated connection games in combinatorics. Although it is known that the first player always has a winning strategy, very little is understood about the complexity of optimal play. Following Campbell's introduction of the parameters $\lambda (n)$ and $\delta (n)$, measuring respectively the length of the shortest guaranteed winning path and the minimum number of stones required by the first player to force a win, we establish new structural properties of these quantities. Our main result determines the exact value \[ λ(5)=7, \] thereby confirming one of Campbell's conjectures. We also show that the corresponding problem on the infinite strip $5\times \infty$ has a markedly different behavior. In this setting we prove that \[ λ(5\times\infty)=5, \] which is strictly smaller than $\lambda (5)$. To the best of our knowledge, this paper provides the first solution to one of Campbell's 2004 conjectures and answers a question posed by Stromquist (2006) in the affirmative. Furthermore, it uncovers a fundamental distinction between finite and infinite boards, offering new insights into the nature of optimal winning strategies in Hex.

14 pages and 19 figures