# Hex (board game)

Hex (board game)

Infobox Game
subject_name=The Game of Hex
image_caption=A rendering of a Hex game on a 19x19 board
players=2
ages=4+
setup_time=1 minute
playing_time=15 minutes (11x11 board)
complexity=Low
strategy=High
random_chance=None
skills=Tactics, strategy, position

Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 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 14x14 as the optimal size.

History

The game was invented by the Danish mathematician Piet Hein, who introduced the game in 1942 at the Niels Bohr Institute, and also independently invented by the mathematician John Nash in 1947 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, 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). In 1952 Parker Brothers marketed a version. They called their version "Hex" and the name stuck.

Hex is an abstract strategy game that belongs to the general category of "connection" games. Other connection games include Omni, Y and Havannah. All of these games are related to the ancient Asian game of Go; Nash's version of Hex, in particular, was done as a response to Go.

Rules

Each player has an allocated color, Red and Blue being conventional. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal is to form a connected path of your stones linking the opposing sides of the board marked by your colors, before your opponent connects his sides in a similar fashion. The first player to complete his connection wins the game. The four corner hexagons each belong to "two" 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.

trategy

The game can never end in a tie, a fact found by John Nash: the only way to prevent your opponent from forming a connecting path is to form a path yourself. In other words, Hex is a determined game.

When the sides of the grid are equal, the game favors the first player. A standard non-constructive strategy-stealing argument proves that the first player has a winning strategy as follows:::Since Hex is a finite, perfect information game that cannot end in a tie, either the first or second player must possess a winning strategy. Note that an extra move for either player in any position can only improve that player's position. Therefore, if the second player has a winning strategy, the first player could "steal" it by making an irrelevant move, and then follow the second player's strategy. If the strategy ever called for moving on the square already chosen, the first player can then make another arbitrary move. This ensures a first player win.

There are two ways to make the game fairer. One way is to make the second player's sides closer together, playing on a parallelogram rather than a rhombus. However, using a simple pairing strategy, this has been proven to result in a win for the second player.

A fairer way is to use the pie rule, aka the swap rule, by which the second player has the option of swapping colors after the first player makes the first move, or first three moves, thus encouraging the first player to even out the game. Nowadays, in most online sites, the swap rule is the default, with the swap made after only one move. In theory the swap rule ensures that the second player has a winning strategy, but in practice the first player can choose a hex for which no winning strategy is known.

Cameron Browne wrote a book entitled "", which covers Hex strategy at a greater level of detail than any preceding work. [cite book | author = Cameron Browne | title = Hex Strategy: Making the Right Connections | id = ISBN 1568811179] However, some Hex players feel that this book contains many factual errors and advocates questionable strategies. Another book, to be written by Jack van Rijswijck and Ryan Hayward, was put on hold soon after the publication of "Hex Strategy"; it was to have a more mathematical bent than the somewhat conversational tone of Browne's book.

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.

Paths

Two groups of stones are said to be "n"-connected if you can connect them safely in "n" moves (or, more precisely, the number of moves you must make in order to safely connect the two groups minus the number of moves your opponent makes is "n"). Safely connected stones, such as adjacent stones are 0-connected. Bridges are also 0-connected. The lower "n" is, the better for you.

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.

Templates

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 you are 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

John Nash proved that a game of Hex cannot end in a tie.

In computational complexity theory, generalized Hex has been proven to be PSPACE-complete. [cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Informatica | issue = 15 | year = 1981 | pages = 167&ndash;191]

Hex has been solved for all symmetrical playing grids up to and including 9x9: that is, a perfect strategy has been demonstrated for the first player to move, such that he is always able to win.

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, [cite journal|author=David Gale |year=1979|title=The Game of Hex and Brouwer Fixed-Point Theorem | journal=The American Mathematical Monthly | volume=86 | pages=818–827] and the determinancy of higher-dimensional variants proves the fixed-point theorem in general.

Variants

Blockbusters

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 games of Y and Havannah

Y and Havannah are considered by some to be generalizations of Hex; they differ primarily in requiring players to connect three or more edges of a polygonal board, rather than two selected edges of a parallelogram.

Mind Ninja

Mind Ninja is another game considered by some to be 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.

Chameleon

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.

The Shannon Switching game

See Shannon switching game. Unlike Hex, this isn't PSPACE hard.

ee also

*Game theory
*Mathematical games
*Smart Game Format
*TwixT

References

* [http://www.hexwiki.org/ HexWiki] , a wiki dedicated to Hex
* [http://www.boardspace.net/ Play "HEX"] online at Boardspace.net, against human or robot opponents.
* [http://maarup.net/thomas/hex/ Thesis on Hex] history, classification and complexity
* [http://mathworld.wolfram.com/GameofHex.html Game of Hex] at MathWorld with links to related mathematical papers
* [http://www.cs.ualberta.ca/~queenbee/openings.html 1x1 to 6x6 opening strategy] by Jack van Rijswijck of the University of Alberta
* [http://www.ee.umanitoba.ca/~jingyang/ 7x7, 8x8 and 9x9 solutions] by Jing Yang of the University of Manitoba
* [http://hex.kosmanor.com/hex/theory.html Theory page] ] gathering theoretical work on the game.
* [http://www.penguinpeepshow.com/extendedY.html Play "HEX"] another page where you can play hex against a computer or discover Y. The A.I. is weak.
* [http://games.wtanaka.com/hex Play "HEX"] online with other people.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Board game — A board game is a game in which counters or pieces that are placed on, removed from, or moved across a board (a premarked surface usually specific to that game). As do other form of entertainment, board games can represent nearly any subject.… …   Wikipedia

• Chandragupta (board game) — Chandragupta Great Battles of the Mauryan Empire, India 319 261 BC Copyright © Rodger B. MacGowan Designer(s) Stephen R …   Wikipedia

• Evo (board game) — Infobox Game subject name=Evo image link= image caption=Players breed dinosaurs, fight for territory, and bid for mutations. players=3 ndash;5 ages=12 + setup time= 20 minutes playing time= 90 ndash;120 minutes complexity=Medium strategy=Medium… …   Wikipedia

• Star (board game) — Star is a two player abstract strategy board game developed in by Craige Schensted (now Ea Ea). It was first published in 1983 in Games magazine. It is connection game, related to games such as Hex, Y, Havannah, and TwixT. Unlike these games,… …   Wikipedia

• Struggle for Rome (board game) — Catan Histories: Struggle for Rome is a 2006 German style board game based on the game mechanics of Settlers of Catan , depicting the fall of the Roman Empire. The game is created by Klaus Teuber, the creator of Settlers , and is published under… …   Wikipedia

• War of the Ring (board game) — War of the Ring is a strategy board game by Roberto Di Meglio, Marco Maggi and Francesco Nepitello, produced by Nexus Editrice (Italy). Since its first print run it has been produced in many languages: Fantasy Flight Games publishes the English… …   Wikipedia

• HEX (disambiguation) — HEX could refer to:* Helsinki Stock Exchange * Hexham railway station, England; National Rail station code HEX. * High energy X rays * Intel HEX * Hex (Discworld) * Hex (TV series) * Hex (board game) …   Wikipedia

• Railroad Tycoon (board game) — Infobox Game subject name = Railroad Tycoon image link = image caption = designer = Martin Wallace and Glenn Drover publisher = Eagle Games players = 2–6 ages = setup time = 5 minutes playing time = 120 minutes complexity = Medium strategy = High …   Wikipedia

• Source of the Nile (board game) — Infobox Game subject name=Source Of The Nile image link= image caption = Source Of The Nile (1979) by Avalon Hill players=1 or more ages=12+ setup time=15 minutes playing time=2 hours complexity=Medium strategy=Medium random chance=Medium… …   Wikipedia

• Imperium (board game) — Imperium is a science fiction board wargame that was published in 1977 by the Conflict Game Company and GDW. It was designed by Marc W. Miller and developed by Frank Chadwick and John Harshman. The game came in a cardboard box illustrated with a… …   Wikipedia