每日算法 — 使用java实现推箱子：Q-Learning强化学习与奖励塑形策略

引言

推箱子（Sokoban）是经典的NP-hard谜题，传统解法依赖BFS、A搜索等精确算法，但在复杂关卡中面临状态空间爆炸问题。本文采用Q-Learning强化学习*方法，让智能体通过与环境交互自主学习推箱策略。通过精心设计的奖励塑形（Reward Shaping），引导智能体优先将箱子推向目标位置，同时避免推到死角。

Q-Learning算法原理

Q-Learning是一种无模型、离策略的时序差分控制算法。智能体维护一个Q值表（或函数近似），记录在每个状态下执行每个动作的期望累积回报：

Q(s,a) ← Q(s,a) + α · [r + γ · max_a' Q(s',a') - Q(s,a)]

在推箱子中，状态由玩家位置和所有箱子位置组成，动作空间为上下左右移动（含推箱子动作）。

奖励塑形设计

推箱子的核心难点在于奖励稀疏——只有完成关卡时才能获得正向反馈。为此设计多层次奖励：

状态编码与特征工程

为避免高维Q表，采用紧凑的状态编码：

// 状态编码：玩家位置 + 每个箱子相对目标的最小距离
// 进一步使用Tile Coding或神经网络进行函数近似

Java完整实现

import java.util.*;

/**
 * 基于Q-Learning的推箱子AI
 * 使用奖励塑形引导智能体学习推箱策略
 */
public class QLearningSokoban {

    // 地图符号
    private static final char WALL = '#';
    private static final char EMPTY = ' ';
    private static final char TARGET = '.';
    private static final char BOX = '$';
    private static final char PLAYER = '@';
    private static final char BOX_ON_TARGET = '*';
    private static final char PLAYER_ON_TARGET = '+';

    // 方向定义：上、下、左、右
    private final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final String[] dirNames = {"UP", "DOWN", "LEFT", "RIGHT"};

    // Q-Learning参数
    private final double alpha = 0.1;       // 学习率
    private final double gamma = 0.95;      // 折扣因子
    private final double epsilon = 0.2;     // 探索率
    private final double epsilonDecay = 0.999;
    private final double minEpsilon = 0.01;

    // Q值表：状态字符串 -> 动作Q值数组
    private Map<String, double[]> qTable;

    // 地图
    private char[][] originalMap;
    private int rows, cols;

    // 目标位置集合（用于快速查询）
    private Set<String> targetSet;

    private final Random random = new Random();

    public QLearningSokoban(String[] level) {
        this.rows = level.length;
        this.cols = level[0].length();
        this.originalMap = new char[rows][cols];
        this.targetSet = new HashSet<>();
        this.qTable = new HashMap<>();

        for (int i = 0; i < rows; i++) {
            originalMap[i] = level[i].toCharArray();
            for (int j = 0; j < cols; j++) {
                if (originalMap[i][j] == TARGET || originalMap[i][j] == BOX_ON_TARGET 
                        || originalMap[i][j] == PLAYER_ON_TARGET) {
                    targetSet.add(i + "," + j);
                }
            }
        }
    }

    /**
     * 游戏状态类：记录玩家位置和箱子位置
     */
    static class State {
        int playerRow, playerCol;
        Set<String> boxes; // 箱子位置集合 "r,c"

        State(int pr, int pc, Set<String> boxes) {
            this.playerRow = pr;
            this.playerCol = pc;
            this.boxes = new HashSet<>(boxes);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof State)) return false;
            State s = (State) o;
            return playerRow == s.playerRow && playerCol == s.playerCol 
                    && boxes.equals(s.boxes);
        }

        @Override
        public int hashCode() {
            return Objects.hash(playerRow, playerCol, boxes);
        }

        /**
         * 将状态编码为紧凑字符串，用于Q表索引
         */
        String encode() {
            StringBuilder sb = new StringBuilder();
            sb.append(playerRow).append(",").append(playerCol).append(";");
            List<String> sorted = new ArrayList<>(boxes);
            Collections.sort(sorted);
            for (String b : sorted) sb.append(b).append(";");
            return sb.toString();
        }
    }

    /**
     * 从原始地图构建初始状态
     */
    private State getInitialState() {
        int pr = -1, pc = -1;
        Set<String> boxes = new HashSet<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = originalMap[i][j];
                if (c == PLAYER || c == PLAYER_ON_TARGET) {
                    pr = i;
                    pc = j;
                }
                if (c == BOX || c == BOX_ON_TARGET) {
                    boxes.add(i + "," + j);
                }
            }
        }
        return new State(pr, pc, boxes);
    }

    /**
     * 判断位置是否为墙
     */
    private boolean isWall(int r, int c) {
        return r < 0 || r >= rows || c < 0 || c >= cols || originalMap[r][c] == WALL;
    }

    /**
     * 判断位置是否在目标上
     */
    private boolean isTarget(int r, int c) {
        return targetSet.contains(r + "," + c);
    }

    /**
     * 判断是否为死角（箱子推入后永远无法推出）
     * 简化为：非目标位置且相邻至少两面是墙
     */
    private boolean isDeadlock(int r, int c, Set<String> boxes) {
        if (isTarget(r, c)) return false;

        int wallCount = 0;
        boolean[] wallDir = new boolean[4];
        for (int d = 0; d < 4; d++) {
            int nr = r + dirs[d][0], nc = c + dirs[d][1];
            if (isWall(nr, nc)) {
                wallCount++;
                wallDir[d] = true;
            }
        }

        // 两面相邻墙构成角落死角
        if (wallCount >= 2) {
            // 检查是否相对两面（这种情况不构成死角，因为可以横向/纵向推出）
            if ((wallDir[0] && wallDir[1]) || (wallDir[2] && wallDir[3])) {
                return true; // 上下或左右都是墙
            }
        }
        return false;
    }

    /**
     * 执行动作，返回(新状态, 奖励, 是否结束)
     */
    private Result takeAction(State s, int action) {
        int dr = dirs[action][0], dc = dirs[action][1];
        int nr = s.playerRow + dr, nc = s.playerCol + dc;

        // 撞墙
        if (isWall(nr, nc)) {
            return new Result(s, -5.0, false);
        }

        String nextPos = nr + "," + nc;
        Set<String> newBoxes = new HashSet<>(s.boxes);
        double reward = -1.0; // 基础步数惩罚

        // 推动箱子
        if (s.boxes.contains(nextPos)) {
            int br = nr + dr, bc = nc + dc;
            String boxNewPos = br + "," + bc;

            // 箱子后面是墙或另一个箱子
            if (isWall(br, bc) || s.boxes.contains(boxNewPos)) {
                return new Result(s, -5.0, false);
            }

            newBoxes.remove(nextPos);
            newBoxes.add(boxNewPos);

            // 奖励塑形
            boolean wasOnTarget = isTarget(nr, nc);
            boolean nowOnTarget = isTarget(br, bc);

            if (nowOnTarget && !wasOnTarget) {
                reward += 50.0; // 箱子到达目标
            } else if (!nowOnTarget && wasOnTarget) {
                reward -= 50.0; // 箱子离开目标
            }

            // 死锁检测
            if (isDeadlock(br, bc, newBoxes)) {
                reward -= 100.0;
            }
        }

        State newState = new State(nr, nc, newBoxes);

        // 检查是否完成
        boolean done = true;
        for (String b : newBoxes) {
            String[] parts = b.split(",");
            int br = Integer.parseInt(parts[0]), bc = Integer.parseInt(parts[1]);
            if (!isTarget(br, bc)) {
                done = false;
                break;
            }
        }

        if (done) reward += 1000.0;

        // 势函数奖励：向最近的未覆盖目标靠近
        reward += potentialReward(newState);

        return new Result(newState, reward, done);
    }

    /**
     * 势函数：基于曼哈顿距离的启发式奖励
     */
    private double potentialReward(State s) {
        Set<String> uncovered = new HashSet<>(targetSet);
        uncovered.removeAll(s.boxes);
        if (uncovered.isEmpty()) return 0.0;

        double totalDist = 0.0;
        for (String t : uncovered) {
            String[] tp = t.split(",");
            int tr = Integer.parseInt(tp[0]), tc = Integer.parseInt(tp[1]);

            double minDist = Double.MAX_VALUE;
            for (String b : s.boxes) {
                if (targetSet.contains(b)) continue; // 已在目标上的箱子不计算
                String[] bp = b.split(",");
                int br = Integer.parseInt(bp[0]), bc = Integer.parseInt(bp[1]);
                double dist = Math.abs(br - tr) + Math.abs(bc - tc);
                minDist = Math.min(minDist, dist);
            }
            totalDist += minDist;
        }
        return -totalDist * 0.1; // 距离越近奖励越高（负值越小）
    }

    /**
     * 获取或创建Q值数组
     */
    private double[] getQValues(String stateKey) {
        return qTable.computeIfAbsent(stateKey, k -> new double[4]);
    }

    /**
     * 选择动作：epsilon-贪心策略
     */
    private int selectAction(State s, double eps) {
        String key = s.encode();
        double[] qvals = getQValues(key);

        if (random.nextDouble() < eps) {
            return random.nextInt(4);
        }

        // 选择Q值最大的动作
        int best = 0;
        for (int i = 1; i < 4; i++) {
            if (qvals[i] > qvals[best]) best = i;
        }
        return best;
    }

    /**
     * 训练一个回合
     */
    public int trainEpisode(double eps) {
        State s = getInitialState();
        int steps = 0;
        int maxSteps = 1000;

        while (steps < maxSteps) {
            int action = selectAction(s, eps);
            Result res = takeAction(s, action);

            String sKey = s.encode();
            String sNextKey = res.state.encode();
            double[] qvals = getQValues(sKey);
            double[] qvalsNext = getQValues(sNextKey);

            double maxNext = Double.NEGATIVE_INFINITY;
            for (double q : qvalsNext) maxNext = Math.max(maxNext, q);
            if (maxNext == Double.NEGATIVE_INFINITY) maxNext = 0.0;

            // Q值更新
            qvals[action] += alpha * (res.reward + gamma * maxNext - qvals[action]);

            s = res.state;
            steps++;

            if (res.done) break;
        }

        return steps;
    }

    /**
     * 使用训练好的策略运行
     */
    public void runPolicy() {
        State s = getInitialState();
        int steps = 0;

        System.out.println("Running learned policy...");
        printState(s);

        while (steps < 500) {
            String key = s.encode();
            double[] qvals = getQValues(key);

            int best = 0;
            for (int i = 1; i < 4; i++) {
                if (qvals[i] > qvals[best]) best = i;
            }

            Result res = takeAction(s, best);
            s = res.state;
            steps++;

            System.out.println("Step " + steps + ": " + dirNames[best] + " (reward: " + res.reward + ")");
            printState(s);

            if (res.done) {
                System.out.println("Level completed in " + steps + " steps!");
                return;
            }
        }
        System.out.println("Failed to complete within step limit.");
    }

    private void printState(State s) {
        char[][] display = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (originalMap[i][j] == WALL) {
                    display[i][j] = WALL;
                } else if (targetSet.contains(i + "," + j)) {
                    display[i][j] = TARGET;
                } else {
                    display[i][j] = EMPTY;
                }
            }
        }
        for (String b : s.boxes) {
            String[] p = b.split(",");
            int br = Integer.parseInt(p[0]), bc = Integer.parseInt(p[1]);
            display[br][bc] = targetSet.contains(b) ? BOX_ON_TARGET : BOX;
        }
        display[s.playerRow][s.playerCol] = 
                targetSet.contains(s.playerRow + "," + s.playerCol) ? PLAYER_ON_TARGET : PLAYER;

        for (int i = 0; i < rows; i++) {
            System.out.println(new String(display[i]));
        }
        System.out.println();
    }

    static class Result {
        State state;
        double reward;
        boolean done;
        Result(State s, double r, boolean d) {
            this.state = s; this.reward = r; this.done = d;
        }
    }

    public static void main(String[] args) {
        // 简单关卡：3x3，一个箱子一个目标
        String[] level = {
            "#####",
            "#@$.#",
            "#####"
        };

        QLearningSokoban agent = new QLearningSokoban(level);

        // 训练
        int episodes = 5000;
        double eps = epsilon;
        for (int ep = 0; ep < episodes; ep++) {
            int steps = agent.trainEpisode(eps);
            eps = Math.max(minEpsilon, eps * epsilonDecay);
            if ((ep + 1) % 500 == 0) {
                System.out.println("Episode " + (ep + 1) + ", epsilon=" + String.format("%.4f", eps));
            }
        }

        // 运行
        agent.runPolicy();
    }
}

算法复杂度分析

关键设计要点

1. 奖励塑形：通过子目标奖励（箱子到达目标）和死锁惩罚，将稀疏奖励转化为密集信号，大幅加速收敛
2. 势函数引导：利用曼哈顿距离的负值作为附加奖励，使智能体天然倾向于将箱子推向目标
3. 死角检测：简单的墙壁角落检测即可过滤大量无效状态，避免智能体学会”推入死角”的错误策略
4. epsilon衰减：初期高探索率帮助发现有效策略，后期低探索率稳定已学策略

总结

Q-Learning为推箱子这类组合优化问题提供了一种不依赖人工启发式的学习框架。通过奖励塑形，智能体能够在数千回合内学会基本推箱策略。对于更复杂关卡，可将Q表替换为神经网络（DQN），利用函数近似处理高维状态空间。