Hex (board game)
11×11 Hex gameboard showing a winning configuration for Blue
Abstract strategy game
|Playing time||15 minutes (11×11 board)|
|Skill(s) required||Strategy, tactics|
Hex is a strategy board game for 2 players played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Players alternate placing markers or stones (Go stones make ideal plying pieces) on unoccupied spaces in an attempt to link their opposite sides of the board in an unbroken chain. One player must win; there are no draws. The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed point theorem. It was invented in the 1940's independently by two mathematicians. The game was first marketed as a board game in Denmark under the name Con-Tac-Tix, and Parker Brothers marketed a version of it in 1952 called "Hex"; they are no longer in production.
- 1 Classification
- 2 History
- 3 Rules
- 4 Strategy
- 5 Theory and proofs
- 6 Complexity
- 7 Variants
- 8 Competition
- 9 See also
- 10 Further reading
- 11 References
- 12 External links
Hex is a finite, perfect information game.
When played on a generalized graph, Hex is equivalent to the Shannon switching game.
Nash and CON-TAC-TIX
The game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. It was independently re-invented in 1947 by the mathematician John Nash at Princeton University. It became known in Denmark under the name Polygon (though Hein called it CON-TAC-TIX); Nash's fellow players at first called the game Nash. According to Martin Gardner, who featured Hex in his July 1957 Mathematical Games column, some of the Princeton University students also referred to the game as John (according to some sources this was because they played the game using the mosaic of the bathroom floor). However, according to Sylvia Nasar's biography of Nash A Beautiful Mind, the game was referred to as "Nash" or "John" after its apparent creator. John Nash was said to have thought of this game, independent of Hein's, during his graduate years at Princeton. In 1952, Parker Brothers marketed a version. They called their version "Hex" and the name stuck.
Shannon's hex machine
About 1950, American mathematician and electrical engineer Claude Shannon constructed an analog Hex playing machine, which was essentially a resistance network with thermistors for edges and lightbulbs for vertices. The move to be made corresponded to a certain specified saddle point in the network. The machine played a reasonably good game of Hex. Later, using a digital computer, researchers demonstrated specific weaknesses of the analog machine.
In 1952 John Nash expounded an existence proof that on symmetrical boards, the first player has a winning strategy.
In 1964, mathematician Alfred Lehman showed that Hex cannot be represented as a binary matroid, so a determinate winning strategy like that for the Shannon switching game on a regular rectangular grid, was unavailable. The game was later shown to be PSPACE-complete.
In 2002, the first explicit winning strategy (a reduction-type strategy) on a 7x7 board was described.
In the 2000's, by using brute force search computer algorithms, Hex boards up to size 9x9 (as of 2016) have been completely solved.
Each player has an allocated color, conventionally Red and Blue or White and Black. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal for each player is to form a connected path of their own stones linking the opposing sides of the board marked by their colors, before their opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corner hexagons each belong to both adjacent sides.
Since the first player to move in Hex has a distinct advantage, the pie rule is generally implemented for fairness. This rule allows the second player to choose whether to switch positions with the first player after the first player makes the first move.
The strongest opening moves are along the short diagonal, followed by other cells near the center of the board. Conversely, the weakest opening moves are cells on the long diagonal or adjacent to it, and not close to the center. The board has 180 degree rotational symmetry: for every opening move (other than e center cell), there is a symmetrically identical move offset 180 degrees.
Bridges and connections
Two (groups of) stones are safely connected if nothing can stop them from being connected even if the opponent has the next move. One example of this is the bridge. Let A, B, C and D be the hexes that make up a rhombus, with A and C being the non-touching pair.
To form a bridge, a player places stones at A and C, leaving B and D empty. If the opponent places a stone at B or D, the remaining hex can be filled to join the original two stones into a single group. This strategy is very useful throughout the game.
Two groups of stones are said to be n-connected if they can be safely connected in n moves (or, more precisely, the number of moves a player must make in order to safely connect the two groups minus the number of moves their opponent makes is n). Safely connected stones, such as adjacent stones are 0-connected. Bridges are also 0-connected. The lower the value of n, the better for the player.
A path consists of two (or more) groups of stones and an empty-point set, which is the set of empty hexes that are required for the given connections. For example, the bridge path consists of the (one-member) group of stones at A and another (one-member) group of stones at C. The empty-point set is made up of the hexes B and D. For two paths to coexist and maintain the level of connectivity they have while independent, their empty-point sets must not contain any of the same hexes (otherwise the opponent could play there).
Two 1-connected paths can be consolidated together if the two groups of stones they start and end in are the same and their empty-point sets do not overlap.
An important concept in the theory of Hex is the template. Templates can be considered a special type of 0-connected path where one of the groups of stones is the edge that the player is trying to connect to.
Ladders are sequences of forcing moves where stones are placed in two parallel lines. They can be considered normal edge templates and can be analyzed using path analysis in the same way that bridges, paths, and templates can.
Theory and proofs
In 1976, Shimon Even and Robert Tarjan proved that determining whether a position in a game of generalized Hex played on arbitrary graphs is a winning position is PSPACE-complete. A strengthening of this result was proved by Reisch by reducing quantified Boolean formula in conjunctive normal form to Hex played on arbitrary planar graphs. In the computational complexity theory, it is widely conjectured that PSPACE-complete problems cannot be solved with efficient (polynomial time) algorithms. This result limits the efficiency of the best possible algorithms when considering arbitrary positions on boards of unbounded size, but it doesn't rule out the possibility of a simple winning strategy for the initial position (on boards of unbounded size), or a simple winning strategy for all positions on a board of a particular size.
In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7×7. They extended the method to the 8×8 and 9×9 boards in 2003. In 2009, Philip Henderson, Broderick Arneson and Ryan B. Hayward completed the analysis of the 8×8 board with a computer search, solving all the possible openings. In 2013, Jakub Pawlewicz and Ryan B. Hayward solved all openings for 9×9 boards, and one opening move on the 10×10 board.
The determinacy of Hex has other mathematical consequences: it can be used to prove the two-dimensional Brouwer fixed point theorem, as David Gale showed in 1979, and the determinacy of higher-dimensional variants proves the fixed-point theorem in general.
In 11x11 Hex, there are approx. 2.4x1056 possible legal positions; this compares to 4.5x1046 legal positions in chess. The game tree size is bounded by 121! = 8.0x10200; however this includes illegal positions resulting from continuing to play stones when a complete chain (win) exists for one side or the other. A rough estimate of the number of playable games may be obtained as follows: the average game lasts 30 moves per player; therefore the number of permutations has an upper bound of 121!/61! = 1.6*10117, again including some number of illegal positions. The number of unique positions/games in the tree can be further reduced by excluding rotations and reflections based on symmetries of the board and colors. This compares to 10123 node game tree size of chess.
Other connection games with similar objectives but different structures include Shannon switching game and TwixT. All of these games bear varying degrees of similarity to the ancient Asian game of Go.
Rectangular grids and paper and pencil
The game may be played on a rectangular grid like a chess, checker or go board, by considering that spaces (intersections in the case of go) are connected in one diagonal direction but not the other. The game may be played with paper and pencil on a rectangular array of dots or graph paper in the same way by using two different colored pencils.
Popular dimensions other than the standard 11x11 are 13×13 and 19×19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14×14 as the optimal size.
Hex had an incarnation as the question board from the television game show Blockbusters. In order to play a "move", contestants had to answer a question correctly. The board had 5 alternating columns of 4 hexagons; the solo player could connect top-to-bottom in 4 moves, while the team of two could connect left-to-right in 5 moves.
The game of Y is Hex played on a triangular grid of hexagons; the object is for either player to connect all three sides of the triangle. Y is a generalization of Hex to the extent that any position on a Hex board can be represented as an equivalent position on a larger Y board.[clarification needed]
Havannah is a rather broardly defined variant of Hex played on a hexagonal grid of hexagons. The objective is for either player to complete one of three characteristic patterns.
Mind Ninja is another game that is a generalization of Hex, albeit a rather broad one. As in Hex, two players vie to create mutually exclusive patterns by filling in cells of a tiled surface. In Mind Ninja, however, the players themselves define the patterns, subject to certain constraints. Mind Ninja differs from Hex also in that it can be played on any tiled surface, and each player may fill in a cell with any available color, rather than just one.
Utilizing the same board and pieces as Hex, Chameleon gives the players the option of placing a piece of either color on the board. One player is attempting to connect the north and south edges, and the other is attempting to connect the east and west edges. The game is won when a connection between a player's goal edges is formed using either color. If a piece is placed that creates a connection between both players' goal edges (i.e. all edges are connected), the winner is the player who placed the final piece.
Chameleon is described in Cameron Browne's book Connection Games: Variations on a Theme (2005) and was independently discovered by Randy Cox and Bill Taylor.
Pex is nearly identical to Hex, except that it's played on a rhombus-shaped tiling of irregular pentagons, instead of regular hexagons. Pex's tiling is notable for the fact that half of the pentagons each connect to seven adjacent neighbors, while the other half each connect to only to five neighbors. Pex's tactics are said to be much sharper than those of Hex.
Hecks is yet another variant of Hex in which the tiles of the square board are irregular polygons and the graph formed by polygon edges is trivalent, i.e. each node has precisely three incident arcs. The trivalence condition is meant to avoid the decision about the validity of the contact between two tiles that share only a vertex. An interesting aspect of Hecks is that the sides of the board have no predefined color: the black and white players do not have to declare in advance which pair of sides they attempt to connect, and the first player who completes a path across the board wins.
Players take turns to place a stone of their color and a neutral stone on empty cells; or replace two neutral stones with stones of their color, and replace a different stone of their color on the board to neutral stone.
As of 2016, there are few organized competitive Hex events.
- For four consecutive years starting in 2013, the International Committee of Mathematical Games has held a Hex competition in Paris, France.
- Hex Strategy, Browne C.(2000), A.K. Peters Ltd. Natick, MA
- Gardner, Martin (1959). Hexaflexagons and other Mathematical Diversions - The First Scientific American Book of Puzzles and Games. Simon and Schuster. pp. 73–75. ISBN 0-226-28254-6.
- S. Even and R. E. Tarjan. 1976. A Combinatorial Problem Which Is Complete in Polynomial Space. J. ACM 23, 4 (October 1976), 710-719. DOI=10.1145/321978.321989 http://doi.acm.org/10.1145/321978.321989
- Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191.
- On a decomposition method for finding winning strategy in Hex game, Jing Yang, Simon Liao and Mirek Pawlak, 2002
- Solving 8x8 Hex, P. Henderson, B. Arneson, and R. Hayward, Proc. IJCAI-09 505-510 (2009)
- Pawlewicz, Jakub; Hayward, Ryan (2013). "Scalable Parallel DFPN Search" (PDF). Proc. Computers and Games. Retrieved 2014-05-21.
- David Gale (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly. Mathematical Association of America. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146.
- Complete rules of Mind Ninja
- History and rules of Pex with the illustration, showing the board shape
- igGameCenter :: Nex