Dots and Boxes（点格棋/围地盘）是一款经典的二人策略纸笔游戏。玩家在 n×m 的点阵网格上轮流连接相邻两点画线，当某位玩家画出的线闭合了一个 1×1 的方格时，该玩家获得这个方格并继续行动。游戏结束时拥有最多方格的玩家获胜。本文用 Java 实现 Dots and Boxes 的 AI 对手，核心算法基于博弈树搜索（Minimax）与链式结构分析（Chain Analysis）。
核心算法思路
Dots and Boxes 是一个有限信息的完全信息博弈，理论上可用 Minimax 求解。但由于棋盘上的可选边数通常为 20-40 条，完全搜索的博弈树极为庞大。因此 AI 需要结合以下策略：
1. 局面评估函数：
– 直接统计双方已占方格数。
– 分析”危险边”：某些边如果被对手画上会导致送出一个或多个方格。
– 识别”链式结构”：一系列首尾相连的未闭合方格形成的链。掌握链的控制权往往决定胜负。
2. 链式分析（Chain Analysis）：
– 短链（长度为 1-2 的链）：通常应尽快取走，避免给对手送分。
– 长链（长度 ≥ 3 的链）：掌握”长链法则”——在标准规则下，先手玩家通常希望棋盘上的长链总数为奇数，后手希望为偶数。
– 双交叉策略（Double-Cross）：当被迫进入长链时，通过只取走链末端两个方格（而非整条链）来切换控制权，这是 Dots and Boxes 最核心的战术。
3. 受限深度 Minimax：
– 由于完整搜索不可行，AI 在关键决策点（如选择进入哪条链、是否执行双交叉）使用受限深度的 Minimax 搜索。
– 对于”被迫行动”（如只有一条安全边可画）则直接执行，不消耗搜索深度。
Java 实现
import java.util.*;
public class DotsAndBoxesAI {
private int rows, cols; // 点阵的行列数
private boolean[][] hEdges; // 水平边 hEdges[r][c] 连接 (r,c) 和 (r,c+1)
private boolean[][] vEdges; // 垂直边 vEdges[r][c] 连接 (r,c) 和 (r+1,c)
private int[][] owner; // 每个方格的拥有者：0=未占, 1=玩家1, 2=玩家2
private int[] scores = new int[3];
public DotsAndBoxesAI(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.hEdges = new boolean[rows][cols - 1];
this.vEdges = new boolean[rows - 1][cols];
this.owner = new int[rows - 1][cols - 1];
}
/**
* 判断某条边是否安全（不会立刻送给对方一个方格）
*/
public boolean isSafeMove(int r, int c, boolean isHorizontal) {
int boxesFilled = 0;
if (isHorizontal) {
// 上方方格
if (r > 0) {
int filled = countFilledEdges(r - 1, c, true);
if (filled == 3) return false;
}
// 下方方格
if (r < rows - 1) {
int filled = countFilledEdges(r, c, true);
if (filled == 3) return false;
}
} else {
// 左方方格
if (c > 0) {
int filled = countFilledEdges(r, c - 1, false);
if (filled == 3) return false;
}
// 右方方格
if (c < cols - 1) {
int filled = countFilledEdges(r, c, false);
if (filled == 3) return false;
}
}
return true;
}
/**
* 统计某个方格已填充的边数
*/
private int countFilledEdges(int boxR, int boxC, boolean ignoreHorizontal) {
int count = 0;
// 上边
if (hEdges[boxR][boxC]) count++;
// 下边
if (hEdges[boxR + 1][boxC]) count++;
// 左边
if (vEdges[boxR][boxC]) count++;
// 右边
if (vEdges[boxR][boxC + 1]) count++;
return count;
}
/**
* 获取某条边画完后能得到的方格数
*/
public int boxesGained(int r, int c, boolean isHorizontal) {
int gained = 0;
if (isHorizontal) {
if (r > 0 && countFilledEdges(r - 1, c, true) == 3 && !hEdges[r][c]) gained++;
if (r < rows - 1 && countFilledEdges(r, c, true) == 3 && !hEdges[r][c]) gained++;
} else {
if (c > 0 && countFilledEdges(r, c - 1, false) == 3 && !vEdges[r][c]) gained++;
if (c < cols - 1 && countFilledEdges(r, c, false) == 3 && !vEdges[r][c]) gained++;
}
return gained;
}
/**
* 执行一步并返回是否获得了方格（可继续行动）
*/
public boolean makeMove(int r, int c, boolean isHorizontal, int player) {
if (isHorizontal) {
if (hEdges[r][c]) throw new IllegalStateException("Edge already drawn");
hEdges[r][c] = true;
} else {
if (vEdges[r][c]) throw new IllegalStateException("Edge already drawn");
vEdges[r][c] = true;
}
int gained = 0;
if (isHorizontal) {
if (r > 0 && countFilledEdges(r - 1, c, true) == 4) {
owner[r - 1][c] = player; gained++;
}
if (r < rows - 1 && countFilledEdges(r, c, true) == 4) {
owner[r][c] = player; gained++;
}
} else {
if (c > 0 && countFilledEdges(r, c - 1, false) == 4) {
owner[r][c - 1] = player; gained++;
}
if (c < cols - 1 && countFilledEdges(r, c, false) == 4) {
owner[r][c] = player; gained++;
}
}
scores[player] += gained;
return gained > 0;
}
/**
* 撤销一步（用于回溯搜索）
*/
public void undoMove(int r, int c, boolean isHorizontal, int player, int gained) {
if (isHorizontal) {
hEdges[r][c] = false;
if (r > 0 && owner[r - 1][c] == player) { owner[r - 1][c] = 0; }
if (r < rows - 1 && owner[r][c] == player) { owner[r][c] = 0; }
} else {
vEdges[r][c] = false;
if (c > 0 && owner[r][c - 1] == player) { owner[r][c - 1] = 0; }
if (c < cols - 1 && owner[r][c] == player) { owner[r][c] = 0; }
}
scores[player] -= gained;
}
/**
* 获取所有合法移动
*/
public List<Move> getAllMoves() {
List<Move> moves = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols - 1; c++) {
if (!hEdges[r][c]) moves.add(new Move(r, c, true));
}
}
for (int r = 0; r < rows - 1; r++) {
for (int c = 0; c < cols; c++) {
if (!vEdges[r][c]) moves.add(new Move(r, c, false));
}
}
return moves;
}
/**
* 获取所有安全移动
*/
public List<Move> getSafeMoves() {
List<Move> safe = new ArrayList<>();
for (Move m : getAllMoves()) {
if (isSafeMove(m.r, m.c, m.horizontal)) safe.add(m);
}
return safe;
}
/**
* 局面评估函数：从当前玩家视角评分
*/
public int evaluate(int player) {
int opponent = player == 1 ? 2 : 1;
int score = (scores[player] - scores[opponent]) * 100;
// 分析链式结构的数量（简化版：统计含恰好两条边的方格数作为链的代理指标）
int chainIndicator = 0;
for (int r = 0; r < rows - 1; r++) {
for (int c = 0; c < cols - 1; c++) {
if (owner[r][c] == 0) {
int filled = countFilledEdges(r, c, false);
if (filled == 2) chainIndicator++;
}
}
}
// 长链奇偶性影响（简化策略）
score += chainIndicator * (player == 1 ? 1 : -1);
return score;
}
/**
* 受限深度 Minimax 搜索
*/
public Move findBestMove(int player, int depth) {
List<Move> moves = getAllMoves();
if (moves.isEmpty()) return null;
Move bestMove = null;
int bestScore = Integer.MIN_VALUE;
// 优先尝试能直接得分的移动
moves.sort((a, b) -> {
int ga = boxesGained(a.r, a.c, a.horizontal);
int gb = boxesGained(b.r, b.c, b.horizontal);
return Integer.compare(gb, ga);
});
for (Move m : moves) {
int gained = boxesGained(m.r, m.c, m.horizontal);
boolean extraTurn = makeMove(m.r, m.c, m.horizontal, player);
int score;
if (extraTurn) {
// 获得方格可继续行动
score = minimax(player, depth - 1, player, Integer.MIN_VALUE, Integer.MAX_VALUE);
} else {
int opponent = player == 1 ? 2 : 1;
score = minimax(opponent, depth - 1, player, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
undoMove(m.r, m.c, m.horizontal, player, gained);
if (score > bestScore) {
bestScore = score;
bestMove = m;
}
}
return bestMove;
}
private int minimax(int currentPlayer, int depth, int evalPlayer, int alpha, int beta) {
if (depth == 0 || getAllMoves().isEmpty()) {
return evaluate(evalPlayer);
}
List<Move> moves = getAllMoves();
boolean isMaximizing = (currentPlayer == evalPlayer);
if (isMaximizing) {
int maxEval = Integer.MIN_VALUE;
for (Move m : moves) {
int gained = boxesGained(m.r, m.c, m.horizontal);
boolean extra = makeMove(m.r, m.c, m.horizontal, currentPlayer);
int nextPlayer = extra ? currentPlayer : (currentPlayer == 1 ? 2 : 1);
int eval = minimax(nextPlayer, depth - 1, evalPlayer, alpha, beta);
undoMove(m.r, m.c, m.horizontal, currentPlayer, gained);
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break;
}
return maxEval;
} else {
int minEval = Integer.MAX_VALUE;
for (Move m : moves) {
int gained = boxesGained(m.r, m.c, m.horizontal);
boolean extra = makeMove(m.r, m.c, m.horizontal, currentPlayer);
int nextPlayer = extra ? currentPlayer : (currentPlayer == 1 ? 2 : 1);
int eval = minimax(nextPlayer, depth - 1, evalPlayer, alpha, beta);
undoMove(m.r, m.c, m.horizontal, currentPlayer, gained);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break;
}
return minEval;
}
}
public void printBoard() {
for (int r = 0; r < rows; r++) {
// 打印点和水平边
for (int c = 0; c < cols; c++) {
System.out.print("•");
if (c < cols - 1) System.out.print(hEdges[r][c] ? "───" : " ");
}
System.out.println();
// 打印垂直边和方格拥有者
if (r < rows - 1) {
for (int c = 0; c < cols; c++) {
System.out.print(vEdges[r][c] ? "│" : " ");
if (c < cols - 1) {
System.out.print(owner[r][c] == 1 ? " 1 " : owner[r][c] == 2 ? " 2 " : " ");
} else {
System.out.print(" ");
}
}
System.out.println();
}
}
System.out.println("Score - P1: " + scores[1] + " P2: " + scores[2]);
}
static class Move {
int r, c;
boolean horizontal;
Move(int r, int c, boolean h) { this.r = r; this.c = c; this.horizontal = h; }
public String toString() { return (horizontal ? "H" : "V") + "(" + r + "," + c + ")"; }
}
public static void main(String[] args) {
DotsAndBoxesAI game = new DotsAndBoxesAI(3, 3); // 2x2 方格的小棋盘
Random rand = new Random();
int currentPlayer = 1;
while (!game.getAllMoves().isEmpty()) {
Move m;
if (currentPlayer == 1) {
m = game.findBestMove(1, 4);
System.out.println("AI Player 1 chooses: " + m);
} else {
List<Move> moves = game.getAllMoves();
m = moves.get(rand.nextInt(moves.size()));
System.out.println("Random Player 2 chooses: " + m);
}
boolean extra = game.makeMove(m.r, m.c, m.horizontal, currentPlayer);
game.printBoard();
if (!extra) {
currentPlayer = currentPlayer == 1 ? 2 : 1;
}
}
System.out.println("Game Over! Winner: " +
(game.scores[1] > game.scores[2] ? "Player 1" : game.scores[2] > game.scores[1] ? "Player 2" : "Draw"));
}
}
复杂度分析
时间复杂度：Minimax 搜索深度为 d 时，分支因子为剩余边数 E’。每次评估需要 O(R×C)。因此复杂度为 O(E’^d × R × C)。对于 3×3 点阵（4 条边），深度 4 是可接受的；对于更大的棋盘需要更深的策略分析而非纯搜索。
空间复杂度：棋盘状态和递归栈，O(R×C + d)。
策略要点
- 安全优先：在开放阶段，AI 应只画安全边，避免给对手送方格。
- 链控制：当被迫进入链时，通过”双交叉”只取 2 个方格并将控制权交给对手，迫使对手开启下一条链。
- 终局处理：在最后阶段，有时主动送一个方格给对手（ sacrifice）反而能控制长链的分配。
总结
Dots and Boxes 的 AI 实现展示了博弈论在实际游戏中的复杂性和趣味性。Minimax 提供了基础的搜索框架，而链式分析则是该游戏特有的高级策略。通过将两者结合，AI 能够在小棋盘上展现出专家级别的水平，同时也为理解组合博弈论中的”控制理论”提供了绝佳的入门案例。
