基于回溯和启发式的全局约束满足扫雷算法  

Global Constraints Minesweeper Algorithm Based on Backtracking and Heuristic

作　　者：陈琳 陈兴国[2] 闫凡宇 戴芮昊 陈钰浩 CHEN Lin;CHEN Xingguo;YAN Fanyu;DAI Ruihao;CHEN Yuhao(Putian University,Putian 351131,China;Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]莆田学院,莆田351131 [2]南京邮电大学,南京210023

出　　处：《中央民族大学学报(自然科学版)》2025年第1期80-89,共10页Journal of Minzu University of China(Natural Sciences Edition)

基　　金：国家自然科学基金(62276142,62206133,62202240,62192783);科技创新2030新一代人工智能重大项目(2018AAA0100905);江苏省初步研究与发展计划(BE2021028);深圳市基础研究计划(2021Szvup056);莆田学院科研项目(2024017)。

摘　　要：扫雷游戏是一款规则简单但复杂度是NP⁃complete的单人小游戏,研究扫雷游戏算法不但是针对算法本身的研究,更是对计算复杂度理论的研究。本文通过马尔可夫决策过程对游戏进行建模,并在规则算法的基础上实现了基于约束满足的二元决策图算法,当无法确定可操作位置时,提出了全局约束满足回溯算法,重新计算含雷概率并打开概率最小的方格。当同时计算出多个概率最小的方格时,提出启发式累加值算法对多个概率最小的方格进行预判,得出最优的可操作方格。在游戏的简单、中等和困难模式下达到了目前最佳水平,分别为91.697%、78.741%和40.459%。扫雷游戏算法的发展为计算复杂度理论的研究提供了新的思路和方法。The minesweeper game is a simple rule⁃based single⁃player,yet it possesses NP⁃complete complexity.Researching Minesweeper algorithms is not only about the algorithms themselves but also about the study of computational complexity theory.In this paper,we model the game using Markov decision processes and implement a binary decision diagram algorithm based on constraint satisfac⁃tion on top of the rule⁃based algorithm.When playable positions is unable to determine playable po⁃sitions,we propose a global constraint satisfaction backtracking algorithm,recalculating the proba⁃bility of containing mines and opening the square with the lowest probability.When multiple squares with the lowest probabilities are computed simultaneously,we propose a heuristic accumulation value algorithm to pre⁃assess multiple squares and determine the optimal playable square.We achieve the current best levels in easy,medium,and hard modes,which are 91.697%,78.741%,and 40.459%respectively.The development of Minesweeper algorithms provides new insights and meth⁃ods for the study of computational complexity theory.

关 键 词：人工智能游戏 扫雷游戏 马尔可夫决策过程 二元决策图 约束满足 启发式 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]