每日算法 — 使用java实现斗牛：组合枚举与动态规划最优组牌策略

引言

斗牛（又称”牛牛”）是一种流行的扑克牌游戏，玩家从五张手牌中选出三张使其点数之和为10的倍数（称为”有牛”），剩余两张之和的个位数决定牌型大小。看似简单的规则背后，隐藏着组合枚举与动态规划的最优策略问题。本文用Java实现组合枚举判断牌型与动态规划最优组牌算法，并深入分析各类牌型的出现概率。

核心算法设计

1. 牌型组合枚举

从5张牌中选3张，共有C(5,3)=10种组合。对每种组合判断其点数之和是否为10的倍数。由于10、J、Q、K均计为10点，实际计算时需先对10取模。

2. 动态规划最优组牌

在某些变体规则中，若存在多种”有牛”组合，需选择使剩余两张牌点数最大的方案。这本质上是一个带约束的最优化问题，可用动态规划求解：设dp[i][j]表示前i张牌中选取若干张，使其点数之和模10等于j的最大可能值。

3. 牌型概率计算

通过枚举所有可能的五张牌组合（从52张牌中选5张，共2,598,960种），统计各牌型出现频率。

完整Java实现

import java.util.*;

/**
 * 斗牛游戏核心算法实现
 * 包含组合枚举牌型判断、动态规划最优组牌与概率统计
 */
public class BullFight {

    // 扑克牌定义
    static class Card {
        int suit;   // 花色: 0=黑桃, 1=红桃, 2=梅花, 3=方片
        int rank;   // 点数: 1=A, 2-10, 11=J, 12=Q, 13=K

        Card(int suit, int rank) {
            this.suit = suit;
            this.rank = rank;
        }

        // 斗牛点数：J/Q/K/10均为10点，其余为面值
        int bullValue() {
            return rank >= 10 ? 10 : rank;
        }

        // 实际点数（用于计算牛几）
        int pointValue() {
            return rank >= 10 ? 10 : rank;
        }

        @Override public String toString() {
            String[] suits = {"♠", "♥", "♣", "♦"};
            String[] ranks = {"", "A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
            return suits[suit] + ranks[rank];
        }
    }

    // 牌型枚举
    enum HandType {
        NO_BULL("无牛", 1),
        BULL_1("牛一", 2), BULL_2("牛二", 3), BULL_3("牛三", 4),
        BULL_4("牛四", 5), BULL_5("牛五", 6), BULL_6("牛六", 7),
        BULL_7("牛七", 8), BULL_8("牛八", 9), BULL_9("牛九", 10),
        BULL_BULL("牛牛", 15),
        FOUR_BULL("四花牛", 20),      // 四张花牌(J/Q/K)
        FIVE_BULL("五花牛", 25);      // 五张花牌

        final String name;
        final int multiplier; // 赔率倍数
        HandType(String name, int mul) { this.name = name; this.multiplier = mul; }
    }

    /**
     * 组合枚举法判断牌型
     * 从5张牌中枚举C(5,3)=10种三张组合，判断是否有和为10的倍数的组合
     */
    public static HandType evaluateHand(Card[] hand) {
        if (hand.length != 5) throw new IllegalArgumentException("必须5张牌");

        // 检查特殊牌型：四花牛、五花牛
        int faceCards = 0; // J/Q/K的数量
        for (Card c : hand) {
            if (c.rank >= 11) faceCards++;
        }
        if (faceCards == 5) return HandType.FIVE_BULL;
        if (faceCards == 4) {
            // 检查剩余一张是否为10
            for (Card c : hand) {
                if (c.rank == 10) return HandType.FOUR_BULL;
            }
        }

        // 枚举所有C(5,3)=10种三张组合
        int bestRemainder = 0;
        boolean hasBull = false;

        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    int sum3 = hand[i].bullValue() + hand[j].bullValue() + hand[k].bullValue();
                    if (sum3 % 10 == 0) {
                        // 有牛，计算剩余两张的点数和
                        int[] remainIdx = new int[2];
                        int idx = 0;
                        for (int m = 0; m < 5; m++) {
                            if (m != i && m != j && m != k) remainIdx[idx++] = m;
                        }
                        int sum2 = hand[remainIdx[0]].bullValue() + hand[remainIdx[1]].bullValue();
                        int remainder = sum2 % 10;
                        if (remainder == 0) remainder = 10; // 牛牛
                        if (!hasBull || remainder > bestRemainder) {
                            bestRemainder = remainder;
                        }
                        hasBull = true;
                    }
                }
            }
        }

        if (!hasBull) return HandType.NO_BULL;
        if (bestRemainder == 10) return HandType.BULL_BULL;
        return HandType.values()[bestRemainder]; // BULL_1到BULL_9
    }

    /**
     * 动态规划最优组牌策略
     * 当存在多种"有牛"方案时，选择使剩余两张牌点数之和最大的方案
     * dp[i][j] = 前i张牌中选若干张，模10余j时的最大点数和
     */
    public static int[] optimalGroupingDP(Card[] hand) {
        if (hand.length != 5) return null;

        // dp[j]表示模10余j时的最大点数和
        int[] dp = new int[10];
        Arrays.fill(dp, -1);
        dp[0] = 0; // 选0张，和为0

        // 记录选择路径
        int[][] choice = new int[10][6]; // choice[j][i]表示第i张牌是否选

        for (int i = 0; i < 5; i++) {
            int val = hand[i].bullValue();
            int[] newDp = dp.clone();
            for (int j = 0; j < 10; j++) {
                if (dp[j] >= 0) {
                    int newMod = (j + val) % 10;
                    int newSum = dp[j] + val;
                    if (newSum > newDp[newMod]) {
                        newDp[newMod] = newSum;
                    }
                }
            }
            dp = newDp;
        }

        // 寻找选3张且模10为0的方案
        // 这里简化处理：dp只记录和，不记录张数
        // 更精确的DP需要增加维度记录选取张数

        // 精确DP：dp[count][mod] = 最大点数和
        int[][] dpExact = new int[4][10];
        for (int[] row : dpExact) Arrays.fill(row, -1);
        dpExact[0][0] = 0;

        for (int i = 0; i < 5; i++) {
            int val = hand[i].bullValue();
            for (int cnt = 2; cnt >= 0; cnt--) {
                for (int mod = 0; mod < 10; mod++) {
                    if (dpExact[cnt][mod] >= 0) {
                        int newCnt = cnt + 1;
                        int newMod = (mod + val) % 10;
                        int newSum = dpExact[cnt][mod] + val;
                        if (newSum > dpExact[newCnt][newMod]) {
                            dpExact[newCnt][newMod] = newSum;
                        }
                    }
                }
            }
        }

        // 找选3张模10为0的最佳方案
        if (dpExact[3][0] < 0) return new int[]{-1, 0}; // 无牛

        // 回溯找出选了哪3张（简化版，实际需要记录parent指针）
        // 这里返回剩余两张的最大可能点数
        int totalPoints = 0;
        for (Card c : hand) totalPoints += c.bullValue();
        int remainMax = totalPoints - dpExact[3][0];
        int bullNumber = remainMax % 10;
        if (bullNumber == 0) bullNumber = 10;

        return new int[]{bullNumber, remainMax};
    }

    /**
     * 蒙特卡洛模拟统计牌型概率
     */
    public static Map<HandType, Integer> monteCarloProbability(int iterations) {
        Map<HandType, Integer> counts = new HashMap<>();
        for (HandType t : HandType.values()) counts.put(t, 0);

        Random rand = new Random();
        for (int i = 0; i < iterations; i++) {
            List<Card> deck = generateDeck();
            Collections.shuffle(deck, rand);
            Card[] hand = deck.subList(0, 5).toArray(new Card[0]);
            HandType type = evaluateHand(hand);
            counts.put(type, counts.get(type) + 1);
        }
        return counts;
    }

    /**
     * 精确概率计算：枚举所有C(52,5)种组合
     * 注意：此计算量极大(2,598,960种)，仅适合离线统计
     */
    public static Map<HandType, Long> exactProbability() {
        Map<HandType, Long> counts = new HashMap<>();
        for (HandType t : HandType.values()) counts.put(t, 0L);

        List<Card> deck = generateDeck();
        Card[] hand = new Card[5];
        long total = combinationEnum(deck, 0, 0, hand, counts);

        System.out.println("总组合数: " + total);
        return counts;
    }

    private static long combinationEnum(List<Card> deck, int start, int depth, 
                                         Card[] hand, Map<HandType, Long> counts) {
        if (depth == 5) {
            HandType type = evaluateHand(hand.clone());
            counts.put(type, counts.get(type) + 1);
            return 1;
        }
        long total = 0;
        for (int i = start; i <= deck.size() - (5 - depth); i++) {
            hand[depth] = deck.get(i);
            total += combinationEnum(deck, i + 1, depth + 1, hand, counts);
        }
        return total;
    }

    private static List<Card> generateDeck() {
        List<Card> deck = new ArrayList<>();
        for (int s = 0; s < 4; s++) {
            for (int r = 1; r <= 13; r++) {
                deck.add(new Card(s, r));
            }
        }
        return deck;
    }

    // 演示主方法
    public static void main(String[] args) {
        // 测试牌型判断
        System.out.println("=== 牌型判断测试 ===");
        Card[] hand1 = {
            new Card(0, 10), new Card(1, 10), new Card(2, 10),
            new Card(0, 2), new Card(1, 8)
        };
        System.out.println("手牌: " + Arrays.toString(hand1));
        System.out.println("牌型: " + evaluateHand(hand1).name);

        Card[] hand2 = {
            new Card(0, 7), new Card(1, 8), new Card(2, 5),
            new Card(0, 3), new Card(1, 7)
        };
        System.out.println("\n手牌: " + Arrays.toString(hand2));
        System.out.println("牌型: " + evaluateHand(hand2).name);

        // 动态规划最优组牌
        System.out.println("\n=== 动态规划最优组牌 ===");
        int[] result = optimalGroupingDP(hand2);
        System.out.printf("最优组牌结果: 牛%d, 剩余点数和=%d%n", result[0], result[1]);

        // 蒙特卡洛概率统计
        System.out.println("\n=== 蒙特卡洛概率统计 (10万次) ===");
        Map<HandType, Integer> mc = monteCarloProbability(100000);
        for (HandType t : HandType.values()) {
            double pct = mc.get(t) * 100.0 / 100000;
            System.out.printf("%-10s: %.3f%% (%d次)%n", t.name, pct, mc.get(t));
        }
    }
}

算法复杂度分析

由于手牌固定为5张，所有牌型判断算法均为常数时间。

扩展思考

1. 多人博弈分析：引入博弈论中的纳什均衡概念，分析在不同下注规则下的最优策略。
2. 牌型概率优化：通过预计算表（Lookup Table）将牌型判断优化至O(1)且无需循环。
3. 机器学习预测：利用历史对局数据训练神经网络，预测对手牌型分布概率，辅助下注决策。