最大最小搜索，alpha beta 剪枝

客官°小女子只卖身不卖艺 2022-04-10 08:48 148阅读 0赞

《对弈程序基本技术》专题 最小-最大搜索：[http://www.xqbase.com/computer/search\_minimax.htm][http_www.xqbase.com_computer_search_minimax.htm]  
《对弈程序基本技术》专题 Alpha-Beta搜索 ：[http://www.xqbase.com/computer/search\_alphabeta.htm][http_www.xqbase.com_computer_search_alphabeta.htm]  
Wikipedia MinMax ：[http://en.wikipedia.org/wiki/Minimax][http_en.wikipedia.org_wiki_Minimax]  
Wiki Alpha–beta pruning ：[http://en.wikipedia.org/wiki/Alpha%E2%80%93beta\_pruning][http_en.wikipedia.org_wiki_Alpha_E2_80_93beta_pruning]  
Minmax Explained：[http://ai-depot.com/articles/minimax-explained/1/][http_ai-depot.com_articles_minimax-explained_1]  
讲解极小极大 (Minimax Explained) \[译\] ：[http://www.starming.com/index.php?action=plugin&v=wave&tpl=union&ac=viewgrouppost&gid=34694&tid=15725][http_www.starming.com_index.php_action_plugin_v_wave_tpl_union_ac_viewgrouppost_gid_34694_tid_15725]  
最小最大原理与搜索方法：[http://blog.pfan.cn/rickone/16930.html][http_blog.pfan.cn_rickone_16930.html]

个人理解：

在博弈中够找一颗博弈树，每层的节点在同一个状态，别且每个节点都有一个取胜的评估值，分为max状态和min状态，比如玩家A对应max状态，玩家B对应min状态。目的是A要使自己的评估值最大，B要使自己的评估值最小（B的评估值用负数表示，这样方便理解）。

max状态要走到min状态选择什么样的路径呢？先不要从玩家A自身的着点考虑，从A的角度去看B，如果A这样着点，估计B会走哪些状态得到的min值情况如何，然后从中选择一个B所有min值中最大的那个（负数最大，绝对值最小），显然这样对A是最有利的。孙子有云“知己知彼，百战不怠也”～

对B来说同样也是如此，如果AB的水平一样的话，那结果就取决于先手和后手了，所以结果会有唯一解。

关于alpha-beta剪枝。还是站在A的角度考虑。A要取使得B的所有min值中最大（负数）的那个状态，那可以对事先得到过的最小状态做一个记录，如果出现比最大（负数）的那个状态小的，则这个分支就可以被减掉，这是alpah剪枝。同理，从B的角度考虑就是去max值最小的，这是beta剪枝。

只能理解这么多了。。。看论文快看哭了。。。吾要学好英语，English...应该累死！！！

POJ 1085

题意：AB轮流在包含9个小三角形的大三角形中放边，当某人放上一条边后构成一个小三角形，则这个人得一分，谁得的分多谁就赢了。

maxmin搜索 + alpha-beta剪枝，过程是对这个大三角形就行压缩，共17条边。然后搜索。这个题里，alpha为1，表示A可以赢，出现搜索值返回的是1的时候其他的就不用再搜了。beta值为-1，表示B可以赢，同理进行剪枝。

参考：[http://blog.csdn.net/dooder\_daodao/article/details/6682971][http_blog.csdn.net_dooder_daodao_article_details_6682971]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#pragma comment(linker,"/STACK:327680000,327680000")
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <set>
    #include <functional>
    #include <numeric>
    #include <sstream>
    #include <stack>
    #include <map>
    #include <queue>
    
    #define CL(arr, val)    memset(arr, val, sizeof(arr))
    #define REP(i, n)       for((i) = 0; (i) < (n); ++(i))
    #define FOR(i, l, h)    for((i) = (l); (i) <= (h); ++(i))
    #define FORD(i, h, l)   for((i) = (h); (i) >= (l); --(i))
    #define L(x)    (x) << 1
    #define R(x)    (x) << 1 | 1
    #define MID(l, r)   (l + r) >> 1
    #define Min(x, y)   (x) < (y) ? (x) : (y)
    #define Max(x, y)   (x) < (y) ? (y) : (x)
    #define E(x)        (1 << (x))
    #define iabs(x)     (x) < 0 ? -(x) : (x)
    #define OUT(x)  printf("%I64d\n", x)
    #define Read()  freopen("data.in", "r", stdin)
    #define Write() freopen("data.out", "w", stdout);
    
    typedef long long LL;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    const int inf = ~0u>>2;
    
    using namespace std;
    //棋盘上17个点，两个点构成一条边，给边编号，mat[a][b]表示a->b这条边对应的编号。
    int mat[11][11]={
        {
          0,0,0,0,0,0,0,0,0,0,0},
        {
          0,0,0,1,0,0,0,0,0,0,0},
        {
          0,0,0,2,3,4,0,0,0,0,0},
        {
          0,1,2,0,0,5,6,0,0,0,0},
        {
          0,0,3,0,0,7,0,9,10,0,0},
        {
          0,0,4,5,7,0,8,0,11,12,0},
        {
          0,0,0,6,0,8,0,0,0,13,14},
        {
          0,0,0,0,9,0,0,0,15,0,0},
        {
          0,0,0,0,10,11,0,15,0,16,0},
        {
          0,0,0,0,0,12,13,0,16,0,17},
        {
          0,0,0,0,0,0,14,0,0,17,0}
    };
    
    //把三条边能够构成的三角形状态压缩
    int tri[9]={
         7,152,52,352,34304,3200,71680,12544,155648};
    int FULL = (1<<18) - 1;
    
    int Max_search(int state, int alpha, int ca, int cb);
    int Min_search(int state, int beta, int ca, int cb);
    
    int new_status(int old, int seg, int& cnt) {
        int _new = old|seg;
        for(int i = 0; i < 9; ++i) {
            if((old&tri[i]) != tri[i] && (_new&tri[i]) == tri[i]) {
                cnt++;
            }
        }
        return _new;
    }
    
    int Max_search(int state, int alpha, int ca, int cb) {
        if(ca >= 5) return 1;
        if(cb >= 5) return -1;
    
        if(state == FULL)   return ca > cb ? 1 : -1;
    
        int _new, seg, tmp, ta, ans = -1;
        int bit = (~state)&FULL;
    
        while(bit) {
            seg = bit&(-bit);
            ta = ca;
            _new = new_status(state, seg, ta);
            if(ta > ca) tmp = Max_search(_new, alpha, ta, cb);
            else    tmp = Min_search(_new, ans, ta, cb);
    
            if(tmp > ans)   ans = tmp;
            if(tmp >= alpha)    return ans;    //A存在能够胜利的状态，直接return
            bit -= seg;
        }
        return ans;
    }
    
    int Min_search(int state, int beta, int ca, int cb) {
        if(ca >= 5) return 1;
        if(cb >= 5) return -1;
    
        if(state == FULL)   return ca > cb ? 1 : -1;
    
        int _new, seg, tmp, tb, ans = 1;
        int bit = (~state)&FULL;
    
        while(bit) {
            seg = bit&(-bit);
            tb = cb;
            _new = new_status(state, seg, tb);
            if(tb > cb) tmp = Min_search(_new, beta, ca, tb);
            else    tmp = Max_search(_new, ans, ca, tb);
    
            if(tmp < ans)   ans = tmp;
            if(tmp <= beta) return ans;    //B存在能够胜利的状态
            bit -= seg;
        }
        return ans;
    }
    
    int main() {
        //Read();
    
        int T, n, a, b, ans, cas = 0;
        int cnt, status, ca, cb, ta, tb;
        cin >> T;
        while(T--) {
            cin >> n;
            cnt = status = 0;
            ca = cb = 0;
    
            while(n--) {
                cin >> a >> b;
                ta = ca; tb = cb;
                status = new_status(status, 1<<mat[a][b], (cnt&1)?cb:ca);
                if(ta == ca && tb == cb)    cnt++;
            }
    
            if(cnt&1)   ans = Min_search(status, -1, ca, cb);    //轮到B走
            else    ans = Max_search(status, 1, ca, cb);    //轮到A走
            printf("Game %d: %s\n", ++cas, ans == 1 ? "A wins." : "B wins.");
        }
        return 0;
    }

[http_www.xqbase.com_computer_search_minimax.htm]: http://www.xqbase.com/computer/search_minimax.htm
[http_www.xqbase.com_computer_search_alphabeta.htm]: http://www.xqbase.com/computer/search_alphabeta.htm
[http_en.wikipedia.org_wiki_Minimax]: http://en.wikipedia.org/wiki/Minimax
[http_en.wikipedia.org_wiki_Alpha_E2_80_93beta_pruning]: http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
[http_ai-depot.com_articles_minimax-explained_1]: http://ai-depot.com/articles/minimax-explained/1/
[http_www.starming.com_index.php_action_plugin_v_wave_tpl_union_ac_viewgrouppost_gid_34694_tid_15725]: http://www.starming.com/index.php?action=plugin&v=wave&tpl=union&ac=viewgrouppost&gid=34694&tid=15725
[http_blog.pfan.cn_rickone_16930.html]: http://blog.pfan.cn/rickone/16930.html
[http_blog.csdn.net_dooder_daodao_article_details_6682971]: http://blog.csdn.net/dooder_daodao/article/details/6682971
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220401/41c5d1d235dc4f62b465acf45eee7392.png