Document Open Access Logo

Dots & Boxes Is PSPACE-Complete

Authors Kevin Buchin , Mart Hagedoorn, Irina Kostitsyna , Max van Mulken

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.25.pdf
  • Filesize: 1.37 MB
  • 18 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Mart Hagedoorn
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Irina Kostitsyna
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Max van Mulken
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands

Cite As Get BibTex

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken. Dots & Boxes Is PSPACE-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.25

Abstract

Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Child’s Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Dots & Boxes
  • PSPACE-complete
  • combinatorial game

Metrics

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

References

  1. Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia. Games on triangulations. Theoretical Computer Science, 343(1):42-71, 2005. Game Theory Meets Theoretical Computer Science. URL: https://doi.org/10.1016/j.tcs.2005.05.007.
  2. Michael H. Albert, Richard J. Nowakowski, and David Wolfe. Lessons in play: an introduction to combinatorial game theory. CRC Press, 2019. Google Scholar
  3. Joseph Barker and Richard Korf. Solving 4× 5 dots-and-boxes. In Proc. 25th AAAI Conference on Artificial Intelligence, pages 1756-1757, 2011. URL: https://doi.org/10.5555/2900423.2900680.
  4. Joseph Barker and Richard Korf. Solving dots-and-boxes. In Proc. 26th AAAI Conference on Artificial Intelligence, pages 414-419, 2012. URL: https://doi.org/10.5555/2900728.2900788.
  5. Elwyn R. Berlekamp. The Dots and Boxes Game: Sophisticated Child’s Play. A K Peters/CRC Press, 2000. Google Scholar
  6. Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Chapter 16: Dots-and-boxes. In Winning Ways for your Mathematical Plays, volume 3, pages 541-584. A K Peters/CRC Press, 2nd edition, 2003. Google Scholar
  7. Elwyn R. Berlekamp and Katherine Scott. Forcing your opponent to stay in control of a loony Dots-and-Boxes endgame. In R. J. Nowakowski, editor, More Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, volume 42, pages 317-330. Cambridge University Press, 2002. Google Scholar
  8. Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & polygons (media exposition). In Proc. 36th Internat. Sympos. Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 79:1-79:4, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.79.
  9. Kyle Burke and Robert A. Hearn. PSPACE-complete two-color planar placement games. International Journal of Game Theory, 48(2):393-410, 2019. URL: https://doi.org/10.1007/s00182-018-0628-8.
  10. Kyle Burke, Silvia Heubach, Melissa A. Huggan, and Svenja Huntemann. Keeping your distance is hard. CoRR, 2016. URL: http://arxiv.org/abs/1605.06801.
  11. Kevin Buzzard and Michael Ciere. Playing simple loony dots-and-boxes endgames optimally. INTEGERS, 14:2, 2014. Google Scholar
  12. Sébastien Collette, Erik D. Demaine, Martin L. Demaine, and Stefan Langerman. Narrow misere Dots-and-Boxes. Games of No Chance 4, 63:57, 2015. Google Scholar
  13. Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In International Symposium on Mathematical Foundations of Computer Science, pages 18-33. Springer, 2001. URL: https://doi.org/10.1007/3-540-44683-4_3.
  14. Erik D. Demaine, Martin L. Demaine, Nicholas J.A. Harvey, Ryuhei Uehara, Takeaki Uno, and Yushi Uno. UNO is hard, even for a single player. Theoretical Computer Science, 521:51-61, 2014. URL: https://doi.org/10.1016/j.tcs.2013.11.023.
  15. Erik D. Demaine and Yevhenii Diomidov. Strings-and-Coins and Nimstring are PSPACE-complete. CoRR, 2021. URL: http://arxiv.org/abs/2101.06361.
  16. Erik D. Demaine and Robert A. Hearn. Playing games with algorithms: algorithmic combinatorial game theory. In Games of No Chance 3, pages 3-56. Cambridge University Press, 2009. URL: http://arxiv.org/abs/cs/0106019.
  17. David Eppstein. Computational complexity of games and puzzles. Last accessed on 06/05/2021. URL: https://www.ics.uci.edu/~eppstein/cgt/hard.html.
  18. Gary William Flake and Eric B. Baum. Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants". Theoretical Computer Science, 270(1):895-911, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00173-6.
  19. Richard K. Guy and Richard J. Nowakowski. Unsolved problems in combinatorial games. In R. J. Nowakowski, editor, More Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, volume 42, page 457–473. Cambridge University Press, 2002. Google Scholar
  20. Robert A. Hearn. Games, puzzles, and computation. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2006. Google Scholar
  21. Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009. Google Scholar
  22. Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, and Yukiko Yamauchi. Sankaku-tori: An old western-japanese game played on a point set. Journal of Information Processing, 25:708-715, 2017. URL: https://doi.org/10.2197/ipsjjip.25.708.
  23. Ming Yu Hsieh and Shi-Chun Tsai. On the fairness and complexity of generalized k-in-a-row games. Theoretical Computer Science, 385(1-3):88-100, 2007. URL: https://doi.org/10.1016/j.tcs.2007.05.031.
  24. Shigeki Iwata and Takumi Kasai. The Othello game on an n× n board is PSPACE-complete. Theoretical Computer Science, 123(2):329-340, 1994. URL: https://doi.org/10.1016/0304-3975(94)90131-7.
  25. Adam S. Jobson, Levi Sledd, Susan Calcote White, and D. Jacob Wildstrom. Variations on narrow dots-and-boxes and dots-and-triangles. INTEGERS, 17:#G2:1-8, 2017. Google Scholar
  26. Will Johnson. The combinatorial game theory of well-tempered scoring games. International Journal of Game Theory, 43(2):415-438, 2014. URL: https://doi.org/10.1007/s00182-013-0386-6.
  27. Anthony Knittel, Terry Bossomaier, and Allan Snyder. Concept accessibility as basis for evolutionary reinforcement learning of dots and boxes. In IEEE Symposium on Computational Intelligence and Games, pages 140-145. IEEE, 2007. URL: https://doi.org/10.1109/CIG.2007.368090.
  28. David Lichtenstein and Michael Sipser. GO is polynomial-space hard. Journal of the ACM, 27(2):393-401, 1980. URL: https://doi.org/10.1145/322186.322201.
  29. Édouard Lucas. Récréations mathématiques, volume 2. Gauthier-Villars et fils, 1883. Google Scholar
  30. Henry Meyniel and Jean-Pierre Roudneff. The vertex picking game and a variation of the game of dots and boxes. Discrete Mathematics, 70:311-313, 1988. URL: https://doi.org/10.1016/0012-365X(88)90007-6.
  31. Richard J. Nowakowski. …, Welter’s game, Sylver coinage, dots-and-boxes, …. In R. K. Guy, editor, Combinatorial Games, Proc. Symposia in Applied Mathematics, volume 43, pages 155-182. AMS, 1991. URL: https://doi.org/10.1090/psapm/043/1095544.
  32. Thomas J. Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185-225, 1978. URL: https://doi.org/10.1016/0022-0000(78)90045-4.
  33. Aaron N. Siegel. Combinatorial game theory, volume 146 of Graduate Studies in Mathematics. American Mathematical Society, 2013. URL: https://doi.org/10.1090/gsm/146.
  34. Julian West. Championship-level play of dots-and-boxes. In R. J. Nowakowski, editor, Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, volume 29, pages 79-84. Cambridge University Press, 1996. Google Scholar
  35. Yimeng Zhuang, Shuqin Li, Tom Vincent Peters, and Chenguang Zhang. Improving monte-carlo tree search for dots-and-boxes with a novel board representation and artificial neural networks. In IEEE Conference on Computational Intelligence and Games, pages 314-321. IEEE, 2015. URL: https://doi.org/10.1109/CIG.2015.7317912.
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