Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.21
URN: urn:nbn:de:0030-drops-117069
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11706/
Bodwin, Greg ; Grossman, Ofer
Strategy-Stealing Is Non-Constructive
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bodwin_et_al:LIPIcs:2020:11706,
author = {Greg Bodwin and Ofer Grossman},
title = {{Strategy-Stealing Is Non-Constructive}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {21:1--21:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11706},
URN = {urn:nbn:de:0030-drops-117069},
doi = {10.4230/LIPIcs.ITCS.2020.21},
annote = {Keywords: PSPACE-hard, Hex, Combinatorial Game Theory}
}
| Keywords: | PSPACE-hard, Hex, Combinatorial Game Theory | |
| Seminar: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 06.01.2020 |
