一、问题背景
五子棋（Gomoku）是一种双人对弈的纯策略型棋类游戏，双方轮流在15×15的棋盘交叉点上落子，先形成五子连珠者获胜。本文用Java实现一个五子棋AI，核心算法为深度卷积神经网络（CNN）提取棋盘空间特征，结合策略网络输出每个空位的落子概率分布，实现端到端的棋力评估与决策。
二、算法核心思想
2.1 棋盘状态表示
将15×15棋盘编码为两个二进制通道：
– 黑子通道：当前玩家执子位置为1，其余为0
– 白子通道：对手执子位置为1，其余为0
这种双通道表示保留了空间结构信息，适合卷积神经网络处理。
2.2 卷积神经网络结构
采用轻量级CNN提取局部棋形特征：
输入(2×15×15) → Conv(16, 3×3, ReLU) → Conv(32, 3×3, ReLU) → Flatten → FC(256, ReLU) → FC(225, Softmax)
最终输出225个概率值，对应15×15每个交叉点的落子概率。
2.3 策略梯度训练
通过自我对弈生成训练数据，以胜负结果为奖励信号。采用REINFORCE策略梯度更新网络：
$$\nabla_\theta J(\theta) = \mathbb{E}\pi \left[ G_t \cdot \nabla\theta \log \pi_\theta(a_t | s_t) \right]$$
其中 $G_t$ 为从时刻 $t$ 开始的累积折扣奖励，$\pi_\theta$ 为策略网络。
三、完整Java实现
import java.util.*;
/**
* 五子棋AI - 深度卷积神经网络与策略网络
*/
public class GomokuCNN {
static final int BOARD_SIZE = 15;
static final int WIN = 5;
// ==================== 卷积层 ====================
static class ConvLayer {
int inChannels, outChannels, kernelSize;
double[][][][] weights; // [out][in][k][k]
double[] bias;
Random rand;
public ConvLayer(int inC, int outC, int k, long seed) {
this.inChannels = inC; this.outChannels = outC; this.kernelSize = k;
weights = new double[outC][inC][k][k];
bias = new double[outC];
rand = new Random(seed);
double scale = Math.sqrt(2.0 / (inC * k * k));
for (int oc = 0; oc < outC; oc++)
for (int ic = 0; ic < inC; ic++)
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
weights[oc][ic][i][j] = rand.nextGaussian() * scale;
}
double[][][] forward(double[][][] input) {
int H = input[0].length, W = input[0][0].length;
int pad = kernelSize / 2;
double[][][] out = new double[outChannels][H][W];
for (int oc = 0; oc < outChannels; oc++) {
for (int h = 0; h < H; h++) {
for (int w = 0; w < W; w++) {
double sum = bias[oc];
for (int ic = 0; ic < inChannels; ic++) {
for (int kh = 0; kh < kernelSize; kh++) {
for (int kw = 0; kw < kernelSize; kw++) {
int ih = h + kh - pad, iw = w + kw - pad;
if (ih >= 0 && ih < H && iw >= 0 && iw < W)
sum += input[ic][ih][iw] * weights[oc][ic][kh][kw];
}
}
}
out[oc][h][w] = Math.max(0, sum); // ReLU
}
}
}
return out;
}
}
// ==================== 全连接层 ====================
static class FCLayer {
int inputSize, outputSize;
double[][] weights;
double[] bias;
double lr;
public FCLayer(int inSize, int outSize, double lr, long seed) {
this.inputSize = inSize; this.outputSize = outSize; this.lr = lr;
weights = new double[inSize][outSize];
bias = new double[outSize];
Random rand = new Random(seed);
double scale = Math.sqrt(2.0 / inSize);
for (int i = 0; i < inSize; i++)
for (int j = 0; j < outSize; j++)
weights[i][j] = rand.nextGaussian() * scale;
}
double[] forward(double[] input) {
double[] out = new double[outputSize];
for (int j = 0; j < outputSize; j++) {
double sum = bias[j];
for (int i = 0; i < inputSize; i++) sum += input[i] * weights[i][j];
out[j] = sum;
}
return out;
}
}
// ==================== 策略网络 ====================
static class PolicyNetwork {
ConvLayer conv1, conv2;
FCLayer fc1, fc2;
public PolicyNetwork() {
conv1 = new ConvLayer(2, 16, 3, 1);
conv2 = new ConvLayer(16, 32, 3, 2);
fc1 = new FCLayer(32 * BOARD_SIZE * BOARD_SIZE, 256, 0.001, 3);
fc2 = new FCLayer(256, BOARD_SIZE * BOARD_SIZE, 0.001, 4);
}
/** 前向传播，返回logits */
double[] forward(double[][][] boardState) {
double[][][] h1 = conv1.forward(boardState);
double[][][] h2 = conv2.forward(h1);
double[] flat = flatten(h2);
double[] h3 = fc1.forward(flat);
for (int i = 0; i < h3.length; i++) h3[i] = Math.max(0, h3[i]); // ReLU
return fc2.forward(h3);
}
double[] flatten(double[][][] arr) {
int c = arr.length, h = arr[0].length, w = arr[0][0].length;
double[] out = new double[c * h * w];
int idx = 0;
for (int i = 0; i < c; i++)
for (int j = 0; j < h; j++)
for (int k = 0; k < w; k++)
out[idx++] = arr[i][j][k];
return out;
}
/** Softmax + 合法位置掩码 */
double[] predict(double[][][] state, boolean[][] validMask) {
double[] logits = forward(state);
// 掩码非法位置
for (int i = 0; i < logits.length; i++)
if (!validMask[i / BOARD_SIZE][i % BOARD_SIZE]) logits[i] = Double.NEGATIVE_INFINITY;
return softmax(logits);
}
}
static double[] softmax(double[] x) {
double max = x[0];
for (double v : x) if (v > max) max = v;
double sum = 0;
double[] out = new double[x.length];
for (int i = 0; i < x.length; i++) {
out[i] = Math.exp(x[i] - max);
sum += out[i];
}
for (int i = 0; i < x.length; i++) out[i] /= sum;
return out;
}
// ==================== 五子棋环境 ====================
static class GomokuEnv {
int[][] board = new int[BOARD_SIZE][BOARD_SIZE]; // 0=空, 1=黑, 2=白
int currentPlayer = 1; // 黑先
boolean gameOver = false;
int winner = 0;
List<int[]> history = new ArrayList<>();
void reset() {
for (int[] row : board) Arrays.fill(row, 0);
currentPlayer = 1;
gameOver = false;
winner = 0;
history.clear();
}
/** 执行落子，返回是否成功 */
boolean step(int row, int col) {
if (gameOver || row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != 0)
return false;
board[row][col] = currentPlayer;
history.add(new int[]{row, col, currentPlayer});
if (checkWin(row, col)) {
gameOver = true;
winner = currentPlayer;
} else if (history.size() == BOARD_SIZE * BOARD_SIZE) {
gameOver = true;
winner = 0; // 和棋
}
currentPlayer = (currentPlayer == 1) ? 2 : 1;
return true;
}
boolean checkWin(int r, int c) {
int player = board[r][c];
int[][] dirs = {{0,1},{1,0},{1,1},{1,-1}};
for (int[] d : dirs) {
int count = 1;
for (int sign = -1; sign <= 1; sign += 2) {
for (int k = 1; k < WIN; k++) {
int nr = r + sign * k * d[0], nc = c + sign * k * d[1];
if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE || board[nr][nc] != player) break;
count++;
}
}
if (count >= WIN) return true;
}
return false;
}
/** 获取当前玩家的状态表示 [2][15][15] */
double[][][] getState() {
double[][][] state = new double[2][BOARD_SIZE][BOARD_SIZE];
int myColor = (currentPlayer == 1) ? 1 : 2;
int oppColor = (currentPlayer == 1) ? 2 : 1;
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (board[r][c] == myColor) state[0][r][c] = 1;
else if (board[r][c] == oppColor) state[1][r][c] = 1;
}
}
return state;
}
boolean[][] getValidMask() {
boolean[][] mask = new boolean[BOARD_SIZE][BOARD_SIZE];
for (int r = 0; r < BOARD_SIZE; r++)
for (int c = 0; c < BOARD_SIZE; c++)
mask[r][c] = (board[r][c] == 0);
return mask;
}
}
// ==================== 策略梯度训练（简化版） ====================
static class Trainer {
PolicyNetwork net;
Random rand = new Random();
public Trainer(PolicyNetwork net) { this.net = net; }
/** 自我对弈一局，返回对局记录 */
List<GameRecord> selfPlay() {
GomokuEnv env = new GomokuEnv();
List<GameRecord> records = new ArrayList<>();
while (!env.gameOver) {
double[][][] state = env.getState();
boolean[][] mask = env.getValidMask();
double[] probs = net.predict(state, mask);
int action = sampleAction(probs);
int row = action / BOARD_SIZE, col = action % BOARD_SIZE;
records.add(new GameRecord(state, action, env.currentPlayer));
env.step(row, col);
}
// 分配奖励：胜者+1，败者-1，和棋0
for (GameRecord gr : records) {
if (env.winner == 0) gr.reward = 0;
else gr.reward = (gr.player == env.winner) ? 1 : -1;
}
return records;
}
int sampleAction(double[] probs) {
double p = rand.nextDouble();
double cum = 0;
for (int i = 0; i < probs.length; i++) {
cum += probs[i];
if (p <= cum) return i;
}
return probs.length - 1;
}
}
static class GameRecord {
double[][][] state;
int action, player;
double reward;
GameRecord(double[][][] s, int a, int p) { state = s; action = a; player = p; }
}
// ==================== 主程序 ====================
public static void main(String[] args) {
PolicyNetwork net = new PolicyNetwork();
Trainer trainer = new Trainer(net);
GomokuEnv env = new GomokuEnv();
// 演示：随机初始化网络 vs 简单启发式玩家
System.out.println("五子棋AI演示局（CNN策略网络 vs 贪心启发式）");
System.out.println("========================================");
env.reset();
int step = 0;
while (!env.gameOver && step < 225) {
if (env.currentPlayer == 1) {
// AI落子
double[] probs = net.predict(env.getState(), env.getValidMask());
int action = argMax(probs);
int r = action / BOARD_SIZE, c = action % BOARD_SIZE;
env.step(r, c);
System.out.printf("AI落子: (%d, %d)%n", r, c);
} else {
// 贪心启发式：寻找最佳进攻/防守位置
int[] move = greedyMove(env);
env.step(move[0], move[1]);
System.out.printf("贪心落子: (%d, %d)%n", move[0], move[1]);
}
printBoard(env.board);
step++;
}
if (env.winner != 0) System.out.println("胜者: " + (env.winner == 1 ? "AI" : "贪心启发式"));
else System.out.println("和棋");
}
/** 简单贪心启发式：优先连成五子，其次阻止对手 */
static int[] greedyMove(GomokuEnv env) {
int bestR = -1, bestC = -1, bestScore = -1;
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (env.board[r][c] != 0) continue;
int score = evaluate(env.board, r, c, env.currentPlayer);
// 也考虑对手威胁
int opp = (env.currentPlayer == 1) ? 2 : 1;
score = Math.max(score, evaluate(env.board, r, c, opp));
if (score > bestScore) {
bestScore = score;
bestR = r; bestC = c;
}
}
}
return new int[]{bestR, bestC};
}
/** 评估落子价值：连子长度越长分数越高 */
static int evaluate(int[][] board, int r, int c, int player) {
int[][] dirs = {{0,1},{1,0},{1,1},{1,-1}};
int maxScore = 0;
for (int[] d : dirs) {
int count = 1;
boolean open1 = false, open2 = false;
for (int sign = -1; sign <= 1; sign += 2) {
int blocked = 0;
for (int k = 1; k <= 5; k++) {
int nr = r + sign * k * d[0], nc = c + sign * k * d[1];
if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE) { blocked = 1; break; }
if (board[nr][nc] == player) count++;
else if (board[nr][nc] == 0) { open1 = true; break; }
else { blocked = 1; break; }
}
if (sign == -1 && count > 1) open2 = open1;
}
int score = count;
if (count >= 5) score = 100000;
else if (count == 4) score = (open1 || open2) ? 10000 : 1000;
else if (count == 3) score = (open1 && open2) ? 1000 : 100;
else if (count == 2) score = (open1 && open2) ? 100 : 10;
maxScore = Math.max(maxScore, score);
}
return maxScore;
}
static int argMax(double[] arr) {
int idx = 0;
for (int i = 1; i < arr.length; i++) if (arr[i] > arr[idx]) idx = i;
return idx;
}
static void printBoard(int[][] board) {
System.out.print(" ");
for (int c = 0; c < BOARD_SIZE; c++) System.out.print(c % 10);
System.out.println();
for (int r = 0; r < BOARD_SIZE; r++) {
System.out.print(r % 10 + " ");
for (int c = 0; c < BOARD_SIZE; c++) {
if (board[r][c] == 0) System.out.print(".");
else if (board[r][c] == 1) System.out.print("X");
else System.out.print("O");
}
System.out.println();
}
System.out.println();
}
}
四、训练优化建议
上述代码展示了网络结构与推理流程。实际训练需注意：
- 数据增强：对棋盘进行旋转和翻转，扩充训练样本8倍
- 温度参数：在Softmax前除以温度 $T$，控制探索程度。$T>1$ 时更均匀，$T<1$ 时更贪婪
- 价值网络辅助：除策略网络外，增加价值网络 $V(s)$ 评估当前胜率，指导MCTS搜索
- 残差连接：在卷积层间添加跳跃连接，缓解梯度消失，提升深层网络训练效果
五、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 卷积前向(Conv1) | $O(C_{out} \cdot C_{in} \cdot K^2 \cdot H \cdot W)$ | $O(C_{out} \cdot H \cdot W)$ |
| 卷积前向(Conv2) | $O(32 \cdot 16 \cdot 9 \cdot 225)$ | $O(32 \cdot 225)$ |
| 全连接 | $O(D_{in} \cdot D_{out})$ | $O(D_{out})$ |
| 贪心评估 | $O(N^2 \cdot D \cdot L)$ | $O(1)$ |
其中 $N=15$ 为棋盘大小，$K=3$ 为卷积核，$D=4$ 为方向数，$L=5$ 为连子长度。
六、总结
本文实现了基于CNN策略网络的五子棋AI：
– 双通道状态编码：分别表示己方与对方的棋子分布，保留空间结构
– 轻量CNN：两层卷积提取局部棋形特征，全连接层输出落子概率
– 策略梯度：通过自我对弈生成数据，以胜负结果驱动网络优化
– 贪心基线：提供可对比的启发式对手，验证网络学习效果
读者可在此基础上扩展残差网络、AlphaZero风格的MCTS+神经网络结合等高级架构。
