Editing Hex (board game) (section)

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