Hex (also called Nash) is a two-player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash.

It is traditionally played on an 11×11 rhombus board, although 13×13 and 19×19 boards are also popular. It can also be played with paper and pencil on hexagonally ruled graph paper. The board is composed of hexagons called cells or hexes. Each player is assigned a pair of opposite sides of the board, which they must try to connect by alternately placing a stone of their color onto any empty hex. Once placed, the stones are never 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.

Despite the simplicity of its rules, the game has deep strategy and sharp tactics. It also has profound mathematical underpinnings related to the Brouwer fixed-point theorem, matroids and graph connectivity.

Game type Hex is a finite, two-player perfect information game, and an abstract strategy game that belongs to the general category of connection games. It can be classified as a Maker-Breaker game, a particular type of positional game. Since the game can never end in a draw, Hex is also a determined game.

Hex is a special case of the "node" version of the Shannon switching game. Hex can be played as a board game or as a paper-and-pencil game.

Rules

Hex is played on a rhombic grid of hexagons, typically of size 11×11, although other sizes are also possible. Each player has an allocated color, conventionally red and blue, or black and white. Each player is also assigned two opposite board edges. The hexagons on each of the four corners belong to both adjacent board edges.

The players take turns placing a stone of their color on a single cell on the board. The most common convention is for Red or Black to go first. Once placed, stones are not moved, replaced, or removed from the board. Each player's goal is to form a connected path of their own stones linking their two board edges. The player who completes such a connection wins the game.

To compensate for the first player's advantage, the swap rule (also called the pie rule) is normally used. This rule allows the second player to choose whether to switch positions with the first player after the first player makes the first move.

When it is clear to both players who will win the game, it is customary, but not required, for the losing player to resign. In practice, most games of Hex end with one of the players resigning.

History

Invention 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.

Nash's claim The game was rediscovered in 1948 or 1949 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. Nash insisted that he discovered the game independently of Hein, but there is some doubt about this, as it is known that there were Danish people, including Aage Bohr, who played Hex at Princeton in the 1940s, so that Nash may have subconsciously picked up the idea. Hein wrote to Gardner in 1957 expressing doubt that Nash discovered Hex independently. Gardner was unable to independently verify or refute Nash's claim. Gardner privately wrote to Hein: "I discussed it with the editor, and we decided that the charitable thing to do was to give Nash the benefit of the doubt. ... The fact that you invented the game before anyone else is undisputed. Any number of people can come along later and say that they thought of the same thing at some later date, but this means little and nobody really cares." In a later letter to Hein, Gardner also wrote: "Just between you and me, and off the record, I think you hit the nail on the head when you referred to a 'flash of a suggestion' which came to Mr. Nash from a Danish source, and which he later forgot about. It seems the most likely explanation."

Published games

The game was first published by Hein under the name Polygon in the Danish newspaper Politiken on 26 December 1942. It was distributed in the form of 50-sheet game pads. Each sheet contained an 11×11 empty board that could be played on with pencils or pens.

In 1952, Parker Brothers marketed a version of the game under the name "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 50-sheet pad of ruled Hex grids.

Hex is currently published by Nestorgames in a 11×11 size, a 14×14, and a 19×19 size. The Game Crafter publishes an 11×11 and 14×14 set.

Shannon's Hex machine About 1950, Claude Shannon and E. F. Moore constructed an analog Hex playing machine, which was essentially a resistance network with resistors for edges and light bulbs 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 create strong computer players.Anshelevich, V. (2002). A Hierarchical Approach to Computer Hex.

Research timeline It was known to Hein in 1942 that Hex cannot end in a draw; in fact, one of his design criteria for the game was that "exactly one of the two players can connect their two sides".

It was also known to Hein that the first player has a theoretical winning strategy.

In 1952, John Nash wrote up an existence proof that on symmetrical boards, the first player has a winning strategy.

In 1964, the 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.

In 1981, Stefan Reisch showed that Hex is 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.

Starting about 2006, the field of computer Hex came to be dominated by Monte Carlo tree search methods borrowed from successful computer implementations of Go. These replaced earlier implementations that combined Shannon's Hex-playing heuristic with alpha-beta search. On the subject of early Computer Hex, notable early implementations include Dolphin Microware's Hexmaster, published in the early 1980s for Atari 8-bit computers.

Until 2019, humans remained better than computers at least on big boards such as 19x19, but on 30 October 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: zero-learning as in AlphaZero boardsize invariance thanks to fully convolutional neural networks (as in U-Net) and pooling and growing architectures (the program can learn on a small board, and then extrapolate on a big board, as opposed to justified popular claims about earlier artificial intelligence methods such as the original AlphaGo).

Strategy

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 their sides of the board and win. The final stage of the game, if necessary, consists of filling in the empty spaces in the path.Browne p.

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.Browne, p.28 One of the simplest such patterns is the bridge, which consists of a diamond of two stones of the same color and two empty spaces, where the two stones do not touch.Browne, pp. 29–30 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.Browne, pp. 71–77 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.Browne, p. 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.Lasker, p.

Mathematical theory Determinacy It is not difficult to convince oneself by exposition, that hex cannot end in a draw, referred to as the "hex theorem". I.e., no matter how the board is filled with stones, there will always be one and only one player who has connected their edges. This fact was known to Piet Hein in 1942, who mentioned it as one of his design criteria for Hex in the original Politiken article. Hein also stated this fact as "a barrier for your opponent is a connection for you". John Nash wrote up a proof of this fact around 1949, but apparently did not publish the proof. Its first exposition appears in an in-house technical report in 1952,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 in which Nash states that "connection and blocking the opponent are equivalent acts". A more rigorous proof was published by John R. Pierce in his 1961 book Symbols, Signals, and Noise.

An informal proof of the no-draw property of Hex can be sketched as follows: in a completely filled Hex board, consider the connected component of one of the red edges, i.e. all the red hexagons directly or indirectly connected to that red edge. The concept of a connected component is well-defined because in a hexagonal grid, two cells can only meet in an edge or not at all; it is not possible for cells to overlap in a single point. This component either includes the opposite red edge, in which case Red has a winning path from one edge to the other, or else it does not, in which case the blue stones along the boundary of the connected component form a winning path for Blue.