Document Open Access Logo

Strategy-Stealing Is Non-Constructive

Authors Greg Bodwin, Ofer Grossman

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.21.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • PSPACE-hard
  • Hex
  • Combinatorial Game Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Greg Bodwin and Ofer Grossman. Strategy-Stealing Is Non-Constructive. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.21

Author Details

Greg Bodwin
  • Georgia Tech, Atlanta, GA, USA
Ofer Grossman
  • MIT, Cambridge, MA, USA

Funding

  • Bodwin, Greg: Supported in part by NSF awards CCF-1717349, DMS-183932 and CCF-1909756.
  • Grossman, Ofer: Supported by the Fannie and John Hertz Foundation fellowship, an NSF GRFP award, NSF CNS-1413920, DARPA/NJIT 491512803, Sloan Foundation 996698, and MIT/IBM W1771646. This work was done in part at the Simons Institute for the Theory of Computing.

References

  1. Wining situation on a Hex Board. URL: https://en.wikipedia.org/wiki/Hex_(board_game)#/media/File:Hex-board-11x11-(2).jpg.
  2. József Beck. Van der Waerden and Ramsey type games. Combinatorica, 1(2):103-116, 1981. Google Scholar
  3. József Beck. Positional games and the second moment method. Combinatorica, 22(2):169-216, 2002. Google Scholar
  4. József Beck. Combinatorial Games: Tic-Tac-Toe Theory, volume 114. Cambridge University Press, 2008. Google Scholar
  5. Jesper Makholm Byskov. Maker-maker and maker-breaker games are PSPACE-complete. BRICS Report Series, 11(14), 2004. Google Scholar
  6. Paul Erdös and John L Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3):298-301, 1973. Google Scholar
  7. Heidi Gebauer. On the clique-game. European Journal of Combinatorics, 33(1):8-19, 2012. Google Scholar
  8. Solomon W Golomb and Alfred W Hales. Hypercube tic-tac-toe. More Games of No Chance, 42:167-180, 2002. Google Scholar
  9. Daniel Grier. Deciding the winner of an arbitrary finite poset game is PSPACE-Complete. In International Colloquium on Automata, Languages, and Programming, pages 497-503. Springer, 2013. Google Scholar
  10. Alfred W Hales and Robert I Jewett. Regularity and positional games. In Classic Papers in Combinatorics, pages 320-327. Springer, 2009. Google Scholar
  11. Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional Games. Springer, 2014. Google Scholar
  12. Christopher Kusch. Problems in Positional Games and Extremal Combinatorics. PhD thesis, FU Berlin, 2017. Google Scholar
  13. Christopher Kusch, Juanjo Rué, Christoph Spiegel, and Tibor Szabó. Random strategies are nearly optimal for generalized Van der Waerden games. Electronic Notes in Discrete Mathematics, 61:789-795, 2017. Google Scholar
  14. Nimrod Megiddo and Christos H Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  15. John F Nash. Some games and machines for playing them, 1952. Google Scholar
  16. Stefan Reisch. Hex ist PSPACE-Vollständig. Acta Informatica, 15(2):167-191, 1981. Google Scholar
  17. Bartel van der Waerden. Beweis einer baudetschen vermutung. Nieuw Arch. Wisk., 19:212-216, 1927. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact