Fast constraint satisfaction problem and learning-based algorithm for
  solving Minesweeper
  Minesweeper is a popular spatial-based decision-making game that works with
incomplete information. As an exemplary NP-complete problem, it is a major area
of research employing various artificial intelligence paradigms. The present
work models this game as Constraint Satisfaction Problem (CSP) and Markov
Decision Process (MDP). We propose a new method named as dependents from the
independent set using deterministic solution search (DSScsp) for the faster
enumeration of all solutions of a CSP based Minesweeper game and improve the
results by introducing heuristics. Using MDP, we implement machine learning
methods on these heuristics. We train the classification model on sparse data
with results from CSP formulation. We also propose a new rewarding method for
applying a modified deep Q-learning for better accuracy and versatile learning
in the Minesweeper game. The overall results have been analyzed for different
kinds of Minesweeper games and their accuracies have been recorded. Results
from these experiments show that the proposed method of MDP based
classification model and deep Q-learning overall is the best methods in terms
of accuracy for games with given mine densities.
