点连框（Dots and Boxes）是一款经典的纸笔双人策略游戏。玩家在网格点之间轮流画线，每当某条线的加入使得一个 $1 \times 1$ 方格的边界被完整封闭时，该玩家占领此方格并获得额外一次行动机会。本文用Java实现完整的点连框游戏引擎，讲解贪心链式捕获策略、Minimax博弈树搜索与启发式评估函数设计，包含完整代码与复杂度分析。
游戏规则与状态表示
在 $m \times n$ 的点阵中，存在 $(m-1) \times n$ 条水平边和 $m \times (n-1)$ 条垂直边，总计 $E = 2mn – m – n$ 条可画边。游戏状态由以下数据结构完整刻画：
– 边集合：记录哪些边已被画出
– 方格归属：每个 $1 \times 1$ 方格属于哪位玩家或仍未被占领
– 当前得分：双方各自占领的方格数
– 下一位玩家：轮到谁行动
核心算法策略
1. 贪心链式捕获（Chain Capture）
游戏中最关键的战术概念是链（Chain）与循环（Loop）：
– 链：一系列相邻的方格，每个方格已有3条边被画出，仅剩1条边未画
– 循环：首尾相接的链，形成闭环
贪心策略的核心规则：
– 安全边：不使任何方格达到3条边的边（不会给对手创造机会）
– 被迫行动：当必须画一条会使某方格达到3条边的边时，选择使损失最小的边
– 链式捕获：主动开启一条链，通过控制链的长度来获取优势
2. Minimax博弈树搜索
对于小规模网格（如 $3 \times 3$），可采用Minimax搜索配合Alpha-Beta剪枝求解近似最优策略。
3. 启发式评估函数
$$Eval(s) = Score_{self} – Score_{opponent} + \sum_{c \in Chains} value(c) + \sum_{b \in Boxes} threat(b)$$
其中 $value(c)$ 根据链长度赋予不同权重，$threat(b)$ 评估未占领方格的威胁程度。
完整Java实现
import java.util.*;
/**
* 点连框游戏引擎
*/
public class DotsAndBoxes {
private final int rows; // 点数行数
private final int cols; // 点数列数
private boolean[][] hEdges; // 水平边 [rows-1][cols]
private boolean[][] vEdges; // 垂直边 [rows][cols-1]
private int[][] boxes; // 方格归属: 0=空, 1=玩家1, 2=玩家2
private int[] scores; // 双方得分
private int currentPlayer; // 当前玩家: 1或2
private int totalMoves; // 总步数
public DotsAndBoxes(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.hEdges = new boolean[rows - 1][cols];
this.vEdges = new boolean[rows][cols - 1];
this.boxes = new int[rows - 1][cols - 1];
this.scores = new int[3]; // 索引0不用
this.currentPlayer = 1;
this.totalMoves = 0;
}
/**
* 尝试画一条边，返回是否成功以及是否获得额外回合
* @param type 'H'为水平边, 'V'为垂直边
* @param r 行索引
* @param c 列索引
* @return [是否成功, 是否获得额外回合]
*/
public boolean[] makeMove(char type, int r, int c) {
if (!isValidMove(type, r, c)) return new boolean[]{false, false};
boolean extraTurn = false;
if (type == 'H') {
hEdges[r][c] = true;
// 检查下方方格（如果存在）
if (r < rows - 1 && isBoxComplete(r, c)) {
boxes[r][c] = currentPlayer;
scores[currentPlayer]++;
extraTurn = true;
}
// 检查上方方格（如果存在）
if (r > 0 && isBoxComplete(r - 1, c)) {
boxes[r - 1][c] = currentPlayer;
scores[currentPlayer]++;
extraTurn = true;
}
} else {
vEdges[r][c] = true;
// 检查右方方格
if (c < cols - 1 && isBoxComplete(r, c)) {
boxes[r][c] = currentPlayer;
scores[currentPlayer]++;
extraTurn = true;
}
// 检查左方方格
if (c > 0 && isBoxComplete(r, c - 1)) {
boxes[r][c - 1] = currentPlayer;
scores[currentPlayer]++;
extraTurn = true;
}
}
totalMoves++;
if (!extraTurn) {
currentPlayer = (currentPlayer == 1) ? 2 : 1;
}
return new boolean[]{true, extraTurn};
}
/**
* 判断指定位置的方格是否已被完整包围
*/
private boolean isBoxComplete(int br, int bc) {
return hEdges[br][bc] && hEdges[br][bc + 1] && vEdges[br][bc] && vEdges[br + 1][bc];
}
/**
* 检查移动是否合法
*/
private boolean isValidMove(char type, int r, int c) {
if (type == 'H') {
return r >= 0 && r < rows - 1 && c >= 0 && c < cols && !hEdges[r][c];
} else {
return r >= 0 && r < rows && c >= 0 && c < cols - 1 && !vEdges[r][c];
}
}
/**
* 获取所有合法移动
*/
public List<Move> getAllMoves() {
List<Move> moves = new ArrayList<>();
for (int r = 0; r < rows - 1; r++) {
for (int c = 0; c < cols; c++) {
if (!hEdges[r][c]) moves.add(new Move('H', r, c));
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols - 1; c++) {
if (!vEdges[r][c]) moves.add(new Move('V', r, c));
}
}
return moves;
}
/**
* 评估当前局面（从当前玩家视角）
*/
public int evaluate() {
int scoreDiff = scores[currentPlayer] - scores[(currentPlayer == 1) ? 2 : 1];
int chainValue = evaluateChains();
return scoreDiff * 100 + chainValue;
}
/**
* 链评估：分析当前局面的链结构价值
*/
private int evaluateChains() {
int value = 0;
for (int r = 0; r < rows - 1; r++) {
for (int c = 0; c < cols - 1; c++) {
if (boxes[r][c] != 0) continue;
int edgeCount = countBoxEdges(r, c);
if (edgeCount == 3) {
// 即将被占领的方格 - 当前玩家应尽可能拿取
value += (currentPlayer == 1) ? 15 : -15;
} else if (edgeCount == 2) {
// 危险方格 - 给对手留下3边方格是糟糕的
value -= 5;
}
}
}
return value;
}
/**
* 统计指定方格已画出的边数
*/
private int countBoxEdges(int br, int bc) {
int count = 0;
if (hEdges[br][bc]) count++;
if (hEdges[br][bc + 1]) count++;
if (vEdges[br][bc]) count++;
if (vEdges[br + 1][bc]) count++;
return count;
}
/**
* 贪心AI：选择当前最优的边
* 优先级：1)能立即得分的边 2)不创造3边方格的安全边 3)损失最小的边
*/
public Move greedyMove() {
List<Move> moves = getAllMoves();
Move bestSafe = null;
Move bestCapture = null;
int minThreat = Integer.MAX_VALUE;
for (Move m : moves) {
DotsAndBoxes sim = this.copy();
boolean[] result = sim.makeMove(m.type, m.r, m.c);
if (result[1]) {
// 此移动能立即得分
if (bestCapture == null || sim.scores[currentPlayer] > this.scores[currentPlayer] + 1) {
bestCapture = m;
}
} else {
// 评估此移动给对手创造的威胁
int threat = countThreats(sim);
if (threat < minThreat) {
minThreat = threat;
bestSafe = m;
}
}
}
// 优先捕获，其次安全移动
return (bestCapture != null) ? bestCapture :
(bestSafe != null) ? bestSafe : moves.get(0);
}
/**
* 统计当前局面中3边方格的数量（即对手下一步可捕获的数量）
*/
private int countThreats(DotsAndBoxes state) {
int threats = 0;
for (int r = 0; r < rows - 1; r++) {
for (int c = 0; c < cols - 1; c++) {
if (state.boxes[r][c] == 0 && state.countBoxEdges(r, c) == 3) {
threats++;
}
}
}
return threats;
}
/**
* Minimax搜索（带Alpha-Beta剪枝）
* @param depth 搜索深度
* @param alpha 当前最大下界
* @param beta 当前最小上界
* @param maximizing 是否为极大化层
*/
public int minimax(int depth, int alpha, int beta, boolean maximizing) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
List<Move> moves = getAllMoves();
if (maximizing) {
int maxEval = Integer.MIN_VALUE;
for (Move m : moves) {
DotsAndBoxes sim = this.copy();
boolean[] result = sim.makeMove(m.type, m.r, m.c);
// 如果获得额外回合，继续当前玩家的极大层
boolean nextMax = result[1] ? maximizing : !maximizing;
int eval = sim.minimax(depth - 1, alpha, beta, nextMax);
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break; // Alpha-Beta剪枝
}
return maxEval;
} else {
int minEval = Integer.MAX_VALUE;
for (Move m : moves) {
DotsAndBoxes sim = this.copy();
boolean[] result = sim.makeMove(m.type, m.r, m.c);
boolean nextMax = result[1] ? maximizing : !maximizing;
int eval = sim.minimax(depth - 1, alpha, beta, nextMax);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break;
}
return minEval;
}
}
/**
* 深拷贝当前游戏状态
*/
public DotsAndBoxes copy() {
DotsAndBoxes copy = new DotsAndBoxes(rows, cols);
for (int r = 0; r < rows - 1; r++) {
System.arraycopy(hEdges[r], 0, copy.hEdges[r], 0, cols);
}
for (int r = 0; r < rows; r++) {
System.arraycopy(vEdges[r], 0, copy.vEdges[r], 0, cols - 1);
}
for (int r = 0; r < rows - 1; r++) {
System.arraycopy(boxes[r], 0, copy.boxes[r], 0, cols - 1);
}
copy.scores[1] = scores[1];
copy.scores[2] = scores[2];
copy.currentPlayer = currentPlayer;
copy.totalMoves = totalMoves;
return copy;
}
public boolean isGameOver() {
return totalMoves == (rows - 1) * cols + rows * (cols - 1);
}
public int getWinner() {
if (!isGameOver()) return 0;
return (scores[1] > scores[2]) ? 1 : (scores[2] > scores[1]) ? 2 : 0;
}
// 数据类
public record Move(char type, int r, int c) {
@Override public String toString() {
return type + "(" + r + "," + c + ")";
}
}
public int getScore(int player) { return scores[player]; }
public int getCurrentPlayer() { return currentPlayer; }
public static void main(String[] args) {
DotsAndBoxes game = new DotsAndBoxes(3, 3);
// 两个贪心AI对弈演示
while (!game.isGameOver()) {
Move m = game.greedyMove();
boolean[] result = game.makeMove(m.type, m.r, m.c);
System.out.println("Player " + game.getCurrentPlayer() + " 的上一回合: " + m +
(result[1] ? " (得分!)" : ""));
System.out.println("得分 - P1: " + game.getScore(1) + ", P2: " + game.getScore(2));
}
int winner = game.getWinner();
System.out.println("\n游戏结束! 胜者: " + (winner == 0 ? "平局" : "Player " + winner));
}
}
复杂度分析
合法移动生成：遍历所有边位，时间复杂度 $O(rows \cdot cols)$。
单步评估：检查所有方格的边数，时间复杂度 $O(rows \cdot cols)$。
Minimax搜索：分支因子 $b \approx 2 \cdot rows \cdot cols$，深度为 $d$ 时复杂度 $O(b^d)$。Alpha-Beta剪枝在理想排序下可将有效分支因子降至 $O(\sqrt{b^d})$。
状态拷贝：完整复制所有数组，时间复杂度 $O(rows \cdot cols)$，空间复杂度 $O(rows \cdot cols)$。
策略进阶：长链控制理论
高水平对弈的核心是长链控制（Long Chain Control）。基本定理指出：在足够大的棋盘上，先手玩家通常希望棋盘上存在偶数条长链，后手玩家则希望奇数条。这是因为每开启一条长链的玩家通常只能拿到链首的2个方格，被迫将剩余方格让给对手。
Java实现中可通过增强评估函数来编码此策略：在终局阶段识别并计数长链结构，调整评估权重。
总结
点连框游戏将几何直觉与组合博弈论完美结合。本文通过Java实现了一个完整的游戏引擎，涵盖状态表示、合法移动生成、贪心策略、Minimax搜索与Alpha-Beta剪枝。贪心链式捕获策略适合实时对弈，而Minimax搜索则适用于小规模棋盘的最优解分析。该框架可进一步扩展为更复杂的组合博弈研究平台。
