每日算法 — 使用java实现木头人：反应时间阈值与贪心静止决策

“一二三木头人”（Red Light, Green Light）是风靡世界的童年游戏：一名”木头人”背对众人喊口令，其余玩家趁其背对时向前移动；木头人突然回头时所有人必须静止，被发现移动者淘汰。本文用Java实现这一反应博弈游戏，核心在于建立反应时间阈值模型与贪心前进策略的最优决策分析。

游戏规则与数学建模

游戏参数定义：
– 赛道长度L：起点到终点的距离
– 喊口令周期T：木头人每次背对/面对状态的持续时间
– 反应时间r：玩家从”转头信号”到完全静止所需时间
– 移动速度v：玩家前进速度

核心风险：当木头人转头瞬间，若玩家正在移动且无法在反应时间r内静止，则被淘汰。玩家的决策问题为：在每个周期内选择移动时长以最大化期望前进距离，同时保证生存概率不低于阈值。

最优决策：反应时间阈值策略

设木头人背对时长为t_on、面对时长为t_off。玩家在背对期间以速度v前进，面临的关键约束是：必须在木头人转头前的r秒内开始减速至静止。

贪心最优策略：
1. 在木头人背对期间尽可能前进
2. 在预计转头前r + ε秒提前停止，留出安全余量
3. 若距离终点仅剩很短距离，可适当冒险缩短安全余量

该策略本质是带风险约束的贪心算法：在每期最大化前进距离，同时以反应时间为硬约束保证不被淘汰。

Java完整实现

import java.util.*;

/**
 * 一二三木头人游戏 - 反应时间阈值与贪心静止决策
 * 核心问题：在反应时间约束下，最大化前进距离的生存策略
 */
public class RedLightGreenLight {

    // ==================== 核心模型：游戏状态 ====================

    enum DollState { FACING_AWAY, FACING_TOWARD } // 背对/面对

    static class GameConfig {
        double trackLength;      // 赛道总长
        double reactionTime;     // 玩家反应时间(秒)
        double moveSpeed;        // 移动速度(米/秒)
        double minGreenDuration; // 最短背对时间
        double maxGreenDuration; // 最长背对时间
        double redDuration;      // 面对持续时间
        double safetyMargin;     // 安全余量系数

        GameConfig(double track, double react, double speed,
                   double minG, double maxG, double red, double margin) {
            this.trackLength = track;
            this.reactionTime = react;
            this.moveSpeed = speed;
            this.minGreenDuration = minG;
            this.maxGreenDuration = maxG;
            this.redDuration = red;
            this.safetyMargin = margin;
        }
    }

    static class Player {
        String name;
        double position;      // 当前位置
        double reactionTime;  // 个人反应时间
        double moveSpeed;     // 个人速度
        boolean alive;
        boolean isMoving;
        double totalMoveTime; // 统计总移动时间
        int roundsSurvived;   // 存活轮数

        Player(String name, double react, double speed) {
            this.name = name;
            this.reactionTime = react;
            this.moveSpeed = speed;
            this.position = 0;
            this.alive = true;
            this.isMoving = false;
            this.totalMoveTime = 0;
            this.roundsSurvived = 0;
        }
    }

    // ==================== 核心算法：贪心策略引擎 ====================

    /**
     * 计算当前周期内的最优移动时长
     * 贪心策略：在背对期间移动，预留反应时间+安全余量
     * @param greenDuration 本轮背对持续时间
     * @param player 玩家对象
     * @param config 游戏配置
     * @return 建议移动时长(秒)，0表示不应移动
     */
    static double computeOptimalMoveTime(double greenDuration, Player player, GameConfig config) {
        double safeStopTime = player.reactionTime * config.safetyMargin;
        double availableMoveTime = greenDuration - safeStopTime;

        if (availableMoveTime <= 0) {
            return 0; // 本轮时间太短，安全第一不移动
        }

        // 若即将到达终点，可适当缩短安全余量
        double remaining = config.trackLength - player.position;
        double timeToFinish = remaining / player.moveSpeed;

        if (timeToFinish <= availableMoveTime) {
            return timeToFinish; // 直接冲过终点
        }

        return availableMoveTime;
    }

    /**
     * 带期望最大化的进阶策略
     * 考虑背对时长的概率分布，计算期望前进距离最大的移动时长
     */
    static double computeExpectedOptimalMove(GameConfig config, Player player, Random rand) {
        int samples = 1000;
        double bestMove = 0;
        double bestExpected = 0;

        // 尝试不同的移动时长
        for (double moveTime = 0.1; moveTime <= config.maxGreenDuration; moveTime += 0.1) {
            double totalAdvance = 0;
            int survivalCount = 0;

            for (int s = 0; s < samples; s++) {
                double green = config.minGreenDuration + 
                    rand.nextDouble() * (config.maxGreenDuration - config.minGreenDuration);

                // 若移动时间 + 反应时间 > 背对时长，则被淘汰
                if (moveTime + player.reactionTime > green) {
                    continue; // 淘汰，不计入收益
                }
                survivalCount++;
                totalAdvance += moveTime * player.moveSpeed;
            }

            double expected = survivalCount > 0 ? totalAdvance / samples : 0;
            if (expected > bestExpected) {
                bestExpected = expected;
                bestMove = moveTime;
            }
        }

        return bestMove;
    }

    // ==================== 游戏模拟器 ====================

    /**
     * 模拟完整游戏，支持多种策略
     */
    static List<Player> simulateGame(GameConfig config, List<Player> players, 
                                      String strategy, Random rand) {
        int round = 1;
        List<Player> alivePlayers = new ArrayList<>(players);

        while (alivePlayers.size() > 1) {
            // 检查是否有人到达终点
            List<Player> finished = new ArrayList<>();
            for (Player p : alivePlayers) {
                if (p.position >= config.trackLength) {
                    finished.add(p);
                }
            }
            if (!finished.isEmpty()) {
                System.out.println("\n到达终点的玩家: " + finished);
                return finished;
            }

            System.out.println("\n===== 第" + round + "轮 =====");
            double greenDuration = config.minGreenDuration + 
                rand.nextDouble() * (config.maxGreenDuration - config.minGreenDuration);
            System.out.printf("木头人背对: %.2f秒\n", greenDuration);

            // 背对阶段：玩家决策并移动
            for (Player p : alivePlayers) {
                double moveTime;
                switch (strategy) {
                    case "greedy":
                        moveTime = computeOptimalMoveTime(greenDuration, p, config);
                        break;
                    case "expected":
                        moveTime = computeExpectedOptimal(config, p, rand);
                        break;
                    case "conservative":
                        moveTime = Math.max(0, greenDuration - p.reactionTime * 2);
                        break;
                    case "aggressive":
                        moveTime = greenDuration - p.reactionTime * 0.5;
                        break;
                    default:
                        moveTime = computeOptimalMoveTime(greenDuration, p, config);
                }

                double actualMove = Math.max(0, Math.min(moveTime, greenDuration));
                p.position += actualMove * p.moveSpeed;
                p.totalMoveTime += actualMove;
                p.isMoving = actualMove > 0;

                // 转头瞬间的淘汰判定
                boolean caught = actualMove + p.reactionTime > greenDuration;
                if (caught && rand.nextDouble() < 0.8) { // 80%概率被发现
                    p.alive = false;
                    System.out.println("  " + p.name + " 移动中被发现，淘汰!");
                } else {
                    System.out.printf("  %s: 前进%.2f米 -> 位置%.2f/%.0f%n", 
                        p.name, actualMove * p.moveSpeed, p.position, config.trackLength);
                }
            }

            alivePlayers.removeIf(p -> !p.alive);
            for (Player p : alivePlayers) p.roundsSurvived++;

            // 面对阶段：所有人静止
            System.out.printf("木头人面对: %.2f秒 (所有人静止)\n", config.redDuration);
            round++;

            if (round > 100) break; // 防止无限循环
        }

        return alivePlayers;
    }

    // ==================== 策略对比实验 ====================

    /**
     * 对比不同策略的长期胜率
     */
    static void compareStrategies(GameConfig config, int simulations) {
        String[] strategies = {"greedy", "expected", "conservative", "aggressive"};
        Map<String, Integer> winCount = new HashMap<>();
        Map<String, Double> avgFinishTime = new HashMap<>();

        for (String strategy : strategies) {
            winCount.put(strategy, 0);
            avgFinishTime.put(strategy, 0.0);
        }

        for (int sim = 0; sim < simulations; sim++) {
            for (String strategy : strategies) {
                List<Player> players = new ArrayList<>();
                players.add(new Player("选手", 0.3, 2.5));

                Random rand = new Random(sim);
                List<Player> winners = simulateGameSilent(config, players, strategy, rand);
                if (!winners.isEmpty()) {
                    winCount.merge(strategy, 1, Integer::sum);
                }
            }
        }

        System.out.println("\n========== 策略对比 (" + simulations + "次模拟) ==========");
        for (String s : strategies) {
            int wins = winCount.get(s);
            System.out.printf("%s策略: %d次成功 (%.1f%%)%n", s, wins, 100.0 * wins / simulations);
        }
    }

    static List<Player> simulateGameSilent(GameConfig config, List<Player> players,
                                            String strategy, Random rand) {
        int round = 0;
        List<Player> alive = new ArrayList<>();
        for (Player p : players) alive.add(new Player(p.name, p.reactionTime, p.moveSpeed));

        while (alive.size() > 0 && round < 200) {
            for (Player p : alive) {
                if (p.position >= config.trackLength) return Collections.singletonList(p);
            }

            double green = config.minGreenDuration + 
                rand.nextDouble() * (config.maxGreenDuration - config.minGreenDuration);

            for (Player p : alive) {
                double moveTime = computeOptimalMoveTime(green, p, config);
                if (strategy.equals("conservative")) {
                    moveTime = Math.max(0, green - p.reactionTime * 2);
                } else if (strategy.equals("aggressive")) {
                    moveTime = green - p.reactionTime * 0.5;
                }

                double actual = Math.max(0, Math.min(moveTime, green));
                p.position += actual * p.moveSpeed;

                if (actual + p.reactionTime > green && rand.nextDouble() < 0.8) {
                    p.alive = false;
                }
            }
            alive.removeIf(p -> !p.alive);
            round++;
        }
        return alive;
    }

    // ==================== 主程序与演示 ====================

    public static void main(String[] args) {
        GameConfig config = new GameConfig(
            20.0,   // 赛道20米
            0.3,    // 基准反应时间0.3秒
            2.5,    // 移动速度2.5米/秒
            2.0,    // 最短背对2秒
            5.0,    // 最长背对5秒
            3.0,    // 面对持续3秒
            1.5     // 安全余量系数1.5
        );

        System.out.println("========== 一二三木头人 - 反应阈值决策 ==========");
        System.out.printf("赛道长度: %.0f米 | 反应阈值: %.1f秒 | 速度: %.1f米/秒%n",
            config.trackLength, config.reactionTime, config.moveSpeed);

        // 多人对战演示
        List<Player> players = new ArrayList<>();
        players.add(new Player("闪电", 0.15, 3.5));   // 反应快速度快
        players.add(new Player("稳健", 0.25, 2.8));   // 均衡型
        players.add(new Player("乌龟", 0.40, 2.0));   // 反应慢
        players.add(new Player("莽夫", 0.20, 3.0));   // 速度快但激进
        players.add(new Player("新手", 0.50, 2.5));   // 反应很慢

        Random rand = new Random(2024);
        List<Player> winners = simulateGame(config, players, "greedy", rand);
        System.out.println("\n最终存活: " + winners);

        // 策略对比
        System.out.println("\n========== 策略对比实验 ==========");
        compareStrategies(config, 1000);
    }
}

算法复杂度分析

贪心策略的精髓在于将连续决策问题离散化为”每期独立优化”：每轮只需根据当前背对时长和自身反应时间计算安全移动窗口，无需考虑远期状态，大幅降低了决策复杂度。

扩展思考

1. 多人博弈纳什均衡：当所有玩家同时决策且互相影响（挤占赛道、遮挡视线），问题转化为非合作博弈，存在对称混合策略均衡。
2. 强化学习策略：用Q-Learning训练神经网络策略，状态空间包括当前位置、剩余距离、历史轮次，动作空间为移动时长，奖励为前进距离减去淘汰惩罚。
3. 物理约束细化：引入加速度上限与减速距离，将”瞬间静止”假设替换为匀减速运动模型，使安全余量计算更符合人体工学。

木头人将反应时间阈值、概率风险与贪心决策融为一体，是理解”带约束优化”与”实时决策”的经典教学案例。