井字棋（Tic-Tac-Toe）是最简单的完全信息博弈游戏之一，但作为理解蒙特卡洛树搜索（MCTS）算法的入门案例非常合适。本文将使用Java实现基于MCTS和UCT（Upper Confidence Bound for Trees）算法的井字棋AI。
蒙特卡洛树搜索原理
MCTS是一种用于决策过程的启发式搜索算法，通过随机模拟（蒙特卡洛方法）来评估棋局。核心流程包含四个阶段：
- 选择（Selection）：从根节点开始，使用UCT公式选择最有潜力的子节点，直到到达未完全展开的节点
- 扩展（Expansion）：为选中的节点添加一个或多个子节点
- 模拟（Simulation）：从新扩展的节点开始，进行随机对弈直到终局
- 回传（Backpropagation）：将模拟结果沿路径回传，更新节点统计信息
UCT公式
UCT平衡了 exploitation（利用已有知识）和 exploration（探索未知）：
$$UCT = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}}$$
其中wi是胜利次数，ni是访问次数，N是父节点访问次数，c是探索常数。
Java实现
import java.util.*;
/**
* 井字棋MCTS AI
* 使用蒙特卡洛树搜索与UCT算法实现井字棋智能对弈
*/
public class TicTacToeMCTS {
// 棋盘状态：0=空, 1=玩家X, -1=玩家O
private static final int EMPTY = 0;
private static final int PLAYER_X = 1;
private static final int PLAYER_O = -1;
private static final int SIZE = 3;
// MCTS参数
private static final int ITERATIONS = 10000; // 每次决策的模拟次数
private static final double EXPLORATION = Math.sqrt(2); // UCT探索常数
/**
* 棋盘状态类
*/
static class Board {
int[][] grid;
int currentPlayer;
Board() {
this.grid = new int[SIZE][SIZE];
this.currentPlayer = PLAYER_X;
}
Board(Board other) {
this.grid = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
this.grid[i] = other.grid[i].clone();
}
this.currentPlayer = other.currentPlayer;
}
/**
* 获取所有合法移动
*/
List<int[]> getLegalMoves() {
List<int[]> moves = new ArrayList<>();
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (grid[r][c] == EMPTY) {
moves.add(new int[]{r, c});
}
}
}
return moves;
}
/**
* 执行移动
*/
void makeMove(int r, int c) {
grid[r][c] = currentPlayer;
currentPlayer = -currentPlayer;
}
/**
* 撤销移动
*/
void undoMove(int r, int c) {
grid[r][c] = EMPTY;
currentPlayer = -currentPlayer;
}
/**
* 检查游戏是否结束
* @return 1=X胜, -1=O胜, 0=平局, null=未结束
*/
Integer checkWinner() {
// 检查行和列
for (int i = 0; i < SIZE; i++) {
if (grid[i][0] != EMPTY && grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2]) {
return grid[i][0];
}
if (grid[0][i] != EMPTY && grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i]) {
return grid[0][i];
}
}
// 检查对角线
if (grid[0][0] != EMPTY && grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2]) {
return grid[0][0];
}
if (grid[0][2] != EMPTY && grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0]) {
return grid[0][2];
}
// 检查平局
if (getLegalMoves().isEmpty()) {
return 0;
}
return null;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Board)) return false;
Board b = (Board) o;
return Arrays.deepEquals(grid, b.grid) && currentPlayer == b.currentPlayer;
}
@Override
public int hashCode() {
return Arrays.deepHashCode(grid) * 31 + currentPlayer;
}
}
/**
* MCTS树节点
*/
static class TreeNode {
Board state;
TreeNode parent;
Map<String, TreeNode> children;
int visits;
double wins; // 从父节点视角的胜利次数
int[] move; // 到达此节点的移动
TreeNode(Board state, TreeNode parent, int[] move) {
this.state = state;
this.parent = parent;
this.children = new HashMap<>();
this.visits = 0;
this.wins = 0;
this.move = move;
}
/**
* 检查是否完全展开（所有合法移动都有对应子节点）
*/
boolean isFullyExpanded() {
return children.size() == state.getLegalMoves().size();
}
/**
* 使用UCT公式选择最佳子节点
*/
TreeNode bestChild() {
TreeNode best = null;
double bestValue = Double.NEGATIVE_INFINITY;
for (TreeNode child : children.values()) {
if (child.visits == 0) {
return child; // 优先探索未访问节点
}
// UCT公式： exploitation + exploration
double exploitation = child.wins / child.visits;
double exploration = EXPLORATION * Math.sqrt(Math.log(this.visits) / child.visits);
double uctValue = exploitation + exploration;
if (uctValue > bestValue) {
bestValue = uctValue;
best = child;
}
}
return best;
}
/**
* 选择最有希望获胜的移动（最高胜率）
*/
TreeNode bestMove() {
TreeNode best = null;
double bestRate = -1;
for (TreeNode child : children.values()) {
double winRate = child.visits > 0 ? child.wins / child.visits : 0;
if (winRate > bestRate) {
bestRate = winRate;
best = child;
}
}
return best;
}
}
private Random random;
public TicTacToeMCTS() {
this.random = new Random();
}
/**
* MCTS搜索主流程
*/
public int[] findBestMove(Board board) {
TreeNode root = new TreeNode(new Board(board), null, null);
for (int i = 0; i < ITERATIONS; i++) {
// 1. 选择
TreeNode node = select(root);
// 2. 扩展
if (node.state.checkWinner() == null) {
node = expand(node);
}
// 3. 模拟
double result = simulate(node);
// 4. 回传
backpropagate(node, result);
}
TreeNode best = root.bestMove();
return best != null ? best.move : null;
}
/**
* 选择阶段：使用UCT递归选择最有潜力的节点
*/
TreeNode select(TreeNode node) {
while (!node.children.isEmpty() && node.isFullyExpanded()) {
node = node.bestChild();
}
return node;
}
/**
* 扩展阶段：为节点添加一个未扩展的子节点
*/
TreeNode expand(TreeNode node) {
List<int[]> legalMoves = node.state.getLegalMoves();
// 找到未扩展的移动
for (int[] move : legalMoves) {
String moveKey = move[0] + "," + move[1];
if (!node.children.containsKey(moveKey)) {
Board newState = new Board(node.state);
newState.makeMove(move[0], move[1]);
TreeNode child = new TreeNode(newState, node, move);
node.children.put(moveKey, child);
return child;
}
}
return node;
}
/**
* 模拟阶段：随机对弈直到终局
* @return 从父节点视角的结果：1=胜, 0.5=平, 0=负
*/
double simulate(TreeNode node) {
Board simState = new Board(node.state);
Integer winner;
while ((winner = simState.checkWinner()) == null) {
List<int[]> moves = simState.getLegalMoves();
int[] move = moves.get(random.nextInt(moves.size()));
simState.makeMove(move[0], move[1]);
}
// 从当前节点视角评估结果
// 当前节点 state's currentPlayer 是下一步要走的玩家
// 模拟开始时，simState.currentPlayer 已经是对手了（因为node.state执行了到达此节点的移动）
// 实际上 winner 是最后一步玩家的胜利
// 我们需要从 node.parent 的视角来评估（即执行了到达node这步移动的玩家）
int myPlayer = node.parent != null ? -node.state.currentPlayer : PLAYER_X;
if (winner == myPlayer) {
return 1.0;
} else if (winner == 0) {
return 0.5;
} else {
return 0.0;
}
}
/**
* 回传阶段：将模拟结果沿路径更新
*/
void backpropagate(TreeNode node, double result) {
while (node != null) {
node.visits++;
// 从父节点视角更新胜利次数
// 如果当前节点轮到对手走，那么父节点执行的上一步对自己有利时result应该增加
if (node.parent != null) {
// 父节点的移动导致了当前局面
// 如果result是从当前节点视角的，需要转换为父节点视角
node.wins += result;
}
// 切换视角：1 - result
result = 1 - result;
node = node.parent;
}
}
/**
* 打印棋盘
*/
void printBoard(Board board) {
char[] symbols = {'O', ' ', 'X'};
System.out.println(" 0 1 2");
for (int r = 0; r < SIZE; r++) {
System.out.print(r + " ");
for (int c = 0; c < SIZE; c++) {
System.out.print(symbols[board.grid[r][c] + 1]);
if (c < SIZE - 1) System.out.print("|");
}
System.out.println();
if (r < SIZE - 1) System.out.println(" -----");
}
System.out.println();
}
/**
* 人机对战演示
*/
public void playGame() {
Board board = new Board();
Scanner scanner = new Scanner(System.in);
System.out.println("井字棋MCTS对战！你是X，AI是O");
System.out.println("输入行和列（如：1 2）进行移动\n");
while (board.checkWinner() == null) {
printBoard(board);
if (board.currentPlayer == PLAYER_X) {
// 人类玩家
System.out.print("你的回合（行 列）：");
int r = scanner.nextInt();
int c = scanner.nextInt();
if (r < 0 || r >= SIZE || c < 0 || c >= SIZE || board.grid[r][c] != EMPTY) {
System.out.println("非法移动！");
continue;
}
board.makeMove(r, c);
} else {
// AI回合
System.out.println("AI思考中...");
long start = System.currentTimeMillis();
int[] move = findBestMove(board);
long end = System.currentTimeMillis();
if (move != null) {
board.makeMove(move[0], move[1]);
System.out.println("AI落子：(" + move[0] + ", " + move[1] + ")，耗时" + (end - start) + "ms");
}
}
}
printBoard(board);
Integer winner = board.checkWinner();
if (winner == PLAYER_X) {
System.out.println("你赢了！");
} else if (winner == PLAYER_O) {
System.out.println("AI赢了！");
} else {
System.out.println("平局！");
}
}
/**
* AI自对弈测试
*/
public void selfPlay(int games) {
int xWins = 0, oWins = 0, draws = 0;
for (int g = 0; g < games; g++) {
Board board = new Board();
while (board.checkWinner() == null) {
int[] move = findBestMove(board);
if (move != null) {
board.makeMove(move[0], move[1]);
}
}
Integer winner = board.checkWinner();
if (winner == PLAYER_X) xWins++;
else if (winner == PLAYER_O) oWins++;
else draws++;
}
System.out.println("AI自对弈" + games + "局结果：");
System.out.println("X胜：" + xWins + "，O胜：" + oWins + "，平局：" + draws);
System.out.println("先手优势：" + (xWins - oWins) + "局");
}
public static void main(String[] args) {
TicTacToeMCTS mcts = new TicTacToeMCTS();
// AI自对弈测试
mcts.selfPlay(100);
System.out.println("\n开始人机对战：");
mcts.playGame();
}
}
MCTS的优势与局限
优势
- 无需领域知识：MCTS不需要人工设计评估函数，完全通过随机模拟来学习
- 随时可用：可以在任意时刻停止搜索，返回当前最优结果
- 渐进收敛：随着迭代次数增加，结果逐渐收敛到最优
- 非对称搜索：自动将更多计算资源投入到更有前景的分支
局限
- 模拟质量依赖：随机模拟的质量直接影响搜索结果
- 计算开销大：需要大量模拟才能获得可靠结果
- 井字棋特殊性：井字棋已被完全破解（最优策略必平局），MCTS在此更多是教学意义
UCT公式的平衡艺术
UCT公式中的探索常数c至关重要：
– c过大：过度探索，忽略已有知识，搜索效率低
– c过小：过早收敛到局部最优，错过更好的策略
– c=√2：理论最优值（针对 rewards ∈ [0,1] 的情况）
在井字棋中，由于状态空间较小（约5,478种合法状态），MCTS能快速收敛到最优策略。
总结
本文使用蒙特卡洛树搜索（MCTS）和UCT算法实现了井字棋AI。MCTS通过选择、扩展、模拟、回传四个阶段的循环，逐步构建搜索树并收敛到最优策略。UCT公式巧妙地平衡了探索与利用，是MCTS算法的核心。虽然井字棋已被完全破解，但MCTS作为通用博弈算法，在五子棋、围棋等复杂游戏中展现了强大的实力。
