梭哈(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 比较规则
- 先比 牌型等级,等级高者胜。
- 若牌型相同,则按照上述排序规则 逐位比较等级,同等级则平局。
- 花色不影响牌型比较,只影响是否构成同花/同花顺。
四、核心算法设计
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)$,极其高效
七、总结
本文实现了一个完整的梭哈牌型判定与博弈分析系统,亮点包括:
- 位运算判牌 — 利用位集并行判断牌型,效率极高
- Tie-breaker 编码 — 将多级比较压缩为一个整数,方便直接比较
- Minimax 博弈树 — 完美解决顺序博弈的最优策略问题
- 模板化设计 — 支持任意张数中选 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;
}
};