License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.12
URN: urn:nbn:de:0030-drops-127735
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12773/
Go to the corresponding LIPIcs Volume Portal

Dempsey, Ross ; Guinn, Charles

A Phase Transition in Minesweeper

pdf-format:
LIPIcs-FUN-2021-12.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{dempsey_et_al:LIPIcs:2020:12773,
  author =	{Ross Dempsey and Charles Guinn},
  title =	{{A Phase Transition in Minesweeper}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{12:1--12:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12773},
  URN =		{urn:nbn:de:0030-drops-127735},
  doi =		{10.4230/LIPIcs.FUN.2021.12},
  annote =	{Keywords: Complexity of Games, Minesweeper}
}

Keywords: Complexity of Games, Minesweeper
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI