每日算法 — 使用java实现打地鼠：泊松过程建模与反应时间最优击中策略

引言

打地鼠是一款考验玩家反应速度与判断力的经典街机游戏。地鼠随机从洞口冒出，玩家需要在有限时间内尽可能多地击中它们。本文将用Java实现一个带AI决策的打地鼠游戏，核心在于如何建模地鼠出现的随机过程，并计算最优击中策略。

算法原理

1. 泊松过程建模

地鼠的出现可以建模为泊松过程（Poisson Process），即在单位时间内地鼠出现的次数服从泊松分布。设单位时间内平均出现λ只地鼠，则在时间t内出现k只地鼠的概率为：

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

2. 反应时间统计分析

人类反应时间近似服从对数正态分布。设反应时间为T，则：

$$\ln(T) \sim N(\mu, \sigma^2)$$

AI可以通过统计历史反应时间，预测下一个地鼠出现的最佳等待窗口。

3. 最优击中决策

给定多个地鼠同时出现的情况，AI需要选择击中顺序使得总得分最大化。这是一个带截止时间的调度问题，可用贪心策略：优先击中得分高且消失快的地鼠。

Java实现

import java.util.*;

/**
 * 打地鼠游戏核心算法实现
 * 包含泊松过程模拟、反应时间统计与最优击中决策
 */
public class WhackAMole {

    // 游戏配置
    private static final int GRID_SIZE = 3;          // 3x3网格
    private static final double LAMBDA = 2.0;        // 单位时间平均出现2只地鼠
    private static final int MOLE_LIFETIME_MS = 2000; // 地鼠存活时间2秒
    private static final int REACTION_TIME_MS = 300;  // 平均反应时间300ms

    // 地鼠状态
    static class Mole {
        int row, col;
        long appearTime;
        long disappearTime;
        int score;
        boolean hit;

        Mole(int row, int col, long appearTime, int score) {
            this.row = row;
            this.col = col;
            this.appearTime = appearTime;
            this.disappearTime = appearTime + MOLE_LIFETIME_MS;
            this.score = score;
            this.hit = false;
        }

        // 计算在指定时间点击中的概率（基于反应时间模型）
        double hitProbability(long clickTime) {
            if (clickTime < appearTime || clickTime > disappearTime) return 0;
            long dt = clickTime - appearTime;
            // 对数正态CDF：反应时间小于dt的概率
            double lnDt = Math.log(dt + 1);
            double mu = Math.log(REACTION_TIME_MS);
            double sigma = 0.5;
            return 0.5 * (1 + erf((lnDt - mu) / (sigma * Math.sqrt(2))));
        }
    }

    // 误差函数近似
    static double erf(double x) {
        double a1 =  0.254829592, a2 = -0.284496736;
        double a3 =  1.421413741, a4 = -1.453152027;
        double a5 =  1.061405429, p  =  0.3275911;
        int sign = x < 0 ? -1 : 1;
        x = Math.abs(x);
        double t = 1.0 / (1.0 + p * x);
        double y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.exp(-x * x);
        return sign * y;
    }

    // 泊松过程：生成下一个地鼠出现的时间间隔
    static double nextPoissonInterval(double lambda) {
        return -Math.log(1.0 - Math.random()) / lambda;
    }

    // 生成一局游戏中的地鼠序列
    List<Mole> generateMoles(int gameDurationSec) {
        List<Mole> moles = new ArrayList<>();
        Random rand = new Random();
        double currentTime = 0;

        while (currentTime < gameDurationSec) {
            currentTime += nextPoissonInterval(LAMBDA);
            if (currentTime >= gameDurationSec) break;

            int r = rand.nextInt(GRID_SIZE);
            int c = rand.nextInt(GRID_SIZE);
            int score = 10 + rand.nextInt(41); // 10-50分
            moles.add(new Mole(r, c, (long)(currentTime * 1000), score));
        }
        return moles;
    }

    // 贪心最优击中策略
    // 在每一时刻，选择期望收益最高的地鼠进行击中
    List<Mole> greedyHitStrategy(List<Mole> moles) {
        List<Mole> hits = new ArrayList<>();
        long currentTime = 0;
        Set<Mole> active = new HashSet<>();
        int idx = 0;

        while (idx < moles.size() || !active.isEmpty()) {
            // 将新出现的地鼠加入活跃集合
            while (idx < moles.size() && moles.get(idx).appearTime <= currentTime) {
                active.add(moles.get(idx));
                idx++;
            }

            // 移除已消失的地鼠
            active.removeIf(m -> m.disappearTime <= currentTime || m.hit);

            if (active.isEmpty()) {
                if (idx < moles.size()) {
                    currentTime = moles.get(idx).appearTime;
                }
                continue;
            }

            // 贪心选择：期望收益 = 分数 * 击中概率
            Mole best = null;
            double bestExpected = 0;
            for (Mole m : active) {
                double prob = m.hitProbability(currentTime + REACTION_TIME_MS);
                double expected = m.score * prob;
                if (expected > bestExpected) {
                    bestExpected = expected;
                    best = m;
                }
            }

            if (best != null) {
                best.hit = true;
                hits.add(best);
                currentTime += REACTION_TIME_MS;
            } else {
                currentTime += 50; // 小步前进
            }
        }
        return hits;
    }

    // 模拟多局游戏，统计得分分布
    void simulateGames(int numGames, int durationSec) {
        int totalScore = 0;
        int totalMoles = 0;
        int totalHits = 0;

        for (int i = 0; i < numGames; i++) {
            List<Mole> moles = generateMoles(durationSec);
            List<Mole> hits = greedyHitStrategy(moles);

            int score = hits.stream().mapToInt(m -> m.score).sum();
            totalScore += score;
            totalMoles += moles.size();
            totalHits += hits.size();
        }

        System.out.println("===== 打地鼠AI模拟结果 =====");
        System.out.printf("模拟局数: %d%n", numGames);
        System.out.printf("平均每局地鼠数: %.2f%n", (double) totalMoles / numGames);
        System.out.printf("平均每局击中数: %.2f%n", (double) totalHits / numGames);
        System.out.printf("平均每局得分: %.2f%n", (double) totalScore / numGames);
        System.out.printf("击中率: %.2f%%%n", 100.0 * totalHits / totalMoles);
    }

    public static void main(String[] args) {
        WhackAMole game = new WhackAMole();
        game.simulateGames(1000, 30); // 模拟1000局，每局30秒
    }
}

复杂度分析

• 泊松生成：O(n)，n为地鼠数量
• 贪心决策：每轮最多检查所有活跃地鼠，时间复杂度为O(m × k)，其中m为地鼠总数，k为平均同时活跃地鼠数
• 空间复杂度：O(m)，存储地鼠状态

扩展方向

1. 多臂老虎机：当不同洞口出现高分的概率不同时，可用UCB算法动态选择最优洞口
2. 强化学习：用Q-Learning训练击中策略，考虑连击奖励与惩罚
3. 注意力模型：模拟人类视觉注意力，限制AI同时关注的地鼠数量

总结

本文通过泊松过程建模地鼠随机出现，结合对数正态分布描述反应时间，最后用贪心策略实现最优击中决策。核心算法简洁高效，可轻松扩展至更复杂的游戏AI场景。