3 条题解

  • 5
    @ 2018-03-25 20:34:37

    参考了一下《训练指南》,发现我比赛的时候写的是弱化版的Alpha-Beta剪枝……以下为正版
    我们显然可以贪心地按照当前一步的获利,优先搜索更利于当前游戏者的后继节点。这样进行节点排序之后,Alpha-Beta剪枝的效率可以大大提高。

    另外,本题卡常数……标程跑了1700+ms,时间限制只开2s……我用了 std::pair 然后直接卡超时了,手写 pair 才过……

    附代码(C++11):

    #include <bits/stdc++.h>
    using namespace std;
    
    template<typename T1, typename T2>
    struct P {
        T1 fst; T2 snd;
        P() {}
        P(T1 a, T2 b) {
            fst = a, snd = b;
        }
        bool operator<(const P<T1, T2> &rhs) const {
            return fst == rhs.fst ? snd < rhs.snd : fst < rhs.fst;
        }
        bool operator>(const P<T1, T2> &rhs) const {
            return fst == rhs.fst ? snd > rhs.snd : fst > rhs.fst;
        }
    };
    
    template<typename T1, typename T2>
    P<T1, T2> MP(T1 fst, T2 snd) {
        return P<T1, T2>(fst, snd);
    }
    
    typedef P<int, P<int, int> > info;
    
    struct State {
        int step, score, Board[4][4];
        inline void rotate_rev(int i, int j) {
            swap(Board[i][j+1], Board[i+1][j+1]);
            swap(Board[i+1][j], Board[i+1][j+1]);
            swap(Board[i+1][j], Board[i][j]);
        }
        inline void rotate_clk(int i, int j) {
            swap(Board[i+1][j], Board[i][j]);
            swap(Board[i+1][j], Board[i+1][j+1]);
            swap(Board[i][j+1], Board[i+1][j+1]);
        }
    };
    
    const int INF = 0x3f3f3f3f;
    
    constexpr int H(State &x, int i, int j) {
        return x.Board[i][j] + x.Board[i][j+1]
             + x.Board[i+1][j] + x.Board[i+1][j+1];
    }
    
    int AlphaBeta(State &S, int player, int alpha, int beta) {
        if(S.step == 0) return S.score;
        
        int sz = 0; info vec[9];
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                vec[sz++] = MP(H(S, i, j), MP(i, j));
        if(!player)
            sort(vec, vec+9, greater<info>());
        else
            sort(vec, vec+9, less<info>());
        
        for(info &p : vec) {
            S.rotate_rev(p.snd.fst, p.snd.snd);
            S.step--; S.score += H(S, p.snd.fst, p.snd.snd);
            
            int v = AlphaBeta(S, player^1, alpha, beta);
            if(!player) alpha = max(alpha, v);
            else beta = min(beta, v);
            
            S.rotate_clk(p.snd.fst, p.snd.snd);
            S.step++; S.score -= H(S, p.snd.fst, p.snd.snd);
            if(alpha >= beta) break;
        }
        return !player ? alpha : beta;
    }
    
    int T, k; State S;
    
    int main() {
        scanf("%d", &T);
        while(T--) {
            scanf("%d", &k); S.step = 2*k; S.score = 0;
            for(int i = 0; i < 4; i++)
                for(int j = 0; j < 4; j++)
                    scanf("%d", &S.Board[i][j]);
            printf("%d\n", AlphaBeta(S, 0, -INF, INF));
        }
        return 0;
    }
    
  • 4
    @ 2018-03-24 23:20:59

    对于这种最大最小化的双人游戏,最基本的思路是分支定界的搜索,也就是alpha-beta剪枝,这就可以得到60分。

    满分做法还需要用到启发式搜索,这里的启发式函数很容易找到:优先选取下一步获利最大(最小)的方案。

    下面的代码供参考。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int MAXK=12;
    const int MAXV=10;
    const int MAXN=4;
    
    const int INF=MAXK*MAXV*4;
    
    int n,k,sum;
    int a[MAXN][MAXN];
    
    void RotL(int i,int j){
        int tmp=a[i][j];
        a[i][j]=a[i][j+1];
        a[i][j+1]=a[i+1][j+1];
        a[i+1][j+1]=a[i+1][j];
        a[i+1][j]=tmp;
        sum+=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
    }
    
    void RotR(int i,int j){
        int tmp=a[i][j];
        a[i][j]=a[i+1][j];
        a[i+1][j]=a[i+1][j+1];
        a[i+1][j+1]=a[i][j+1];
        a[i][j+1]=tmp;
        sum-=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
    }
    
    int pro_max(int height,int downbound,int upbound);
    int pro_min(int height,int downbound,int upbound);
    
    int pro_max(int height,int downbound,int upbound){
        if(height==k)
            return sum;
        pair<int,int> heuristic_order[9];
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++){
                int sum2times2=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
                heuristic_order[i*3+j]=make_pair(sum2times2,i*3+j);
            }
        sort(heuristic_order,heuristic_order+9);
        for(int t=8;t>=0;t--){
            int i=heuristic_order[t].second/3;
            int j=heuristic_order[t].second%3;
            RotL(i,j);
            int val=pro_min(height+1,downbound,upbound);
            RotR(i,j);
            if(val>=upbound)
                return upbound;
            if(val>downbound)
                downbound=val;
        }
        return downbound;
    }
    
    int pro_min(int height,int downbound,int upbound){
        if(height==k)
            return sum;
        pair<int,int> heuristic_order[9];
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++){
                int sum2times2=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
                heuristic_order[i*3+j]=make_pair(sum2times2,i*3+j);
            }
        sort(heuristic_order,heuristic_order+9);
        for(int t=0;t<=8;t++){
            int i=heuristic_order[t].second/3;
            int j=heuristic_order[t].second%3;
            RotL(i,j);
            int val=pro_max(height+1,downbound,upbound);
            RotR(i,j);
            if(val<=downbound)
                return downbound;
            if(val<upbound)
                upbound=val;
        }
        return upbound;
    }
    
    int main(){
        int test;
        cin>>test;
        for(int cas=1;cas<=test;cas++){
            cin>>k;
            k*=2;
            n=4;
            for(int x=0;x<n;x++)
                for(int y=0;y<n;y++)
                    cin>>a[x][y];
            sum=0;
            int ans=pro_max(0,0,INF);
            cout<<ans<<"\n";
        }
    } 
    
  • 3
    @ 2018-03-25 22:12:05

    NegaMax+AlphaBeta剪枝+启发式:优先选取最大(最小)的方案
    总用时约14s

    #include<bits/stdc++.h>
    using namespace std;
    
    const int INF=100000000;
    
    int k,T,sum;
    int a[5][5];
    
    struct node
    {
        int i,j,val;
        bool operator < (node& x)
        {
            return val<x.val;
        }
    };
    
    void Rot_anticlock(int i,int j)
    {
        int t=a[i][j];
        a[i][j]=a[i][j+1];
        a[i][j+1]=a[i+1][j+1];
        a[i+1][j+1]=a[i+1][j];
        a[i+1][j]=t;
    }
    
    void Rot_clock(int i,int j)
    {
        int t=a[i][j];
        a[i][j]=a[i+1][j];
        a[i+1][j]=a[i+1][j+1];
        a[i+1][j+1]=a[i][j+1];
        a[i][j+1]=t;
    }
    
    void input()
    {
        cin >>k;
        for(int i=1; i<=4; i++)
        {
            for(int j=1; j<=4; j++)
            {
                cin >>a[i][j];
            }
        }
    }
    
    int NegaMax(int dep,int alpha,int beta)
    {
        if(dep==(k<<1)) return sum;
    
        int t,ins=0;
        node arr[10];
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                ins++;
                t=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];
                arr[ins].i=i;
                arr[ins].j=j;
                arr[ins].val=t;
            }
        }
        sort(arr+1,arr+10);
    
        if(dep&1) ins=1;
        else ins=9;
        for(int i=1;i<=9;i++)
        {
            Rot_anticlock(arr[ins].i,arr[ins].j);
            sum+=arr[ins].val;
            t=-NegaMax(dep+1,-beta,-alpha);
            Rot_clock(arr[ins].i,arr[ins].j);
            sum-=arr[ins].val;
            if(t>=beta)
            {
                return beta;
            }
            alpha=max(alpha,t);
    
            if(dep&1) ins++;
            else ins--;
        }
        return alpha;
    }
    
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin >>T;
        while(T--)
        {
            input();
    
            sum=0;
            cout <<NegaMax(0,-INF,INF)<<endl;
        }
    
        return 0;
    }
    
    
  • 1

信息

ID
2034
难度
7
分类
(无)
标签
(无)
递交数
105
已通过
19
通过率
18%
被复制
3
上传者