2012/04/20 by Michiel de Bondt, de Bondt, Michiel · 1 voice
Computer Science · #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1204.4659
14 pages, LaTeX => DVI => PS => PDF
arxiv created 2012/04/20 · openalex publication_date 2012/04/20 · arxiv published 2012/04/20 · arxiv updated 2012/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the Minesweeper game is PP-hard, when the object is to locate all mines with the highest probability. When the probability of locating all mines may be infinitesimal, the Minesweeper game is even PSPACE-complete. In our construction, the player can reveal a boolean circuit in polynomial time, after guessing an initial square with no surrounding mines, a guess that has 99 percent probability of success. Subsequently, the mines must be located with a maximum probability of success. Furthermore, we show that determining the solvability of a partially uncovered Minesweeper board is NP-complete with hexagonal and triangular grids as well as a square grid, extending a similar result for square grids only by R. Kaye. Actually finding the mines with a maximum probability of success is again PP-hard or PSPACE-complete respectively. Our constructions are in such a way that the number of mines can be computed in polynomial time and hence a possible mine counter does not provide additional information. The results are obtained by replacing the dyadic gates in [3] by two primitives which makes life more easy in this context.