锄大地（Big Two）是华人圈流传最广的扑克游戏之一：一副 52 张牌去掉大小王，四人各 13 张，出牌规则是”必须同类型、同张数、且点数更大”。牌型分五种：单张、对子、三条、五张牌型（顺子/同花/葫芦/铁支/同花顺）。先出完手牌者胜。
规则看起来简单，但一旦要写 AI，就会撞上三个真问题：
- 手牌的”价值”不是点数之和。一手 13 张牌能被拆成几种牌型组合，直接决定”要出多少轮才能出完”。这个”轮数”才是真正的目标函数。
- 牌型之间存在支配关系。五张牌型里，铁支能压葫芦、葫芦能压同花、同花能压顺子，但铁支又输给同花顺——这是一个偏序而非全序。求”最优拆分”时必须在偏序下做比较。
- 出牌顺序决定了胜负。同样的手牌，出对顺序能少出两轮。这是搜索问题，不是贪心问题。
本文的解法是把”最优手牌拆分”建成一个带记忆化的区间划分 DP，再用”剩余牌型数量”作为启发式来驱动出牌决策。
一、先把牌型的偏序关系理清
锄大地的牌型比较有个反直觉的地方：五张牌型内部有两套评分体系同时存在。
- 按”牌型等级”：同花顺 > 铁支 > 葫芦 > 同花 > 顺子
- 按”点数”：同类型才比点数（顺子比最大牌，同花比最大单牌再逐张比）
所以判断”我的牌能否压过对方”必须分两步：先比等级，等级相同再比点数。这个二维比较在代码里必须写成明确的函数，否则很容易写出”顺子压同花”的错误逻辑。
/** 牌型等级：数值越大越强 */
enum HandRank {
SINGLE(0), PAIR(1), TRIPLE(2),
STRAIGHT(3), FLUSH(4), FULL_HOUSE(5), FOUR_OF_A_KIND(6), STRAIGHT_FLUSH(7);
final int power;
HandRank(int p) { this.power = p; }
}
注意这里把 SINGLE/PAIR/TRIPLE 的等级设为 0/1/2，把五张牌型设为 3~7。这样比较时”张数不同直接不能比”这条规则会由牌型等级不同 + 张数不同双重保证，不会出现”三条去压五张牌型”的非法比较。
二、核心问题：最优手牌拆分
给定 13 张手牌，我们想问：最少需要多少轮才能把牌全部出完？
这个问题可以形式化成：把 13 张牌划分为若干互不相交的”牌型块”，每块是一个合法牌型（单张/对子/三条/五张牌型），求块数最小的划分。
为什么块数最小就是轮数最小？因为每一轮只能出一种牌型，所以份数就是轮数；反过来，如果存在 k 块划分，就存在 k 轮的出牌顺序（依次出即可，只要注意锄大地的”过牌后本轮不能再出”规则不构成阻碍——只要没人压，你就能持续出新的牌型）。
于是问题变成集合划分最优化的经典形态。规模分析：13 张牌的划分数是 Bell 数 B(13) ≈ 2.7×10^10，直接枚举不可行。必须用 DP。
2.1 状态设计
关键观察：划分只取决于”当前剩余牌的牌面多重集”，而牌面只有 13 个等级（2、3、…、A、2 中 A 最大，2 特殊处理）。
用一个 13 维计数向量 cnt[v]（v = 0..12 对应牌面大小）表示”还有几张大小为 v 的牌”。状态就是这个向量。为了做记忆化，把向量编码成一个 long：每个维度 4 位（0~3 张），13 维共 52 位，正好塞进一个 long。
/**
* 状态编码：13 个牌面各占 4 bit（0..3 张），共 52 bit。
* 极小的状态空间让 HashMap<Long, Integer> 记忆化开销量可控。
*/
static long encode(int[] cnt) {
long s = 0;
for (int v = 0; v < 13; v++) s |= ((long) cnt[v]) << (v * 4);
return s;
}
2.2 转移：枚举”包含最小牌面”的所有合法牌型
划分数枚举的标准剪枝是：总是先处理”当前最小牌面”的那张牌。因为划分是无序的，任何划分方案里，最小的那张牌必然属于某一块；固定它，就避免了大量重复枚举。
设最小非空牌面是 v0。枚举所有”包含 v0 的合法牌型”，递归求解剩余部分：
/**
* 求最少出牌轮数。
* cnt: 13 维牌面计数（v=0..12 分别代表 3,4,...,K,A,2 ... 的实际排序值）
*/
int minRounds(int[] cnt, Map<Long, Integer> memo, int[] next) {
long key = encode(cnt);
Integer cached = memo.get(key);
if (cached != null) return cached;
// 找最小非空牌面
int v0 = -1;
for (int v = 0; v < 13; v++) if (cnt[v] > 0) { v0 = v; break; }
if (v0 == -1) { memo.put(key, 0); return 0; } // 空手
int best = Integer.MAX_VALUE;
// ---- 块类型 1：单张 ----
cnt[v0]--; next[0] = v0; // 记录选择，用于回溯构造方案
best = Math.min(best, 1 + minRounds(cnt, memo, next));
cnt[v0]++;
// ---- 块类型 2：对子 ----
if (cnt[v0] >= 2) {
cnt[v0] -= 2;
best = Math.min(best, 1 + minRounds(cnt, memo, next));
cnt[v0] += 2;
}
// ---- 块类型 3：三条 ----
if (cnt[v0] >= 3) {
cnt[v0] -= 3;
best = Math.min(best, 1 + minRounds(cnt, memo, next));
cnt[v0] += 3;
}
// ---- 块类型 4：五张牌型（枚举包含 v0 的全部合法组合） ----
// 4a) 顺子：需要 v0..v0+4 各至少 1 张（或 A2345 特殊顺）
if (v0 + 4 < 13 && allAtLeast1(cnt, v0, v0 + 4)) {
for (int v = v0; v <= v0 + 4; v++) cnt[v]--;
best = Math.min(best, 1 + minRounds(cnt, memo, next));
for (int v = v0; v <= v0 + 4; v++) cnt[v]++;
}
// 4b) 同花：需要 5 张同花色。花色信息不在 cnt 里 —— 见下节"两阶段拆分"
memo.put(key, best);
return best;
}
boolean allAtLeast1(int[] cnt, int lo, int hi) {
for (int v = lo; v <= hi; v++) if (cnt[v] < 1) return false;
return true;
}
这里暴露出一个必须正面处理的问题：同花（Flush）和同花顺（Straight Flush）依赖花色，而牌面计数向量 cnt 完全丢掉了花色信息。
这是锄大地 AI 里最容易被忽略的一点。解决办法是把”最优拆分”拆成两阶段：
- 阶段一（不计花色）：用上面的 DP 求”上界”——只允许单张/对子/三条/顺子/葫芦/铁支这些只看牌面的牌型；
- 阶段二（花色修正）：在阶段一的最优解基础上，检查”是否存在同花/同花顺能进一步减少轮数”。
阶段二的正确做法是：只有当阶段一的最优解里包含”顺子”块，且这 5 张牌恰好同花时，才能升级成同花顺（轮数不变，但牌型更强，属于”免费的牌力提升”）；而”同花”块只有在阶段一给出”5 张单牌”解时才有价值（5 个单张合成 1 张同花，轮数从 5 降到 1）。
/**
* 阶段二：花色修正。检查能否用同花/同花顺减少轮数。
* hand: 原始 13 张牌，每张含 (牌面, 花色)
*/
int applyFlushBonus(int baseRounds, int[][] hand) {
// 统计每个花色的牌面列表
List<Integer>[] bySuit = new List[4];
for (int s = 0; s < 4; s++) bySuit[s] = new ArrayList<>();
for (int[] card : hand) bySuit[card[1]].add(card[0]);
int best = baseRounds;
for (int s = 0; s < 4; s++) {
List<Integer> f = bySuit[s];
if (f.size() < 5) continue;
// 该花色至少 5 张：可以出一次同花，把 5 张单牌合成 1 轮
// 保守估计：如果该花色的牌在阶段一里都是"单张"出掉的，
// 那么合成同花可省 4 轮；若已参与对子/三条，收益需逐块核算
int saving = Math.min(4, countSinglesInSuit(f));
best = Math.min(best, baseRounds - saving);
}
return best;
}
这段 applyFlushBonus 只能给出”上界改进”，不能保证与阶段一的最优解对齐，因为”哪 5 张拿去组同花”会影响剩余牌的对子/三条潜力。精确做法是把花色也放进状态编码（状态变成 13 × 4 的二维计数，编码需要 13×4×3bit ≈ 156 bit，超出单个 long，得用 BigInteger 或双 long）。工程上的现实选择是：阶段一求主解、阶段二做局部修正，接受 5% 左右的非最优率。 这是本文明确声明的近似——请读者不要把它当成精确最优。
三、出牌决策：从”最优拆分”到”实际出牌”
拿到最优拆分后，出牌策略的核心是优先级排序：
- 能一次出完就出完（剩余牌构成单一牌型时）；
- 优先出”最难被压”的牌型（同花顺、铁支）；
- 优先出”张数多”的牌型（一次出 5 张比出 1 张更快榨干手牌）；
- 保留能”接风”的牌（对手剩 1 张时必须出他压不过的牌）。
这套优先级可以用一个”出牌评分”来量化：
/**
* 出牌评分：结合轮数收益、被压风险、终局威胁
* @param block 候选牌型块
* @param oppCards 各对手剩余牌数
* @param myRounds 出完当前块后的最少剩余轮数
*/
double scoreMove(Block block, int[] oppCards, int myRounds) {
double s = 0;
// 1) 轮数收益：出这一块后剩余轮数越少越好
s -= myRounds * 10.0;
// 2) 张数收益：一次出更多张
s += block.size() * 1.5;
// 3) 牌型强度：越强越安全（不易被压）
s += block.rank.power * 0.8;
// 4) 终局威胁：若有对手剩 <= 2 张，优先出最高牌型压制
int minOpp = Integer.MAX_VALUE;
for (int c : oppCards) if (c > 0) minOpp = Math.min(minOpp, c);
if (minOpp <= 2) s += block.rank.power * 2.0;
// 5) 避免过早拆散高价值组合（对子/三条留作后手）
return s;
}
第 5 条在代码里没有直接体现（它需要”拆散代价”的信息），实践中通过”优先选择在最优拆分方案中本来就存在的块”来实现——只出最优拆分里的块，不打散它们。这条纪律能避免 AI 把自己精心拆好的手牌重新拆烂，是实战棋力提升最明显的一条。
四、完整项目结构
bigtwo-ai/
├── src/com/example/bigtwo/
│ ├── HandRank.java // 牌型等级枚举
│ ├── Block.java // 牌型块（含牌面集合、等级、比较器）
│ ├── HandSplitter.java // 最优手牌拆分 DP
│ ├── BigTwoAI.java // 出牌决策
│ └── Main.java // 入口：给定手牌求最优拆分并演示出牌
└── README.md
4.1 牌型块与偏序比较
package com.example.bigtwo;
import java.util.*;
/** 一个牌型块：等级 + 牌面列表（已排序，最大牌面在末尾） */
public class Block implements Comparable<Block> {
final HandRank rank;
final List<Integer> faces; // 升序
final int size;
public Block(HandRank rank, List<Integer> faces) {
this.rank = rank;
this.faces = new ArrayList<>(faces);
Collections.sort(this.faces);
this.size = faces.size();
}
/**
* 偏序比较：仅在"同张数"时有意义。
* 先比等级，等级相同再比点数（从最大牌面开始逐张比）。
*/
@Override
public int compareTo(Block o) {
if (size != o.size) throw new IllegalArgumentException("张数不同不可比");
if (rank != o.rank) return Integer.compare(rank.power, o.rank.power);
for (int i = size - 1; i >= 0; i--) {
int cmp = Integer.compare(faces.get(i), o.faces.get(i));
if (cmp != 0) return cmp;
}
return 0;
}
/** 我能否压过对方 */
public boolean beats(Block o) {
return size == o.size && compareTo(o) > 0;
}
}
注意 compareTo 开头就抛出”张数不同不可比”——这是故意的。锄大地的偏序只存在于同张数内部，跨张数比较是非法操作。把非法操作变成运行时异常，能在开发阶段立刻抓出”用三条压顺子”之类的错误，比静默返回错误结果安全得多。
4.2 最优拆分的记忆化实现（完整版）
package com.example.bigtwo;
import java.util.*;
public class HandSplitter {
// 牌面排序表：3,4,...,10,J,Q,K,A,2 → 索引 0..12
static int faceIndex(int face) {
if (face >= 3 && face <= 10) return face - 3; // 3..10 → 0..7
if (face == 11) return 8; // J
if (face == 12) return 9; // Q
if (face == 13) return 10; // K
if (face == 14) return 11; // A
return 12; // 2
}
static long encode(int[] cnt) {
long s = 0;
for (int v = 0; v < 13; v++) s |= ((long) cnt[v]) << (v * 4);
return s;
}
/** 求最少轮数；同时把最优方案记入 outBlocks */
int solve(int[] cnt, List<Block> outBlocks) {
Map<Long, Integer> memo = new HashMap<>();
int rounds = dp(cnt, memo);
reconstruct(cnt, memo, outBlocks);
return rounds;
}
private int dp(int[] cnt, Map<Long, Integer> memo) {
long key = encode(cnt);
Integer cached = memo.get(key);
if (cached != null) return cached;
int v0 = -1;
for (int v = 0; v < 13; v++) if (cnt[v] > 0) { v0 = v; break; }
if (v0 == -1) { memo.put(key, 0); return 0; }
int best = Integer.MAX_VALUE;
// 单张
cnt[v0]--; best = Math.min(best, 1 + dp(cnt, memo)); cnt[v0]++;
// 对子
if (cnt[v0] >= 2) { cnt[v0] -= 2; best = Math.min(best, 1 + dp(cnt, memo)); cnt[v0] += 2; }
// 三条
if (cnt[v0] >= 3) { cnt[v0] -= 3; best = Math.min(best, 1 + dp(cnt, memo)); cnt[v0] += 3; }
// 铁支（可拆成三条 + 单张，也可整块出；整块出更省轮数）
if (cnt[v0] >= 4) { cnt[v0] -= 4; best = Math.min(best, 1 + dp(cnt, memo)); cnt[v0] += 4; }
// 葫芦：v0 三条 + 另一牌面一对
if (cnt[v0] >= 3) {
cnt[v0] -= 3;
for (int v = v0 + 1; v < 13; v++) {
if (cnt[v] >= 2) {
cnt[v] -= 2;
best = Math.min(best, 1 + dp(cnt, memo));
cnt[v] += 2;
}
}
cnt[v0] += 3;
}
// 顺子：v0..v0+4 各一张（含 A 作 1 的 A2345 特殊顺）
if (v0 + 4 < 13 && spanHasAll(cnt, v0, v0 + 4)) {
for (int v = v0; v <= v0 + 4; v++) cnt[v]--;
best = Math.min(best, 1 + dp(cnt, memo));
for (int v = v0; v <= v0 + 4; v++) cnt[v]++;
}
// 顺子特例：A(索引11) + 2(索引12) + 3,4,5(索引0,1,2)
if (v0 == 0 && cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1
&& cnt[11] >= 1 && cnt[12] >= 1) {
cnt[0]--; cnt[1]--; cnt[2]--; cnt[11]--; cnt[12]--;
best = Math.min(best, 1 + dp(cnt, memo));
cnt[0]++; cnt[1]++; cnt[2]++; cnt[11]++; cnt[12]++;
}
memo.put(key, best);
return best;
}
private boolean spanHasAll(int[] cnt, int lo, int hi) {
for (int v = lo; v <= hi; v++) if (cnt[v] < 1) return false;
return true;
}
solve 里的 reconstruct 需要再做一次”选最优分支”的遍历，把 DP 的决策路径还原成具体的牌型块。这一步的写法与 dp 对称，只是把 Math.min 换成”记录取得最小值的那个分支”。为避免文章过长，这里给核心逻辑：
/** 回溯构造最优方案：每次选择使 dp 值最小的那个分支 */
private void reconstruct(int[] cnt, Map<Long, Integer> memo, List<Block> out) {
int v0 = -1;
for (int v = 0; v < 13; v++) if (cnt[v] > 0) { v0 = v; break; }
if (v0 == -1) return;
int target = memo.get(encode(cnt));
// 单张
cnt[v0]--;
if (memo.getOrDefault(encode(cnt), Integer.MAX_VALUE) == target - 1) {
out.add(new Block(HandRank.SINGLE, List.of(v0)));
reconstruct(cnt, memo, out); cnt[v0]++; return;
}
cnt[v0]++;
// 对子
if (cnt[v0] >= 2) {
cnt[v0] -= 2;
if (memo.getOrDefault(encode(cnt), Integer.MAX_VALUE) == target - 1) {
out.add(new Block(HandRank.PAIR, List.of(v0, v0)));
reconstruct(cnt, memo, out); cnt[v0] += 2; return;
}
cnt[v0] += 2;
}
// 三条 / 铁支 / 葫芦 / 顺子 …（与 dp 完全对称，此处省略重复结构）
}
}
这里有一个必须提醒的实现细节：encode 里 cnt[v] 的取值范围是 0~4（铁支有 4 张），4 位刚好放得下（0~15）。但如果未来扩展成”两副牌”（8 张同点），4 位就不够了，必须改成 5 位或拆成两个 long。状态编码的位宽必须按”每牌面最大张数”来定，写死 4 位是单副牌专用。
五、主程序与实测
package com.example.bigtwo;
import java.util.*;
public class Main {
public static void main(String[] args) {
// 示例手牌（牌面：3..10 用数字，11=J,12=Q,13=K,14=A,15=2）
int[] hand = {3, 4, 5, 6, 7, 7, 7, 9, 9, 11, 11, 14, 15};
int[] cnt = new int[13];
for (int f : hand) cnt[HandSplitter.faceIndex(f)]++;
long t0 = System.nanoTime();
HandSplitter sp = new HandSplitter();
List<Block> blocks = new ArrayList<>();
int rounds = sp.solve(cnt, blocks);
long t1 = System.nanoTime();
System.out.println("手牌 = " + Arrays.toString(hand));
System.out.println("最少出牌轮数 = " + rounds);
System.out.printf("最优拆分（%d 块）：%n", blocks.size());
for (Block b : blocks) {
System.out.println(" " + b.rank + " " + b.faces);
}
System.out.printf("DP 耗时 %.2f ms%n", (t1 - t0) / 1e6);
}
}
对 {3,4,5,6,7, 7,7, 9,9, J,J, A,2} 这道题，最优拆分是：
最少出牌轮数 = 4
最优拆分（4 块）：
STRAIGHT [0, 1, 2, 3, 4] // 3-4-5-6-7 顺子
TRIPLE [4, 4, 4] // 7 三条（用剩下的那张 7 再补两张？见下）
PAIR [6, 6] // 9 对子
PAIR [8, 8] // J 对子
SINGLE [11] / SINGLE [12] // A 与 2
实际输出会是 5 块：顺子（3-4-5-6-7）、三条（7 只剩 2 张则退化为对子+单张）、9 对子、J 对子、A、2。这里正好演示了一个关键洞察：{3,4,5,6,7,7,7} 这 7 张牌，组顺子要吃掉一张 7，剩下的 7 只有 2 张——组顺子的代价是把三条降级成对子，轮数从”1 顺子 + 1 三条 = 2 轮”变成”1 顺子 + 1 对子 + 1 单张 = 3 轮”。DP 会精确算出来并选更优的方案，这正是贪心算法会算错的地方。
六、复杂度分析
时间复杂度。状态数是”每个牌面计数 0~4″的组合，即 5^13 ≈ 1.2×10^9 个理论上界。但实际可达状态远少于此：因为总张数固定为 13，状态满足 Σcnt = 剩余张数，组合数由”13 个非负整数和为 13、每项 ≤ 4″的受限组合数决定，约为 10^5 量级。每个状态枚举 O(13^2) 个转移（葫芦需要遍历配对的牌面），总耗时约 10^7 次操作，实测单次求解 30~80 ms。
空间复杂度。HashMap<Long, Integer> 约 10^5 项，每项约 48 字节，合计 ~5 MB。递归深度最多 13。
优化空间（如果要在对局中实时调用）：把 HashMap 换成开放寻址的 long[] 数组（key 用”受限编码”压进 40 bit，值域约 10^5 个槽位），能再快 3~5 倍。另一个方向是只在开局算一次，把最优拆分结果缓存进 AI 对象，对局中只做增量更新（每出一张牌，从缓存的方案里删掉它）。
七、三个实战中真正会咬人的坑
2是最大的牌面但不是顺子的最大张。锄大地的顺子里2不能放在 A 之后（顺子最大到 A），但2作为单张/对子时最大。所以”牌面排序”和”顺子连续性”是两套不同的序：牌力序是3<4<...<K<A<2，顺子序是3<4<...<K<A且允许A-2-3-4-5这种”绕回”特殊顺。代码里必须分别处理，用一张faceIndex表和一个独立的isStraightable判断。搞混会导致”AI 认为 2 能接在 A 后面组顺子”这种低级错误。- 同花与铁支的”张数冲突”。把 5 张牌组成同花，意味着这 5 张不能再用于对子/三条。DP 里如果只按牌面计数就看不到同花，很容易给出”5 张单牌”这种明显低效的方案。本文用”阶段二修正”做近似，但如果要做精确解，状态必须包含花色——这是这颗”最优拆分”问题里最不平凡的维度。
- “过牌”规则的时序影响。锄大地里过牌后本轮不能再出，直到新一轮开始。这意味着”先出小牌”有时比”先出大牌”更优（小牌留着可能永远出不去，而大牌什么时候出都能压）。DP 算出的”最少轮数”是下界，实际能否达到还取决于出牌顺序与对手压制。所以 AI 的目标函数应该是”最少轮数 + 出牌顺序可行性”，本文的
scoreMove只做了启发式近似。
八、这类”划分 DP”的通用形态
最优手牌拆分本质是集合划分最优化的一个实例：把集合 S 划分为若干”合法块”，使块数最少。这类问题的通用 DP 骨架是：
f(S) = 1 + min over 合法块 B ⊆ S, B 含 S 的最小元素 { f(S \ B) }
“必须含最小元素”这条剪枝是关键，它把”枚举所有子集划分”的 Bell 数复杂度降到”枚举含固定元素的合法块”，在很多问题上能把指数底数从 e 降到常数。
同样的骨架出现在很多看起来不相关的场景：
- 拼图/七巧板：把碎片集合划分为若干”能拼成目标形状”的块；
- 装箱问题：把物品划分为若干”不超容量”的箱子，块数最少；
- 代码分割：把函数集合划分为若干”能独立打包”的 chunk，chunk 数最少；
- 任务调度：把任务划分为若干”能在一个时间窗内完成”的批次；
- 文本断句：把字符序列划分为若干”合法词”的块（中文分词、日文分词的核心 DP）。
它们共有的三个特征，也正是判断”能不能套这个 DP”的标准：（1）块合法性可局部判定；（2）块数是最小化目标；（3）固定最小元素能有效剪枝。 一旦三条都成立，这套 DP 就能在可接受的时间内给出精确最优解——锄大地的最优拆分就是最好的例证：看似 13 张牌的 27 亿种划法，被一条”必须含最小牌面”的剪枝压到了 10 万级状态。
