對稱博弈與DFS

博弈論主要考慮游戲中的個體在對抗類場景中的預測行為蚓峦，并研究它們的優(yōu)化策略。有如下特征：
1.有兩名選手济锄。
2.兩名選手交替操作暑椰，每次一步，每步都是在有限的合法集合中選取一種進行荐绝。
3.在任何情況下一汽，合法操作只取決于情況本身，與選手無關低滩。
4.游戲的敗北條件為：當某位選手需要進行操作時召夹，當前沒有任何可以執(zhí)行的合法操作，則該選手敗北恕沫。
尋找必敗態(tài)即為針對此類試題給出一種解題思路监憎。
如下圖描述了博弈算法的通用結構:

dfs搜索樹.png

說明:

1.選手A和B決策邏輯是對稱的(MinMax算法)，以對自己分數(shù)最大化婶溯、對方分數(shù)最小化為原則:如在A0狀態(tài)下做決策,會在[B0,B1,B2]選擇分支最高的那個路徑;在B的輪次中如B1狀態(tài)下鲸阔，就從[A1,A2,A3]中選擇分值最小的路徑;
2.選手A在某一個狀態(tài)下偷霉，窮舉所有合法的決策，生成下一層狀態(tài)列表,然后輪到B在各個狀態(tài)下做決策褐筛，依次交替.
3.直到某一方勝出类少，然后更新各個狀態(tài)的分數(shù).
4.在構建狀態(tài)節(jié)點的時候，注意剪枝渔扎，如在某一決策下已經(jīng)決出勝負就不需要遍歷其他決策方案.
可以看出對稱博弈的算法本質就是DFS+剪枝來嘗試找出一條最優(yōu)路徑硫狞，這條路徑就是選手的可能致勝的決策方案。

優(yōu)化方案

dfs作為暴力窮舉法赞警，時間復雜度非常高O(n^2)妓忍，所以如何剪枝和快速計算狀態(tài)成了優(yōu)化的主要方向.
1.目前剪枝優(yōu)化主要方案是alpha-beta剪枝,本文不涉及.具體方案詳見.https://zhuanlan.zhihu.com/p/566795656.
2.MinMax 可以簡化為 Negamax它的思想是：父節(jié)點的值是各個子節(jié)點極大值的相反數(shù)，這樣避免了上一層取極大值下一層取極小值互相轉換的麻煩愧旦。如A0的決策選擇[B0,B1,B2]分數(shù)為B1(+Max)世剖，而在B1選擇會選擇[A1,A2,A3]中最小的(負極大值).
3.加入置換表緩存節(jié)點狀態(tài)對應的分值，加速狀態(tài)節(jié)點的遍歷笤虫。這時候要考慮當緩存碰撞的時候直接返回分數(shù)旁瘫，此時這個節(jié)點只是有分數(shù)，但是沒構建下一層的子節(jié)點琼蚯。這個后面代碼走讀中會說明酬凳。
本案例代碼地址: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峦睡，依次往復翎苫。
遍歷過程中加入標記數(shù)組去重
這樣每條從根節(jié)點到葉子節(jié)點的路徑就構成了一個全排列。套用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:回溯，返回上一層節(jié)點
            temp.removeLast();
            visited[i] = false;
        }
    }
}
//結果如下:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

主要流程就是站在一個節(jié)點上，遍歷可選列表做選擇热某，直到葉子節(jié)點。對稱博弈搜索樹也是類似的思想作岖。

斗地主殘局博弈代碼分析

核心類說明

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;
};

搜索樹節(jié)點TreeNode

這個是搜索樹的狀態(tài)節(jié)點渔彰，主要包括:
1.輪次:0表示地主出牌,farmer表示農(nóng)民出牌
2.分數(shù):1表示當前角色贏，-1表示當前角色輸
3.地主和農(nóng)民當前的手牌

4. last_move表示對手打出去的牌推正，也就是父節(jié)點做的決策打出的那組牌,決定當前角色能打出那些牌組恍涂，打出的牌組類型需要一致，大小比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對應的分數(shù).
1.key:node的hash;
2.value:node的分數(shù)尊残。

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

算法實現(xiàn)的核心類，入口:

TreeNode *Negamax::search(const CardSet &lord, const CardSet &farmer) {
        CardSet pass;
        Pattern start = {-1, Pass, pass};
        //根節(jié)點寝衫，地主先出
        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掛載子節(jié)點的。
        if (search != 0) {
            hash_hit_ += 1;
            return search;
        }
        //step1:這個node能出那些牌組?
        //step2:每個出牌方案都對應一個子節(jié)點
        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已經(jīng)決出勝負
                //負極大值賦分,這里只有輸和贏兩種狀態(tài)慰毅，所以取反即可
                val = -child->score;
                nodes_searched_ += 1;
            } else {
                //dfs
                val = -negamax(child);
            }
            //如果有讓自己贏的情況隘截，則不需要遍歷其他出牌策略了,更新分數(shù)為贏
            if (val > 0) {
                score = val;
                break;          //發(fā)生剪枝
            }
        }

        node->score = score;
        table_.add(node);
        //step4:剪枝，刪掉農(nóng)民贏的節(jié)點
        pruning_tree(node);

        return score;
    }

整個流程主要分四部:
Step1.根據(jù)對手的出牌和當前我的手牌汹胃，計算我可以打出那些牌組技俐。
Step2.遍歷這些牌組，執(zhí)行出牌操作统台，構造子節(jié)點列表加入搜索樹。
Step3.遍歷子節(jié)點列表啡邑，如果子節(jié)點是葉子節(jié)點（已經(jīng)分出勝負)則設置分數(shù)結束遍歷贱勃，如果不是則繼續(xù)對子節(jié)點做DFS遞歸。
Step4.剪枝谤逼，刪掉會讓地主輸?shù)墓?jié)點贵扰。
其中前1、2步在 gen_nodes(node)中流部，3在循環(huán)體里實現(xiàn)戚绕，4在pruning_tree(node)中。
下面分別分析這四個步驟:

算法流程

構造子節(jié)點列表

/**
 * 計算下一層節(jié)點
 * @param node
 */
    void Negamax::gen_nodes(TreeNode *node) {
        if (node->turn == 1) { //農(nóng)民出牌
          //....
        } else {//lord turn
            //當前能出的牌組列表
            std::vector<Pattern *> selections;
            //根據(jù)當前雙方牌組和對手出的牌枝冀，計算所有能管住對方的牌組
            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);
            }
        }
    }

農(nóng)民的和地主邏輯對稱.只看地主的邏輯即可舞丛。先上流程圖:

Negamax生成決策子節(jié)點流程-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)
{
    //搜索的順序對剪枝的發(fā)生影響很大,
    // 這里把 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張牌谷誓，優(yōu)先出小牌
        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最后恩商，優(yōu)先級最低：

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);
                //構建子節(jié)點，也就是農(nóng)民輪次的狀態(tài)節(jié)點:
               //輪次:農(nóng)民
              //地主手牌: after_play
              //農(nóng)民手牌不變
              //move就是對手(地主)打出的牌
                auto child = new TreeNode{1, 0, after_play, node->farmer, move};
               //如果地主手牌全部打完研叫，表示地主贏了锤窑，那對農(nóng)民child而言，分數(shù)=-1為輸嚷炉。
                if (after_play.empty()) {
                    child->score = -1;//地主贏渊啰，農(nóng)民輸child分數(shù)=-1
                    //刪除無用空節(jié)點
                    for (TreeNode *i: node->child) {
                        delete I;
                    }
                    std::vector<TreeNode *>().swap(node->child);
                    //走到?jīng)Q勝的節(jié)點了，已經(jīng)有贏的方案了申屹，后續(xù)的兄弟節(jié)點就不需要遍歷了
                    node->child.emplace_back(child);
                    return;
                }
                //地主牌沒空绘证，子節(jié)點加入搜索樹
                node->child.emplace_back(child);
            }
}

主要流程如下:
1.地主出牌打出move，更新地主手牌哗讥，農(nóng)民手牌不變嚷那。
2.構造下一層節(jié)點: 輪次變成農(nóng)民，雙方手牌,move就是農(nóng)民節(jié)點的last_move杆煞。
3.如果地主出牌后魏宽，手牌空了，則農(nóng)民節(jié)點設置分值-1决乎，已經(jīng)找到了贏的方案队询，不用遍歷兄弟方案了,掛載節(jié)點后直接返回。
目前為止gen_nodes流程已經(jīng)走完构诚，完成整個算法的Step1和Step2蚌斩，此時node下已經(jīng)掛載了所有出牌決策的子節(jié)點。以下面最簡單的手牌為例:
地主:23
農(nóng)民:4
剪枝前的搜索樹如下范嘱，后面的分析都是基于下面的這個決策樹.

搜索樹樣例.png

可以發(fā)現(xiàn)改決策樹確定了兩條路徑送膳，結果分別是地主贏和輸.
下面結合這個圖來分析算法的第三步员魏，負極大值dfs流程.

Negamax遞歸邏輯

        int8_t score = -1;
        //step3:開始對children做dfs
        //說明1：構建了當前node的下一層子節(jié)點后，遍歷這些子節(jié)點
        for (TreeNode *&child: node->child) {
             //更新子節(jié)點“歸上來的分值”
            int8_t val{};
            //basecase
            //說明 2.如果某一個決策已經(jīng)決出勝負肠缨，則node分數(shù)去反逆趋；
            if (child->score != 0) {//+/-1表示出牌方案child已經(jīng)決出勝負
                //負極大值賦分
                val = -child->score;
                nodes_searched_ += 1;
            } else {
             // 說明 3..如果某一個決策還沒決出勝負，則繼續(xù)深度遞歸晒奕；
                //dfs
                val = -negamax(child);
            }
            // 說明 4. 如果某一個決策能讓node贏闻书，得到一條贏的路徑，則不需要遍歷其他兄弟節(jié)點了脑慧。
            if (val > 0) {
                score = val;
                break;  
            }
        }
        node->score = score;
        table_.add(node);

說明1.構建了當前node的下一層子節(jié)點后魄眉，遍歷這些子節(jié)點，如搜索樹的第二層闷袒；
說明 2.如果某一個決策已經(jīng)決出勝負坑律，則node分數(shù)去反，對應最下層的倆葉子節(jié)點,方法返回的時候更新父節(jié)點的分值囊骤；
說明 3..如果某一個決策還沒決出勝負晃择，則繼續(xù)深度遞歸，對應地主贏的路徑的二三層節(jié)點也物；
說明 4. 如果某一個決策能讓node贏宫屠，得到一條贏的路徑，則不需要遍歷其他兄弟節(jié)點了,對應搜索樹的葉子節(jié)點滑蚯。
下面看最后一步：將地主輸?shù)穆窂竭M行剪枝浪蹂。

剪枝

   //...
   table_.add(node);
   //剪枝，刪掉農(nóng)民贏的節(jié)點
  pruning_tree(node);


//....
void Negamax::pruning_tree(TreeNode *node) {
        if (node->turn == 0) {//站在地主的立場刪掉讓地主輸?shù)墓?jié)點告材，child.back()->score=1表示農(nóng)民贏,不允許坤次，剪枝!
            //刪除掉地主不能贏的節(jié)點
            while (!node->child.empty() && node->child.back()->score != -1) {
                destroy_tree(node->child.back());
                node->child.pop_back();
            }
            //刪除掉空節(jié)點，剩下的都是合法節(jié)點斥赋，幺麼輸幺麼贏
            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
        }
    }

此處邏輯也比較簡單缰猴，剪掉地主輸?shù)某雠坡窂郊纯伞Ｗ叩竭@里疤剑，圖中左邊的路徑被刪除洛波。整棵樹只保留了地址贏的路徑。

置換表的節(jié)點的補丁

在回頭看看Negamax算法的BaseCase:

        int8_t search = table_.get(node);
        //緩存命中骚露，直接返回分值,這里是沒有構建子節(jié)點的。
        if (search != 0) {
            hash_hit_ += 1;
            return search;
        }

緩存命中的時候直接返回了分數(shù)缚窿，沒有構建子節(jié)點棘幸。所以在打印搜索樹的時候遇到這種節(jié)點需要構建它的搜索樹，見 restart_search(node, last);后面模擬過程中會說到倦零。

模擬博弈

//process_result(root->child[0]);
/**
 * 在地主能贏的情況下误续，根據(jù)農(nóng)民出牌打印節(jié)點吨悍。child是地主。葉子節(jié)點都是農(nóng)民輸蹋嵌。
 * @param node 農(nóng)民
 */
    void Solution::process_result(TreeNode *node) {
         //記錄農(nóng)民出的牌,用于緩存命中時構建地主的搜索樹
        Pattern *last = nullptr;

        bool search = true;
        while (!node->child.empty() && search) {
            CardSet hand;
            hand.from_string(input_stdin("輸入農(nóng)民出牌:"));
            //找農(nóng)民出牌的對應路徑
            for (auto child: node->child) {
                //路徑匹配
                if (child->last_move->hand == hand) {
                    //更新農(nóng)民出的牌
                    last = child->last_move;
                   //還沒到葉子節(jié)點
                    if (!child->child.empty()) {
                        //更新node為下一層的農(nóng)民節(jié)點
                        node = child->child[0];
                       //打印農(nóng)民節(jié)點
                        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 {//到葉子節(jié)點了育瓜，結束循環(huán)，注意此時可能是置換表中的節(jié)點栽烂，沒有child,但不是葉子節(jié)點躏仇。
                        search = false;
                    }
                } 
            }
        }

        //........
        //此處的場景，構建搜索樹的時候腺办，如果用的緩存節(jié)點焰手，此時直接返回分值，沒有構建樹,所以需要當前的農(nóng)民節(jié)點+農(nóng)民要出的牌構建新的搜索樹
        if (!node->lord.empty() && last != nullptr) {
            std::cout << "-------------hash碰撞了怀喉，構建樹-----------------=" << search << "\n";
            restart_search(node, last);

        } else {
            //finsh process
        }
    }

1.主要邏輯是根據(jù)農(nóng)民的出牌找到匹配的路徑书妻，然后打印農(nóng)民出牌后的農(nóng)民節(jié)點信息，直到葉子節(jié)點
2.前面說的置換表的補丁也是在這里打的躬拢，如果碰到緩存節(jié)點躲履，且農(nóng)民已經(jīng)出牌，那么就代表還未決出勝負聊闯，那么就用當前的農(nóng)民節(jié)點信息和農(nóng)民要打出的牌構建地主節(jié)點的搜索樹工猜，邏輯如下:

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

        reset_engine();
        //構建新的地主的節(jié)點
        TreeNode *re = engine_->search(lord, farmer, &last_);
        //繼續(xù)模擬博弈過程
        if (!re->child.empty()) {
            std::cout << "出: [" << re->child[0]->last_move->hand.str() << "]\n";
            //地主出牌了，等待農(nóng)民出牌
            process_result(re->child[0]);

        } else {
            std::cout << "無法取勝" << "\n";
        }
    }

測試用例打印

輸入不帶空格,'10'用'0'（零）代替
如：[大王 小王 2 A 10 9 9 9 4]
輸入：zy2a09994
地主先出
------------------------------
輸入地主手牌:
23
輸入農(nóng)民手牌:
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]
輸入農(nóng)民出牌:
P
------------------------------
地主出: [3]
currt loard hand: [Pass]
currt farmer hand:[4]
currt turn:[1]
currt score:[-1]
-------------退出process_result循環(huán)-----------------=1
currt loard hand: [Pass]
currt farmer hand:[4]

總結：
對稱博弈的算法的本質就是暴力窮舉馅袁，主要是包括搜索樹的構建與剪枝域慷，本文中的Negamax和置換表都是為了加速這個構建過程，剪枝邏輯也是直接剪掉讓自己輸?shù)墓?jié)點汗销，減少了接近一半的節(jié)點犹褒。其他如五子棋象棋的實現(xiàn)也是類似的流程，復雜的是它們需要針對一個棋局弛针，找出一個合適的估分函數(shù)用于決策樹的選擇叠骑。