UOJ Logo Universal Online Judge

UOJ

#640. 【美团杯2021】D. 德州扑克

附件下载 统计

这是一道交互题

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

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

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

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

规则

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

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

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

  1. 同花顺:花色相同的顺子(顺子的定义见下方),例如同花色的 $T,J,Q,K,A$。
  2. 四条:存在四张大小相同的牌,例如任意花色的 $T,T,T,T,2$。
  3. 葫芦:有三张牌大小相同,另外两张牌大小相同,例如任意花色的 $T,T,T,J,J$。
  4. 同花:五张牌花色相同,例如同花色的 $7, J,Q,K,A$。
  5. 顺子:五张牌大小连续,例如任意花色的 $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$。
  6. 三条:存在三张大小相同的牌,例如任意花色的 $T,T,T,J,Q$。
  7. 两对:存在两个大小不同的对子(一个对子是两张大小一样的牌),例如任意花色的 $T,T,Q,Q,K$。
  8. 对子:存在两张大小相同的牌,例如任意花色的 $T,T,J,Q,K$。
  9. 高牌:不满足以上任何一个牌型的手牌都是高牌。

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

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

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

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

下面是一些例子:

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

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

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

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

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

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

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

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

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

任务

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

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

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

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

  1. 假设现在还有 $a$ 张牌没有出现,小美会均匀随机产生一个这 $a$ 张牌的排列。
  2. 假设游戏中还有 $b$ 张牌没有公开(包括没有公开的公共牌和蒜斜的底牌),小美会把这些牌依次赋值为排列中的前 $b$ 张牌。
  3. 这一轮模拟实验的收益为:(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
  };
  1. 卡牌结构 Card 包含了两个成员变量 colorvalue。其中 color 取值为 $[0,3]$ 中的整数,分别表示了每一种花色;value 取值为 $[1,13]$ 中的整数,按照大小递增的顺序对应了每一种牌,即依次对应 $2,3,4,5,6,7,8,9,T,J,Q,K,A$。

    特别地,如果一张卡片未知(从小美的视角看不见),那么它的 colorvalue 都会被赋值为 $-1$。

  2. 局面结构 State 包含了游戏过程中的一个局面。其中数组 alice 代表蒜斜的两张底牌,bob 代表小美的两张底牌,community 代表公共牌。State 一定满足以下的性质:

    1. 所有已知的牌一定两两不同。
    2. 在蒜斜的视角下,alice 数组中的卡牌一定已知,bob 数组中的卡牌一定未知。
    3. community 数组中一定是下标在区间 $[0,k)$ 的卡牌已知,其中 $k$ 的取值为 $\{0,3,4,5\}$,分别对应每一轮加注。
  3. 决策结构 ActionType 包含了所有可能的决策,其中 CHECK, CALL, RAISE, FOLD 分别表示了过牌、跟牌、加注、盖牌。

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

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

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

  1. (ActionType::CHECK, 0),表示蒜斜选择过牌。
  2. (ActionType::RAISE, i),表示蒜斜选择加注,加注大小为 $i$。此时 $i$ 的大小应当至少为 $1$,至多为蒜斜手上还剩下的筹码数量。
  3. (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 中一些函数的实现也可以作为参考:

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

样例程序

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

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

限制与约定

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

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

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

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

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

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

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

下载

样例交互库下载