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 gQ. 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 fQ. 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
- - WW - - -
- W - -
- - W -
- - - WW - - - -
W W W W -
- W W W -
- W W W W
- - - - WW - - - - -
W W W W W -
W W W W W W
W W W W W W
- W W W W W
- - - - - WQ. 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)