Document Open Access Logo

Quantum-Inspired Combinatorial Games: Algorithms and Complexity

Authors Kyle W. Burke, Matthew Ferland, Shang-Hua Teng

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.11.pdf
  • Filesize: 0.87 MB
  • 20 pages

Document Identifiers

Author Details

Kyle W. Burke
  • Department of Computer Science, Plymouth State University, NH, USA
Matthew Ferland
  • Department of Computer Science, University of Southern California, Los Angeles, CA, USA
Shang-Hua Teng
  • Department of Computer Science, University of Southern California, Los Angeles, CA, USA

Funding

  • Teng, Shang-Hua: Supported by the Simons Investigator Award for fundamental & curiosity driven research and NSF grant CCF-1815254.

Cite As Get BibTex

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FUN.2022.11

Abstract

Recently, quantum concepts inspired a new framework in combinatorial game theory. This transformation uses discrete superpositions to yield beautiful new rulesets with succinct representations that require sophisticated strategies. In this paper, we address the following fundamental questions:  
- Complexity Leap: Can this framework transform polynomial-time solvable games into intractable games?
- Complexity Collapse: Can this framework transform PSPACE-complete games into ones with complexity in the lower levels of the polynomial-time hierarchy? 
We focus our study on how it affects two extensively studied polynomial-time-solvable games: Nim and Undirected Geography. We prove that both Nim and Undirected Geography make a complexity leap over NP, when starting with superpositions: The former becomes Σ₂^p-hard and the latter becomes PSPACE-complete. We further give an algorithm to prove that from any classical starting position, quantumized Undirected Geography remains polynomial-time solvable. Together they provide a nearly-complete characterization for Undirected Geography. Both our algorithm and its correctness proof require strategic moves and graph contraction to extend the matching-based theory for classical Undirected Geography.
Our constructive proofs for both games highlight the intricacy of this framework. The polynomial time robustness of Undirected Geography in this quantum-inspired setting provides a striking contrast to the recent result that the disjunctive sum of two Undirected Geography games is PSPACE-complete. We give a Σ₂^p-hardness analysis of quantumized Nim, even if there are no pile sizes of more than 1.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Quantum-Inspired Games
  • Combinatorial Games
  • Computational Complexity
  • Polynomial Hierarchy
  • çlass{PSPACE}
  • Nim
  • Generalized Geography
  • Snort

Metrics

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

Related Versions

Supplementary Materials

References

  1. Selim G Akl. On the importance of being quantum. Parallel processing letters, 20(03):275-286, 2010. Google Scholar
  2. M. H. Albert, R. J. Nowakowski, and D. Wolfe. Lessons in Play: An Introduction to Combinatorial Game Theory. A. K. Peters, Wellesley, Massachusetts, 2007. Google Scholar
  3. D. Applegate, G. Jacobson, and D. Sleator. Computer analysis of Sprouts. Technical Report CMU-CS-91-144, Carnegie Mellon University Computer Science, 1991. Google Scholar
  4. Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways for your Mathematical Plays, volume 1. A K Peters, Wellesley, Massachsetts, 2001. Google Scholar
  5. Charles L. Bouton. Nim, a game with a complete mathematical theory. Annals of Mathematics, 3(1/4):pp. 35-39, 1901. Google Scholar
  6. Kyle Burke, Matthew Ferland, and Shang-Hua Teng. Quantum combinatorial games: Structures and computational complexity. CoRR, abs/2011.03704, 2020. URL: http://arxiv.org/abs/2011.03704.
  7. Kyle Burke, Matthew Ferland, and Shang-Hua Teng. Winning the war by (strategically) losing battles: Settling the complexity of Grundy-values in undirected geography. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2021. Google Scholar
  8. Kyle W. Burke and Shang-Hua Teng. Atropos: A PSPACE-complete Sperner triangle game. Internet Mathematics, 5(4):477-492, 2008. Google Scholar
  9. Kyle Webster Burke. Science for Fun: New Impartial Board Games. PhD thesis, Boston University, USA, 2009. Google Scholar
  10. Nathann Cohen, Mathieu Hilaire, Nicolas Martins, Nicolas Nisse, and Stéphane Pérennes. Spy-game on graphs. PhD thesis, Inria, 2016. Google Scholar
  11. Nathann Cohen, Nícolas A. Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, and Rudini Sampaio. Spy-game on graphs: Complexity and simple topologies. Theoretical Computer Science, 725:1-15, 2018. Google Scholar
  12. Erik D. Demaine and Robert A. Hearn. Playing games with algorithms: Algorithmic combinatorial game theory. In Michael H. Albert and Richard J. Nowakowski, editors, Games of No Chance 3, volume 56 of Mathematical Sciences Research Institute Publications, pages 3-56. Cambridge University Press, 2009. Google Scholar
  13. Paul Dorbec and Mehdi Mhalla. Toward quantum combinatorial games. arXiv preprint arXiv:1701.02193, 2017. Google Scholar
  14. Jens Eisert, Martin Wilkens, and Maciej Lewenstein. Quantum games and quantum strategies. Physical Review Letters, 83(15):3077, 1999. Google Scholar
  15. David Eppstein. Computational complexity of games and puzzles, 2006. URL: http://www.ics.uci.edu/~eppstein/cgt/hard.html.
  16. Stephen Finbow, Margaret-Ellen Messinger, and Martin F van Bommel. Eternal domination on 3 × n grid graphs. Australas. J Comb., 61:156-174, 2015. Google Scholar
  17. Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199-214, 1981. URL: https://doi.org/10.1016/0097-3165(81)90016-9.
  18. Aviezri S. Fraenkel, Edward R. Scheinerman, and Daniel Ullman. Undirected edge geography. Theor. Comput. Sci., 112(2):371-381, 1993. Google Scholar
  19. David Gale. The game of Hex and the Brouwer fixed-point theorem. American Mathematical Monthly, 10:818-827, 1979. Google Scholar
  20. Adam Glos and Jarosław Adam Miszczak. The role of quantum correlations in cop and robber game. Quantum Studies: Mathematics and Foundations, 6(1):15-26, 2019. Google Scholar
  21. Allan Goff. Quantum tic-tac-toe: A teaching metaphor for superposition in quantum mechanics. American Journal of Physics, 74(11):962-973, 2006. Google Scholar
  22. P. M. Grundy. Mathematics and games. Eureka, 2:198 - -211, 1939. Google Scholar
  23. Robert A. Hearn and Erik D. Demaine. Games, puzzles and computation. A K Peters, 2009. Google Scholar
  24. Takumi Ishizeki and Akihiro Matsuura. Solving quantum tic-tac-toe. International Conference on Advanced Computing and Communication Technologies, 2011. Google Scholar
  25. Valerie King, Satish Rao, and Rorbert Tarjan. A faster deterministic maximum flow algorithm. Journal of Algorithms, 17(3):447-474, 1994. Google Scholar
  26. Ker-I Ko. Relativized polynomial time hierarchies having exactly k levels. SIAM J. Comput., 18(2):392-408, April 1989. Google Scholar
  27. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, January 1975. Google Scholar
  28. David Lichtenstein and Michael Sipser. Go is polynomial-space hard. J. ACM, 27(2):393-401, 1980. Google Scholar
  29. G Mahadevan, T Ponnuchamy, Selvam Avadayappan, and Jyoti Mishra. Application of eternal domination in epidemiology. In Mathematical Modeling and Soft Computing in Epidemiology, pages 147-171. CRC Press, 2020. Google Scholar
  30. John F. Nash. Some Games and Machines for Playing Them. RAND Corporation, Santa Monica, CA, 1952. Google Scholar
  31. Thomas J. Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185-225, 1978. Google Scholar
  32. A.N. Siegel. Combinatorial Game Theory. Graduate Studies in Mathematics. American Mathematical Society, 2013. Google Scholar
  33. Michael Soltys and Craig Wilson. On the complexity of computing winning strategies for finite poset games. Theory Comput. Syst., 48:680-692, April 2011. Google Scholar
  34. R. P. Sprague. Über mathematische Kampfspiele. Tôhoku Mathematical Journal, 41:438 - -444, 1935-36. Google Scholar
  35. David Wolfe. Go endgames are PSPACE-hard. In Richard J. Nowakowski, editor, More Games of No Chance, volume 42 of Mathematical Sciences Research Institute Publications, pages 125-136. Cambridge University Press, 2002. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact