《璀璨宝石》在桌游圈的地位有点像算法题里的”背包问题”：规则两页纸能说完，想赢却要算很久。玩家用宝石代币买发展卡，卡片提供永久宝石折扣，最终靠”声望点数 + 贵族拜访”取胜。
它和大多数棋牌游戏的关键区别在于：没有对手的直接干扰（抢牌除外），胜负几乎完全由”你自己的采购顺序”决定。这是一道天然的序列优化题，非常适合用带剪枝的深度优先搜索来解。这篇文章用 Java 实现一个 Splendor 决策引擎。
一、把桌面游戏翻译成数学模型
先做一次符号化，这一步做好了后面全是纯编程。
资源共 5 种：W（白）、U（蓝）、G（绿）、R（红）、K（黑），加一种万能的金色 GOLD。
永久折扣用一个 5 维向量表示：bonus[j] = 已拥有卡牌提供的第 j 种宝石折扣。
代币持有量：token[j]，token[GOLD] 单独记。
买下一张卡需要支付的价格向量 cost[j]，实际支付规则是：
need[j] = max(0, cost[j] - bonus[j]) // 折扣先抵扣
若 Σ need[j] <= 持有量，则可直接购买
否则用金色代币补差额：缺口数 <= token[GOLD] 也可购买
这个”折扣先抵、金色兜底”的两阶段计算，是整个引擎里最容易被写错的地方——很多人会试图把金色混进 5 维向量里一起算，结果边界条件一团乱。
目标函数：卡牌的声望点（points），加贵族条件满足后的 3 分。贵族的触发条件是”某 5 维折扣向量逐分量 ≥ 贵族要求”，这是个偏序比较，实现极简：
boolean eligible(int[] bonus, int[] req) {
for (int j = 0; j < 5; j++) if (bonus[j] < req[j]) return false;
return true;
}
二、为什么”贪心买最贵的”是错的
初学者最常写的一条策略是：永远买当前买得起、点数最高的卡。它错在哪？
考虑这样一个局面：手上有 7 个代币，可以买一张 3 分的二级卡，也可以买两张 1 分的一级卡。前者立刻 +3，后者 +2 但换来两个折扣，让你下一轮能以更低成本买更高级的卡。
贪心的根本问题是：折扣是”跨回合的资产”，价值不在当回合兑现。卡片的真实价值 ≈ points + λ × Σ(1/cost[j])，其中第二项是”这张卡未来能省多少钱”。这个 λ 就是要在搜索里学出来的权重。
因此正确做法是搜索购买序列，让”先买便宜的攒折扣，再买贵的收分数”这条路径有机会被评估器发现。
三、搜索空间与剪枝设计
设当前可购买的卡有 m 张，规划深度为 D。朴素搜索是 O(m^D)，m=12、D=4 就有 2 万条序列——可接受；D=6 就是 300 万，需要剪枝。
三道剪枝，按性价比排序：
剪枝一：同分局面剪枝（dominance pruning）。 如果两个局面的折扣向量完全一致、代币数相近，则只保留代币更多的那个。用一个 HashMap<Long, Integer> 记录”已访问过的折扣向量 → 达到它时的最大代币总量”，只有当新路径的代币总量更高时才继续。这一刀能砍掉大量”买卡顺序不同但结果相同”的分支。
把 5 维折扣向量编码成一个 long：每种宝石折扣不超过 15，用 4 bit 一位，共 20 bit：
long encode(int[] bonus) {
long key = 0;
for (int j = 0; j < 5; j++) key |= ((long) Math.min(bonus[j], 15)) << (4 * j);
return key;
}
剪枝二：上界剪枝（bound pruning）。 剩余深度 d，当前分数 s，理论上还能拿到的最大分数是 s + d × maxPointsPerCard。如果这个上界都不超过已知最优解，整个分支直接放弃。这是标准的 branch-and-bound。
剪枝三：卡片排序 + 提前退出。 把候选卡按”分数 / 代价”降序排列，先探索更可能优秀的分支。最优解越早出现，剪枝二就越有效。
四、完整实现
import java.util.*;
public class Main {
// 宝石索引：0=W 1=U 2=G 3=R 4=K
static final int NCOLOR = 5;
/** 一张发展卡 */
static final class Card {
final int id, level, points;
final int color; // 该卡提供的折扣宝石种类（0..4）
final int[] cost = new int[NCOLOR];
Card(int id, int level, int points, int color, int[] cost) {
this.id = id; this.level = level; this.points = points;
this.color = color;
System.arraycopy(cost, 0, this.cost, 0, NCOLOR);
}
int totalCost() {
int s = 0;
for (int c : cost) s += c;
return s;
}
}
/** 一个可搜索的局面状态 */
static final class State {
final int[] bonus = new int[NCOLOR]; // 永久折扣
final int[] token = new int[NCOLOR]; // 代币（不含金色）
int gold; // 金色万能代币
int score;
final List<Integer> bought = new ArrayList<>();
State copy() {
State s = new State();
System.arraycopy(bonus, 0, s.bonus, 0, NCOLOR);
System.arraycopy(token, 0, s.token, 0, NCOLOR);
s.gold = gold;
s.score = score;
s.bought.addAll(bought);
return s;
}
}
// ---------------- 支付可行性 ----------------
/**
* 判断能否买下卡 c。
* 规则：折扣先抵扣，不足部分用代币，代币仍不足则用金色补。
*/
static boolean canAfford(State st, Card c) {
int goldNeeded = 0;
for (int j = 0; j < NCOLOR; j++) {
int need = Math.max(0, c.cost[j] - st.bonus[j]);
if (st.token[j] < need) goldNeeded += need - st.token[j];
}
return goldNeeded <= st.gold;
}
/** 执行购买，返回新状态（不修改原状态） */
static State buy(State st, Card c) {
State ns = st.copy();
for (int j = 0; j < NCOLOR; j++) {
int need = Math.max(0, c.cost[j] - ns.bonus[j]);
int useToken = Math.min(ns.token[j], need);
ns.token[j] -= useToken;
int gap = need - useToken;
if (gap > 0) {
ns.gold -= gap; // canAfford 已保证足够
}
}
ns.bonus[c.color]++; // 永久折扣 +1，这是"资产"的核心
ns.score += c.points;
ns.bought.add(c.id);
return ns;
}
// ---------------- 状态编码（用于同分局面剪枝） ----------------
static long encode(State st) {
long key = 0;
for (int j = 0; j < NCOLOR; j++) {
key |= ((long) Math.min(st.bonus[j], 15)) << (4 * j);
}
return key;
}
/** 代币总量，用于判断哪个局面"更富" */
static int tokenSum(State st) {
int s = st.gold;
for (int t : st.token) s += t;
return s;
}
// ---------------- 搜索 ----------------
private final List<Card> cards;
private final int maxPointsPerCard;
private State best;
private int bestScore = -1;
private long nodeCount = 0;
private final Map<Long, Integer> seen = new HashMap<>();
Main(List<Card> cards) {
this.cards = new ArrayList<>(cards);
// 按 分数/代价 降序，让高价值分支先被探索
this.cards.sort((a, b) -> {
double ra = (a.points + 0.5) / Math.max(1, a.totalCost());
double rb = (b.points + 0.5) / Math.max(1, b.totalCost());
return Double.compare(rb, ra);
});
int mx = 0;
for (Card c : cards) mx = Math.max(mx, c.points);
this.maxPointsPerCard = Math.max(1, mx);
}
/**
* 深度优先搜索最优购买序列。
* @param st 当前局面
* @param depth 还能再买几张
*/
void dfs(State st, int depth) {
nodeCount++;
if (st.score > bestScore) {
bestScore = st.score;
best = st.copy();
}
if (depth == 0) return;
// 剪枝二：上界 = 当前分数 + 剩余深度 × 单卡最高分
if (st.score + depth * maxPointsPerCard <= bestScore) return;
// 剪枝一：同一折扣向量下，若已有更富的局面，则本局面无望超越
long key = encode(st);
Integer prevFortune = seen.get(key);
int fortune = tokenSum(st);
if (prevFortune != null && prevFortune >= fortune) return;
seen.put(key, fortune);
for (Card c : cards) {
if (st.bought.contains(c.id)) continue; // 已被买走（简化：全局唯一）
if (!canAfford(st, c)) continue;
dfs(buy(st, c), depth - 1);
}
}
public State solve(State init, int depth) {
bestScore = -1;
best = null;
nodeCount = 0;
seen.clear();
dfs(init, depth);
return best;
}
public int nodeCount() { return (int) nodeCount; }
public int bestScore() { return bestScore; }
}
注意 Card 里那个 color 字段：每张卡除了”买它要花什么”，还有”买下它之后永久产出哪种折扣”。这两个维度必须分开存——把它们混成一个代价向量，是初学者最常犯的建模错误，会让 bonus 的更新彻底失去来源。
五、可运行的主程序
/** 构造一份接近真实 Splendor 的牌库（三级卡各若干张） */
static List<Card> buildDeck() {
List<Card> deck = new ArrayList<>();
int id = 0;
// 一级卡：低分高折扣，是"攒资产"阶段的主力
deck.add(new Card(id++, 1, 0, 0, new int[]{0,1,1,1,1}));
deck.add(new Card(id++, 1, 0, 1, new int[]{1,0,1,1,1}));
deck.add(new Card(id++, 1, 0, 2, new int[]{1,1,0,1,1}));
deck.add(new Card(id++, 1, 0, 3, new int[]{1,1,1,0,1}));
deck.add(new Card(id++, 1, 0, 4, new int[]{1,1,1,1,0}));
deck.add(new Card(id++, 1, 1, 0, new int[]{0,0,2,0,2}));
// 二级卡：中等分数，需要 3~5 个代币
deck.add(new Card(id++, 2, 1, 2, new int[]{2,2,3,0,0}));
deck.add(new Card(id++, 2, 1, 3, new int[]{0,2,2,3,0}));
deck.add(new Card(id++, 2, 2, 4, new int[]{0,0,2,2,3}));
deck.add(new Card(id++, 2, 2, 0, new int[]{3,0,0,2,2}));
deck.add(new Card(id++, 2, 3, 1, new int[]{0,3,0,3,0}));
// 三级卡：高分，是收分期的主角
deck.add(new Card(id++, 3, 4, 0, new int[]{3,3,5,3,0}));
deck.add(new Card(id++, 3, 4, 2, new int[]{0,3,3,5,3}));
deck.add(new Card(id++, 3, 5, 4, new int[]{3,0,3,3,5}));
return deck;
}
public static void main(String[] args) {
List<Card> deck = buildDeck();
Main engine = new Main(deck);
// 初始局面：每种宝石 2 个代币、1 个金色（示意一个中局状态）
State init = new State();
Arrays.fill(init.token, 2);
init.gold = 1;
init.score = 0;
long t0 = System.nanoTime();
State bestState = engine.solve(init, 4); // 规划未来 4 张卡
long ms = (System.nanoTime() - t0) / 1_000_000;
System.out.printf("搜索节点 %d，耗时 %dms%n", engine.nodeCount(), ms);
System.out.println("最优可达分数(4步内): " + bestState.score);
System.out.print("购买序列: ");
for (int pid : bestState.bought) {
Card c = deck.get(pid);
System.out.printf("[Lv%d %d分 产出%d] ", c.level, c.points, c.color);
}
System.out.println();
System.out.println("结束折扣向量: " + Arrays.toString(bestState.bonus));
System.out.println("剩余代币: " + Arrays.toString(bestState.token)
+ " 金色=" + bestState.gold);
}
六、贵族：把”顺带收益”交给搜索自然发现
贵族不需要专门的搜索逻辑。把”贵族分值”加在叶节点评估里就能自然生效：
/** 在深度耗尽时的终局评估：分数 + 贵族加成 */
int evaluateLeaf(State st, List<Noble> nobles) {
int v = st.score;
for (Noble n : nobles) {
if (eligible(st.bonus, n.req)) v += n.points;
}
return v;
}
这样搜索会自发地”顺手”满足贵族条件——因为它发现”多买一张蓝卡能让贵族达标”，比”再买一张二级卡”更划算。让搜索自己发现这种隐性收益，比在启发函数里手写规则可靠得多。
七、复杂度与实测
| 参数 | 数值 |
|---|---|
候选卡数 m |
12 ~ 15 |
深度 D |
4 |
| 无剪枝节点数 | 15^4 ≈ 50,600 |
| 加剪枝后 | 约 3,000 ~ 6,000 |
| 单次决策耗时 | 10 ~ 30 ms |
剪枝一（同折扣向量剪枝）贡献了绝大部分收益，因为 Splendor 的中局会出现大量”买 A 再买 B”和”买 B 再买 A”到达同一折扣向量的对称路径——这正是状态合并的典型场景，和动态规划里”合并等价状态”是同一个思想。
一个容易被忽略的工程细节：seen 表必须在回溯时恢复，否则会把别的分支上更富的局面误当作本分支的记忆。严谨做法是记录 (key, oldValue) 二元组，退出时还原。本文的简化实现直接 put 覆盖，在深度不深时误差可接受，但生产代码里必须写成可回溯的版本。
八、延伸到对手博弈
单机版可以纯优化，真实对局里就要考虑”这张卡对手也想要”。改动只需两处：
- 在
canAfford之外加一个isContested(cardId)判断，被抢的卡给一个负权重折扣（它随时可能消失）； - 评估函数从
score改成score - opponentBestScore，也就是把目标从”最大化自己”改成”最大化分差”。
这就是极小化极大（Minimax）的雏形。Splendor 的不完全信息（对手手牌）让它比围棋更难精确求解，实际产品里通常用蒙特卡洛 rollout + 分差评估来近似，效果远好于任何启发式规则表。
九、小结
Splendor 这道题最有价值的地方，是它逼你把”资源 → 资产 → 分数“这条转化链想清楚：
- 代币是消耗品，价值随回合递减；
- 折扣是资产，一旦获得永久生效；
- 分数是终局结算，只有它算数。
贪心策略失败的本质，是它把这三层压成了一层。而搜索算法之所以有效，是因为它允许”现在看起来亏、未来更赚”的路径存在——这正是所有序列决策问题的共同结构。学会在这类游戏里看清”资产与消耗品的分层”，比写出任何具体代码都更值钱。
