引言
Dots and Boxes（点格棋、连点成框）是经典的两人纸笔博弈游戏。玩家在网格的相邻两点之间画线，当闭合一个 1×1 方框时，占据该框并获得额外一次落子机会。游戏结束时占据方框多者获胜。本文用Java实现Dots and Boxes，核心讲解博弈树搜索、贪心评估与链式结构分析。
游戏规则与状态表示
标准游戏在 m × n 的网格点上进行，存在水平和垂直两种边。每步选择一条未画的边，若该边使某方框的四边完整，则玩家获得该方框并继续落子。状态空间为所有边的占据情况，共 m(n-1) + n(m-1) 条边。
// 边类型
enum EdgeType { HORIZONTAL, VERTICAL }
// 游戏状态
boolean[][] hEdges; // 水平边 (m+1) x n
boolean[][] vEdges; // 垂直边 m x (n+1)
int[][] owner; // 方框归属 -1=未占, 0=玩家A, 1=玩家B
核心算法：贪心 + 链分析
Dots and Boxes的最优策略涉及复杂的组合博弈论。实用求解采用两层策略：
1. 必拿框：若某边能立即闭合方框，优先落子。
2. 链分析：识别长链（一串相互依赖的方框），通过控制链的归属来最大化收益。关键定理：双方都不愿在终局前开启长链（除非被迫）。
贪心评估函数
/**
* 评估当前局面对当前玩家的优势
* 核心指标：已占方框数 + 潜在可拿方框数 - 对手潜在可拿方框数
*/
int evaluate(boolean isPlayerA) {
int myBoxes = countBoxes(isPlayerA ? 0 : 1);
int oppBoxes = countBoxes(isPlayerA ? 1 : 0);
int myThreats = countThreats(isPlayerA); // 再画一条边即可得框
int oppThreats = countThreats(!isPlayerA);
return (myBoxes - oppBoxes) * 100 + (myThreats - oppThreats) * 10;
}
链识别算法
链是由相邻的、仅缺一条边的方框组成的序列。识别链有助于判断何时被迫开启链（牺牲）以及链的长度对终局的影响。
Java实现
import java.util.*;
/**
* Dots and Boxes 点格棋实现
*/
public class DotsAndBoxes {
private int rows, cols; // 方框行数、列数
private boolean[][] hEdges; // 水平边 (rows+1) x cols
private boolean[][] vEdges; // 垂直边 rows x (cols+1)
private int[][] owner; // 方框归属 -1=未占
private int[] scores; // 双方得分
private boolean playerA; // 当前玩家 true=A, false=B
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.owner = new int[rows][cols];
for (int[] row : owner) Arrays.fill(row, -1);
this.scores = new int[2];
this.playerA = true;
}
/**
* 落子：返回本轮获得的方框数（0表示回合结束，>0可继续）
*/
public int makeMove(int r, int c, boolean isHorizontal) {
if (isHorizontal) {
if (hEdges[r][c]) return -1; // 非法
hEdges[r][c] = true;
} else {
if (vEdges[r][c]) return -1;
vEdges[r][c] = true;
}
int gained = checkBoxes(r, c, isHorizontal);
scores[playerA ? 0 : 1] += gained;
if (gained == 0) {
playerA = !playerA; // 换玩家
}
return gained;
}
/**
* 检查新边是否闭合方框
*/
private int checkBoxes(int r, int c, boolean isHorizontal) {
int gained = 0;
if (isHorizontal) {
// 水平边上方框：若r>0检查上方，若r<rows检查下方
if (r > 0 && boxComplete(r - 1, c)) {
owner[r - 1][c] = playerA ? 0 : 1;
gained++;
}
if (r < rows && boxComplete(r, c)) {
owner[r][c] = playerA ? 0 : 1;
gained++;
}
} else {
// 垂直边左方框：若c>0检查左方，若c<cols检查右方
if (c > 0 && boxComplete(r, c - 1)) {
owner[r][c - 1] = playerA ? 0 : 1;
gained++;
}
if (c < cols && boxComplete(r, c)) {
owner[r][c] = playerA ? 0 : 1;
gained++;
}
}
return gained;
}
private boolean boxComplete(int r, int c) {
return hEdges[r][c] && hEdges[r + 1][c]
&& vEdges[r][c] && vEdges[r][c + 1];
}
/**
* AI贪心决策：优先拿框，否则避免给对手送框
*/
public int[] aiMove() {
List<int[]> safeMoves = new ArrayList<>();
List<int[]> sacrificingMoves = new ArrayList<>();
List<int[]> boxMoves = new ArrayList<>();
// 遍历所有可用边
for (int r = 0; r <= rows; r++) {
for (int c = 0; c < cols; c++) {
if (!hEdges[r][c]) {
int gain = previewGain(r, c, true);
if (gain > 0) boxMoves.add(new int[]{r, c, 1, gain});
else if (isSafe(r, c, true)) safeMoves.add(new int[]{r, c, 1, gain});
else sacrificingMoves.add(new int[]{r, c, 1, gain});
}
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c <= cols; c++) {
if (!vEdges[r][c]) {
int gain = previewGain(r, c, false);
if (gain > 0) boxMoves.add(new int[]{r, c, 0, gain});
else if (isSafe(r, c, false)) safeMoves.add(new int[]{r, c, 0, gain});
else sacrificingMoves.add(new int[]{r, c, 0, gain});
}
}
}
// 优先级：必拿框 > 安全步 > 牺牲步（选给对手框最少的）
if (!boxMoves.isEmpty()) {
// 优先拿能开启连环的框
boxMoves.sort((a, b) -> Integer.compare(b[3], a[3]));
return new int[]{boxMoves.get(0)[0], boxMoves.get(0)[1], boxMoves.get(0)[2]};
}
if (!safeMoves.isEmpty()) {
return new int[]{safeMoves.get(0)[0], safeMoves.get(0)[1], safeMoves.get(0)[2]};
}
// 被迫牺牲：选择让对手获得方框数最少的边
sacrificingMoves.sort((a, b) -> Integer.compare(a[3], b[3]));
return new int[]{sacrificingMoves.get(0)[0], sacrificingMoves.get(0)[1], sacrificingMoves.get(0)[2]};
}
/**
* 预览落子后立即获得的方框数
*/
private int previewGain(int r, int c, boolean isHorizontal) {
// 临时设置并检查
int gain = 0;
if (isHorizontal) {
hEdges[r][c] = true;
if (r > 0 && boxComplete(r - 1, c)) gain++;
if (r < rows && boxComplete(r, c)) gain++;
hEdges[r][c] = false;
} else {
vEdges[r][c] = true;
if (c > 0 && boxComplete(r, c - 1)) gain++;
if (c < cols && boxComplete(r, c)) gain++;
vEdges[r][c] = false;
}
return gain;
}
/**
* 判断落子是否为安全步：不立即给对手创造拿框机会
*/
private boolean isSafe(int r, int c, boolean isHorizontal) {
// 若该边使某方框从缺2边变为缺1边，则为不安全
if (isHorizontal) {
hEdges[r][c] = true;
boolean safe = true;
if (r > 0 && countMissingEdges(r - 1, c) == 1) safe = false;
if (r < rows && countMissingEdges(r, c) == 1) safe = false;
hEdges[r][c] = false;
return safe;
} else {
vEdges[r][c] = true;
boolean safe = true;
if (c > 0 && countMissingEdges(r, c - 1) == 1) safe = false;
if (c < cols && countMissingEdges(r, c) == 1) safe = false;
vEdges[r][c] = false;
return safe;
}
}
private int countMissingEdges(int r, int c) {
int count = 0;
if (!hEdges[r][c]) count++;
if (!hEdges[r + 1][c]) count++;
if (!vEdges[r][c]) count++;
if (!vEdges[r][c + 1]) count++;
return count;
}
public boolean isGameOver() {
return scores[0] + scores[1] == rows * cols;
}
public int getWinner() {
if (scores[0] > scores[1]) return 0;
if (scores[1] > scores[0]) return 1;
return -1; // 平局
}
public void printBoard() {
System.out.println("A=" + scores[0] + " B=" + scores[1] + " 当前=" + (playerA ? "A" : "B"));
for (int r = 0; r <= rows; r++) {
for (int c = 0; c <= cols; c++) {
System.out.print("+");
if (c < cols && hEdges[r][c]) System.out.print("---");
else if (c < cols) System.out.print(" ");
}
System.out.println();
if (r < rows) {
for (int c = 0; c <= cols; c++) {
if (vEdges[r][c]) System.out.print("|");
else System.out.print(" ");
if (c < cols) {
if (owner[r][c] == 0) System.out.print(" A ");
else if (owner[r][c] == 1) System.out.print(" B ");
else System.out.print(" ");
}
}
System.out.println();
}
}
}
public static void main(String[] args) {
DotsAndBoxes game = new DotsAndBoxes(3, 3);
Random rand = new Random();
while (!game.isGameOver()) {
game.printBoard();
int[] move = game.aiMove();
int gained = game.makeMove(move[0], move[1], move[2] == 1);
System.out.println((game.playerA ? "B" : "A") + " 落子: " +
(move[2] == 1 ? "H" : "V") + "[" + move[0] + "," + move[1] + "] 得框=" + gained);
}
game.printBoard();
int winner = game.getWinner();
System.out.println("获胜者: " + (winner == 0 ? "A" : winner == 1 ? "B" : "平局"));
}
}
博弈分析
Dots and Boxes的终局通常由长链控制决定。当剩余未画边形成一条链状结构时，先手进入链的玩家可以通过控制每次取走的框数，迫使对手在链尾开启下一条链。经典策略是双交叉（double-cross）：在长链末端保留两个方框不取，迫使对手进入下一条链。
该游戏的计算复杂度为 PSPACE-complete，对于 3×3 以上的棋盘，精确求解需借助深度博弈树搜索或神经网络评估。
扩展方向
- ** Minimax/Alpha-Beta**：对小型棋盘实现完整博弈树搜索。
- ** 神经网络评估**：训练CNN评估局面价值，支持更大棋盘。
- ** 不规则棋盘**：支持六边形、三角形网格变体。
