Minesweeper, a classic logic puzzle game, poses significant computational challenges due to the uncertainty of hidden mine locations and its NP-complete complexity. Traditional deterministic solvers based on Boolean Satisfiability (SAT) and Constraint Satisfaction Problems (CSP) perform well on simple grids but degrade substantially in complex scenarios where logical inference alone is insufficient. This paper presents TRIMS (Tri-Phase Reasoning Intelligence for Minesweeper Solving), a novel hybrid approach that systematically combines a three-phase strategy: (1) fast deterministic constraint propagation for immediate logical deductions, (2) probabilistic move selection based on local and global risk estimates when determinism stalls and (3) strategic fallback moves to break deadlocks. This approach further integrates advanced constraint intersection analysis, position-aware probability adjustments reflecting empirical mine distribution biases and information value heuristics to guide decision-making under uncertainty. Experimental results on various difficulty levels demonstrate that TRIMS achieves state-of-the-art win rates: 99.0% on Beginner, 94.4% on Intermediate and 73.1% on Expert boards, outperforming existing solvers like PAFG and traditional CSP-based methods. TRIMS sets a new benchmark for automated Minesweeper solving and demonstrates the potential of hybrid strategies in complex, uncertain decision-making environments such as autonomous navigation, medical diagnosis, computer vision, underground mine detection etc.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Progressive Reasoning Under Uncertainty: A Three-Phase Approach to Automated Minesweeper Solving

  • Tuhin Dhar,
  • Rapti Chaudhuri,
  • Suman Deb

摘要

Minesweeper, a classic logic puzzle game, poses significant computational challenges due to the uncertainty of hidden mine locations and its NP-complete complexity. Traditional deterministic solvers based on Boolean Satisfiability (SAT) and Constraint Satisfaction Problems (CSP) perform well on simple grids but degrade substantially in complex scenarios where logical inference alone is insufficient. This paper presents TRIMS (Tri-Phase Reasoning Intelligence for Minesweeper Solving), a novel hybrid approach that systematically combines a three-phase strategy: (1) fast deterministic constraint propagation for immediate logical deductions, (2) probabilistic move selection based on local and global risk estimates when determinism stalls and (3) strategic fallback moves to break deadlocks. This approach further integrates advanced constraint intersection analysis, position-aware probability adjustments reflecting empirical mine distribution biases and information value heuristics to guide decision-making under uncertainty. Experimental results on various difficulty levels demonstrate that TRIMS achieves state-of-the-art win rates: 99.0% on Beginner, 94.4% on Intermediate and 73.1% on Expert boards, outperforming existing solvers like PAFG and traditional CSP-based methods. TRIMS sets a new benchmark for automated Minesweeper solving and demonstrates the potential of hybrid strategies in complex, uncertain decision-making environments such as autonomous navigation, medical diagnosis, computer vision, underground mine detection etc.