Is there a known winning strategy for the game of Hex?
competition/games/hex New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Is there a known winning strategy for the game of Hex? You have n^2 hexagons arranged in a rhombus, and O and X take turns to fill in one of the hexagons. The object is to get a line from one side of the board to the other---if the sides of the board are ABCD, then O is trying to link A and C, and X is linking B and D. It's quite tricky to show (but very believable) that precisely 1 player wins any given game. The analysis is easy for small boards. As n increases, it probably gets trickier, unless you know something I don't (i.e. a winning algorithm). Is anything known about the status of this game? Presumably there's complete solutions for lots of small n. But is there a known algorithm for winning? Because playing a move is never a disadvantage, I guess for any n it's a first player win by the remark that someone must have a winning algorithm, and the obvious player-1-mimics-player-2s-winning-strategy trick. But is there an algorithm known for general n? -- Kevin Buzzard <K.M.Buzzard@pmms.cam.ac.uk> [ Editor: the first line is the editor's; the rest is from Kevin Buzzard's mail to Brian Tung. ]
Show solution
Odd boards are a win for the first player by playing the center, then
playing the 180 degree opposite strategy. Other than that, however,
what you have summarized is about what is known about this game, as far
as I know. Most of what I know is contained in Martin Gardner's column
on the subject. (I forget the month---I could look it up if you need.)
Solutions for small n:
The case n=2 is trivial. Here's my solution for n=4.
The board:
2
a b c d
e f g h
1 1
i j k l
m n o p
2
Player 1 plays f, say. Player 1 then plays depending on Player 2's
play, according to the following table:
P 2 P 1 P 2 P 1 P 2 P 1 P 2 P 1
--- --- --- --- --- --- --- ---
a e g k TRIVIAL
h k TRIVIAL
l c b g TRIVIAL
d h TRIVIAL
h d TRIVIAL
X b TRIVIAL
X g TRIVIAL
e a g k TRIVIAL
h k TRIVIAL
l c b g TRIVIAL
d h TRIVIAL
h d TRIVIAL
X b TRIVIAL
X g TRIVIAL
g k a e TRIVIAL
e a TRIVIAL
l p TRIVIAL
X l TRIVIAL
h k a e TRIVIAL
e a TRIVIAL
l p TRIVIAL
X l TRIVIAL
l c b g TRIVIAL
d h TRIVIAL
h d TRIVIAL
X b TRIVIAL
X g TRIVIAL
X = any other move
TRIVIAL means remaining moves are trivial.
It might be possible to extend this strategy for all even n.
A correction, two days later:
Hex odd boards are not a first player win with the strategy I
suggested. (Otherwise, second player would just play along one of his
borders.)
Martin Gardner points out that in 4x4 Hex, all plays along the short
diagonal are winning first moves.
-- Brian Tung <brian@cs.ucla.edu>