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 two player abstract strategy board game in which players attempt to connect opposite sides of a hexagonal board. Hex was invented by mathematician and poet Piet Hein in 1942 and independently by John Nash in 1948.
It is traditionally played on an 11×11 rhombus board, although 13×13 and 19×19 boards are also popular. Each player is assigned a pair of opposite sides of the board which they must try to connect by taking turns placing a stone of their color onto any empty space. Once placed, the stones are unable to be moved or removed. A player wins when they successfully connect their sides together through a chain of adjacent stones. Draws are impossible in Hex due to the topology of the game board.
The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed-point theorem. 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 artificial intelligence.
Hex is a connection game, 122 a particular type of positional game. The game can never end in a draw (tie), :99 in other words, Hex is also a "determined game".and can be classified as a Maker-Breaker game, :
Hex is a finite, perfect information game, and an abstract strategy game that belongs to the general category of connection games . Hex is a special case of the "node" version of the Shannon switching game. 122:
As a product, Hex is a board game; it may also be played with paper and pencil.
The game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. Although Hein later renamed it to Con-tac-tix,it became known in Denmark under the name Polygon due to an article by Hein in the 26 December 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. Hein wrote to Gardner in 1957 expressing doubt that Nash discovered Hex independently, but Nash insists that he reinvented the game before being exposed to Hein's work. Gardner was unable to independently verify or refute Nash's claim.
In 1952, Parker Brothers marketed a version. They called their version "Hex" and the name stuck.Parker Brothers also sold a version under the "Con-tac-tix" name in 1968. 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. Hex is currently published by Nestorgames in a 11x11 size and a 14x14 size.
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.
Until 2019, humans remained better than computers at least on big boards such as 19x19, but on Oct 30, 2019 the program Mootwo won against the human player with the best ELO rank on LittleGolem, also winner of various tournaments (the game is available here). This program was based on Polygames(an open-source project, initially developed by Facebook Artificial Intelligence Research and several universities ) using a mix of:
In the early 1980s Dolphin Microware published Hexmaster, an implementation for Atari 8-bit computers.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. Once placed, stones are not moved, captured or removed from the 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 hexagons on each of the four corners belong to both adjacent sides.
It is not necessary to construct a complete chain between sides or fill up the whole board before the game is decided (but if it does by construction, the player placing the last stone will win); usually only 1/3 to 40% of the board is filled before it becomes obvious that one player or the other can force a win. This is somewhat analogous to chess games ending long before checkmate - the game usually ends with one player or the other resigning.
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.
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. 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 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.
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 first rigorous proof was published by John R. Pierce in his 1961 book Symbols, Signals, and Noise. In 1979, David Gale published a proof which 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:
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:
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 11×11 Hex, there are approximately 2.4×1056 possible legal positions;this compares to 4.6×1046 legal positions in chess.
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 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.[ citation needed ] This compares to 10123 node game tree size of chess.[ citation needed ]
Interesting game tree reductions are available by noting that the board has dual bilateral symmetry as well as 180° rotational symmetry: for each position, a topologically identical position is obtained by flipping the board left-right, top-bottom, or rotating it 180°.
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. ×N hex is the most-central one, suggesting the conjecture that this is true for every N≥1.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 (the most-central) opening move on the 10×10 board. For every N≤10, a winning first move in N
Other connection games with similar objectives but different structures include Shannon switching game and TwixT. Both of these bear some degree of similarity to the ancient Asian game of Go.
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.
The misère variant of Hex. Each player tries to force his opponent to make a chain. Rex is slower than Hex since, on any empty board with equal dimensions, the losing play can delay a loss until the entire board is full.On boards with unequal dimensions, the player whose sides are further apart can win regardless of who plays first. On boards with equal dimensions, 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. On boards with an even number, one of the first player's winning moves is always to place a stone in the accute corner.
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 game based on Hex.It differs from Hex in that it is played on a hexagonal grid of hexagons and a win is achieved by forming one of three 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 weretournaments reported from Brazil, Czech Republic, Denmark, France, Germany, Italy, Netherlands, Norway, Poland, Portugal, Spain, UK and the US.
One of the largest Hex tourneys is organized by the International Committee of Mathematical Games in Paris, France, which is annually held since 2013.
Hex is also part of the Computer Olympiad.
Gomoku, also called Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces on a Go board. It can be played using the 15×15 board or the 19×19 board. Because pieces are typically not moved or removed from the board, Gomoku may also be played as a paper-and-pencil game. The game is known in several countries under different names.
Phutball is a two-player abstract strategy board game described in Elwyn Berlekamp, John Horton Conway, and Richard K. Guy's Winning Ways for your Mathematical Plays.
A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.
Havannah is a two-player abstract strategy board game invented by Christian Freeling. It belongs to the family of games commonly called connection games; its relatives include Hex and TwixT. Havannah has "a sophisticated and varied strategy" and is best played on a base-10 hexagonal board, 10 hex cells to a side.
Y is an abstract strategy board game, first described by John Milnor in the early 1950s. The game was independently invented in 1953 by Craige Schensted and Charles Titus. It is a member of the connection game family inhabited by Hex, Havannah, TwixT, and others; it is also an early member in a long line of games Schensted has developed, each game more complex but also more generalized.
TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games in the series. It is a connection game where players alternate turns placing pegs and links on a pegboard in an attempt to link their opposite sides. The rules are simple but the strategy complex, so young children can play it, but it also appeals to adults. The game has been discontinued except in Germany.
The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory" some time before 1951. Two players take turns coloring the edges of an arbitrary graph. One player has the goal of connecting two distinguished vertices by a path of edges of their color. The other player aims to prevent this by using their color instead. The game is commonly played on a rectangular grid; this special case of the game was independently invented by American mathematician David Gale in the late 1950s and is known as Gale or Bridg-It.
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.
In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage.
The Black Path Game is a two-player board game described and analysed in Winning Ways for your Mathematical Plays. It was invented by Larry Black in 1960.
In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.
The Game of the Amazons is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina. It is a member of the territorial game family, a distant relative of Go and chess. El Juego de las Amazonas is a trademark of Ediciones de Mente.
In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.
PÜNCT is a two-player strategy board game. It is the sixth release in the GIPF project of six abstract strategy games, although it is considered the fifth game in the project. It was released in 2005. PÜNCT won the Games Magazine Best Abstract Strategy game for 2007.
Star is a two-player abstract strategy board game developed by Craige Schensted. 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, however, the result is based on a player having a higher final score rather than achieving a specific goal. He has since developed a slightly more complicated version called *Star with better balance between edge and center moves, writing "*Star is what those other games wanted to be."
Hexagonal chess refers to a group of chess variants played on boards composed of hexagon . The best known is Gliński's variant, played on a symmetric 91-cell hexagonal board.
The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, a Chinese scholar in 11th century, estimated that the number of possible board positions is around 10172 in The Dream Pool Essays. In more recent years, research of the game by John H. Conway led to the invention of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).
Kōnane is a two-player strategy board game from Hawaii. It was invented by the ancient Hawaiian Polynesians. The game is played on a rectangular board. It begins with black and white counters filling the board in an alternating pattern. Players then hop over one another's pieces, capturing them similar to checkers. The first player unable to capture is the loser; their opponent is the winner.
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. Connection games typically have simple rules, but complex strategies. They have minimal components and may be played as board games, computer games, or even paper and pencil games.