Document Open Access Logo

A Phase Transition in Minesweeper

Authors Ross Dempsey , Charles Guinn

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.12.pdf
  • Filesize: 0.72 MB
  • 10 pages

Document Identifiers

Author Details

Ross Dempsey
  • Joseph Henry Laboratories, Princeton University, NJ, USA
Charles Guinn
  • Joseph Henry Laboratories, Princeton University, NJ, USA

Acknowledgements

The authors would like to thank Dumitru Caligaru and Katherine Xiang for interesting conversations and correspondence related to this project. We are also grateful to Anton Belov and Joao Marques-Silva for their open source GMUS extractor MUSer2.

Cite As Get BibTex

Ross Dempsey and Charles Guinn. A Phase Transition in Minesweeper. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.12

Abstract

We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Complexity of Games
  • Minesweeper

Metrics

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

References

  1. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. 2008 49th Annual IEEE Symposium on Foundations of Computer Science, October 2008. URL: https://doi.org/10.1109/focs.2008.11.
  2. David J Becerra. Algorithmic approaches to playing Minesweeper. Master’s thesis, Harvard University, 2015. Google Scholar
  3. Anton Belov and Joao Marques-Silva. MUSer2: an efficient MUS extractor, system description. JSAT, 2012. Google Scholar
  4. Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI’91, page 331–337, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. Google Scholar
  5. Kim Christensen. Percolation theory. Imperial College London, 1, 2002. Google Scholar
  6. Ehud Friedgut. Hunting for sharp thresholds. Random Structures & Algorithms, 26(1-2):37-51, 2005. Google Scholar
  7. Ehud Friedgut, Jean Bourgain, et al. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society, 12(4):1017-1054, 1999. Google Scholar
  8. Ian P. Gent and Toby Walsh. The SAT phase transition. In ECAI, 1994. Google Scholar
  9. R. Kaye. Infinite versions of Minesweeper are Turing complete. URL: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf.
  10. R. Kaye. Minesweeper is NP-complete. The Mathematical Intelligencer, 22:9-15, 2000. Google Scholar
  11. Abbas Ali Saberi. Recent advances in percolation theory and its applications. Physics Reports, 578:1–32, May 2015. URL: https://doi.org/10.1016/j.physrep.2015.03.003.
  12. Allan Scott, Ulrike Stege, and Iris van Rooij. Minesweeper may not be NP-complete but is hard nonetheless. The Mathematical Intelligencer, 33:5-17, 2011. Google Scholar
  13. Dietrich Stauffer and Ammon Aharony. Introduction to percolation theory. Taylor & Francis, 1994. Google Scholar
  14. Yakov M. Strelniker, Shlomo Havlin, and Armin Bunde. Fractals and percolation. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 3847-3858. Springer New York, New York, NY, 2009. URL: https://doi.org/10.1007/978-0-387-30440-3_227.
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