对称博弈与DFS

博弈论主要考虑游戏中的个体在对抗类场景中的预测行为，并研究它们的优化策略。有如下特征：
1.有两名选手。
2.两名选手交替操作，每次一步，每步都是在有限的合法集合中选取一种进行。
3.在任何情况下，合法操作只取决于情况本身，与选手无关。
4.游戏的败北条件为：当某位选手需要进行操作时，当前没有任何可以执行的合法操作，则该选手败北。
寻找必败态即为针对此类试题给出一种解题思路。
如下图描述了博弈算法的通用结构:

dfs搜索树.png

说明:

1.选手A和B决策逻辑是对称的(MinMax算法)，以对自己分数最大化、对方分数最小化为原则:如在A0状态下做决策,会在[B0,B1,B2]选择分支最高的那个路径;在B的轮次中如B1状态下，就从[A1,A2,A3]中选择分值最小的路径;
2.选手A在某一个状态下，穷举所有合法的决策，生成下一层状态列表,然后轮到B在各个状态下做决策，依次交替.
3.直到某一方胜出，然后更新各个状态的分数.
4.在构建状态节点的时候，注意剪枝，如在某一决策下已经决出胜负就不需要遍历其他决策方案.
可以看出对称博弈的算法本质就是DFS+剪枝来尝试找出一条最优路径，这条路径就是选手的可能致胜的决策方案。

优化方案

dfs作为暴力穷举法，时间复杂度非常高O(n^2)，所以如何剪枝和快速计算状态成了优化的主要方向.
1.目前剪枝优化主要方案是alpha-beta剪枝,本文不涉及.具体方案详见.https://zhuanlan.zhihu.com/p/566795656.
2.MinMax 可以简化为 Negamax它的思想是：父节点的值是各个子节点极大值的相反数，这样避免了上一层取极大值下一层取极小值互相转换的麻烦。如A0的决策选择[B0,B1,B2]分数为B1(+Max)，而在B1选择会选择[A1,A2,A3]中最小的(负极大值).
3.加入置换表缓存节点状态对应的分值，加速状态节点的遍历。这时候要考虑当缓存碰撞的时候直接返回分数，此时这个节点只是有分数，但是没构建下一层的子节点。这个后面代码走读中会说明。
本案例代码地址:https://github.com/naturalleo/doudizhu_endgame
dfs+ negamax伪代码如下:

int negamax(int depth)
{
    if (gameover || depth > MAX_DEPTH) {//达到最大深度返回评估值
        return evaluation;
    }
    int score = -1;
    //遍历决策列表
    for (each possible node) {
        //找负极大值
        int tmp_score = -negamax(depth + 1);
        if (tmp_score > score) {
            score = tmp_score;
            break;  //剪枝
        }
    }
    return score;
}

搜索树简单入门

DFS的一个简单案例就是求解全排列问题,以这个例子作为入门，对DFS有大致的理解。以求解[1,2,3]的全排列为例，搜索树如下:

全排列搜索树.jpeg

流程如下:
第一层站在[0]的位置,有三种选择[1,2,3],如选择1;
第二层有两种选择[2,3],如选择2;
第三层只有一种选择3;
第三层选择完，回溯到第二层做下一个选择3，依次往复。
遍历过程中加入标记数组去重
这样每条从根节点到叶子节点的路径就构成了一个全排列。套用DFS模板代码如下:

class Solution {
    //存放所有路径集合
    private List<List<Integer>> permuteResult = new LinkedList<>();
   //当前的搜索路径
    private LinkedList<Integer> temp = new LinkedList<>();
    //标记是否在路径中
    private boolean[] visited;

    public List<List<Integer>> permute(int[] nums) {
        visited = new boolean[nums.length];
        permuteDfs(nums);
        return permuteResult;
    }

    private void permuteDfs(int[] nums) {
        //step1:边界条件
        if (temp.size() == nums.length) {
            permuteResult.add(new LinkedList<>(temp));
            return;
        }
        //step2:遍历选项
        // 1.排列和顺序有关，所以前后顺序不同排列也不同，所以选项都从第一个开始
        // 2.去重，引入标记visited
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            //step3:选择元素加入路径
            temp.add(nums[I]);
            visited[i] = true;
            //step4:往下层搜索树递归
            permuteDfs(nums);
            //step5:回溯，返回上一层节点
            temp.removeLast();
            visited[i] = false;
        }
    }
}
//结果如下:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

主要流程就是站在一个节点上，遍历可选列表做选择，直到叶子节点。对称博弈搜索树也是类似的思想。

斗地主残局博弈代码分析

核心类说明

CardSet

CardSet描述牌组，核心其实是个位图bitset.

class CardSet {
      ...
     private:
    std::bitset<64> card_mask_;
      ...
}

从低位开始 ’3‘(也就是0)存储在0,1,2,3位， 有多少张牌就有多少位为true比如 ['3', '3', '4', '5'] 在 bitset 中表示为:

0001 0001 0011

此外还提供了一系列写入牌信息的方法，如设置对子、王炸、单张之类的api.

//cardset.h
void CardSet::set_rocket()
{
    card_mask_.set((size_t) (14 << 2));
    card_mask_.set((size_t) (13 << 2));
}

void CardSet::set_single(int8_t card, bool val)
{
    card_mask_.set((size_t) (card << 2), val);
}

void CardSet::set_pair(int8_t card, bool val)
{
    card <<= 2;
    card_mask_.set((size_t) card, val);
    card_mask_.set((size_t) (card + 1), val);
}
//字串转bitset
void CardSet::from_string(std::string string){
    ....
}

牌型Pattern

Pattern表示能打出去的牌组(如单张、对子、三带1等)，双方的手牌就是Pattern的集合，每一次出牌都是打出一个Pattern。

struct Pattern {
    //牌型的大小
    int8_t  power{};
    //牌的类型，对子、单张等牌组类型
    Type    type{};
    //包含的牌
    CardSet hand;
};

搜索树节点TreeNode

这个是搜索树的状态节点，主要包括:
1.轮次:0表示地主出牌,farmer表示农民出牌
2.分数:1表示当前角色赢，-1表示当前角色输
3.地主和农民当前的手牌

4. last_move表示对手打出去的牌，也就是父节点做的决策打出的那组牌,决定当前角色能打出那些牌组，打出的牌组类型需要一致，大小比last_move大。

struct TreeNode {
        int8_t turn;       //角色轮次 0: lord 1:farmer
        int8_t score; //-1表示输， 1表示赢
        CardSet lord;//出牌后的双方手牌
        CardSet farmer;
        Pattern *last_move;//对方出的牌
        std::vector<TreeNode *> child;//可以做出的出牌选择
    };

置换表TranspositionTable

本质是个Map: unordered_map,用于快速递归构建树,缓存命中立即返回分值给TreeNode，缓存TreeNode对应的分数.
1.key:node的hash;
2.value:node的分数。

class TranspositionTable {
    public:

        TranspositionTable() {
            table_.reserve(TRANSPOSITION_TABLE_INIT_SIZE);
        }

        ~TranspositionTable() = default;

        size_t size();

        void add(TreeNode *node);

        //return score from table, if not in table return 0
        int8_t get(TreeNode *node);

    private:
        //value=score
        //置换表: key为TreeNode的hash值，value是分值
        std::unordered_map<uint64_t, int8_t> table_;

        uint64_t gen_key(TreeNode *node);
    };

Negamax

算法实现的核心类，入口:

TreeNode *Negamax::search(const CardSet &lord, const CardSet &farmer) {
        CardSet pass;
        Pattern start = {-1, Pass, pass};
        //根节点，地主先出
        auto root = new TreeNode{0, 0, lord, farmer, &start};
        //开始dfs
        negamax(root);
        tree_ = root;
        deque<TreeNode*>q;
        //bfs打印搜索树
        dumpSearch(tree_, q);

        return root;
    }

DFS入口:

int8_t Negamax::negamax(TreeNode *node) {
        nodes_searched_ += 1;
        int8_t search = table_.get(node);
        //缓存命中，直接返回分值,注意这里是不会给node挂载子节点的。
        if (search != 0) {
            hash_hit_ += 1;
            return search;
        }
        //step1:这个node能出那些牌组?
        //step2:每个出牌方案都对应一个子节点
        gen_nodes(node);
        int8_t score = -1;
        //step3:开始对children做dfs
        for (TreeNode *&child: node->child) {
            int8_t val{};
            //basecase
            if (child->score != 0) {//+/-1表示出牌方案child已经决出胜负
                //负极大值赋分,这里只有输和赢两种状态，所以取反即可
                val = -child->score;
                nodes_searched_ += 1;
            } else {
                //dfs
                val = -negamax(child);
            }
            //如果有让自己赢的情况，则不需要遍历其他出牌策略了,更新分数为赢
            if (val > 0) {
                score = val;
                break;          //发生剪枝
            }
        }

        node->score = score;
        table_.add(node);
        //step4:剪枝，删掉农民赢的节点
        pruning_tree(node);

        return score;
    }

整个流程主要分四部:
Step1.根据对手的出牌和当前我的手牌，计算我可以打出那些牌组。
Step2.遍历这些牌组，执行出牌操作，构造子节点列表加入搜索树。
Step3.遍历子节点列表，如果子节点是叶子节点（已经分出胜负)则设置分数结束遍历，如果不是则继续对子节点做DFS递归。
Step4.剪枝，删掉会让地主输的节点。
其中前1、2步在 gen_nodes(node)中，3在循环体里实现，4在pruning_tree(node)中。
下面分别分析这四个步骤:

算法流程

构造子节点列表

/**
 * 计算下一层节点
 * @param node
 */
    void Negamax::gen_nodes(TreeNode *node) {
        if (node->turn == 1) { //农民出牌
          //....
        } else {//lord turn
            //当前能出的牌组列表
            std::vector<Pattern *> selections;
            //根据当前双方牌组和对手出的牌，计算所有能管住对方的牌组
            doudizhu_.next_hand(node->lord, node->last_move, selections);
            node->child.reserve(selections.size());
            for (Pattern *move: selections) {
                CardSet after_play;
                doudizhu_.play(node->lord, move, after_play);

                auto child = new TreeNode{1, 0, after_play, node->farmer, move};
                if (after_play.empty()) {
                    child->score = -1;//-1表示对手赢了

                    for (TreeNode *i: node->child) {
                        delete I;
                    }
                    std::vector<TreeNode *>().swap(node->child);
                    node->child.emplace_back(child);
                    return;
                }
                node->child.emplace_back(child);
            }
        }
    }

农民的和地主逻辑对称.只看地主的逻辑即可。先上流程图:

Negamax生成决策子节点流程-2.png

先看如何构建能出的牌组:

doudizhu_.next_hand(node->lord, node->last_move, selections);
/**
 * 计算能出牌的牌组
 * @param hand 我当前的手牌
 * @param last 对手出的牌
 * @param next_moves 能出的牌组列表
 */
void DouDiZhuHand::next_hand(const CardSet& hand, Pattern* last, std::vector<Pattern *> &next_moves)
{
    //搜索的顺序对剪枝的发生影响很大,
    // 这里把 pass 作为最后考虑的选项
    next_moves.reserve(50);
    //王炸无视对方出的牌last
    get_rocket(hand, next_moves);
    //我能出对子吗?
    get_pair(hand, last, next_moves);
   
    //其他类型的牌组都是类似逻辑....

    get_pass(hand, last, next_moves);
}

以出对子为例看看：

/**
 * 计算我能出对子的路径，加到next_moves集合里
 * @param hand
 * @param last 表示对方出的牌组
 * @param next_moves
 */
void DouDiZhuHand::get_pair( const CardSet& hand, Pattern* last, std::vector<Pattern *> &next_moves)
{
    /**
     * 如果对方pass或者出的对子，则查找手牌hand里有没有比last大的对子，注意Pass的大小为-1.
     */
    if (last->type == Pass || last->type == Pair) {
        //遍历15张牌，优先出小牌
        for (int8_t i = 0; i < 15; ++i) {
            //手牌有对子,且对子比对手的大
            if (hand.is_pair(i) && i > last->power) {
                //构建要出的牌
                CardSet res;
                res.set_pair(i);
                //生成一个能出的牌组，加到next_moves集合
                Pattern* tmp = pattern_pool_.get(i, Pair, res);
                //添加
                next_moves.emplace_back(tmp);
            }
        }

    }
}

代码比较简单，从小到大遍历手牌，如果对方出的是对子或者没出，则看手牌有没有比last大的对子，如果有则构建牌组Pattern加到next_moves集合。其他逻辑也是类似。还有比较特殊的一直出牌情况是Pass,不出牌的决策需要挂在child最后，优先级最低：

void DouDiZhuHand::get_pass(const CardSet& hand, Pattern* last, std::vector<Pattern *> &next_moves)
{
    //对方出牌了，本方pass
    if (last->type != Pass) {
        CardSet res;//空牌组
        next_moves.emplace_back(this->pattern_pool_.get(-1, Pass, res));
    } else {
        //can not pass twice
    }
}

走完DouDiZhuHand::next_hand方法，Negamax::gen_nodes方法里的selections就有了当前所有能出的牌组的集合。

void Negamax::gen_nodes(TreeNode *node){
    //...
    doudizhu_.next_hand(node->farmer, node->last_move, selections);
   //遍历能出的牌组
     for (Pattern *move: selections) {
                CardSet after_play;
                //打出牌组move后，node->lord= after_play更新:去掉move中的牌
                doudizhu_.play(node->lord, move, after_play);
                //构建子节点，也就是农民轮次的状态节点:
               //轮次:农民
              //地主手牌: after_play
              //农民手牌不变
              //move就是对手(地主)打出的牌
                auto child = new TreeNode{1, 0, after_play, node->farmer, move};
               //如果地主手牌全部打完，表示地主赢了，那对农民child而言，分数=-1为输。
                if (after_play.empty()) {
                    child->score = -1;//地主赢，农民输child分数=-1
                    //删除无用空节点
                    for (TreeNode *i: node->child) {
                        delete I;
                    }
                    std::vector<TreeNode *>().swap(node->child);
                    //走到决胜的节点了，已经有赢的方案了，后续的兄弟节点就不需要遍历了
                    node->child.emplace_back(child);
                    return;
                }
                //地主牌没空，子节点加入搜索树
                node->child.emplace_back(child);
            }
}

主要流程如下:
1.地主出牌打出move，更新地主手牌，农民手牌不变。
2.构造下一层节点: 轮次变成农民，双方手牌,move就是农民节点的last_move。
3.如果地主出牌后，手牌空了，则农民节点设置分值-1，已经找到了赢的方案，不用遍历兄弟方案了,挂载节点后直接返回。
目前为止gen_nodes流程已经走完，完成整个算法的Step1和Step2，此时node下已经挂载了所有出牌决策的子节点。以下面最简单的手牌为例:
地主:23
农民:4
剪枝前的搜索树如下，后面的分析都是基于下面的这个决策树.

搜索树样例.png

可以发现改决策树确定了两条路径，结果分别是地主赢和输.
下面结合这个图来分析算法的第三步，负极大值dfs流程.

Negamax递归逻辑

        int8_t score = -1;
        //step3:开始对children做dfs
        //说明1：构建了当前node的下一层子节点后，遍历这些子节点
        for (TreeNode *&child: node->child) {
             //更新子节点“归上来的分值”
            int8_t val{};
            //basecase
            //说明 2.如果某一个决策已经决出胜负，则node分数去反；
            if (child->score != 0) {//+/-1表示出牌方案child已经决出胜负
                //负极大值赋分
                val = -child->score;
                nodes_searched_ += 1;
            } else {
             // 说明 3..如果某一个决策还没决出胜负，则继续深度递归；
                //dfs
                val = -negamax(child);
            }
            // 说明 4. 如果某一个决策能让node赢，得到一条赢的路径，则不需要遍历其他兄弟节点了。
            if (val > 0) {
                score = val;
                break;  
            }
        }
        node->score = score;
        table_.add(node);

说明1.构建了当前node的下一层子节点后，遍历这些子节点，如搜索树的第二层；
说明 2.如果某一个决策已经决出胜负，则node分数去反，对应最下层的俩叶子节点,方法返回的时候更新父节点的分值；
说明 3..如果某一个决策还没决出胜负，则继续深度递归，对应地主赢的路径的二三层节点；
说明 4. 如果某一个决策能让node赢，得到一条赢的路径，则不需要遍历其他兄弟节点了,对应搜索树的叶子节点。
下面看最后一步：将地主输的路径进行剪枝。

剪枝

   //...
   table_.add(node);
   //剪枝，删掉农民赢的节点
  pruning_tree(node);


//....
void Negamax::pruning_tree(TreeNode *node) {
        if (node->turn == 0) {//站在地主的立场删掉让地主输的节点，child.back()->score=1表示农民赢,不允许，剪枝!
            //删除掉地主不能赢的节点
            while (!node->child.empty() && node->child.back()->score != -1) {
                destroy_tree(node->child.back());
                node->child.pop_back();
            }
            //删除掉空节点，剩下的都是合法节点，幺麽输幺麽赢
            if (!node->child.empty()) {
                std::swap(node->child.front(), node->child.back());
                //然后
                while (node->child.size() > 1) {
                    destroy_tree(node->child.back());
                    node->child.pop_back();
                }
            } 
        } else {
            //not pruning
        }
    }

此处逻辑也比较简单，剪掉地主输的出牌路径即可。走到这里，图中左边的路径被删除。整棵树只保留了地址赢的路径。

置换表的节点的补丁

在回头看看Negamax算法的BaseCase:

        int8_t search = table_.get(node);
        //缓存命中，直接返回分值,这里是没有构建子节点的。
        if (search != 0) {
            hash_hit_ += 1;
            return search;
        }

缓存命中的时候直接返回了分数，没有构建子节点。所以在打印搜索树的时候遇到这种节点需要构建它的搜索树，见 restart_search(node, last);后面模拟过程中会说到。

模拟博弈

//process_result(root->child[0]);
/**
 * 在地主能赢的情况下，根据农民出牌打印节点。child是地主。叶子节点都是农民输。
 * @param node 农民
 */
    void Solution::process_result(TreeNode *node) {
         //记录农民出的牌,用于缓存命中时构建地主的搜索树
        Pattern *last = nullptr;

        bool search = true;
        while (!node->child.empty() && search) {
            CardSet hand;
            hand.from_string(input_stdin("输入农民出牌:"));
            //找农民出牌的对应路径
            for (auto child: node->child) {
                //路径匹配
                if (child->last_move->hand == hand) {
                    //更新农民出的牌
                    last = child->last_move;
                   //还没到叶子节点
                    if (!child->child.empty()) {
                        //更新node为下一层的农民节点
                        node = child->child[0];
                       //打印农民节点
                        std::cout << "------------------------------" << "\n";
                        std::cout << BOLDGREEN << "地主出: [" << node->last_move->hand.str() << "]" << RESET << "\n";
                        std::cout << "currt loard hand: [" << node->lord.str() << "]\n";
                        std::cout << "currt farmer hand:[" << node->farmer.str() << "]\n";
                        std::cout << "currt turn:[" << (int)(node->turn) << "]\n";
                        std::cout << "currt score:[" << (int)(node->score) << "]\n";

                    } else {//到叶子节点了，结束循环，注意此时可能是置换表中的节点，没有child,但不是叶子节点。
                        search = false;
                    }
                } 
            }
        }

        //........
        //此处的场景，构建搜索树的时候，如果用的缓存节点，此时直接返回分值，没有构建树,所以需要当前的农民节点+农民要出的牌构建新的搜索树
        if (!node->lord.empty() && last != nullptr) {
            std::cout << "-------------hash碰撞了，构建树-----------------=" << search << "\n";
            restart_search(node, last);

        } else {
            //finsh process
        }
    }

1.主要逻辑是根据农民的出牌找到匹配的路径，然后打印农民出牌后的农民节点信息，直到叶子节点
2.前面说的置换表的补丁也是在这里打的，如果碰到缓存节点，且农民已经出牌，那么就代表还未决出胜负，那么就用当前的农民节点信息和农民要打出的牌构建地主节点的搜索树，逻辑如下:

 void Solution::restart_search(TreeNode *node, Pattern *last) {
        CardSet lord = node->lord;
       //去掉农民要打出的牌
        CardSet farmer = node->farmer;
        farmer.remove(last->hand);
        Pattern last_{last->power, last->type, last->hand};
        std::cout << "restart search..." << "\n";

        reset_engine();
        //构建新的地主的节点
        TreeNode *re = engine_->search(lord, farmer, &last_);
        //继续模拟博弈过程
        if (!re->child.empty()) {
            std::cout << "出: [" << re->child[0]->last_move->hand.str() << "]\n";
            //地主出牌了，等待农民出牌
            process_result(re->child[0]);

        } else {
            std::cout << "无法取胜" << "\n";
        }
    }

测试用例打印

输入不带空格,'10'用'0'（零）代替
如：[大王 小王 2 A 10 9 9 9 4]
输入：zy2a09994
地主先出
------------------------------
输入地主手牌:
23
输入农民手牌:
4
------------------------------
--------------打印搜索树start----------------
出: [Pass]
currt loard hand: [2 3]
currt farmer hand:[4]
currt turn:[0]
currt score:[1]
出: [2]
currt loard hand: [3]
currt farmer hand:[4]
currt turn:[1]
currt score:[-1]
出: [Pass]
currt loard hand: [3]
currt farmer hand:[4]
currt turn:[0]
currt score:[1]
出: [3]
currt loard hand: [Pass]
currt farmer hand:[4]
currt turn:[1]
currt score:[-1]
--------------打印搜索树end----------------
nodes calculated: 6
search time: 9.8e-05 seconds.
transposition table hit rate: 0%

出:[2]
输入农民出牌:
P
------------------------------
地主出: [3]
currt loard hand: [Pass]
currt farmer hand:[4]
currt turn:[1]
currt score:[-1]
-------------退出process_result循环-----------------=1
currt loard hand: [Pass]
currt farmer hand:[4]

总结：
对称博弈的算法的本质就是暴力穷举，主要是包括搜索树的构建与剪枝，本文中的Negamax和置换表都是为了加速这个构建过程，剪枝逻辑也是直接剪掉让自己输的节点，减少了接近一半的节点。其他如五子棋象棋的实现也是类似的流程，复杂的是它们需要针对一个棋局，找出一个合适的估分函数用于决策树的选择。