Hex
 

Hex is my favourite board game. The rules are very easy -- indeed, the easiest rule of any game I know. Yet the strategy is quite deep and complex. Hex is played on a rhombic hexagonal pattern, as displayed on the right. This board has 11x11 cells, which is the most commonly used size, but Hex can be played on a board of any size.

Notice the blue and red coloured borders. The players take turns colouring the cells one at a time. The Red player attempts to build a chain of red coloured cells connecting the two red borders, while the Blue player tries to connect the blue borders with blue coloured cells. In the second diagram on the right, Blue has completed a winning chain.

Properties

Hex has many wonderful properties and deep mathematical connections. One of these properties is that Hex cannot end in a draw. There will inevitably be a winner, no matter what happens, and in fact there will be only one winner. Another great property is that we know that the first player has a winning strategy. That means that if you begin, you can always win -- if you don't make a mistake. This can be proved even though we don't generally know what that winning strategy is! John Nash in fact came up with Hex as a specific example of a game where this is the case.

Explicit winning strategies are known for boards of size up to 9x9, constructed by Jing Yang. A general winning strategy is unknown. It is known, however, that Hex is PSPACE-complete. This means that discovering a winning strategy that can be efficiently calculated would, as a side effect, solve the "P = NP" problem, the premier unsolved problem in mathematics today. The likely answer to this problem is that P does not equal NP, which would mean that there simply is no efficiently computable winning strategy for Hex. It's clear that Hex is quite a strategic challenge!

The first player enjoys a pretty substantial advantage in Hex. One would think that this could be offset by playing on a rectangular board where the first player's borders are farther apart than the second player's. Alas, that does not work, as it allows a simple pairing strategy for the second player to win. Advanced players usually use the swap rule instead. The first player plays the opening move, and the second player then chooses which colour to play from then on. This rule is also known as the pie rule: "I cut, you choose." It turns the game into a theoretical win for the second player, but in practice it evens things out quite adequately.

More information

  • Hex has a relatively short history, having been discovered only some 60 years ago.

  • Though there are several related games that some people claim to be superior, I still like Hex the best.

  • Due to its nice mathematical properties, Hex has been the subject of scientific papers and books. I have a few proofs of the no draw property and a proof of the first-player win online. I try to maintain an exhaustive Hex bibliography.

  • I used to have a page with Hex links, but the thing with internet links is that they go and change or die when you're not looking. So let's follow a more dynamic and modern approach to give you current Hex links, thanks to some wonderful piece of technological magic.

  • Marvel at my design skills: Hex boards to print out and play our favourite game on. Beads not included.

 an empty Hex board of size 11x11


Blue has a winning connection

(explanation)