## 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.

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