Hex: The Full Story

Over the years, there have been several board games that have attracted the interest of mathematicians. One is the Japanese game Go, and another is Hex, which is the subject matter of the book now under review, a book that can reasonably (with apologies to Dr. David Reuben) be subtitled Everything You Always Wanted to Know about Hex (But Were Afraid to Ask). Sorry, but some puns are simply impossible to resist.

The basic rules of the game (there are variations) are simple, and belie its underlying complexity. It is played on an n x n board of hexagons (as, for example, might be found on a tiled bathroom floor). There are two players, one (player W) with white tiles and one (player B) with black tiles. Two opposite sides of the board are white, the other sides are black. One player goes first and places his or her tile on any hexagon. The players then alternate turns, placing their tiles on empty hexagons. The first person to join his colored sides by an unbroken string of appropriately colored tiles is the winner.

There is some interesting mathematics associated with this game, with elegant and interesting proofs. The game never ends in a tie, for example, and the first player can always force a win. Both of these results are proved in the text. (Also interesting, and mentioned in the text, is that although it is known that the first player can always force a win, no specific strategy for doing so for arbitrary n x n games is known.)

The fact that the game does not end in a tie – i.e., a fully-completed Hex board has either a white or black path from one side to the other -- turns out to be equivalent to both the two-dimensional case of Sperner’s Lemma in combinatorics, and also to a discrete case of the Brouwer fixed point theorem. Yet, it has a simple intuitive explanation (this was shown to me many years ago, but I cannot now remember the source): think of white as water and black as a barrier. The only way that water will not flow from one end of the board to the other is if there is a barrier extending from one opposing side to the other.

Other mathematical ideas are discussed in the text, including the four-color problem, complexity and the P vs NP problem, and applications to computer play.  

However, this is not a mathematics textbook, and people who are not terribly interested in mathematical proofs and reasoning will still find much of interest here. In addition to discussing some of the mathematics behind the game, for example, the book also addresses at great length the history of Hex. This history can be briefly summarized as follows: the Danish poet Piet Hein invented the game (then called Polygon) in the 1940s, but it was apparently introduced to the United States via a subsequent conversation between John Nash and David Gale. (The extent to which Nash discovered Hex independently is a matter of some dispute.) It was marketed, without great success, by Parker Brothers, and then in July 1957 achieved considerable publicity through a Scientific American column by Martin Gardner.

The book discusses this history in considerable detail, and we are treated to glimpses of the personalities of Nash and Hein. Upset by Gardner’s column, which did not mention him, Nash complained to Gardner, who in his October 1957 column updated his July column by mentioning him. This, in turn, upset Hein. Extensive correspondence between Gardner and Hein are reproduced in the book and make interesting reading.

In addition to tracing the history of Hex, the authors also include lots of actual puzzles, with solutions, and discuss at length aspects of Hex strategy. Games that are related to Hex, such as Bridg-It and Rex (also known as “reverse Hex”), are also discussed.

Who should read this book? Because of its mathematical content, instructors of courses in subjects like game theory or discrete mathematics might want to flip through it as a potential source of lecture material. People interested in the history of mathematics might find some of the biographical and historical detail here interesting. And of course anybody who enjoys the game of Hex will find much of here interest as well. It’s a fun book.

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.