The Game of Hex
Created | Updated Aug 21, 2003
Hex is a game where two players alternate placing counters on a diamond1 of hexagons, with the aim of completing an unbroken line from one of their sides to the other. Unlike Tic Tac Toe (Noughts and Crosses) it cannot end in a draw - one of the two players must be able to complete a chain, since no chain can be completely blocked except by an opposing complete chain.
Great minds think alike
Although Hex was first invented by Piet Hein, it is accepted that it was also invented independently a few years later by John Nash2 (not an EG Entry ref yet), who became an outstanding authority on game theory (not an EG Entry ref yet). Hein initially called the game Polygon, and first showed it when lecturing to students at the Institute for Theoretical Physics of the University of Copenhagen in 1942. Nash independently invented the game in 1948 while he was a graduate mathematics student at Princeton University, and it became popular among the mathematics students there, who called it either John or Nash.
The name Hex (note this is a link to a pdf file) was given to the game in 1952, when a commercial version was issued by the game company Parker Brothers. The game was later copyrighted in 1968 under a further name Con-Tac-Tix (note this is a link to a pdf file), and it is this name that it is given at Piet Hein's official site, though generally the game remains known as Hex.
Can I have a P Bob?
Hex will be familiar to British Researchers through its use as the basis for the Blockbusters TV gameshow hosted by Bob Holness.
Blockbusters uses a 4x5 rectangular board of twenty hexagons (so the distance between top and bottom sides is shorter than between left and right sides), and in each hexagon is a letter that begins the answers for questions about that cell. The competitors attempt to join their two sides by correctly answering questions on the cells they want.
The asymmetrical board is matched by using uneven 'teams', one 'team' consisting of a single player, the other of two players. The two-player team has to link the sides which are further apart. Since each hexagon has to be won, by correctly buzzing the answer first to a question, the greater distance is balanced by the greater chance of buzzing first by having two people available to guess. In Blockbusters both sides have the chance to 'play' first on the randomly chosen hexagon, and the winner of each hexagon has the chance to choose the next hexagon to play for in a game.
Blockbusters actually started life in the USA, one of the many 1970s Mark Goodson game-shows. The idea was spotted by a producer who piloted the show in the 1980s in the UK.
Ooh Strategy!
While Hex has a simple board and rules it does not have a simple winning strategy. It was shown by John Nash in 1949 that the first player can force a win, but this proof is not translatable into a winning strategy for the first player to follow for all sizes of board3. The first link below also has a good summary of small scale strategies.
What is the proof? It is one of those reductio ad absurdum ones, that only proves the existence of a winning strategy, without giving the decision procedure that will assure a win. Since the first or second player must win (a game can't be drawn remember), then it is either the case that the first player can always force a win by playing the best strategy, or that the second player can.
If you assume that there is a strategy by which the second player could force a win then 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 second player "winning strategy" calls for playing on a space already occupied (eg because that was the arbitrary first play), the first player just makes another arbitrary move. The extra counter would not hurt. Thus the first player would win, which contradicts the assumption of a second player "winning strategy" , therefore this strategy can not exist, and the first player winning strategy must. Clear?
Variations on a Theme
To negate the first player theoretical advantage in the standard game there are a few variations that have been proposed to even things out.
One is an additional rule that allows the second player to swap sides with the first player after the first counter has been placed, effectively stealing the first move. Knowing this is an option the first player is forced to choose a first move which won't give a definite win.- Another is the the misère variant, which has been called Reverse Hex or Rex, in which each player attempts to force the other player to be the first to make a complete line. It has been shown that the first player can win this variant on boards with even number of cells on each side, but the second player can always win when it is odd.
- The 'Blockbuster' variant, of having one pair of sides a hexagon longer than the other, and making the first player try to join the sides furthest apart, would in a normal game (ie one without having to win each hexagon in turn) be susceptible to a certain second player win by using a fairly simple pairing strategy.
References and links
- Martin Gardner wrote about Hex in two of his books, Mathematical Puzzles and Diversions and Time Travel and Other Mathematical Bewilderments.
- Hex Game and strategies will link to a site with a game you can pit yourself against the computer (and generally lose unless you concentrate hard).
- Mathworld Hex history provides a concise history of the game, and a good list of other references.
