华容道是中国传统滑块拼图游戏，目标是在4×5的棋盘上通过滑动棋子，将最大的”曹操”块移动到出口位置。其状态空间虽然有限但极其复杂，传统搜索算法在面对深度较大的布局时效率受限。本文用Java实现一个结合神经网络估值函数与蒙特卡洛树搜索（MCTS）的华容道AI，通过神经网络学习状态评估，指导MCTS高效探索最优解路径。
一、神经网络+MCTS架构
AlphaZero的成功验证了”神经网络+MCTS”范式的强大威力。其核心流程为：
- 神经网络同时输出两个信息：当前状态每个合法动作的先验概率（策略头），以及当前状态的胜率期望（价值头）
- MCTS利用神经网络的输出进行有偏向的搜索，通过多次模拟迭代收敛到最优动作选择
- 自我对弈生成的数据用于训练神经网络，形成数据-模型-搜索的闭环提升
二、华容道状态表示
华容道棋盘为5行4列，棋子分为：1×2的竖块、2×1的横块、2×2的大块和1×1的小块。本文使用二维数组表示棋盘占据关系，每个位置记录占据该位置的棋子ID。
三、Java核心实现
import java.util.*;
/**
* 华容道：神经网络估值 + 蒙特卡洛树搜索AI
*/
public class KlotskiNeuralMCTS {
static final int ROWS = 5;
static final int COLS = 4;
static final int EMPTY = -1;
// MCTS参数
static final int SIMULATIONS = 800;
static final double C_PUCT = 1.5; // PUCT探索常数
static final double TEMPERATURE = 1.0;
// 神经网络
private NeuralNetwork network;
public KlotskiNeuralMCTS() {
// 输入：5x4的棋子类型编码 + 出口位置信息
this.network = new NeuralNetwork(ROWS * COLS + 2, new int[]{256, 128}, ROWS * COLS * 4, 1);
}
/**
* 棋子类
*/
static class Piece {
int id;
int type; // 0=1x1, 1=1x2横, 2=2x1竖, 3=2x2
int r, c; // 左上角位置
Piece(int id, int type, int r, int c) {
this.id = id; this.type = type; this.r = r; this.c = c;
}
int getHeight() {
return (type == 2 || type == 3) ? 2 : 1;
}
int getWidth() {
return (type == 1 || type == 3) ? 2 : 1;
}
boolean occupies(int row, int col) {
return row >= r && row < r + getHeight() && col >= c && col < c + getWidth();
}
}
/**
* 棋盘状态类
*/
static class Board {
List<Piece> pieces = new ArrayList<>();
int[][] grid = new int[ROWS][COLS];
int targetR = 3, targetC = 1; // 曹操出口位置（2x2块的左下角应在(3,1)）
Board() {
initClassicLayout();
}
/**
* 经典横刀立马布局
*/
void initClassicLayout() {
pieces.clear();
// 曹操 (2x2) id=0
pieces.add(new Piece(0, 3, 0, 1));
// 关羽 (1x2) id=1
pieces.add(new Piece(1, 1, 2, 1));
// 张飞 (2x1) id=2
pieces.add(new Piece(2, 2, 0, 0));
// 赵云 (2x1) id=3
pieces.add(new Piece(3, 2, 0, 3));
// 马超 (2x1) id=4
pieces.add(new Piece(4, 2, 2, 0));
// 黄忠 (2x1) id=5
pieces.add(new Piece(5, 2, 2, 3));
// 四个小兵 (1x1) id=6-9
pieces.add(new Piece(6, 0, 3, 0));
pieces.add(new Piece(7, 0, 3, 1));
pieces.add(new Piece(8, 0, 3, 2));
pieces.add(new Piece(9, 0, 3, 3));
updateGrid();
}
void updateGrid() {
for (int r = 0; r < ROWS; r++) {
Arrays.fill(grid[r], EMPTY);
}
for (Piece p : pieces) {
for (int dr = 0; dr < p.getHeight(); dr++) {
for (int dc = 0; dc < p.getWidth(); dc++) {
grid[p.r + dr][p.c + dc] = p.id;
}
}
}
}
/**
* 生成所有合法走法
* 走法表示为: (piece_id, direction) direction: 0=上,1=下,2=左,3=右
*/
List<int[]> getLegalMoves() {
List<int[]> moves = new ArrayList<>();
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (Piece p : pieces) {
for (int d = 0; d < 4; d++) {
int nr = p.r + dirs[d][0];
int nc = p.c + dirs[d][1];
// 检查新位置是否合法
if (nr < 0 || nr + p.getHeight() > ROWS) continue;
if (nc < 0 || nc + p.getWidth() > COLS) continue;
boolean valid = true;
for (int dr = 0; dr < p.getHeight() && valid; dr++) {
for (int dc = 0; dc < p.getWidth() && valid; dc++) {
int cellR = nr + dr, cellC = nc + dc;
int occupant = grid[cellR][cellC];
if (occupant != EMPTY && occupant != p.id) {
valid = false;
}
}
}
if (valid) {
moves.add(new int[]{p.id, d});
}
}
}
return moves;
}
/**
* 执行走法
*/
Board makeMove(int pieceId, int dir) {
Board next = new Board();
next.pieces = new ArrayList<>();
for (Piece p : this.pieces) {
next.pieces.add(new Piece(p.id, p.type, p.r, p.c));
}
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (Piece p : next.pieces) {
if (p.id == pieceId) {
p.r += dirs[dir][0];
p.c += dirs[dir][1];
break;
}
}
next.updateGrid();
return next;
}
/**
* 检查是否达成目标（曹操到达出口）
*/
boolean isSolved() {
Piece caocao = pieces.get(0);
return caocao.r == 3 && caocao.c == 1;
}
/**
* 状态哈希（用于MCTS树节点标识）
*/
long hash() {
long h = 0;
for (Piece p : pieces) {
h = h * 31 + p.id;
h = h * 7 + p.r;
h = h * 5 + p.c;
}
return h;
}
/**
* 转换为神经网络输入
*/
double[] toInput() {
double[] input = new double[ROWS * COLS + 2];
int idx = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int pid = grid[r][c];
if (pid == EMPTY) {
input[idx++] = 0;
} else {
Piece p = pieces.get(pid);
input[idx++] = (p.type + 1) / 4.0; // 归一化编码
}
}
}
input[idx++] = targetR / (double) ROWS;
input[idx++] = targetC / (double) COLS;
return input;
}
}
/**
* 简化的神经网络
*/
static class NeuralNetwork {
List<double[][]> weights;
List<double[]> biases;
int policySize;
Random rand = new Random(42);
NeuralNetwork(int inputSize, int[] hiddenSizes, int policySize, int valueSize) {
this.policySize = policySize;
weights = new ArrayList<>();
biases = new ArrayList<>();
int prev = inputSize;
for (int h : hiddenSizes) {
weights.add(initMatrix(prev, h));
biases.add(new double[h]);
prev = h;
}
// 策略头
weights.add(initMatrix(prev, policySize));
biases.add(new double[policySize]);
// 价值头
weights.add(initMatrix(prev, valueSize));
biases.add(new double[valueSize]);
}
double[][] initMatrix(int rows, int cols) {
double[][] m = new double[rows][cols];
double scale = Math.sqrt(2.0 / rows);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
m[i][j] = rand.nextGaussian() * scale;
}
}
return m;
}
/**
* 前向传播，返回策略logits和价值
*/
double[][] forward(double[] input) {
double[] current = input;
int layerIdx = 0;
// 共享隐藏层
for (; layerIdx < weights.size() - 2; layerIdx++) {
double[] next = new double[biases.get(layerIdx).length];
for (int j = 0; j < next.length; j++) {
double sum = biases.get(layerIdx)[j];
for (int k = 0; k < current.length; k++) {
sum += current[k] * weights.get(layerIdx)[k][j];
}
next[j] = Math.max(0, sum); // ReLU
}
current = next;
}
// 策略头
double[] policy = new double[policySize];
for (int j = 0; j < policySize; j++) {
double sum = biases.get(layerIdx)[j];
for (int k = 0; k < current.length; k++) {
sum += current[k] * weights.get(layerIdx)[k][j];
}
policy[j] = sum;
}
layerIdx++;
// 价值头
double[] value = new double[1];
value[0] = biases.get(layerIdx)[0];
for (int k = 0; k < current.length; k++) {
value[0] += current[k] * weights.get(layerIdx)[k][0];
}
value[0] = Math.tanh(value[0]); // tanh输出[-1,1]
return new double[][]{policy, value};
}
}
/**
* MCTS树节点
*/
static class MCTSNode {
Board state;
MCTSNode parent;
Map<String, MCTSNode> children = new HashMap<>();
List<int[]> untriedMoves;
int visitCount = 0;
double totalValue = 0;
double priorProb = 0; // 神经网络先验概率
MCTSNode(Board state, MCTSNode parent, double prior) {
this.state = state;
this.parent = parent;
this.priorProb = prior;
this.untriedMoves = state.getLegalMoves();
}
boolean isFullyExpanded() {
return untriedMoves.isEmpty();
}
/**
* PUCT选择
*/
MCTSNode selectChild() {
MCTSNode best = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (MCTSNode child : children.values()) {
double q = child.visitCount == 0 ? 0 : -child.totalValue / child.visitCount;
double u = C_PUCT * child.priorProb * Math.sqrt(this.visitCount) / (1 + child.visitCount);
double score = q + u;
if (score > bestScore) {
bestScore = score;
best = child;
}
}
return best;
}
/**
* 扩展一个子节点
*/
MCTSNode expand(int[] move, double prior) {
Board nextState = state.makeMove(move[0], move[1]);
String key = move[0] + "," + move[1];
MCTSNode child = new MCTSNode(nextState, this, prior);
children.put(key, child);
untriedMoves.removeIf(m -> m[0] == move[0] && m[1] == move[1]);
return child;
}
/**
* 更新节点统计
*/
void update(double value) {
this.visitCount++;
this.totalValue += value;
}
}
/**
* 执行MCTS搜索
*/
int[] mctsSearch(Board rootState) {
MCTSNode root = new MCTSNode(rootState, null, 1.0);
// 神经网络评估根节点，获取先验概率
double[] input = rootState.toInput();
double[][] netOut = network.forward(input);
double[] policyLogits = netOut[0];
// 初始化根节点的先验概率
List<int[]> legalMoves = rootState.getLegalMoves();
double[] maskedPolicy = new double[policyLogits.length];
Arrays.fill(maskedPolicy, -1e9);
for (int[] m : legalMoves) {
int idx = m[0] * 4 + m[1];
if (idx < policyLogits.length) {
maskedPolicy[idx] = policyLogits[idx];
}
}
// softmax
double max = Double.NEGATIVE_INFINITY;
for (double v : maskedPolicy) if (v > -1e8) max = Math.max(max, v);
double sum = 0;
for (int i = 0; i < maskedPolicy.length; i++) {
if (maskedPolicy[i] > -1e8) {
maskedPolicy[i] = Math.exp(maskedPolicy[i] - max);
sum += maskedPolicy[i];
}
}
for (int i = 0; i < maskedPolicy.length; i++) {
if (maskedPolicy[i] > -1e8) maskedPolicy[i] /= sum;
}
for (int sim = 0; sim < SIMULATIONS; sim++) {
MCTSNode node = root;
// Selection: 选择路径直到叶子节点
while (node.isFullyExpanded() && !node.children.isEmpty()) {
node = node.selectChild();
}
// Expansion: 如果未完全扩展，扩展一个新节点
if (!node.state.isSolved() && !node.untriedMoves.isEmpty()) {
int[] move = node.untriedMoves.remove(0);
int idx = move[0] * 4 + move[1];
double prior = (idx < maskedPolicy.length && maskedPolicy[idx] > 0)
? maskedPolicy[idx] : 0.01;
node = node.expand(move, prior);
}
// Evaluation: 神经网络评估
double value;
if (node.state.isSolved()) {
value = 1.0; // 胜利
} else if (node.state.getLegalMoves().isEmpty()) {
value = -1.0; // 无路可走=失败
} else {
double[][] eval = network.forward(node.state.toInput());
value = eval[1][0]; // 价值头输出
}
// Backup: 反向传播更新路径上的所有节点
while (node != null) {
node.update(value);
value = -value; // 切换视角（零和博弈）
node = node.parent;
}
}
// 选择访问次数最多的动作
int[] bestMove = null;
int maxVisits = -1;
for (Map.Entry<String, MCTSNode> entry : root.children.entrySet()) {
if (entry.getValue().visitCount > maxVisits) {
maxVisits = entry.getValue().visitCount;
String[] parts = entry.getKey().split(",");
bestMove = new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
}
}
return bestMove;
}
/**
* 使用MCTS求解华容道
*/
List<int[]> solve(Board initial) {
List<int[]> solution = new ArrayList<>();
Board current = initial;
Set<Long> visited = new HashSet<>();
int maxSteps = 200;
for (int step = 0; step < maxSteps; step++) {
if (current.isSolved()) {
System.out.println("Solved in " + step + " steps!");
return solution;
}
long h = current.hash();
if (visited.contains(h)) {
// 出现循环，尝试其他走法
System.out.println("Cycle detected at step " + step);
}
visited.add(h);
int[] move = mctsSearch(current);
if (move == null) {
System.out.println("No valid move found at step " + step);
break;
}
solution.add(move);
current = current.makeMove(move[0], move[1]);
}
return solution;
}
public static void main(String[] args) {
KlotskiNeuralMCTS solver = new KlotskiNeuralMCTS();
Board board = new Board();
System.out.println("Initial state:");
printBoard(board);
List<int[]> solution = solver.solve(board);
System.out.println("Solution length: " + solution.size());
// 验证解法
Board verify = new Board();
for (int[] m : solution) {
verify = verify.makeMove(m[0], m[1]);
}
System.out.println("Verified solved: " + verify.isSolved());
}
static void printBoard(Board b) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
System.out.printf("%2d ", b.grid[r][c]);
}
System.out.println();
}
System.out.println();
}
}
四、MCTS+神经网络的关键设计
PUCT选择公式结合了访问次数和先验概率：U(s,a) = c_puct * P(a|s) * sqrt(N(s)) / (1 + N(s,a))。其中P(a|s)来自神经网络的策略头，引导搜索优先探索网络认为更有前景的动作。
视角切换在备份阶段至关重要。华容道是确定性的单人谜题，但MCTS框架将其建模为”当前玩家”与”环境”的交替：每次移动后价值符号取反，确保从当前状态视角评估每个动作。
神经网络输入编码直接影响估值质量。除了棋子类型占据信息，加入目标出口位置的相对坐标、每个棋子到目标的曼哈顿距离等特征，可以帮助网络更快地学会状态评估。
五、复杂度分析
MCTS每次模拟的时间复杂度为O(d·b)，其中d为搜索深度，b为平均分支因子。华容道的分支因子在不同阶段约为2-8。800次模拟的搜索通常能在秒级完成。
神经网络前向传播为O(H·W·D_hidden)，其中H=5, W=4。整体求解时间取决于MCTS模拟次数和神经网络评估速度。
传统BFS求解华容道最优解需要遍历整个状态空间（约2×10^5个状态），而MCTS+神经网络通过启发式引导，通常能在远少于BFS的状态评估次数内找到满意解（不一定最优但接近最优）。
六、扩展方向
对于追求最优解的场景，可以将MCTS与IDA*结合：神经网络提供启发式估计h(s)，配合迭代加深搜索保证最优性。此外，通过大规模自我对弈数据训练更强大的估值网络，或使用图神经网络（GNN）更好地建模棋子间的空间关系，都是提升AI求解能力的有效方向。残差网络结构和注意力机制也可以帮助网络学习更复杂的块间交互模式。
