Editing Strategy-stealing argument (section)

== 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|last1=Bodwin|first1=Greg|last2=Grossman|first2=Ofer|date=2019-11-15|title=Strategy-Stealing is Non-Constructive|eprint=1911.06907|class=cs.DS}}</ref>