2021/05/10 by Yash Sinha, Sinha, Yash Pratyush, Pranshu Malviya +3
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2105.04120
openalex publication_date 2021/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.