Hex (board game)
11×11 Hex gameboard showing a winning configuration for Blue
|Genre(s)||Board game |
Abstract strategy game
|Playing time||30 minutes – 2 hours (11×11 board)|
|Skill(s) required||Strategy, tactics|
Hex is a strategy board game for two 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 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 1940s independently by two mathematicians, Piet Hein and John Nash. 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 hexagonally ruled graph paper.
Hex-related research is current in the areas of topology, graph and matroid theory, combinatorics, game theory and computer heuristics.
- 1 Game type
- 2 History
- 3 Rules
- 4 Strategy
- 5 Theory and proofs
- 6 Complexity
- 7 Variants
- 8 Competition
- 9 See also
- 10 References
- 11 Further reading
- 12 External links
This section does not cite any sources. (January 2017) (Learn how and when to remove this template message)
Hex is a finite, perfect information game, and an abstract strategy game that belongs to the general category of connection games. When played on a generalized graph, it is equivalent to the Shannon switching game.
This section is missing information about which Danish company published Con-tac-tix.(January 2017)
The game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. Although Hein called it Con-tac-tix, it became known in Denmark under the name Polygon due to an article by Hein in the December 26, 1942 edition of the Danish newspaper Politiken, the first published description of the game, in which he used that name. The game was independently re-invented in 1948 by the mathematician John Nash at Princeton University. According to Martin Gardner, who featured Hex in his July 1957 Mathematical Games column, Nash's fellow players called the game either Nash or John, with the latter name referring to the fact that the game could be played on hexagonal bathroom tiles. In 1952, Parker Brothers marketed a version. They called their version "Hex" and the name stuck. 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
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. 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.
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 7×7 board was described.
In the 2000s, by using brute force search computer algorithms, Hex boards up to size 9×9 (as of 2016) have been completely solved.
Various paradigms resulting from research into the game have been used to create digital computer Hex playing automatons starting about 2000. The first implementations used evaluation functions that emulated Shannon and Moore's electrical circuit model embedded in an alpha-beta search framework with hand-crafted knowledge-based patterns. Starting about 2006, Monte Carlo tree search methods borrowed from successful computer implementations of Go were introduced and soon dominated the field. Later, hand crafted patterns were supplemented by machine learning methods for pattern discovery. These programs are now competitive against skilled human players. Elo based ratings have been assigned to the various programs and can be used to measure technical progress as well as assess playing strength against Elo-rated humans. Current research is often published in either the quarterly ICGA Journal or the annual Advances in Computer Games series (van den Herik et al. eds.).
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.
This section relies largely or entirely on a single source. (January 2017)
This section is missing information about diagrams 2 - 3.(January 2017)
From the proof of a winning strategy for the first player, it is known that the hex board must have a complex type of connectivity which has never been solved. Play consists of creating small patterns which have a simpler type of connectivity called "safely connected", and joining them into sequences that form a "path". Eventually, one of the players will succeed in forming a safely connected path of stones and spaces between his sides of the board and win. The final stage of the game, if necessary, consists of filling in the empty spaces in the path.
A "safely connected" pattern is composed of stones of the player's color and open spaces which can be joined into a chain, an unbroken sequence of edge-wise adjacent stones, no matter how the opponent plays. One of the simplest such patterns is the bridge (see diagram 1), which consists of two stones of the same color (A and C), and a pair of open spaces (B and D). If the opponent plays in either space, the player plays in the other, creating a contiguous chain. There are also safely connected patterns which connect stones to edges. One such pattern, analogous to the bridge, is shown in diagram 2. There are many more safely connected patterns, some quite complex, built up of simpler ones like those shown. Patterns and paths can be disrupted by the opponent before they are complete, so the configuration of the board during an actual game often looks like a patchwork rather than something planned or designed.
There are weaker types of connectivity than "safely connected" which exist between stones or between safely connected patterns which have multiple spaces between them. The middle part of the game consists of creating a network of such weakly connected stones and patterns which hopefully will allow the player, by filling in the weak links, to construct just one safely connected path (see diagram 3) between sides as the game progresses.
Success at hex requires a particular ability to visualize synthesis of complex patterns in a heuristic way, and estimating whether such patterns are 'strongly enough' connected to enable an eventual win. The skill is somewhat similar to the visualization of patterns, sequencing of moves, and evaluating of positions in chess.
Theory and proofs
John Nash was the first to prove (c. 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 in-house technical report in 1952, in which he states that "connection and blocking the opponent are equivalent acts." The earliest published proof of the determinacy of Hex, by David Gale in 1979, also showed that it can be used to prove the two-dimensional Brouwer fixed-point theorem, and that the determinacy of higher-dimensional variants proves the fixed-point theorem in general. A brief sketch of the no-draw ending requirement of Hex from that paper is presented below:
- Begin with a Hex board completely filled with hexagons marked with either X or O (indicating which player played on that hexagon).
- Starting at a hexagon vertex at the corner of the board where the X side and O sides meet, draw a path along the edges between hexagons with different X/O markings.
- Since every vertex of the path is surrounded by three hexagons, the path cannot self-intersect or loop, since the intersecting portion of the path would have to approach between two hexagons of the same marking. So, the path must terminate.
- The path cannot terminate in the middle of the board since every edge of the path ends in a node surrounded by three hexagons--two of which have to be differently marked by construction. The third hexagon must be differently marked from the two adjacent to the path, so the path can continue to one side or the other of the third hexagon.
- Similarly, if the sides of the board are considered to be a solid wall of X or O hexagons, depending on which player is trying to connect there, then the path cannot terminate on the sides.
- Thus the path can only terminate on another corner.
- The hexagons on either side of the line form an unbroken chain of X hexagons on one side and O hexagons on the other by construction.
- The path cannot terminate on the opposite corner because the X and O markings would be reversed at that corner, violating the construction rule of the path.
- Since the path connects adjacent corners, the side of the board between the two corners (say, an X side) is cut off from the rest of the board by an unbroken chain of the opposite markings (O in this case). That unbroken chain necessarily connects the other two sides adjacent to the corners.
- Thus, the completely filled Hex board must have a winner.
There is a reductio ad absurdum existence proof attributed to John Nash c. 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:
- Either the first or second player must win, therefore there must be a winning strategy for either the first or second player.
- Let us assume that the second player has a winning strategy.
- 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.
- 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.
- Because we have now contradicted our assumption that there is a winning strategy for the second player, we are forced to drop this assumption.
- 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. 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 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. 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. 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.
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; 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 approximately 10043 = 1086. 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. This compares to 10123 node game tree size of chess.
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 180°.
This section needs additional citations for verification. (January 2017) (Learn how and when to remove this template message)
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.
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.
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.
Havannah is a rather broadly defined variant of Hex played on a hexagonal grid of hexagons. The objective is for either player to complete one of three characteristic patterns.
Projex is a variation of Hex played on a real projective plane, where the players have the goal of creating a noncontractible loop. Like in Hex, there are no ties, and there is no position in which both players have a winning connection.
As of 2016, there were tournaments reported from Brazil (Catalão GO), Czech Republic (Praha), Denmark (Odense), France (Cannes, Le Mans, Neufchâtel-en-Bray, Paris), Germany (Leipzig, Sinzig), Italy (Genova, Pisa), Netherlands (Hilversum, Tiel), Norway (Oslo), Poland (Wrocław), Portugal (Aljezur, Alpedrinha, Amaraleja, Amares, Arcos de Valdevez, Aveiro, Barreiro, Batalha, Braga, Cacém-Agualva (Sintra), Cantanhede, Carnaxide, Coimbra, Covilhã, Curral das Freiras, Évora, Faro, Fátima, Fundão, Ginetes, Guimarães, Lagoa (Algarve), Lagos (Algarve), Lisboa, Moscavide, Odivelas, Ovar, Ponta Delgada, Portas do Mar, Portimão, Porto, Sabadim, Salvaterra de Magos, Santarém, Seixal (Setúbal), Silves, Valbom, Vila d'Este, Vila do Conde), Spain (Granollers), UK (London) and the US (Ann Arbor MI, Ypsilanti MI, Ripton VT).
One of the largest Hex tourneys is organized by the International Committee of Mathematical Games in Paris, France, which is annually held since 2013.
- 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.
- Nasar, Sylvia (November 13, 1994). "The Lost Years of a Nobel Laureate". The New York Times. Retrieved 23 August 2017.
- Shannon, C. (1953). "Computers and Automata". Proceedings of the Institute of Radio Engineers. 41 (10): 1234–41. doi:10.1109/jrproc.1953.274273.
- Anshelevich, V. (2002). A Hierarchical Approach to Computer Hex.
- Browne p.
- Browne, p.28
- Browne, p.29-30
- Browne, p.71-77
- Browne, p.
- Lasker, p.
- 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
- 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.
- 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. doi:10.1007/bf00288964.
- On a decomposition method for finding winning strategy in Hex game Archived 2 April 2012 at the Wayback Machine., Jing Yang, Simon Liao and Mirek Pawlak, 2002
- Unpublished white papers, formerly @ www.ee.umanitoba.com/~jingyang/
- 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.
- Browne, C (2000). Hex Strategy. Natick, MA: A.K. Peters, Ltd. pp. 5–6. ISBN 1-56881-117-9.
- Tromp, J. "Number of chess diagrams and positions". John's Chess Playground. Archived from the original on 29 June 2011.
- The exact number of nodes is actually 121*120*...*79=121!/78!=7.4*1085.
- Gardner (1959) p.78
- Browne (2000) p.310
- "Projex". BoardGameGeek. Retrieved 2018-02-28.
- Hex Strategy, Browne C.(2000), A.K. Peters Ltd. Natick, MA. ISBN 1-56881-117-9 (trade paperback, 363pgs)
- Thesis on Hex history, classification and complexity
- HexWiki, a wiki dedicated to Hex
- University of Alberta Computer Hex Research Group
- Theory page gathering theoretical work on Hex (moved - top level pages at Hex archive; downloadable material no longer available)
- Hex at BoardGameGeek
- Game of Hex at MathWorld with links to related mathematical papers
- Hex variants for gamers