.gif)
Hex (board game)
Encyclopedia
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.
, 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). However, according to Sylvia Nasar's biography of John Forbes 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.
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 bear varying degrees of similarity to the ancient Asian game of Go
.
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 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:
One might attempt to compensate for the second player's disadvantage by making 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 an easy win for the second player.
, 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.
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.
, and can be classified as a Maker-Breaker game
, a particular type of positional game
.
John Nash
proved in 1952 that a game of Hex cannot end in a tie, and that for a symmetric board there exists a winning strategy for the player who makes the first move (by the strategy-stealing argument
). However, the argument is non-constructive : it only shows the existence of a winning strategy, without describing it explicitly. Finding an explicit strategy has been the main subject of research since then.
An explicit winning strategy with a pairing argument exists on non-symmetrical nxm boards, which leaves only symmetrical nxn boards as the center of interest.
In 1981, Stefan Reisch proved that generalized
Hex on a nxn board is PSPACE-complete
. In the computational complexity theory
, it is widely conjectured that PSPACE-complete problems cannot be solved with efficient (polynomial) algorithms. This result limits the efficiency of the best possible algorithms when considering boards of arbitrary size, but it doesn't rule out the possibility of computing explicit strategies on small boards of a given size.
In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7x7. They extended the method to the 8x8 and 9x9 boards in 2003.
In 2009, Philip Henderson, Broderick Arneson and Ryan B. Hayward completed the analysis of the 8x8 board with a computer search, solving all the possible openings. The same team has solved most 9x9 openings, but some of them are still unknown.
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 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.
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
has some similarities to Hex, but the winning structures (target of game) are different.
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.
involves two players coloring the edges of an arbitrary graph
, each attempting to connect two distinguished vertices with edges of his/her color. It was invented by "the father of information theory", Claude Shannon. A rectangular grid is commonly used for the graph; in this form the game was independently invented by David Gale
, and has been known as Gale, Bridg-It, and Bird Cage.
Unlike Hex, this game is not PSPACE
hard.
, 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.
Board game
A board game is a game which involves counters or pieces being moved on a pre-marked surface or "board", according to a set of rules. Games may be based on pure strategy, chance or a mixture of the two, and usually have a goal which a player aims to achieve...
played on a hexagonal grid
Hex map
A hex map, hex board or hex grid is a gameboard design commonly used in wargames of all scales. The map is subdivided into small regular hexagons of identical size.-Advantages and disadvantages:...
, 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
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
. According to the book A Beautiful Mind
A Beautiful Mind (book)
A Beautiful Mind is an unauthorized biography of Nobel Prize-winning economist and mathematician John Forbes Nash, Jr. by Sylvia Nasar, professor of journalism at Columbia University...
, John Nash
John Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
(one of the game's inventors) advocated 14x14 as the optimal size.
History
The game was invented by the Danish mathematician Piet HeinPiet Hein (Denmark)
Piet Hein was a Danish scientist, mathematician, inventor, designer, author, and poet, often writing under the Old Norse pseudonym "Kumbel" meaning "tombstone"...
, who introduced the game in 1942 at the Niels Bohr Institute, and also independently invented by the mathematician John Nash
John Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
in 1947 at Princeton University. It became known in Denmark under the name Polygon (though Hein called it CON-TAC-TIX); Nash
John Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
's fellow players at first called the game Nash. According to Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
, some of the Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
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 John Forbes 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
Parker Brothers
Parker Brothers is a toy and game manufacturer and brand. Since 1883, the company has published more than 1,800 games; among their best known products are Monopoly, Cluedo , Sorry, Risk, Trivial Pursuit, Ouija, Aggravation, and Probe...
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
Y (game)
]Y is an abstract strategy game which was first described by Claude Shannon in the early 1950s. Y was independently invented in 1953 by Craige Schensted and Charles Titus...
and Havannah
Havannah
Havannah is an abstract strategy board game invented by Christian Freeling. It is played on a base-10 hexagonal board, ten hexes to a side...
. All of these games bear varying degrees of similarity to the ancient Asian game of Go
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
.
Rules
Each player has an allocated color, Red and Blue or White and Black 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 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
Pie rule
The pie rule, sometimes referred to as the swap rule, is a meta-rule used to balance abstract strategy board games. Its use has been first reported in 1909 for a game from the Mancala family. Among recent games, Hex uses this 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
The game can never end in a tie, a fact proved by John NashJohn Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
: 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
Strategy-stealing argument
In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
proves that the first player has a winning strategy
Strategy (game theory)
In game theory, a player's strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour...
as follows:
- Since Hex is a finite, perfect informationPerfect informationIn game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
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.
One might attempt to compensate for the second player's disadvantage by making 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 an easy win for the second player.
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 rhombusRhombus
In Euclidean geometry, a rhombus or rhomb is a convex quadrilateral whose four sides all have the same length. The rhombus is often called a diamond, after the diamonds suit in playing cards, or a lozenge, though the latter sometimes refers specifically to a rhombus with a 45° angle.Every...
, 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.
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 toLadders
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
Hex is a connection gameConnection game
A connection game is a type of abstract strategy game in which players attempt to complete a specific type of connection with their pieces. This could involve forming a path between two or more goals, completing a closed loop, or connecting all of one's pieces so they are adjacent to each other....
, and can be classified as a Maker-Breaker game
Maker-Breaker game
Maker-Breaker games are a subclass of positional games.It is a two-person game with complete information played on a hypergraph where V is an arbitrary set and H is a family of subsets of V , called the winning sets...
, a particular type of positional game
Positional game
Positional games are a class of combinatorial games. Well-known games that fall into this class include tic-tac-toe, hex and Shannon switching game....
.
John Nash
John Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
proved in 1952 that a game of Hex cannot end in a tie, and that for a symmetric board there exists a winning strategy for the player who makes the first move (by the strategy-stealing argument
Strategy-stealing argument
In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
). However, the argument is non-constructive : it only shows the existence of a winning strategy, without describing it explicitly. Finding an explicit strategy has been the main subject of research since then.
An explicit winning strategy with a pairing argument exists on non-symmetrical nxm boards, which leaves only symmetrical nxn boards as the center of interest.
In 1981, Stefan Reisch proved that generalized
Generalized game
In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...
Hex on a nxn board is PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
. In the computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, it is widely conjectured that PSPACE-complete problems cannot be solved with efficient (polynomial) algorithms. This result limits the efficiency of the best possible algorithms when considering boards of arbitrary size, but it doesn't rule out the possibility of computing explicit strategies on small boards of a given size.
In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7x7. They extended the method to the 8x8 and 9x9 boards in 2003.
In 2009, Philip Henderson, Broderick Arneson and Ryan B. Hayward completed the analysis of the 8x8 board with a computer search, solving all the possible openings. The same team has solved most 9x9 openings, but some of them are still unknown.
The determinacy
Determinacy
In set theory, a branch of mathematics, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies.-Games:...
of Hex has other mathematical consequences: it can be used to prove the two-dimensional Brouwer fixed point theorem
Brouwer fixed point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after Luitzen Brouwer. It states that for any continuous function f with certain properties there is a point x0 such that f = x0. The simplest form of Brouwer's theorem is for continuous functions f from a disk D to...
, as David Gale
David Gale
David Gale was a distinguished American mathematician and economist. He was a Professor Emeritus at University of California, Berkeley, affiliated with departments of Mathematics, Economics, and Industrial Engineering and Operations Research...
showed in 1979, and the determinacy of higher-dimensional variants proves the fixed-point theorem in general.
Blockbusters
Hex had an incarnation as the question board from the television game show BlockbustersBlockbusters (US game show)
Blockbusters is an American game show which had two separate runs in the 1980s. Created by Steve Ryan for Mark Goodson Productions, the first series debuted on NBC on October 27, 1980 and aired until April 23, 1982. In the first series, a team of two family members competed against a solo contestant...
. 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
The game of YY (game)
]Y is an abstract strategy game which was first described by Claude Shannon in the early 1950s. Y was independently invented in 1953 by Craige Schensted and Charles Titus...
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
Havannah
Havannah is an abstract strategy board game invented by Christian Freeling. It is played on a base-10 hexagonal board, ten hexes to a side...
has some similarities to Hex, but the winning structures (target of game) are different.
Mind Ninja
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.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
The Shannon switching gameShannon switching game
The Shannon switching game is an abstract strategy game for two players, invented by Claude Shannon, and independently invented by David Gale; it has also been known as Gale, Bridg-It, and Bird Cage....
involves two players coloring the edges of an arbitrary graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, each attempting to connect two distinguished vertices with edges of his/her color. It was invented by "the father of information theory", Claude Shannon. A rectangular grid is commonly used for the graph; in this form the game was independently invented by David Gale
David Gale
David Gale was a distinguished American mathematician and economist. He was a Professor Emeritus at University of California, Berkeley, affiliated with departments of Mathematics, Economics, and Industrial Engineering and Operations Research...
, and has been known as Gale, Bridg-It, and Bird Cage.
Unlike Hex, this game is not PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
hard.
Pex
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
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 trivalentCubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
, 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.
External links
- HexWiki, a wikiWikiA wiki is a website that allows the creation and editing of any number of interlinked web pages via a web browser using a simplified markup language or a WYSIWYG text editor. Wikis are typically powered by wiki software and are often used collaboratively by multiple users. Examples include...
dedicated to Hex - Thesis on Hex history, classification and complexity
- Game of Hex at MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
with links to related mathematical papers - 1x1 to 6x6 opening strategy by Jack van Rijswijck of the University of AlbertaUniversity of AlbertaThe University of Alberta is a public research university located in Edmonton, Alberta, Canada. Founded in 1908 by Alexander Cameron Rutherford, the first premier of Alberta and Henry Marshall Tory, its first president, it is widely recognized as one of the best universities in Canada...
- University of Alberta Computer Hex Research Group
- Theory page gathering theoretical work on the game.
- BGG Board Game Geek entry on Hex
- Hecks boards Hecks board application from Wolfram Demonstration Project
- Hexy Hexy is a strong Hex player for Windows