Hex

In this blog post and the presentation to follow, I will do my best to teach you about the game of Hex, or Polygon, or John, or Nash, or CON-TAC-TIX. Quite confusing, I know. But the multiple names are because it was discovered twice, once by Piet Hein in 1942, and then rediscovered in 1947 by John Nash. Each inventor had multiple names for the game. My personal favorite is John, because John Nash’s students at the time the game was invented, played on the hexagonal tiles on the bathroom floor, AKA the John. But when the game was later marketed, the name Hex stuck.

The Game

Hex is different from all the games that we have talked about so far in this class. Hex is a board game made up of small hexagons, combined to make an nxn rhombus shaped board. The traditional sizes of the board are 11x11, 13x13, & 19x19, because of the relationship to older connection games such as GO. However, John Nash argued that 14x14 sized board was the optimal size. The most common size and the marketed size is a 11x11 board. 

The game is played with two players, each with a different set of stones, traditionally black and white, or red and blue. The players alternate turns placing stones within an empty hexagon on the board. The objective is to connect opposite sides of the board. One player goes for a horizontal connection and the other player goes for the vertical connection. It is important to know that the corners of the board belong to both sides.

With a little bit of knowledge of the game, it appears pretty obvious that you want to go first. Having one more piece on the board than the second player is never a bad thing in Hex, unless you are playing Misere Hex, which I will talk about later. So a few attempts have been made to try and even out the playing field between the first and second players. One attempt was the Pie Rule, this allows the second player to switch positions with the first player after the first player has gone. (Now I am not entirely sure what happens to the first player’s stone, but I will report back on Thursday) The Second option is to make the board an nxm board, where m=n-1.

The first player will work to connect n, while the second player works to connect m. But the second player wins, if played correctly.

Now when I say a player wins, or usually wins, I am referring to the fact that that player is in favor to win. This is not saying that one player is guaranteed a win. There is some strategy to Hex, that could help the second player win, yet the first player can always steal the strategy. One method is the idea of bridges and connections. As seen below, the two blue groups are considered to be safely connected, or 0-connected. If the second player places a stone in either B or D, the first player can place a stone in D or B the next turn.

Paths are considered to be n-connected if they can be safely connected. To find out what n is, the number of moves to connect the groups minus the number of moves the opponent has equals n. In the example above, these are 0-connected because each player can make one move.

Theory and Proofs

One rule of Hex, is that it can never end in a tie. Now this is not like Tic-Tac-Toe, where you start over with a fresh board until someone wins, this is a fact. The only way for one player not to be able to connect a path to the opposite side is if the other player has already connected a path.

Now the proof… While researching, I found the same thing multiple times. There exists a proof to Hex, that is about four pages long of fine print. But they all summed up the proof in the same way that makes sense, and can be written in about a paragraph.

As previously stated, the game of Hex cannot end in a tie, thus the game is finite, meaning that one player has a winning strategy. Through contradiction, we assume that the second player has the winning strategy, and so the first player places a stone in an arbitrary location on the board. The first player can simply follow the strategy of the second player, and imagine that the hexagon containing the first stone is empty. If the strategy requires the first player to place a stone in the location of the arbitrarily placed first stone, the first player can place the stone elsewhere. And since an extra stone does not hurt the first player, the first player wins.

Now this proof contradicts the fact that the second player had a sinning strategy, and it is also non-constructive. Furthermore, a winning strategy for the first player is not known.

Now I must say this was a little annoying to me that the proof said just copying the strategy will help you win the game. I personally wanted there to be more strategy involved in the game, and apparently so have other mathematicians. And so every win/lose status/position has been determined for every move on a 7x7 board, by Hayward. A winning strategy is know for 8x8 and 9x9 boards as long as the first move is in the center of the board. C.F. Shannon and E.F. More have built a hex playing machine to help with the process of finding the winning strategy of lager boards.

Extra

Misère Hex is where the first player to connect the sides of the board will lose. In this case, there is an equal chance at winning, for both players, and so going first is not always a benefit.

If you are interested in playing the game of Hex online, here is a link

http://www.lutanho.net/play/hex.html

Good luck, I tried multiple times on multiple difficulties, and never won.

References

https://en.wikipedia.org/wiki/Hex_(board_game)

https://en.wikipedia.org/wiki/PSPACE-complete

http://mathworld.wolfram.com/GameofHex.html

https://www.cs.cmu.edu/~sleator/papers/Misere-Hex.pdf

http://www.math.pitt.edu/~gartside/hex_Browuer.pdf