用c++实现alphabeta剪枝算法的五子棋

以下是使用C++实现alpha-beta剪枝算法的五子棋代码示例：

#include<bits/stdc++.h>
using namespace std;

const int N=20;
const int INF=0x3f3f3f3f;

char mp[N][N];  //棋盘
int score[N][N];  //每个位置的分值
int n,m;  //棋盘大小
int Max_depth=3;  //最大深度
int win=5;  //五子棋

int dx[4]={1,1,0,-1};  //方向数组
int dy[4]={0,1,1,1};

bool check(int x,int y,char c)  //判断是否有五子连珠
{
    for(int i=0;i<4;i++)
    {
        int cnt=1;
        int nx=x+dx[i],ny=y+dy[i];
        while(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==c)
        {
            cnt++;
            nx+=dx[i];
            ny+=dy[i];
        }
        nx=x-dx[i],ny=y-dy[i];
        while(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==c)
        {
            cnt++;
            nx-=dx[i];
            ny-=dy[i];
        }
        if(cnt>=win) return true;
    }
    return false;
}

int calc(int x,int y)  //计算每个位置的分值
{
    int ans=0;
    for(int i=0;i<4;i++)
    {
        int cnt=1;
        int nx=x+dx[i],ny=y+dy[i];
        while(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==mp[x][y])
        {
            cnt++;
            nx+=dx[i];
            ny+=dy[i];
        }
        nx=x-dx[i],ny=y-dy[i];
        while(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==mp[x][y])
        {
            cnt++;
            nx-=dx[i];
            ny-=dy[i];
        }
        if(cnt>=win-1) ans+=score[cnt];  //根据连珠数加分
    }
    return ans;
}

int dfs(int depth,int alpha,int beta,char c)  //alpha-beta剪枝算法
{
    if(depth==Max_depth) return 0;
    int ans=-INF;
    vector<pair<int,int>> v;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mp[i][j]!='.') continue;
            if(!check(i,j,'O')&&!check(i,j,'X')) continue;  //只考虑周围有棋子的位置
            int val=calc(i,j);
            v.push_back(make_pair(val,i*n+j));  //将位置按分值排序
        }
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    for(int i=0;i<v.size();i++)
    {
        int x=v[i].second/n,y=v[i].second%n;
        mp[x][y]=c;
        if(check(x,y,c)) ans=INF;
        else if(c=='O') ans=max(ans,dfs(depth+1,alpha,beta,'X')-v[i].first);
        else ans=min(ans,dfs(depth+1,alpha,beta,'O')+v[i].first);
        mp[x][y]='.';
        if(c=='O')
        {
            if(ans>=beta) return ans;
            alpha=max(alpha,ans);
        }
        else
        {
            if(ans<=alpha) return ans;
            beta=min(beta,ans);
        }
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j]='.';
    for(int i=2;i<=win;i++)
        score[i]=score[i-1]+i*i;
    int x,y;
    while(m--)
    {
        cin>>x>>y;
        mp[x][y]='O';
        int ans=dfs(0,-INF,INF,'X');
        cout<<ans<<"\n";
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(mp[i][j]=='X')
                {
                    cout<<i<<" "<<j<<"\n";
                    mp[i][j]='.';
                    break;
                }
            }
        }
    }
    return 0;
}

在这个示例中，我们使用alpha-beta剪枝算法来搜索最优解。我们首先计算每个位置的分值，然后将所有可下棋的位置按照分值排序，从高到低依次尝试。在搜索时，我们用check函数来判断是否有五子连珠，如果有，我们返回一个极大值或极小值。在搜索时，我们使用alpha-beta剪枝算法来避免不必要的搜索。