Answers to infrequently asked questions about the game of Hex
by Bert Enderton
(Most of this material was written in 1995, but some was added in April 2000)
Isn't Hex a solved game?
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.
Is that the same John Nash who was awarded a Nobel prize in Economics in 1994?
Yes.
What's the largest size board for which a complete winning
strategy is known?
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).
Wait, isn't 7x7 easy, because you can just play in the middle and
connect that to both sides?
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 (Vertical's) center stone is firmly connected to the top edge, and it may
appear that H (Horizontal) has little hope of stopping her from connecting to the bottom, but H can play at d3 and win!
Where's d3?
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
When my friends play the first player almost always wins. How can
we make it more fair?
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.
What about mxn Hex?
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
What literature is there about Hex?
Not much. Here are a few references:
- Martin Gardner. 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. 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. American Mathematical Monthly, number 86, 1979.
- Stefan Reisch. Hex ist PSPACE-vollstandig. Acta Informatica, volume 15, pp. 167-191, 1981.
- Vadim Anshelevich. The Game of Hex: An Automatic Theorem Proving Approach to
Game Programming. Will appear in AAAI-2000 proceedings.
See also the ICGA hex page.
What is the computational complexity of Hex?
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. I haven't checked his proof.)
Got any neat Hex problems?
A few. Here are some:
- - - - - - -
- - V - - - -
- - - - H - -
- - - V - - -
- - V H V - -
- - - - - - -
- - - - - H -
Horizontal to play and win.
- - - - - - -
- - - - V - -
- - - - - - -
- - - - - - -
- - V - - - -
- - - - - H -
- - - - - - -
Horizontal to play and win. (Hard)
What if V's stone on e6 were at d6?
- - - - - -
- - - H - -
- - - - - -
V - - - - -
- - - - - -
- - - - - -
Vertical to play and win. (Very hard)
What are the winning first moves on small boards?
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
Hex looks simple to program, surely easier than a complicated game like chess, right?
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 was about, but I never finished it.
Vadim Anshelevich appears to have modeled the most important proof-building
methods in his program Hexy.
What other sites should I look at for information about Hex strategy
and Hex programs?
The International Computer Games Association
looks to be a great place to start. See their page on Hex. It is kept up
to date, which my page isn't!
hde@cs.cmu.edu