骰子游戏是一类跨越文化与时代的经典概率博弈，从简单的”猜大小”到策略性极强的”快艇骰子”（Yahtzee），骰子的每一次翻滚都蕴含着丰富的决策空间。在允许保留部分骰子并重新投掷的规则下，玩家面临的核心问题是：面对当前骰面，应该保留哪些骰子、重新投掷哪些骰子，才能最大化期望得分？本文将使用Java实现一个骰子游戏AI决策系统，运用动态规划（Dynamic Programming）与期望值递归评估，求解每一轮的最优保留策略。
游戏规则与决策空间
以经典的”快艇骰子”变体为例，每轮游戏流程如下：
- 初始投掷：同时掷出5颗六面骰
- 保留决策：观察骰面后，可选择保留任意子集的骰子（也可全部保留或全部重投）
- 二次投掷：将未保留的骰子重新投掷
- 再次保留决策：观察新骰面后，再次选择保留子集
- 三次投掷：最后机会，投掷未保留的骰子
- 计分：根据最终5颗骰面的组合，在13个计分类别中选择一个得分
决策的复杂性在于：每次保留选择不仅影响当前可见的得分机会，还会改变后续投掷的概率分布。动态规划正是解决这种”多阶段决策最优性”问题的利器。
状态空间定义
动态规划的状态由两个要素构成：
- 当前骰面多重集：5颗骰子的面值分布，可用长度为6的计数数组表示
- 剩余重投次数：0、1或2次
对于5颗六面骰，其面值分布可编码为 (c1,c2,c3,c4,c5,c6)，其中 ci 表示面值为 i 的骰子数量，满足 Σci = 5。这种编码将状态空间从 6^5 = 7776 压缩至 C(5+6-1, 5) = 252 种分布。
import java.util.*;
/**
* 骰子游戏AI：基于动态规划的最优保留策略求解器
* 以快艇骰子变体为模型，支持任意骰子数量与面数
*/
public class DiceGameAI {
private static final int DICE_SIDES = 6;
private static final int NUM_DICE = 5;
private static final int MAX_ROLLS = 3;
// 计分类别及其得分函数
interface ScoringCategory {
String getName();
int score(int[] diceCounts);
}
// 上节类别（1-6点）
static class UpperCategory implements ScoringCategory {
int targetFace;
String name;
UpperCategory(int face) {
this.targetFace = face;
this.name = face + "点";
}
public String getName() { return name; }
public int score(int[] counts) {
return counts[targetFace - 1] * targetFace;
}
}
// 同花（全部相同）
static class YahtzeeCategory implements ScoringCategory {
public String getName() { return "同花"; }
public int score(int[] counts) {
for (int c : counts) if (c == NUM_DICE) return 50;
return 0;
}
}
// 四条
static class FourOfAKind implements ScoringCategory {
public String getName() { return "四条"; }
public int score(int[] counts) {
for (int c : counts) if (c >= 4) {
int sum = 0;
for (int i = 0; i < DICE_SIDES; i++) sum += counts[i] * (i + 1);
return sum;
}
return 0;
}
}
// 葫芦（三条+一对）
static class FullHouse implements ScoringCategory {
public String getName() { return "葫芦"; }
public int score(int[] counts) {
boolean hasThree = false, hasTwo = false;
for (int c : counts) {
if (c == 3) hasThree = true;
if (c == 2) hasTwo = true;
}
return (hasThree && hasTwo) ? 25 : 0;
}
}
// 小顺（4连）
static class SmallStraight implements ScoringCategory {
public String getName() { return "小顺"; }
public int score(int[] counts) {
String pattern = "";
for (int i = 0; i < DICE_SIDES; i++) pattern += (counts[i] > 0 ? "1" : "0");
return (pattern.contains("1111")) ? 30 : 0;
}
}
// 大顺（5连）
static class LargeStraight implements ScoringCategory {
public String getName() { return "大顺"; }
public int score(int[] counts) {
String pattern = "";
for (int i = 0; i < DICE_SIDES; i++) pattern += (counts[i] > 0 ? "1" : "0");
return (pattern.contains("11111")) ? 40 : 0;
}
}
// 机会（总和）
static class Chance implements ScoringCategory {
public String getName() { return "机会"; }
public int score(int[] counts) {
int sum = 0;
for (int i = 0; i < DICE_SIDES; i++) sum += counts[i] * (i + 1);
return sum;
}
}
private List<ScoringCategory> categories;
private Map<String, Double> memo; // 记忆化缓存
private Random random;
public DiceGameAI() {
this.random = new Random();
this.memo = new HashMap<>();
initCategories();
}
private void initCategories() {
categories = new ArrayList<>();
for (int i = 1; i <= 6; i++) categories.add(new UpperCategory(i));
categories.add(new YahtzeeCategory());
categories.add(new FourOfAKind());
categories.add(new FullHouse());
categories.add(new SmallStraight());
categories.add(new LargeStraight());
categories.add(new Chance());
}
/** 将骰子列表转换为计数数组 */
int[] toCounts(List<Integer> dice) {
int[] counts = new int[DICE_SIDES];
for (int d : dice) counts[d - 1]++;
return counts;
}
/** 生成所有可能的保留子集（从5颗骰子中选择保留哪些） */
List<List<Integer>> generateKeepSubsets(List<Integer> currentDice) {
List<List<Integer>> subsets = new ArrayList<>();
int n = currentDice.size();
// 枚举所有2^n个子集
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> keep = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
keep.add(currentDice.get(i));
}
}
subsets.add(keep);
}
return subsets;
}
/**
* 计算给定保留决策下的期望最大得分
* @param keptDice 已保留的骰子
* @param rollsLeft 剩余投掷次数
* @return 期望得分
*/
double expectedValue(List<Integer> keptDice, int rollsLeft) {
String key = rollsLeft + ":" + keptDice.toString();
if (memo.containsKey(key)) return memo.get(key);
int keptCount = keptDice.size();
int rerollCount = NUM_DICE - keptCount;
if (rollsLeft == 0 || rerollCount == 0) {
// 无剩余投掷，直接计算当前最优计分
int[] counts = toCounts(keptDice);
double best = 0;
for (ScoringCategory cat : categories) {
best = Math.max(best, cat.score(counts));
}
memo.put(key, best);
return best;
}
// 枚举rerollCount颗骰子的所有可能结果（6^rerollCount种）
double totalEV = 0;
int totalOutcomes = (int) Math.pow(DICE_SIDES, rerollCount);
// 使用递归生成所有可能的补充骰子组合
List<Integer> outcomes = new ArrayList<>();
totalEV = enumerateRerolls(keptDice, rerollCount, 0, rollsLeft);
double ev = totalEV / totalOutcomes;
memo.put(key, ev);
return ev;
}
private double enumerateRerolls(List<Integer> keptDice, int rerollCount,
int currentDepth, int rollsLeft) {
if (currentDepth == rerollCount) {
// 所有补充骰子已确定，做保留决策
return optimalKeepDecision(keptDice, rollsLeft - 1);
}
double sum = 0;
for (int face = 1; face <= DICE_SIDES; face++) {
List<Integer> extended = new ArrayList<>(keptDice);
extended.add(face);
sum += enumerateRerolls(extended, rerollCount, currentDepth + 1, rollsLeft);
}
return sum;
}
/**
* 最优保留决策：对当前骰面，选择保留哪个子集使期望最大
*/
double optimalKeepDecision(List<Integer> currentDice, int rollsLeft) {
double bestEV = 0;
List<Integer> bestKeep = null;
// 枚举所有保留子集
List<List<Integer>> subsets = generateKeepSubsets(currentDice);
for (List<Integer> keep : subsets) {
double ev = expectedValue(keep, rollsLeft);
if (ev > bestEV) {
bestEV = ev;
bestKeep = keep;
}
}
return bestEV;
}
/**
* 对外接口：给定当前骰面，返回最优保留策略建议
*/
public KeepAdvice getAdvice(List<Integer> currentDice, int rollsLeft) {
double bestEV = 0;
List<Integer> bestKeep = null;
List<List<Integer>> subsets = generateKeepSubsets(currentDice);
for (List<Integer> keep : subsets) {
double ev = expectedValue(keep, rollsLeft);
if (ev > bestEV) {
bestEV = ev;
bestKeep = keep;
}
}
// 计算应重新投掷的骰子
List<Integer> reroll = new ArrayList<>(currentDice);
for (int k : bestKeep) {
reroll.remove(Integer.valueOf(k));
}
return new KeepAdvice(bestKeep, reroll, bestEV);
}
static class KeepAdvice {
List<Integer> keep;
List<Integer> reroll;
double expectedScore;
KeepAdvice(List<Integer> keep, List<Integer> reroll, double ev) {
this.keep = keep;
this.reroll = reroll;
this.expectedScore = ev;
}
@Override
public String toString() {
return String.format("保留: %s, 重投: %s, 期望得分: %.2f", keep, reroll, expectedScore);
}
}
/** 随机投掷n颗骰子 */
public List<Integer> rollDice(int n) {
List<Integer> dice = new ArrayList<>();
for (int i = 0; i < n; i++) dice.add(random.nextInt(DICE_SIDES) + 1);
return dice;
}
/** 模拟完整一轮游戏，使用AI策略 */
public int playRoundWithAI() {
List<Integer> dice = rollDice(NUM_DICE);
System.out.println("初始投掷: " + dice);
// 第一次保留决策
KeepAdvice advice1 = getAdvice(dice, 2);
System.out.println(" -> " + advice1);
// 二次投掷
List<Integer> afterRoll2 = new ArrayList<>(advice1.keep);
afterRoll2.addAll(rollDice(advice1.reroll.size()));
System.out.println("二次投掷: " + afterRoll2);
// 第二次保留决策
KeepAdvice advice2 = getAdvice(afterRoll2, 1);
System.out.println(" -> " + advice2);
// 三次投掷
List<Integer> afterRoll3 = new ArrayList<>(advice2.keep);
afterRoll3.addAll(rollDice(advice2.reroll.size()));
System.out.println("最终骰面: " + afterRoll3);
// 选择最优计分类别
int[] counts = toCounts(afterRoll3);
int bestScore = 0;
String bestCat = "";
for (ScoringCategory cat : categories) {
int s = cat.score(counts);
if (s > bestScore) {
bestScore = s;
bestCat = cat.getName();
}
}
System.out.println(" 选择类别 [" + bestCat + "] 得分: " + bestScore);
return bestScore;
}
public static void main(String[] args) {
DiceGameAI ai = new DiceGameAI();
System.out.println("=== 骰子游戏动态规划最优策略 ===\n");
// 演示1：给定具体骰面，输出最优保留策略
System.out.println("【示例分析】当前骰面: [1, 1, 2, 3, 4]");
List<Integer> example = Arrays.asList(1, 1, 2, 3, 4);
KeepAdvice advice = ai.getAdvice(example, 2);
System.out.println("最优策略: " + advice);
System.out.println();
// 演示2：完整AI对局
System.out.println("【AI对局演示】");
int score = ai.playRoundWithAI();
System.out.println("\n本轮最终得分: " + score);
// 演示3：统计AI长期平均得分
System.out.println("\n【长期性能测试】模拟1000轮...");
long totalScore = 0;
for (int i = 0; i < 1000; i++) {
// 每轮需要新的AI实例或清空缓存
DiceGameAI roundAI = new DiceGameAI();
List<Integer> dice = roundAI.rollDice(NUM_DICE);
KeepAdvice a1 = roundAI.getAdvice(dice, 2);
List<Integer> d2 = new ArrayList<>(a1.keep);
d2.addAll(roundAI.rollDice(a1.reroll.size()));
KeepAdvice a2 = roundAI.getAdvice(d2, 1);
List<Integer> d3 = new ArrayList<>(a2.keep);
d3.addAll(roundAI.rollDice(a2.reroll.size()));
int[] counts = roundAI.toCounts(d3);
int best = 0;
for (ScoringCategory cat : roundAI.categories) {
best = Math.max(best, cat.score(counts));
}
totalScore += best;
}
System.out.printf("1000轮平均得分: %.2f\n", totalScore / 1000.0);
}
}
动态规划最优性原理
骰子游戏的最优保留问题满足贝尔曼最优性原理：无论之前做出了什么决策，剩余的子问题仍然必须是最优的。这一性质保证了动态规划的正确性。
状态压缩技巧
原始状态空间为 6^5 = 7776 种骰面组合 × 3 次投掷 = 23328 个状态。通过将骰面排序后编码为计数数组 (c1,c2,c3,c4,c5,c6)，状态空间压缩至 252 种分布 × 3 = 756 个状态。进一步地，由于同面值的骰子不可区分，保留决策的枚举量从 2^5 = 32 个子集降至基于分布的少量有意义选择。
期望值递归的核心逻辑
对于每个状态 (counts, rollsLeft)，其期望值计算遵循：
$$EV(counts, k) = \max_{keep \subseteq dice} \frac{1}{6^{|reroll|}} \sum_{all\ reroll\ outcomes} EV(newCounts, k-1)$$
即：尝试所有保留子集，对每种保留方案，枚举所有补充骰子的可能结果，取平均值后选择期望值最大的保留方案。
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单状态期望值计算 | O(2^D × S^(D-K)) | O(1) |
| 完整状态空间求解 | O(States × 2^D × S^D) | O(States) |
| 单轮AI决策 | O(2^D × S^D) | O(States) |
其中 D 为骰子数量，S 为面数，K 为保留数量，States 为压缩后的状态数。对于标准5骰6面配置，States ≈ 252，整体求解在普通计算机上可在秒级完成。
从骰子游戏到通用序贯决策
骰子游戏的最优策略框架可推广至更广泛的序贯决策问题：
- 医疗决策：根据检查结果决定下一步检测项目
- 投资组合：根据市场状态动态调整持仓
- 游戏AI：卡牌游戏中的保留与打出决策
- 资源调度：根据当前负载决定任务分配
这些问题的共同特征是：决策具有多阶段性、每阶段面临不确定性、目标为最大化长期期望收益。掌握动态规划求解这类问题的思路，就掌握了处理现实世界复杂决策的算法武器。
通过本文的实现，读者不仅获得了一个能给出最优保留建议的骰子游戏AI，更重要的是理解了动态规划如何将”指数级爆炸的决策树”转化为”可计算的多阶段优化问题”。这正是算法之美——用结构化的思维驯服看似混乱的随机性。
