|
This is the first in a series of articles about the abstract board game Hex. In this issue we look at the game's rules, its history, and some basic strategy. Upcoming issues examine key points of strategy in more depth, followed by a discussion of a simple algorithm that plays a surprisingly strong game of Hex, complete with C code. Hex puzzles relevant to the topics covered are included at the end of each instalment.
Introduction to Hex
Hex is an abstract board game that has fascinated mathematicians with its beauty and surprising difficulty since it was first invented over half a century ago. It is a seminal game that has inspired many variants over the years, some of which have achieved greater fame than Hex itself.
If a game's worth can be estimated by its strategic depth versus rule complexity, then Hex provides excellent value. It is extraordinarily complex yet with a rule set among the simplest of any game possible.
Rules
The Hex board is an mxn hexagonal tiling in a rhombus shape. 11x11 is the standard board size that we will focus on, although larger boards provide a richer game. Two players, Black and White, are assigned opposite edges of the board. The board is initially empty.
The rules of Hex are simple:
*Players take turns placing a piece of their color on an unoccupied hexagon.
*The game is won when one player establishes an unbroken chain of his pieces connecting his sides of the board.
A game can never end in a tie: if one player completes a connection between his edges, then the other player is prevented from doing so. Figure 1 illustrates a game won by White, who has formed a contiguous chain of pieces between his edges.
The player to move first has a huge (winning) advantage if he is allowed to make a strong opening play. An additional rule is often used to reduce this first move advantage:
The player to move second has the choice of swapping colors, effectively stealing the first player's move.
Figure 1. A game won by White.
This is called the swap option, and it's recommended that all games be played with this additional rule. There is no universally accepted starting color; either Black or White may start the game.
History
Hex was first invented in 1942 by Danish mathematician Piet Hein, and was originally called Polygon. The same game was independently developed in 1948 by Nobel laureate John Nash, then a graduate student of mathematics at Princeton University.
Hex has always had a dedicated following amongst the mathematical community, and has been the subject of many worthwhile research papers. It was introduced to a wider audience with the publication of Martin Gardner's Scientific American article "The Game of Hex" during the late 1950s. Hex is currently enjoying another resurgence of interest and is becoming a popular game amongst the internet gaming community.
In terms of strategy, two aspects of the game are of particular interest:
*One player must win.
*First player has a winning line.
The first point is related to the fact that Hex is a generalization of the Shannon Switching Game. It is analogous to an electric circuit where one player (Cut) tries to break the circuit, or connection, while the other player (Short) tries to complete the circuit, or connection. At the completion of a game only one of these states can exist.
The second point derives from the first, and is based upon a strategy stealing argument proposed by Nash. Essentially, if a winning strategy exists for the second player, then the first player can win the game by stealing this strategy given that he has the advantage of an extra move.
The huge first move advantage is a flaw in the game that players have attempted to address with a number of superficial fixes. The swap option described above is the most satisfactory solution, and in fact adds a dimension of strategy to the game. It does for Hex what the doubling cube does for Backgammon.
Nature of the Game
Hex belongs to the class of two-person zero-sum finite deterministic games of strategy. David Parlett, in The Oxford History of Board Games, places it within the overall context of board games as a game of linear connection and describes Hex as a classic of its type.
Although it is known that a winning strategy exists for Hex, the strategy itself has eluded researchers, except for smaller boards. This is largely due to the extraordinary combinatorial complexity of the game. The study of Hex strategy is an attempt to reduce this complexity to a manageable level and tame the game's branching factor by pruning suboptimal choices from the game tree.
Estimating the strategic depth of a game is not as simple as describing the size of the complete game tree. As Robert Abbott points out in relation to his game Ultima, the depth of a game depends not so much on the size of the game tree as on how far a player can see down the game tree.
This concept of clarity essentially describes the amount of certainty with which a player can plan ahead and formulate strategies. Hex has excellent clarity: each piece is of uniform strength, the board is uniformly distributed, the goals of the game are well defined, and it's often possible to plan a dozen or more moves ahead with reasonable certainty.
Other Tilings
At its most essential, the Hex board can be described as a graph with connections between adjacent hexagons. This raises the intriguing possibility of playing the game on other surfaces such as semi-regular tilings, irregular tilings, or even maps, as suggested by David Book.
Figure 2. Hex played on a map of the contiguous United States.
Figure 2 shows a game of Hex played on a map of the contiguous United States. White's goals are the shores of the Pacific and Atlantic oceans and Black's goals are the borders Mexico and Canada. This map is not ideal: as can be seen Black has a distinct advantage and wins easily, and the game can theoretically be deadlocked as four states meet at one point.
The hexagonal grid is the optimal choice of playing surface for a number of reasons. It is regular and hence uniform in distribution, is the regular tiling with the greatest number of neighbors and hence connective potential and scope for strategy, and does not allow deadlocks to occur.
Now for some strategy….
Connectivity Is Everything
The concept of connectivity is central to Hex. Two pieces are said to be n-connected if they can be joined to form an unbeatable connection in n moves when considered in isolation. Pieces that are 0-connected are described as safely connected and other connections unsafe.
Non-adjacent pieces can still be safely connected as shown by pieces a and b in Figure 3. If Black plays in one of the empty points separating a and b then White can play in the other empty point next turn to complete the connection. Empty points such as these that provide an alternative route within a safe connection are called the dual points of the connection.
Figure 3. White's pieces are: 0-connected,
1-connected, and 2-connected.
Pieces c and d require one move by White to ensure their safe connection. Pieces e and f require two moves through the intermediate White piece at the top of the figure.
The golden rule of Hex is: a player's position is only as good as the weakest link in his best connection across the board.
Bridges
The simplest non-adjacent safe connection between two pieces is the bridge formation as shown in the right of Figure 4. This is the basic building block that a player will use to extend his connection across the board.
Figure 4. Adjacent and bridge pieces with links shown underneath.
For board analysis it is useful to show links between pieces explicitly. Links between adjacent pieces are drawn directly, and bridge links are drawn as two arcs through the connection's dual empty points.
Figure 5. Expansion by adjacent moves versus bridge moves.
Bridges allow a player to expand a safe connection twice as fast as using adjacent moves, as can be seen in Figure 5.
Just as bridges contain dual paths between two pieces, more complex connections between groups of pieces and edges can be developed through the recursive growth of dual links as shown in Figure 6.
Figure 6. Completed game with 0-connected spanning path.
White's edges are safely connected by a spanning path across the board. Black cannot defeat this connection. This is the same game as that shown in Figure 1 after the fourteenth move. If both players are evenly matched there is no point in playing any further, and it would be prudent for Black to concede at this point and get on with the next game.
So when exactly is a game of Hex over? As soon as either player forms a 0-connected spanning path between his edges.
Forcing Moves
Safe but non-adjacent connections contain vulnerable dual points that may be exploited. If the opponent occupies such a vulnerable point, the player is obliged to play in its dual to preserve the connection. Such intrusions or forcing moves are the key to Hex's rich strategy.
The following example shows how forcing moves can wrest the initiative away from the opponent and win the game.
Figure 7. White to move.
The situation shown in Figure 7 looks good for Black. He has a 1-connected spanning path whose only weak link appears to be through empty point C7. What is White's best play?
Figure 8. Move 11 forces reply 12.
Move 11 intrudes into one of Black's bridges and threatens to give White a 0-connected spanning path if he moves at C5. Black is forced to reply at C5 with move 12 to keep the game alive.
Figure 9. Move 13 forces reply 14.
White then moves in Black's weak link with move 13. Again Black is forced to reply with move 14 to avoid immediate defeat.
Figure 10. Move 15 wins the game for White.
Move 15 wins the game for White as shown by the spanning path in Figure 10. Forcing move 11 provided the stepping stone necessary to complete this connection.
As suggested by David Boll, the following options are available to a player when his opponent has just made a forcing move:
*Answer the forcing move and save the link,
*Give up the link and move elsewhere (if not a winning link), or
*Play a forcing move himself.
In general a forcing move should not be ignored unless the reply is a stronger forcing move itself or the threatened connection is not essential. When considering a reply to a forcing move, the player should first determine how important the link is to his overall connection and whether it can be abandoned or not.
Forcing moves are a good way to gain the momentum, and when used properly force the opponent into a series of weak forced replies. This is a good opportunity for the player to force a win or develop his connection while maneuvering the opponent into a disadvantageous position.
Next issue we will look at some more advanced points of strategy.
Puzzles
This first set of puzzles is a gentle introduction to the game based on combinatorial play rather than knowledge of strategy. Solutions are provided in the next issue.
Puzzle A: White to play and win. This puzzle was devised by Piet Hein over 50 years ago.
Puzzle B: Black to play and win.
Puzzle C: White to play and win.
Puzzle D: White to play and win.
References
Abbott, R. (1988) "What's Wrong With Ultima," World Game Review, 8, 12-13.
Boll, D. (1994) "Hex: Answers to common questions," http://www.frii.com/~dboll/hexfaq.txt.
Book, D. L. (1998) "What the Hex," The Washington Post, September 9th, page H02.
Gardner, M. (1959) "The Game of Hex," Mathematical Puzzles and Diversions, Penguin, Hammondsworth, 70-77.
Parlett, D. (1999) The Oxford History of Board Games, Oxford University Press, Oxford.
| 
