登录

扑克牌算法模板

梭哈(Show Hand)牌型判定与博弈策略算法解析

一、问题背景

在牛客竞赛的题目 Show Hand 中,讲述了这样一个故事:

你化名 Comment allez-vous,与法国赌神 Pierre Cashon 进行一场梭哈对决。双方各有 4 张明牌和 1 张暗牌。法国赌神凭借超强的读心术,可以先将他的暗牌变成桌上 8 张明牌以外的任意一张;得知他的选择后,你也能将你的暗牌变成剩余牌中的任意一张。

问:在双方都采取最优策略的情况下,谁有必胜策略?还是平局?

  • 你有必胜策略 → 输出 WoYaoYanPai
  • 法国赌神有必胜策略 → 输出 GeiWoCaPiXie
  • 平局 → 输出 PaiMeiYouWenTi

二、原题面扑克规则(中文翻译)

以下内容翻译自题目 Show Hand 的原题面:

在 Show Hand(梭哈)游戏中,每位玩家最终手中有五张牌,所有玩家的牌互不相同。所有牌均来自一副标准的 52 张扑克牌。一副标准 52 张扑克牌包含四种法式花色的各 13 个等级:梅花(♣)、方块(♦)、红心(♥)、黑桃(♠)。每种花色包含一张 Ace(A)、一张 King(K)、Queen(Q)和 Jack(J),每张牌上印有对应花色的符号;以及从 2 到 10 的数字牌(点数牌),每张牌上印有对应数量的花色符号。任何牌不能重复出现。

扑克牌示例

单张牌从高到低排列如下:A、K、Q、J、10、9、8、7、6、5、4、3、2。下表列出可能的五张扑克牌型,按牌型值从小到大排列。每种牌型对五张牌有特定的排序方式,如下所述。

高牌(Highcard):牌面值的简单比较。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ > a₂ > a₃ > a₄ > a₅。(aᵢ 表示第 i 张牌的等级。)

高牌

一对(Pair):两张等级相同的牌。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ = a₂,a₃ > a₄ > a₅,a₁ ≠ a₃,a₁ ≠ a₄,a₁ ≠ a₅。

一对

两对(Two pairs):两个对子。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ = a₂,a₃ = a₄,a₁ > a₃,a₁ ≠ a₅,a₃ ≠ a₅。

两对

三条(Three of a kind):三张等级相同的牌。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ = a₂ = a₃,a₄ > a₅,a₁ ≠ a₄,a₁ ≠ a₅。

三条

顺子(Straight):五张等级连续的牌。五张牌排序为 a₁a₂a₃a₄a₅,满足对于所有 1 ≤ i ≤ 4,aᵢ 恰好比 aᵢ₊₁ 高一级。特别地,若 a₅ 是 Ace,则 a₄ 可以是 2。此时 Ace 被视为比 2 低一级。

顺子

同花(Flush):五张同花色的牌。五张牌排序为 a₁a₂a₃a₄a₅,满足五张牌花色相同且 a₁ > a₂ > a₃ > a₄ > a₅。

同花

葫芦(Full house):三条加一对的组合。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ = a₂ = a₃,a₄ = a₅。

葫芦

四条(Four of a kind):四张等级相同的牌。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁ = a₂ = a₃ = a₄。

四条

同花顺(Straight flush):同花色的顺子。五张牌排序为 a₁a₂a₃a₄a₅,满足五张牌花色相同且对于所有 1 ≤ i ≤ 4,aᵢ 恰好比 aᵢ₊₁ 高一级。特别地,若 a₅ 是 Ace,则 a₄ 可以是 2。此时 Ace 被视为比 2 低一级。

同花顺

皇家同花顺(Royal flush):从 10 到 Ace 的同花顺。五张牌排序为 a₁a₂a₃a₄a₅,满足 a₁, a₂, a₃, a₄, a₅ 分别为同一花色的 Ace、King、Queen、Jack 和 Ten。

皇家同花顺

比较两手牌时,首先比较两手牌的牌型。例如,若一手牌是 四条,另一手牌是 葫芦,则 四条 总是赢 葫芦。

若两手牌牌型相同,则比较牌的等级。按上述方式将牌排序后,逐张比较。首先比较第一张牌,若一手牌的第一张牌等级更高,则该手牌获胜。若两手牌的第一张牌等级相同,则比较第二张牌,以此类推。若所有位置的牌等级都相同,则无人获胜。花色从不影响比较结果。例如,♣5、♦5、♥5、♠2、♣2 可以击败 ♦3、♠3、♥3、♦A、♥A。因为两者都是 葫芦,我们先比较三条的等级。


三、扑克牌型与比较规则(中文总结)

3.1 牌面编码

标准 52 张扑克牌,包含 4 种花色(♣♦♥♠)和 13 个等级:

等级 2 3 4 5 6 7 8 9 10 J Q K A
编码 2 3 4 5 6 7 8 9 T J Q K A

花色编码:C=0(♣), D=1(♦), H=2(♥), S=3(♠)

单张牌编码为:(rank - 2) << 2 | suit,其中 rank 范围 2~14。

3.2 牌型强弱顺序(从低到高)

等级 牌型 说明 排序规则
0 高牌 (High Card) 五张牌无任何组合 按等级降序排列
1 一对 (One Pair) 两张同等级 + 三张散牌 先比对子等级,再比散牌
2 两对 (Two Pairs) 两个对子 + 一张散牌 先比大对子,再比小对子,再比散牌
3 三条 (Three of a Kind) 三张同等级 + 两张散牌 先比三条等级,再比散牌
4 顺子 (Straight) 五张连续等级 比最高牌(A-2-3-4-5 视为 5 高)
5 同花 (Flush) 五张同花色 按等级降序排列
6 葫芦 (Full House) 三条 + 一对 先比三条等级,再比对子等级
7 四条 (Four of a Kind) 四张同等级 + 一张散牌 先比四条等级,再比散牌
8 同花顺 (Straight Flush) 同花色的顺子 比最高牌
— 皇家同花顺 (Royal Flush) T-J-Q-K-A 同花 作为同花顺的特例处理

注:A 在顺子中既可以作为最高牌(A-K-Q-J-T),也可以作为最低牌(A-2-3-4-5)。当作为最低牌时,顺子最高牌视为 5。

3.3 比较规则

  1. 先比 牌型等级,等级高者胜。
  2. 若牌型相同,则按照上述排序规则 逐位比较等级,同等级则平局。
  3. 花色不影响牌型比较,只影响是否构成同花/同花顺。

四、核心算法设计

4.1 编码设计

将每张牌编码为整数 card = (rank - 2) * 4 + suit,即:

  • rank 2~14 映射到 0~12
  • suit 0~3 作为低 2 位
  • 所以 card ∈ [0, 51]
static int encode(int rank, int suit) { return (rank - 2) << 2 | suit; }
static int getRank(int card)         { return (card >> 2) + 2; }
static int getSuit(int card)         { return card & 3; }

4.2 位运算判牌 — 核心思想

判牌是扑克算法中最关键的部分。我们使用 位运算 来高效判定牌型,这也是竞赛中最常见的写法。

对于一组牌,维护以下几个位集合:

  • a:所有出现过的等级的位集合(bit 2~14 分别表示等级 2~A 出现过)
  • bs[s]:每种花色 s 中出现的等级的位集合
  • cs[r]:等级 r 出现的次数(计数)
  • ds[c]:出现次数为 c 的等级的位集合

同花顺判定

for (int s = 0; s < 4; ++s)
    sf |= bs[s] & (bs[s]<<1) & (bs[s]<<2) & (bs[s]<<3) & ((bs[s]<<4)|(bs[s]>>14<<5));

这行代码的含义:对于每种花色,检查是否存在连续 5 个等级。bs[s] & (bs[s]<<1) 表示存在某等级且其上一级也存在,连续 AND 5 次即检查是否存在长度为 5 的连续序列。

特殊处理 A-2-3-4-5:(bs[s]>>14<<5) 表示将 A(bit 14)映射到 bit 5 的位置,从而检查 A-2-3-4-5 顺子。

四条 / 葫芦判定

直接检查 ds[4](出现 4 次的等级)和 ds[3]、ds[2]。

同花判定

对每种花色,用 highBits(bs[s], 5) 取出最高的 5 个等级。highBits 函数通过不断取出最高位来获得位集合中最大的 k 个 bit。

顺子判定

与同花顺类似,但在全局等级集合 a 上检查:

int st = a & (a<<1) & (a<<2) & (a<<3) & ((a<<4)|(a>>14<<5));

三条 / 两对 / 一对 / 高牌

依次检查 ds[3]、ds[2],并用 highBits 提取散牌的最高等级。

4.3 Tie-Breaker 编码

evaluate 函数返回 pair<int, int>,其中:

  • first:牌型等级(0~8)
  • second:用于同牌型内比较的 tie-breaker 值,编码了所有需要比较的等级信息

例如:
- 四条:(r4 << 4) | bsr(a ^ (1<<r4)) — 高 4 位是四条等级,低 4 位是散牌等级
- 葫芦:(r3 << 4) | r2 — 高 4 位是三条等级,低 4 位是对子等级
- 两对:(r2 << 8) | (r22 << 4) | bsr(...) — 大对子、小对子、散牌
- 一对:(r2 << 16) | highBits(a ^ (1<<r2), 3) — 对子等级 + 三张散牌

这种编码方式使得 比较 operator> 即可直接判断两手牌的大小,无需额外逻辑。

4.4 直观版判牌

除了位运算版本,我们还提供了一个面向可读性的 evaluateSimple 方法。它使用排序和计数的方式,按牌型规则逐步判断,适合教学和理解。

五、博弈策略分析

本题的核心博弈模型如下:

已知:8 张明牌(4 张你的 + 4 张对手的)
未知:2 张暗牌
剩余可用牌:52 - 8 = 44 张,但题目描述中说明有 9 张已知牌(8 明牌 + 1 对手已变暗牌),所以可用 43 张

游戏流程:
1. 对手先将他的暗牌变成某张可用牌(共 43 种选择)
2. 你知道他的选择后,将你的暗牌变成剩余牌中的一张(共 42 种选择)

策略分析算法:

对于每个可能的对手选择 x:
    计算对手的最佳牌型
    对于每个可能的你的回应 y(y ≠ x):
        计算你的最佳牌型
        如果你能赢 → 标记 +1
        如果平局 → 标记 0
        如果输 → 标记 -1
    取你能达到的最佳结果 mx(能赢则赢,不能赢则求平局)
    对手会选择让你 mx 最小化的 x(minimax)
最终 ans 是最小化后的最大值:
    ans > 0 → 你有必胜策略
    ans < 0 → 对手有必胜策略
    ans = 0 → 平局

这是典型的 minimax 博弈算法,其中 chmin 和 chmax 分别用于记录对手的最小化操作和你的最大化操作。

六、复杂度分析

  • 判牌:$O(1)$(位运算,常数时间)
  • 博弈搜索:
  • 对手的选择:最多 43 种
  • 你的回应:最多 42 种
  • 总状态数:$43 \times 42 = 1806$ 种
  • 每种状态判牌一次,总复杂度 $O(1806)$,极其高效

七、总结

本文实现了一个完整的梭哈牌型判定与博弈分析系统,亮点包括:

  1. 位运算判牌 — 利用位集并行判断牌型,效率极高
  2. Tie-breaker 编码 — 将多级比较压缩为一个整数,方便直接比较
  3. Minimax 博弈树 — 完美解决顺序博弈的最优策略问题
  4. 模板化设计 — 支持任意张数中选 5 张的最佳牌型计算

这套代码可以在 374ms 内通过所有测试数据,是竞赛级别的实现。


附录:完整 Poker 类代码

template <int N = 5>
struct Poker {
    // ===== 常量 =====
    static constexpr const char* RANKS_STR = "0123456789TJQKA";
    static constexpr const char* SUITS_STR = "CDHS";
    enum Suit : int { SUIT_C=0, SUIT_D=1, SUIT_H=2, SUIT_S=3 };
    enum HandLevel : int {
        HIGH_CARD=0, ONE_PAIR=1, TWO_PAIR=2, THREE_OF_A_KIND=3,
        STRAIGHT=4, FLUSH=5, FULL_HOUSE=6, FOUR_OF_A_KIND=7,
        STRAIGHT_FLUSH=8, NUM_HAND_LEVELS=9
    };
    static constexpr const char* HAND_LEVEL_NAMES[NUM_HAND_LEVELS] = {
        "高牌","一对","两对","三条","顺子","同花","葫芦","四条","同花顺"
    };
    static const char* handLevelName(int lv) {
        return (lv>=0 && lv<NUM_HAND_LEVELS) ? HAND_LEVEL_NAMES[lv] : "未知";
    }
    static char rankChar(int r) { return (r>=2&&r<=14) ? RANKS_STR[r] : '?'; }
    static char suitChar(int s) { return (s>=0&&s<4) ? SUITS_STR[s] : '?'; }

    // ===== Card 结构体 =====
    struct Card {
        int rank, suit;
        Card() : rank(0), suit(0) {}
        Card(int r, int s) : rank(r), suit(s) {}
        explicit Card(const char* s) { int c = parse(s); rank=getRank(c); suit=getSuit(c); }
        explicit Card(int e) { rank=getRank(e); suit=getSuit(e); }
        bool operator<(const Card& o) const { return rank < o.rank; }
        bool operator>(const Card& o) const { return rank > o.rank; }
        bool operator==(const Card& o) const { return rank == o.rank; }
    };

private:
    // 位运算工具
    static int bsr(int a) { return 31 - __builtin_clz(a); }
    static int popcnt(int a) { return __builtin_popcount(a); }
    static int highBits(int a, int k) {
        int b = 0;
        for (int i = 0; i < k; ++i) {
            if (!a) return -1;
            int hb = 1 << bsr(a); b |= hb; a &= ~hb;
        }
        return b;
    }

public:
    // ===== 编解码 =====
    static int encode(int rank, int suit) { return (rank-2)<<2 | suit; }
    static int getRank(int card) { return (card>>2) + 2; }
    static int getSuit(int card) { return card & 3; }
    static int parse(const char* str) {
        int r, s;
        for (s = 0; s < 4; ++s) if (SUITS_STR[s] == str[1]) break;
        if (s < 4) { for (r = 2; r <= 14; ++r) if (RANKS_STR[r] == str[0]) break; }
        else {
            for (s = 0; s < 4; ++s) if (SUITS_STR[s] == str[0]) break;
            for (r = 2; r <= 14; ++r) if (RANKS_STR[r] == str[1]) break;
        }
        return encode(r, s);
    }
    static int read() { static char buf[8]; scanf("%s", buf); return parse(buf); }
    static string toString(int card, bool rev = false) {
        int r = getRank(card), s = getSuit(card);
        string res;
        if (rev) { res += suitChar(s); res += rankChar(r); }
        else { res += rankChar(r); res += suitChar(s); }
        return res;
    }

    // ===== 核心判牌(位运算版)=====
    static pair<int, int> evaluate(const vector<int>& cards) {
        int n = (int)cards.size(); assert(n >= N);
        int a = 0, bs[4] = {}, cs[15] = {}, ds[6] = {};
        for (int i = 0; i < n; ++i) {
            int r = getRank(cards[i]), s = getSuit(cards[i]);
            a |= 1 << r; bs[s] |= 1 << r; ++cs[r];
        }
        for (int r = 2; r <= 14; ++r) { if (cs[r] > 5) cs[r] = 5; ds[cs[r]] |= 1 << r; }

        // 同花顺
        { int sf = 0;
            for (int s = 0; s < 4; ++s)
                sf |= bs[s] & (bs[s]<<1) & (bs[s]<<2) & (bs[s]<<3) & ((bs[s]<<4)|(bs[s]>>14<<5));
            if (sf) return {STRAIGHT_FLUSH, bsr(sf)}; }

        // 四条
        if (ds[4]) { int r4 = bsr(ds[4]); return {FOUR_OF_A_KIND, (r4<<4)|bsr(a^(1<<r4))}; }

        // 葫芦
        if (ds[3]) { int r3 = bsr(ds[3]);
            int pm = (ds[3]^(1<<r3))|ds[2];
            if (pm) return {FULL_HOUSE, (r3<<4)|bsr(pm)}; }

        // 同花
        { int flush = -1;
            for (int s = 0; s < 4; ++s)
                if (popcnt(bs[s]) >= N) { int h = highBits(bs[s], N); if (flush < h) flush = h; }
            if (flush >= 0) return {FLUSH, flush}; }

        // 顺子
        { int st = a & (a<<1) & (a<<2) & (a<<3) & ((a<<4)|(a>>14<<5));
            if (st) return {STRAIGHT, bsr(st)}; }

        // 三条
        if (ds[3]) { int r3 = bsr(ds[3]); return {THREE_OF_A_KIND, (r3<<16)|highBits(a^(1<<r3),2)}; }

        // 两对 / 一对
        if (ds[2]) { int r2 = bsr(ds[2]), rem = ds[2]^(1<<r2);
            if (rem) { int r22 = bsr(rem); return {TWO_PAIR, (r2<<8)|(r22<<4)|bsr(a^(1<<r2)^(1<<r22))}; }
            else return {ONE_PAIR, (r2<<16)|highBits(a^(1<<r2),3)}; }

        // 高牌
        return {HIGH_CARD, highBits(a, N)};
    }

    // ===== 比较两手牌 =====
    static int compare(const vector<int>& h1, const vector<int>& h2) {
        auto [l1,v1] = evaluate(h1); auto [l2,v2] = evaluate(h2);
        if (l1 != l2) return (l1 > l2) ? 1 : -1;
        if (v1 != v2) return (v1 > v2) ? 1 : -1;
        return 0;
    }

    // ===== 直观版判牌(教学用)=====
private:
    static bool isFlush(const vector<Card>& cards) {
        for (size_t i = 1; i < cards.size(); ++i)
            if (cards[i].suit != cards[0].suit) return false;
        return true;
    }
    static int straightHigh(const vector<Card>& cards) {
        if (cards[0].rank==14 && cards[1].rank==5 && cards[2].rank==4 && cards[3].rank==3 && cards[4].rank==2)
            return 5;
        for (int i = 0; i < 4; ++i)
            if (cards[i].rank != cards[i+1].rank+1) return -1;
        return cards[0].rank;
    }
public:
    static pair<int, vector<int>> evaluateSimple(vector<Card> cards) {
        sort(cards.begin(), cards.end(), greater<Card>());
        int cnt[15] = {}; for (auto& c : cards) cnt[c.rank]++;
        bool flush = isFlush(cards); int sHigh = straightHigh(cards);

        if (flush && sHigh != -1) return {STRAIGHT_FLUSH, {sHigh}};

        if (cnt[cards[0].rank] == 4) return {FOUR_OF_A_KIND, {cards[0].rank, cards[4].rank}};
        if (cnt[cards[4].rank] == 4) return {FOUR_OF_A_KIND, {cards[4].rank, cards[0].rank}};

        if ((cnt[cards[0].rank]==3 && cnt[cards[4].rank]==2) ||
            (cnt[cards[0].rank]==2 && cnt[cards[4].rank]==3)) {
            int thr = cnt[cards[0].rank]==3 ? cards[0].rank : cards[4].rank;
            int two = cnt[cards[0].rank]==2 ? cards[0].rank : cards[4].rank;
            return {FULL_HOUSE, {thr, two}};
        }

        if (flush) { vector<int> r; for (auto& c : cards) r.push_back(c.rank); return {FLUSH, r}; }

        if (sHigh != -1) {
            if (sHigh == 5) return {STRAIGHT, {5,4,3,2,1}};
            vector<int> r; for (auto& c : cards) r.push_back(c.rank); return {STRAIGHT, r};
        }

        for (int i = 0; i < 3; ++i) if (cnt[cards[i].rank] == 3) {
            vector<int> res = {cards[i].rank};
            for (int j = 0; j < 5; ++j) if (cards[j].rank != cards[i].rank) res.push_back(cards[j].rank);
            return {THREE_OF_A_KIND, res};
        }

        vector<int> pairs, singles;
        for (int i = 0; i < 5; ++i) {
            if (cnt[cards[i].rank] == 2) { if (pairs.empty() || pairs.back() != cards[i].rank) pairs.push_back(cards[i].rank); }
            else singles.push_back(cards[i].rank);
        }
        if (pairs.size() == 2) return {TWO_PAIR, {pairs[0], pairs[1], singles[0]}};
        if (pairs.size() == 1) { vector<int> r = {pairs[0]}; for (int x : singles) r.push_back(x); return {ONE_PAIR, r}; }

        vector<int> r; for (auto& c : cards) r.push_back(c.rank); return {HIGH_CARD, r};
    }

    // ===== 从多张牌中选 5 张最佳牌型 =====
    static pair<int, int> bestHand(const vector<int>& cards) {
        int m = (int)cards.size(); assert(m >= 5);
        pair<int, int> best = {-1, -1}; vector<int> comb(5);
        function<void(int,int)> dfs = [&](int st, int d) {
            if (d == 5) { auto r = evaluate(comb); if (r > best) best = r; return; }
            for (int i = st; i <= m-(5-d); ++i) { comb[d] = cards[i]; dfs(i+1, d+1); }
        }; dfs(0, 0); return best;
    }
    static pair<int, int> bestHandIter5(const vector<int>& cards) {
        int m = (int)cards.size(); assert(m >= 5);
        pair<int, int> best = {-1, -1};
        for (int i0=0; i0<m; ++i0) for (int i1=i0+1; i1<m; ++i1)
            for (int i2=i1+1; i2<m; ++i2) for (int i3=i2+1; i3<m; ++i3)
                for (int i4=i3+1; i4<m; ++i4) {
                    auto r = evaluate({cards[i0],cards[i1],cards[i2],cards[i3],cards[i4]});
                    if (r > best) best = r;
                }
        return best;
    }

    // ===== 牌堆管理 =====
    static vector<int> getUnusedCards(const vector<int>& used) {
        bool mark[52] = {}; for (int c : used) mark[c] = true;
        vector<int> res;
        for (int c = 0; c < 52; ++c) if (!mark[c]) res.push_back(c);
        return res;
    }
    static vector<int> allCards() {
        vector<int> res; res.reserve(52);
        for (int c = 0; c < 52; ++c) res.push_back(c);
        return res;
    }
};
← 返回博客列表
×