View source for Module:Strategy-stealing argument

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.  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 tell you that there exists a winning strategy, the proof gives you 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.

== Example ==
A strategy-stealing argument can be used on the example of the game of [[tic-tac-toe]], for a board and winning rows of any size.<ref name="b"/><ref name="hj"/> Suppose that the second player (P2) is using a strategy ''S'' which guarantees a win. The first player (P1) places an '''X''' in an arbitrary position. P2 responds by placing an '''O''' according to ''S''. But if P1 ignores the first random '''X''', P1 is now in the same situation as P2 on P2's first move: a single enemy piece on the board. P1 may therefore make a move according to ''S'' – that is, unless ''S'' calls for another '''X''' to be placed where the ignored '''X''' is already placed. But in this case, P1 may simply place an '''X''' in some other random position on the board, the net effect of which will be that one '''X''' is in the position demanded by ''S'', while another is in a random position, and becomes the new ignored piece, leaving the situation as before. Continuing in this way, ''S'' is, by hypothesis, guaranteed to produce a winning position (with an additional ignored '''X''' of no consequence). But then P2 has lost – contradicting the supposition that P2 had a guaranteed winning strategy. Such a winning strategy for P2, therefore, does not exist, and tic-tac-toe is either a forced win for P1 or a tie. (Further analysis shows it is in fact a tie.)

The same proof holds for any [[strong positional game]].

== Chess ==
{{Main|First-move advantage in chess}}
{{Chess diagram small
|tright
|Philidor, 1777
|  |  |  |  |  |  |  | 
|  |  |  |  |  |  |  | 
|  |  |  |  |  |  |  | 
|  |  |  |  |  |  |  | 
|ql|  |  |  |  |  |  | 
|  |  |  |kl|  |  |  | 
|  |rd|  |  |  |  |  | 
|  |kd|  |  |  |  |  | 
|Black is in zugzwang, since they must move their rook away from their king.
}}
There is a class of [[chess]] positions called [[Zugzwang]] in which the player obligated to move would prefer to "pass" if this were allowed. Because of this, the strategy-stealing argument cannot be applied to chess.<ref name="ant">{{citation
 | last1 = Bishop | first1 = J. M.
 | last2 = Nasuto | first2 = S. J.
 | last3 = Tanay | first3 = T.
 | last4 = Roesch | first4 = E. B.
 | last5 = Spencer | first5 = M. C.
 | editor-last = Müller | editor-first = Vincent C.
 | contribution = HeX and the single anthill: Playing games with Aunt Hillary
 | doi = 10.1007/978-3-319-26485-1_22
 | pages = 369–390
 | publisher = Springer
 | series = Synthese Library
 | title = Fundamental Issues of Artificial Intelligence
 | volume = 376
 | year = 2016| url = https://philpapers.org/archive/BISHAT-3.pdf
 }}. See in particular Section 22.2.2.2, The Strategy-Stealing Argument, [https://books.google.com/books?id=MZFPDAAAQBAJ&pg=PA376 p.&nbsp;376].</ref> It is not currently known whether White or Black can force a win with optimal play, or if both players can force a draw. However, virtually all students of chess consider White's first move to be an advantage and statistics from modern high-level games have White's winning percentage about 10%{{Citation needed|date=January 2022}} higher than Black's.

== Go ==
In [[Go (game)|Go]] passing is allowed. When the starting position is symmetrical (empty board, neither player has any points), this means that the first player could steal the second player's winning strategy simply by giving up the first move. Since the 1930s, however,<ref>{{Citation | last = Fairbairn | first = John | url = http://senseis.xmp.net/?HistoryOfKomi | title = History of Komi | access-date = 2010-04-09 }}</ref> the second player is typically awarded some [[komidashi|compensation points]], which makes the starting position asymmetrical, and the strategy-stealing argument will no longer work.

An elementary strategy in the game is "[[mirror go]]", where the second player performs moves which are diagonally opposite those of this opponent. This approach may be defeated using [[Ladder (Go)|ladder tactic]]s, [[ko fight]]s, or successfully competing for control of the board's central point.

== Constructivity ==
The strategy-stealing argument shows that the second player cannot win, by means of deriving a contradiction from any hypothetical winning strategy for the second player. The argument is commonly employed in games where there can be no draw, by means of the [[law of the excluded middle]]. However, it does not provide an explicit strategy for the first player, and because of this it has been called non-constructive.<ref name="ant" /> This raises the question of how to actually compute a winning strategy.

For games with a finite number of reachable positions, such as [[chomp]], a winning strategy can be found by exhaustive search.<ref>{{Cite web|url=https://rjlipton.wordpress.com/2013/10/02/stealing-strategies/|title=Stealing Strategies|last=rjlipton|date=2013-10-02|website=Gödel's Lost Letter and P=NP|language=en|access-date=2019-11-30}}</ref> However, this might be impractical if the number of positions is large.

In 2019, Greg Bodwin and Ofer Grossman proved that the problem of finding a winning strategy is [[PSPACE-complete|PSPACE-hard]] in two kinds of games in which strategy-stealing arguments were used: the [[Minimum Poset Game|minimum poset game]] and the symmetric [[Maker-Maker game]].<ref>{{cite arXiv|last=Bodwin|first=Greg|last2=Grossman|first2=Ofer|date=2019-11-15|title=Strategy-Stealing is Non-Constructive|eprint=1911.06907|class=cs.DS}}</ref>

== References ==
{{Reflist|2}}
{{Game theory}}

[[Category:Mathematical games]]
[[Category:Arguments]]