迷你斗地主

这是AI小班课的大作业之一，也是我的第一个小组合作项目。项目的内容是写一个能够打斗地主的AI，基于蒙特卡洛树搜索（MCTS）。我们小组当时只有三个人，具体分工如下：yqh负责MCTS算法的主体构建，glc负责修改样例程序使之适配MCTS，我负责对接botzone+debug。我原以为我的任务会比较轻松，殊不知那几天debug de得昏天黑地浑浑噩噩。（我昨天一整天都在和代码搏斗，又重新体验了这种感觉）这让我明白一个道理：不要把debug工作留到最后做，正确的做法是写一点de一点。还有，debug方法要选对，我一开始直接在botzone上无脑debug，这样做一点用都没有，后面改为本地控制台输出debug马上豁然开朗。

借此项目，我还学会了使用git进行版本控制和团队合作。虽然踩了很多坑，但这一切都是值得的。我们的代码如下：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <ctime>
#include <time.h>
#include <map>
#include "jsoncpp/json.h"

using namespace std;

namespace doudizhu
{
    // 游戏使用的牌总数，不要修改
    const int MAX_CARD_NUM = 54;

    // 游戏使用的牌类型的数目，不要修改
    const int MAX_CARD_TYPE_NUM = 15;

    // 对每种牌的数目编码，每种占4bit
    typedef unsigned long long EncodedCards;
    const EncodedCards NO_CARDS = 0ull;

    // bitmap，用于枚举子集
    typedef unsigned long long Bitmap;
    const Bitmap EMPTY_SET = 0ull;

    // 牌张按照3-JOKER的顺序从0-53编号
    typedef int Card;

    // 定义牌张类型：一共15种不同大小的牌
    typedef enum
    {
        THREE = 0,
        FOUR = 1,
        FIVE = 2,
        SIX = 3,
        SEVEN = 4,
        EIGHT = 5,
        NINE = 6,
        TEN = 7,
        JACK = 8,
        QUEEN = 9,
        KING = 10,
        ACE = 11,
        TWO = 12,
        Joker = 13,
        JOKER = 14
    } CardType;

    // 游戏中最小的牌张类型（可修改为NINE，适配迷你斗地主）
    const CardType START_CARD = NINE;

    // 将一张牌的char转化为CardType
    CardType transCharintoInt(char c)
    {
        switch (c)
        {
        case '9':
            return NINE;
        case '0':
            return TEN;
        case 'J':
            return JACK;
        case 'Q':
            return QUEEN;
        case 'K':
            return KING;
        case 'A':
            return ACE;
        case '2':
            return TWO;
        case 'r':
            return Joker;
        case 'R':
            return JOKER;
        default:
            return NINE;
        }
        return NINE;
    }

    // 将一张牌的CardType转化为char
    char transIntToChar(CardType x)
    {
        switch (x)
        {
        case NINE:
            return '9';
        case TEN:
            return '0';
        case JACK:
            return 'J';
        case QUEEN:
            return 'Q';
        case KING:
            return 'K';
        case ACE:
            return 'A';
        case TWO:
            return '2';
        case Joker:
            return 'r';
        case JOKER:
            return 'R';
        }
        return '!';
    }

    // 主牌类型
    // 对于连牌 (456789:SINGLE; 334455:PAIR; JJJQQQ:TRIPLET, 77778888:QUADRUPLE)
    // 对于含副牌的 (333A:TRIPLET; 222255JJ:QUADRUPLE)
    // 对于连牌含副牌的 (34KKKAAA:TRIPLET; 4444555589JQ:QUADRUPLE)
    typedef enum
    {
        PASS = 0,      // 过
        SINGLE = 1,    // 单张
        PAIR = 2,      // 对子
        TRIPLET = 3,   // 三张
        QUADRUPLE = 4, // 四张
        ROCKET = 5     //火箭
    } MainCardComboType;

    // 某种主牌类型要想形成合法序列（顺子、连对、飞机、连炸），所需的最小长度
    const int SEQ_MIN_LENGTH[] = {0, 5, 3, 2, 2, 1};

    // 返回具体牌张的类型：（0-14编号，对应于THREE, FOUR,... Joker, JOKER）
    inline CardType cardTypeOf(Card c)
    {
        return CardType((c >> 2) + int(bool(c & 1) && (c >= MAX_CARD_NUM - 2)));
    }

    // 将牌张序列转为各种牌的数目向量
    vector<int> toCardCountVector(const vector<Card> &card_combo)
    {
        vector<int> card_counter(MAX_CARD_TYPE_NUM);
        for (Card c : card_combo)
        {
            card_counter[cardTypeOf(c)]++;
        }
        return card_counter;
    }

    // 将各种牌的数目向量转为EncodedCards表示
    EncodedCards toEncodedCards(const vector<int> &card_counter)
    {
        EncodedCards combo = NO_CARDS;
        for (CardType i = START_CARD; i <= JOKER; i = CardType(i + 1))
        {
            // 4i~(4i+3)的位置上编码第i种牌的数目
            combo |= (EncodedCards(card_counter[i]) << (i << 2));
        }
        return combo;
    }

    // 直接将牌张序列转为EncodedCards
    EncodedCards toEncodedCardsDirectly(const vector<Card> &card_combo)
    {
        vector<int> card_counter = toCardCountVector(card_combo);
        EncodedCards combo = toEncodedCards(card_counter);
        return combo;
    }

    // 在EncodedCards combo中将CardType ct类型的牌的数目增加n
    inline EncodedCards addToEncodedCards(
        CardType ct, EncodedCards combo, int n = 1)
    {
        return combo + (EncodedCards(n) << (ct << 2));
    }

    // 在EncodedCards combo中将CardType ct类型的牌的数目减少n
    inline EncodedCards minusFromEncodedCards(
        CardType ct, EncodedCards combo, int n = 1)
    {
        return combo - (EncodedCards(n) << (ct << 2));
    }

    // 在EncodedCards中判断某种牌有多少张
    inline int numCardOfEncoded(
        CardType ct, EncodedCards combo)
    {
        return int((combo >> (ct << 2)) & 0xfull);
    }

    // 在EncodedCards中判断总牌数
    int sumCardOfEncoded(EncodedCards combo)
    {
        int sum = 0;
        for (int ct = START_CARD; ct <= JOKER; ct++)
        {
            sum += numCardOfEncoded((CardType)ct, combo);
        }
        return sum;
    }

    // 分析一手牌的类型、大小等
    struct Hand
    {
        // 一手牌的编码形式，每4位对应一种牌的数目。
        EncodedCards combo;
        // 一手牌主牌的类型：单张（顺）、两张（顺）……火箭
        MainCardComboType type;
        // 一手牌主牌开始的牌张
        CardType start;
        // 主牌的长度：单牌1，对牌1，顺子按其长度来
        int length;
        // 副牌不带、带单还是带双(0,1,2)
        int appendix;

        // 解析对手的一手牌（牌张编码、主牌类型、主牌开始、主牌长度、副牌所带数目）

        Hand(const EncodedCards &_combo) : combo(_combo)
        {
            CardType max_freq_card = START_CARD;
            // 最多出现的牌出现了多少次
            int max_freq = 0;
            // 出现次数最多的牌有几种
            int max_freq_length = 0;
            // 最小出现的手牌是什么牌
            CardType min_card = JOKER;
            // 这一手牌一共有多少张
            int total_cards = sumCardOfEncoded(combo);
            // 编码对手这一手牌到位图中
            for (CardType i = START_CARD; i <= JOKER; i = CardType(i + 1))
            {
                // 记录出现次数最多的牌是哪一种，及其出现次数
                if (numCardOfEncoded(i, combo) > max_freq)
                {
                    max_freq = numCardOfEncoded(i, combo);
                    max_freq_card = i;
                    max_freq_length = 1;
                }
                else if (numCardOfEncoded(i, combo) == max_freq)
                {
                    max_freq_length++;
                }
                // 记录出现的最小牌张
                if (numCardOfEncoded(i, combo) != 0 && i < min_card)
                {
                    min_card = i;
                }
            }
            // 下面判断主要牌型
            // 空牌，PASS
            if (max_freq == 0)
            {
                type = PASS;
                start = START_CARD;
                length = 0;
                appendix = 0;
                return;
            }
            // 火箭
            if (min_card == Joker && total_cards == 2)
            {
                type = ROCKET;
                start = Joker;
                length = 2;
                appendix = 0;
                return;
            }
            // 序列牌（单、双、三、四：独立出现或者连续出现）
            type = MainCardComboType(max_freq);
            // 主牌开始的牌张
            start = max_freq_card;
            // 主牌长度
            length = max_freq_length;
            // 副牌带0,1,2张
            appendix = total_cards / length - int(type);
        }
        // card_counter表示这一手牌每种有多少张
        Hand(const vector<int> &card_counter)
        {
            // 初始化这一手牌的编码形式为空
            combo = NO_CARDS;
            // 最多的牌是哪一种（取最先出现的那一种）
            CardType max_freq_card = START_CARD;
            // 最多出现的牌出现了多少次
            int max_freq = 0;
            // 出现次数最多的牌有几种
            int max_freq_length = 0;
            // 最小出现的手牌是什么牌
            CardType min_card = JOKER;
            // 这一手牌一共有多少张
            int total_cards = 0;
            // 编码对手这一手牌到位图中
            // 扫一遍对手的牌，看看出现次数最多的牌、主牌的长度
            Hand(toEncodedCards(card_counter));
        }
        Hand(const Hand &another) : combo(another.combo), type(another.type), start(another.start), length(another.length), appendix(another.appendix) {}
        bool isPass()
        {
            return type == PASS;
        }
        bool isSingle()
        {
            return type == SINGLE && length == 1;
        }
        bool isPair()
        {
            return type == PAIR && length == 1;
        }
        bool isBomb()
        {
            return type == QUADRUPLE && length == 1 && appendix == 0;
        }
        bool isRocket()
        {
            return type == ROCKET;
        }

        // 判断是三带(0,1,2)还是四带(0,2,4)
        bool isTripletOrQuadruple()
        {
            return (type == TRIPLET || type == QUADRUPLE) && length == 1;
        }

        // 判断有无副牌
        bool hasAppendix()
        {
            return appendix > 0;
        }

        // 含有副牌的连续三带、四带也算Chain，但是长度至少得是2
        bool isChain()
        {
            return ((type == SINGLE && length >= SEQ_MIN_LENGTH[SINGLE]) || (type == PAIR && length >= SEQ_MIN_LENGTH[PAIR]) || (type == TRIPLET && length >= SEQ_MIN_LENGTH[TRIPLET]) || (type == QUADRUPLE && length >= SEQ_MIN_LENGTH[QUADRUPLE]));
        }
    };

    // 使用上一手牌、我方现有的牌，构造游戏状态。可分析我方可行动作
    struct DoudizhuState
    {

    public:
        // 当前玩家，0为地主，1地主下家，2地主下家的下家
        int my_id;

        // 上一个玩家，0为地主，1地主下家，2地主下家的下家
        int last_player_id;

        // 上一手出了什么牌
        EncodedCards last_action;

        // 玩家牌型
        EncodedCards *player_cards;

        // 传入我的ID，三名玩家的牌编码，上一次出牌者ID，对手上一次出的牌（一手牌）
        // 应该要简化，但我不会QAQ
        DoudizhuState(int _myID, EncodedCards *_playerCards, int _lastPlayerID, EncodedCards _lastAction) : my_id(_myID), last_player_id(_lastPlayerID), last_action(_lastAction)
        {
            player_cards = new EncodedCards[3];
            for (int i = 0; i < 3; i++)
            {
                player_cards[i] = _playerCards[i];
            }
        }

        // 复制构造函数，深拷贝
        DoudizhuState(DoudizhuState &another) : my_id(another.my_id), last_player_id(another.last_player_id), last_action(another.last_action)
        {
            player_cards = new EncodedCards[3];

            for (int i = 0; i < 3; i++)
            {
                player_cards[i] = another.player_cards[i];
            }
        }

        ~DoudizhuState() { delete[] player_cards; /*delete[] player_cards_num;*/ }

        // 判断进入本状态时游戏是否结束，所以只判定上一个出牌人此时的牌数。返回值0游戏继续，1地主赢，-1地主输
        int gameover()
        {
            for (int i = 0; i < 3; i++)
                if (sumCardOfEncoded(player_cards[i]) == 0)
                    return i == 0 ? 1 : -1;
            return 0;
        }

        // 我的牌中是否有火箭，如果有，则返回该牌型的EncodedCards表示
        EncodedCards genRocket(int *my_card_counter)
        {
            EncodedCards action = NO_CARDS;
            if (my_card_counter[JOKER] == 1 && my_card_counter[Joker] == 1)
            {
                action = addToEncodedCards(Joker, NO_CARDS, 1);
                action = addToEncodedCards(JOKER, action, 1);
            }
            return action;
        }

        // 返回我的牌中所有炸弹的列表，均用EncodedCards类型表示
        vector<EncodedCards> genBombs(int *my_card_counter)
        {
            vector<EncodedCards> actions;
            EncodedCards action = NO_CARDS;
            for (CardType i = START_CARD; i <= TWO; i = CardType(i + 1))
            {
                if (my_card_counter[i] == 4)
                {
                    action = addToEncodedCards(i, NO_CARDS, 4);
                    actions.push_back(action);
                }
            }
            return actions;
        }

        // 下一手可以出什么牌，返回所有可能动作的列表，元素是EncodedCards的形式
        // generate_appendix == true: 生成的动作中包含三带单、对，四带两单、对的各种情况，包含带的副牌
        // generate_appendix == false: 只生成主牌（三带四带的连三连四部分），不含带的副牌，且主牌部分不重复

        vector<EncodedCards> validActions(bool generate_appendix = true)
        {
            // 待返回动作列表
            vector<EncodedCards> actions;
            // 用于临时保存同一手主牌对应的不同副牌选择
            vector<EncodedCards> appendix_actions;
            // 用于构造主牌动作
            EncodedCards action = NO_CARDS;
            // 用于构造副牌选择
            EncodedCards appendix_action = NO_CARDS;

            Hand last_action_asHand(last_action);

            // 我手牌中各种牌的数量
            int *my_card_counter = new int[MAX_CARD_TYPE_NUM];
            memset(my_card_counter, 0, sizeof(my_card_counter));
            for (CardType ct = START_CARD; ct <= JOKER; ct = CardType(ct + 1))
            {
                my_card_counter[ct] = numCardOfEncoded(ct, player_cards[my_id]);
            }
            // 如果有火箭，生成火箭作为动作，否则为NO_CARDS
            EncodedCards rocket = genRocket(my_card_counter);
            // 生成当前我方持有的炸弹列表
            vector<EncodedCards> bombs = genBombs(my_card_counter);

            // 上家牌非Pass并且带副牌，生成动作才需考虑副牌，否则只考虑我方意愿
            generate_appendix = generate_appendix &&
                                (last_action_asHand.hasAppendix() || last_action_asHand.isPass());

            // ! 如果轮到我先出牌
            if (last_action_asHand.isPass())
            {
                // 生成单、对（范围从最小牌到大王）
                for (CardType i = START_CARD; i <= JOKER; i = CardType(i + 1))
                {
                    // j=1单/j=2对
                    for (int j = 1; j <= 2 && j <= my_card_counter[i]; ++j)
                    {
                        action = addToEncodedCards(i, NO_CARDS, j);
                        actions.push_back(action);
                    }
                }

                // 生成三带，四带（有副牌当且仅当generate_appendix，范围从最小牌到2）
                for (CardType i = START_CARD; i <= TWO; i = CardType(i + 1))
                {
                    // 如果牌有3张，考虑三带；如果有4张，三带、四带都要考虑
                    for (int j = 3, num_appendix; j <= my_card_counter[i]; ++j)
                    {
                        action = addToEncodedCards(i, NO_CARDS, j);
                        if (generate_appendix)
                        {
                            // 是三带1还是四带2
                            num_appendix = j == 3 ? 1 : 2;
                            // 带单牌还是双牌
                            for (int k = 1; k <= 2; ++k)
                            {
                                // 生成副牌
                                appendix_actions = generateAppendix(i, 1, num_appendix, k);
                                for (EncodedCards ec : appendix_actions)
                                {
                                    appendix_action = ec;
                                    // 副牌可以直接加到主牌动作上（位串设计保证了这一点）
                                    actions.push_back(action + appendix_action);
                                }
                            }
                            // 如果不生成副牌，这里不添加四张，因为后面添加了
                        }
                        else if (j < QUADRUPLE)
                        {
                            actions.push_back(action);
                        }
                    }
                }
                // accumulated_length[1,2,3,4]: 统计到某种牌时，记录以其为结尾的最长（单/对/三/四）连牌长度
                vector<int> accumulated_length(5);
                // 暂时保存action的值
                vector<EncodedCards> a(5), _a(5);
                // 生成连续牌：连单、连双、连三（带）、连四（带）
                for (CardType i = START_CARD; i <= ACE; i = CardType(i + 1))
                {
                    for (int j = 1; j <= my_card_counter[i]; ++j)
                    {
                        // 能进循环说明牌张数目够
                        accumulated_length[j]++;
                        // 将j张类型i的牌添加到a[j]中
                        a[j] = addToEncodedCards(i, a[j], j);
                    }
                    for (int j = my_card_counter[i] + 1; j <= 4; ++j)
                    {
                        // 进了这个循环说明牌张数目不够，清空连牌长度，连牌断裂
                        accumulated_length[j] = 0;
                        a[j] = NO_CARDS;
                    }
                    for (int j = 1; j <= 4; ++j)
                    {
                        _a[j] = a[j];
                    }
                    // 考虑连单、双、三、四的序列
                    for (int j = 1, num_appendixes; j <= 4; ++j)
                    {
                        // 当前序列以i结尾，以k开始
                        for (CardType k = CardType(i - accumulated_length[j] + 1);
                             // j重的牌序列最短长度要大于等于SEQ_MIN_LENGTH[j]，因此k最多到i-SEQ_MIN_LENGTH[j]+1
                             k <= i - SEQ_MIN_LENGTH[j] + 1; k = CardType(k + 1))
                        {
                            action = _a[j];
                            if (generate_appendix && j >= 3)
                            {
                                // 如果j=3，那么需要为每段生成一份副牌，如果j=4，那么需要为每段生成2份副牌
                                num_appendixes = j == 3 ? 1 : 2;
                                // 副牌是带单牌还是对牌（l=1单，l=2对）
                                for (int l = 1; l <= 2; ++l)
                                {
                                    // 生成所有以牌种i为结尾，长度为i-k+1的连三/连四的副牌
                                    //（每段配num_appendixes份副牌，并且副牌张数为l(1/2)）
                                    appendix_actions = generateAppendix(i, i - k + 1, num_appendixes, l);
                                    for (EncodedCards ec : appendix_actions)
                                    {
                                        appendix_action = ec;
                                        actions.push_back(action + appendix_action);
                                    }
                                }
                            }
                            else
                            {
                                actions.push_back(action);
                            }
                            // 考虑过k开始到i-SEQ_MIN_LENGTH[j]+1的子序列后，考虑从k+1开始的子序列
                            _a[j] = minusFromEncodedCards(k, _a[j], j);
                        }
                    }
                }
                // 生成火箭、炸弹的情况在最后考虑了，这里不返回。
            }
            else if (last_action_asHand.isRocket())
            {
                // 对面火箭，直接开摆，返回空动作集
                return actions;
            }
            else if (last_action_asHand.isBomb())
            {
                // 对面是炸弹，找更大的炸弹
                for (EncodedCards ec : bombs)
                {
                    // 炸弹比较只需要比较bitmap大小即可
                    if (ec > last_action_asHand.combo)
                    {
                        action = ec;
                        actions.push_back(action);
                    }
                }
                // 考虑火箭的情况
                if (rocket != NO_CARDS)
                {
                    actions.push_back(rocket);
                }
                // 直接返回，下面非炸弹的情况才需要考虑所有能打的炸弹
                return actions;
            }
            else if (last_action_asHand.isSingle() || last_action_asHand.isPair())
            {
                // 考虑对面出单牌、对牌的情况
                for (CardType i = CardType(last_action_asHand.start + 1); i <= JOKER; i = CardType(i + 1))
                {
                    // 如果我的牌够出，那么直接加入动作列表
                    if (my_card_counter[i] >= last_action_asHand.type)
                    {
                        action = addToEncodedCards(i, NO_CARDS, last_action_asHand.type);
                        actions.push_back(action);
                    }
                }
                // 生成炸弹火箭最后考虑了，这里不返回
            }
            else if (last_action_asHand.isTripletOrQuadruple())
            {
                // 三带、四带等（不连）
                for (CardType i = CardType(last_action_asHand.start + 1); i <= TWO; i = CardType(i + 1))
                {
                    if (my_card_counter[i] >= last_action_asHand.type)
                    {
                        action = addToEncodedCards(i, NO_CARDS, last_action_asHand.type);
                        // 如果需要生成副牌，那么将其考虑到action中
                        if (generate_appendix)
                        {
                            appendix_actions = generateAppendix(i);
                            for (EncodedCards ec : appendix_actions)
                            {
                                appendix_action = ec;
                                actions.push_back(action + appendix_action);
                            }
                        }
                        else if (last_action_asHand.type < QUADRUPLE)
                        {
                            // 后面会添加炸弹，所以这里不重复添加，只加入三张
                            actions.push_back(action);
                        }
                    }
                }
                // 生成炸弹火箭的情况最后考虑了，这里不返回
            }
            else if (last_action_asHand.isChain())
            {
                // 连续牌：可能为连单、双、三、四。对于连三、四还可能带副牌
                // 当前找到的序列长度
                int cur_length = 0;

                // 从前一手牌最小牌张+1开始考虑，寻找连牌
                for (CardType i = CardType(last_action_asHand.start + 1); i <= ACE; i = CardType(i + 1))
                {
                    // 如果我拥有的此种牌张数目大于上一手序列的重复数
                    if (my_card_counter[i] >= last_action_asHand.type)
                    {
                        cur_length++;
                        action = addToEncodedCards(i, action, last_action_asHand.type);
                        // 如果当前发现的序列长度超过上一手序列的长度，将序列头部剪去
                        if (cur_length > last_action_asHand.length)
                        {
                            action = minusFromEncodedCards(
                                CardType(i - last_action_asHand.length), action, last_action_asHand.type);
                        }
                        // 如果序列长度达标了，可以加入动作列表
                        if (cur_length >= last_action_asHand.length)
                        {
                            if (generate_appendix)
                            {
                                appendix_actions = generateAppendix(i);
                                for (EncodedCards ec : appendix_actions)
                                {
                                    appendix_action = ec;
                                    actions.push_back(action + appendix_action);
                                }
                            }
                            else
                            {
                                actions.push_back(action);
                            }
                        }
                    }
                    else
                    {
                        cur_length = 0;
                        action = NO_CARDS;
                    }
                }
            }
            // 最后考虑炸弹的情况
            for (EncodedCards ec : bombs)
            {
                action = ec;
                actions.push_back(action);
            }
            // 最后考虑火箭的情况
            if (rocket != NO_CARDS)
            {
                actions.push_back(rocket);
            }

            delete[] my_card_counter;

            return actions;
        }

        // 如果只传第一个参数意味着是针对对手的牌型反制，否则是在上一手Pass的情况下随意出牌
        // 参数分别为：我方主牌最大牌张、主牌序列长度、带牌数目（1单/对或2单/对）、带单(1)或双(2) -> 生成备选副牌列表
        vector<EncodedCards> generateAppendix(CardType end_type,
                                              int seq_length = 1, int num_appendixes = 1, int appendix_type = 1)
        {
            // 存储所有可能的副牌
            vector<EncodedCards> appendixes;
            EncodedCards appendix = NO_CARDS;
            Hand last_action_asHand(last_action);
            // 依据上家出的牌是三带还是四带还是pass，如果pass则采用输入的参数
            if (last_action_asHand.type == TRIPLET)
            {
                // 三带主牌部分长度
                seq_length = last_action_asHand.length;
                // 三带副牌部分为1单或者1对
                num_appendixes = 1;
                // 三带副牌部分为单还是双
                appendix_type = last_action_asHand.appendix;
            }
            else if (last_action_asHand.type == QUADRUPLE)
            {
                // 四带主牌部分长度
                seq_length = last_action_asHand.length;
                // 四带副牌部分为2单或者2对
                num_appendixes = 2;
                // 四带副牌部分为单还是双
                appendix_type = last_action_asHand.appendix;
            }
            else if (last_action_asHand.isPass())
            {
                // 按照输入的seq_length来
                // 按照输入的num_appendixes来
                // 按照输入的appendix_type来
                // 所以这里不用写任何东西
            }
            // 有多少种副牌可以用
            int useable_appendix_count = 0;
            // 需要多少种副牌
            int all_appendix_needed = seq_length * num_appendixes;
            // 保存可用的副牌种类
            vector<CardType> useable_appendix_set;
            // 遍历我方手牌，看看那些种类的牌数目够做副牌
            for (CardType i = START_CARD; i <= JOKER; i = CardType(i + 1))
            {
                // 如果我有的牌大于副牌所需数目，并且当前的牌不在序列范围之内
                if (numCardOfEncoded(i, player_cards[my_id]) >= appendix_type &&
                    (i > end_type || i <= end_type - seq_length))
                {
                    useable_appendix_count++;
                    // 标记该种牌可以用作副牌
                    useable_appendix_set.push_back(i);
                }
            }
            // 如果可用的副牌种类数目不够，返回空集
            if (useable_appendix_count < all_appendix_needed)
            {
                return appendixes;
            }

            // 临时保存副牌选择子集
            Bitmap appendix_subset = (1ull << all_appendix_needed) - 1ull;
            // 临时保存appendix_subset
            Bitmap s;
            // 副牌选择子集的范围
            Bitmap appendix_subset_limit = 1ull << useable_appendix_count;

            // Gosper's Hack Algorithm
            // 枚举C(usable_appendix_count, all_appendixes_needed)个可行的副牌选择子集
            Bitmap lb, r;
            while (appendix_subset < appendix_subset_limit)
            {
                s = appendix_subset;
                appendix = NO_CARDS;
                // 解析生成的子集，将之对应到牌的类别上
                for (int j = 0; s != EMPTY_SET; ++j)
                {
                    if (s & 1ull)
                    {
                        appendix = addToEncodedCards(useable_appendix_set[j], appendix, appendix_type);
                    }
                    s >>= 1;
                }
                appendixes.push_back(appendix);

                // 以下代码负责枚举子集，不用管这一部分
                lb = appendix_subset & -appendix_subset;
                r = appendix_subset + lb;
                appendix_subset = ((appendix_subset ^ r) >> (__builtin_ctzll(lb) + 2)) | r;
            }

            return appendixes;
        }

        // 更新状态，传入action
        void updateState(EncodedCards action)
        {
            // 我出牌
            if (action != NO_CARDS)
            {
                // !
                player_cards[my_id] -= action;
                /*for (CardType i = START_CARD; i <= JOKER; i = CardType(i + 1))
                {
                    // 更新我的牌
                    player_cards[my_id] = minusFromEncodedCards(i, player_cards[my_id], numCardOfEncoded(i, action));
                }*/
                // 上一步的牌是我出的牌
                last_action = action;
                // 上一个玩家是我
                last_player_id = my_id;
            }
            else
            {
                // 我若不出牌, 我的牌和上一个出牌的人保持不变
                // ! 如果我和上家都不出牌, 上一个出牌的人是我的下家, 那么清空last_action
                if (last_player_id == (my_id + 1) % 3)
                    last_action = NO_CARDS;
            }

            my_id = (my_id + 1) % 3;
        }
    };

    // 对validAction生成的可能动作，解析出实际要出的牌张
    vector<Card> decodeAction(EncodedCards encoded_action, vector<Card> my_cards)
    {
        vector<Card> action;
        CardType ct;
        int encoded_ct_num;
        // 对每一张我有的牌，看看我打算打出去的动作中需不需要这张牌
        for (Card c : my_cards)
        {
            ct = cardTypeOf(c);
            encoded_ct_num = numCardOfEncoded(ct, encoded_action);
            // 如果需要，就加入输出列表，并且在打出的动作中删掉一张这种牌
            if (encoded_ct_num > 0)
            {
                encoded_action = minusFromEncodedCards(ct, encoded_action, 1);
                action.push_back(c);
            }
        }
        return action;
    }

    /// 通过自己的牌和场上已经打了的牌，进行随机发牌
    /// 我自己的手牌, 场上所有打出的牌, 玩家1拥有的手牌数, 玩家1的手牌, 玩家2的手牌
    void giveOtherPlayerCards(const EncodedCards &my_cards, const EncodedCards &history, int player1_owned_number, EncodedCards &player1_cards, EncodedCards &player2_cards)
    {
        // ! 记得赋初值
        player1_cards = player2_cards = NO_CARDS;
        // 所有的牌
        int cards_pool[MAX_CARD_TYPE_NUM] = {0};
        for (int i = START_CARD; i <= JOKER; ++i)
        {
            cards_pool[i] += numCardOfEncoded((CardType)i, my_cards);
        }
        for (int i = START_CARD; i <= JOKER; ++i)
        {
            cards_pool[i] += numCardOfEncoded((CardType)i, history);
        }

        int i = 0;
        while (i < player1_owned_number)
        {
            int r = rand() % MAX_CARD_TYPE_NUM;
            // ! 注意: 大小王各一张
            if ((r >= START_CARD && r < Joker && cards_pool[r] < 4) || (r >= Joker && !cards_pool[r]))
            {
                ++cards_pool[r];
                ++i;
                player1_cards = addToEncodedCards((CardType)r, player1_cards);
            }
        }
        for (int i = START_CARD; i < Joker; i++)
        {
            for (int j = 1; j <= 4 - cards_pool[i]; j++)
            {
                player2_cards = addToEncodedCards((CardType)i, player2_cards);
            }
        }
        // 单独判断
        if (!cards_pool[Joker])
            player2_cards = addToEncodedCards(Joker, player2_cards);
        if (!cards_pool[JOKER])
            player2_cards = addToEncodedCards(JOKER, player2_cards);
    }

}

using namespace doudizhu;

clock_t TIME_LIMIT = 900000;                  // 时间限制，单位是毫秒
const bool ENABLE_TIME_LIMIT = true;          // 是否启动时限，请注意，启动时限时MCTS_RANDOM_ROOTS无效
const int MCTS_RANDOM_ROOTS = 50;             // 生成的随机根结点数目
const int MCTS_ITERS = 50;                    // 对于单个根结点迭代次数
const int NUMBER_OF_ROLLOUT = 15;             // 对于未展开的叶子结点rollout的次数
const double PRIORITY_CONSTANT = sqrt(2) / 2; // 计算子结点优先级时所用的常数C

class MCTSNode
{

    friend MCTSNode *treePolicy(MCTSNode *const, MCTSNode *);
    friend void backPropagation(MCTSNode *, double);
    friend EncodedCards MCTS(int, int, int, EncodedCards, EncodedCards, EncodedCards, bool);
    friend double rollOut(MCTSNode *, double);
    friend void MCTSNodePrint(const MCTSNode *);

private:
    // 质量 quality
    double Q;
    // 访问次数
    int N;
    // 结点类型 0地主 1农民一号 2农民二号
    int node_type;

    MCTSNode *parent;
    vector<MCTSNode *> children;

    DoudizhuState game_state;
    vector<EncodedCards> valid_actions;
    // 上家(上一个结点)采取的行动, 叫parent_action更合适
    EncodedCards root_action;

public:
    MCTSNode(MCTSNode *_parent, DoudizhuState _game_state, EncodedCards _root_action = 0) : parent(_parent), game_state(_game_state), root_action(_root_action)
    {
        node_type = _game_state.my_id;
        valid_actions = _game_state.validActions(true); // 需要针对pass调整
        N = 0;
        Q = 0;
        // 根结点的子结点手动更新
    }
    ~MCTSNode()
    {
        /*while (!children.empty())
        {
            delete children.back();
            children.pop_back();
        }*/

        for (auto it = children.begin(); it != children.end();)
        {
            delete *it;
            it = children.erase(it);
        }
    }
    inline double quality() { return (node_type == 1 ? Q : 1 - Q); }
    inline double priority()
    {
        if (!parent)
            throw("cannot calculate priority of the root node");
        return (quality() / N + PRIORITY_CONSTANT * sqrt(2 * log(parent->N) / N));
    }

    MCTSNode *expand(MCTSNode *const root)
    {
        if (game_state.gameover())
            return this;

        // 如果上两家没有全部跳过则可以跳过
        bool pass_available = game_state.last_player_id != node_type;

        //先扩展pass结点
        if (!children.size() && pass_available)
        {
            DoudizhuState next_state(game_state);
            // 下一位出牌者身份
            next_state.updateState(NO_CARDS);

            children.push_back(new MCTSNode(this, next_state));

            return children.back();
        }

        if (children.size() < valid_actions.size() + pass_available)
        {
            EncodedCards action = valid_actions[children.size() - pass_available];

            DoudizhuState next_state(game_state);

            next_state.updateState(action);

            children.push_back(new MCTSNode(this, next_state, action));

            return children.back();
        }
        // 无法扩展新的结点
        return nullptr;
    }
};

void PrintEncodedCards(string note, EncodedCards cards, int k = 0)
{
    if (!k)
        cout << note << ": ";
    else
        cout << note << k << ": ";
    if (cards == NO_CARDS)
    {
        cout << "null" << endl;
        return;
    }
    for (int i = START_CARD; i <= JOKER; i++)
    {
        int card_num = numCardOfEncoded((CardType)i, cards);
        for (int j = 1; j <= card_num; j++)
        {
            cout << transIntToChar((CardType)i);
        }
    }
    cout << endl;
}

MCTSNode *treePolicy(MCTSNode *const root, MCTSNode *node_now)
{
    MCTSNode *next_node = node_now->expand(root);
    if (next_node != nullptr)
        return next_node;
    MCTSNode *best_child = nullptr;
    double best_score = -1145.14;
    for (auto it = node_now->children.begin(); it != node_now->children.end(); it++)
    {
        if ((*it)->priority() > best_score)
        {
            best_score = (*it)->priority();
            best_child = (*it);
        }
    }
    if (best_child == nullptr)
        return nullptr;
    return treePolicy(root, best_child);
}

void backPropagation(MCTSNode *now, double Q)
{
    now->Q = Q;
    now->N = 1;
    while (now->parent != nullptr)
    {
        now = now->parent;
        now->Q = (now->Q * now->N + Q) / (now->N + 1);
        now->N += 1;
    }
}

// 快速模拟
// 当前结点, rollout次数
double rollOut(MCTSNode *now, double number_of_rollout)
{
    // 地主胜利次数
    double lord_win_times = 0;
    while (number_of_rollout)
    {
        // 当前结点, 复制构造深拷贝
        DoudizhuState current_state(now->game_state);
        int is_gameover = current_state.gameover();

        // rollout深度
        int cnt = 0;

        // 只要游戏还未结束, 就一直模拟
        while (is_gameover == 0)
        {
            cnt++;

            vector<EncodedCards> valid_actions = current_state.validActions(true);

            // 随机选择得到的动作在所有可行动作中的序号
            unsigned random_action_id;

            // 随机出牌
            EncodedCards random_choice = NO_CARDS;

            // 无牌可打
            if (valid_actions.size() == 0)
            {
                random_choice = NO_CARDS;
            }
            // 之前人都Pass了，我就得出牌，不能pass
            else if (current_state.my_id == current_state.last_player_id)
            {
                random_action_id = rand() % valid_actions.size();
                random_choice = valid_actions[random_action_id];
            }
            else
            {
                // 之前人没有都Pass，我可以选择pass
                random_action_id = rand() % (valid_actions.size() + 1);
                // 此时我方动作选择不是pass，需要计算具体action
                if (random_action_id != valid_actions.size())
                {
                    random_choice = valid_actions[random_action_id];
                }
            }
            // 更新状态
            current_state.updateState(random_choice);
            // 检测游戏是否结束
            is_gameover = current_state.gameover();
        }

        if (is_gameover == 1)
            lord_win_times++;

        number_of_rollout--;
    }

    double roll_q = double((double)lord_win_times / (double)NUMBER_OF_ROLLOUT);
    return roll_q;
}

// 用于Debug, 输出结点状态
void MCTSNodePrint(const MCTSNode *now)
{
    cout << "=========================" << endl;
    cout << "parent: " << now->parent << endl;
    cout << "this: " << now << endl;
    cout << "node_type: " << now->node_type << endl;
    cout << "children size: " << now->children.size() << endl;
    PrintEncodedCards("parent_action", now->root_action);
    cout << "Q: " << now->Q << endl;
    cout << "visited time: " << now->N << endl;

    cout << "---gamestate---" << endl;
    cout << "last_player_id: " << now->game_state.last_player_id << endl;
    PrintEncodedCards("last_action", now->game_state.last_action);
    for (int k = 0; k < now->valid_actions.size(); k++)
    {
        PrintEncodedCards("valid_action_", now->valid_actions[k], k);
    }
    PrintEncodedCards("lord   ", now->game_state.player_cards[0]);
    PrintEncodedCards("farmer1", now->game_state.player_cards[1]);
    PrintEncodedCards("farmer2", now->game_state.player_cards[2]);
    cout << endl;
}

/// 蒙特卡洛树搜索主体
/// 我的id, 上一个出牌的玩家的id, 下家拥有牌的数量, 上一个出牌的玩家出的牌, 我的牌, 场上已经打出的牌
EncodedCards MCTS(int my_id, int last_player_id, int player1_owned_number, EncodedCards last_action, EncodedCards my_cards, EncodedCards history, bool enable_time_limit = ENABLE_TIME_LIMIT)
{
    // 预留给其他部分50ms
    clock_t time_limit_per_root = (TIME_LIMIT - 50l) / MCTS_RANDOM_ROOTS;

    int player1, player2;
    // ! player1 严格是下家
    if (my_id == 0)
    {
        player1 = 1;
        player2 = 2;
    }
    else if (my_id == 1)
    {
        player1 = 2;
        player2 = 0;
    }
    else
    {
        player1 = 0;
        player2 = 1;
    }

    /// 合法的出牌方案valid_action, 评估值q
    map<EncodedCards, double> valid_actions_map;

    // 多次随机根结点
    for (int i = 0; i < MCTS_RANDOM_ROOTS; i++)
    {
        clock_t start = clock();

        EncodedCards player_cards[3];
        player_cards[my_id] = my_cards;
        // 随机发牌
        giveOtherPlayerCards(my_cards, history, player1_owned_number, player_cards[player1], player_cards[player2]); //...
        // 构建游戏状态
        DoudizhuState game_state(my_id, player_cards, last_player_id, last_action); //...
        MCTSNode *root = new MCTSNode(nullptr, game_state);

        // ! debug 查看根结点
        // cout << "this is root: " << endl;
        // MCTSNodePrint(&root);

        for (int j = 0; (!enable_time_limit && j < MCTS_ITERS) || (enable_time_limit && clock() - start < time_limit_per_root); j++)
        {
            EncodedCards my_choice = 0;
            // 第一个root是指针常量
            MCTSNode *now = treePolicy(root, root);

            if (now == nullptr)
                continue;

            double roll_q = rollOut(now, NUMBER_OF_ROLLOUT);

            // ! debug 查看roll的结果
            // cout << "roll_q: " << roll_q << endl;

            backPropagation(now, roll_q);

            // ! debug 查看拓展的结点
            // MCTSNodePrint(now);
        }

        // 更新根结点的Q
        for (auto it = root->children.begin(); it != root->children.end(); it++)
        {
            MCTSNode *valid_node = *it;
            EncodedCards valid_action = valid_node->root_action;
            // ! 注意是quality!! 否则农民会疯狂让牌
            double q = valid_node->quality();

            valid_actions_map[valid_action] += q / (double)MCTS_RANDOM_ROOTS;
        }

        delete root;
    }

    // 选取最好的action
    EncodedCards best_choice = 0;
    double Q = -1145.14f;
    for (auto it = valid_actions_map.begin(); it != valid_actions_map.end(); it++)
    {
        if ((*it).second >= Q)
        {
            Q = (*it).second;
            best_choice = (*it).first;
        }
    }

    return best_choice;
}

/// 用于获取上一个玩家的身份,
/// 参数: 我的身份, 我的上家是否出牌
int attainLastPlayerIdentity(int my_id, bool shangjia_take_action)
{
    if (shangjia_take_action)
    {
        return (my_id + 2) % 3;
    }
    return (my_id + 1) % 3;
}

// 对接botzone
void botzone()
{
    // 我的牌具体有哪些
    bool my_cards_bm[MAX_CARD_NUM] = {};
    // 我的身份
    // 0 是地主
    // 1, 2 是农民
    int my_id;

    Json::Value input;
    Json::Reader reader;
    string line;
    getline(cin, line);
    reader.parse(line, input);
    // 这对大括号不要删掉
    {
        auto req = input["requests"][0u];
        auto own = req["own"];
        auto history = req["history"];
        // 标记一开始发给我的牌
        for (unsigned i = 0; i < own.size(); ++i)
        {
            my_cards_bm[own[i].asInt()] = true;
        }
        if (history[0u].size() > 0)
        {
            my_id = 2; // 农民乙
        }
        else if (history[1u].size() > 0)
        {
            my_id = 1; // 农民甲
        }
        else
        {
            my_id = 0;
        }
    }

    // 场上已经打出的手牌
    vector<Card> history_cards;

    // 把我出过的牌从初始手牌中去掉, 顺便存入history_cards
    for (unsigned i = 0; i < input["responses"].size(); ++i)
    {
        auto resp = input["responses"][i];
        for (unsigned j = 0; j < resp.size(); ++j)
        {
            my_cards_bm[resp[j].asInt()] = false;
            history_cards.push_back(resp[j].asInt());
        }
    }

    // ! 下家出的牌的数量
    int player1_out_num = 0;
    // 把其他玩家出过的牌存入history
    int turn = input["requests"].size();

    // 如果是第一回合
    if (turn == 1)
        TIME_LIMIT *= 2;

    for (int i = 0; i < turn; i++)
    {
        auto history = input["requests"][i]["history"];
        if (history[1u].size() > 0) // 上家出牌
        {
            for (unsigned j = 0; j < history[1u].size(); ++j)
            {
                int c = history[1u][j].asInt();
                history_cards.push_back(c);
            }
        }
        if (history[0u].size() > 0) // 上上家出牌
        {
            for (unsigned j = 0; j < history[0u].size(); ++j)
            {
                int c = history[0u][j].asInt();
                history_cards.push_back(c);
                player1_out_num++;
            }
        }
    }

    // !下家牌数, 判断下家是不是地主, 地主初始牌数为12, 农民为9
    int MAX_NUM = 9;
    if ((my_id + 1) % 3 == 0)
        MAX_NUM = 12;
    int player1_hold_num = MAX_NUM - player1_out_num;

    // 我当前实际拥有的牌
    vector<Card> my_cards;
    // 待响应的上一手牌（0-53编码）
    vector<Card> last_action;
    last_action.clear();

    for (int i = 0; i < MAX_CARD_NUM; ++i)
    {
        // 如果这牌我没出过，那么加入列表
        if (my_cards_bm[i])
        {
            my_cards.push_back(i);
        }
    }

    // 上一个出牌的玩家的id
    // ! 上一个出牌的可能还是我
    int last_player_id = my_id;

    // 看看上一位玩家出了什么牌
    auto history = input["requests"][input["requests"].size() - 1]["history"];
    if (history[1u].size() > 0) // 上家出牌
    {
        last_player_id = attainLastPlayerIdentity(my_id, true);
        for (unsigned i = 0; i < history[1u].size(); ++i)
        {
            int c = history[1u][i].asInt();
            last_action.push_back(c);
        }
    }
    else if (history[0u].size() > 0) // 上家没出牌，上上家出牌
    {
        last_player_id = attainLastPlayerIdentity(my_id, false);
        for (unsigned i = 0; i < history[0u].size(); ++i)
        {
            int c = history[0u][i].asInt();
            last_action.push_back(c);
        }
    }

    EncodedCards last_action_encoded = toEncodedCardsDirectly(last_action),
                 my_cards_encoded = toEncodedCardsDirectly(my_cards),
                 history_cards_encoded = toEncodedCardsDirectly(history_cards);

    // 进入MCTS
    EncodedCards best_choice = MCTS(my_id, last_player_id, player1_hold_num, last_action_encoded, my_cards_encoded, history_cards_encoded);

    vector<Card> action;

    // 将EncodedCards转化为vector<Card>
    action = decodeAction(best_choice, my_cards);

    Json::Value result, response(Json::arrayValue);
    for (Card c : action)
    {
        response.append(c);
    }
    result["response"] = response;
    Json::FastWriter writer;
    cout << writer.write(result) << endl;
}

// ! 控制台debug工具
void debug()
{
    //定义clock_t变量
    clock_t start, end;

    // 我的牌具体有哪些
    EncodedCards my_cards = NO_CARDS;
    // 我的身份
    // 0 是地主
    // 1, 2 是农民
    int my_id, round;
    string str_player_cards[3];
    // 场上已经打出的手牌
    EncodedCards history = NO_CARDS;

    // ! 输入玩家身份
    cout << "player id: ";
    cin >> my_id;

    // ! 输入玩家, 下家, 上家的手牌 (上家下家随便输入)
    // 9-NINE, 0-TEN, J-JACK, Q-QUEEN, K-KING, A-ACE, 2-TWO, r-Joker, R-JOKER
    cout << "player/downer/uper cards? (e.g. 990JAA22Rr) (0 stands for 10, R stands for JOKER, r stands for Joker)";
    cin >> str_player_cards[my_id] >> str_player_cards[(my_id + 1) % 3] >> str_player_cards[(my_id + 2) % 3];

    for (int i = 0; i < str_player_cards[my_id].length(); i++)
    {
        CardType _card = transCharintoInt(str_player_cards[my_id][i]);
        my_cards = addToEncodedCards(_card, my_cards, 1);
    }

    cout << "how many round: (start from 1)";
    cin >> round;

    int last_player_id = my_id;

    // 上一个玩家的牌
    EncodedCards last_action = NO_CARDS;

    // ! 下家出的牌的数量
    int player1_out_num = 0;

    for (int i = 0; i < round; i++)
    {
        string str_out;
        cout << "round " << i << " downer: (if empty: \"null\")";
        cin >> str_out;
        if (str_out[0] != 'n')
        {
            for (int j = 0; j < str_out.length(); j++)
            {
                CardType _card = transCharintoInt(str_out[j]);
                history = addToEncodedCards(_card, history, 1);
                if (i == round - 1)
                {
                    last_action = addToEncodedCards(_card, last_action, 1);
                }

                player1_out_num++;
            }

            last_player_id = (my_id + 1) % 3;
        }
        cout << "round " << i << " uper: (if empty: \"null\")";
        cin >> str_out;
        if (str_out[0] != 'n')
        {
            if (i == round - 1)
                last_action = NO_CARDS;

            for (int j = 0; j < str_out.length(); j++)
            {
                CardType _card = transCharintoInt(str_out[j]);
                history = addToEncodedCards(_card, history, 1);
                if (i == round - 1)
                {
                    last_action = addToEncodedCards(_card, last_action, 1);
                }
            }

            last_player_id = (my_id + 2) % 3;
        }

        if (i != round - 1)
        {
            cout << "round " << i << " player: (if empty: \"null\")";
            cin >> str_out;
            if (str_out[0] != 'n')
            {
                for (int j = 0; j < str_out.length(); j++)
                {
                    CardType _card = transCharintoInt(str_out[j]);
                    history = addToEncodedCards(_card, history, 1);
                    my_cards = minusFromEncodedCards(_card, my_cards, 1);
                }
                last_player_id = my_id;
            }
        }
    }

    // 地主和农民初始牌数不同
    int MAX_NUM = 9;
    if ((my_id + 1) % 3 == 0)
        MAX_NUM = 12;
    int player1_hold_num = MAX_NUM - player1_out_num;

    // 开始时间
    start = clock();

    // 最好的出牌选择
    EncodedCards best_choice = MCTS(my_id, last_player_id, player1_hold_num, last_action, my_cards, history);

    PrintEncodedCards("best_choice", best_choice);

    // 结束时间
    end = clock();
    // 输出时间（单位:s）
    cout << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}

int main()
{
    srand(time(nullptr));
    botzone();
    // debug();
    return 0;
}

/*
0
99000JJQKA2R
900JQQA22
9JJJQKA2r
1
null
null

1
900JQQA22
9JJJQKA2r
99000JJQKA2R
2
null
JJ
QQ
null
null

1
00QQKKAA2
999JJQA2R
AJJ900QKK22r
3
9QA2R
AJJ9QK22r
QKKAA
null
null
2
null
null


1
JJQKKA22r
null
null
3
null
000JJ
null
null
99QQQ
null
null
2

*/