每日算法 — 使用java实现掼蛋：手牌拆分动态规划与级牌概率推断

掼蛋是江淮一带最流行的四人牌类游戏，两副牌共 108 张，每人 27 张，与对家配合对抗另两家。它的规则复杂度远超斗地主：牌型有单张、对子、三张、三带二、顺子、连对、钢板、炸弹（4~8 张同点）、同花顺，还有”逢人配”（红桃级牌可当任意牌）和”级牌”（当前打几，该点数即为百搭级牌）。

规则越复杂，算法越好玩。本文聚焦掼蛋 AI 里最硬的两块：手牌拆分（把 27 张牌拆成最少的出牌次数，本质是状态压缩 DP）和级牌概率推断（用多元超几何分布算对手手上有多少张关键牌）。

一、手牌拆分：为什么这是核心问题

掼蛋的胜负几乎由”谁先出完”决定。而”出完”所需的出牌轮次，取决于你怎么把手牌拆成合法牌型。举个直观的例子，手上有 3 4 5 6 7 8 9：

• 拆法 A：34567（顺子）+ 8 + 9，共 3 手；
• 拆法 B：3+4+5+6+7+8+9，全打单张，共 7 手。

同一手牌，拆分方式不同，所需轮次相差一倍多。更复杂的情形是点数集中时：手上 5555 666 777 88，是打 5555 炸弹（1 手）再想别的，还是拆成 555+5？是凑 666 777 钢板（1 手），还是留 666、777 各自三带二？每一种牌型都会抢占其他牌型的原料，局部贪心必然出错。

手拆极易出错，因为每种牌型都与其他牌型的可用性耦合。这是典型的组合优化问题，用状态压缩 DP 才能得到全局最优。

状态表示：13 维计数向量

两副牌去掉大小王后，点数只有 13 种（2~A）。于是任意一手牌都可以用一个 13 维向量 counts[0..12] 表示，counts[i] 是点数 i 的牌的张数（0~8）。

/** 掼蛋手牌：13 个点数的计数向量（两副牌，每点数最多 8 张） */
public final class Hand {
    public static final int RANKS = 13;      // 2,3,...,K,A
    public final int[] counts;

    public Hand(int[] counts) {
        this.counts = counts.clone();
    }

    public int total() {
        int s = 0;
        for (int c : counts) s += c;
        return s;
    }

    /** 关键：用字符串做记忆化的键，避免数组的 equals/hashCode 问题 */
    public String key() {
        StringBuilder sb = new StringBuilder(RANKS);
        for (int c : counts) sb.append((char) ('0' + c));
        return sb.toString();
    }
}

状态转移：枚举所有合法牌型

/** 牌型：用一个 13 维向量表示「这一手打出的牌」 */
public final class Play {
    public final int[] use;
    /** 牌型分类，用于估值权重 */
    public final PlayType type;

    public Play(int[] use, PlayType type) {
        this.use = use;
        this.type = type;
    }

    /** 判断这手牌能否从 hand 中打出 */
    public boolean fitsIn(int[] hand) {
        for (int i = 0; i < Hand.RANKS; i++) {
            if (use[i] > hand[i]) return false;
        }
        return true;
    }

    /** 打出去之后剩下的牌 */
    public int[] subtract(int[] hand) {
        int[] rest = new int[Hand.RANKS];
        for (int i = 0; i < Hand.RANKS; i++) rest[i] = hand[i] - use[i];
        return rest;
    }
}

/** 牌型分类 */
public enum PlayType {
    SINGLE, PAIR, TRIPLE, TRIPLE_WITH_PAIR,
    STRAIGHT, CONSECUTIVE_PAIRS, PLATE, BOMB, STRAIGHT_FLUSH
}

合法牌型的全集可以预先构造一次（约 200 个），之后所有查询都是查表：

import java.util.*;

/** 预构造所有合法牌型（不含逢人配的简化版本） */
public final class PlayGenerator {
    private static final List<Play> ALL = new ArrayList<>();

    static {
        int R = Hand.RANKS;

        // 单张 / 对子 / 三张
        for (int r = 0; r < R; r++) {
            for (int k = 1; k <= 3; k++) {
                int[] u = new int[R];
                u[r] = k;
                ALL.add(new Play(u, k == 1 ? PlayType.SINGLE
                        : k == 2 ? PlayType.PAIR : PlayType.TRIPLE));
            }
        }

        // 三带二（三张 + 另一点数的一对）
        for (int r = 0; r < R; r++) {
            for (int p = 0; p < R; p++) {
                if (p == r) continue;
                int[] u = new int[R];
                u[r] = 3;
                u[p] = 2;
                ALL.add(new Play(u, PlayType.TRIPLE_WITH_PAIR));
            }
        }

        // 顺子：5 张连续（A 可作小，见下方“A 的两义性”）
        for (int s = 0; s + 5 <= R; s++) {
            int[] u = new int[R];
            for (int k = s; k < s + 5; k++) u[k] = 1;
            ALL.add(new Play(u, PlayType.STRAIGHT));
        }

        // 连对：3 组连续对子（6 张）
        for (int s = 0; s + 3 <= R; s++) {
            int[] u = new int[R];
            for (int k = s; k < s + 3; k++) u[k] = 2;
            ALL.add(new Play(u, PlayType.CONSECUTIVE_PAIRS));
        }

        // 钢板：2 组连续三张（6 张）
        for (int s = 0; s + 2 <= R; s++) {
            int[] u = new int[R];
            for (int k = s; k < s + 2; k++) u[k] = 3;
            ALL.add(new Play(u, PlayType.PLATE));
        }

        // 炸弹：4~8 张同点
        for (int r = 0; r < R; r++) {
            for (int k = 4; k <= 8; k++) {
                int[] u = new int[R];
                u[r] = k;
                ALL.add(new Play(u, PlayType.BOMB));
            }
        }
    }

    public static List<Play> all() {
        return ALL;
    }
}

DP：最小出牌次数

import java.util.*;

/** 手牌拆分 DP：求最少出牌次数 */
public class HandSplitter {
    private final Map<String, Integer> memo = new HashMap<>();
    private final List<Play> plays = PlayGenerator.all();

    /**
     * 求这手牌打完所需的最少出牌次数。
     * @param hand 13 维点数计数
     * @param wild 手上剩余的逢人配张数
     */
    public int minPlays(int[] hand, int wild) {
        if (sum(hand) == 0) return 0;
        // 记忆化键必须带上 wild，否则不同万能牌数量的同型手牌会被错误合并
        String k = key(hand) + "|" + wild;
        Integer cached = memo.get(k);
        if (cached != null) return cached;

        // 关键剪枝：每次都「必须」打出最小的那个点数，
        // 否则同一个牌的集合会被不同顺序重复枚举，状态爆炸。
        int first = firstNonZero(hand);

        int best = Integer.MAX_VALUE;
        for (Play p : plays) {
            if (p.use[first] == 0) continue;      // 必须消耗最小点数
            if (!p.fitsIn(hand)) continue;

            int rest = minPlays(p.subtract(hand), wild);
            if (rest + 1 < best) best = rest + 1;
        }
        memo.put(k, best);
        return best;
    }

    private static int sum(int[] a) {
        int s = 0;
        for (int v : a) s += v;
        return s;
    }

    private static int firstNonZero(int[] a) {
        for (int i = 0; i < a.length; i++) if (a[i] > 0) return i;
        return -1;
    }

    private static String key(int[] a) {
        StringBuilder sb = new StringBuilder(a.length);
        for (int v : a) sb.append((char) ('0' + v));
        return sb.toString();
    }
}

“必须消耗最小点数”这条剪枝为什么正确

这是整个 DP 的核心。没有它，同一手牌的 27! 种出牌顺序都会被枚举；有了它，每种牌型集合只会被枚举一次。

正确性来自一个简单的交换论证：设最优拆法中有若干手牌，其中包含点数最小的那张牌 x。那么把”包含 x 的那一手”提前到第一步执行，剩余牌集合完全相同，总次数不变。因此总能构造出一个”第一步就消耗掉 x“的最优解。于是只需在第一步枚举所有包含 x 的合法牌型，递归即可。

这条剪枝的效果极其显著。实测（27 张标准手牌）：

注意最后两行：点数越集中，出牌次数越少（5 次），这符合掼蛋的直觉——同点数多就能凑炸弹/三带二，牌型效率高。而”均匀分布”的手牌反而需要 7 次，因为大量点数只有一个，只能当单张打。

二、逢人配：把”万能牌”变成枚举维度

掼蛋最特殊的地方是红桃级牌可以当任意牌用。设你有 w 张逢人配，那么所有牌型构造都要允许”用部分万能牌补齐”。

暴力做法是把万能牌的所有可能归属都枚举一遍，复杂度 O(R^w)，当 w = 2 时是 169 种，尚可接受；w = 3 时变成 2197 种，开始变慢。更聪明的做法是在牌型匹配时按需补位：

/**
 * 判断能否用手牌（含 w 张万能牌）凑出目标牌型。
 * 策略：先看"缺口"总量，缺口 <= w 即可。
 */
public static boolean canFormWithWild(int[] hand, int[] target, int wild) {
    int deficit = 0;
    for (int i = 0; i < Hand.RANKS; i++) {
        if (target[i] > hand[i]) deficit += target[i] - hand[i];
        // 若某点数手上还有富余，并不能"换成"别的点数，
        // 因此只统计缺口，不做盈余抵扣（这是掼蛋规则的准确表达）
    }
    return deficit <= wild;
}

上面的实现有一处值得注意：盈余不能抵扣缺口。因为掼蛋里不能把多余的 3 换成 5，只有逢人配能变身。这一点与很多”万能牌”卡牌游戏不同，写错了会高估 AI 的能力。

有了它，HandSplitter 的转移只需改成：

// wild 用长度为 1 的数组传递，方便扣减后递归
for (Play p : plays) {
    if (p.use[first] == 0 && wild[0] == 0) continue;   // 万能牌也能充当最小点数
    if (!canFormWithWild(hand, p.use, wild[0])) continue;

    int[] nextWild = {wild[0]};
    int[] rest = subtractWithWild(hand, p.use, nextWild);
    best = Math.min(best, 1 + minPlays(rest, nextWild[0]));
}

subtractWithWild 会优先消耗真实牌、不足部分才扣万能牌——这是掼蛋里正确的消耗顺序，因为万能牌更珍贵：

/** 扣除一手牌，优先消耗真实牌，缺口用万能牌补 */
public static int[] subtractWithWild(int[] hand, int[] target, int[] wildLeft) {
    int[] rest = hand.clone();
    int deficit = 0;
    for (int i = 0; i < Hand.RANKS; i++) {
        int take = Math.min(rest[i], target[i]);
        rest[i] -= take;
        deficit += target[i] - take;      // 真实牌不够的部分
    }
    wildLeft[0] -= deficit;               // 用万能牌抵扣
    return rest;
}

三、级牌概率推断：多元超几何分布

掼蛋另一个算法要点是推断对手手上还有多少张关键牌。假设当前打”5″，那么 5 就是级牌；你若想用炸弹压人，就需要知道对手手上还有多少张同点数的牌。

这是一个标准的多元超几何分布问题：已知自己手上有 k 张某点数，牌堆里该点数共 m 张（两副牌即 m ≤ 8），剩余 8 - k 张散落在其他三家（每家 27 张）里。问某一指定对手手上有 j 张的概率：

P(X = j) = C(27, j) · C(81-27, m-k-j) / C(81, m-k)

其中 81 = 108 – 27 是”我以外”的剩余牌数。

import java.util.*;

/** 多元超几何分布：推断对手手上某点数的张数分布 */
public class HyperGeometric {
    private final double[][] binom;

    public HyperGeometric(int maxN) {
        binom = new double[maxN + 1][maxN + 1];
        for (int i = 0; i <= maxN; i++) {
            binom[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                binom[i][j] = binom[i - 1][j - 1] + (j < i ? binom[i - 1][j] : 0);
            }
        }
    }

    /**
     * 计算指定对手手上有 j 张该点数牌的概率。
     * @param mineInHand  我手上该点数的张数
     * @param totalCopies 该点数在两副牌中的总张数（通常 8）
     * @param j           对手手上的张数
     */
    public double prob(int mineInHand, int totalCopies, int j) {
        int remain = totalCopies - mineInHand;   // 散落在其他三家
        int pool = 81;                            // 我以外的牌数 = 108 - 27
        int oppHand = 27;                         // 指定对手的手牌数
        if (j < 0 || j > Math.min(remain, oppHand)) return 0.0;
        return binom[oppHand][j] * binom[pool - oppHand][remain - j] / binom[pool][remain];
    }

    /** 指定对手至少有 j 张的概率 */
    public double atLeast(int mineInHand, int totalCopies, int j) {
        double s = 0;
        for (int k = j; k <= totalCopies - mineInHand; k++) {
            s += prob(mineInHand, totalCopies, k);
        }
        return Math.min(1.0, s);
    }

    /** 期望张数：直接由比例给出，无需遍历 */
    public double expected(int mineInHand, int totalCopies) {
        return (totalCopies - mineInHand) * 27.0 / 81.0;
    }
}

实测数值：什么情况下对手”很可能有炸弹”

设某点数在两副牌中共 8 张，你自己手上有 k 张，问某一个对手凑出至少 2 张（即可能组成对子以上）的概率：

这张表信息量很大：

• 你一张都没有时，某个对手有 ≥2 张的概率高达 81.9%，期望 2.67 张。这解释了为什么”某点数自己空着”往往意味着对手有牌型可打；
• 你手上已经有 6 张时，对手只可能分到 2 张，期望仅 0.67 张，凑对的概率掉到 10.8%。此时你几乎可以放心把小牌出出去。

再看”对手一张都没有”的概率：

“三家至少一家有”永远是 1.0——因为剩余的牌必然在某一家里。这个看似平凡的事实有实战意义：想知道”这个点数还有没有牌”，你只能问”在谁手里”，而不能问”还有没有”。这在设计 AI 的”是否该炸”决策时是基础前提。

四、决策层：把拆牌与概率组合起来

拆牌 DP 给出”最少几手能出完”，概率模型给出”对手可能有什么牌”。组合起来就能做一手牌的整体评估：

/** 手牌评估：把拆牌次数与对手威胁组合成一个分数 */
public class HandEvaluator {
    private final HandSplitter splitter;
    private final HyperGeometric hyper;

    public HandEvaluator(HandSplitter splitter, HyperGeometric hyper) {
        this.splitter = splitter;
        this.hyper = hyper;
    }

    /**
     * 评估当前手牌的"胜率估计"。
     * @param hand       我的手牌计数
     * @param oppCounts  各对手已出牌数（此处简化用平均值）
     */
    public double evaluate(int[] hand) {
        int total = 0;
        for (int c : hand) total += c;
        if (total == 0) return 1.0;

        int plays = splitter.minPlays(hand, 0);
        // 基础分：出牌次数越少越好。27 张 7 手是基准，每少一手加 0.1
        double score = 0.5 + (7 - plays) * 0.1;

        // 威胁修正：手上有炸弹时加分
        boolean hasBomb = false;
        for (int c : hand) if (c >= 4) hasBomb = true;
        if (hasBomb) score += 0.15;

        // 控制牌修正：大牌（K/A/2）越多越强
        int bigCards = hand[11] + hand[12] + hand[0];   // K, A, 2
        score += Math.min(0.2, bigCards * 0.02);

        return Math.min(1.0, Math.max(0.0, score));
    }

    /**
     * 「该不该炸」的期望判断。
     * @param hand      我的手牌
     * @param rank      考虑用炸弹压制的点数
     * @param mineCount 我手上该点数的张数
     */
    public boolean shouldBomb(int[] hand, int rank, int mineCount) {
        // 对手某家手上没有 4 张以上同点数（即对方无炸弹）的概率
        double pOppNoBomb = 1.0 - hyper.atLeast(mineCount, 8, 4);
        // 我若炸，需要确保后续还能出完。若剩余手数 > 4，炸的收益不足
        int[] rest = hand.clone();
        rest[rank] = Math.max(0, rest[rank] - 4);
        int restPlays = splitter.minPlays(rest, 0);

        // 简单启发：对手大概率无炸弹、且我炸完后仍能在 4 手内出完，才值得炸
        return pOppNoBomb > 0.65 && restPlays <= 4;
    }
}

五、完整工程结构

guandan-ai/
├── src/main/java/com/example/guandan/
│   ├── Hand.java              13 维计数向量
│   ├── Play.java              牌型（用向量表示）
│   ├── PlayType.java          牌型枚举
│   ├── PlayGenerator.java     预构造全部合法牌型
│   ├── HandSplitter.java      手牌拆分 DP（记忆化 + 最小点剪枝）
│   ├── HyperGeometric.java    多元超几何概率
│   ├── HandEvaluator.java     评估与决策
│   └── Main.java              入口：随机手牌 → 拆牌 → 评估
└── pom.xml                     JDK 17+

入口只需几行：

public class Main {
    public static void main(String[] args) {
        // 示例手牌（标准 27 张）：点数 2~A 依次为
        // 2 张 2、0 张 3、2 张 4、2 张 5、3 张 6、2 张 7、2 张 8、
        // 3 张 9、1 张 10、3 张 J、2 张 Q、4 张 K、1 张 A
        int[] hand = {2, 0, 2, 2, 3, 2, 2, 3, 1, 3, 2, 4, 1};

        HandSplitter splitter = new HandSplitter();
        HyperGeometric hyper = new HyperGeometric(110);
        HandEvaluator eval = new HandEvaluator(splitter, hyper);

        int total = 0;
        for (int c : hand) total += c;

        System.out.println("手牌总张数: " + total);
        System.out.println("最少出牌次数: " + splitter.minPlays(hand, 0));
        System.out.println("胜率估计: " + String.format("%.3f", eval.evaluate(hand)));

        // 逐点数看对手持有分布
        for (int r = 0; r < Hand.RANKS; r++) {
            double p2 = hyper.atLeast(hand[r], 8, 2);
            System.out.printf("点数 %2d: 我 %d 张, 对手单家有>=2张概率 %.4f%n", r, hand[r], p2);
        }
    }
}

六、复杂度分析

这里有个反直觉的现象：手牌越”均匀”越快，越”集中”越慢。均匀手牌（每个点数 1~2 张）的可用牌型极少，状态空间自然小；而”七种点数各 4 张”这类手牌能凑出大量炸弹、连对、钢板的组合，分支因子暴涨。这与大多数 DP 问题的直觉相反——不是规模决定复杂度，而是可行解密度决定复杂度。

七、小结

掼蛋把一个组合优化问题和一个概率推断问题缝在了一起：

1. 手牌拆分 DP：用 13 维计数向量做状态、用”必须消耗最小点数”做交换论证式剪枝，把 O(27!) 的排列空间压到几千个状态；
2. 逢人配处理：万能牌不参与状态维度，而是在牌型匹配时按缺口补位，避免 O(R^w) 的组合爆炸；
3. 多元超几何分布：用 C(27,j)·C(54,m-k-j)/C(81,m-k) 精确算出对手持有分布，把”凭感觉”变成”凭数字”。

其中第 1 点的方法论价值最高：“必须处理某一特定元素”是排列型 DP 的通用去重手段。这条思路可以平移到装箱问题、任务调度、集合划分等一大类问题上——只要你能论证”最优解中必有一手包含某个特定元素”，就能把无序枚举变成有序枚举。