算法概述
蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）是一种结合了随机模拟与树搜索的决策算法。它通过大量随机对局来评估棋局状态，无需复杂的启发式评估函数即可在复杂博弈中找到近似最优解。MCTS的四个核心阶段为：选择（Selection）、扩展（Expansion）、模拟（Simulation）和反向传播（Backpropagation）。
UCT公式
UCT（Upper Confidence Bound applied to Trees）公式用于平衡探索与利用：
UCT = wins/visits + C * sqrt(ln(parentVisits) / visits)
其中C为探索常数，通常取sqrt(2)。
完整Java实现
import java.util.*;
/**
* MCTS（蒙特卡洛树搜索）实现 - 以井字棋为例
*/
public class MCTSTicTacToe {
// 探索常数，平衡探索与利用
private static final double EXPLORATION_CONSTANT = Math.sqrt(2);
// 每次决策的模拟次数
private static final int SIMULATIONS = 5000;
// 玩家标识
private static final int PLAYER_X = 1;
private static final int PLAYER_O = 2;
private static final int EMPTY = 0;
/**
* 树节点：表示博弈树中的一个状态
*/
static class TreeNode {
int[][] board; // 当前棋盘状态
int player; // 当前轮到哪个玩家
TreeNode parent; // 父节点
List<TreeNode> children;// 子节点列表
int visits = 0; // 访问次数
double wins = 0; // 胜利次数（从当前玩家视角）
boolean isTerminal = false; // 是否为终局
int terminalResult = 0; // 终局结果：1=X胜, 2=O胜, -1=平局
TreeNode(int[][] board, int player, TreeNode parent) {
this.board = copyBoard(board);
this.player = player;
this.parent = parent;
this.children = new ArrayList<>();
checkTerminal();
}
int[][] copyBoard(int[][] src) {
int[][] dst = new int[3][3];
for (int i = 0; i < 3; i++)
dst[i] = src[i].clone();
return dst;
}
void checkTerminal() {
int winner = checkWinner(board);
if (winner != 0) {
isTerminal = true;
terminalResult = winner;
return;
}
if (isBoardFull(board)) {
isTerminal = true;
terminalResult = -1;
}
}
boolean isBoardFull(int[][] b) {
for (int[] row : b)
for (int cell : row)
if (cell == EMPTY) return false;
return true;
}
int checkWinner(int[][] b) {
for (int i = 0; i < 3; i++) {
if (b[i][0] != EMPTY && b[i][0] == b[i][1] && b[i][1] == b[i][2])
return b[i][0];
if (b[0][i] != EMPTY && b[0][i] == b[1][i] && b[1][i] == b[2][i])
return b[0][i];
}
if (b[0][0] != EMPTY && b[0][0] == b[1][1] && b[1][1] == b[2][2])
return b[0][0];
if (b[0][2] != EMPTY && b[0][2] == b[1][1] && b[1][1] == b[2][0])
return b[0][2];
return 0;
}
List<int[]> getLegalMoves() {
List<int[]> moves = new ArrayList<>();
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == EMPTY)
moves.add(new int[]{i, j});
return moves;
}
boolean isFullyExpanded() {
return children.size() == getLegalMoves().size();
}
TreeNode selectBestChild() {
TreeNode best = null;
double bestValue = Double.NEGATIVE_INFINITY;
for (TreeNode child : children) {
double uctValue;
if (child.visits == 0) {
uctValue = Double.POSITIVE_INFINITY;
} else {
double winRate = child.wins / child.visits;
double exploration = EXPLORATION_CONSTANT *
Math.sqrt(Math.log(this.visits) / child.visits);
uctValue = winRate + exploration;
}
if (uctValue > bestValue) {
bestValue = uctValue;
best = child;
}
}
return best;
}
}
public int[] findBestMove(int[][] board, int currentPlayer) {
TreeNode root = new TreeNode(board, currentPlayer, null);
for (int i = 0; i < SIMULATIONS; i++) {
TreeNode selected = select(root);
TreeNode expanded = expand(selected);
int result = simulate(expanded);
backpropagate(expanded, result, currentPlayer);
}
TreeNode bestChild = null;
int maxVisits = -1;
for (TreeNode child : root.children) {
if (child.visits > maxVisits) {
maxVisits = child.visits;
bestChild = child;
}
}
return findMove(root.board, bestChild.board);
}
TreeNode select(TreeNode node) {
while (!node.isTerminal && node.isFullyExpanded()) {
node = node.selectBestChild();
}
return node;
}
TreeNode expand(TreeNode node) {
if (node.isTerminal) return node;
List<int[]> moves = node.getLegalMoves();
Set<String> created = new HashSet<>();
for (TreeNode child : node.children) {
created.add(boardToKey(child.board));
}
for (int[] move : moves) {
int[][] newBoard = node.copyBoard(node.board);
newBoard[move[0]][move[1]] = node.player;
int nextPlayer = (node.player == PLAYER_X) ? PLAYER_O : PLAYER_X;
if (!created.contains(boardToKey(newBoard))) {
TreeNode child = new TreeNode(newBoard, nextPlayer, node);
node.children.add(child);
return child;
}
}
return node;
}
int simulate(TreeNode node) {
int[][] simBoard = node.copyBoard(node.board);
int currentPlayer = node.player;
TreeNode temp = new TreeNode(simBoard, currentPlayer, null);
while (true) {
int winner = temp.checkWinner(simBoard);
if (winner != 0) return winner;
if (temp.isBoardFull(simBoard)) return -1;
List<int[]> moves = new ArrayList<>();
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (simBoard[i][j] == EMPTY)
moves.add(new int[]{i, j});
int[] move = moves.get((int)(Math.random() * moves.size()));
simBoard[move[0]][move[1]] = currentPlayer;
currentPlayer = (currentPlayer == PLAYER_X) ? PLAYER_O : PLAYER_X;
}
}
void backpropagate(TreeNode node, int result, int rootPlayer) {
TreeNode current = node;
while (current != null) {
current.visits++;
if (result == -1) {
current.wins += 0.5;
} else if (result == rootPlayer) {
current.wins += 1.0;
}
current = current.parent;
}
}
String boardToKey(int[][] board) {
StringBuilder sb = new StringBuilder();
for (int[] row : board)
for (int cell : row)
sb.append(cell);
return sb.toString();
}
int[] findMove(int[][] before, int[][] after) {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (before[i][j] != after[i][j])
return new int[]{i, j};
return null;
}
void printBoard(int[][] board) {
for (int[] row : board) {
for (int cell : row) {
char c = (cell == EMPTY) ? '.' : (cell == PLAYER_X ? 'X' : 'O');
System.out.print(c + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
MCTSTicTacToe mcts = new MCTSTicTacToe();
int[][] board = new int[3][3];
int currentPlayer = PLAYER_X;
System.out.println("MCTS井字棋对战演示:");
mcts.printBoard(board);
for (int turn = 0; turn < 9; turn++) {
int[] move = mcts.findBestMove(board, currentPlayer);
System.out.println((currentPlayer == PLAYER_X ? "X" : "O") + " 选择: (" + move[0] + "," + move[1] + ")");
board[move[0]][move[1]] = currentPlayer;
mcts.printBoard(board);
TreeNode temp = new TreeNode(board, currentPlayer, null);
int winner = temp.checkWinner(board);
if (winner != 0) {
System.out.println((winner == PLAYER_X ? "X" : "O") + " 获胜!");
return;
}
currentPlayer = (currentPlayer == PLAYER_X) ? PLAYER_O : PLAYER_X;
}
System.out.println("平局!");
}
}
算法复杂度分析
- 时间复杂度：每次模拟需要O(d)时间，其中d为博弈深度。总时间复杂度为O(N * d)，N为模拟次数。
- 空间复杂度：O(N * d)用于存储树节点，每个节点存储棋盘状态和统计信息。
应用场景
MCTS广泛应用于围棋AI（如AlphaGo早期版本）、即时策略游戏、卡牌游戏以及任何具有大状态空间的序贯决策问题。其优势在于无需领域知识即可实现强大的AI决策能力。
