C++实现简单五子棋AI

使用方法:
输入二维坐标0~14落子,输入-1 -1可以悔棋
注:输入7 7 即会开始在坐标7 7落子

#include<bits/stdc++.h>
using namespace std;
#define bas 15
#define Dep_limit 3
#define inf 0x3f3f3f
int score[2][6]={{0,5,25,4000,inf,inf},{0,0,2,50,4000,inf}};///0活,1死
int mo[8][2]={{0,1},{0,-1},{1,-1},{1,0},{1,1},{-1,-1},{-1,0},{-1,1}};
int dir[4][2]={{1,0},{1,1},{0,1},{1,-1}};
struct opmem///操作记录
{
    int x,y;
    int kind;//黑1,白-1,空0
};
stack<opmem>s;
bool vis[bas][bas];
struct Mat///描述局面
{
    short a[bas][bas];
    void out()
    {
        printf(" ");
        for(int i=0;i<bas;i++)printf("%2d",i);
        printf("\n");
        for(int i=0;i<bas;i++)
        {
            printf("%2d ",i);
            for(int j=0;j<bas;j++)
            {
                if(a[i][j]==0)printf(". ");
                else if(a[i][j]==1)printf("* ");
                else printf("O ");
            }
            printf("\n");
        }
    }
    void add(int x,int y,int col,int add)
    {
        if(add==-1)a[x][y]=0;
        else a[x][y]=col;
    }
    bool in(int x,int y)
    {
        return x>=0&&y>=0&&x<bas&&y<bas;
    }
    bool win5(int x,int y)///返回该棋子是否可以组成五子
    {
        for(int i=0;i<4;i++)
        {
            int l=0,r=-1;
            int mx=dir[i][0],my=dir[i][1];
            int lx=x,ly=y,rx=x,ry=y,col=a[x][y];
            while(in(lx,ly)&&a[lx][ly]==col)
            {
                l++;
                lx-=mx;ly-=my;
            }
            while(in(rx,ry)&&a[rx][ry]==col)
            {
                r++;
                rx+=mx;ry+=my;
            }
            if(l+r>=5)return 1;
        }
        return 0;
    }
    int val(int aim)///接下来aim下,计算局面好坏
    {
        int ret=0;
        int num[6][2]={0};
        for(int xcx=0;xcx<4;xcx++)
        {
            memset(vis,0,sizeof(vis));
            int col=0;
            int mx=dir[xcx][0],my=dir[xcx][1];
            for(int i=0;i<bas;i++) for(int j=0;j<bas;j++)
            {
                if(vis[i][j]||a[i][j]==0)continue;
                col=a[i][j];
                int p=0,limit=0,x=i,y=j;
                if(!in(x-mx,y-my)||a[x-mx][y-my]!=0)limit++;
                while( in(x,y) && a[x][y]==col )
                {
                    vis[x][y]=1;
                    p++;
                    x+=mx;
                    y+=my;
                }
                if(!in(x,y)||a[x][y]!=0)limit++;
                if(p>=5)
                    if(col==aim)return inf;
                    else return -inf;
                if(limit==2)continue;
                if(p>=4&&col==aim)return inf;
                num[p][limit]+=col;
            }
        }
        for(int j=0;j<2;j++) for(int i=2;i<6;i++)
        {
            ret+=num[i][j]*score[j][i];
        }
        return aim*ret;
    }
    bool colse(int x,int y)
    {
        for(int i=0;i<8;i++)
        {
            int tx=x+mo[i][0],ty=y+mo[i][1];
            if(in(tx,ty)&&a[tx][ty]!=0)return 1;
        }
        return 0;
    }
}now;
void outlin()
{
    for(int i=0;i<30;i++)printf("-");printf("\n");
}
int dfs(int x,int y,int frd,int col,int deep)//下(x,y)点成col色,能得到的最大评分,兄弟节点最大值为frd。
{
    if(deep==Dep_limit)
    {
        return -now.val(-col);
    }
    int ret=-inf;
    for(int i=0;i<bas;i++) for(int j=0;j<bas;j++)
    {
        if( now.a[i][j]!=0 || !now.colse(i,j) )continue;
        now.add(i,j,-col,1);
        if(now.win5(i,j))
        {
            now.add(i,j,-col,-1);
            return -inf;
        }
        ret = max( dfs(i,j,-inf,-col,deep+1), ret);
        now.add(i,j,-col,-1);
        if(ret>=inf)break;
        if(ret<frd){return inf;}///abcd剪枝
        frd=ret;
    }
    return -ret;
}

void work(int &x,int &y,int col)//传入下棋位置,颜色(黑1,白-1),传出决策位置
{
    int best=-inf*2;
    for(int i=0;i<bas;i++) for(int j=0;j<bas;j++)
    {
        if(now.a[i][j]==0){x=i;y=j;break;}
    }
    for(int i=0;i<bas;i++)
    {
        for(int j=0;j<bas;j++)
        {
            if( now.a[i][j]!=0 || !now.colse(i,j) )continue;
            now.add(i,j,-col,1);
            if(now.win5(i,j))
            {
                now.add(i,j,-col,-1);
                x=i,y=j;
                return;
            }
            if(now.val(col)!=inf)
            {
                int temp= dfs(i,j,-inf,-col,1);
                if(temp>best)
                {
                    best=temp;
                    x=i,y=j;
                }
            }
            now.add(i,j,-col,-1);
        }
    }
}
void outway()//输出棋局
{
    int x[200],y[200],cnt=0;
    while(!s.empty())
    {
        x[cnt]=s.top().x;
        y[cnt]=s.top().y;
        cnt++;
        s.pop();
        if(!s.empty())s.pop();
    }
    for(int i=cnt-1;i>=0;i--)
    {
        printf("%d %d\n",x[i],y[i]);
    }
}
int main()
{
    //test();
    int x,y;
    memset(now.a,0,sizeof(now.a));
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        opmem temp;
        if(x==-2&&y==-2)break;
        if(x==-1&&y==-1)
        {
            printf("back:\n");
            //scanf("%d%d",&x,&y);
            now.add(s.top().x,s.top().y,s.top().kind,-1);
            s.pop();
            now.add(s.top().x,s.top().y,s.top().kind,-1);
            s.pop();
            now.out();
            continue;
        }
        if(!now.in(x,y)||now.a[x][y]!=0)
        {
            printf("error %d %d\n",x,y);continue;
        }
        now.add(x,y,1,1);
        now.out();outlin();
        temp.kind=1;    temp.x=x;   temp.y=y;
        s.push(temp);
        if(now.win5(x,y)){printf("you win\n");break;}

        work(x,y,1);
        now.add(x,y,-1,1);
        now.out();outlin();
        temp.kind=-1;    temp.x=x;   temp.y=y;
        s.push(temp);
        printf("%d %d\n",x,y);
        if(now.win5(x,y)){printf("ai win\n");}
    }
    outway();
    return 0;
}
全部评论

相关推荐

04-11 00:51
已编辑
门头沟学院 Java
先说一下楼主的情况:双非本大三,两段实习,javaer,想要找一个暑期大厂offer,努力了两个月,三月份每天的状态就是算法,八股,项目,四月份更是一个面试没有,最终还是没有结果,心碎了一地。期间面了一些中小厂,大厂只有腾讯约面,其他大厂都投了一遍,但是还是石沉大海。再看一下楼主的面试结果吧,就不说ttl了腾讯s3:三面挂csig:一面挂teg:三面挂wxg:一面挂没错,面了八次腾讯,两次三面挂,当时真的心都碎了。其他中小厂都有面,有的没过,有的oc,但是都没有去。其他大厂投了简历,但是不是简历挂,就是测评挂,都说今年行情好很多,各大厂都扩招,可是问题出在那里呢?学历背景吗?实习经历吗?还是简历不够好看?依稀记得,从年初七就离开了家里,回到学校,早早准备面试,当时自己认为凭借着自己的两段实习经历,以及大二就开始准备的八股算法,拿大厂offer不是问题,但是还是不敢放松,回校的状态每天就是算法,八股,还有查看各种招聘信息,想着尽早投机会多,但是事实证明,投的早,不如投的刚刚好。当时想着,先投一些中小厂开始面试,找找面试感觉,从2.10就开始有面试了,基本都是线下面试,面试的感觉都很不错,觉得自己的状态慢慢回来了,期间也有oc一些中小厂,但是自己的目标并不在此,只是想练一下手,遂拒。后面投了腾讯的暑期实习基地,不久就约面了,第一次面这么大的厂,多少有点紧张,好在运气还不错,遇到的面试官也比较好,一直干到了三面,期间看牛客有不少说一面就挂了的,感觉自己还是比较幸运的,但是没想到倒在了三面,一周后就挂了,伤心是有的,但是想到这才刚刚开始,还有很多机会,便继续准备下一次面试了,很快,被另外一个部门捞了,一进会议,面试官没开摄像头,看网上说没开摄像头很多都是kpi,但是自己给自己打气,认为面试官只是不方便开摄像头罢了,面完,感觉良好,没问什么很难得问题,基本都答出来了,算法两道也a了一道,感觉实习不会这么严格吧?还是过了一会挂了,因为这个?还是技术不太匹配?面试过程中说搞C++的,心想,搞c++的你面我干啥?唉,这时候有点气馁,然后就接下来半个月没有面试。这时已经是三月底了,看到牛客好多人都已经陆陆续续拿到了offer,看人家的面试准备也没那么早,有0实习的,有没刷算法的,有两个面的,,,唉,反正是一言难尽啊,感觉努力没有什么意义,面试多半是看面试官的感觉,主观性很大啊,只要你技术没有太大的问题。第三次面试腾讯,面试来的比较突然,期间已经有几天没看八股什么的了,临时看了一下之前自己做的面试笔记,但是面试却异常顺利,三天闯到了三面,自己也不敢相信,三面玩感觉也良好,脑子里不得不想着一些“offer结算画面”,但是过了一会查看流程显示“流程终止”,我?哎,当时真的有苦说不出啊,也是一晚没睡。后面就逐渐开始褪去大厂梦了,看着曾经跟自己交流的牛油,朋友,认识的人,觉得他们技术不太如你,算法刷的没你多,进了大厂,但是这又如何呢?能力强不强不是你了说了,面试官说了算。也逐渐知道,不是你能力好就可以了,还得有运气,运气,运气。这个过程太累了,和自己和解吧,不用非得大厂,找个合适一点的就好,放轻松一点。今天有点心事睡不着,闲着想写一些自己的面试过程,勿喷。附上一张面试的情况,公司就不方便透露了。
怒卷的斯科特:八分运气两分实力
点赞 评论 收藏
分享
04-10 08:14
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务