Editing Hex (board game) (section)

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