Hex (board game)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about the abstract strategy game. For the hexagonal map style popular in wargaming, see Hex map.
Hex
Hex-board-11x11-(2).jpg
11×11 Hex gameboard showing a winning configuration for Blue
Years active 1942–
Genre(s) Board game
Abstract strategy game
Players 2
Age range 8+ to adult
Setup time none
Playing time 30 minutes - 2 hours (11×11 board)
Random chance None
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 playing 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. Hex can also be played with paper and pencil on hexagonal ruled graph paper.

Classification[edit]

Hex is a connection game, and can be classified as a Maker-Breaker game, a particular type of positional game.

The game can never end in a draw (tie), in other words, Hex is a "determined game".

Hex is a finite, perfect information game.

Hex is an abstract strategy game that belongs to the general category of "connection" games.

When played on a generalized graph, Hex is equivalent to the Shannon switching game.

As a product, Hex is a board game; it may also be played with paper and pencil.

History[edit]

Published games[edit]

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.[1] Hex was also issued as one of the games in the 1974 3M Paper Games Series; the game contained a 5½ × 8½ inch 50-sheet pad of ruled hex grids.

Shannon's hex machine[edit]

About 1950, American mathematician and electrical engineer Claude Shannon and E. F. Moore constructed an analog Hex playing machine, which was essentially a resistance network with resistors for edges and lightbulbs for vertices.[2] 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, researchers attempting to solve the game and develop hex-playing computer algorithms, emulated Shannon's network to make strong automatons.[3]

Research[edit]

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.

Automatons[edit]

Various paradigms resulting from research into the game have been used to create digital computer Hex playing automatons starting about 2000.

Rules[edit]

A CG rendering of a game of Hex on a Go-style 19×19 board

Each player has an allocated color, conventionally Red and Blue or White and Black.[1] 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.

Strategy[edit]

The objective is to establish a connected chain of stones between one's own sides of the board. The notion of connectivity may be extended to patterns of stones that are not edge-wise adjacent, but can be connected in turn no matter how the opponent plays. Such local patterns of stones are in turn connected in a more general network that has a property called 2-connectivity: there will be pairs of spaces such that should the opponent play one, the first player plays the other, such that the property can be maintained, until the closing of the final pair completes a chain of edge-wise adjacent stones between sides. Pairs are not necessarily reciprocally symmetric: if there is a pair of spaces (a,b), and the opponent plays on a, the indicated move may be b; but if the opponent plays on b, b may be a part of another asymmetric pair (b,c) so that the indicated move is c. Recognizably establishing the property (i.e. being able to enumerate the pairs) is equivalent to winning the game. As it is known that the first player has a winning strategy, the configuration of the empty board in fact has the 2-connected property with respect to the first player, though not in an enumerable form. As a corollary of the Hex Theorem, the establishment of the 2-connected property with respect to either player excludes it for the other.

The strategy then consists of three phases:

  • establishing 2-connected local patterns of stones
  • melding the local patterns into a 2-connected network
  • closing the pairs sequentially, or in response to the opponent

It is usually not necessary to complete the last phase, because both players will recognize at some point that 2-connectedness has been established, and the game is at an end. The average length of a Hex game is about 20 moves per player on a standard board.

The initial pattern is established in or near the center of the board or along the short diagonal. A pattern may consist of a single stone, but others are a complex relationship between a set of the players own stones, the opponent's stones and open spaces. Patterns close to the player's own edges of the board include the edge as part of the pattern. The patterns are somewhat analogous to tactical elements of combination in chess.The repertoire of such patterns is substantial; stronger players will have larger repertoires than weaker players. As an example, the solution of 7x7 Hex by decomposition into such patterns involved a set of 63. 11x11 Hex is vastly more complex than 7x7 Hex.

Patterns may be elementary or complex (composite); some elementary patterns are:

Opening patterns

The strongest opening moves are along the short diagonal,[citation needed] 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.

Chains

A chain is a set of edge-wise adjacent stones of one color (may be only a single stone). A chain is always safely connected. A chain which spans opposite sides of the board is a win.

Connections

Two groups of stones are said to be n-connected if they can be safely connected in n moves. The lower the value of n, the better the connection. Two (groups of) stones are safely connected if nothing can stop them from being connected even if the opponent has the next move. Safely connected stones, such as adjacent stones are 0-connected. Bridges are also 0-connected.

Paths

A path consists of two (or more) groups of stones and an empty-point set, which is the set of empty cells 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 spaces B and D. Independent paths must have disjoint empty-point sets.

Bridges

Red cannot stop Blue from connecting A and C on the next move.

One example of a safe connection is the bridge, a pattern of two stones on a pair of cells (A and C) separated by a pair of adjacent empty points (B and D). If the opponent plays a stone at B or D, the adjacent cell can be played to join the original two stones into a single group.

Templates

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

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.

Virtual connections

A virtual connection is a generalization of the bridge connection: Two 1-connected paths can be consolidated together[clarification needed] if the two groups of stones they start and end with are the same and their empty-point sets do not overlap.

Theory and proofs[edit]

John Nash was the first to prove (circa 1949) that Hex cannot end in a draw, a non-trivial result colloquially called the "Hex theorem", which we now know is equivalent to the Brouwer fixed-point theorem. Apparently, he didn't publish the proof. The first exposition of it appears in an an in-house technical report in 1952.[4]

There is a reductio ad absurdum existence proof attributed to John Nash circa 1949 that the first player in Hex on a board of any size has a winning strategy. Such a proof gives no indication of a correct strategy for play. The proof is common to a number of games including Hex, and has come to be called the "strategy-stealing" argument. Here is a highly condensed informal statement of the proof:[1]

1. Either the first or second player must win, therefore there must be a winning strategy for either the first or second player.
2. Let us assume that the second player has a winning strategy.
3. The first player can now adopt the following defense. He makes an arbitrary move. Thereafter he plays the winning second player strategy assumed above. If in playing this strategy, he is required to play on the cell where an arbitrary move was made, he makes another arbitrary move. In this way he plays the winning strategy with one extra piece always on the board.
4. This extra piece cannot interfere with the first player's imitation of the winning strategy, for an extra piece is always an asset and never a handicap. Therefore the first player can win.
5. Because we have now contradicted our assumption that there is a winning strategy for the second player, we are forced to drop this assumption.
6. Consequently, there must be a winning strategy for the first player.

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.[5] 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.[6] In 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 using a decomposition method with a set of reusable local patterns.[7] They extended the method to weakly solve the center pair of topologically congruent openings on 8×8 boards in 2002 and the center opening on 9×9 boards in 2003.[8] 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.[9] In 2013, Jakub Pawlewicz and Ryan B. Hayward solved all openings for 9×9 boards, and one opening move on the 10×10 board.[10]

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,[11] and the determinacy of higher-dimensional variants proves the fixed-point theorem in general.

Complexity[edit]

In 11x11 Hex, there are approx. 2.4x1056 possible legal positions;[12] this compares to 4.6x1046 legal positions in chess.[13]

A rough estimate of the number of nodes in the game tree can be obtained as an exponential function of the average branching factor and the average number of plies in a game thus: bd where d is the ply depth and b is the branching factor. In Hex, the average branching factor is a function of the ply depth. It has been stated that the average branching factor is about 100;[citation needed] that implies an average ply depth of 43 (there will be 121 open spaces on the board when the first player is to make his first move, and 79 when he is to make his 22nd move, the 43rd ply - the average number of open spaces, i.e. branching factor, during the game is (121+120+...+79)/43=100). Therefore the game tree size has an upper bound of approx. 10043 = 1086.[14] The bound includes some number of illegal positions due to playing on when there is a complete chain for one player or the other, as well as excludes legal positions for games longer than 43 ply. Another researcher obtained a state space estimate of 1057 and a game tree size of 1098 using an upper limit of 50 plies for the game.[citation needed] This compares to 10123 node game tree size of chess.[citation needed]

An interesting reduction is available by noting that the board has rotational symmetry: for each position, a topologically identical position is obtained by rotating the board 1800.

Variants[edit]

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[edit]

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.

Board sizes[edit]

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.

Reverse hex[edit]

A variation has been described in which each player tries to force his opponent to make a chain. This is a slow game. A clever proof has been discovered that the first player can win on a board with an even number of cells per side, and the second player can win on a board with an odd number.[15][16]

Blockbusters[edit]

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.

Y[edit]

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.

Havannah[edit]

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.

PÜNCT[edit]

PÜNCT is also played on a hexvalent grid with pieces which cover three hexes each. The pieces can be moved, rotated, and stacked.

Competition[edit]

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.

See also[edit]

Further reading[edit]

  • Hex Strategy, Browne C.(2000), A.K. Peters Ltd. Natick, MA. ISBN 1-56881-117-9 (trade paperback, 363pgs)

References[edit]

  1. ^ a b c Gardner, M. (1959). The Scientific American Book of Mathematical Puzzles & Diversions. N.Y., N.Y.: Simon and Schuster. pp. 73–83. ISBN 0-226-28254-6. 
  2. ^ Shannon, C. (Oct. 1953). Computers and Automata, Proceedings of the Institute of Radio Engineers, Vol. 41, No. 10, pages 1234-41
  3. ^ Anshelevich, V. (2002). A Hierarchical Approach to Computer Hex.
  4. ^ Nash, John (Feb. 1952). Rand Corp. technical report D-1164: Some Games and Machines for Playing Them. https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf
  5. ^ 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
  6. ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191. 
  7. ^ On a decomposition method for finding winning strategy in Hex game, Jing Yang, Simon Liao and Mirek Pawlak, 2002
  8. ^ Unpublished white papers, formerly @ www.ee.umanitoba.com/~jingyang/
  9. ^ Solving 8x8 Hex, P. Henderson, B. Arneson, and R. Hayward, Proc. IJCAI-09 505-510 (2009)
  10. ^ Pawlewicz, Jakub; Hayward, Ryan (2013). "Scalable Parallel DFPN Search" (PDF). Proc. Computers and Games. Retrieved 2014-05-21. 
  11. ^ 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. 
  12. ^ Browne, C (2000). Hex Stratey. Natick,MA: A.K. Peters, Ltd. pp. 5–6. ISBN 1-56881-117-9. 
  13. ^ Tromp, J. "Number of chess diagrams and positions". John's Chess Playground. 
  14. ^ The exact number of nodes is actually 121*120*...*79=121!/78!=7.4*1085.
  15. ^ Gardner (1959) p.78
  16. ^ Browne (2000) p.310

External links[edit]