引言
快艇骰子（Yahtzee）是一款经典的骰子策略游戏，玩家通过三次投掷五枚骰子，根据最终点数组合获取分数。游戏的核心乐趣不仅在于运气，更在于每一次投掷后的决策：保留哪些骰子、重投哪些骰子，才能最大化期望得分。
本文将用Java实现一个完整的最优决策引擎，通过期望动态规划（Expected Value DP）计算每种状态下的最优保留策略，帮助玩家做出数学上最优的选择。
游戏规则与计分体系
快艇骰子共有13个计分类别，每个类别只能使用一次：
- 一点至六点：对应点数之和
- 三条（Three of a Kind）：至少三枚相同，总和计分
- 四条（Four of a Kind）：至少四枚相同，总和计分
- 满堂红（Full House）：三条加一对，固定25分
- 小顺（Small Straight）：四枚连续，固定30分
- 大顺（Large Straight）：五枚连续，固定40分
- 快艇（Yahtzee）：五枚相同，固定50分
- 机会（Chance）：任意五枚之和
核心算法：期望动态规划
状态设计
决策的关键在于：给定当前五枚骰子的点数，以及剩余的投掷次数，决定保留哪些骰子。
我们使用状态压缩表示五枚骰子的分布。由于骰子只有1-6点，可以用一个6维向量 (c1,c2,c3,c4,c5,c6) 表示，其中 ci 是点数为 i 的骰子数量。这个向量可以用一个整数编码（例如六进制或组合编码）。
期望值计算
对于每个状态，我们需要计算两个值：
- 立即得分期望：如果将当前骰子放入最佳可用类别，能得到多少分
- 继续投掷期望：保留某些骰子后重投，最终得分的期望
动态规划递推式：
E(state, rolls_left) = max(
score_now(state), // 立即停止，选择最佳类别
max_subset E(roll(subset), rolls_left-1) // 保留某个子集，继续投掷
)
其中 roll(subset) 表示保留子集后重投剩余骰子得到的所有可能状态及其概率。
最优保留策略
对于五枚骰子，共有 2^5 = 32 种保留子集（包括全不保留和全保留）。对于每个子集，计算重投后的期望得分，选择期望最大的子集。
重投 k 枚骰子会产生 6^k 种等概率结果，需要枚举所有可能并加权平均。
Java实现
import java.util.*;
/**
* 快艇骰子最优决策引擎
* 使用期望动态规划计算每次投掷后的最优保留策略
*/
public class YahtzeeSolver {
// 骰子点数分布的编码：用6位数字表示每个点数的数量
// 例如 [1,2,0,0,0,0] 表示一个1点和两个2点，编码为 120000
// 为简化，使用长度为6的数组作为状态键
// 预计算：所有可能的投掷结果（五枚骰子的所有组合）
private static final List<int[]> ALL_ROLLS = generateAllRolls();
// 动态规划缓存：dp[rollsLeft][stateCode] = 最大期望得分
// 由于状态空间较大，使用HashMap
private final Map<String, Double> memo = new HashMap<>();
// 可用类别掩码：13位二进制，第i位为1表示该类别仍可用
private int availableCategories;
public YahtzeeSolver() {
this.availableCategories = (1 << 13) - 1; // 初始所有类别可用
}
/**
* 生成五枚骰子的所有可能结果（有序）
* 每枚骰子1-6点，共6^5=7776种结果
*/
private static List<int[]> generateAllRolls() {
List<int[]> rolls = new ArrayList<>();
for (int d1 = 1; d1 <= 6; d1++) {
for (int d2 = 1; d2 <= 6; d2++) {
for (int d3 = 1; d3 <= 6; d3++) {
for (int d4 = 1; d4 <= 6; d4++) {
for (int d5 = 1; d5 <= 6; d5++) {
rolls.add(new int[]{d1, d2, d3, d4, d5});
}
}
}
}
}
return rolls;
}
/**
* 将五枚骰子的有序数组转换为点数计数分布
* @param dice 长度为5的数组，每个元素1-6
* @return 长度为6的数组，counts[i]表示点数为(i+1)的骰子数量
*/
public int[] toCounts(int[] dice) {
int[] counts = new int[6];
for (int d : dice) {
counts[d - 1]++;
}
return counts;
}
/**
* 将计数分布编码为字符串，作为HashMap的键
*/
private String encodeCounts(int[] counts) {
StringBuilder sb = new StringBuilder();
for (int c : counts) {
sb.append(c);
}
return sb.toString();
}
/**
* 计算给定骰子点数在指定类别中的得分
* @param dice 五枚骰子的点数
* @param category 类别索引 0-12
* @return 该类别的得分
*/
public int scoreCategory(int[] dice, int category) {
int[] counts = toCounts(dice);
int sum = Arrays.stream(dice).sum();
switch (category) {
case 0: return counts[0] * 1; // 一点
case 1: return counts[1] * 2; // 二点
case 2: return counts[2] * 3; // 三点
case 3: return counts[3] * 4; // 四点
case 4: return counts[4] * 5; // 五点
case 5: return counts[5] * 6; // 六点
case 6: // 三条
for (int c : counts) if (c >= 3) return sum;
return 0;
case 7: // 四条
for (int c : counts) if (c >= 4) return sum;
return 0;
case 8: // 满堂红
boolean hasThree = false, hasTwo = false;
for (int c : counts) {
if (c == 3) hasThree = true;
if (c == 2) hasTwo = true;
}
return (hasThree && hasTwo) ? 25 : 0;
case 9: // 小顺
return hasStraight(counts, 4) ? 30 : 0;
case 10: // 大顺
return hasStraight(counts, 5) ? 40 : 0;
case 11: // 快艇
for (int c : counts) if (c == 5) return 50;
return 0;
case 12: // 机会
return sum;
default: return 0;
}
}
/**
* 检查是否存在长度为len的连续序列
*/
private boolean hasStraight(int[] counts, int len) {
int consecutive = 0;
for (int c : counts) {
if (c > 0) {
consecutive++;
if (consecutive >= len) return true;
} else {
consecutive = 0;
}
}
return false;
}
/**
* 计算当前骰子在所有可用类别中的最佳立即得分
* @param dice 当前骰子
* @return 最佳得分
*/
public int bestImmediateScore(int[] dice) {
int best = 0;
for (int cat = 0; cat < 13; cat++) {
if ((availableCategories & (1 << cat)) != 0) {
best = Math.max(best, scoreCategory(dice, cat));
}
}
return best;
}
/**
* 枚举所有保留子集，计算最优期望
* @param dice 当前五枚骰子
* @param rollsLeft 剩余投掷次数（1或2）
* @return 最优期望得分
*/
public double solveRoll(int[] dice, int rollsLeft) {
if (rollsLeft == 0) {
return bestImmediateScore(dice);
}
String key = rollsLeft + "_" + Arrays.toString(dice) + "_" + availableCategories;
if (memo.containsKey(key)) {
return memo.get(key);
}
// 选项1：立即停止，获得最佳立即得分
double bestScore = bestImmediateScore(dice);
// 选项2：保留某些骰子，继续投掷
// 枚举所有保留子集（用5位二进制掩码表示）
for (int mask = 0; mask < (1 << 5); mask++) {
double expected = computeExpectedForMask(dice, mask, rollsLeft);
bestScore = Math.max(bestScore, expected);
}
memo.put(key, bestScore);
return bestScore;
}
/**
* 计算保留给定掩码对应的骰子后，重投其余骰子的期望得分
* @param dice 当前骰子
* @param mask 保留掩码，第i位为1表示保留第i枚骰子
* @param rollsLeft 剩余投掷次数
*/
private double computeExpectedForMask(int[] dice, int mask, int rollsLeft) {
int keepCount = Integer.bitCount(mask);
int rerollCount = 5 - keepCount;
// 如果全部保留，等同于停止
if (rerollCount == 0) {
return bestImmediateScore(dice);
}
// 枚举所有重投结果：rerollCount枚骰子，每枚1-6点
double totalExpected = 0;
int totalOutcomes = (int) Math.pow(6, rerollCount);
int[] newDice = new int[5];
// 先复制保留的骰子
for (int i = 0; i < 5; i++) {
if ((mask & (1 << i)) != 0) {
newDice[i] = dice[i];
}
}
// 生成所有重投组合
generateRerolls(newDice, mask, 0, rollsLeft - 1, new double[]{0});
// 由于递归返回值难以聚合，改用迭代方式
return iterativeRerollExpectation(dice, mask, rollsLeft);
}
/**
* 迭代计算重投期望
*/
private double iterativeRerollExpectation(int[] dice, int mask, int rollsLeft) {
int rerollCount = 5 - Integer.bitCount(mask);
if (rerollCount == 0) return bestImmediateScore(dice);
int total = (int) Math.pow(6, rerollCount);
double sum = 0;
// 使用计数器生成所有重投组合
int[] counters = new int[rerollCount];
int[] newDice = Arrays.copyOf(dice, 5);
for (int outcome = 0; outcome < total; outcome++) {
// 将outcome转换为rerollCount个1-6的骰子值
int temp = outcome;
int rerollIdx = 0;
for (int i = 0; i < 5; i++) {
if ((mask & (1 << i)) == 0) {
newDice[i] = (temp % 6) + 1;
temp /= 6;
rerollIdx++;
}
}
// 递归计算剩余投掷次数下的最优期望
sum += solveRoll(newDice, rollsLeft - 1);
}
return sum / total;
}
/**
* 获取当前骰子状态下的最优保留建议
* @param dice 当前骰子
* @param rollsLeft 剩余投掷次数
* @return 最优保留掩码和对应期望
*/
public Result getBestAction(int[] dice, int rollsLeft) {
if (rollsLeft == 0) {
return new Result(0, bestImmediateScore(dice), "停止，立即计分");
}
double bestScore = bestImmediateScore(dice);
int bestMask = (1 << 5) - 1; // 全保留（停止）
String bestAction = "停止，立即计分，期望得分: " + bestScore;
for (int mask = 0; mask < (1 << 5); mask++) {
double expected = iterativeRerollExpectation(dice, mask, rollsLeft);
if (expected > bestScore + 1e-9) {
bestScore = expected;
bestMask = mask;
bestAction = String.format("保留掩码 %d，重投后期望得分: %.2f", mask, expected);
}
}
return new Result(bestMask, bestScore, bestAction);
}
/**
* 辅助类：存储决策结果
*/
public static class Result {
public final int mask;
public final double expectedScore;
public final String action;
public Result(int mask, double expectedScore, String action) {
this.mask = mask;
this.expectedScore = expectedScore;
this.action = action;
}
@Override
public String toString() {
return String.format("最优行动: %s, 期望得分: %.2f", action, expectedScore);
}
}
/**
* 运行示例：模拟一次投掷后的决策
*/
public static void main(String[] args) {
YahtzeeSolver solver = new YahtzeeSolver();
Random rand = new Random(42);
// 模拟第一次投掷
int[] firstRoll = new int[5];
for (int i = 0; i < 5; i++) {
firstRoll[i] = rand.nextInt(6) + 1;
}
System.out.println("第一次投掷: " + Arrays.toString(firstRoll));
Result action1 = solver.getBestAction(firstRoll, 2);
System.out.println(action1);
// 模拟第二次投掷（根据最优策略保留）
int[] secondRoll = simulateReroll(firstRoll, action1.mask, rand);
System.out.println("\n第二次投掷: " + Arrays.toString(secondRoll));
Result action2 = solver.getBestAction(secondRoll, 1);
System.out.println(action2);
// 模拟第三次投掷
int[] thirdRoll = simulateReroll(secondRoll, action2.mask, rand);
System.out.println("\n第三次投掷: " + Arrays.toString(thirdRoll));
int finalScore = solver.bestImmediateScore(thirdRoll);
System.out.println("最终最佳立即得分: " + finalScore);
}
/**
* 根据保留掩码模拟重投
*/
private static int[] simulateReroll(int[] dice, int mask, Random rand) {
int[] result = Arrays.copyOf(dice, 5);
for (int i = 0; i < 5; i++) {
if ((mask & (1 << i)) == 0) {
result[i] = rand.nextInt(6) + 1;
}
}
return result;
}
}
复杂度分析
- 状态空间：五枚骰子的计数分布可用组合数学计算，共有
C(5+6-1, 5) = 252种不同的计数状态。但由于骰子是有序的，实际需要考虑的有序状态为6^5 = 7776种。 - 子集枚举：每次决策需要枚举
2^5 = 32种保留子集。 - 重投枚举：保留
k枚骰子需要枚举6^(5-k)种重投结果。 - 时间复杂度：单次决策的最坏时间复杂度为
O(32 × 6^5) ≈ O(250,000)，在现代计算机上可在毫秒级完成。 - 空间复杂度：
O(6^5 × 投掷次数)用于记忆化存储。
优化方向
- 对称性剪枝：骰子点数的排列是对称的，可以通过排序和去重大幅减少状态数。
- 预计算表：在游戏开始前预计算所有状态的最优决策，实现O(1)查询。
- 上界剪枝：在枚举子集时，利用得分上界提前剪枝不可能超过当前最优解的分支。
- 类别可用性扩展：完整版本需要考虑13个类别的使用组合（
2^13 = 8192种可用性状态），可通过分层DP或蒙特卡洛近似求解。
总结
快艇骰子的最优决策问题完美展示了期望动态规划在实际游戏中的应用。通过将随机投掷建模为概率分布，将保留决策建模为子集选择，我们能够用数学方法找到每一步的最优策略。虽然完整版需要考虑13个类别的全局规划（状态空间更大），但本文的单轮最优决策引擎已经能够为玩家提供强有力的决策支持。
理解这个算法的关键在于：在存在随机性的决策问题中，期望是连接当前决策与未来收益的最佳桥梁。无论是游戏还是现实中的资源分配，期望动态规划都是一种强大的分析工具。
