Editing Strategy-stealing argument (section)

In [[combinatorial game theory]], the '''strategy-stealing argument''' is a general [[argument]] that shows, for many [[two-player game]]s, that the second player cannot have a guaranteed [[winning strategy]]. The strategy-stealing argument applies to any [[symmetric game]] (one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage.<ref>{{cite arXiv |last1=Bodwin |first1=Greg |title=Strategy-Stealing is Non-Constructive |date=2019-11-15 |eprint=1911.06907 |last2=Grossman |first2=Ofer|class=cs.DS }}</ref>  A key property of a strategy-stealing argument is that it proves that the first player can win (or possibly draw) the game without actually constructing such a strategy.  So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

The argument works by obtaining a [[reductio ad absurdum|contradiction]]. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making an arbitrary first move – which by the conditions above is not a disadvantage – the first player may then also play according to this winning strategy. The result is that both players are guaranteed to win – which is absurd, thus contradicting the assumption that such a strategy exists.

Strategy-stealing was invented by [[John Forbes Nash Jr.|John Nash]] in the 1940s to show that the game of [[hex (board game)|hex]] is always a first-player win, as ties are not possible in this game.<ref name="b">{{citation
 | last = Beck | first = József | author-link = József Beck
 | doi = 10.1017/CBO9780511735202
 | location = Cambridge
 | mr = 2402857
 | publisher = Cambridge University Press
 | series = Encyclopedia of Mathematics and its Applications
 | title = Combinatorial Games: Tic-Tac-Toe Theory
 | title-link = Combinatorial Games: Tic-Tac-Toe Theory
 | at = [https://books.google.com/books?id=AU4dh_eKNfkC&pg=PA65 p.65], [https://books.google.com/books?id=AU4dh_eKNfkC&pg=PA74 74]
 | volume = 114
 | year = 2008| isbn = 9780511735202 }}.</ref> However, Nash did not publish this method, and [[József Beck]] credits its first publication to [[Alfred W. Hales]] and Robert I. Jewett, in the 1963 paper on [[tic-tac-toe]] in which they also proved the [[Hales–Jewett theorem]].<ref name="b" /><ref name="hj">{{citation
 | last1 = Hales | first1 = A. W. | author1-link = Alfred W. Hales
 | last2 = Jewett | first2 = R. I.
 | doi = 10.2307/1993764
 | journal = [[Transactions of the American Mathematical Society]]
 | mr = 0143712
 | pages = 222–229
 | title = Regularity and positional games
 | volume = 106
 | issue = 2 | year = 1963| jstor = 1993764 | doi-access = free
 }}.</ref> Other examples of games to which the argument applies include the [[m,n,k-game|''m'',''n'',''k''-games]] such as [[gomoku]]. In the game of [[Chomp]] strategy stealing shows that the first player has a winning strategy in any rectangular board (other than 1x1).  In the game of [[Sylver coinage]], strategy stealing has been used to show that the first player can win in certain positions called "enders".<ref>{{citation | first = George | last = Sicherman  | title = Theory and Practice of Sylver Coinage | journal = Integers | year = 2002 | volume = 2 | at = G2 | url = http://www.integers-ejcnt.org/cg2/cg2.pdf}}</ref>   In all of these examples the proof reveals nothing about the actual strategy.