引言
抓石子是中国民间流传已久的传统儿童游戏。游戏规则简单却充满技巧：玩家将若干颗石子撒在地上，选定一颗”目标石子”抛向空中，在目标石子尚未落地的短暂时间内，迅速从地上抓取其他石子，然后接住落下的目标石子。抓取的石子越多得分越高，但如果目标石子落地或碰到其他石子则失败。这一游戏的核心挑战在于时间压力下的最优决策：面对不同分布的石子，如何在极短的反应时间内制定最优抓取顺序，最大化得分同时保证成功率？本文将用Java实现抓石子游戏的反应时间建模系统，讲解概率分布拟合与动态规划最优抓取序列算法。
算法原理
反应时间概率模型
人类反应时间服从近似对数正态分布或Gamma分布。设目标石子在空中的停留时间为 $T_{air}$，玩家的反应时间为 $T_{react}$，则可用于抓取的净时间为：
$$T_{grab} = T_{air} – T_{react}$$
抓取 $k$ 颗石子所需时间可建模为：
$$T_{need}(k) = k \cdot t_{single} + t_{handmove} \cdot d_{max}$$
其中 $t_{single}$ 为抓取单颗石子的平均时间，$t_{handmove}$ 为手部移动单位距离所需时间，$d_{max}$ 为最远两颗被抓取石子之间的距离。
最优抓取序列的动态规划
将地上的石子视为平面上的点集，问题转化为：在净时间 $T_{grab}$ 内，选择一条从手起始位置出发、经过若干石子的路径，使得抓取的石子数量最多，且总行程时间不超过限制。
这是一个带时间约束的旅行商问题变体（Orienteering Problem），对于小规模数据可用动态规划求解。状态定义为 $dp[mask][i]$：表示已抓取石子集合为 $mask$ 且最后抓取的是第 $i$ 颗石子时的最小总耗时。通过状态转移寻找在时限内能抓取最多石子的方案。
Java实现
1. 基础数据结构与物理模型
import java.util.*;
/**
* 石子：表示地面上的单颗石子
*/
public class Pebble {
public final int id;
public final double x;
public final double y;
public final double weight; // 石子重量（影响抓取难度）
public Pebble(int id, double x, double y, double weight) {
this.id = id;
this.x = x;
this.y = y;
this.weight = weight;
}
/** 计算到另一颗石子的欧几里得距离 */
public double distanceTo(Pebble other) {
return Math.hypot(this.x - other.x, this.y - other.y);
}
@Override
public String toString() {
return String.format("Pebble%d(%.1f,%.1f)", id, x, y);
}
}
/**
* 反应时间模型：基于Gamma分布模拟玩家反应能力
*/
public class ReactionTimeModel {
private final double shape; // Gamma分布形状参数
private final double scale; // Gamma分布尺度参数
private final Random random;
public ReactionTimeModel(double shape, double scale, long seed) {
this.shape = shape;
this.scale = scale;
this.random = new Random(seed);
}
/**
* 生成一次反应时间样本（毫秒）
* 使用Marsaglia-Tsang方法生成Gamma分布随机数
*/
public double sampleReactionTime() {
if (shape < 1) {
// 对于shape < 1，使用指数变换
return sampleGamma(shape + 1, scale) * Math.pow(random.nextDouble(), 1.0 / shape);
}
// Marsaglia-Tsang方法
double d = shape - 1.0 / 3.0;
double c = 1.0 / Math.sqrt(9.0 * d);
while (true) {
double x = random.nextGaussian();
double v = 1.0 + c * x;
if (v <= 0) continue;
v = v * v * v;
double u = random.nextDouble();
if (u < 1.0 - 0.0331 * x * x * x * x) return d * v * scale;
if (Math.log(u) < 0.5 * x * x + d * (1.0 - v + Math.log(v))) return d * v * scale;
}
}
/**
* 计算抓取单颗石子的平均耗时（毫秒）
* @param pebble 目标石子
* @param handSpeed 手部移动速度 (cm/ms)
* @return 抓取该石子所需时间
*/
public double grabTime(Pebble pebble, double handSpeed) {
double baseTime = 80 + pebble.weight * 20; // 基础抓取时间 + 重量修正
return baseTime;
}
/**
* 计算手部在两点间移动所需时间
*/
public double moveTime(Pebble from, Pebble to, double handSpeed) {
double dist = from.distanceTo(to);
return dist / handSpeed;
}
}
2. 动态规划求解器
/**
* 抓石子动态规划求解器
* 状态：dp[mask][i] = 抓取集合mask且最后抓i的最小耗时
*/
public class PebbleGrabSolver {
private final List<Pebble> pebbles;
private final ReactionTimeModel reactionModel;
private final double handSpeed; // 手部移动速度 (单位/ms)
private final double airTime; // 目标石子在空中停留时间 (ms)
private final Pebble handStart; // 手起始位置
public PebbleGrabSolver(List<Pebble> pebbles, ReactionTimeModel reactionModel,
double handSpeed, double airTime, Pebble handStart) {
this.pebbles = pebbles;
this.reactionModel = reactionModel;
this.handSpeed = handSpeed;
this.airTime = airTime;
this.handStart = handStart;
}
/**
* 使用动态规划求解最优抓取序列
* @return 最优抓取方案 [石子索引列表, 总耗时, 预期成功率]
*/
public GrabResult solve() {
int n = pebbles.size();
if (n == 0) return new GrabResult(new ArrayList<>(), 0, 1.0);
int totalStates = 1 << n;
double[][] dp = new double[totalStates][n];
int[][] parent = new int[totalStates][n];
for (double[] row : dp) Arrays.fill(row, Double.MAX_VALUE);
for (int[] row : parent) Arrays.fill(row, -1);
// 初始化：从手起始位置直接抓取某颗石子
for (int i = 0; i < n; i++) {
double time = reactionModel.moveTime(handStart, pebbles.get(i), handSpeed)
+ reactionModel.grabTime(pebbles.get(i), handSpeed);
dp[1 << i][i] = time;
}
// 状态转移
for (int mask = 1; mask < totalStates; mask++) {
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue; // last不在mask中
if (dp[mask][last] == Double.MAX_VALUE) continue;
for (int next = 0; next < n; next++) {
if ((mask & (1 << next)) != 0) continue; // next已被抓取
int newMask = mask | (1 << next);
double moveTime = reactionModel.moveTime(pebbles.get(last), pebbles.get(next), handSpeed);
double grabTime = reactionModel.grabTime(pebbles.get(next), handSpeed);
double newTime = dp[mask][last] + moveTime + grabTime;
if (newTime < dp[newMask][next]) {
dp[newMask][next] = newTime;
parent[newMask][next] = last;
}
}
}
}
// 找到在airTime内能抓取最多石子的方案
int bestMask = 0;
int bestLast = -1;
int maxCount = 0;
double bestTime = Double.MAX_VALUE;
// 模拟多次反应时间，计算期望成功率
double avgReactTime = 0;
int samples = 1000;
for (int s = 0; s < samples; s++) {
avgReactTime += reactionModel.sampleReactionTime();
}
avgReactTime /= samples;
double netTime = airTime - avgReactTime;
for (int mask = 1; mask < totalStates; mask++) {
int count = Integer.bitCount(mask);
if (count < maxCount) continue;
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue;
if (dp[mask][last] == Double.MAX_VALUE) continue;
if (count > maxCount || (count == maxCount && dp[mask][last] < bestTime)) {
if (dp[mask][last] <= netTime) {
maxCount = count;
bestTime = dp[mask][last];
bestMask = mask;
bestLast = last;
}
}
}
}
// 回溯还原最优序列
List<Integer> sequence = new ArrayList<>();
if (bestLast >= 0) {
int mask = bestMask;
int last = bestLast;
while (last >= 0) {
sequence.add(last);
int prev = parent[mask][last];
mask ^= (1 << last);
last = prev;
}
Collections.reverse(sequence);
}
// 计算成功率：若总耗时远小于净时间则成功率高
double successRate = bestTime <= netTime * 0.7 ? 0.95 :
bestTime <= netTime ? 0.85 : 0.5;
return new GrabResult(sequence, bestTime, successRate);
}
/** 结果封装 */
public static class GrabResult {
public final List<Integer> sequence;
public final double totalTime;
public final double successRate;
public GrabResult(List<Integer> sequence, double totalTime, double successRate) {
this.sequence = sequence;
this.totalTime = totalTime;
this.successRate = successRate;
}
}
}
3. 游戏主程序
/**
* 抓石子游戏主程序
*/
public class PebbleGameDemo {
public static void main(String[] args) {
Random random = new Random(42);
int n = 8; // 地上8颗石子
// 生成随机石子分布
List<Pebble> pebbles = new ArrayList<>();
System.out.println("=== 石子分布 ===");
for (int i = 0; i < n; i++) {
double x = random.nextDouble() * 20;
double y = random.nextDouble() * 15;
double weight = 0.5 + random.nextDouble() * 1.5;
pebbles.add(new Pebble(i, x, y, weight));
System.out.printf(" %s 重量=%.2f%n", pebbles.get(i), weight);
}
// 游戏参数
Pebble handStart = new Pebble(-1, 10, 7.5, 0); // 手起始在中心区域
double handSpeed = 0.08; // 手部移动速度 0.08 单位/ms
double airTime = 800; // 目标石子在空中停留800ms
ReactionTimeModel model = new ReactionTimeModel(3.0, 60.0, 42);
System.out.printf("%n=== 游戏参数 ===%n");
System.out.printf("手部起始位置: (%.1f, %.1f)%n", handStart.x, handStart.y);
System.out.printf("手部移动速度: %.3f 单位/ms%n", handSpeed);
System.out.printf("目标石子空中时间: %.0f ms%n", airTime);
// 反应时间统计
System.out.println("\n=== 反应时间模拟（1000次采样）===");
double sum = 0, min = Double.MAX_VALUE, max = 0;
for (int i = 0; i < 1000; i++) {
double t = model.sampleReactionTime();
sum += t;
min = Math.min(min, t);
max = Math.max(max, t);
}
System.out.printf("平均反应时间: %.1f ms%n", sum / 1000);
System.out.printf("最快反应时间: %.1f ms%n", min);
System.out.printf("最慢反应时间: %.1f ms%n", max);
// 求解最优抓取序列
PebbleGrabSolver solver = new PebbleGrabSolver(pebbles, model, handSpeed, airTime, handStart);
PebbleGrabSolver.GrabResult result = solver.solve();
System.out.println("\n=== 最优抓取方案 ===");
System.out.printf("抓取数量: %d 颗%n", result.sequence.size());
System.out.printf("总耗时: %.1f ms%n", result.totalTime);
System.out.printf("预期成功率: %.1f%%%n", result.successRate * 100);
if (!result.sequence.isEmpty()) {
System.out.println("\n抓取顺序:");
double totalDist = handStart.distanceTo(pebbles.get(result.sequence.get(0)));
System.out.printf(" 起点 -> %s (距离 %.2f)%n",
pebbles.get(result.sequence.get(0)), totalDist);
for (int i = 1; i < result.sequence.size(); i++) {
Pebble from = pebbles.get(result.sequence.get(i - 1));
Pebble to = pebbles.get(result.sequence.get(i));
double dist = from.distanceTo(to);
totalDist += dist;
System.out.printf(" %s -> %s (距离 %.2f)%n", from, to, dist);
}
System.out.printf("总移动距离: %.2f%n", totalDist);
}
// 不同空中时间下的表现分析
System.out.println("\n=== 不同空中时间下的最优抓取数 ===");
System.out.printf("%-12s %-12s %-12s %-10s%n", "空中时间", "抓取数量", "总耗时", "成功率");
System.out.println("-".repeat(50));
for (double t = 400; t <= 1200; t += 100) {
PebbleGrabSolver s = new PebbleGrabSolver(pebbles, model, handSpeed, t, handStart);
PebbleGrabSolver.GrabResult r = s.solve();
System.out.printf("%-12.0f %-12d %-12.1f %-10.1f%%%n",
t, r.sequence.size(), r.totalTime, r.successRate * 100);
}
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 反应时间采样 | $O(1)$ | $O(1)$ | Gamma分布随机数生成 |
| 距离计算 | $O(1)$ | $O(1)$ | 欧几里得距离 |
| 动态规划求解 | $O(n^2 \cdot 2^n)$ | $O(n \cdot 2^n)$ | $n$ 为石子数量 |
| 回溯还原序列 | $O(n)$ | $O(n)$ | 按parent数组回溯 |
由于状态数为 $2^n \cdot n$，该DP方法适用于 $n \leq 15$ 的场景。对于更多石子，需采用启发式算法（如最近邻贪心、2-OPT局部搜索）近似求解。
扩展思考
- 多目标优化：除抓取数量外，可引入”抓取总重量”或”抓取颜色组合得分”等目标，将问题扩展为多目标旅行商问题。
- 在线决策：实际游戏中玩家无法提前看到所有石子分布。引入部分可观察马尔可夫决策过程（POMDP），在信息不完整时做出最优决策。
- 协作模式：多人同时抓取时，引入博弈论模型，避免手部碰撞并最大化团队总得分。
总结
本文通过Java实现了抓石子游戏的反应时间建模与最优抓取序列求解，核心要点包括：
- Gamma分布精确建模人类反应时间的随机性，使模拟更贴近真实场景
- 动态规划枚举所有可能的抓取子集和结束位置，在时限约束下找到石子数最多的最优路径
- 成功率评估结合反应时间分布与动作耗时，量化评估方案的可行性
抓石子将生理反应特性与组合优化巧妙结合，是理解概率建模和状态压缩动态规划的生动案例。通过调整分布参数和游戏难度，还能进一步探索人机交互中的决策边界。
