A Phase Transition in Minesweeper

Dempsey, Ross; Guinn, Charles

doi:10.4230/LIPIcs.FUN.2021.12

File

LIPIcs.FUN.2021.12.pdf

Filesize: 0.72 MB
10 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FUN.2021.12
URN: urn:nbn:de:0030-drops-127735

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 AsGet 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

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.
David J Becerra. Algorithmic approaches to playing Minesweeper. Master’s thesis, Harvard University, 2015.
Anton Belov and Joao Marques-Silva. MUSer2: an efficient MUS extractor, system description. JSAT, 2012.
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.
Kim Christensen. Percolation theory. Imperial College London, 1, 2002.
Ehud Friedgut. Hunting for sharp thresholds. Random Structures & Algorithms, 26(1-2):37-51, 2005.
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.
Ian P. Gent and Toby Walsh. The SAT phase transition. In ECAI, 1994.
R. Kaye. Infinite versions of Minesweeper are Turing complete. URL: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf.
R. Kaye. Minesweeper is NP-complete. The Mathematical Intelligencer, 22:9-15, 2000.
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.
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.
Dietrich Stauffer and Ammon Aharony. Introduction to percolation theory. Taylor & Francis, 1994.
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.