引言
扫雷是一款考验逻辑推理的经典游戏。传统解法通常依赖确定性规则（如相邻数字与未揭开格子的精确匹配），但在复杂局面下往往面临信息不足、无法确定安全格的困境。本文引入贝叶斯推理框架，将扫雷的每一步决策建模为概率推断问题：在已知数字约束的条件下，计算每个未揭开格子是地雷的后验概率，从而做出期望损失最小的决策。
问题建模
状态定义
将扫雷地图划分为三类格子：
– 已揭开数字格：提供邻接地雷数量的精确约束
– 未揭开格：待推断的后验概率分布
– 已标记雷格：确定是地雷
贝叶斯网络结构
每个已揭开的数字格是一个约束节点，其值等于周围8格中地雷数量的总和。所有未揭开格是二值隐变量（是雷/非雷）。整个地图构成一个因子图（Factor Graph）：数字格作为因子节点，未揭开格作为变量节点，边表示邻接关系。
推理目标
对每个未揭开格子c，计算：
P(c = 地雷 | 所有已揭开数字) = ?
当精确推理因组合爆炸不可行时，采用信念传播（Belief Propagation）的近似推断方法。
核心算法设计
1. 约束提取与分组
将相互关联的未揭开格子和数字约束划分为独立组件，降低推理复杂度。若两个数字格共享未揭开邻居，则属于同一组件。
2. 精确枚举（小组件）
对于未揭开格子数n ≤ 20的组件，直接枚举所有2^n种地雷配置，筛选满足所有数字约束的合法配置，统计每个格子在合法配置中为地雷的频率作为后验概率。
3. 边缘概率计算（大组件）
对于大组件，采用以下策略：
– 确定性推断优先：如果某数字格的剩余未揭开邻居数恰好等于剩余雷数，则全部标记为雷；如果剩余雷数为0，则全部安全
– 安全格优先：选择后验概率最小的未揭开格子揭开
– 最小风险决策：当所有未揭开格概率相近时，优先选择邻接已揭开数字最少的格子（信息增益最大）
Java完整实现
import java.util.*;
/**
* 基于贝叶斯推理的扫雷AI
* 使用条件概率计算安全格，实现期望损失最小化决策
*/
public class BayesianMinesweeper {
// 地图状态
private final int rows, cols, totalMines;
private Cell[][] board;
private int remainingMines;
private int unrevealedCount;
private final Random random = new Random();
// 单元格状态
enum CellState { UNREVEALED, REVEALED, FLAGGED }
static class Cell {
CellState state = CellState.UNREVEALED;
boolean isMine = false;
int adjacentMines = 0; // 周围地雷数（仅REVEALED时有效）
double probMine = 0.5; // 是雷的后验概率
}
public BayesianMinesweeper(int rows, int cols, int mines) {
this.rows = rows;
this.cols = cols;
this.totalMines = mines;
this.remainingMines = mines;
this.unrevealedCount = rows * cols;
this.board = new Cell[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
board[i][j] = new Cell();
}
}
}
/**
* 初始化地雷（确保第一次点击安全）
*/
public void initMines(int safeRow, int safeCol) {
List<int[]> candidates = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (i != safeRow || j != safeCol) {
candidates.add(new int[]{i, j});
}
}
}
Collections.shuffle(candidates, random);
for (int k = 0; k < totalMines && k < candidates.size(); k++) {
int[] pos = candidates.get(k);
board[pos[0]][pos[1]].isMine = true;
}
// 计算每个格子的邻接地雷数
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!board[i][j].isMine) {
board[i][j].adjacentMines = countAdjacentMines(i, j);
}
}
}
}
private int countAdjacentMines(int r, int c) {
int count = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (inBounds(nr, nc) && board[nr][nc].isMine) count++;
}
}
return count;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
/**
* 揭开格子，返回是否触发地雷
*/
public boolean reveal(int r, int c) {
Cell cell = board[r][c];
if (cell.state != CellState.UNREVEALED) return false;
cell.state = CellState.REVEALED;
unrevealedCount--;
if (cell.isMine) return true; // 踩雷
// 如果是0，自动揭开周围（级联展开）
if (cell.adjacentMines == 0) {
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (inBounds(nr, nc)) reveal(nr, nc);
}
}
}
return false;
}
/**
* 标记/取消标记地雷
*/
public void flag(int r, int c) {
Cell cell = board[r][c];
if (cell.state == CellState.UNREVEALED) {
cell.state = CellState.FLAGGED;
remainingMines--;
} else if (cell.state == CellState.FLAGGED) {
cell.state = CellState.UNREVEALED;
remainingMines++;
}
}
/**
* 获取邻居列表
*/
private List<int[]> getNeighbors(int r, int c) {
List<int[]> list = new ArrayList<>();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (inBounds(nr, nc)) list.add(new int[]{nr, nc});
}
}
return list;
}
/**
* 提取所有约束组件
* 每个约束为：(数字格位置, 相邻未揭开格子列表, 剩余地雷数)
*/
private List<Constraint> extractConstraints() {
List<Constraint> constraints = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
Cell cell = board[i][j];
if (cell.state != CellState.REVEALED) continue;
List<int[]> neighbors = getNeighbors(i, j);
List<int[]> unrevealed = new ArrayList<>();
int flaggedCount = 0;
for (int[] n : neighbors) {
Cell nc = board[n[0]][n[1]];
if (nc.state == CellState.UNREVEALED) {
unrevealed.add(n);
} else if (nc.state == CellState.FLAGGED) {
flaggedCount++;
}
}
int remaining = cell.adjacentMines - flaggedCount;
if (remaining >= 0 && !unrevealed.isEmpty()) {
constraints.add(new Constraint(i, j, unrevealed, remaining));
}
}
}
return constraints;
}
static class Constraint {
int row, col;
List<int[]> cells;
int remainingMines;
Constraint(int r, int c, List<int[]> cells, int rem) {
this.row = r; this.col = c; this.cells = cells; this.remainingMines = rem;
}
}
/**
* 将约束划分为连通组件
*/
private List<List<Constraint>> splitComponents(List<Constraint> constraints) {
if (constraints.isEmpty()) return new ArrayList<>();
// 构建邻接图：共享未揭开格子的约束相连
int n = constraints.size();
boolean[][] adj = new boolean[n][n];
for (int i = 0; i < n; i++) {
Set<String> cellsI = new HashSet<>();
for (int[] c : constraints.get(i).cells) cellsI.add(c[0] + "," + c[1]);
for (int j = i + 1; j < n; j++) {
for (int[] c : constraints.get(j).cells) {
if (cellsI.contains(c[0] + "," + c[1])) {
adj[i][j] = adj[j][i] = true;
break;
}
}
}
}
boolean[] vis = new boolean[n];
List<List<Constraint>> components = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
List<Constraint> comp = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
q.add(i);
vis[i] = true;
while (!q.isEmpty()) {
int u = q.poll();
comp.add(constraints.get(u));
for (int v = 0; v < n; v++) {
if (adj[u][v] && !vis[v]) {
vis[v] = true;
q.add(v);
}
}
}
components.add(comp);
}
return components;
}
/**
* 对小组件进行精确枚举，计算每个格子的地雷概率
*/
private Map<String, Double> enumerateComponent(List<Constraint> comp) {
Set<String> vars = new HashSet<>();
for (Constraint c : comp) {
for (int[] cell : c.cells) vars.add(cell[0] + "," + cell[1]);
}
List<String> varList = new ArrayList<>(vars);
int n = varList.size();
Map<String, Integer> varIndex = new HashMap<>();
for (int i = 0; i < n; i++) varIndex.put(varList.get(i), i);
// 枚举所有2^n种配置
long[] mineCount = new long[n]; // 每个变量为1的次数
long validConfigs = 0;
int totalConfigs = 1 << n;
for (int mask = 0; mask < totalConfigs; mask++) {
// 快速检查约束
boolean valid = true;
for (Constraint c : comp) {
int count = 0;
for (int[] cell : c.cells) {
int idx = varIndex.get(cell[0] + "," + cell[1]);
if ((mask & (1 << idx)) != 0) count++;
}
if (count != c.remainingMines) {
valid = false;
break;
}
}
if (valid) {
validConfigs++;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) mineCount[i]++;
}
}
}
Map<String, Double> probs = new HashMap<>();
for (int i = 0; i < n; i++) {
double p = validConfigs > 0 ? (double) mineCount[i] / validConfigs : 0.5;
probs.put(varList.get(i), p);
}
return probs;
}
/**
* 贝叶斯推理主函数：更新所有未揭开格子的地雷概率
*/
public void updateProbabilities() {
// 重置概率
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j].state == CellState.UNREVEALED) {
board[i][j].probMine = (double) remainingMines / unrevealedCount;
}
}
}
List<Constraint> constraints = extractConstraints();
if (constraints.isEmpty()) return;
List<List<Constraint>> components = splitComponents(constraints);
for (List<Constraint> comp : components) {
Set<String> vars = new HashSet<>();
for (Constraint c : comp) {
for (int[] cell : c.cells) vars.add(cell[0] + "," + cell[1]);
}
Map<String, Double> probs;
if (vars.size() <= 22) {
// 精确枚举
probs = enumerateComponent(comp);
} else {
// 大组件：仅做确定性推断
probs = deterministicInference(comp);
}
// 更新概率
for (Map.Entry<String, Double> e : probs.entrySet()) {
String[] p = e.getKey().split(",");
int r = Integer.parseInt(p[0]), c = Integer.parseInt(p[1]);
board[r][c].probMine = e.getValue();
}
}
}
/**
* 确定性推断：仅处理概率为0或1的情况
*/
private Map<String, Double> deterministicInference(List<Constraint> comp) {
Map<String, Double> probs = new HashMap<>();
boolean changed = true;
while (changed) {
changed = false;
for (Constraint c : comp) {
List<String> unknown = new ArrayList<>();
for (int[] cell : c.cells) {
String key = cell[0] + "," + cell[1];
if (!probs.containsKey(key) || (probs.get(key) > 0 && probs.get(key) < 1)) {
unknown.add(key);
}
}
int knownMines = 0;
for (int[] cell : c.cells) {
String key = cell[0] + "," + cell[1];
if (probs.getOrDefault(key, 0.0) == 1.0) knownMines++;
}
int rem = c.remainingMines - knownMines;
if (unknown.size() == rem && rem > 0) {
// 全部是雷
for (String k : unknown) {
probs.put(k, 1.0);
changed = true;
}
} else if (rem == 0) {
// 全部安全
for (String k : unknown) {
probs.put(k, 0.0);
changed = true;
}
}
}
}
// 未推断的设为未知
for (Constraint c : comp) {
for (int[] cell : c.cells) {
String key = cell[0] + "," + cell[1];
probs.putIfAbsent(key, 0.5);
}
}
return probs;
}
/**
* AI决策：选择最优动作
* 返回 [action, row, col]: action 0=reveal, 1=flag
*/
public int[] decideAction() {
updateProbabilities();
// 优先标记确定是雷的格子
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j].state == CellState.UNREVEALED && board[i][j].probMine >= 0.999) {
return new int[]{1, i, j};
}
}
}
// 优先揭开确定安全的格子
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j].state == CellState.UNREVEALED && board[i][j].probMine <= 0.001) {
return new int[]{0, i, j};
}
}
}
// 选择概率最小的格子揭开
double minProb = 1.1;
int bestR = -1, bestC = -1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j].state == CellState.UNREVEALED) {
if (board[i][j].probMine < minProb) {
minProb = board[i][j].probMine;
bestR = i;
bestC = j;
}
}
}
}
if (bestR != -1) {
return new int[]{0, bestR, bestC};
}
return null;
}
/**
* 打印当前地图（AI视角）
*/
public void printBoard() {
System.out.println(" " + "0 1 2 3 4 5 6 7 8".substring(0, cols * 2));
for (int i = 0; i < rows; i++) {
System.out.print(i + " ");
for (int j = 0; j < cols; j++) {
Cell c = board[i][j];
if (c.state == CellState.FLAGGED) {
System.out.print("F ");
} else if (c.state == CellState.UNREVEALED) {
System.out.print("? ");
} else {
System.out.print(c.adjacentMines + " ");
}
}
System.out.println();
}
}
/**
* 打印概率地图
*/
public void printProbabilities() {
System.out.println("\nMine Probabilities:");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j].state == CellState.UNREVEALED) {
System.out.printf("%.2f ", board[i][j].probMine);
} else {
System.out.print("---- ");
}
}
System.out.println();
}
}
/**
* 运行完整游戏
*/
public void play() {
// 第一步随机点击中心区域
int sr = rows / 2, sc = cols / 2;
initMines(sr, sc);
reveal(sr, sc);
int steps = 0;
while (unrevealedCount > remainingMines) {
int[] action = decideAction();
if (action == null) break;
int act = action[0], r = action[1], c = action[2];
if (act == 1) {
flag(r, c);
System.out.println("Step " + (++steps) + ": Flag (" + r + "," + c + ")");
} else {
System.out.println("Step " + (++steps) + ": Reveal (" + r + "," + c + ") prob="
+ String.format("%.3f", board[r][c].probMine));
if (reveal(r, c)) {
System.out.println("BOOM! Hit a mine at (" + r + "," + c + ")");
printBoard();
return;
}
}
}
System.out.println("Victory! All mines cleared.");
printBoard();
}
public static void main(String[] args) {
BayesianMinesweeper game = new BayesianMinesweeper(9, 9, 10);
game.play();
}
}
算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 约束提取 | O(rows × cols) | O(rows × cols) |
| 组件划分（BFS） | O(constraints² × neighbors) | O(constraints²) |
| 精确枚举 | O(2^n × constraints) | O(n) |
| 确定性推断 | O(iterations × constraints) | O(variables) |
| 单步决策 | O(rows × cols + 2^n) | O(rows × cols) |
关键设计要点
- 组件分解：将全局推理问题拆分为多个独立子问题，每个组件单独求解，指数级降低复杂度
- 精确与近似混合：小组件精确枚举保证可靠性，大组件退化为确定性推断避免爆炸
- 概率最小化决策：始终选择地雷概率最低的格子揭开，实现期望生存率最大化
- 约束传播：利用数字格的精确等式约束，快速确定概率为0或1的格子
总结
贝叶斯推理为扫雷提供了一套严谨的概率决策框架。与确定性规则法相比，它能在信息不足时给出最优概率估计，在复杂局面下显著降低踩雷风险。读者可进一步探索将精确枚举替换为马尔可夫链蒙特卡洛（MCMC）采样，以处理更大规模的组件推理。
