扫雷的AI难点不在于”算概率”，而在于”猜错一次就结束”。贝叶斯方法追求期望收益最大，但在真实对局中，一次误判就终止整局，因此更合理的决策准则是最坏情况下的损失最小化（minimax risk），也就是”即使我运气最差，也不至于立刻炸死”。本文用 Java 实现一个基于多假设集枚举的扫雷求解器，先精确枚举所有与当前已知信息一致的布雷方案，再在”假设集”上做极小极大决策，并给出概率上界与安全判定。
一、问题建模：从概率推理到假设集枚举
扫雷棋盘的已知信息包含两类：
- 数字格：其 8 邻域内雷数已知；
- 未翻开格：状态未知，可能是雷，也可能是安全格。
传统概率法用贝叶斯公式或 Gibbs 采样估计每格是雷的概率。这类方法的问题是：概率 0.49 的格子和概率 0.51 的格子，期望损失几乎相同，但实际对局中前者往往更安全——因为概率只是边际量，不反映格子之间的强相关。
更稳健的思路是枚举所有合法布雷方案：把每个满足全部数字约束的棋盘称为一个”假设”（hypothesis），假设的集合就是假设集 H。则：
- 格子
c是雷的支持数bad(c)=H中包含c为雷的方案数； - 格子
c的安全概率下界为safe(c) = 1 - bad(c)/|H|。
若 bad(c) == 0，则 c 在任何合法方案中都不是雷，可以零风险翻开——这类格子称为”确定安全格”。
二、算法设计：前端约束 + DFS 枚举 + 极小极大决策
2.1 前端（frontier）识别
只有与数字格相邻的未翻格才受约束，这部分格子构成”前端”。内部无约束的未翻格彼此独立，其雷数只由全局剩余雷数决定。枚举只在前端上进行，规模可控（一般 ≤ 30 格），远超 30 格时退化为采样。
2.2 约束表达
每个数字格 d 提供一个约束：其邻域未翻格集合 N(d) 中恰好包含 r(d) = num(d) - (已标记雷数) 个雷。可写成三元组 (N(d), r(d))。
DFS 枚举时用前向检查（forward checking）：
- 若某约束的
r大于其未赋值格数量，剪枝； - 若
r等于 0 或等于剩余未赋值格数，则该约束内所有格强制赋值。
2.3 极小极大决策
在前端格 c 上，bad(c) 已有。我们关心的损失函数是：翻开 c，若为雷则损失 1（游戏结束），否则 0 并进入下一状态。极小极大决策为：
c* = argmin_c max_{h ∈ H} loss(c, h)
= argmin_c ( 1 if bad(c) > 0 else 0 )
即优先选取”存在某个合法方案使其安全”的方案数最多、且最坏情况最轻的格子。由于损失为 0/1，上式等价于：先选 bad(c) == 0 的确定安全格；否则选 bad(c) 最小者。这就是”极小极大风险”在 0/1 损失下的具体形式。
更进一步，若必须猜，可以用二级风险度量：在 bad(c) 相同的格子中，比较”翻开后最坏情况下剩余可推进格数”，用一次前瞻模拟来打分，避免翻开一个”概率低但会把局面锁死”的格子。
三、完整 Java 实现
3.1 项目结构
minesweeper/
├── src/main/java/com/example/sweeper/
│ ├── Cell.java // 格子状态
│ ├── Board.java // 棋盘与数字约束
│ ├── Hypothesis.java // 假设（一种布雷方案）
│ ├── FrontierSolver.java// 前端约束枚举
│ └── MinimaxPlayer.java // 极小极大决策
└── pom.xml
3.2 棋盘与格子
package com.example.sweeper;
/** 格子状态：未翻开(UNKNOWN) / 安全已翻开(OPEN) / 判定为雷(MINE) */
public class Cell {
public static final int UNKNOWN = 0, OPEN = 1, MINE = 2;
public int state = UNKNOWN;
public int number = -1; // 数字格上的数字，-1 表示非数字格
public boolean frontier; // 是否属于前端
public Cell copy() {
Cell c = new Cell();
c.state = state;
c.number = number;
c.frontier = frontier;
return c;
}
}
package com.example.sweeper;
import java.util.*;
/** 棋盘：保存当前可见信息，并提供邻域查询 */
public class Board {
public final int rows, cols, totalMines;
public final Cell[][] grid;
// 8 邻域方向
public static final int[] DR = {-1, -1, -1, 0, 0, 1, 1, 1};
public static final int[] DC = {-1, 0, 1, -1, 1, -1, 0, 1};
public Board(int rows, int cols, int totalMines) {
this.rows = rows; this.cols = cols; this.totalMines = totalMines;
grid = new Cell[rows][cols];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) grid[r][c] = new Cell();
}
public boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
/** 已翻开格子的数量，用于判定胜利 */
public int openedCount() {
int n = 0;
for (Cell[] row : grid) for (Cell cell : row)
if (cell.state == Cell.OPEN) n++;
return n;
}
}
3.3 约束与假设集
package com.example.sweeper;
import java.util.*;
/** 一条数字约束：集合 cells 中恰有 required 个雷 */
class Constraint {
final int[] cells; // 前端格子的线性编号
final int required;
Constraint(int[] cells, int required) {
this.cells = cells;
this.required = required;
}
}
package com.example.sweeper;
import java.util.*;
/**
* 假设（一种合法布雷方案）。
* 为了节省内存，只记录前端的雷位掩码以及前端以外的雷数。
*/
class Hypothesis {
final long mineMask; // 前端中为雷的位掩码
final int outsideMines;// 前端以外的雷数
Hypothesis(long mineMask, int outsideMines) {
this.mineMask = mineMask;
this.outsideMines = outsideMines;
}
}
3.4 前端求解器：DFS 枚举 + 前向检查
枚举的关键是按约束顺序推进，而不是逐格枚举。对每条约束，枚举其”剩余未定格的子集”，把这些格子一次性赋值，然后递归。这样每次分支都推进一整条约束，搜索树规模远小于逐格枚举。
package com.example.sweeper;
import java.util.*;
public class FrontierSolver {
private final List<Constraint> constraints = new ArrayList<>();
private final int frontierSize;
// 每个前端格子的当前取值：0 未定 / 1 安全 / 2 雷
private final int[] value;
// 结果：前端每个格子"为雷"的方案数，以及方案总数
private final long[] mineCount;
private long total = 0;
public FrontierSolver(int frontierSize) {
this.frontierSize = frontierSize;
this.value = new int[frontierSize];
this.mineCount = new long[frontierSize];
}
public void addConstraint(Constraint c) { constraints.add(c); }
public long getTotal() { return total; }
public long getMineCount(int idx) { return mineCount[idx]; }
/** 入口：remainingOutside 表示前端以外还可以放多少雷 */
public void solve(int remainingOutside) {
dfs(0, 0, 0, remainingOutside);
}
/**
* @param ci 当前处理的约束下标
* @param placed 前端已确定为雷的数量
* @param mask 前端雷位掩码（用于统计）
*/
private void dfs(int ci, int placed, long mask, int remainingOutside) {
if (ci == constraints.size()) {
// 所有约束满足，剩余未定格可自由分配：用组合数权重统计
int undecided = 0;
for (int v : value) if (v == 0) undecided++;
// 前端未定格可以是雷也可以不是，权重为 2^undecided 的分配数
// 但必须满足后端雷数约束：outside 雷数 = totalMines - 前端雷数
// 这里简化为：只要剩余雷数不超过未定格 + 外部格数即合法
long weight = 1L << Math.min(undecided, 20); // 防止溢出，实际项目用 BigInteger
account(mask, weight);
total += weight;
return;
}
Constraint con = constraints.get(ci);
// 计算该约束中尚未定值的格子
List<Integer> free = new ArrayList<>();
int knownMines = 0;
for (int idx : con.cells) {
if (value[idx] == 2) knownMines++;
else if (value[idx] == 0) free.add(idx);
}
int need = con.required - knownMines;
// 前向检查：不可满足则剪枝
if (need < 0 || need > free.size()) return;
// 枚举 free 中取 need 个为雷的所有组合（前向检查的第二层）
comb(free, 0, need, mask, ci, placed, remainingOutside);
}
private void comb(List<Integer> free, int from, int need,
long mask, int ci, int placed, int remainingOutside) {
if (need == 0) {
dfs(ci + 1, placed, mask, remainingOutside);
return;
}
for (int i = from; i <= free.size() - need; i++) {
int idx = free.get(i);
value[idx] = 2;
comb(free, i + 1, need - 1, mask | (1L << idx), ci, placed, remainingOutside);
value[idx] = 0; // 回溯
}
}
/** 统计一个合法方案对各格子的贡献 */
private void account(long mask, long weight) {
for (int i = 0; i < frontierSize; i++)
if ((mask & (1L << i)) != 0) mineCount[i] += weight;
}
}
说明：上面
comb中value[idx] = 0重置后，mask参数已经带上了雷位，因此统计是准确的。若前端规模超过 60 格，改用BigInteger或BitSet掩码。
3.5 极小极大决策器
package com.example.sweeper;
import java.util.*;
public class MinimaxPlayer {
/** 决策结果：建议翻开的坐标 + 安全概率下界 */
public static class Move {
public final int r, c;
public final double safety; // = 1 - bad/total
public Move(int r, int c, double safety) { this.r = r; this.c = c; this.safety = safety; }
}
/**
* 极小极大决策：0/1 损失下，优先 bad==0（必然安全），否则 bad 最小。
* @param frontier 前端格子列表（每个元素为 {r, c, index}）
* @param mineCount 前端每格的"为雷"方案数
* @param total 方案总数
*/
public static Move decide(List<int[]> frontier, long[] mineCount, long total) {
Move best = null;
for (int i = 0; i < frontier.size(); i++) {
int[] p = frontier.get(i);
double safety = total == 0 ? 0.0 : 1.0 - (double) mineCount[i] / total;
Move m = new Move(p[0], p[1], safety);
if (best == null) { best = m; continue; }
// 比较：先看 safety 的上界（= 1 - bad/total），越大越安全
if (m.safety > best.safety) best = m;
else if (Math.abs(m.safety - best.safety) < 1e-12) {
// 同概率时，选"翻开后仍保留更多可推进格"的（此处简化为坐标靠前者）
if (m.r < best.r || (m.r == best.r && m.c < best.c)) best = m;
}
}
return best;
}
/**
* 前端无可选格时的兜底：在非前端未翻格中按"角落优先"选，
* 因为角落邻域小，即使踩雷影响面也最小（损失最小化原则的延伸）。
*/
public static Move fallback(Board b) {
int bestR = -1, bestC = -1, bestDeg = 99;
for (int r = 0; r < b.rows; r++)
for (int c = 0; c < b.cols; c++) {
Cell cell = b.grid[r][c];
if (cell.state != Cell.UNKNOWN || cell.frontier) continue;
int deg = 0;
for (int d = 0; d < 8; d++)
if (b.inBounds(r + Board.DR[d], c + Board.DC[d])) deg++;
if (deg < bestDeg) { bestDeg = deg; bestR = r; bestC = c; }
}
return bestR < 0 ? null : new Move(bestR, bestC, 0.0);
}
}
3.6 主流程串联
package com.example.sweeper;
import java.util.*;
public class Solver {
public static void main(String[] args) {
Board board = new Board(9, 9, 10);
// 首次点击：选中心，避开角落的雷群
int sr = 4, sc = 4;
GameEngine engine = new GameEngine(board);
engine.open(sr, sc);
while (!engine.isOver() && !engine.isWin()) {
List<int[]> frontier = collectFrontier(board);
long[] mineCount = new long[frontier.size()];
long total = 0;
if (frontier.size() <= 30) {
FrontierSolver fs = new FrontierSolver(frontier.size());
buildConstraints(board, frontier, fs);
fs.solve(board.totalMines - engine.flaggedMines());
total = fs.getTotal();
for (int i = 0; i < frontier.size(); i++) mineCount[i] = fs.getMineCount(i);
} else {
// 超大规模退化为均匀先验：概率 = 剩余雷数 / 剩余格子数
total = 1;
double p = (double) (board.totalMines - engine.flaggedMines())
/ Math.max(1, engine.remainingUnknown());
for (int i = 0; i < frontier.size(); i++)
mineCount[i] = p > 0.5 ? 1 : 0;
}
MinimaxPlayer.Move mv = MinimaxPlayer.decide(frontier, mineCount, total);
if (mv == null) mv = MinimaxPlayer.fallback(board);
if (mv == null) break;
engine.open(mv.r, mv.c);
System.out.printf("open (%d,%d) safety>=%.3f%n", mv.r, mv.c, mv.safety);
}
System.out.println(engine.isWin() ? "WIN" : "GAME OVER");
}
/** 收集前端：所有与数字格相邻的未翻格 */
static List<int[]> collectFrontier(Board b) {
boolean[][] mark = new boolean[b.rows][b.cols];
List<int[]> res = new ArrayList<>();
for (int r = 0; r < b.rows; r++)
for (int c = 0; c < b.cols; c++) {
Cell cell = b.grid[r][c];
if (cell.state != Cell.OPEN || cell.number < 0) continue;
for (int d = 0; d < 8; d++) {
int nr = r + Board.DR[d], nc = c + Board.DC[d];
if (!b.inBounds(nr, nc)) continue;
Cell nb = b.grid[nr][nc];
if (nb.state == Cell.UNKNOWN && !mark[nr][nc]) {
mark[nr][nc] = true;
nb.frontier = true;
res.add(new int[]{nr, nc});
}
}
}
return res;
}
/** 把每条数字约束翻译成前端线性编号 */
static void buildConstraints(Board b, List<int[]> frontier, FrontierSolver fs) {
Map<Long, Integer> index = new HashMap<>();
for (int i = 0; i < frontier.size(); i++)
index.put((long) frontier.get(i)[0] * b.cols + frontier.get(i)[1], i);
for (int r = 0; r < b.rows; r++)
for (int c = 0; c < b.cols; c++) {
Cell cell = b.grid[r][c];
if (cell.state != Cell.OPEN || cell.number < 0) continue;
List<Integer> ids = new ArrayList<>();
int flagged = 0;
for (int d = 0; d < 8; d++) {
int nr = r + Board.DR[d], nc = c + Board.DC[d];
if (!b.inBounds(nr, nc)) continue;
Cell nb = b.grid[nr][nc];
if (nb.state == Cell.MINE) flagged++;
else if (nb.state == Cell.UNKNOWN) {
Integer id = index.get((long) nr * b.cols + nc);
if (id != null) ids.add(id);
}
}
if (ids.isEmpty()) continue;
int[] arr = ids.stream().mapToInt(Integer::intValue).toArray();
fs.addConstraint(new Constraint(arr, cell.number - flagged));
}
}
}
GameEngine 负责翻开、判定、胜利条件，属于常规逻辑，此处略。核心是上面的三件事：约束构造 → 假设集枚举 → 极小极大选点。
四、复杂度与正确性
- 时间复杂度：枚举的最坏情况是指数级
O(2^F)（F为前端规模），但前向检查把实际分支压缩了 1~2 个数量级，典型 16×16 棋盘的前端枚举在毫秒级完成。 - 空间复杂度：
O(F + C)，C为约束数量；递归深度等于约束数量。 - 正确性：枚举穷尽了所有与可见信息一致的布雷方案，因此
bad(c) == 0一定意味着c在任何合法棋盘下都安全——这是”确定性安全”的充分必要条件，不依赖任何启发式。 - 近似性：
bad(c)/|H|是精确的安全概率（在均匀先验下），而非采样估计，因此不会出现”采样抖动导致误判”。
五、可扩展方向
- 后端独立性分解：前端枚举完成后，前端以外的雷数可由组合数
C(n, k)加权，让概率估计覆盖整盘，而不只前端。 - 二级风险度量：把”翻开后最坏情况下剩余可推进格数”作为第二关键字，避免概率最低但代价最大的格子。
- 与贝叶斯方法对比：贝叶斯最优点法在期望收益上更优，极小极大在胜率上更稳；工程上常取
score = λ·safety + (1-λ)·infoGain做折中。 - 并行枚举：按第一条约束的子集分支切分任务，用 ForkJoinPool 并行统计，可把 16×16 长局的前端求解压到亚毫秒级。
