每日算法 — 使用java实现斗地主：组合数学牌型识别与贪心出牌策略

引言

斗地主是中国最经典的扑克牌游戏之一，三人对抗的玩法融合了运气与策略。作为AI算法研究者，我们可以将斗地主抽象为组合数学与贪心决策问题：如何枚举所有合法牌型、评估手牌价值、以及制定最优出牌策略。本文将用Java实现斗地主的核心牌型识别引擎与贪心AI决策系统。

问题建模

一副扑克54张（含大小王），三人游戏每人17张，留3张底牌。斗地主的算法核心包括：

1. 牌型表示：如何高效表示手牌，支持快速的牌型检测与出牌操作
2. 牌型识别：给定一组牌，判断它们构成什么牌型（单张、对子、三张、顺子、连对、飞机、炸弹等）
3. 合法出牌：给定当前出牌，计算手牌中所有能压过的牌型组合
4. 贪心策略：在多个可选出牌中，选择最优策略（尽快走完、保留炸弹、配合队友等）

核心算法设计

1. 手牌表示

使用计数数组表示手牌，索引0-12对应3-A-2（斗地主点数顺序），索引13为小王，14为大王。数组值表示该点数的牌数量（0-4）。

2. 牌型枚举

斗地主共有约15种牌型，可分为：
– 单牌型：单张、对子、三张、炸弹、王炸
– 带牌型：三带一、三带二、四带二
– 连续型：单顺（5+连张）、连对（3+连对）、飞机（2+连三）

对于带牌和连续型，需要组合数学枚举所有可能。

3. 贪心出牌策略

核心启发式：
– 优先出非炸弹的牌型，保留炸弹到最后
– 优先出难以组成的牌型（如长顺子），保留灵活的牌
– 牌力评估：计算每种出牌后剩余手牌的”走牌难度”
– 压牌策略：对手出牌时，能用最小代价压住则压，否则选择过

Java完整实现

import java.util.*;

/**
 * 斗地主牌型识别与贪心出牌策略实现
 */
public class DoudizhuAI {

    // 点数：3,4,5,6,7,8,9,10,J,Q,K,A,2,小王,大王
    private static final String[] RANK_NAMES = {
        "3","4","5","6","7","8","9","10","J","Q","K","A","2","小王","大王"
    };

    // 牌型定义
    enum HandType {
        INVALID,        // 无效
        SINGLE,         // 单张
        PAIR,           // 对子
        TRIPLE,         // 三张
        BOMB,           // 炸弹
        ROCKET,         // 王炸
        TRIPLE_SINGLE,  // 三带一
        TRIPLE_PAIR,    // 三带二
        STRAIGHT,       // 单顺（5张及以上）
        DOUBLE_STRAIGHT,// 连对（3对及以上）
        PLANE,          // 飞机（2个及以上连续三张）
        PLANE_SINGLE,   // 飞机带翅膀（单张）
        PLANE_PAIR,     // 飞机带翅膀（对子）
        FOUR_TWO_SINGLE,// 四带二（单张）
        FOUR_TWO_PAIR   // 四带二（对子）
    }

    static class CardGroup {
        HandType type;
        int mainRank;      // 主牌点数（如三带一的主牌是三张的点数）
        int length;        // 连续型牌型的长度（如顺子长度）
        List<Integer> cards; // 实际使用的牌（点数索引）

        CardGroup(HandType type, int mainRank, int length, List<Integer> cards) {
            this.type = type;
            this.mainRank = mainRank;
            this.length = length;
            this.cards = cards;
        }

        /**
         * 判断当前牌型是否能压住other
         */
        boolean beats(CardGroup other) {
            if (other == null) return true; // 首家出牌
            if (this.type == HandType.ROCKET) return true;
            if (other.type == HandType.ROCKET) return false;
            if (this.type == HandType.BOMB && other.type != HandType.BOMB) return true;
            if (this.type != HandType.BOMB && other.type == HandType.BOMB) return false;
            if (this.type != other.type) return false;
            if (this.length != other.length) return false;
            return this.mainRank > other.mainRank;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(type.name() + "[");
            for (int c : cards) sb.append(RANK_NAMES[c]).append(" ");
            return sb.append("]").toString();
        }
    }

    /**
     * 手牌类：使用计数数组表示
     */
    static class Hand {
        int[] count = new int[15]; // 各点数牌的数量
        int totalCards = 0;

        void addCard(int rank) {
            count[rank]++;
            totalCards++;
        }

        void removeCards(List<Integer> cards) {
            for (int c : cards) {
                count[c]--;
                totalCards--;
            }
        }

        Hand copy() {
            Hand h = new Hand();
            System.arraycopy(this.count, 0, h.count, 0, 15);
            h.totalCards = this.totalCards;
            return h;
        }

        boolean isEmpty() {
            return totalCards == 0;
        }
    }

    /**
     * 识别一组牌构成的牌型
     */
    static CardGroup identifyHandType(int[] cardCounts) {
        List<Integer> cards = new ArrayList<>();
        for (int i = 0; i < 15; i++) {
            for (int j = 0; j < cardCounts[i]; j++) cards.add(i);
        }

        int n = cards.size();

        // 王炸
        if (n == 2 && cardCounts[13] == 1 && cardCounts[14] == 1) {
            return new CardGroup(HandType.ROCKET, 14, 1, cards);
        }

        // 单张
        if (n == 1) {
            return new CardGroup(HandType.SINGLE, cards.get(0), 1, cards);
        }

        // 对子
        if (n == 2 && cardCounts[cards.get(0)] == 2) {
            return new CardGroup(HandType.PAIR, cards.get(0), 1, cards);
        }

        // 三张
        if (n == 3 && cardCounts[cards.get(0)] == 3) {
            return new CardGroup(HandType.TRIPLE, cards.get(0), 1, cards);
        }

        // 炸弹
        if (n == 4 && cardCounts[cards.get(0)] == 4) {
            return new CardGroup(HandType.BOMB, cards.get(0), 1, cards);
        }

        // 三带一
        if (n == 4) {
            for (int i = 0; i < 15; i++) {
                if (cardCounts[i] == 3) {
                    return new CardGroup(HandType.TRIPLE_SINGLE, i, 1, cards);
                }
            }
        }

        // 三带二
        if (n == 5) {
            for (int i = 0; i < 15; i++) {
                if (cardCounts[i] == 3) {
                    return new CardGroup(HandType.TRIPLE_PAIR, i, 1, cards);
                }
            }
        }

        // 顺子（5张及以上连续单张，2和王不能参与）
        if (n >= 5) {
            boolean isStraight = true;
            Collections.sort(cards);
            for (int i = 1; i < n; i++) {
                if (cards.get(i) - cards.get(i-1) != 1 || cards.get(i) >= 13) {
                    isStraight = false; break;
                }
            }
            if (isStraight) {
                return new CardGroup(HandType.STRAIGHT, cards.get(n-1), n, cards);
            }
        }

        // 连对（3对及以上连续对子）
        if (n >= 6 && n % 2 == 0) {
            List<Integer> pairs = new ArrayList<>();
            for (int i = 0; i < 13; i++) {
                if (cardCounts[i] == 2) pairs.add(i);
            }
            if (pairs.size() == n / 2 && pairs.size() >= 3) {
                boolean isDoubleStraight = true;
                for (int i = 1; i < pairs.size(); i++) {
                    if (pairs.get(i) - pairs.get(i-1) != 1) isDoubleStraight = false;
                }
                if (isDoubleStraight) {
                    return new CardGroup(HandType.DOUBLE_STRAIGHT, pairs.get(pairs.size()-1), pairs.size(), cards);
                }
            }
        }

        // 飞机（2个及以上连续三张）
        if (n >= 6 && n % 3 == 0) {
            List<Integer> triples = new ArrayList<>();
            for (int i = 0; i < 13; i++) {
                if (cardCounts[i] == 3) triples.add(i);
            }
            if (triples.size() == n / 3 && triples.size() >= 2) {
                boolean isPlane = true;
                for (int i = 1; i < triples.size(); i++) {
                    if (triples.get(i) - triples.get(i-1) != 1) isPlane = false;
                }
                if (isPlane) {
                    return new CardGroup(HandType.PLANE, triples.get(triples.size()-1), triples.size(), cards);
                }
            }
        }

        return new CardGroup(HandType.INVALID, -1, 0, cards);
    }

    /**
     * 生成手牌中所有能压过target的出牌方案
     */
    static List<CardGroup> getValidPlays(Hand hand, CardGroup target) {
        List<CardGroup> validPlays = new ArrayList<>();

        // 如果target为null，生成所有合法牌型
        if (target == null) {
            generateAllHandTypes(hand, validPlays);
            return validPlays;
        }

        // 王炸直接压
        if (hand.count[13] == 1 && hand.count[14] == 1) {
            List<Integer> rocket = Arrays.asList(13, 14);
            validPlays.add(new CardGroup(HandType.ROCKET, 14, 1, rocket));
        }

        // 炸弹压非炸弹
        if (target.type != HandType.ROCKET && target.type != HandType.BOMB) {
            for (int i = 0; i < 13; i++) {
                if (hand.count[i] == 4) {
                    List<Integer> bomb = new ArrayList<>();
                    for (int j = 0; j < 4; j++) bomb.add(i);
                    validPlays.add(new CardGroup(HandType.BOMB, i, 1, bomb));
                }
            }
        }

        // 同类型压制
        switch (target.type) {
            case SINGLE:
                for (int i = target.mainRank + 1; i < 15; i++) {
                    if (hand.count[i] >= 1) {
                        validPlays.add(new CardGroup(HandType.SINGLE, i, 1, Arrays.asList(i)));
                    }
                }
                break;
            case PAIR:
                for (int i = target.mainRank + 1; i < 13; i++) {
                    if (hand.count[i] >= 2) {
                        validPlays.add(new CardGroup(HandType.PAIR, i, 1, Arrays.asList(i, i)));
                    }
                }
                break;
            case TRIPLE:
                for (int i = target.mainRank + 1; i < 13; i++) {
                    if (hand.count[i] >= 3) {
                        validPlays.add(new CardGroup(HandType.TRIPLE, i, 1, Arrays.asList(i, i, i)));
                    }
                }
                break;
            case TRIPLE_SINGLE:
                for (int i = target.mainRank + 1; i < 13; i++) {
                    if (hand.count[i] >= 3) {
                        for (int j = 0; j < 15; j++) {
                            if (j != i && hand.count[j] >= 1) {
                                List<Integer> cards = new ArrayList<>(Arrays.asList(i, i, i, j));
                                validPlays.add(new CardGroup(HandType.TRIPLE_SINGLE, i, 1, cards));
                            }
                        }
                    }
                }
                break;
            case STRAIGHT:
                int len = target.length;
                for (int start = 0; start <= 13 - len; start++) {
                    if (start + len - 1 <= target.mainRank) continue;
                    boolean canForm = true;
                    for (int i = start; i < start + len; i++) {
                        if (hand.count[i] < 1 || i >= 13) canForm = false;
                    }
                    if (canForm) {
                        List<Integer> cards = new ArrayList<>();
                        for (int i = start; i < start + len; i++) cards.add(i);
                        validPlays.add(new CardGroup(HandType.STRAIGHT, start + len - 1, len, cards));
                    }
                }
                break;
            case BOMB:
                for (int i = target.mainRank + 1; i < 13; i++) {
                    if (hand.count[i] == 4) {
                        List<Integer> bomb = new ArrayList<>();
                        for (int j = 0; j < 4; j++) bomb.add(i);
                        validPlays.add(new CardGroup(HandType.BOMB, i, 1, bomb));
                    }
                }
                break;
            // 其他类型类似处理...
        }

        return validPlays;
    }

    /**
     * 生成所有可能的出牌（首家出牌时）
     */
    static void generateAllHandTypes(Hand hand, List<CardGroup> result) {
        // 单张
        for (int i = 0; i < 15; i++) {
            if (hand.count[i] >= 1) result.add(new CardGroup(HandType.SINGLE, i, 1, Arrays.asList(i)));
        }
        // 对子
        for (int i = 0; i < 13; i++) {
            if (hand.count[i] >= 2) result.add(new CardGroup(HandType.PAIR, i, 1, Arrays.asList(i, i)));
        }
        // 三张
        for (int i = 0; i < 13; i++) {
            if (hand.count[i] >= 3) result.add(new CardGroup(HandType.TRIPLE, i, 1, Arrays.asList(i, i, i)));
        }
        // 炸弹
        for (int i = 0; i < 13; i++) {
            if (hand.count[i] == 4) result.add(new CardGroup(HandType.BOMB, i, 1, Arrays.asList(i, i, i, i)));
        }
        // 王炸
        if (hand.count[13] == 1 && hand.count[14] == 1) {
            result.add(new CardGroup(HandType.ROCKET, 14, 1, Arrays.asList(13, 14)));
        }
        // 更多类型可继续扩展...
    }

    /**
     * 贪心策略：评估一手牌的价值
     * 值越小越好走（牌型越整齐）
     */
    static int evaluateHand(Hand hand) {
        int score = 0;
        // 剩余牌越少越好
        score += hand.totalCards * 10;
        // 零散单牌扣分
        for (int i = 0; i < 13; i++) {
            if (hand.count[i] == 1) score += 5;
        }
        // 保留炸弹加分（最后出）
        for (int i = 0; i < 13; i++) {
            if (hand.count[i] == 4) score -= 20;
        }
        return score;
    }

    /**
     * 贪心选择最优出牌
     */
    static CardGroup selectBestPlay(Hand hand, List<CardGroup> options) {
        if (options.isEmpty()) return null;

        CardGroup best = null;
        int bestScore = Integer.MAX_VALUE;

        for (CardGroup play : options) {
            Hand after = hand.copy();
            after.removeCards(play.cards);
            int score = evaluateHand(after);

            // 如果出完所有牌，优先级最高
            if (after.isEmpty()) score = Integer.MIN_VALUE;

            if (score < bestScore) {
                bestScore = score;
                best = play;
            }
        }

        return best;
    }

    public static void main(String[] args) {
        // 构造示例手牌：3,3,3,4,5,6,7,8,9,10,J,Q,K,A,A,2,大王
        Hand hand = new Hand();
        int[] sample = {0,0,0, 1,2,3,4,5,6,7,8,9,10,10, 12, 14};
        for (int c : sample) hand.addCard(c);

        System.out.println("手牌: " + Arrays.toString(sample));
        System.out.println("可出牌型数量: " + getValidPlays(hand, null).size());

        // 对手出了一张5
        CardGroup opponentPlay = new CardGroup(HandType.SINGLE, 2, 1, Arrays.asList(2));
        System.out.println("\n对手出: " + opponentPlay);

        List<CardGroup> responses = getValidPlays(hand, opponentPlay);
        System.out.println("可压制方案数量: " + responses.size());

        CardGroup best = selectBestPlay(hand, responses);
        System.out.println("AI最优应对: " + best);
    }
}

复杂度分析

算法优化方向

1. 带牌枚举优化：三带一、飞机带翅膀需要枚举所有带牌组合，可用回溯法系统生成
2. 连续型牌型识别：顺子、连对、飞机的检测可用滑动窗口优化
3. 蒙特卡洛模拟：通过大量随机对局模拟评估出牌选择的胜率
4. 强化学习：使用DQN训练斗地主AI，学习复杂的出牌策略

总结

斗地主AI的核心在于组合数学枚举所有合法牌型，以及贪心启发式评估手牌价值。通过计数数组表示手牌，我们可以高效地进行牌型检测和出牌模拟。虽然贪心策略在简单场景下表现良好，但面对复杂牌局时，结合蒙特卡洛模拟或强化学习才是通往顶级AI的必经之路。