引言
Yahtzee（快艇骰子）是一款风靡全球的骰子策略游戏。玩家每轮可投掷5颗骰子，最多保留部分骰子后重投两次，最终将骰子组合填入13个计分格之一。每个格子只能使用一次，游戏目标是最大化总分。本文用Java实现Yahtzee的AI决策核心，通过期望动态规划计算每轮的最优保留策略。
游戏规则与计分模型
Yahtzee共有13个计分类别：
– 上部（1~6点）：对应点数的骰子之和；
– 下部：三条、四条、满堂红（25分）、小顺子（30分）、大顺子（40分）、Yahtzee（50分）、机会（所有骰子之和）。
若上部总分≥63，额外奖励35分。每轮玩家可选择保留任意 subset 的骰子，重投其余骰子0~2次，最后选择计分格。
期望动态规划建模
将决策过程建模为期望最大化问题。定义状态为：
– 当前5颗骰子的面值组合（多重集合）；
– 剩余重投次数（0~2）；
– 已被占用的计分格集合。
对于每次保留决策，枚举所有 2^5 = 32 种保留子集，计算重投后期望得分，选择期望最大的保留方案。
Java实现
import java.util.*;
/**
* Yahtzee AI：期望动态规划与最优骰子保留策略
*/
public class YahtzeeAI {
// 13个计分格的索引常量
static final int ONES = 0, TWOS = 1, THREES = 2, FOURS = 3, FIVES = 4, SIXES = 5;
static final int THREE_KIND = 6, FOUR_KIND = 7, FULL_HOUSE = 8;
static final int SMALL_STRAIGHT = 9, LARGE_STRAIGHT = 10, YAHTZEE = 11, CHANCE = 12;
static final int CATEGORIES = 13;
/**
* 将5颗骰子排序后的结果编码为状态（每位0~6，共6^5=7776种）
*/
static int encodeDice(int[] dice) {
Arrays.sort(dice);
int code = 0;
for (int d : dice) {
code = code * 7 + d; // d 范围 1~6
}
return code;
}
/**
* 解码骰子状态
*/
static int[] decodeDice(int code) {
int[] dice = new int[5];
for (int i = 4; i >= 0; i--) {
dice[i] = code % 7;
code /= 7;
}
return dice;
}
/**
* 计算某组骰子在指定类别下的得分
*/
static int scoreCategory(int[] dice, int cat) {
int[] count = new int[7];
int sum = 0;
for (int d : dice) { count[d]++; sum += d; }
switch (cat) {
case ONES: return count[1] * 1;
case TWOS: return count[2] * 2;
case THREES: return count[3] * 3;
case FOURS: return count[4] * 4;
case FIVES: return count[5] * 5;
case SIXES: return count[6] * 6;
case THREE_KIND:
for (int c : count) if (c >= 3) return sum;
return 0;
case FOUR_KIND:
for (int c : count) if (c >= 4) return sum;
return 0;
case FULL_HOUSE:
boolean has3 = false, has2 = false;
for (int c : count) {
if (c == 3) has3 = true;
if (c == 2) has2 = true;
}
return (has3 && has2) ? 25 : 0;
case SMALL_STRAIGHT:
// 检查是否存在至少4个连续不同点数
int mask = 0;
for (int d : dice) mask |= 1 << d;
int[] patterns = {0b11110, 0b11101, 0b11011, 0b10111, 0b01111};
for (int p : patterns) {
if ((mask & p) == p) return 30;
}
return 0;
case LARGE_STRAIGHT:
int m = 0;
for (int d : dice) m |= 1 << d;
return (m == 0b111110 || m == 0b011111) ? 40 : 0;
case YAHTZEE:
for (int c : count) if (c == 5) return 50;
return 0;
case CHANCE:
return sum;
default: return 0;
}
}
/**
* 枚举所有重投结果并计算期望得分
* @param keepMask 5位掩码，第i位为1表示保留第i颗骰子
*/
static double expectedScore(int[] dice, int keepMask, int rollsLeft,
Map<String, Double> memo) {
if (rollsLeft == 0) {
return bestImmediateScore(dice);
}
String key = encodeDice(dice) + "_" + keepMask + "_" + rollsLeft;
if (memo.containsKey(key)) return memo.get(key);
// 确定需要重投的骰子数量
int rerollCount = 5 - Integer.bitCount(keepMask);
if (rerollCount == 0) {
double best = bestImmediateScore(dice);
memo.put(key, best);
return best;
}
// 枚举所有重投结果（rerollCount颗骰子，每颗1~6）
double total = 0;
int[] kept = new int[5];
int ki = 0;
for (int i = 0; i < 5; i++) {
if ((keepMask & (1 << i)) != 0) {
kept[ki++] = dice[i];
}
}
int outcomes = (int) Math.pow(6, rerollCount);
for (int outcome = 0; outcome < outcomes; outcome++) {
int[] newDice = new int[5];
System.arraycopy(kept, 0, newDice, 0, ki);
int temp = outcome;
for (int i = ki; i < 5; i++) {
newDice[i] = (temp % 6) + 1;
temp /= 6;
}
// 下一轮决策：在所有32种保留方案中选择最优
double bestNext = 0;
for (int nextMask = 0; nextMask < 32; nextMask++) {
double ev = expectedScore(newDice, nextMask, rollsLeft - 1, memo);
if (ev > bestNext) bestNext = ev;
}
total += bestNext;
}
double avg = total / outcomes;
memo.put(key, avg);
return avg;
}
/**
* 计算当前骰子在所有类别中的最大即时得分（简化版，不考虑全局状态）
*/
static double bestImmediateScore(int[] dice) {
int best = 0;
for (int cat = 0; cat < CATEGORIES; cat++) {
int s = scoreCategory(dice, cat);
if (s > best) best = s;
}
return best;
}
/**
* 给定当前骰子，计算最优保留掩码（用于第1次或第2次投掷后）
*/
static int findBestKeepMask(int[] dice, int rollsLeft) {
double bestEv = -1;
int bestMask = 0;
Map<String, Double> memo = new HashMap<>();
for (int mask = 0; mask < 32; mask++) {
double ev = expectedScore(dice.clone(), mask, rollsLeft, memo);
if (ev > bestEv) {
bestEv = ev;
bestMask = mask;
}
}
return bestMask;
}
/**
* 模拟完整的一轮：掷骰子 -> 决策保留 -> 重投 -> 再决策 -> 最终计分
*/
public static void playRound() {
Random rand = new Random();
int[] dice = new int[5];
for (int i = 0; i < 5; i++) dice[i] = rand.nextInt(6) + 1;
System.out.println("首次投掷：" + Arrays.toString(dice));
// 第一次保留决策（还剩2次重投机会）
int mask1 = findBestKeepMask(dice, 2);
System.out.println("最优保留掩码：" + String.format("%5s", Integer.toBinaryString(mask1)).replace(' ', '0'));
// 执行重投
for (int i = 0; i < 5; i++) {
if ((mask1 & (1 << i)) == 0) dice[i] = rand.nextInt(6) + 1;
}
System.out.println("第一次重投后：" + Arrays.toString(dice));
// 第二次保留决策（还剩1次重投机会）
int mask2 = findBestKeepMask(dice, 1);
System.out.println("最优保留掩码：" + String.format("%5s", Integer.toBinaryString(mask2)).replace(' ', '0'));
// 执行重投
for (int i = 0; i < 5; i++) {
if ((mask2 & (1 << i)) == 0) dice[i] = rand.nextInt(6) + 1;
}
System.out.println("第二次重投后：" + Arrays.toString(dice));
// 选择最佳计分类别
int bestCat = -1, bestScore = -1;
for (int cat = 0; cat < CATEGORIES; cat++) {
int s = scoreCategory(dice, cat);
if (s > bestScore) {
bestScore = s;
bestCat = cat;
}
}
System.out.println("最佳计分类别：" + bestCat + "，得分：" + bestScore);
}
public static void main(String[] args) {
System.out.println("=== Yahtzee AI 演示 ===");
playRound();
}
}
复杂度分析
- 状态空间：5颗骰子排序后有
C(10,5) = 252种唯一多重集合；考虑顺序则有6^5 = 7776种。 - 保留决策：每轮需枚举
2^5 = 32种保留子集。 - 时间复杂度：单次保留决策的期望计算为
O(32 × 6^k)，k为重投骰子数。通过记忆化搜索可将多轮重复状态降至毫秒级。 - 空间复杂度：记忆化表存储
O(7776 × 32 × 3)个状态值。
总结
Yahtzee的AI决策本质是期望最大化问题。本文通过状态编码、枚举保留子集与记忆化搜索，实现了每轮的最优保留策略计算。读者可进一步扩展完整13轮的全局动态规划，引入上部奖励 bonus 的期望估计，构建更强的端到端AI。
