斗地主
最编程
2024-06-24 16:08:03
...
【题目描述】
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下:
牌型 | 牌型说明 | 牌型举例 |
---|---|---|
火箭 | 即双王(双鬼牌) | ♂ ♀ |
炸弹 | 四张同点牌。 | ♠A ♥A ♣A ♦A |
单张牌 | 单张牌 | ♠3 |
对子牌 | 两张码数相同的牌 | ♠2 ♥2 |
三张牌 | 三张码数相同的牌 | ♠3 ♥3 ♣3 |
三带一 | 三张码数相同的牌 + 一张单牌 | ♠3 ♥3 ♣3 ♠4 |
三带二 | 三张码数相同的牌 + 一对牌 | ♠3 ♥3 ♣3 ♠4 ♥4 |
单顺子 | 五张或更多码数连续的单牌(不包括 2 点和双王) | ♠7 ♣8 ♠9 ♣10 ♣J |
双顺子 | 三对或更多码数连续的对牌(不包括 2 点和双王) | ♣3 ♥3 ♠4 ♥4 ♠5 ♥5 |
三顺子 | 二个或更多码数连续的三张牌(不能包括 2 点和双王) | ♠3 ♥3 ♣3 ♠4 ♥4 ♣4 ♠5 ♦5 ♥5 |
四带二 | 四张码数相同的牌+任意两张单牌(或任意两对牌) | ♠5 ♥5 ♣5 ♦5 ♣3 ♣8 |
【输入描述】
第一行包含用空格隔开的2个正整数T、n,表示手牌的组数以及每组手牌的张数。
接下来T组数据,每组数据n行,每行一个非负整数ai、bi,对表示一张牌,其中ai表示牌的数码,bi表示牌的花色,中间用空格隔开。特别的,我们用1来表示数码A,11表示数码J,12表示数码Q,13表示数码K;黑桃、红心、梅花、方片分别用1-4来表示;小王的表示方法为0 1,大王的表示方法为0 2
。【输出描述】
共T行,每行一个整数,表示打光第i组手牌的最少次数。
【样例输入】
样例1:
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
样例2:
1 1712 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2
12 4
2 2
7 2
【样例输出】
样例1:
3
样例2:
6
【数据范围及提示】
对于不同的测试点,我们约定手牌组数T,与张数n的规模如下:
测试点编号 | T的规模 | n的规模 | 测试点编号 | T的规模 | n的规模 |
---|---|---|---|---|---|
1 | 100 |
2 |
11 | 100 |
14 |
2 | 100 |
2 |
12 | 100 |
15 |
3 | 100 |
3 |
13 | 10 |
16 |
4 | 100 |
3 |
14 | 10 |
17 |
5 | 100 |
4 |
15 | 10 |
18 |
6 | 100 |
4 |
16 | 10 |
19 |
7 | 100 |
10 |
17 | 10 |
20 |
8 | 100 |
11 |
18 | 10 |
21 |
9 | 100 |
12 |
19 | 10 |
22 |
10 | 100 |
13 |
20 | 10 |
23 |
数据保证所有的手牌都是随机生成的。
推荐阅读
-
创造一个全新的在线斗地主游戏经验 (上篇)
-
创造一个在线斗地主游戏:从零到一(第二部)
-
用C语言玩转斗地主的关键计算方法
-
用Python打造智能AI斗地主出牌器,每局都稳赢不输
-
简易 JS & HTML 斗地主游戏的源代码实现
-
斗地主
-
简单用java集合模拟斗地主发牌操作
-
java实战(一)Java模仿斗地主洗牌发牌小游戏
-
Python 模拟斗地主发牌
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果