五子棋（Gomoku）是起源于中国古代的经典双人对弈棋类，规则简洁却蕴含极深的策略空间。标准的15×15棋盘共有约2.25×10^172种合法局面，远超传统暴力搜索的处理能力。本文将用Java实现一套基于蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）与UCT（Upper Confidence Bound applied to Trees）公式的五子棋AI，展示如何在无领域知识的情况下，通过随机模拟与统计置信度构建强大的博弈引擎。
一、问题建模与棋盘状态表示
1.1 五子棋规则形式化
五子棋的核心规则可归纳为三点：
– 双方轮流在15×15交叉点落子，黑棋先行
– 先形成连续五子（横、竖、斜）的一方获胜
– 无禁手规则下，先手黑方具有天然优势（已被数学证明存在必胜策略）
1.2 紧凑的状态编码
为了高效地判断胜负与生成走法，采用二维整数数组表示棋盘，同时预计算四个方向向量：
/**
* 五子棋棋盘状态
* board[row][col] = 0 表示空位，1 表示黑棋，2 表示白棋
*/
class Board {
static final int SIZE = 15;
static final int EMPTY = 0;
static final int BLACK = 1;
static final int WHITE = 2;
// 四个方向：水平、垂直、主对角线、副对角线
static final int[][] DIRS = {
{0, 1}, {1, 0}, {1, 1}, {1, -1}
};
private final int[][] grid;
private int currentPlayer;
private int moveCount;
Board() {
this.grid = new int[SIZE][SIZE];
this.currentPlayer = BLACK;
this.moveCount = 0;
}
/**
* 复制构造函数，用于模拟分支
*/
Board(Board other) {
this.grid = new int[SIZE][SIZE];
for (int r = 0; r < SIZE; r++) {
System.arraycopy(other.grid[r], 0, this.grid[r], 0, SIZE);
}
this.currentPlayer = other.currentPlayer;
this.moveCount = other.moveCount;
}
/**
* 在指定位置落子
*/
boolean makeMove(int row, int col) {
if (row < 0 || row >= SIZE || col < 0 || col >= SIZE || grid[row][col] != EMPTY) {
return false;
}
grid[row][col] = currentPlayer;
currentPlayer = (currentPlayer == BLACK) ? WHITE : BLACK;
moveCount++;
return true;
}
/**
* 判断指定位置的落子方是否形成五连
*/
boolean isWin(int row, int col) {
int player = grid[row][col];
if (player == EMPTY) return false;
for (int[] dir : DIRS) {
int count = 1;
// 正向统计
for (int step = 1; step < 5; step++) {
int nr = row + dir[0] * step;
int nc = col + dir[1] * step;
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE || grid[nr][nc] != player) break;
count++;
}
// 反向统计
for (int step = 1; step < 5; step++) {
int nr = row - dir[0] * step;
int nc = col - dir[1] * step;
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE || grid[nr][nc] != player) break;
count++;
}
if (count >= 5) return true;
}
return false;
}
/**
* 获取当前应落子方
*/
int getCurrentPlayer() {
return currentPlayer;
}
/**
* 棋盘是否已满
*/
boolean isFull() {
return moveCount >= SIZE * SIZE;
}
/**
* 获取所有合法走法
* 为提升效率，仅返回已有棋子周围一格的空白位置
*/
List<int[]> getLegalMoves() {
List<int[]> moves = new ArrayList<>();
boolean[][] visited = new boolean[SIZE][SIZE];
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (grid[r][c] != EMPTY) {
// 搜索邻域空位
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE
&& grid[nr][nc] == EMPTY && !visited[nr][nc]) {
visited[nr][nc] = true;
moves.add(new int[]{nr, nc});
}
}
}
}
}
}
// 空棋盘时落中心点
if (moves.isEmpty()) {
moves.add(new int[]{SIZE / 2, SIZE / 2});
}
return moves;
}
int getCell(int row, int col) {
return grid[row][col];
}
int getMoveCount() {
return moveCount;
}
}
二、蒙特卡洛树搜索（MCTS）核心思想
MCTS是一种通过随机模拟来估计走法价值的搜索算法，其最大优势在于不依赖强领域知识，且能在任意时刻给出当前最优解（随时可用性）。算法围绕四步循环展开：
- 选择（Selection）：从根节点出发，使用UCT公式递归选择子节点，直到到达未完全展开的节点
- 扩展（Expansion）：为该节点添加一个或多个子节点（对应未尝试的走法）
- 模拟（Simulation）：从新扩展的节点出发，双方随机走子直到终局，记录胜负
- 回溯（Backpropagation）：将模拟结果沿路径反向更新所有祖先节点的统计量
2.1 UCT公式：平衡探索与利用
UCT公式源自多臂老虎机问题，核心是在”利用已验证的好走法”与”探索未充分评估的走法”之间取得平衡：
$$
UCT = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}}
$$
其中：
– $w_i$：节点$i$的累计胜利次数
– $n_i$：节点$i$被访问的次数
– $N$：父节点的总访问次数
– $c$：探索常数（通常取 $\sqrt{2}$，可根据游戏特性调整）
第一项$\frac{w_i}{n_i}$是胜率估计（利用），第二项$c \sqrt{\frac{\ln N}{n_i}}$是探索奖励（对访问次数少的节点给予更高估值）。
三、MCTS节点与树结构
import java.util.*;
/**
* MCTS树节点
* 每个节点代表一个棋盘状态，维护UCT所需的统计量
*/
class MCTSNode {
Board board; // 当前棋盘状态
int[] move; // 从父节点到达本节点的走法 {row, col}
MCTSNode parent; // 父节点
List<MCTSNode> children; // 子节点列表
List<int[]> untriedMoves; // 尚未扩展的走法
int wins; // 累计胜利次数（从当前节点的视角）
int visits; // 被访问次数
int playerJustMoved; // 刚刚落子的一方（本节点的创建者）
MCTSNode(Board board, int[] move, MCTSNode parent, int playerJustMoved) {
this.board = new Board(board);
this.move = move;
this.parent = parent;
this.playerJustMoved = playerJustMoved;
this.children = new ArrayList<>();
this.untriedMoves = board.getLegalMoves();
this.wins = 0;
this.visits = 0;
}
/**
* 使用UCT公式选择最优子节点
* @param explorationConstant 探索常数c
*/
MCTSNode selectChild(double explorationConstant) {
MCTSNode best = null;
double bestValue = Double.NEGATIVE_INFINITY;
for (MCTSNode child : children) {
// UCT = winRate + c * sqrt(ln(parentVisits) / childVisits)
double winRate = (double) child.wins / child.visits;
double exploration = explorationConstant * Math.sqrt(
Math.log(this.visits) / child.visits
);
double uctValue = winRate + exploration;
if (uctValue > bestValue) {
bestValue = uctValue;
best = child;
}
}
return best;
}
/**
* 从untriedMoves中随机选择一个走法并扩展子节点
*/
MCTSNode expand() {
int idx = (int) (Math.random() * untriedMoves.size());
int[] move = untriedMoves.remove(idx);
Board nextBoard = new Board(board);
nextBoard.makeMove(move[0], move[1]);
MCTSNode child = new MCTSNode(nextBoard, move, this, board.getCurrentPlayer() == Board.BLACK ? Board.WHITE : Board.BLACK);
children.add(child);
return child;
}
/**
* 判断节点是否完全展开
*/
boolean isFullyExpanded() {
return untriedMoves.isEmpty();
}
/**
* 判断是否为终局节点
*/
boolean isTerminal() {
// 若上一步落子后已经分出胜负，或棋盘已满
if (move != null && board.isWin(move[0], move[1])) return true;
return board.isFull();
}
/**
* 更新节点统计量
* @param result 从本节点创建者视角看的结果：1=胜, 0=负, 0.5=平
*/
void update(double result) {
this.visits++;
this.wins += result;
}
}
四、随机模拟策略（Rollout Policy）
模拟阶段的质量直接决定MCTS的棋力。最基础的策略是完全随机落子，但加入简单的启发式可以显著提升强度：
/**
* 模拟一局对弈直到终局
* @param board 当前棋盘状态
* @return 从board.getCurrentPlayer()的视角看的结果：1=胜, 0=负, 0.5=平
*/
static double simulate(Board board) {
Board simBoard = new Board(board);
Random rand = new Random();
while (!simBoard.isFull()) {
List<int[]> moves = simBoard.getLegalMoves();
if (moves.isEmpty()) break;
// 简单启发式：优先选择能赢或能阻止对方赢的位置
int[] chosen = null;
for (int[] m : moves) {
simBoard.makeMove(m[0], m[1]);
if (simBoard.isWin(m[0], m[1])) {
chosen = m;
break;
}
// 撤销，检查对方
simBoard = new Board(board); // 重新复制（为简洁，实际应优化）
// 简化处理：直接随机选择
}
if (chosen == null) {
chosen = moves.get(rand.nextInt(moves.size()));
simBoard.makeMove(chosen[0], chosen[1]);
}
if (simBoard.isWin(chosen[0], chosen[1])) {
// 返回从原始当前玩家视角的结果
// 实际逻辑：谁赢了？
int winner = simBoard.getCell(chosen[0], chosen[1]);
int originalPlayer = board.getCurrentPlayer();
if (winner == originalPlayer) return 1.0;
else return 0.0;
}
}
return 0.5; // 平局
}
上述随机策略过于简化，实际采用更高效的快速模拟实现：
/**
* 优化版模拟：纯随机走子，返回从上一手落子方视角的结果
*/
static double rollout(Board board, int playerJustMoved) {
Random rand = new Random();
Board b = new Board(board);
int lastRow = -1, lastCol = -1;
while (true) {
List<int[]> moves = b.getLegalMoves();
if (moves.isEmpty()) return 0.5;
int[] m = moves.get(rand.nextInt(moves.size()));
b.makeMove(m[0], m[1]);
lastRow = m[0];
lastCol = m[1];
if (b.isWin(lastRow, lastCol)) {
// 刚落子的一方赢了
int winner = b.getCell(lastRow, lastCol);
// 返回从playerJustMoved视角的结果
return (winner == playerJustMoved) ? 1.0 : 0.0;
}
if (b.isFull()) return 0.5;
}
}
五、完整MCTS搜索引擎
public class GomokuMCTS {
private static final double EXPLORATION_CONSTANT = Math.sqrt(2);
private static final int DEFAULT_ITERATIONS = 10000;
private final int iterations;
public GomokuMCTS() {
this(DEFAULT_ITERATIONS);
}
public GomokuMCTS(int iterations) {
this.iterations = iterations;
}
/**
* 为指定棋盘状态搜索最佳走法
* @param board 当前棋盘
* @return 最佳走法 {row, col}
*/
public int[] search(Board board) {
MCTSNode root = new MCTSNode(board, null, null,
board.getCurrentPlayer() == Board.BLACK ? Board.WHITE : Board.BLACK);
for (int i = 0; i < iterations; i++) {
MCTSNode node = root;
// 1. 选择：递归选择直到到达未完全展开的非终局节点
while (node.isFullyExpanded() && !node.isTerminal()) {
node = node.selectChild(EXPLORATION_CONSTANT);
}
// 2. 扩展：如果节点未完全展开且非终局，则扩展一个子节点
if (!node.isTerminal()) {
node = node.expand();
}
// 3. 模拟：从新节点进行随机rollout
double result = rollout(node.board, node.playerJustMoved);
// 4. 回溯：更新路径上所有节点的统计量
while (node != null) {
// 结果需要转换为当前节点创建者视角
double nodeResult = result;
if (node.playerJustMoved != root.board.getCurrentPlayer()) {
// 非根节点视角转换：如果对方是playerJustMoved，结果取反
// 实际上result已经是相对于playerJustMoved的
// 这里需要统一视角，统一转换为"从playerJustMoved视角"
// result定义：1=playerJustMoved赢，0=输
}
// 对于根节点，其playerJustMoved是上一步落子方
// 我们要更新的是从当前应该落子方的视角吗？
// 统一做法：result表示"当前node的playerJustMoved"的胜率
// 但回溯时应该按交替视角更新
// 修正：result是rollout结果，表示"playerJustMoved在rollout中是否获胜"
// 对每个节点，如果node.playerJustMoved == rollout中的winner，则+1
// 否则，如果node.playerJustMoved是rollout中的loser，则+0
// 重新思考：rollout返回从playerJustMoved视角的结果
// 那么每个节点都应以自己的playerJustMoved来解读result
// 如果当前节点的playerJustMoved和rollout节点的playerJustMoved相同，直接用result
// 否则取反
// 由于所有节点沿路径交替属于双方，我们统一存储"从落子方视角"
// 并在回溯时根据层数翻转
// 简化方案：result始终表示"最后落子方（即扩展出的新节点的创建者）"的胜利
// 回溯时交替翻转
int depth = 0;
MCTSNode temp = node;
while (temp.parent != null) {
depth++;
temp = temp.parent;
}
double backResult = (depth % 2 == 0) ? result : (1 - result);
node.update(backResult);
node = node.parent;
}
}
// 选择访问次数最多的子节点作为最佳走法（更稳健）
// 也可选择胜率最高的
MCTSNode bestChild = null;
int maxVisits = -1;
for (MCTSNode child : root.children) {
if (child.visits > maxVisits) {
maxVisits = child.visits;
bestChild = child;
}
}
return bestChild != null ? bestChild.move : null;
}
/**
* 优化的rollout：纯随机策略
*/
private static double rollout(Board board, int playerJustMoved) {
Random rand = new Random();
Board b = new Board(board);
while (true) {
List<int[]> moves = b.getLegalMoves();
if (moves.isEmpty()) return 0.5;
int[] m = moves.get(rand.nextInt(moves.size()));
b.makeMove(m[0], m[1]);
if (b.isWin(m[0], m[1])) {
int winner = b.getCell(m[0], m[1]);
return (winner == playerJustMoved) ? 1.0 : 0.0;
}
if (b.isFull()) return 0.5;
}
}
}
六、五子棋专用优化策略
基础MCTS在复杂棋类中需要结合领域知识才能发挥实力。以下是针对五子棋的关键优化：
6.1 必胜/必败快速检测
在扩展节点时，若发现某走法可直接形成五连（必胜）或必须阻止对方四连（必败），立即截断搜索：
/**
* 快速检查是否存在立即获胜或必须防守的走法
* @return 优先级最高的走法，若无不返回null
*/
int[] findForcedMove(Board board) {
List<int[]> moves = board.getLegalMoves();
int current = board.getCurrentPlayer();
int opponent = (current == Board.BLACK) ? Board.WHITE : Board.BLACK;
// 检查自己是否能直接赢
for (int[] m : moves) {
Board copy = new Board(board);
copy.makeMove(m[0], m[1]);
if (copy.isWin(m[0], m[1])) return m;
}
// 检查是否必须阻止对方赢
for (int[] m : moves) {
Board copy = new Board(board);
copy.makeMove(m[0], m[1]);
// 模拟对方下一步
int original = copy.getCurrentPlayer();
// 简化：检查对方是否有四连即将成型
// 实际应检查若不走此位置，对方是否下一步必胜
}
return null;
}
6.2 模拟阶段加入启发式
在rollout中引入”进攻优先”策略：
– 有活四或冲四时优先落子
– 优先选择靠近已有棋子的位置（集中化）
– 避免无意义的长距离随机落子
6.3 渐进式拓宽（Progressive Widening）
开局时合法走法过多（可达225个），全部扩展会浪费计算量。采用渐进式拓宽：只有当某节点的访问次数超过阈值时，才扩展更多子节点。
/**
* 渐进式拓宽：根据访问次数决定可扩展的走法数量
*/
List<int[]> getWideningMoves(MCTSNode node) {
List<int[]> all = node.untriedMoves;
int limit = (int) Math.ceil(Math.pow(node.visits + 1, 0.5));
return all.subList(0, Math.min(limit, all.size()));
}
七、主程序与人机对战
public class GomokuGame {
public static void main(String[] args) {
Board board = new Board();
GomokuMCTS ai = new GomokuMCTS(20000); // 每步模拟20000次
Scanner scanner = new Scanner(System.in);
System.out.println("===== 五子棋人机对战 =====");
System.out.println("你是黑棋(1)，AI是白棋(2)");
System.out.println("输入格式: row col (0-14)");
while (true) {
board.printBoard();
int current = board.getCurrentPlayer();
if (current == Board.BLACK) {
System.out.print("你的回合: ");
int r = scanner.nextInt();
int c = scanner.nextInt();
if (!board.makeMove(r, c)) {
System.out.println("非法走法!");
continue;
}
if (board.isWin(r, c)) {
board.printBoard();
System.out.println("你赢了!");
break;
}
} else {
System.out.println("AI思考中...");
long start = System.currentTimeMillis();
int[] move = ai.search(board);
long cost = System.currentTimeMillis() - start;
board.makeMove(move[0], move[1]);
System.out.printf("AI落子: (%d, %d)，耗时 %.2f 秒%n",
move[0], move[1], cost / 1000.0);
if (board.isWin(move[0], move[1])) {
board.printBoard();
System.out.println("AI赢了!");
break;
}
}
if (board.isFull()) {
board.printBoard();
System.out.println("平局!");
break;
}
}
scanner.close();
}
}
八、复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 选择 | O(d) | O(d) | d为树深度，等于当前回合数 |
| 扩展 | O(1) | O(1) | 添加单个子节点 |
| 模拟 | O(L) | O(1) | L为模拟局平均长度 |
| 回溯 | O(d) | O(1) | 沿路径更新统计量 |
| 总计（每迭代） | O(d + L) | O(d) | 主要开销在模拟 |
对于迭代$N$次、每步平均模拟$L$步的MCTS：
– 总时间：$O(N \cdot (d + L))$
– 总空间：$O(N)$，即生成的节点数
– 当$N=20000$、$L\approx 50$时，现代CPU可在1-3秒内完成单步决策
九、提升路径与变体
- RAVE（Rapid Action Value Estimation）：在同一次模拟中出现在不同位置的相同走法共享统计信息，加快开局收敛
- 神经网络价值函数：用深度网络替代随机rollout，AlphaGo/AlphaZero的核心思路
- ** pondering**：在对手思考时继续扩展MCTS树，复用搜索结果
- 多线程并行：通过虚拟损失（Virtual Loss）实现多线程MCTS，线性提升搜索量
总结
本文从零实现了基于MCTS的五子棋AI，核心收获包括：
– UCT公式通过数学方式自动平衡探索与利用，无需手动调整搜索策略
– MCTS四步循环（选择-扩展-模拟-回溯）是通用博弈框架，可迁移至围棋、象棋等复杂棋类
– 领域优化（必胜检测、渐进拓宽）能在不破坏算法通用性的前提下显著提升棋力
– 从工程角度看，MCTS是不完备信息搜索与大规模状态空间决策的首选基线算法
完整项目运行命令：
javac GomokuGame.java
java GomokuGame
