引言
五子棋是两人对弈的纯策略型棋类游戏，规则简单但变化无穷。与基于Minimax的Alpha-Beta剪枝不同，蒙特卡洛树搜索（MCTS）通过随机模拟来评估局面，无需复杂的静态估值函数，在围棋、五子棋等游戏中表现出色。本文将用Java实现带MCTS AI的五子棋，讲解UCT选择策略、扩展、模拟与反向传播四个核心阶段。
蒙特卡洛树搜索核心原理
MCTS通过迭代构建搜索树，每次迭代包含四个步骤：
- 选择（Selection）：从根节点出发，使用UCT公式选择子节点，直到到达未完全扩展的节点。
- 扩展（Expansion）：为选中的节点添加一个或多个子节点。
- 模拟（Simulation）：从新节点出发进行随机对弈，直到终局。
- 反向传播（Backpropagation）：将模拟结果沿路径更新到根节点。
UCT公式平衡了探索与利用：
$$
UCT = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}}
$$
其中 $w_i$ 为获胜次数，$n_i$ 为访问次数，$N$ 为父节点访问次数，$c$ 为探索常数。
Java实现
棋盘与游戏状态
public class GomokuBoard {
public static final int SIZE = 15;
public static final int EMPTY = 0;
public static final int BLACK = 1;
public static final int WHITE = 2;
private int[][] board;
private int currentPlayer;
public GomokuBoard() {
board = new int[SIZE][SIZE];
currentPlayer = BLACK;
}
public GomokuBoard(GomokuBoard other) {
this.board = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(other.board[i], 0, this.board[i], 0, SIZE);
}
this.currentPlayer = other.currentPlayer;
}
public boolean placeStone(int row, int col) {
if (row < 0 || row >= SIZE || col < 0 || col >= SIZE || board[row][col] != EMPTY) {
return false;
}
board[row][col] = currentPlayer;
currentPlayer = (currentPlayer == BLACK) ? WHITE : BLACK;
return true;
}
public int checkWinner() {
int[][] dirs = {{0,1}, {1,0}, {1,1}, {1,-1}};
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == EMPTY) continue;
int player = board[r][c];
for (int[] d : dirs) {
int count = 1;
for (int step = 1; step < 5; step++) {
int nr = r + d[0] * step;
int nc = c + d[1] * step;
if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE && board[nr][nc] == player) {
count++;
} else break;
}
if (count >= 5) return player;
}
}
}
return EMPTY;
}
public boolean isFull() {
for (int[] row : board) {
for (int cell : row) {
if (cell == EMPTY) return false;
}
}
return true;
}
public List<int[]> getEmptyPositions() {
List<int[]> positions = new ArrayList<>();
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == EMPTY) {
positions.add(new int[]{r, c});
}
}
}
return positions;
}
public int getCurrentPlayer() { return currentPlayer; }
public int[][] getBoard() { return board; }
}
MCTS节点
public class MCTSNode {
GomokuBoard state;
MCTSNode parent;
List<MCTSNode> children;
int[] move; // {row, col}
int visits;
double wins;
int player; // 执行该move的玩家
public MCTSNode(GomokuBoard state, MCTSNode parent, int[] move, int player) {
this.state = state;
this.parent = parent;
this.move = move;
this.player = player;
this.children = new ArrayList<>();
this.visits = 0;
this.wins = 0;
}
public boolean isFullyExpanded() {
return children.size() == state.getEmptyPositions().size();
}
public MCTSNode bestChild(double c) {
MCTSNode best = null;
double bestValue = Double.NEGATIVE_INFINITY;
for (MCTSNode child : children) {
if (child.visits == 0) return child;
double uct = (child.wins / child.visits) + c * Math.sqrt(Math.log(this.visits) / child.visits);
if (uct > bestValue) {
bestValue = uct;
best = child;
}
}
return best;
}
}
MCTS AI核心
public class MCTSPlayer {
private static final int SIMULATION_COUNT = 10000;
private static final double EXPLORATION_CONSTANT = Math.sqrt(2);
private int aiPlayer;
private Random random;
public MCTSPlayer(int aiPlayer) {
this.aiPlayer = aiPlayer;
this.random = new Random();
}
public int[] findBestMove(GomokuBoard board) {
MCTSNode root = new MCTSNode(new GomokuBoard(board), null, null, board.getCurrentPlayer());
for (int i = 0; i < SIMULATION_COUNT; i++) {
MCTSNode node = select(root);
int result = simulate(node);
backpropagate(node, result);
}
// 选择访问次数最多的子节点作为最佳走法
MCTSNode best = null;
int maxVisits = -1;
for (MCTSNode child : root.children) {
if (child.visits > maxVisits) {
maxVisits = child.visits;
best = child;
}
}
return best != null ? best.move : null;
}
private MCTSNode select(MCTSNode node) {
while (!node.state.getEmptyPositions().isEmpty() && node.state.checkWinner() == GomokuBoard.EMPTY) {
if (!node.isFullyExpanded()) {
return expand(node);
}
node = node.bestChild(EXPLORATION_CONSTANT);
}
return node;
}
private MCTSNode expand(MCTSNode node) {
List<int[]> empty = node.state.getEmptyPositions();
Set<String> existing = new HashSet<>();
for (MCTSNode child : node.children) {
existing.add(child.move[0] + "," + child.move[1]);
}
for (int[] move : empty) {
String key = move[0] + "," + move[1];
if (!existing.contains(key)) {
GomokuBoard newState = new GomokuBoard(node.state);
newState.placeStone(move[0], move[1]);
MCTSNode child = new MCTSNode(newState, node, move, node.state.getCurrentPlayer());
node.children.add(child);
return child;
}
}
return node;
}
private int simulate(MCTSNode node) {
GomokuBoard simBoard = new GomokuBoard(node.state);
while (simBoard.checkWinner() == GomokuBoard.EMPTY && !simBoard.isFull()) {
List<int[]> empty = simBoard.getEmptyPositions();
int[] move = empty.get(random.nextInt(empty.size()));
simBoard.placeStone(move[0], move[1]);
}
return simBoard.checkWinner();
}
private void backpropagate(MCTSNode node, int winner) {
while (node != null) {
node.visits++;
// 如果winner是当前节点的player（即执行该节点move的玩家），则加分
if (winner != GomokuBoard.EMPTY && winner == node.player) {
node.wins += 1.0;
} else if (winner == GomokuBoard.EMPTY) {
node.wins += 0.5; // 平局
}
node = node.parent;
}
}
}
主程序
public class GomokuGame {
public static void main(String[] args) {
GomokuBoard board = new GomokuBoard();
MCTSPlayer ai = new MCTSPlayer(GomokuBoard.BLACK);
Scanner scanner = new Scanner(System.in);
while (board.checkWinner() == GomokuBoard.EMPTY && !board.isFull()) {
printBoard(board);
if (board.getCurrentPlayer() == GomokuBoard.BLACK) {
System.out.println("AI思考中...");
int[] move = ai.findBestMove(board);
board.placeStone(move[0], move[1]);
System.out.println("AI落子: " + move[0] + "," + move[1]);
} else {
System.out.print("请输入落子位置(行 列): ");
int r = scanner.nextInt();
int c = scanner.nextInt();
board.placeStone(r, c);
}
}
printBoard(board);
int winner = board.checkWinner();
System.out.println(winner == GomokuBoard.EMPTY ? "平局" : (winner == GomokuBoard.BLACK ? "AI胜" : "玩家胜"));
}
static void printBoard(GomokuBoard board) {
int[][] b = board.getBoard();
System.out.print(" ");
for (int c = 0; c < GomokuBoard.SIZE; c++) System.out.print(c % 10 + " ");
System.out.println();
for (int r = 0; r < GomokuBoard.SIZE; r++) {
System.out.print(r % 10 + " ");
for (int c = 0; c < GomokuBoard.SIZE; c++) {
char ch = b[r][c] == GomokuBoard.EMPTY ? '.' : (b[r][c] == GomokuBoard.BLACK ? 'X' : 'O');
System.out.print(ch + " ");
}
System.out.println();
}
}
}
算法优化建议
- 启发式模拟：在模拟阶段优先选择有连子潜力的位置，而非完全随机。
- 先验知识：扩展时优先评估靠近已有棋子的位置，减少搜索空间。
- 并行化：多线程并行运行多次MCTS迭代，提升搜索深度。
- RAVE快速行动价值估计：共享兄弟节点的模拟结果，加速收敛。
复杂度分析
- 时间复杂度：每次迭代为 $O(d + s)$，其中 $d$ 为树深度，$s$ 为模拟步数。总复杂度 $O(k(d+s))$，$k$ 为迭代次数。
- 空间复杂度：$O(k)$，与迭代次数和树的分支因子成正比。
总结
蒙特卡洛树搜索通过统计模拟结果来指导决策，无需人工设计的估值函数，在信息不完全或状态空间巨大的场景中表现优异。本文实现的UCT策略在五子棋中能有效平衡探索与利用，通过调整模拟次数和探索常数可进一步提升棋力。
