每日算法 — 使用java实现打地鼠：泊松过程建模与最优反应窗口决策

引言

打地鼠（Whac-A-Mole）看似简单——地鼠随机冒出，玩家快速敲击——但其背后隐藏着丰富的概率建模与决策优化问题。本文从泊松过程（Poisson Process）出发，对地鼠的出现规律进行数学建模，并推导在有限反应时间下的最优敲击策略。读者将看到，即使是这款童年游戏，也能成为理解随机过程与最优停时理论的绝佳载体。

核心算法思想

1. 泊松过程建模

假设每个洞口独立地以泊松过程产生地鼠，速率为 $\lambda$（单位时间内平均冒出次数）。那么在时间区间 $[0, t]$ 内，该洞口冒出 $k$ 只地鼠的概率为：

$$P(N(t)=k) = \frac{(\lambda t)^k e^{-\lambda t}}{k!}$$

相邻两只地鼠的等待时间服从指数分布：$T \sim Exp(\lambda)$，均值为 $1/\lambda$。

2. 反应窗口与命中概率

玩家从看到地鼠到挥锤命中存在一个反应时间 $R$（通常为 200-400ms）。地鼠在洞口停留的时间为 $S$（通常 1-2 秒）。只有当玩家在地鼠消失前完成反应并命中，才算得分。因此，对于一只在时刻 $t_0$ 出现的地鼠，玩家的有效命中窗口为 $[t_0, t_0 + S]$，而玩家的反应+动作耗时为 $R$。

3. 最优反应窗口决策

当多个洞口同时有地鼠时，玩家面临选择。最优策略基于以下价值函数：

$$V_i = p_i \cdot (score_i + futureValue_i) – c$$

其中 $p_i$ 为命中洞口 $i$ 的概率（取决于距离、地鼠剩余停留时间），$c$ 为切换目标的认知代价。贪心策略选择当前 $V_i$ 最大的洞口；更高级的策略则通过动态规划计算多步期望收益。

4. 反应时间分布拟合

通过记录大量玩家的反应时间数据，可以用对数正态分布或伽马分布拟合：

$$R \sim LogNormal(\mu, \sigma^2)$$

据此可以计算不同难度下的预期命中率，并动态调整地鼠出现速率 $\lambda$ 以维持恒定的挑战水平（动态难度调整，DDA）。

Java 实现

import java.util.*;

/**
 * 打地鼠 AI/模拟器 — 泊松过程建模 + 最优反应窗口决策
 * 功能：
 * 1. 按泊松过程生成地鼠出现事件
 * 2. 模拟玩家反应时间分布
 * 3. 计算最优敲击顺序（贪心/动态规划）
 * 4. 动态难度调整（DDA）
 */
public class WhacAMoleSimulator {

    // 游戏配置
    private final int rows;
    private final int cols;
    private final double baseLambda;    // 基础泊松速率（每秒每只地鼠）
    private final double stayTime;      // 地鼠停留时间（秒）
    private final Random rand;

    // 玩家模型
    private final double reactionMean;  // 平均反应时间（秒）
    private final double reactionStd;   // 反应时间标准差

    // 动态难度
    private double currentLambda;
    private double targetHitRate = 0.75; // 目标命中率

    public WhacAMoleSimulator(int rows, int cols, double lambda, double stay,
                              double reactMean, double reactStd) {
        this.rows = rows;
        this.cols = cols;
        this.baseLambda = lambda;
        this.stayTime = stay;
        this.reactionMean = reactMean;
        this.reactionStd = reactStd;
        this.currentLambda = lambda;
        this.rand = new Random();
    }

    /**
     * 泊松过程生成：在时间段 [0, duration] 内生成所有地鼠出现事件
     * 使用指数分布采样等待时间
     */
    public List<MoleEvent> generateEvents(double duration) {
        List<MoleEvent> events = new ArrayList<>();
        int holes = rows * cols;

        for (int h = 0; h < holes; h++) {
            double t = 0;
            while (t < duration) {
                // 指数分布：等待时间 ~ Exp(lambda)
                double wait = -Math.log(1 - rand.nextDouble()) / currentLambda;
                t += wait;
                if (t < duration) {
                    events.add(new MoleEvent(h / cols, h % cols, t));
                }
            }
        }
        events.sort(Comparator.comparingDouble(e -> e.appearTime));
        return events;
    }

    /**
     * 模拟玩家反应时间：从对数正态分布采样
     */
    public double sampleReactionTime() {
        // 对数正态分布参数转换
        double sigma2 = Math.log(1 + (reactionStd * reactionStd) / (reactionMean * reactionMean));
        double mu = Math.log(reactionMean) - sigma2 / 2;
        double z = rand.nextGaussian();
        return Math.exp(mu + Math.sqrt(sigma2) * z);
    }

    /**
     * 贪心最优策略：在每一时刻选择预期收益最高的地鼠
     * @param events 所有地鼠出现事件
     * @return 实际命中事件列表
     */
    public List<MoleEvent> simulateGreedyPlayer(List<MoleEvent> events) {
        List<MoleEvent> hits = new ArrayList<>();
        double currentTime = 0;

        // 活跃地鼠：已出现且未消失
        PriorityQueue<MoleEvent> active = new PriorityQueue<>(
            Comparator.comparingDouble(e -> e.deadline)
        );

        int idx = 0;
        while (idx < events.size() || !active.isEmpty()) {
            // 加入新出现的地鼠
            while (idx < events.size() && events.get(idx).appearTime <= currentTime) {
                MoleEvent e = events.get(idx);
                e.deadline = e.appearTime + stayTime;
                active.offer(e);
                idx++;
            }

            if (active.isEmpty()) {
                // 跳到下一个事件
                currentTime = events.get(idx).appearTime;
                continue;
            }

            // 贪心选择：找价值最高的活跃地鼠
            MoleEvent best = selectBest(active, currentTime);
            if (best == null) {
                // 所有地鼠都来不及打了，跳到下一个
                currentTime = events.get(idx).appearTime;
                active.removeIf(e -> e.deadline < currentTime);
                continue;
            }

            double react = sampleReactionTime();
            double hitTime = currentTime + react;

            if (hitTime <= best.deadline) {
                best.hitTime = hitTime;
                best.hit = true;
                hits.add(best);
                currentTime = hitTime;
            } else {
                // 反应太慢， missed
                best.missed = true;
            }
            active.remove(best);
            // 移除已超时的地鼠
            active.removeIf(e -> e.deadline < currentTime);
        }
        return hits;
    }

    /**
     * 选择当前最优地鼠
     * 价值 = 基础分 / (距离惩罚 + 剩余时间倒数)
     * 距离惩罚：玩家当前位置到地鼠洞口的欧氏距离对应的移动时间
     */
    private MoleEvent selectBest(PriorityQueue<MoleEvent> active, double now) {
        MoleEvent best = null;
        double bestValue = -1;
        // 假设玩家当前在中心位置 (rows/2, cols/2)
        double pr = rows / 2.0, pc = cols / 2.0;

        for (MoleEvent e : active) {
            double remaining = e.deadline - now;
            if (remaining <= 0) continue;
            double dist = Math.sqrt((e.r - pr) * (e.r - pr) + (e.c - pc) * (e.c - pc));
            double moveTime = dist * 0.1; // 每格移动耗时 0.1s
            double value = 1.0 / (moveTime + 0.5 / remaining + 0.1);
            if (value > bestValue) {
                bestValue = value;
                best = e;
                pr = e.r; pc = e.c; // 更新假设位置（贪心移动）
            }
        }
        return best;
    }

    /**
     * 动态难度调整（DDA）
     * 根据最近 N 局的命中率调整 lambda
     */
    public void adjustDifficulty(List<Double> recentHitRates) {
        if (recentHitRates.isEmpty()) return;
        double avgHit = recentHitRates.stream().mapToDouble(Double::doubleValue).average().orElse(0);
        double error = avgHit - targetHitRate;
        // PID 控制器简化版：比例调整
        double kp = 0.5;
        currentLambda = baseLambda * (1 - kp * error);
        currentLambda = Math.max(0.1, Math.min(currentLambda, baseLambda * 3));
    }

    /**
     * 计算泊松过程的理论命中率上界
     * 使用 Erlang B 公式思想近似
     */
    public double theoreticalMaxHitRate(List<MoleEvent> events, double duration) {
        int totalMoles = events.size();
        if (totalMoles == 0) return 0;
        double avgReact = reactionMean;
        // 理论上限：总有效窗口时间 / 总反应耗时
        double totalWindow = totalMoles * stayTime;
        double totalReact = totalMoles * avgReact;
        return Math.min(1.0, totalWindow / (totalReact + totalWindow * 0.5));
    }

    // ============== 地鼠事件类 ==============
    public static class MoleEvent {
        int r, c;           // 洞口坐标
        double appearTime;  // 出现时刻
        double deadline;    // 消失时刻
        double hitTime;     // 命中时刻
        boolean hit;        // 是否命中
        boolean missed;     // 是否错过

        MoleEvent(int r, int c, double t) {
            this.r = r; this.c = c; this.appearTime = t;
        }
    }

    // ============== 演示入口 ==============
    public static void main(String[] args) {
        // 3x3 洞口，基础速率 0.5/s，停留 1.5s，反应均值 0.3s，标准差 0.1s
        WhacAMoleSimulator sim = new WhacAMoleSimulator(3, 3, 0.5, 1.5, 0.3, 0.1);

        double duration = 30.0; // 30秒游戏
        List<MoleEvent> events = sim.generateEvents(duration);
        System.out.println("总地鼠数：" + events.size());

        List<MoleEvent> hits = sim.simulateGreedyPlayer(events);
        long hitCount = hits.stream().filter(e -> e.hit).count();
        long missedCount = events.size() - hitCount;

        System.out.println("命中：" + hitCount + "，错过：" + missedCount);
        System.out.println("命中率：" + String.format("%.2f%%", 100.0 * hitCount / events.size()));
        System.out.println("理论命中率上界：" + String.format("%.2f%%",
            100.0 * sim.theoreticalMaxHitRate(events, duration)));

        // DDA 演示
        List<Double> recent = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            List<MoleEvent> ev = sim.generateEvents(duration);
            List<MoleEvent> hi = sim.simulateGreedyPlayer(ev);
            double rate = hi.size() / (double) ev.size();
            recent.add(rate);
        }
        sim.adjustDifficulty(recent);
        System.out.println("调整后的 lambda：" + String.format("%.3f", sim.currentLambda));
    }
}

复杂度分析

其中 $H$ 为洞口数，$T$ 为游戏时长，$E$ 为事件总数，$N$ 为历史局数。

总结

泊松过程为打地鼠的地鼠出现规律提供了严谨的数学描述，指数分布的等待时间让游戏节奏天然具有不可预测性。贪心最优策略在每个决策点最大化即时期望收益，而动态难度调整则确保了玩家始终处于”心流通道”——既不会因过于简单而厌倦，也不会因过于困难而挫败。读者可以在此基础上继续扩展：引入多玩家竞争模型、设计基于强化学习的自适应 AI 对手、或将泊松过程升级为非齐次泊松过程（Non-homogeneous Poisson Process），让地鼠出现速率随时间动态变化，制造更丰富的波峰波谷体验。