【美团杯2021】D. 德州扑克 - 题目

这是一道交互题

在正式比赛中出一道 AI 打牌题一直都是九条可怜的梦想，今天她总算圆梦了。

蒜斜这学期选修了《德州扑克》这门课。马上就要期末考试了，蒜斜喊来了他的好朋友小美来帮他特训德州扑克技术。

今天是特训的第一天，小美希望能够充分地锻炼蒜斜的运算能力。因此，她选择了一种固定的策略（见任务小节）并把这种策略告诉了蒜斜。而蒜斜的目标就是在已知小美策略的情况下，赢得尽可能多的筹码。

然而，蒜斜实在是不擅长这一类大计算题。为了不在小美面前出丑，他希望你能帮他找到一个足够好的策略，使得他可以赢得足够数量的筹码。

规则

以下规则和标准的德州扑克规则完全相同

一副去掉大小王的扑克牌包含 $13$ 种不同的数值：$2,3,4,5,6,7,8,9,T,J,Q,K,A$，它们的大小从左到右依次递增。扑克牌中有四种不同的花色，用 $0,1,2,3$ 表示，每一种花色都有 $13$ 张牌，分别对应每一种数值。在德州扑克中，我们只需要考虑这 $52$ 张牌。

一副手牌包含 $5$ 张扑克牌，他们可能会形成若干种牌型，按照从大到小的顺序依次为：

同花顺：花色相同的顺子（顺子的定义见下方），例如同花色的 $T,J,Q,K,A$。
四条：存在四张大小相同的牌，例如任意花色的 $T,T,T,T,2$。
葫芦：有三张牌大小相同，另外两张牌大小相同，例如任意花色的 $T,T,T,J,J$。
同花：五张牌花色相同，例如同花色的 $7, J,Q,K,A$。
顺子：五张牌大小连续，例如任意花色的 $2,3,4,5,6$, $T,J,Q,K,A$。特殊地，$A,2,3,4,5$ 也是一个顺子（但是 $K,A,2,3,4$ 不是）。因此一共有 $10$ 种不同数值的顺子，它们的第一张牌分别是 $A,2,3,4,5,6,7,8,9,T$。
三条：存在三张大小相同的牌，例如任意花色的 $T,T,T,J,Q$。
两对：存在两个大小不同的对子（一个对子是两张大小一样的牌），例如任意花色的 $T,T,Q,Q,K$。
对子：存在两张大小相同的牌，例如任意花色的 $T,T,J,Q,K$。
高牌：不满足以上任何一个牌型的手牌都是高牌。

一副手牌可能同时满足很多个不同的牌型，这个时候我们会把最大的那个牌型作为这副手牌的牌型。

我们可以通过如下方式来比较两副手牌的大小：

如果两副手牌牌型不同，那么牌型较大的手牌更大。
如果两副手牌都是顺子或者都是同花顺，那么按照顺子第一张牌的大小排序，从小到大分别为 $A,2,3,4,5,6,7,8,9,T$，即 $A,2,3,4,5$ 是最小的顺子，$T,J,Q,K,A$ 是最大的顺子。
否则，我们按照（出现次数，数值）的双关键字从大到小把这五张牌排序，例如 $K,K,T,T,T$ 排序后就是 $T,T,T,K,K$；$2,T,T,K,A$ 排序后是 $T,T,A,K,2$。
比较两副牌的字典序。

注意，牌的花色只影响第一步比较牌型，并不影响后面两步的比大小。

下面是一些例子：

相同花色的 $5,6,7,8,9$ 大于相同花色的 $A,2,3,4,5$。
相同花色的 $A,2,3,4,5$ 大于相同花色的 $2,4,5,6,7$。
任意花色的 $3,3,8,8,K$ 大于任意花色的 $5,5,7,7,A$。
任意花色的 $Q,Q,Q,T,T$ 大于任意花色的 $J,J,J,A,A$。

在德州扑克中，一个人的场面包含 $7$ 张扑克牌，这 $7$ 张牌可以形成 $\binom{7}{5}$ 种不同的手牌，而这个人场面的大小等于这些手牌中最大的那一个。

以下规则和标准的德州扑克规则略有不同

每一局德州扑克的游戏都包含五个阶段：

准备阶段
1. 首先，所有的 $52$ 张牌被完全均匀地打乱（即 $52!$ 种顺序等概率出现）。
2. 蒜斜抽取这 $52$ 张牌中最前面的 $2$ 张作为底牌，小美抽取剩下的 $50$ 牌中最前面的 $2$ 张作为底牌。每个人只能看见自己的底牌。
3. 游戏的彩池被设置为 $10$ 枚筹码，同时，小美和蒜斜各获得 $100$ 枚筹码。
轮次 1
1. 蒜斜和小美进行一轮下注（下注规则见后文）。
2. 剩下的 $48$ 张牌的最前面 $3$ 张被公开（双方都能看见）。
轮次 2
1. 蒜斜和小美进行一轮下注（下注规则见后文）。
2. 剩下的 $45$ 张牌的最前面 $1$ 张被公开（双方都能看见）。
轮次 3
1. 蒜斜和小美进行一轮下注（下注规则见后文）。
2. 剩下的 $44$ 张牌的最前面 $1$ 张被公开（双方都能看见）。
轮次 4
1. 蒜斜和小美进行一轮下注（下注规则见后文）。
2. 每个人的场面由自己在准备阶段摸的 $2$ 张牌加上公开的 $5$ 张牌组成，两个人场面较大的一方赢。如果场面大小相同，则平局。游戏结束。

下面给出一种平局的情况：假设蒜斜和小美的手牌分别是花色 $0$ 的 $2,3$ 和花色 $1$ 的 $2,3$，公共牌是花色 $2$ 的 $T,J,Q,K,A$，那么两个人的场面都是 $T,J,Q,K,A$ 的同花顺，大小相同，因此结果为平局。

每一局游戏中，蒜斜和小美都要进行若干轮的下注。因为蒜斜是一名新手，所以第一天的训练采用了一种简化版的下注规则：

首先蒜斜进行决策。蒜斜可以选择的决策有如下几种：
1. 过牌 (Check)，此时什么事情都不会发生。
2. 盖牌 (Fold)，此时游戏直接结束，小美获胜。
3. 加注 (Raise)，假设加注阶段开始时蒜斜手上还有 $k$ 枚筹码，那么蒜斜可以选择一个 $[1,k]$ 范围内的整数 $x$ 进行加注。此时，蒜斜需要将手上的 $x$ 枚筹码移入彩池中，即彩池大小增加 $x$，蒜斜手上的筹码数量减少 $x$。
接着小美进行决策。小美可以选择的决策有如下几种：
1. 过牌 (Check)，只有在蒜斜选择过牌的时候小美才能选择该决策。此时什么事情都不会发生。
2. 盖牌 (Fold)，此时游戏直接结束，蒜斜获胜。
3. 跟牌 (Call)，只有在蒜斜选择加注的时候小美才能选择该决策。此时，假设蒜斜选择加注 $x$ 枚筹码，小美同样需要将手上的 $x$ 枚筹码移入彩池中。（可以证明在这种情况下，小美手上的筹码数一定不少于 $x$ 枚）

在游戏结束的时候，如果有一方胜利，则胜利方获得彩池中全部的筹码；如果双方平局，则双方平分彩池中的筹码。一位玩家在一句游戏中的收益等于游戏结束时他/她手上的筹码数量减去开始时他/她手上的筹码数量（即 $100$）。

任务

你需要编写一个函数 makeDecision，来帮助蒜斜在每一轮下注的过程中进行决策，从而帮助蒜斜赢得足够多的筹码。

小美选择了一种非常简单的策略：

如果蒜斜选择过牌，那么小美同样也选择过牌。
如果蒜斜选择加注，那么小美只有在跟牌的预期收益大于盖牌的预期收益的时候，才会选择跟牌。

根据规则，盖牌的预期收益为小美手上剩下的筹码数量减去初始筹码数量（即 $100$）。小美会使用模拟实验的方式来计算跟注的预期收益。模拟实验会进行 $100$ 轮，每一轮模拟实验的过程如下：

假设现在还有 $a$ 张牌没有出现，小美会均匀随机产生一个这 $a$ 张牌的排列。
假设游戏中还有 $b$ 张牌没有公开（包括没有公开的公共牌和蒜斜的底牌），小美会把这些牌依次赋值为排列中的前 $b$ 张牌。
这一轮模拟实验的收益为：(1) 这一轮小美选择跟注且 (2) 在接下来的加注过程中蒜斜始终选择过牌的情况下，小美在游戏结束时的收益。

小美会将这 $100$ 轮模拟实验的平均收益作为她的预期收益。

实现细节

本题只支持 C++11 以及更新版本的 C++。

你需要包含头文件 texas.h。头文件中包含了如下三个数据结构：

  struct Card {
      int color, value;
      Card(): color(-1), value(-1) {}
      Card(int _color, int _value): color(_color), value(_value) {}
  };

  struct State {
      Card alice[2], bob[2];
      Card community[5];
  };

  enum class ActionType {
      CHECK, CALL, RAISE, FOLD
  };

卡牌结构 Card 包含了两个成员变量 color 和 value。其中 color 取值为 $[0,3]$ 中的整数，分别表示了每一种花色；value 取值为 $[1,13]$ 中的整数，按照大小递增的顺序对应了每一种牌，即依次对应 $2,3,4,5,6,7,8,9,T,J,Q,K,A$。

特别地，如果一张卡片未知（从小美的视角看不见），那么它的 color 和 value 都会被赋值为 $-1$。
局面结构 State 包含了游戏过程中的一个局面。其中数组 alice 代表蒜斜的两张底牌，bob 代表小美的两张底牌，community 代表公共牌。State 一定满足以下的性质：
1. 所有已知的牌一定两两不同。
2. 在蒜斜的视角下，alice 数组中的卡牌一定已知，bob 数组中的卡牌一定未知。
3. community 数组中一定是下标在区间 $[0,k)$ 的卡牌已知，其中 $k$ 的取值为 $\{0,3,4,5\}$，分别对应每一轮加注。
决策结构 ActionType 包含了所有可能的决策，其中 CHECK, CALL, RAISE, FOLD 分别表示了过牌、跟牌、加注、盖牌。

你只能提交一个源文件实现如上所述的 maxDecision 函数，并且遵循下面的命名和接口。

std::pair<ActionType, int> makeDecision(const State& s);

其中输入 s 表示当前蒜斜可以看见的局面。你需要输出一个决策和整数的 pair 来表示蒜斜的决策，决策有如下几种可能性：

(ActionType::CHECK, 0)，表示蒜斜选择过牌。
(ActionType::RAISE, i)，表示蒜斜选择加注，加注大小为 $i$。此时 $i$ 的大小应当至少为 $1$，至多为蒜斜手上还剩下的筹码数量。
(ActionType::FOLD, 0)，表示蒜斜选择盖牌。

makeDecision 在评测过程中会被调用若干次，但是评测系统保证 makeDecision 的调用一定遵循前文所述的游戏进程，即对应同一局游戏的 makeDecision 调用一定连续且遵循时间顺序。因此，你可以通过一些本地变量来跟踪游戏的进程，包括但不限于记录蒜斜手上剩余的筹码数量以及彩池大小。

辅助函数

德州扑克是一个相当复杂的游戏，为了减轻大家的解题负担，texas.h 中提供了一些可用的辅助函数。

int getResult(const State& s);

函数 getResult 接受一个完整的局面（即所有的 $9$ 张牌都不能未知），并会根据规则比较蒜斜和小美的场面大小。对应蒜斜场面较大、双方场面相同、小美场面较大这三种情况，getResult 会分别返回 1,0,-1。

std::pair<double, double> getRatesBySampling(const State& s, int t);

函数 getRatesBySampling 接受一个部分局面（即一部分牌可以是未知的）和一个正整数 $t$，并会用随机采样的方法计算蒜斜的胜率。随机采样会进行 $t$ 轮。在每一轮中，ggetRatesBySampling 都会把 $s$ 中未知的牌随机赋值成还未出现过的牌，并比较蒜斜和小美的场面。getRatesBySampling 返回一个数对 $(w,d)$，其中 $w,d$ 分别表示在这 $t$ 次采用中，蒜斜场面较大和双方场面大小相等的概率。

评测方式

评测方式可以参见下发的评测器 grader.cpp。在本地测试的时候，你需要把你的程序 d.cpp、评测器 grader.cpp 以及头文件 texas.h 放在同一个文件夹下，并在命令行中使用指令 g++ grader.cpp d.cpp -o d -O2 -std=c++11 进行编译。

请注意，最终测试时所用的评测器与该参考实现有所不同，因此选手的解法不应该依赖该评测器的实现。

评测器会随机进行 $5 \times 10^4$ 局游戏，并输出所有游戏中小美的平均收益。

同时，grader.cpp 中一些函数的实现也可以作为参考：

函数 runGame 对一局随机的游戏进行了模拟。
函数 bobAction 实现了小美使用的策略。
函数 getResult 和 getRatesBySampling 实现了 texas.h 中的两个辅助函数。

样例程序

在下发文件夹中有两个样例程序 example1.cpp 和 example2.cpp：

example1.cpp 总是会在每局游戏的第一轮下注中 All In（即压下自己的所有筹码）。
example2.cpp 在每一轮押注的时候，会调用 getRatesBySampling 计算自己的胜率。如果蒜斜场面更大的概率大于小美场面更大的概率，那么就会 All In（即压下自己的所有筹码）。

限制与约定

本题严禁任何形式的攻击交互库的行为，一旦发现，将取消相关选手的参赛资格。

定义 $w$ 为蒜斜的平均收益，即评测器的输出。

Small Task: 你需要让 $w \geq 11$。

Large Task: 你需要让 $w \geq 16$。

在评测每一次提交的时候，评测器都会使用不同的随机种子来生成局面。因此，同一个程序的多次提交对应的 $w$ 可能会略有波动。在比赛中，只要有一次提交满足对应的要求即可获得对应的分数，但是请注意每支队伍在一道题上最多提交 $16$ 次。

时间限制：$120\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例交互库下载

Universal Online Judge

UOJ

2021年“美团杯”程序设计挑战赛

D. 德州扑克

规则

任务

实现细节

辅助函数

评测方式

样例程序

限制与约定

下载