Editing Hex (board game) (section)

==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).