2026-07-23T16:54:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11706 2024-03-06T10:48:30Z ddc:004 open_access

Strategy-Stealing Is Non-Constructive Bodwin, Greg Grossman, Ofer PSPACE-hard Hex Combinatorial Game Theory In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists? We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Greg Bodwin and Ofer Grossman 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.21 urn:nbn:de:0030-drops-117069 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.21 eng https://creativecommons.org/licenses/by/3.0/legalcode