Editing Hex (board game)

{{Short description|Abstract strategy board game}}
{{About|the abstract strategy game|other uses|Hex game (disambiguation)}}
{{Use dmy dates|date=May 2020}}
{{Infobox game
| title         = Hex
| subject_name  = Hex
| image_link    = Hex-board-11x11-(2).svg
| image_caption = 11×11 Hex gameboard showing a winning configuration for Blue
| years         = 1942–present
| genre         = [[Board game]]<br />[[Abstract strategy game]]<br />[[Connection game]]
| players       = 2
| setup_time    = None
| playing_time  = 30 minutes – 2 hours (11×11 board)
| random_chance = None
| skills        = [[Strategy game|Strategy]], tactics
}}

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

It is traditionally played on an 11×11 [[rhombus]] board, although 13×13 and 19×19 boards are also popular. 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]]. The game was first published under the name '''Polygon''' in the Danish newspaper ''Politiken'' on December 26, 1942. It was later 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.

==Game type==
Hex is a finite, 2-player [[perfect information]] game, and an [[abstract strategy game]] that belongs to the general category of ''[[connection game]]s''.<ref name="HexFullStory"/> It can be classified as a [[Maker-Breaker game]],<ref name="HexFullStory">{{cite book |title= Hex, Inside and Out: The Full Story |last1=Hayward |first1=Ryan B.|last2=Toft |first2=Bjarne|year=2019 |publisher= CRC Press}}</ref>{{rp|122}} a particular type of [[positional game]]. Since the game can never end in a [[draw (tie)|draw]],<ref name="HexFullStory"/>{{rp|99}} Hex is also a [[determined game]].

Hex is a special case of the "node" version of the [[Shannon switching game]].<ref name="HexFullStory"/>{{rp|122}} Hex can be played as a [[board game]] or as a [[paper-and-pencil game]].

==Rules==
[[File:HEX 11x11 (47)_flipped.jpg|thumb|The end of a game of Hex on a standard 11×11 board. Here, White wins the game.]]

Hex is played on a [[rhombus|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.<ref name="Gardner1"/> 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 complete 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 [[Danes|Danish]] mathematician [[Piet Hein (scientist)|Piet Hein]], who introduced it in 1942 at the [[Niels Bohr Institute]]. Although Hein later renamed it to Con-tac-tix,<ref name="ContactixManual">{{cite book |title=Con-tac-tix manual |url=https://www.hasbro.com/common/instruct/Con-Tac-Tix.PDF |archive-url=https://ghostarchive.org/archive/20221009/https://www.hasbro.com/common/instruct/Con-Tac-Tix.PDF |archive-date=2022-10-09 |url-status=live |year=1968 |publisher= Parker Brothers}}</ref><ref>{{cite book |last1=Hayward |first1=Ryan B. |last2=Toft |first2=Bjarne |title=Hex, inside and out : the full story |year=2019 |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-0367144258 |page=156}}</ref> 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 Forbes Nash Jr.|John Nash]] at [[Princeton University]].<ref name="Gardner1">{{cite book|title=The Scientific American Book of Mathematical Puzzles & Diversions|url=https://archive.org/details/scientificameric02gard|url-access=registration|last= Gardner|first= M.|year= 1959|publisher= Simon and Schuster|location=N.Y., N.Y.|isbn= 0-226-28254-6|pages=[https://archive.org/details/scientificameric02gard/page/73 73–83]}}</ref><ref>{{cite news|last1=Nasar|first1=Sylvia|title=The Lost Years of a Nobel Laureate|url=https://www.nytimes.com/books/98/06/14/reviews/nasar-nash.html|access-date=23 August 2017|work=The New York Times|date=13 November 1994}}</ref> 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.<ref name="Gardner1"/> 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.<ref>{{cite book |last1=Hayward |first1=Ryan B. |last2=Toft |first2=Bjarne |title=Hex, inside and out : the full story |year=2019 |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-0367144258 |pages=127–138}}</ref> 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."<ref name="HexFullStory"/>{{rp|134}} 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."<ref name="HexFullStory"/>{{rp|136}}

===Published games===
[[File:Hex zig-zag.jpg|thumb|A Parker Brothers edition of the game]]
Initially in 1942, Hein distributed the game, which was then called Polygon, 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.<ref name="HexFullStory"/> In 1952, [[Parker Brothers]] marketed a version of the game under the name "Hex", and the name stuck.<ref name="Gardner1"/> [[Parker Brothers]] also sold a version under the "Con-tac-tix" name in 1968.<ref name="ContactixManual"/> Hex was also issued as one of the games in the 1974 3M Paper Games Series; the game contained a {{convert|5+1/2|x|8+1/2|in|adj=on}} 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.<ref>{{Cite web|title=nestorgames - fun to take away|url=https://www.nestorgames.com/#hexset_detail|access-date=2020-09-03|website=www.nestorgames.com}}</ref>

===Shannon's Hex machine===
About 1950, [[Claude Shannon]] and [[Edward F. Moore|E. F. Moore]] constructed an analog Hex playing machine, which was essentially a resistance network with resistors for edges and light bulbs for vertices.<ref>{{cite journal | last1 = Shannon | first1 = C. | year = 1953 | title = Computers and Automata | journal = Proceedings of the Institute of Radio Engineers | volume = 41 | issue = 10| pages = 1234–41 | doi=10.1109/jrproc.1953.274273| s2cid = 51666906 }}</ref> 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.<ref>Anshelevich, V. (2002).  A Hierarchical Approach to Computer Hex.</ref>

===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".<ref name="HexFullStory"/>{{rp|29}}

It was also known to Hein that the first player has a theoretical winning strategy.<ref name="HexFullStory"/>{{rp|42}}

In 1952, John Nash wrote up an existence proof that on symmetrical boards, the first player has a winning strategy.<ref name="HexFullStory"/>{{rp|97}}

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.<ref>{{cite journal | last1 = Lehman | first1 = Alfred | year = 1964 | title = A Solution of the Shannon Switching Game | journal = JSIAM | volume = 12 | issue = 4 | pages= 687–725 | publisher = Society for Industrial and Applied Mathematics }}</ref>

In 1981, the Stefan Reisch showed that Hex is PSPACE-complete.<ref>{{cite journal | last1 = Reisch | first1 = Stefan | year = 1981 | title = Hex ist PSPACE-vollständig | journal = Acta Informatica | volume = 15 | issue = 2 | pages = 167–191 | doi=10.1007/BF00288964 | s2cid = 9125259 }}</ref>

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|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 machine|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.<ref name="kucherawy198401">{{Cite magazine |last=Kucherawy |first=Murray |author-link=Murray Kucherawy |date=January 1984 |title=Hexmaster |url=https://archive.org/details/1984-01-anticmagazine/page/n111 |magazine=Antic |page=112 |access-date=2019-01-18}}</ref>

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 [https://littlegolem.net/jsp/game/game.jsp?gid=2129789 here]). This program was based on Polygames<ref>{{Citation|title=facebookincubator/Polygames|date=2020-05-28|url=https://github.com/facebookincubator/Polygames|publisher=Facebook Incubator|access-date=2020-05-29}}</ref> (an open-source project, initially developed by [[:fr:Facebook Artificial Intelligence Research|Facebook Artificial Intelligence Research]] and several universities<ref>{{Cite web|title=Open-sourcing Polygames, a new framework for training AI bots through self-play|url=https://ai.facebook.com/blog/open-sourcing-polygames-a-new-framework-for-training-ai-bots-through-self-play/|website=ai.facebook.com|language=en|access-date=2020-05-29}}</ref>) using a mix of:<ref>{{cite arXiv|last1=Cazenave|first1=Tristan|last2=Chen|first2=Yen-Chi|last3=Chen|first3=Guan-Wei|last4=Chen|first4=Shi-Yu|last5=Chiu|first5=Xian-Dong|last6=Dehos|first6=Julien|last7=Elsa|first7=Maria|last8=Gong|first8=Qucheng|last9=Hu|first9=Hengyuan|last10=Khalidov|first10=Vasil|last11=Li|first11=Cheng-Ling|last12=Lin|first12=Hsin-I|last13=Lin|first13=Yu-Jin|last14=Martinet|first14=Xavier |last15=Mella|first15=Vegard|last16=Rapin|first16=Jeremy|last17=Roziere|first17=Baptiste|last18=Synnaeve|first18=Gabriel |last19=Teytaud|first19=Fabien|last20=Teytaud|first20=Olivier|last21=Ye|first21=Shi-Cheng|last22=Ye|first22=Yi-Jun|last23=Yen|first23=Shi-Jim|last24=Zagoruyko|first24=Sergey|date=2020-01-27|title=Polygames: Improved Zero Learning|class=cs.LG|eprint=2001.09832}}</ref>
* zero-learning as in [[AlphaZero]]
* boardsize invariance thanks to fully convolutional neural networks (as in [[U-Net]]) and [[Convolutional neural network#Pooling|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<ref>{{cite arXiv|last=Marcus|first=Gary|date=2018-01-17|title=Innateness, AlphaZero, and Artificial Intelligence|class=cs.AI|eprint=1801.05667}}</ref> about earlier artificial intelligence methods such as the original AlphaGo).

==Strategy==
{{Expand section|1=general strategy and typical endgames|section=1|date=November 2023|small=no|talksection=Talk:Hex_(board_game)#Strategy_section,_redux}}

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.<ref name="Browne p">Browne p.</ref>

[[Image:Hex situation bridge.svg|thumb|right|A "bridge" (A ↔ C) is a simple example of a safely connected pattern. It consists of two stones of the same color (A and C), and a pair of open spaces (B and D).]]

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.<ref>Browne, p.28</ref> 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.<ref>Browne, pp. 29–30</ref> 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.<ref>Browne, pp. 71–77</ref> 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.<ref name="Browne p"/>

There are weaker types of connectivity than "safely connected" which exist between stones or between safely connected patterns which have multiple spaces between them.<ref name="Browne, p">Browne, p.</ref> The middle part of the game consists of creating a network of such weakly connected stones and patterns<ref name="Browne, p"/> 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.<ref name="Browne, p"/>

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.<ref name="Browne p"/> The skill is somewhat similar to the visualization of patterns, sequencing of moves, and evaluating of positions in chess.<ref>Lasker, p.</ref>

==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.<ref name="HexFullStory"/>{{rp|29}}
Hein also stated this fact as "a barrier for your opponent is a
connection for you".<ref name="HexFullStory"/>{{rp|35}} John Nash wrote up a proof of this fact around 1949,<ref>{{cite journal |last1=Hayward |first1=Ryan B. |last2=Rijswijck, van |first2=Jack |title=Hex and combinatorics |journal=Discrete Mathematics |date=6 October 2006 |volume=306 |issue=19–20 |pages=2515–2528 |doi=10.1016/j.disc.2006.01.029 |doi-access= }}</ref> but apparently did not publish the proof.  Its first exposition appears in an in-house technical report in 1952,<ref>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 {{webarchive |url=https://web.archive.org/web/20170121094752/https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf |date=21 January 2017 }}</ref> 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''.<ref>{{cite book |last1=Hayward |first1=Ryan B. |last2=Toft |first2=Bjarne |title=Hex, inside and out : the full story |year=2019 |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-0367144258 |page=99}}</ref> In 1979, [[David Gale]] published a proof that the determinacy of Hex is equivalent to the two-dimensional [[Brouwer fixed-point theorem]], and that the determinacy of higher-dimensional ''n''-player variants proves the fixed-point theorem in general.<ref>{{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|doi=10.2307/2320146|jstor=2320146|issue=10|publisher=Mathematical Association of America}}</ref> 

An informal proof of the no-draw property of Hex can be sketched as follows: consider the connected component of one of the red edges. This component either includes the opposite red edge, in which case Red has a connection, or else it does not, in which case the blue stones along the boundary of the connected component form a winning path for Blue.  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.

===First-player win, informal existence proof===

In Hex without the [[swap rule]] on any board of size ''n''x''n'', the first player has a theoretical winning strategy. This fact was mentioned by Hein in his notes for a lecture he gave in 1943: "in contrast to most other games, it can be proved that the first player in theory always can win, that is, if she could see to the end of all possible lines of play".<ref name="HexFullStory"/>{{rp|42}} 

All known proofs of this fact are non-constructive, i.e., the proof gives no indication of what the actual winning strategy is.   Here is a condensed version of a proof that is attributed to John Nash c. 1949.<ref name="Gardner1"/> The proof works for a number of games including Hex, and has come to be called the [[strategy-stealing argument]].

# Since Hex is a finite two-player game with perfect information either the first or second player has a winning strategy, or both can force a draw by [[Zermelo's theorem (game theory)|Zermelo's theorem]].
# Since draws are impossible (see above), we can conclude that either the first or second player has a winning strategy.
# Let us assume that the second player has a winning strategy.
# The first player can now adopt the following strategy.  They make an arbitrary move.  Thereafter they play the winning second player strategy assumed above. If in playing this strategy, they are required to play on the cell where an arbitrary move was made, they make another arbitrary move.<ref group="note">If the board has been completely filled, then one player must have won already, and it must be the first player since they have been playing a winning strategy.</ref>  In this way they play 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 never a disadvantage. Therefore, the first player can win.
# Because we have now contradicted our assumption that there is a winning strategy for the second player, we conclude that there is no winning strategy for the second player.
# Consequently, there must be a winning strategy for the first player.

===Computational complexity===
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]].<ref>{{Cite journal|doi = 10.1145/321978.321989|title = A Combinatorial Problem Which is Complete in Polynomial Space|year = 1976|last1 = Even|first1 = S.|last2 = Tarjan|first2 = R. E.|journal = Journal of the ACM|volume = 23|issue = 4|pages = 710–719|s2cid = 8845949|doi-access = free}}</ref>
A strengthening of this result was proved by Reisch by reducing the [[True quantified Boolean formula|quantified Boolean formula problem]] in [[conjunctive normal form]] to Hex.<ref>{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Informatica | issue = 2 | year = 1981 | pages = 167–191 |  volume=15 | doi=10.1007/bf00288964| s2cid = 9125259 }}</ref> This result means that there is no efficient (polynomial time in board size) algorithm to solve an arbitrary Hex position unless there is an efficient algorithm for all PSPACE problems, which is widely believed not to be the case.<ref>Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach". Cambridge University Press, 2009. Section 4.3</ref> However, it doesn't rule out the possibility of a simple winning strategy for the initial position (on boards of arbitrary size), or a simple winning strategy for all positions on a board of a particular size.

In 11×11 Hex, the state space complexity is approximately 2.4×10<sup>56</sup>;<ref>{{cite book|last1=Browne|first1=C|title=Hex Strategy|date=2000|publisher=A.K. Peters, Ltd.|location=Natick, MA|isbn=1-56881-117-9|pages=5–6}}</ref> versus 4.6×10<sup>46</sup> for chess.<ref>{{cite web|last1=Tromp |first1=J |title=Number of chess diagrams and positions |url=http://homepages.cwi.nl/~tromp/chess/chess.html |website=John's Chess Playground |url-status=bot: unknown |archive-url=https://web.archive.org/web/20110629215923/http://homepages.cwi.nl/~tromp/chess/chess.html |archive-date=29 June 2011}}</ref> The game tree complexity is approximately 10<sup>98</sup><ref>H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. </ref> versus 10<sup>123</sup> for chess.<ref>Victor Allis (1994). ''Searching for Solutions in Games and Artificial Intelligence''. Ph.D. Thesis, University of Limburg, pdf, 6.3.9 Chess pp. 171</ref>

==Computed strategies for smaller boards==
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.<ref>[http://zernike.uwinnipeg.ca/~s_liao/pdf/adcog21.pdf On a decomposition method for finding winning strategy in Hex game] {{webarchive|url=https://web.archive.org/web/20120402234617/http://zernike.uwinnipeg.ca/~s_liao/pdf/adcog21.pdf |date=2 April 2012 }}, Jing Yang, Simon Liao and Mirek Pawlak, 2002</ref> 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.<ref>Unpublished white papers, formerly @ www.ee.umanitoba.com/~jingyang/</ref> 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.<ref>[http://webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Solving 8x8 Hex], {{webarchive |url=https://web.archive.org/web/20110716030553/http://webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf |date=16 July 2011 }}, P. Henderson, B. Arneson, and R. Hayward, Proc. IJCAI-09 505-510 (2009)</ref> 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.<ref>{{cite journal
|url=http://webdocs.cs.ualberta.ca/~hayward/papers/pawlhayw.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://webdocs.cs.ualberta.ca/~hayward/papers/pawlhayw.pdf |archive-date=2022-10-09 |url-status=live
|title=Scalable Parallel DFPN Search
|last1=Pawlewicz |first1=Jakub |last2=Hayward |first2=Ryan 
|date=2013
|access-date=2014-05-21
|journal=Proc. Computers and Games}}</ref>
Since Gardner first postulated in his column in Scientific American in 1957, albeit speciously, that any first play on the short diagonal is a winning play,<ref>Gardner, Martin, Scientific American, July, 1957, pgs 145-151</ref> for all solved game boards up to n=9, that has indeed been the case. In addition, for all boards except n=2 and n=4, there have been numerous additional winning first moves; the number of winning first moves generally is ≥ n²/2.

==Variants==
Other connection games with similar objectives but different structures include [[Shannon switching game]] (also known as Gale and Bridg-It) and [[TwixT]]. Both of these bear some degree of similarity to the ancient Chinese game of [[Go (board game)|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.

=== Board sizes ===
Popular dimensions other than the standard 11×11 are 13×13 and 19×19 as a result of the game's relationship to the older game of [[Go (board game)|Go]].  According to the book ''[[A Beautiful Mind (book)|A Beautiful Mind]]'', [[John Forbes Nash Jr.|John Nash]] (one of the game's inventors) advocated 14×14 as the optimal size.

=== Rex (Reverse Hex) ===
The [[misère]] variant of Hex is called "Rex", in which each player tries to force their opponent to make a chain.  Rex is slower than Hex since, on any empty board with equal dimensions, the losing player can delay a loss until the entire board is full.<ref name="CRC Press">{{cite book |last1=Hayward |first1=Ryan B. |last2=Toft |first2=Bjarne |title=Hex, inside and out : the full story |year=2019 |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-0367144258 |page=175}}</ref>  On boards with unequal dimensions, the player whose sides are further apart can win regardless of who plays first.<ref>{{cite book |last1=Hayward |first1=Ryan B. |last2=Toft |first2=Bjarne |title=Hex, inside and out : the full story |year=2019 |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-0367144258 |page=154}}</ref>   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.<ref>Gardner (1959) p.78</ref><ref>Browne (2000) p.310</ref>  On boards with an even number, one of the first player's winning moves is always to place a stone in the acute corner.<ref name="CRC Press"/>

===''Blockbusters''===
Hex had an incarnation as the question board from the television game show ''[[Blockbusters (U.S. 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.

===Y===
{{Main article|Y (game)}}

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===
{{Main article|Havannah (board game)}}

Havannah is a game based on Hex.<ref>{{cite web |last1=Freeling |first1=Christian |title=How I invented games and why not |url=https://www.mindsports.nl/index.php/how-i-invented-games-and-why-not/organicity?start=5 |website=MindSports |access-date=19 October 2020}}</ref> It too has a board space composed of hexagonal tiles, however the board is itself in the shape of a large hexagon, and a win is achieved by forming one of three patterns.

=== Projex ===
Projex is a variation of Hex played on a [[real projective plane]], where the players have the goal of creating a [[Contractible space|noncontractible]] loop.<ref>{{Cite web|url=https://boardgamegeek.com/boardgame/31805/projex|title=Projex|website=BoardGameGeek|access-date=2018-02-28}}</ref> Like in Hex, there are no ties, and there is no position in which both players have a winning connection.

===Dark Hex===
Dark Hex (also known as Phantom Hex) is an imperfect information version of Hex.<ref>{{cite web |last1=Tapkan |first1=M.Bedir |title=Dark Hex: A Large Scale Imperfect Information Game |date=2022 |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=mUiNYg8AAAAJ&citation_for_view=mUiNYg8AAAAJ:d1gkVwhDpl0C}}</ref> The players are not exposed to each other's stones at any point in the game unless they discover them first. The game is played in the presence of an umpire where each player first verifies the move if its a collision or not. Based on the continuation of this point the game has different versions.
<!-- 

    please don't add arbitrary gamer variants from private websites to the list; see talk page for qualifying criteria.  Additions must have a citation to a published source. -->

==Competition==
As of 2016, there were {{boardgloss|over-the-board}} tournaments reported from Brazil, Czech Republic, Denmark, France, Germany, Italy, Netherlands, Norway, Poland, Portugal, Spain, UK and the US.{{cn|date=June 2023}} One of the largest Hex competitions is organized by the International Committee of Mathematical Games in Paris, France, which is annually held since 2013.{{cn|date=November 2023}} Hex is also part of the [[Computer Olympiad]].<ref>{{Cite web|url=https://icga.org/?page_id=1566|title=ICGA – Computer Olympiad}}</ref> During this competition the pie rule is used.

==Reviews==
*''[[Games & Puzzles]]'' #16<ref>{{cite web | url=https://archive.org/details/sim_games-and-puzzles_1973-08_16/page/8/mode/2up | title=Games and Puzzles 1973-08: Iss 16 | date=August 1973 | publisher=A H C Publications }}</ref>
*''[[:fr:Jeux et Stratégie|Jeux & Stratégie]]'' #6<ref>{{cite web | url=https://archive.org/details/jeux-et-strategie-06/page/48/mode/2up | title=Jeux & stratégie 06 | date=December 1980 }}</ref>

==See also==
* [[Connection game]]s
* [[Mathematical game]]s
* [[GIPF project]], a set of 6 games played on hexavalent grids
*[[Tak (game)|Tak]]

==Notes==
{{Reflist|group=note}}

==References==
{{Reflist|30em}}

==Further reading==
*''Hex Strategy: Making the Right Connections '', Browne C.(2000), A.K. Peters Ltd. Natick, MA. {{ISBN|1-56881-117-9}} (trade paperback, 363pgs)
*''HEX: The Full Story'', Hayward R. with Toft B.(2019), CRC Press Boca Raton, FL. {{ISBN|978-0-367-14422-7}} (paperback)

==External links==
* [http://www.mseymour.ca/hex_book/hexstrat.html Hex: A Strategy Guide] free Net book by Matthew Seymour
* [http://www.mseymour.ca/hex_puzzle/hexpuzzle.html 500 Hex Puzzles] Interactive tactical puzzles by Matthew Seymour
* [https://drericsilverman.com/2021/02/15/a-beginners-guide-to-hex/ A Beginner's Guide to Hex] Hex strategy for beginners by Matthew Seymour and Eric Silverman
* [http://maarup.net/thomas/hex/ Thesis on Hex] {{Webarchive|url=https://web.archive.org/web/20201106232456/http://maarup.net/thomas/hex/ |date=6 November 2020 }} history, classification and complexity
* [https://www.hexwiki.net/ HexWiki], a [[wiki]] dedicated to Hex
* [http://webdocs.cs.ualberta.ca/~hayward/hex/ University of Alberta Computer Hex Research Group]
* [http://hex.kosmanor.com/hex/theory.html Theory page] gathering theoretical work on Hex (moved - top level pages at [https://web.archive.org/web/20041204023334/http://hex.kosmanor.com/hex/theory.html Hex archive]; downloadable material no longer available)
*{{bgg|4112|Hex}}
* [http://mathworld.wolfram.com/GameofHex.html Game of Hex] at [[MathWorld]] with links to related mathematical papers
* [https://web.archive.org/web/20140308080351/http://quatramaran.ens.fr/~viger/hex/ Printable Hex boards] on A4 or A3 paper, for use with standard Go stones
* 300dpi printable Hex board  https://sites.google.com/view/cavegames-hex/home

{{Authority control}}

[[Category:Board games introduced in 1942]]<!-- Hein version -->
[[Category:Board games introduced in 1947]]<!-- Nash version -->
[[Category:Abstract strategy games]]
[[Category:Connection games]]
[[Category:Positional games]]
[[Category:PSPACE-complete problems]]
[[Category:Parker Brothers games]]
[[Category:Paper-and-pencil games]]
[[Category:Solved games]]
[[Category:Theorems in topology]]