每日算法 — 使用java实现井字棋：多层感知机神经网络与反向传播训练

引言

井字棋（Tic-Tac-Toe）是规则最简单的博弈游戏之一，但用深度学习让AI从零开始学习策略，依然是一个极具教育意义的课题。本文将使用Java实现一个基于多层感知机（MLP）神经网络的井字棋AI，通过反向传播算法训练网络评估棋局状态，最终让AI掌握接近完美的对弈策略。

核心算法思路

多层感知机（MLP）

我们设计一个三层全连接神经网络：
– 输入层：9个神经元，对应3×3棋盘的每个位置（1表示己方，-1表示对手，0表示空位）
– 隐藏层：18个神经元，使用ReLU激活函数
– 输出层：1个神经元，输出当前局面对己方的评估值（越接近1表示越有利）

反向传播训练

通过自对弈生成训练数据，利用反向传播更新权重。损失函数采用均方误差（MSE），让网络预测值尽量接近真实对局结果。

Minimax决策

训练后的神经网络作为评估函数，结合Minimax搜索选择最优落子位置。

Java实现

神经网络核心类

import java.util.Random;

/**
 * 多层感知机神经网络
 */
public class NeuralNetwork {
    private int inputSize;
    private int hiddenSize;
    private int outputSize;
    private double[][] weightsInputHidden;  // 输入到隐藏层权重
    private double[] biasHidden;             // 隐藏层偏置
    private double[][] weightsHiddenOutput;  // 隐藏到输出层权重
    private double[] biasOutput;             // 输出层偏置
    private double learningRate = 0.01;
    private Random random = new Random(42);  // 固定种子便于复现

    // 训练时缓存的中间结果
    private double[] hiddenInput;
    private double[] hiddenOutput;
    private double[] outputInput;
    private double[] outputResult;

    public NeuralNetwork(int inputSize, int hiddenSize, int outputSize) {
        this.inputSize = inputSize;
        this.hiddenSize = hiddenSize;
        this.outputSize = outputSize;

        weightsInputHidden = new double[inputSize][hiddenSize];
        biasHidden = new double[hiddenSize];
        weightsHiddenOutput = new double[hiddenSize][outputSize];
        biasOutput = new double[outputSize];

        initializeWeights();
    }

    /**
     * Xavier初始化权重
     */
    private void initializeWeights() {
        double wihLimit = Math.sqrt(6.0 / (inputSize + hiddenSize));
        for (int i = 0; i < inputSize; i++) {
            for (int j = 0; j < hiddenSize; j++) {
                weightsInputHidden[i][j] = (random.nextDouble() * 2 - 1) * wihLimit;
            }
        }

        double whoLimit = Math.sqrt(6.0 / (hiddenSize + outputSize));
        for (int h = 0; h < hiddenSize; h++) {
            for (int o = 0; o < outputSize; o++) {
                weightsHiddenOutput[h][o] = (random.nextDouble() * 2 - 1) * whoLimit;
            }
        }
    }

    /**
     * 前向传播
     */
    public double forward(double[] input) {
        this.hiddenInput = new double[hiddenSize];
        this.hiddenOutput = new double[hiddenSize];
        this.outputInput = new double[outputSize];
        this.outputResult = new double[outputSize];

        // 输入层 -> 隐藏层
        for (int j = 0; j < hiddenSize; j++) {
            double sum = biasHidden[j];
            for (int i = 0; i < inputSize; i++) {
                sum += input[i] * weightsInputHidden[i][j];
            }
            hiddenInput[j] = sum;
            hiddenOutput[j] = relu(sum);
        }

        // 隐藏层 -> 输出层
        for (int k = 0; k < outputSize; k++) {
            double sum = biasOutput[k];
            for (int j = 0; j < hiddenSize; j++) {
                sum += hiddenOutput[j] * weightsHiddenOutput[j][k];
            }
            outputInput[k] = sum;
            outputResult[k] = tanh(sum); // 输出层使用tanh，范围[-1,1]
        }

        return outputResult[0];
    }

    /**
     * 反向传播训练单个样本
     * @param input 输入特征
     * @param target 目标值（1表示赢，-1表示输，0表示平）
     */
    public void train(double[] input, double target) {
        double prediction = forward(input);
        double error = prediction - target;

        // 输出层梯度
        double[] outputDelta = new double[outputSize];
        for (int k = 0; k < outputSize; k++) {
            outputDelta[k] = error * tanhDerivative(outputInput[k]);
        }

        // 隐藏层梯度
        double[] hiddenDelta = new double[hiddenSize];
        for (int j = 0; j < hiddenSize; j++) {
            double sum = 0;
            for (int k = 0; k < outputSize; k++) {
                sum += outputDelta[k] * weightsHiddenOutput[j][k];
            }
            hiddenDelta[j] = sum * reluDerivative(hiddenInput[j]);
        }

        // 更新隐藏层到输出层权重
        for (int j = 0; j < hiddenSize; j++) {
            for (int k = 0; k < outputSize; k++) {
                weightsHiddenOutput[j][k] -= learningRate * outputDelta[k] * hiddenOutput[j];
            }
        }
        for (int k = 0; k < outputSize; k++) {
            biasOutput[k] -= learningRate * outputDelta[k];
        }

        // 更新输入层到隐藏层权重
        for (int i = 0; i < inputSize; i++) {
            for (int j = 0; j < hiddenSize; j++) {
                weightsInputHidden[i][j] -= learningRate * hiddenDelta[j] * input[i];
            }
        }
        for (int j = 0; j < hiddenSize; j++) {
            biasHidden[j] -= learningRate * hiddenDelta[j];
        }
    }

    private double relu(double x) {
        return Math.max(0, x);
    }

    private double reluDerivative(double x) {
        return x > 0 ? 1.0 : 0.0;
    }

    private double tanh(double x) {
        return Math.tanh(x);
    }

    private double tanhDerivative(double x) {
        double t = Math.tanh(x);
        return 1.0 - t * t;
    }

    public void setLearningRate(double lr) { this.learningRate = lr; }
}

棋盘状态管理

/**
 * 井字棋棋盘
 */
public class TicTacToeBoard {
    private int[] board = new int[9]; // 0=空, 1=玩家1(X), -1=玩家2(O)
    private int currentPlayer = 1;

    /**
     * 将棋盘转换为神经网络输入
     */
    public double[] toNeuralInput(int perspective) {
        double[] input = new double[9];
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                input[i] = 0;
            } else if (board[i] == perspective) {
                input[i] = 1;
            } else {
                input[i] = -1;
            }
        }
        return input;
    }

    /**
     * 落子
     */
    public boolean makeMove(int position) {
        if (position < 0 || position >= 9 || board[position] != 0) {
            return false;
        }
        board[position] = currentPlayer;
        currentPlayer = -currentPlayer;
        return true;
    }

    /**
     * 撤销落子（用于搜索回溯）
     */
    public void undoMove(int position) {
        board[position] = 0;
        currentPlayer = -currentPlayer;
    }

    /**
     * 检查是否获胜
     */
    public int checkWinner() {
        int[][] lines = {
            {0,1,2}, {3,4,5}, {6,7,8}, // 横
            {0,3,6}, {1,4,7}, {2,5,8}, // 竖
            {0,4,8}, {2,4,6}           // 对角
        };
        for (int[] line : lines) {
            if (board[line[0]] != 0 && 
                board[line[0]] == board[line[1]] && 
                board[line[1]] == board[line[2]]) {
                return board[line[0]];
            }
        }
        return 0; // 无人获胜
    }

    /**
     * 检查是否平局
     */
    public boolean isDraw() {
        if (checkWinner() != 0) return false;
        for (int cell : board) {
            if (cell == 0) return false;
        }
        return true;
    }

    /**
     * 获取所有合法落子位置
     */
    public java.util.List<Integer> getLegalMoves() {
        java.util.List<Integer> moves = new java.util.ArrayList<>();
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) moves.add(i);
        }
        return moves;
    }

    public int getCurrentPlayer() { return currentPlayer; }
    public int[] getBoard() { return board.clone(); }

    public TicTacToeBoard copy() {
        TicTacToeBoard copy = new TicTacToeBoard();
        copy.board = board.clone();
        copy.currentPlayer = currentPlayer;
        return copy;
    }

    public void printBoard() {
        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0) System.out.println();
            if (board[i] == 1) System.out.print(" X ");
            else if (board[i] == -1) System.out.print(" O ");
            else System.out.print("   ");
            if (i % 3 != 2) System.out.print("|");
        }
        System.out.println();
    }
}

自对弈训练引擎

import java.util.*;

/**
 * 自对弈训练引擎
 */
public class SelfPlayTrainer {
    private NeuralNetwork network;
    private Random random = new Random();

    public SelfPlayTrainer(NeuralNetwork network) {
        this.network = network;
    }

    /**
     * 执行一轮自对弈训练
     */
    public void trainEpisode() {
        TicTacToeBoard board = new TicTacToeBoard();
        List<TrainingSample> samples = new ArrayList<>();

        while (board.checkWinner() == 0 && !board.isDraw()) {
            int currentPlayer = board.getCurrentPlayer();
            double[] state = board.toNeuralInput(currentPlayer);
            int move = selectMove(board);
            board.makeMove(move);
            samples.add(new TrainingSample(state, currentPlayer));
        }

        // 确定对局结果
        int winner = board.checkWinner();
        double finalReward;
        if (winner == 0) {
            finalReward = 0; // 平局
        } else {
            finalReward = 1; // 有获胜方
        }

        // 为每一步分配目标值
        for (int i = samples.size() - 1; i >= 0; i--) {
            TrainingSample sample = samples.get(i);
            double target;
            if (winner == 0) {
                target = 0;
            } else if (sample.player == winner) {
                target = finalReward;
            } else {
                target = -finalReward;
            }
            network.train(sample.state, target);
        }
    }

    /**
     * 基于神经网络评估选择落子（带ε-贪心探索）
     */
    private int selectMove(TicTacToeBoard board) {
        double epsilon = 0.3; // 探索率
        List<Integer> legalMoves = board.getLegalMoves();

        if (random.nextDouble() < epsilon) {
            return legalMoves.get(random.nextInt(legalMoves.size()));
        }

        int bestMove = -1;
        double bestValue = Double.NEGATIVE_INFINITY;
        int currentPlayer = board.getCurrentPlayer();

        for (int move : legalMoves) {
            TicTacToeBoard sim = board.copy();
            sim.makeMove(move);

            double value;
            int winner = sim.checkWinner();
            if (winner == currentPlayer) {
                value = 1.0; // 立即获胜
            } else if (winner == -currentPlayer) {
                value = -1.0; // 对手获胜（不应发生）
            } else if (sim.isDraw()) {
                value = 0.0;
            } else {
                // 评估对手视角的反向值
                value = -network.forward(sim.toNeuralInput(-currentPlayer));
            }

            if (value > bestValue) {
                bestValue = value;
                bestMove = move;
            }
        }

        return bestMove;
    }

    /**
     * 批量训练
     */
    public void train(int episodes) {
        for (int ep = 0; ep < episodes; ep++) {
            trainEpisode();
            if ((ep + 1) % 1000 == 0) {
                System.out.println("已完成 " + (ep + 1) + " 轮训练");
            }
        }
    }

    private static class TrainingSample {
        double[] state;
        int player;

        TrainingSample(double[] state, int player) {
            this.state = state;
            this.player = player;
        }
    }
}

人机对战与测试

import java.util.*;

/**
 * 井字棋AI对战主程序
 */
public class TicTacToeAI {
    public static void main(String[] args) {
        // 创建并训练神经网络
        NeuralNetwork network = new NeuralNetwork(9, 18, 1);
        network.setLearningRate(0.01);

        System.out.println("开始自对弈训练...");
        SelfPlayTrainer trainer = new SelfPlayTrainer(network);
        trainer.train(20000);
        System.out.println("训练完成！\n");

        // 测试AI胜率
        testAI(network, 1000);

        // 人机对战
        playWithHuman(network);
    }

    /**
     * 测试AI对随机玩家的胜率
     */
    private static void testAI(NeuralNetwork network, int games) {
        int wins = 0, draws = 0, losses = 0;
        Random rand = new Random();

        for (int g = 0; g < games; g++) {
            TicTacToeBoard board = new TicTacToeBoard();
            boolean aiFirst = g % 2 == 0;

            while (board.checkWinner() == 0 && !board.isDraw()) {
                if ((board.getCurrentPlayer() == 1) == aiFirst) {
                    // AI落子
                    int move = aiMove(board, network);
                    board.makeMove(move);
                } else {
                    // 随机玩家落子
                    List<Integer> moves = board.getLegalMoves();
                    board.makeMove(moves.get(rand.nextInt(moves.size())));
                }
            }

            int winner = board.checkWinner();
            if (winner == 0) draws++;
            else if ((winner == 1) == aiFirst) wins++;
            else losses++;
        }

        System.out.printf("AI对随机玩家 %d 局: 胜%d 平%d 负%d%n", 
            games, wins, draws, losses);
        System.out.printf("胜率: %.1f%% %n%n", (wins + 0.5 * draws) / games * 100);
    }

    /**
     * AI选择最优落子
     */
    private static int aiMove(TicTacToeBoard board, NeuralNetwork network) {
        List<Integer> legalMoves = board.getLegalMoves();
        int bestMove = legalMoves.get(0);
        double bestValue = Double.NEGATIVE_INFINITY;
        int currentPlayer = board.getCurrentPlayer();

        for (int move : legalMoves) {
            TicTacToeBoard sim = board.copy();
            sim.makeMove(move);

            double value;
            int winner = sim.checkWinner();
            if (winner == currentPlayer) {
                value = 10.0; // 优先立即获胜
            } else if (sim.isDraw()) {
                value = 0.0;
            } else {
                value = -network.forward(sim.toNeuralInput(-currentPlayer));
            }

            if (value > bestValue) {
                bestValue = value;
                bestMove = move;
            }
        }

        return bestMove;
    }

    /**
     * 人机对战交互
     */
    private static void playWithHuman(NeuralNetwork network) {
        Scanner scanner = new Scanner(System.in);
        TicTacToeBoard board = new TicTacToeBoard();

        System.out.println("开始人机对战！你是 O，AI 是 X");
        System.out.println("棋盘位置编号：");
        System.out.println(" 0 | 1 | 2 ");
        System.out.println(" 3 | 4 | 5 ");
        System.out.println(" 6 | 7 | 8 ");

        boolean humanFirst = false; // AI先手

        while (board.checkWinner() == 0 && !board.isDraw()) {
            board.printBoard();

            if ((board.getCurrentPlayer() == 1) != humanFirst) {
                // AI回合
                System.out.println("AI 思考中...");
                int move = aiMove(board, network);
                board.makeMove(move);
                System.out.println("AI 落子位置: " + move);
            } else {
                // 人类回合
                System.out.print("请输入落子位置(0-8): ");
                int move = scanner.nextInt();
                if (!board.makeMove(move)) {
                    System.out.println("非法落子，请重试！");
                }
            }
        }

        board.printBoard();
        int winner = board.checkWinner();
        if (winner == 0) {
            System.out.println("平局！");
        } else if ((winner == 1) != humanFirst) {
            System.out.println("AI 获胜！");
        } else {
            System.out.println("你获胜了！");
        }

        scanner.close();
    }
}

算法复杂度分析

其中：I=9（输入），H=18（隐藏层），O=1（输出），N=训练轮数。

总结

本文通过Java实现了一个基于深度学习的井字棋AI，核心要点包括：

• 多层感知机将棋盘状态映射为胜率评估值
• 反向传播算法通过自对弈数据不断优化网络权重
• ε-贪心策略平衡探索与利用，防止陷入局部最优
• 神经网络评估替代传统启发式函数，实现端到端学习

读者可以尝试调整网络结构（增加隐藏层、改变激活函数）、训练策略（引入经验回放、对抗训练）和搜索深度（结合Minimax），进一步提升AI的对弈水平。