TY - JOUR
AU - Gaspers, Serge
AU - RÃ¼mmele, Stefan
AU - Saffidine, Abdallah
AU - Tran, Kevin
PY - 2018/04/25
Y2 - 2023/11/28
TI - Minesweeper with Limited Moves
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - AAAI Technical Track: Game Playing and Interactive Entertainment
DO - 10.1609/aaai.v32i1.11433
UR - https://ojs.aaai.org/index.php/AAAI/article/view/11433
SP -
AB - <p> We consider the problem of playing Minesweeper with a limited number of moves: Given a partially revealed board, a number of available clicks k, and a target probability p, can we win with probability p. We win if we do not click on a mine, and, after our sequence of at most k clicks (which reveal information about the neighboring squares) can correctly identify the placement of all mines. We make the assumption, that, at all times, all placements of mines consistent with the currently revealed squares are equiprobable. Our main results are that the problem is PSPACE-complete, and it remains PSPACE-complete when p is a constant, in particular when p = 1. When k = 0 (i.e., we are not allowed to click anywhere), the problem is PP-complete in general, but co-NP-complete when p is a constant, and in particular when p = 1. </p>
ER -