16 Normat 55:1, 16–24 (2007)
Mathematics and Games, a case study: Hex
Jorge Nuno Silva
Dept. Matem ática - FCUL
Campo Grande, C6, Piso 2
P-1749-016 Lisboa
Portugal
jnsilva@cal.b erkeley.edu
The game Hex was invented twice. The first, by the Danish scientist and poet
Piet Hein, in 1942; the second, by the American mathematician John Nash, in
1948. However, it was Martin Gardner, in the pages of Scientific American, that
popularized it in the 1950s ([6]). Today Hex is becoming even more popular and
studied, there is already a full book on Hex, by Cameron Browne, who wrote later
about other games of the same family ([3; 4]).
Hex is a connection game, usually played in a board like this:
There are two players, White and Black. They alternate coloring one hexagon of
the board. White tries to build a connection between SW and NE banks, Black
connects SE to NW.
Nash’s e quivalent game is played on the intersections of a board like this:
Normat 1/2007 Jorge Nuno Silva 17
n
1
1
m
One player connects N-S, by droping colored counters, for example, the other E-W.
Usually the board is square (n=m).
The first striking fact about this game is that Hex cannot end in a draw. Suppose
we fill the board with white and black pieces, at random. Now think of the white
stones as water and the blacks as land. Then, either the water flows from SW to
NE, or there is a dam connecting SE to NW. In the latter case Black has won, in
the former White was the winner. There is no possibility of drawing, wich helps
making Hex an interesting game to play.
The above argument is intutive, of course, but the rigorous proof is not difficult.
The most well known proof is combinatorial (see, for example, [2]), but we present
one by induction on the dimension n × m of the board (we use Nash’s version of
the game). This proof deals with the general rectangular board, in the rest of the
paper we assume the board is s quare (n=m).
The result is clear for boards 1 × m, n × 1 and 2 × 2, so we suppose n, m > 3.
Our hypothesis will be that all boards smaller than n × m admit no draws. On a
board n × m let White connect W-E, and Black connect N-S. Assume the board
is completely filled with white and black stones. Consider the board n × (m 1)
that we get deleting the last column. This board size falls within our induction
hypothesis, therefore there is a black chain connecting N-S (and we are done) or
there is a white one, W
1
, c onnecting the first and the (m-1)th columns.
1
m1
Now let us delete the first column and apply the same argument. In the n ×(m1)
board, either Black connected N-S, and there is nothing else to prove, or White
buit a chain, W
2
, c onnecting the columns 2 and m.
18 Jorge Nuno Silva Normat 1/2007
m
2
If W
1
and W
2
are linked to each other, their union contains a chain W-E, so we
assume they are not.
A similar argument shows that there must exist a black chain, B
1
, connecting
rows 1 and n-1
1
n!1
and another, B
2
, linking columns 2 and n
n
2
Again, we may suppose these black chains do not touch each other.
Consider now the board (n 2) × (m 2) that we obtain deleting the first and
last rows and columns.
Normat 1/2007 Jorge Nuno Silva 19
By the induction hypothesis there is a white chain W connecting rows 2 and n-1
or a black chain B linking columns 2 and m-1 (notice that we changed orientation,
which is ok). Without loss of generality suppose such a W exists. Then W links
W
1
to W
2
and the pro of is complete.
n!1
m!1
2
2
As Hex has no draws, it must be a first player win or a s ec ond player win. Suppose
it is the second player who has a winning strategy. Then, the first player, in his
first move, plays at random and acts as if he were the second. An extra move, in a
connection game, can never hurt, therefore the first player is going to win, stealing
second’s winning plan. This is, of course, contradictory. We conclude that it is the
first player that has a winning strategy.
This argument was devised by John Nash and is known by strategy stealing
argument. It proves the existence of a strategy, but does not show it. Winning
strategies for the first player are e xplicitely known for small boards (up to 7 × 7).
For the usual size, 11 × 11, nobody found one yet.
As the first player is in advantage, there is a special rule for the beginning of the
game. The pie rule holds: on his first move, the s ec ond player can change colors
(using the move his adversary just did). This way the first player wont play too
strongly in his first move (playing in the smaller diagonal, for instance).
As this is a connection game, it is important to know how to extend a group. A
move to a neighbor cell seems too slow.
11
10
9
8
7
6
5
4
3
2
1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
Here the pieces in l7 and m7 are too close to each other, hardly being of any help
connecting the edges.
20 Jorge Nuno Silva Normat 1/2007
On the other hand, a big jump can be cut by the adversary:
11
10
9
8
7
6
5
4
3
2
1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
In this case, the pieces l7 and p7 can be effectively separated if White plays in n7.
An example of a good connection, not too far reaching, is a bridge, which consists
on having two stones that share two neighbor cells:
Here, if White tries to cut, playing l6, Black replies in m7, and if White plays in m7,
Black replies in l6. The two stones are as good as if they were already connected.
Defensive moves must also be well thought out. For instance, trying to block
an adversary group should not lead us to play too close to it, because then it can
extend eas ily:
Trying to block in k6 is met with a move in l7. Even at a bridge distance a block
is not effective:
Normat 1/2007 Jorge Nuno Silva 21
11
10
9
8
7
6
5
4
3
2
1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
1
2
If White takes j5, Black replies in k7. Good moves are to be found at a distance:
11
10
9
8
7
6
5
4
3
2
1
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
1
David Gale ([5]) found a surprising mathematical connection to the no draws res-
ult. He proved that it is equivalent to Brouwer’s fixed point theorem. This is an
advanced result in functional analysis, it asserts that under certain hypotheses, a
function f has a fixed p oint (ie, there is an x such that f(x) = x).
The rigorous version of this theorem we’ll use is the following:
Theorem of Brouwer. Let Z be a square in the plane (including boundaries) and
f : Z Z a continuous function. Then there is an x in Z with f (x) = x.
Let us see that this theorem is a consequence of our result on Hex. Let Z be a
square in the plane and suppose f : Z Z is continuous. For each (small) positive
d let W e be the set of points of the square f moves in the East direction at least
the distance d. Define W w, Bn, Bs in a similar way.
22 Jorge Nuno Silva Normat 1/2007
We’ll show now that these four sets we defined cannot be all of the square, no
matter how small d is. We use the Hex result for that. Suppose that, for some
d > 0 every point of the square Z is in at least one of W e, W w, Bn, Bs. Make
of the square a Hex field by drawing a fine mesh. Color each intersection White
or Black. As there are no draws, we may assume whichever color connects E-W
won. In the winning chain there must e xist consecutive (therefore very close to
each other, as the mesh is fine) intersections in different sets (W e and W w) which
means their images are far from each other, contradicting the continuity of f.
Therefore, for each d > 0, there is an x such that |f(x)x| < 2d. Taking a vanishing
sequence for d we get a sequence (x
n
) that must converge to some x Z, since Z
is closed and bounded. Such an x must satisfy f(x) = x.
To prove the reciprocal result we argue as follows: if there were ties in Hex we
could get a continuous function on a square of the plane with no fixed point. We
just summarize the main steps of the deduction, as they are somewhat technical.
Theorem. Brouwer’s fixed point theorem implies that there are no ties in Hex.
Proof. Suppose there is a position, with Nash’s board filled with pieces where
neither player won. Let Black connect E-W and White connect N-S. Call the board
B
n
.
Normat 1/2007 Jorge Nuno Silva 23
Let Z be the square of the plane with corners (1, 1), (n, n), and cover it with the
board mencioned above.
(n,n)
(1,1)
Let W
0
be the s et of black counters that are connected to the leftmost edge of
the board. Let E
0
be the set of all other Black’s counters. Define N
0
as the set of
White’s counters connected to the upper edge, S
0
the set of all other white counters.
Note that W
0
and E
0
have no adjacent counters (the same for N
0
and S
0
).
Define the function f on B
n
by
f(z) =
z + e
1
if z W
0
z e
1
if z E
0
z + e
2
if z S
0
z e
2
if z N
0
where e
1
= (1, 0), e
2
= (0, 1) are the usual unit vectors. The main facts are:
We can extend f to all of Z using the fact that each point of Z, z, falls is
a triangle of B
n
, of vertices x
1
, x
2
, x
3
, say. Then, as the triangle is convex,
z = λ
1
x
1
+ λ
2
x
2
+ λ
3
x
3
where all the λs are nonnegative and add up to 1.
We define f(z) = λ
1
f(x
1
) + λ
2
f(x
2
) + λ
3
f(x
3
).
Clearly this function is continuous.
The fact that f aplies Z in itself is a consequence of W
0
and E
0
(N
0
and S
0
)
not being contiguous.
The following lemma shows that f has no fixed points.
Lemma. Let z
1
, z
2
, z
3
be vertices of a riange in R
2
and let ˆρ be the simplicial
extension of the mapping defined by ρ(z
i
) = z
i
+ v
i
where the v
i
s are given
vectors. Then ˆρ has a fixed point if and only if 0 is in the convex hull of
v
1
, v
2
, v
3
.
We got a counterexample to Brouwer’s Theorem. Thus, our assumption ties are
possible in Hex must be dropped.
24 Jorge Nuno Silva Normat 1/2007
References
[1] Berman, D., “Hex must have a winner: an inductive proof", in Mathematics
Magazine, Vol. 49, No. 2, March 1976, p. 85–86.
[2] Binmore, K., Fun and Games, D. C. Heath and Co., 1992.
[3] Browne, C., Hex Strategy: Making the Right Connections, A. K. Peters 2000.
[4] Browne, C., Connection games, A. K. Peters, 2004.
[5] Gale, David, W., “The game of Hex and the Brouwer fixed-point theorem",
American Math. Monthly, Vol. 86, 1979, pp. 818–827.
[6] Gardner, M., “The Game of Hex", in The Scientific American Book of Math-
ematical Puzzles and Diversions, Simon and Shuster, New York, 1959, pp.
73–83.