引言
点格棋（Dots and Boxes）是一款经典的双人纸笔游戏，规则简单却策略深远。两名玩家轮流在网格点之间画线，完成一个方格四边闭合的玩家占领该格并额外获得一次行动机会。
本文将用Java实现点格棋的AI对手，核心算法采用Minimax博弈树搜索配合Alpha-Beta剪枝，让计算机能够进行高水平的对抗。
游戏规则与状态表示
游戏规则
- 棋盘为 $(N+1) \times (M+1)$ 的点阵，形成 $N \times M$ 个方格
- 两名玩家轮流连接相邻两点画线（水平或垂直）
- 当一条线使某个方格四边闭合时，画该线的玩家占领此方格（+1分）
- 占领方格的玩家获得额外一次行动机会（连击）
- 游戏结束当所有线都被画完，占领方格多者获胜
状态表示
// 棋盘由两种边组成
- horizontalEdges[N+1][M]: // 水平边，(i,j)连接点(i,j)和(i,j+1)
- verticalEdges[N][M+1]: // 垂直边，(i,j)连接点(i,j)和(i+1,j)
- boxes[N][M]: // 每个方格的归属：0=未占，1=玩家1，2=玩家2
核心算法：Minimax with Alpha-Beta Pruning
Minimax原理
Minimax是一种对抗搜索算法，假设对手也会采取最优策略：
– Max层（我方回合）：选择使我方收益最大的行动
– Min层（对方回合）：选择使我方收益最小的行动（即对方收益最大）
递归评估博弈树，叶节点的价值由终局评估函数给出。
Alpha-Beta剪枝
在Minimax基础上增加剪枝：
– Alpha：Max节点目前能保证的最小得分下界
– Beta：Min节点目前能保证的最大得分上界
– 当 $\alpha \geq \beta$ 时，该分支无需继续搜索
评估函数设计
点格棋的评估需要综合考虑：
1. 当前得分差：已占领方格数之差
2. 链与环的结构：控制长链/环的玩家通常有优势
3. 可移动性：剩余可选边的数量
4. 关键边：可能送给对方方格的”毒药”边
Java实现
项目结构
dots-and-boxes/
├── src/
│ └── com/
│ └── dotsboxes/
│ ├── GameState.java // 游戏状态
│ ├── Move.java // 移动操作
│ ├── Evaluator.java // 评估函数
│ ├── MinimaxAI.java // Minimax AI
│ ├── GameBoard.java // 游戏界面
│ └── Main.java // 入口
游戏状态与移动
package com.dotsboxes;
import java.util.*;
/**
* 移动操作
*/
class Move {
enum Direction { HORIZONTAL, VERTICAL }
final Direction direction;
final int row;
final int col;
Move(Direction direction, int row, int col) {
this.direction = direction;
this.row = row;
this.col = col;
}
@Override
public String toString() {
return String.format("%s(%d,%d)", direction, row, col);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Move move = (Move) o;
return row == move.row && col == move.col && direction == move.direction;
}
@Override
public int hashCode() {
return Objects.hash(direction, row, col);
}
}
/**
* 游戏状态
*/
class GameState {
final int rows; // 方格行数
final int cols; // 方格列数
final boolean[][] hEdges; // 水平边
final boolean[][] vEdges; // 垂直边
final int[][] boxes; // 方格归属：0=空，1=玩家1，2=玩家2
int currentPlayer; // 当前行动玩家：1或2
int score1; // 玩家1得分
int score2; // 玩家2得分
int movesMade; // 已进行的移动数
GameState(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][cols];
this.currentPlayer = 1;
this.score1 = 0;
this.score2 = 0;
this.movesMade = 0;
}
/**
* 深拷贝
*/
GameState(GameState other) {
this.rows = other.rows;
this.cols = other.cols;
this.hEdges = new boolean[rows + 1][cols];
this.vEdges = new boolean[rows][cols + 1];
this.boxes = new int[rows][cols];
for (int i = 0; i <= rows; i++) {
System.arraycopy(other.hEdges[i], 0, this.hEdges[i], 0, cols);
}
for (int i = 0; i < rows; i++) {
System.arraycopy(other.vEdges[i], 0, this.vEdges[i], 0, cols + 1);
System.arraycopy(other.boxes[i], 0, this.boxes[i], 0, cols);
}
this.currentPlayer = other.currentPlayer;
this.score1 = other.score1;
this.score2 = other.score2;
this.movesMade = other.movesMade;
}
/**
* 生成所有合法移动
*/
List<Move> generateMoves() {
List<Move> moves = new ArrayList<>();
// 水平边
for (int i = 0; i <= rows; i++) {
for (int j = 0; j < cols; j++) {
if (!hEdges[i][j]) {
moves.add(new Move(Move.Direction.HORIZONTAL, i, j));
}
}
}
// 垂直边
for (int i = 0; i < rows; i++) {
for (int j = 0; j <= cols; j++) {
if (!vEdges[i][j]) {
moves.add(new Move(Move.Direction.VERTICAL, i, j));
}
}
}
return moves;
}
/**
* 应用移动，返回占领的方格数
*/
int applyMove(Move move) {
int boxesCaptured = 0;
if (move.direction == Move.Direction.HORIZONTAL) {
hEdges[move.row][move.col] = true;
// 检查下方的方格（如果存在）
if (move.row < rows) {
if (isBoxComplete(move.row, move.col)) {
boxes[move.row][move.col] = currentPlayer;
boxesCaptured++;
}
}
// 检查上方的方格（如果存在）
if (move.row > 0) {
if (isBoxComplete(move.row - 1, move.col)) {
boxes[move.row - 1][move.col] = currentPlayer;
boxesCaptured++;
}
}
} else {
vEdges[move.row][move.col] = true;
// 检查右方的方格（如果存在）
if (move.col < cols) {
if (isBoxComplete(move.row, move.col)) {
boxes[move.row][move.col] = currentPlayer;
boxesCaptured++;
}
}
// 检查左方的方格（如果存在）
if (move.col > 0) {
if (isBoxComplete(move.row, move.col - 1)) {
boxes[move.row][move.col - 1] = currentPlayer;
boxesCaptured++;
}
}
}
// 更新得分
if (currentPlayer == 1) score1 += boxesCaptured;
else score2 += boxesCaptured;
movesMade++;
// 如果没有占领方格，切换玩家
if (boxesCaptured == 0) {
currentPlayer = (currentPlayer == 1) ? 2 : 1;
}
return boxesCaptured;
}
/**
* 检查指定方格是否四边闭合
*/
private boolean isBoxComplete(int r, int c) {
return hEdges[r][c] && hEdges[r + 1][c] && vEdges[r][c] && vEdges[r][c + 1];
}
/**
* 检查游戏是否结束
*/
boolean isGameOver() {
return movesMade == (rows + 1) * cols + rows * (cols + 1);
}
/**
* 获取当前玩家视角的得分差
*/
int getScoreDiff() {
return (currentPlayer == 1) ? (score1 - score2) : (score2 - score1);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i <= rows; i++) {
// 打印点行
for (int j = 0; j <= cols; j++) {
sb.append("+");
if (j < cols) {
sb.append(hEdges[i][j] ? "---" : " ");
}
}
sb.append("\n");
// 打印方格行
if (i < rows) {
for (int j = 0; j <= cols; j++) {
if (j < cols) {
sb.append(vEdges[i][j] ? "|" : " ");
if (boxes[i][j] == 0) sb.append(" ");
else if (boxes[i][j] == 1) sb.append(" 1 ");
else sb.append(" 2 ");
} else {
sb.append(vEdges[i][j] ? "|" : " ");
}
}
sb.append("\n");
}
}
sb.append("Score: P1=").append(score1).append(" P2=").append(score2);
sb.append(" Current=").append(currentPlayer);
return sb.toString();
}
}
评估函数
package com.dotsboxes;
/**
* 评估函数
* 从当前行动玩家的视角评估局面
*/
public class Evaluator {
/**
* 综合评估函数
* 正值表示对当前玩家有利
*/
public static int evaluate(GameState state) {
if (state.isGameOver()) {
int diff = state.score1 - state.score2;
return (state.currentPlayer == 1) ? diff : -diff;
}
int score = 0;
// 1. 直接得分差（权重最高）
score += state.getScoreDiff() * 100;
// 2. 链与环分析（控制链的玩家有巨大优势）
score += analyzeChains(state) * 10;
// 3. 三方格威胁（即将完成3边的方格）
score += analyzeThreats(state) * 5;
// 4. 可完成方格数估计
score += estimateCapturableBoxes(state) * 3;
return score;
}
/**
* 分析链结构
* 长链和环的控制权是点格棋的高级策略核心
*/
private static int analyzeChains(GameState state) {
int chainValue = 0;
boolean[][] visited = new boolean[state.rows][state.cols];
for (int r = 0; r < state.rows; r++) {
for (int c = 0; c < state.cols; c++) {
if (state.boxes[r][c] != 0 || visited[r][c]) continue;
int edges = countBoxEdges(state, r, c);
if (edges == 0 || edges == 1) {
// 可能是链的起点，追踪链
int chainLen = traceChain(state, r, c, visited);
if (chainLen >= 3) {
// 长链的控制权分析：通常让对手先打开长链的玩家获利
chainValue += (chainLen % 2 == 0) ? chainLen : -chainLen;
}
}
}
}
return chainValue;
}
private static int countBoxEdges(GameState state, int r, int c) {
int count = 0;
if (state.hEdges[r][c]) count++;
if (state.hEdges[r + 1][c]) count++;
if (state.vEdges[r][c]) count++;
if (state.vEdges[r][c + 1]) count++;
return count;
}
private static int traceChain(GameState state, int startR, int startC, boolean[][] visited) {
// BFS追踪开放的方格链
int len = 0;
java.util.Queue<int[]> queue = new java.util.LinkedList<>();
queue.add(new int[]{startR, startC});
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int r = pos[0], c = pos[1];
if (visited[r][c]) continue;
visited[r][c] = true;
len++;
// 检查四个方向的相邻方格
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < state.rows && nc >= 0 && nc < state.cols
&& state.boxes[nr][nc] == 0 && !visited[nr][nc]) {
// 检查两个方格之间是否已有边
if (hasSharedEdge(state, r, c, nr, nc)) {
// 如果共享边已经画好，它们是连通的
// 但如果共享边未画，需要检查是否只能通过这条边连接
}
queue.add(new int[]{nr, nc});
}
}
}
return len;
}
private static boolean hasSharedEdge(GameState state, int r1, int c1, int r2, int c2) {
// 简化实现：假设相邻方格总是连通的
return true;
}
/**
* 分析威胁方格（已有3边的方格）
*/
private static int analyzeThreats(GameState state) {
int threats = 0;
for (int r = 0; r < state.rows; r++) {
for (int c = 0; c < state.cols; c++) {
if (state.boxes[r][c] != 0) continue;
if (countBoxEdges(state, r, c) == 3) {
// 这个方格即将被完成，下一位玩家会占领它
threats--;
}
}
}
return threats;
}
/**
* 估计双方还能占领的方格数
*/
private static int estimateCapturableBoxes(GameState state) {
int capturable = 0;
for (int r = 0; r < state.rows; r++) {
for (int c = 0; c < state.cols; c++) {
if (state.boxes[r][c] != 0) continue;
int edges = countBoxEdges(state, r, c);
if (edges == 2) capturable += 1;
}
}
return capturable;
}
}
Minimax AI with Alpha-Beta
package com.dotsboxes;
import java.util.*;
/**
* Minimax AI with Alpha-Beta剪枝
*/
public class MinimaxAI {
private final int maxDepth;
private int nodesEvaluated = 0;
public MinimaxAI(int maxDepth) {
this.maxDepth = maxDepth;
}
/**
* 选择最佳移动
*/
public Move findBestMove(GameState state) {
List<Move> moves = state.generateMoves();
if (moves.isEmpty()) return null;
// 优先尝试可能得分的移动（移动排序优化）
moves.sort((m1, m2) -> {
GameState s1 = new GameState(state);
int c1 = s1.applyMove(m1);
GameState s2 = new GameState(state);
int c2 = s2.applyMove(m2);
return Integer.compare(c2, c1); // 得分高的优先
});
Move bestMove = null;
int bestValue = Integer.MIN_VALUE;
for (Move move : moves) {
GameState next = new GameState(state);
next.applyMove(move);
int value = minimax(next, maxDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, false);
if (value > bestValue) {
bestValue = value;
bestMove = move;
}
}
return bestMove;
}
/**
* Minimax递归搜索
* @param isMaximizing true表示当前是Max层（我方回合）
*/
private int minimax(GameState state, int depth, int alpha, int beta, boolean isMaximizing) {
nodesEvaluated++;
// 终止条件
if (depth == 0 || state.isGameOver()) {
return Evaluator.evaluate(state);
}
List<Move> moves = state.generateMoves();
if (moves.isEmpty()) {
return Evaluator.evaluate(state);
}
if (isMaximizing) {
int maxEval = Integer.MIN_VALUE;
for (Move move : moves) {
GameState next = new GameState(state);
next.applyMove(move);
// 如果占领了方格，仍然是当前玩家的回合（连击）
boolean stillMyTurn = (next.currentPlayer == state.currentPlayer);
int eval = minimax(next, depth - 1, alpha, beta, stillMyTurn);
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break; // Beta剪枝
}
return maxEval;
} else {
int minEval = Integer.MAX_VALUE;
for (Move move : moves) {
GameState next = new GameState(state);
next.applyMove(move);
boolean stillOpponentTurn = (next.currentPlayer != state.currentPlayer);
int eval = minimax(next, depth - 1, alpha, beta, stillOpponentTurn);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break; // Alpha剪枝
}
return minEval;
}
}
public int getNodesEvaluated() { return nodesEvaluated; }
}
演示入口
package com.dotsboxes;
/**
* 点格棋AI演示
*/
public class Main {
public static void main(String[] args) {
// 3x3 点格棋
GameState state = new GameState(3, 3);
MinimaxAI ai = new MinimaxAI(6); // 搜索深度6
System.out.println("=== 点格棋 Minimax AI ===\n");
System.out.println("初始棋盘：");
System.out.println(state);
// AI vs 随机玩家 演示前10步
java.util.Random random = new java.util.Random(123);
for (int turn = 0; turn < 10 && !state.isGameOver(); turn++) {
Move move;
String playerName;
if (state.currentPlayer == 1) {
// AI移动
playerName = "AI(玩家1)";
move = ai.findBestMove(state);
} else {
// 随机移动
playerName = "随机(玩家2)";
var moves = state.generateMoves();
move = moves.get(random.nextInt(moves.size()));
}
if (move == null) break;
int captured = state.applyMove(move);
System.out.println("\n" + playerName + " 移动: " + move +
(captured > 0 ? " [占领" + captured + "格!]" : ""));
System.out.println(state);
}
System.out.println("\n评估节点数：" + ai.getNodesEvaluated());
}
}
算法优化策略
1. 移动排序（Move Ordering）
优先尝试可能占领方格的移动，可显著提高Alpha-Beta剪枝效率。
2. 置换表（Transposition Table）
使用Zobrist哈希缓存已评估状态，避免重复计算。
3. 迭代加深（Iterative Deepening）
从浅层到深层逐步搜索，配合时间控制。
4. 终局数据库
对剩余边数很少的局面预计算最优解。
复杂度分析
状态空间
总边数为 $(N+1) \times M + N \times (M+1)$。对于 $3 \times 3$ 棋盘，共24条边，状态空间上界 $2^{24} \approx 1600$ 万。
搜索复杂度
- Minimax：$O(b^d)$，$b$ 为分支因子，$d$ 为深度
- Alpha-Beta剪枝：理想情况下 $O(b^{d/2})$，移动排序良好时接近此界限
总结
点格棋AI展示了博弈论中的核心概念：Minimax搜索、Alpha-Beta剪枝、评估函数设计。与简单的贪”吃”策略不同，高级点格棋玩法需要牺牲短期利益以控制长链——这是典型的组合博弈论（Combinatorial Game Theory）现象。这些技术同样适用于 chess、围棋、五子棋等更复杂的对抗性游戏AI。
