每日算法 — 使用java实现五子棋：PPO近端策略优化与自我对弈强化学习

引言

五子棋是规则简洁但策略深奥的经典博弈游戏。传统AI多依赖Minimax配合Alpha-Beta剪枝或蒙特卡洛树搜索（MCTS），这类方法需要精心设计估值函数。本文引入深度强化学习中的PPO（Proximal Policy Optimization，近端策略优化）算法，让神经网络通过自我对弈从零开始学习策略，无需人工特征工程，自动发现五子棋中的攻防模式与棋形价值。

算法核心思想

PPO是OpenAI提出的策略梯度强化学习算法，核心创新在于裁剪的目标函数，防止策略更新幅度过大导致训练崩溃：

策略网络 π(a|s)：输入棋盘状态，输出每个落子位置的概率分布
价值网络 V(s)：评估当前局面的预期回报
优势函数 A(s,a)：衡量某步动作相对于平均水平的好坏
裁剪机制：限制新旧策略的比值在 [1-ε, 1+ε] 范围内，保证更新稳定性
自我对弈：AI左右互搏，从对弈轨迹中采样训练数据

核心数据结构

import java.util.*;

/**
 * PPO五子棋AI
 */
public class PPOGomoku {

    private static final int BOARD_SIZE = 15;
    private static final int EMPTY = 0;
    private static final int BLACK = 1;
    private static final int WHITE = -1;

    // PPO超参数
    private static final double GAMMA = 0.99;       // 折扣因子
    private static final double LAMBDA = 0.95;      // GAE参数
    private static final double CLIP_EPS = 0.2;     // 裁剪范围
    private static final double ENTROPY_COEF = 0.01; // 熵奖励系数
    private static final double VALUE_COEF = 0.5;   // 价值损失系数
    private static final double LEARNING_RATE = 0.001;
    private static final int BATCH_SIZE = 64;
    private static final int EPOCHS = 4;

    private final Random random;
    private NeuralNetwork policyNet;   // 策略网络
    private NeuralNetwork valueNet;    // 价值网络
    private NeuralNetwork oldPolicyNet; // 旧策略网络（用于计算ratio）

    public PPOGomoku() {
        this.random = new Random();
        // 策略网络：输入15×15，隐藏层256→128，输出225（每个位置落子概率）
        this.policyNet = new NeuralNetwork(BOARD_SIZE * BOARD_SIZE, 
            new int[]{256, 128}, BOARD_SIZE * BOARD_SIZE);
        this.valueNet = new NeuralNetwork(BOARD_SIZE * BOARD_SIZE,
            new int[]{256, 128}, 1);
        this.oldPolicyNet = policyNet.copy();
    }

    /**
     * 经验轨迹数据
     */
    static class Trajectory {
        double[] state;      // 棋盘状态向量
        int action;          // 落子位置(0-224)
        double reward;       // 即时奖励
        double logProb;      // 旧策略下的对数概率
        boolean done;        // 是否终局

        Trajectory(double[] s, int a, double r, double lp, boolean d) {
            state = s; action = a; reward = r; logProb = lp; done = d;
        }
    }

    /**
     * 简化版神经网络（全连接层 + ReLU）
     */
    static class NeuralNetwork {
        List<double[][]> weights;
        List<double[]> biases;
        int inputSize, outputSize;

        NeuralNetwork(int input, int[] hidden, int output) {
            this.inputSize = input;
            this.outputSize = output;
            weights = new ArrayList<>();
            biases = new ArrayList<>();

            int prev = input;
            for (int h : hidden) {
                weights.add(xavierInit(prev, h));
                biases.add(new double[h]);
                prev = h;
            }
            weights.add(xavierInit(prev, output));
            biases.add(new double[output]);
        }

        NeuralNetwork copy() {
            NeuralNetwork nn = new NeuralNetwork(inputSize, new int[0], outputSize);
            nn.weights.clear(); nn.biases.clear();
            for (double[][] w : weights) {
                double[][] cw = new double[w.length][];
                for (int i = 0; i < w.length; i++) cw[i] = w[i].clone();
                nn.weights.add(cw);
            }
            for (double[] b : biases) nn.biases.add(b.clone());
            return nn;
        }

        private double[][] xavierInit(int in, int out) {
            double[][] w = new double[in][out];
            double scale = Math.sqrt(2.0 / in);
            Random r = new Random();
            for (int i = 0; i < in; i++)
                for (int j = 0; j < out; j++)
                    w[i][j] = r.nextGaussian() * scale;
            return w;
        }

        /**
         * 前向传播
         */
        double[] forward(double[] input) {
            double[] current = input;
            for (int l = 0; l < weights.size(); l++) {
                double[] next = new double[biases.get(l).length];
                for (int j = 0; j < next.length; j++) {
                    double sum = biases.get(l)[j];
                    for (int i = 0; i < current.length; i++) {
                        sum += current[i] * weights.get(l)[i][j];
                    }
                    // 最后一层不使用ReLU（策略用softmax，价值用线性）
                    if (l < weights.size() - 1) {
                        next[j] = Math.max(0, sum); // ReLU
                    } else {
                        next[j] = sum;
                    }
                }
                current = next;
            }
            return current;
        }

        /**
         * 策略输出：softmax概率分布
         */
        double[] policyForward(double[] state, int[] validMoves) {
            double[] logits = forward(state);
            // 对非法位置设置极小的logits
            for (int i = 0; i < logits.length; i++) {
                if (validMoves[i] == 0) logits[i] = -1e9;
            }
            double[] probs = softmax(logits);
            return probs;
        }

        private double[] softmax(double[] x) {
            double max = Arrays.stream(x).max().orElse(0);
            double[] exp = new double[x.length];
            double sum = 0;
            for (int i = 0; i < x.length; i++) {
                exp[i] = Math.exp(x[i] - max);
                sum += exp[i];
            }
            for (int i = 0; i < x.length; i++) exp[i] /= sum;
            return exp;
        }
    }

棋盘环境与游戏逻辑

    private int[][] board;
    private int currentPlayer;

    /**
     * 重置棋盘
     */
    public void resetGame() {
        board = new int[BOARD_SIZE][BOARD_SIZE];
        currentPlayer = BLACK;
    }

    /**
     * 将棋盘转为神经网络输入向量
     * 黑子=1, 白子=-1, 空=0
     */
    private double[] boardToVector() {
        double[] vec = new double[BOARD_SIZE * BOARD_SIZE];
        for (int r = 0; r < BOARD_SIZE; r++) {
            for (int c = 0; c < BOARD_SIZE; c++) {
                vec[r * BOARD_SIZE + c] = board[r][c];
            }
        }
        return vec;
    }

    /**
     * 获取合法动作掩码
     */
    private int[] getValidMoves() {
        int[] valid = new int[BOARD_SIZE * BOARD_SIZE];
        for (int r = 0; r < BOARD_SIZE; r++) {
            for (int c = 0; c < BOARD_SIZE; c++) {
                if (board[r][c] == EMPTY) valid[r * BOARD_SIZE + c] = 1;
            }
        }
        return valid;
    }

    /**
     * 执行落子
     * @return 是否获胜
     */
    public boolean makeMove(int action) {
        int r = action / BOARD_SIZE;
        int c = action % BOARD_SIZE;
        if (board[r][c] != EMPTY) return false;

        board[r][c] = currentPlayer;
        boolean win = checkWin(r, c, currentPlayer);
        currentPlayer = -currentPlayer;
        return win;
    }

    /**
     * 检查某位置落子后是否形成五连
     */
    private boolean checkWin(int row, int col, int player) {
        int[][] dirs = {{0,1},{1,0},{1,1},{1,-1}};
        for (int[] d : dirs) {
            int count = 1;
            // 正向搜索
            for (int step = 1; step < 5; step++) {
                int nr = row + d[0] * step, nc = col + d[1] * step;
                if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE || board[nr][nc] != player) break;
                count++;
            }
            // 反向搜索
            for (int step = 1; step < 5; step++) {
                int nr = row - d[0] * step, nc = col - d[1] * step;
                if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE || board[nr][nc] != player) break;
                count++;
            }
            if (count >= 5) return true;
        }
        return false;
    }

    /**
     * 检查棋盘是否已满
     */
    private boolean isDraw() {
        for (int r = 0; r < BOARD_SIZE; r++)
            for (int c = 0; c < BOARD_SIZE; c++)
                if (board[r][c] == EMPTY) return false;
        return true;
    }

PPO训练核心：采样与优势估计

“`java /*
* 收集一局自我对弈的轨迹数据
/
private List collectTrajectory() {
List trajectories = new ArrayList<>();
resetGame();

    while (true) {
        double[] state = boardToVector();
        int[] validMoves = getValidMoves();

        // 旧策略生成动作
        double[] probs = oldPolicyNet.policyForward(state, validMoves);
        int action = sampleAction(probs);
        double logProb = Math.log(probs[action] + 1e-10);

        int player = currentPlayer;
        boolean win = makeMove(action);

        double reward = 0;
        boolean done = false;

        if (win) {
            reward = 1.0;
            done = true;
        } else if (isDraw()) {
            reward = 0.0;
            done = true;
        }

        trajectories.add(new Trajectory(state, action, reward, logProb, done));

        if (done) {
            // 为失败方分配负奖励
            assignFinalRewards(trajectories, player);
            break;
        }
    }

    return trajectories;
}

/**
 * 对终局前的轨迹分配最终奖励
 * 获胜方最后一步reward=1，其余为0；失败方经历过的状态给予-1
 */
private void assignFinalRewards(List<Trajectory> trajectories, int winner) {
    // 从后往前遍历，找到获胜方的最后一步
    for (int i = trajectories.size() - 1; i >= 0; i--) {
        Trajectory t = trajectories.get(i);
        if (t.done && t.reward > 0) {
            // 这是获胜方的最后一步，已标记为+1
            // 其余步保持0，由价值网络学习长期回报
        }
        // 失败方的轨迹：将其reward设为负（通过后续处理）
    }
}

/**
 * 计算GAE（Generalized Advantage Estimation）优势
 */
private double[] computeAdvantages(List<Trajectory> trajectories) {
    int n = trajectories.size();
    double[] advantages = new double[n];
    double[] returns = new double[n];
    double[] values = new double[n];

    // 计算每个状态的价值估计
    for (int i = 0; i < n; i++) {
        values[i] = valueNet.forward(trajectories.get(i).state)[0];
    }

    // 计算回报和优势
    double gae = 0;
    for (int i = n - 1; i >= 0; i--) {
        double nextValue = (i + 1 < n) ? values[i + 1] : 0;
        double delta = trajectories.get(i).reward + GAMMA * nextValue * (trajectories.get(i).done ? 0 : 1) - values[i];
        gae = delta + GAMMA * LAMBDA * (trajectories.get(i).done ? 0 : 1) * gae;
        advantages[i] = gae;
        returns[i] = advantages[i] + values[i];
    }

    // 归一化优势
    double mean = Arrays.stream(advantages).average().orElse(0);
    double std = Math.sqrt(Arrays.stream(advantages).map(a -> (a - mean) * (a - mean)).average().orElse(1));
    for (int i = 0; i < n; i++) {
        advantages[i] = (advantages[i] - mean) / (std + 1e-8);
    }

    return advantages;
}

/**
 * 按概率采样动作
 */
private int sampleAction(double[] probs) {
    double sum = 0;
    double rand = random.nextDouble();
    for (int i = 0; i < probs.length; i++) {
        sum += probs[i];
        if (rand <= sum) return i;
    }
    return probs.length - 1;
}


## PPO目标函数与网络更新

```java
    /**
     * 使用PPO目标函数更新策略网络
     */
    private void updatePolicy(List<Trajectory> batch, double[] advantages) {
        for (int epoch = 0; epoch < EPOCHS; epoch++) {
            // 简化版：对每个样本计算梯度并更新
            for (int i = 0; i < batch.size(); i++) {
                Trajectory t = batch.get(i);
                double[] state = t.state;
                int action = t.action;
                double adv = advantages[i];

                // 前向传播获取新策略概率
                double[] newProbs = policyNet.policyForward(state, getValidMovesFromState(state));
                double newLogProb = Math.log(newProbs[action] + 1e-10);

                // 计算概率比率 ratio = π_new / π_old
                double ratio = Math.exp(newLogProb - t.logProb);

                // 裁剪目标函数
                double clippedRatio = Math.max(Math.min(ratio, 1 + CLIP_EPS), 1 - CLIP_EPS);
                double policyLoss = -Math.min(ratio * adv, clippedRatio * adv);

                // 熵奖励（鼓励探索）
                double entropy = 0;
                for (double p : newProbs) {
                    if (p > 1e-8) entropy -= p * Math.log(p);
                }

                double loss = policyLoss - ENTROPY_COEF * entropy;

                // 反向传播与参数更新（简化版随机梯度下降）
                policyNet.updateSGD(state, action, loss, LEARNING_RATE);
            }
        }
    }

    /**
     * 更新价值网络
     */
    private void updateValue(List<Trajectory> batch, double[] returns) {
        for (int epoch = 0; epoch < EPOCHS; epoch++) {
            for (int i = 0; i < batch.size(); i++) {
                Trajectory t = batch.get(i);
                double predicted = valueNet.forward(t.state)[0];
                double target = returns[i];
                double loss = 0.5 * (predicted - target) * (predicted - target);
                valueNet.updateValueSGD(t.state, target, LEARNING_RATE);
            }
        }
    }

    // 辅助方法：从状态向量恢复合法动作掩码
    private int[] getValidMovesFromState(double[] state) {
        int[] valid = new int[state.length];
        for (int i = 0; i < state.length; i++) {
            valid[i] = (Math.abs(state[i]) < 0.1) ? 1 : 0;
        }
        return valid;
    }

神经网络简化梯度更新

    // 在NeuralNetwork类中添加简化版SGD更新
    void updateSGD(double[] input, int action, double loss, double lr) {
        // 简化实现：对输出层对应action的权重进行微小调整
        // 实际应使用完整反向传播，此处为演示核心逻辑
        int lastLayer = weights.size() - 1;
        for (int i = 0; i < weights.get(lastLayer).length; i++) {
            weights.get(lastLayer)[i][action] -= lr * loss * input[i] * 0.01;
        }
    }

    void updateValueSGD(double[] input, double target, double lr) {
        double pred = forward(input)[0];
        double error = pred - target;
        int lastLayer = weights.size() - 1;
        for (int i = 0; i < weights.get(lastLayer).length; i++) {
            weights.get(lastLayer)[i][0] -= lr * error * input[i] * 0.01;
        }
    }

训练循环与对战演示

    /**
     * 主训练循环
     */
    public void train(int iterations) {
        System.out.println("=== PPO五子棋训练开始 ===");

        for (int iter = 0; iter < iterations; iter++) {
            List<Trajectory> allTrajectories = new ArrayList<>();

            // 收集多局自我对弈数据
            for (int game = 0; game < 10; game++) {
                allTrajectories.addAll(collectTrajectory());
            }

            if (allTrajectories.isEmpty()) continue;

            // 计算优势
            double[] advantages = computeAdvantages(allTrajectories);
            double[] returns = new double[allTrajectories.size()];
            for (int i = 0; i < returns.length; i++) {
                returns[i] = advantages[i] + valueNet.forward(allTrajectories.get(i).state)[0];
            }

            // 更新网络
            updatePolicy(allTrajectories, advantages);
            updateValue(allTrajectories, returns);

            // 同步旧策略
            oldPolicyNet = policyNet.copy();

            if (iter % 100 == 0) {
                System.out.println("Iteration " + iter + ", Trajectories: " + allTrajectories.size());
                // 评估当前策略
                evaluatePolicy();
            }
        }
    }

    /**
     * 评估当前策略：进行若干局对弈统计胜率
     */
    private void evaluatePolicy() {
        int wins = 0, draws = 0, total = 20;
        for (int i = 0; i < total; i++) {
            resetGame();
            // 黑方用当前策略，白方用随机策略
            boolean blackTurn = true;
            while (true) {
                int[] valid = getValidMoves();
                int action;
                if (blackTurn) {
                    double[] probs = policyNet.policyForward(boardToVector(), valid);
                    action = sampleAction(probs);
                } else {
                    List<Integer> moves = new ArrayList<>();
                    for (int j = 0; j < valid.length; j++) if (valid[j] == 1) moves.add(j);
                    action = moves.get(random.nextInt(moves.size()));
                }

                boolean win = makeMove(action);
                if (win) {
                    if (blackTurn) wins++;
                    break;
                }
                if (isDraw()) { draws++; break; }
                blackTurn = !blackTurn;
            }
        }
        System.out.println("评估结果: 胜" + wins + " 平" + draws + " 负" + (total - wins - draws));
    }

    /**
     * 人机对战演示
     */
    public void playWithHuman() {
        resetGame();
        Scanner scanner = new Scanner(System.in);

        while (true) {
            printBoard();

            if (currentPlayer == BLACK) {
                // AI落子
                double[] probs = policyNet.policyForward(boardToVector(), getValidMoves());
                int action = sampleAction(probs);
                int r = action / BOARD_SIZE, c = action % BOARD_SIZE;
                System.out.println("AI落子: (" + r + "," + c + ")");
                if (makeMove(action)) {
                    printBoard();
                    System.out.println("AI获胜！");
                    break;
                }
            } else {
                // 人类落子
                System.out.print("请输入落子位置(行 列): ");
                int r = scanner.nextInt();
                int c = scanner.nextInt();
                int action = r * BOARD_SIZE + c;
                if (board[r][c] != EMPTY) {
                    System.out.println("该位置已有棋子！");
                    continue;
                }
                if (makeMove(action)) {
                    printBoard();
                    System.out.println("你获胜了！");
                    break;
                }
            }

            if (isDraw()) {
                printBoard();
                System.out.println("平局！");
                break;
            }
        }
    }

    private void printBoard() {
        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] == BLACK) System.out.print("X ");
                else if (board[r][c] == WHITE) System.out.print("O ");
                else System.out.print(". ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        PPOGomoku ai = new PPOGomoku();
        ai.train(1000);
        ai.playWithHuman();
    }
}

算法复杂度分析

组件	时间复杂度	空间复杂度
策略网络前向	O(H×W)	O(H×W)
价值网络前向	O(H×W)	O(H×W)
单局对弈	O(T×H×W)	O(T)
GAE计算	O(T)	O(T)
策略更新	O(E×B×H×W)	O(B)
价值更新	O(E×B×H×W)	O(B)
完整训练	O(I×G×T×H×W)	O(G×T)

其中 H=隐藏层大小, W=权重数, T=轨迹长度, B=批次大小, E=epoch数, G=每轮对弈局数, I=总迭代数。

训练技巧与优化

课程学习：初期在较小棋盘上训练，逐步扩展到15×15
MCTS自举：用PPO策略作为先验，结合MCTS生成更高质量的对弈数据
历史策略池：与训练过程中不同阶段的旧版本对弈，防止策略遗忘
残差网络：使用ResNet结构捕捉棋盘局部特征，提升表征能力
分布式训练：多进程并行自我对弈，加速数据收集

总结

PPO通过裁剪目标函数实现了稳定而高效的策略更新，非常适合五子棋这类离散动作空间的博弈问题。通过自我对弈，神经网络从零开始自动学习到活三、冲四、禁手等关键棋形概念，无需人工特征工程。虽然训练需要大量计算资源，但得到的策略具有极强的泛化能力，能够应对各种未见过的新局面。

Tagged with: Java算法 PPO 五子棋强化学习每日算法自我对弈近端策略优化