引言
扫雷是一款经典的逻辑推理游戏，表面上是运气与概率的博弈，实则蕴含丰富的约束满足与概率推理思想。本文使用Java实现一个基于贝叶斯网络的概率推理引擎，通过分析已揭开的数字格子周围的约束关系，计算每个未揭开格子的精确或近似条件概率，并基于信息增益理论选择最优的下一步点击位置。
核心算法原理
扫雷的约束满足结构
每个已揭开的数字格子$c$向其周围8个邻域格子传递一个精确约束：邻域中地雷总数等于该数字。形式上，若$N(c)$表示$c$的邻域未揭开格子集合，则：
$$\sum_{x \in N(c)} \mathbb{I}(x \text{ is mine}) = \text{value}(c)$$
所有已揭开数字格子的约束构成一个巨大的约束满足问题（CSP）。当约束足够多时，某些格子的地雷状态可以被逻辑推导唯一确定；否则，需要借助概率推理计算各格子的条件概率。
贝叶斯网络建模
将扫雷的CSP转化为贝叶斯网络：每个未揭开格子是一个二元随机变量$X_i \in {0, 1}$，所有已揭开数字格子的约束构成证据$E$。我们需要计算：
$$P(X_i = 1 | E) = \frac{P(E | X_i = 1) \cdot P(X_i = 1)}{P(E)}$$
由于变量间通过约束高度耦合，精确推断需要枚举所有满足约束的配置，当变量数较大时不可行。本文采用约束分组策略：将相互约束关联的格子划分为独立的分组，在每个分组内精确枚举所有合法配置，再综合计算全局概率。
信息增益最优策略
在概率推理的基础上，最优点击策略不是简单地选择概率最低的格子，而是选择期望信息增益最大的格子。信息增益（互信息）衡量点击某格子后获得的信息量：
$$IG(X_i) = H(X_i) – H(X_i | \text{observation})$$
对于扫雷，我们近似使用”最小化期望剩余不确定性”作为启发式：优先点击那些无论结果如何都能最大程度缩小搜索空间的格子。
Java实现
项目结构
src/
├── game/
│ ├── MinesweeperGame.java // 游戏环境
│ └── Cell.java // 格子状态枚举
├── solver/
│ ├── Constraint.java // 约束表示
│ ├── BayesianSolver.java // 贝叶斯推理引擎
│ └── GroupEnumerator.java // 分组枚举器
└── train/
└── Evaluator.java // 胜率评估
游戏环境
package game;
import java.util.Random;
/**
* 扫雷游戏环境，支持标准难度（9x9, 10雷）
*/
public class MinesweeperGame {
public static final int SIZE = 9;
public static final int MINES = 10;
private final int[][] board; // -1=雷, 0-8=数字
private final boolean[][] revealed;
private final boolean[][] flagged;
private boolean gameOver;
private boolean firstClick; // 首击保护
public MinesweeperGame() {
this.board = new int[SIZE][SIZE];
this.revealed = new boolean[SIZE][SIZE];
this.flagged = new boolean[SIZE][SIZE];
this.firstClick = true;
reset();
}
public void reset() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
board[i][j] = 0;
revealed[i][j] = false;
flagged[i][j] = false;
}
}
gameOver = false;
firstClick = true;
}
/**
* 首次点击后生成地雷，确保首击安全
*/
private void generateMines(int safeRow, int safeCol) {
Random rand = new Random();
int placed = 0;
while (placed < MINES) {
int r = rand.nextInt(SIZE);
int c = rand.nextInt(SIZE);
if (board[r][c] == -1) continue;
if (Math.abs(r - safeRow) <= 1 && Math.abs(c - safeCol) <= 1) continue;
board[r][c] = -1;
placed++;
}
// 计算数字
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == -1) continue;
int count = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE && board[nr][nc] == -1) {
count++;
}
}
}
board[r][c] = count;
}
}
}
/**
* 点击格子，返回是否存活
*/
public boolean click(int row, int col) {
if (gameOver || revealed[row][col] || flagged[row][col]) return true;
if (firstClick) {
generateMines(row, col);
firstClick = false;
}
if (board[row][col] == -1) {
gameOver = true;
return false;
}
reveal(row, col);
return true;
}
/**
* 递归揭开空白区域（Flood Fill）
*/
private void reveal(int row, int col) {
if (row < 0 || row >= SIZE || col < 0 || col >= SIZE) return;
if (revealed[row][col]) return;
revealed[row][col] = true;
if (board[row][col] == 0) {
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
reveal(row + dr, col + dc);
}
}
}
}
/**
* 获取已揭开格子的数字值，未揭开返回-2
*/
public int getCellValue(int row, int col) {
if (!revealed[row][col]) return -2;
return board[row][col];
}
public boolean isRevealed(int row, int col) { return revealed[row][col]; }
public boolean isFlagged(int row, int col) { return flagged[row][col]; }
public boolean isGameOver() { return gameOver; }
public boolean isWon() {
if (gameOver) return false;
int revealedCount = 0;
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
if (revealed[i][j]) revealedCount++;
return revealedCount == SIZE * SIZE - MINES;
}
}
约束表示与分组
package solver;
import java.util.*;
/**
* 表示一个数字格子向其邻域传递的约束
*/
public class Constraint {
public final int sourceRow, sourceCol;
public final Set<int[]> variables; // 涉及的未揭开格子坐标
public final int requiredMines; // 需要的地雷数
public Constraint(int sr, int sc, Set<int[]> vars, int req) {
this.sourceRow = sr;
this.sourceCol = sc;
this.variables = vars;
this.requiredMines = req;
}
/**
* 检查给定赋值是否满足本约束
*/
public boolean isSatisfied(Map<String, Integer> assignment) {
int mineCount = 0;
int unknownCount = 0;
for (int[] v : variables) {
String key = v[0] + "," + v[1];
if (assignment.containsKey(key)) {
mineCount += assignment.get(key);
} else {
unknownCount++;
}
}
// 已确定的地雷数必须在可行范围内
return mineCount <= requiredMines && mineCount + unknownCount >= requiredMines;
}
@Override
public String toString() {
return String.format("C[%d,%d]: %d mines in %d cells", sourceRow, sourceCol, requiredMines, variables.size());
}
}
贝叶斯推理引擎
package solver;
import game.MinesweeperGame;
import java.util.*;
/**
* 基于约束分组与精确枚举的贝叶斯推理求解器
*/
public class BayesianSolver {
private final MinesweeperGame game;
public BayesianSolver(MinesweeperGame game) {
this.game = game;
}
/**
* 提取当前所有有效约束
*/
public List<Constraint> extractConstraints() {
List<Constraint> constraints = new ArrayList<>();
for (int r = 0; r < MinesweeperGame.SIZE; r++) {
for (int c = 0; c < MinesweeperGame.SIZE; c++) {
int val = game.getCellValue(r, c);
if (val < 0) continue; // 未揭开或边界
Set<int[]> unrevealed = new HashSet<>();
int flaggedCount = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= MinesweeperGame.SIZE || nc < 0 || nc >= MinesweeperGame.SIZE) continue;
if (game.isFlagged(nr, nc)) flaggedCount++;
else if (!game.isRevealed(nr, nc)) unrevealed.add(new int[]{nr, nc});
}
}
int remainingMines = val - flaggedCount;
if (remainingMines >= 0 && !unrevealed.isEmpty()) {
constraints.add(new Constraint(r, c, unrevealed, remainingMines));
}
}
}
return constraints;
}
/**
* 将约束涉及的变量划分为连通分量（独立分组）
*/
public List<Set<String>> groupVariables(List<Constraint> constraints) {
Map<String, Set<String>> graph = new HashMap<>();
for (Constraint c : constraints) {
List<String> vars = new ArrayList<>();
for (int[] v : c.variables) {
String key = v[0] + "," + v[1];
vars.add(key);
graph.putIfAbsent(key, new HashSet<>());
}
// 同一约束内的变量相互连通
for (int i = 0; i < vars.size(); i++) {
for (int j = i + 1; j < vars.size(); j++) {
graph.get(vars.get(i)).add(vars.get(j));
graph.get(vars.get(j)).add(vars.get(i));
}
}
}
List<Set<String>> groups = new ArrayList<>();
Set<String> visited = new HashSet<>();
for (String node : graph.keySet()) {
if (visited.contains(node)) continue;
Set<String> group = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(node);
visited.add(node);
while (!queue.isEmpty()) {
String curr = queue.poll();
group.add(curr);
for (String neighbor : graph.getOrDefault(curr, Collections.emptySet())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
groups.add(group);
}
return groups;
}
/**
* 对单个分组进行精确枚举，计算每个变量的边际概率
*/
public Map<String, Double> enumerateGroup(Set<String> groupVars, List<Constraint> allConstraints) {
Map<String, Double> probs = new HashMap<>();
for (String v : groupVars) probs.put(v, 0.0);
// 筛选出与本分组相关的约束
List<Constraint> relevant = new ArrayList<>();
for (Constraint c : allConstraints) {
for (int[] v : c.variables) {
if (groupVars.contains(v[0] + "," + v[1])) {
relevant.add(c);
break;
}
}
}
List<String> varList = new ArrayList<>(groupVars);
int totalConfigs = 0;
// 二进制枚举所有可能的赋值
int n = varList.size();
for (int mask = 0; mask < (1 << n); mask++) {
Map<String, Integer> assignment = new HashMap<>();
int mineCount = 0;
for (int i = 0; i < n; i++) {
int val = (mask >> i) & 1;
assignment.put(varList.get(i), val);
mineCount += val;
}
// 检查是否满足所有相关约束
boolean valid = true;
for (Constraint c : relevant) {
if (!c.isSatisfied(assignment)) {
valid = false;
break;
}
}
if (valid) {
totalConfigs++;
for (int i = 0; i < n; i++) {
if (((mask >> i) & 1) == 1) {
String v = varList.get(i);
probs.put(v, probs.get(v) + 1.0);
}
}
}
}
// 归一化
if (totalConfigs > 0) {
for (String v : groupVars) {
probs.put(v, probs.get(v) / totalConfigs);
}
}
return probs;
}
/**
* 综合所有分组，返回全局概率图
*/
public Map<String, Double> computeProbabilities() {
List<Constraint> constraints = extractConstraints();
if (constraints.isEmpty()) return Collections.emptyMap();
List<Set<String>> groups = groupVariables(constraints);
Map<String, Double> allProbs = new HashMap<>();
for (Set<String> group : groups) {
Map<String, Double> groupProbs = enumerateGroup(group, constraints);
allProbs.putAll(groupProbs);
}
return allProbs;
}
/**
* 选择最优点击位置：优先逻辑确定的安全格子，否则选概率最低的
*/
public int[] selectBestMove() {
Map<String, Double> probs = computeProbabilities();
// 第一步：检查是否有概率为0的安全格子
for (Map.Entry<String, Double> entry : probs.entrySet()) {
if (entry.getValue() == 0.0) {
String[] parts = entry.getKey().split(",");
return new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
}
}
// 第二步：检查是否有概率为1的确定雷，标记它（这里简化处理为避开）
// 第三步：在未揭开的边界格子中选概率最低的
double minProb = 1.0;
int[] best = null;
for (Map.Entry<String, Double> entry : probs.entrySet()) {
if (entry.getValue() < minProb) {
minProb = entry.getValue();
String[] parts = entry.getKey().split(",");
best = new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
}
}
// 如果没有约束覆盖的格子（游戏初期），选角落
if (best == null) {
return new int[]{0, 0};
}
return best;
}
}
胜率评估器
package train;
import game.MinesweeperGame;
import solver.BayesianSolver;
/**
* 评估贝叶斯求解器的胜率
*/
public class Evaluator {
public static void main(String[] args) {
final int GAMES = 1000;
int wins = 0;
int losses = 0;
for (int g = 0; g < GAMES; g++) {
MinesweeperGame game = new MinesweeperGame();
BayesianSolver solver = new BayesianSolver(game);
// 首击固定选角落
game.click(0, 0);
boolean alive = true;
int moves = 0;
while (alive && !game.isWon() && moves < 100) {
int[] move = solver.selectBestMove();
if (move == null) break;
alive = game.click(move[0], move[1]);
moves++;
}
if (game.isWon()) wins++;
else if (!alive) losses++;
}
System.out.printf("Total Games: %d | Wins: %d | Losses: %d | Win Rate: %.2f%%%n",
GAMES, wins, losses, (wins * 100.0 / GAMES));
}
}
算法复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 约束提取 | $O(N^2)$ | $O(N^2)$ | $N$为棋盘边长，遍历所有格子 |
| 变量分组 | $O(V + E)$ | $O(V + E)$ | $V$为变量数，$E$为约束关联边数 |
| 单组精确枚举 | $O(2^k \cdot m \cdot k)$ | $O(k)$ | $k$为分组变量数，$m$为相关约束数 |
| 最坏情况 | $O(2^{N^2})$ | $O(N^2)$ | 全图连通时需枚举所有变量 |
对于标准$9 \times 9$初级难度，约束通常将变量划分为多个小分组（每组$k < 20$），精确枚举完全可行。对于高级难度$16 \times 30$，大分组需要结合近似推理（如信念传播或采样方法）。
推理示例
假设某时刻盘面如下（R=已揭开数字，?=未揭开）：
? ? ? ?
? 2 1 ?
? 1 0 ?
? ? ? ?
约束分析：
– 格子(1,1)=2：周围4个?中需2雷
– 格子(1,2)=1：周围3个?中需1雷
– 格子(2,1)=1：周围3个?中需1雷
联合求解可得：格子(0,0)必为安全（概率0），因为无论其他格子如何配置，(0,0)都不可能是雷。
扩展方向
- 约束传播预处理：在枚举前执行单元传播（Unit Propagation）和子集约束消减，大幅缩小搜索空间。
- 信息增益启发式：不仅考虑$P(\text{mine})$，还计算点击某格后期望剩余约束系统的熵减，选择”信息量最大”的格子。
- 近似推理：对大分组使用Gibbs采样或变分推断，避免指数级枚举。
- 结合SAT求解器：将约束编码为CNF公式，利用现代SAT求解器（如MiniSat）高效枚举所有解。
总结
本文使用Java实现了基于贝叶斯网络的扫雷概率推理引擎。通过将数字约束提取为CSP、按连通性分组变量、在小分组内精确枚举所有合法配置，我们能够精确计算每个未揭开格子的条件地雷概率。当逻辑推导能够唯一确定安全格子时优先点击，否则选择概率最低的格子，实现了一个胜率远超随机点击的智能求解器。
