Copyright 1995 by Bert Enderton, all rights reserved.

Q. Isn't Hex a solved game?

A. Only "ultra-weakly," to use Victor Allis's terminology.
John Nash

proved in 1949 that the first player has a theoretical win, but his

proof is non-constructive; i.e., it does not indicate how to win.
The

proof goes like this: Either there is a winning strategy for
the first

player, or there is a winning strategy for the second player (note

there are no draws). Suppose there were a winning strategy for
the

second player. The first player could "steal" this strategy by
making

an arbitrary first move and then pretending to be the second player

from then on. Whenever the strategy would call for playing on
hex he

already occupied (e.g. because that was his arbitrary first play),
the

first player would just make another arbitrary move. His extra
stone

could not hurt him. Thus the first player would win, which is
a

contradiction, therefore the second player does not have a winning

strategy, therefore the first player does.

Q. Is that the same John Nash who was recently awarded a Nobel prize?

A. Yes.

Q. What's the largest size board for which a complete winning

strategy is known?

A. 7x7. Jing Yang has written down such a strategy for 7x7 Hex;
it is

non-trivial (many pages). My program "knows" three winning strategies

for 7x7 Hex (each starting with a different first move).

Q. Wait, isn't 7x7 easy, because you can just play in the middle
and

connect that to both sides?

A. No. Playing in the middle is strong, but one cannot simply
force

a connection from there the edge. E.g.:

- - - - - - -

- H - V H - -

- - - V - - -

- - - V - - -

- - - = - - -

- - - - - - -

- - - - - - -

V's center stone is firmly connected to the top edge, and it may

appear that H has little hope of stopping her from connecting to the

bottom, but H can play at d3 and win!

Q. Where's d3?

A. I use chess-algebraic-like notation, i.e.:

a b c d e f g

7 - - - - - - - 7

6 - - - - - - - 6

5 - - - - - - - 5

4 - - - - - - - 4

3 - - - - - - - 3

2 - - - - - - - 2

1 - - - - - - - 1

a b c d e f g

Q. When my friends play the first player almost always wins.
How can

we make it more fair?

A. Have one player set up a position (preferably with not very
many

stones), specifying which color moves next, and let the other player

decide which color to play. Sort of like the "I cut you choose"
method

for dividing pie. The player with the choice of colors has a
theoretical

win, but the other player can make it very tough for him.

Q. What about mxn Hex?

A. The side with shorter length to traverse can win pretty easily,

even playing second. E.g. for 6x7 Hex, Horizontal (playing second)

need only use the following pairing strategy:

a g l p s u

a b h m q t

g b c i n r

l h c d j o

p m i d e k

s q n j e f

u t r o k f

Q. What literature is there about Hex?

A. Not much. Here are a few references:

Martin Gardner. {\em The Scientific American Book of

Mathematical Puzzles and Diversions}. Simon and Schuster

1959.

S. Even and R. E. Tarjan. A Combinatorial Problem Which

Is Complete in Polynomial Space. {\em Journal of the

Association for Computing Machinery}, volume 23 number 4,

October 1976.

David Gale. The Game of Hex and the Brouwer Fixed-point

Theorem. {\em American Mathematical Monthly}, number 86,

1979.

Stefan Reisch. Hex ist PSPACE-vollstandig. {\em Acta

Informatica}, volume 15, pp. 167-191, 1981.

Q. What is the computational complexity of Hex?

A. Hex, or more precisely the decision problem of whether one
has a

winning move in a given Hex position, is PSPACE-complete. (See
the

Reisch paper.)

Q. Got any neat Hex problems?

A. A few. Here are some:

- - - - - - -

- - V - - - -

- - - - H - -

- - - V - - -

- - V H V - -

- - - - - - -

- - - - - H -

Horizontal to play and win. (Easy)

- - - - - - -

- - - - V - -

- - - - - - -

- - - - - - -

- - V - - - -

- - - - - H -

- - - - - - -

Horizontal to play and win. (Medium)

What if V's stone on e6 were at d6?

- - - - - -

- - - H - -

- - - - - -

V - - - - -

- - - - - -

- - - - - -

Vertical to play and win. (Hard)

Q. What are the winning first moves on small boards?

A. Winning first moves for Vertical on small boards:

W - -

W W W

- - W

W - - -

- W - -

- - W -

- - - W

W - - - -

W W W W -

- W W W -

- W W W W

- - - - W

W - - - - -

W W W W W -

W W W W W W

W W W W W W

- W W W W W

- - - - - W

Q. Why aren't there any good Hex programs? It looks so simple to program.

A. Hex is simple, but standard computer chess methods would be
woefully

inadequate. Human players use several powerful reasoning techniques
to

analyse the game. A good hex program must approximate these methods.
That's

what my thesis work is about.

Q. When are you going to finish your thesis?

A. I don't know, maybe in a few months.

Send comments to Bert Enderton (hde@cs.cmu.edu)