0
0

如何编写一个五子棋AI（附AI源码）

注:此文章的代码推荐在

           小熊猫 
          
         
           c 
          
         
           + 
          
         
           + 
          
         
        
       
      
     
    
   
     \boxed{小熊猫c++} 
    
   
 小熊猫c++​上运行（使用了EGE图形库）

AI的原理

1.三子棋AI的编写

三子棋的总局面数约为 

     549 
    
   
     , 
    
   
     946 
    
   
  
    549,946 
   
  
549,946，因此我们先以它为基础开始编写。

Test1:构建决策树

在这里插入图片描述

注意:节点上方的 

     [ 
    
   
     a 
    
   
     / 
    
   
     b 
    
   
     ] 
    
   
  
    [a/b] 
   
  
[a/b]表示某个决策下一步还有 
 
  
   
   
     b 
    
   
  
    b 
   
  
b种可能，还剩下 
 
  
   
   
     a 
    
   
  
    a 
   
  
a种未显示

这里，我们先来讨论某个局面下一步的决策。
在这里插入图片描述
源码见文末 

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
     1 
    
   
  
    Test 1 
   
  
Test1 源码

关注左上红下 

     ( 
    
   
     1 
    
   
     , 
    
   
     3 
    
   
     ) 
    
   
  
    (1,3) 
   
  
(1,3)的节点，可以发现下一步蓝色可以获胜，那么红方必然不能下 
 
  
   
   
     ( 
    
   
     1 
    
   
     , 
    
   
     3 
    
   
     ) 
    
   
  
    (1,3) 
   
  
(1,3)。

同理，红下 

     ( 
    
   
     3 
    
   
     , 
    
   
     2 
    
   
     ) 
    
   
     & 
    
   
     ( 
    
   
     1 
    
   
     , 
    
   
     2 
    
   
     ) 
    
   
  
    (3,2)\&(1,2) 
   
  
(3,2)&(1,2)同样不行，只能下 
 
  
   
   
     ( 
    
   
     3 
    
   
     , 
    
   
     1 
    
   
     ) 
    
   
  
    (3,1) 
   
  
(3,1)。

继续看蓝方，可以发现蓝方也只能下 

     ( 
    
   
     1 
    
   
     , 
    
   
     3 
    
   
     ) 
    
   
  
    (1,3) 
   
  
(1,3)

于是，我们就得到了三子棋的AI的博弈树，现在来分析具体方法。

Test2:Min-Max算法

在这里插入图片描述
我们将平局定为 

     5 
    
   
  
    5 
   
  
5分，红胜为 
 
  
   
   
     10 
    
   
  
    10 
   
  
10，红负为 
 
  
   
   
     0 
    
   
  
    0 
   
  
0分，这样，我们就可以得到每个局面对红方的好处。

设前一步的节点为 

     u 
    
   
  
    u 
   
  
u,下一步的节点为 
 
  
   
   
     v 
    
   
  
    v 
   
  
v

对于每一个蓝点（到蓝色下棋），下一步是红方控制的，当然会选择对自己优的，所以取 

      V 
     
    
      u 
     
    
   
     = 
    
   
     max 
    
   
     ⁡ 
    
   
     { 
    
    
    
      V 
     
    
      v 
     
    
   
     } 
    
   
  
    V_u=\max\{V_v\} 
   
  
Vu​=max{Vv​}，比如下图中粉框节点，下一步红方可以取胜，那当然要选取胜了

在这里插入图片描述

对于每一个红点（到红色下棋），下一步是对方控制的，当然会选择对红方劣的，所以取 

      V 
     
    
      u 
     
    
   
     = 
    
   
     min 
    
   
     ⁡ 
    
   
     { 
    
    
    
      V 
     
    
      v 
     
    
   
     } 
    
   
  
    V_u=\min\{V_v\} 
   
  
Vu​=min{Vv​}，比如如果有一个节点，下一步蓝方可以取胜，那当然要选取胜（红败）了

这样，我们就得到了所有局面的胜率。
源码见文末 

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     2 
    
   
     − 
    
   
     1 
    
   
  
    Test\ 2-1 
   
  
Test 2−1 源码，AI下3子棋见  
 
  
   
   
     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     2 
    
   
     − 
    
   
     2 
    
   
  
    Test\ 2-2 
   
  
Test 2−2 源码

在这里插入图片描述
当然，经过对所有局面的考察，可以发现没有必胜的可能，但是还是有可能在前几步利用对手失误获得必胜（读者可以自行查看程序），如上图。

1.五子棋AI的编写

五子棋的总局面数约为 

     1 
    
    
    
      0 
     
    
      50 
     
    
   
  
    10^{50} 
   
  
1050，因此不可能构造完整的决策树。

Test3:对局面进行估分

待续
还是以三子棋为例，把 

     [ 
    
   
     X 
    
   
     ] 
    
   
     [ 
    
   
     X 
    
   
     ] 
    
   
     [ 
    
   
         
    
   
     ] 
    
   
  
    [X][X][\ \ \ ] 
   
  
[X][X][   ]记为 
 
  
   
   
     50 
    
   
  
    50 
   
  
50分， 
 
  
   
   
     [ 
    
   
         
    
   
     ] 
    
   
     [ 
    
   
     X 
    
   
     ] 
    
   
     [ 
    
   
         
    
   
     ] 
    
   
  
    [\ \ \ ][X][\ \ \ ] 
   
  
[   ][X][   ]和 
 
  
   
   
     [ 
    
   
         
    
   
     ] 
    
   
     [ 
    
   
         
    
   
     ] 
    
   
     [ 
    
   
     X 
    
   
     ] 
    
   
  
    [\ \ \ ][\ \ \ ][X] 
   
  
[   ][   ][X]记为 
 
  
   
   
     10 
    
   
  
    10 
   
  
10分， 
 
  
   
   
     [ 
    
   
     X 
    
   
     ] 
    
   
     [ 
    
   
     X 
    
   
     ] 
    
   
     [ 
    
   
     X 
    
   
     ] 
    
   
  
    [X][X][X] 
   
  
[X][X][X]记为 
 
  
   
   
     100 
    
   
  
    100 
   
  
100分，就可以在决策树层数较少的情况估算价值。

在这里插入图片描述
有了估值，AI就智慧多了，如果我们把比较有可能的点（这里是选前2个）单独挑出来，其余的点不进行展开，可以发现它已经把较优的点选好了（如上图），就会大大减少节点数。
以下是一次对局：（AI:蓝）
在这里插入图片描述
评价：目光较短浅，但是速度非常快(约0.3s)
源码见 

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     3 
    
   
  
    Test \ 3 
   
  
Test 3

Test4:α-β剪枝

AI不行，就加深度，时间太长，就加剪枝

在这里插入图片描述
发现 

      V 
     
    
      u 
     
    
   
     = 
    
   
     m 
    
   
     a 
    
   
     x 
    
   
     { 
    
   
     m 
    
   
     i 
    
   
     n 
    
   
     { 
    
   
     a 
    
   
     , 
    
   
     b 
    
   
     } 
    
   
     , 
    
   
     c 
    
   
     } 
    
   
  
    V_u=max\{min\{a,b\},c\} 
   
  
Vu​=max{min{a,b},c}时，如果 
 
  
   
   
     a 
    
   
     & 
    
   
     b 
    
   
  
    a\&b 
   
  
a&b有一个 
 
  
   
   
     < 
    
   
     c 
    
   
  
    <c 
   
  
<c，那就不用算了， 
 
  
   
    
    
      V 
     
    
      u 
     
    
   
  
    V_u 
   
  
Vu​就是 
 
  
   
   
     c 
    
   
  
    c 
   
  
c，

同理 

      V 
     
    
      u 
     
    
   
     = 
    
   
     m 
    
   
     i 
    
   
     n 
    
   
     { 
    
   
     m 
    
   
     a 
    
   
     x 
    
   
     { 
    
   
     a 
    
   
     , 
    
   
     b 
    
   
     } 
    
   
     , 
    
   
     c 
    
   
     } 
    
   
  
    V_u=min\{max\{a,b\},c\} 
   
  
Vu​=min{max{a,b},c}，如果 
 
  
   
   
     a 
    
   
     & 
    
   
     b 
    
   
  
    a\&b 
   
  
a&b有一个 
 
  
   
   
     > 
    
   
     c 
    
   
  
    >c 
   
  
>c， 
 
  
   
    
    
      V 
     
    
      u 
     
    
   
  
    V_u 
   
  
Vu​就是 
 
  
   
   
     c 
    
   
  
    c 
   
  
c

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
即： 

     m 
    
   
     i 
    
   
     n 
    
   
     ( 
    
   
     7 
    
   
     , 
    
   
     m 
    
   
     a 
    
   
     x 
    
   
     ( 
    
   
     10 
    
   
     , 
    
   
     ? 
    
   
     ) 
    
   
     ) 
    
   
     = 
    
   
     7 
    
   
  
    min(7,max(10,?))=7 
   
  
min(7,max(10,?))=7

在这里插入图片描述
(实测大约剪掉了 

      3 
     
    
      / 
     
    
      4 
     
    
   
     3/4 
    
   
 3/4的节点，效率不太高，所以笔者并没有用)

本文中所有源代码

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     1 
    
   
  
    Test \ 1 
   
  
Test 1

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int check(BOARD now)
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(now.a[i][j])
            for(int fx=-1;fx<=1;fx++)
                for(int fy=-1;fy<=1;fy++)
                    if(fx!=0||fy!=0)
                {
                    int bo=now.a[i][j];
                    for(int f=1;f<=2;f++)
                        if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
                    if(bo)return bo;
                }
    return 0;
}
int getstep(BOARD now)
{
    int step=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)step+=now.a[i][j];
    if(step==0)step=1;else step=-1;
    return step;
}
void dfs(BOARD now)
{
    tree[now.number]=now;
    if(now.win)
    {
        return;
    }
    int step=getstep(now);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        if(!now.a[i][j])
        {
            NODE++;BOARD next=now;next.number=NODE;
            son[now.number].push_back(NODE);
            next.a[i][j]=step;
            next.win=check(next);
            dfs(next);
        }
}
BOARD empty_board()
{
    BOARD empty;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
    return empty;
}
void print_board(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+100,y+100);
    x+=10;y+=10;
    setcolor(BLACK);
    int t=80/3;
    for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
    for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(z.a[i][j]==1)
            {
                setcolor(BLUE);setlinewidth(2);
                circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
            }
            else if(z.a[i][j]==-1)
            {
                setcolor(RED);
                setlinewidth(3);
                line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
                line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
                setlinewidth(1);
            }
}
void change_board(int x,int y,BOARD &z)
{
    x+=10;y+=10;
    int t=80/3;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
            {
                if(Dr)z.a[i][j]=getstep(z);
            }
}
void print_line()
{
    setcolor(BLACK);
    for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
    if(Dr==0)LOCK=0;
    Dl=0;Rc=0;
    while(mousemsg())
    {
        mouse_msg m=getmouse();
        if(m.is_move())mx=m.x,my=m.y;
        if(m.is_down()&&m.is_mid())Dl=1;
        if(m.is_down()&&m.is_left())Dr=1;
        if(m.is_up()&&m.is_left())Dr=0;
        if(m.is_down()&&m.is_right())Rc=1;
    }    
}
int main()
{
    initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
    BOARD empty=empty_board();
    while(1)
    {
        dfs(empty);
        setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
        cout<<"TOTAL:"<<NODE<<endl;
        int t=0;
        node[1].y=250;node[1].x=5;show[1]=1;Rc=0;tree[1]=empty;
        while(Rc==0)
        {
            cleardevice();
            print_line();
            for(int i=1;i<=NODE;i++)
                if(show[i])
                {
                    print_board(node[i].x,node[i].y,tree[i]);
                    outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"/"+to_string(node[i].SON+son[i].size())+"]").c_str());
                    if(tree[i].win==-1)outtextxy(node[i].x,node[i].y-20,"WIN:RED");
                    if(tree[i].win==1)outtextxy(node[i].x,node[i].y-20,"WIN:BLUE");
                    if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
                        node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
                        son[i].pop_back();node[i].SON++;
                    }
                    if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        if(LOCK==i||LOCK==0)
                        {
                            node[i].x=mx-50;node[i].y=my-50;
                            LOCK=i;
                        }
                        
                    }
                }
            mousedata();
            delay_ms(100);
        }
        setcaption("编辑模式（点击右键开始计算，左键编辑棋盘）");
        Rc=0;
        cleardevice();
        while(Rc==0)
        {
            print_board(5,250,empty);
            change_board(5,250,empty);
            mousedata();
            if(Dl)empty=empty_board();
            delay_ms(100);
        }
        for(int i=1;i<=NODE;i++)
        {
            show[i]=0;tree[i].number=0;tree[i].win=0;
            son[i].clear();node[i].SON=0;
        }
        NODE=1;LN=0;
    }
}

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     2 
    
   
     − 
    
   
     1 
    
   
  
    Test \ 2-1 
   
  
Test 2−1

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win,score;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int check(BOARD now)
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(now.a[i][j])
                for(int fx=-1;fx<=1;fx++)
                    for(int fy=-1;fy<=1;fy++)
                        if(fx!=0||fy!=0)
                        {
                            int bo=now.a[i][j];
                            for(int f=1;f<=2;f++)
                                if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
                            if(bo)return bo;
                        }
    return 0;
}
int getstep(BOARD now)
{
    int step=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)step+=now.a[i][j];
    if(step==0)step=1;else step=-1;
    return step;
}
int dfs(BOARD now)
{
    tree[now.number]=now;
    if(now.win)
    {
        tree[now.number].score=now.win==-1?10:0;
        return now.win==-1?10:0;
    }
    int step=getstep(now),ping=1,Min=1e9,Max=-1e9;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(!now.a[i][j])
            {ping=0;
                NODE++;BOARD next=now;next.number=NODE;
                son[now.number].push_back(NODE);
                next.a[i][j]=step;
                next.win=check(next);
                if(step==1)Min=min(Min,dfs(next));
                else Max=max(Max,dfs(next));
                
            }
    if(ping==1)
    {
        tree[now.number].score=5;
        return 5;
    }
    tree[now.number].score=(step==1?Min:Max);
    return tree[now.number].score;
}
BOARD empty_board()
{
    BOARD empty;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
    return empty;
}
void print_board(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+100,y+100);
    x+=10;y+=10;
    setcolor(BLACK);
    int t=80/3;
    for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
    for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(z.a[i][j]==1)
            {
                setcolor(BLUE);setlinewidth(2);
                circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
            }
    else if(z.a[i][j]==-1)
    {
        setcolor(RED);
        setlinewidth(3);
        line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
        line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
        setlinewidth(1);
    }
}
void change_board(int x,int y,BOARD &z)
{
    x+=10;y+=10;
    int t=80/3;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
            {
                if(Dr)z.a[i][j]=getstep(z);
            }
}
void print_line()
{
    setcolor(BLACK);
    for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
    if(Dr==0)LOCK=0;
    Dl=0;Rc=0;
    while(mousemsg())
    {
        mouse_msg m=getmouse();
        if(m.is_move())mx=m.x,my=m.y;
        if(m.is_down()&&m.is_mid())Dl=1;
        if(m.is_down()&&m.is_left())Dr=1;
        if(m.is_up()&&m.is_left())Dr=0;
        if(m.is_down()&&m.is_right())Rc=1;
    }    
}
int main()
{
    initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
    BOARD empty=empty_board();
    while(1)
    {
        dfs(empty);
        setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
        cout<<"TOTAL:"<<NODE<<endl;
        int t=0;
        node[1].y=250;node[1].x=5;show[1]=1;Rc=0;
        while(Rc==0)
        {
            cleardevice();
            print_line();
            for(int i=1;i<=NODE;i++)
                if(show[i])
                {
                    print_board(node[i].x,node[i].y,tree[i]);
                    outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
                    if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
                        node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
                        son[i].pop_back();node[i].SON++;
                    }
                    if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        if(LOCK==i||LOCK==0)
                        {
                            node[i].x=mx-50;node[i].y=my-50;
                            LOCK=i;
                        }
                        
                    }
                }
            mousedata();
            delay_ms(100);
        }
        setcaption("编辑模式（点击右键开始计算，左键编辑棋盘）");
        Rc=0;
        cleardevice();
        while(Rc==0)
        {
            print_board(5,250,empty);
            change_board(5,250,empty);
            mousedata();
            if(Dl)empty=empty_board();
            delay_ms(100);
        }
        for(int i=1;i<=NODE;i++)
        {
            show[i]=0;tree[i].number=0;tree[i].win=0;
            son[i].clear();node[i].SON=0;
        }
        NODE=1;LN=0;
    }
}

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     2 
    
   
     − 
    
   
     2 
    
   
  
    Test \ 2-2 
   
  
Test 2−2

#include<iostream>
#include<vector>
#include<graphics.h>
using namespace std;
struct BOARD{int a[3][3];int number,win,score;};
struct SHOW{int x,y;int SON;}node[4020889];
int NODE=1;bool show[4028089];
BOARD tree[4028809];
vector<int>son[4002889];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1,PC=0;
int check(BOARD now)
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(now.a[i][j])
                for(int fx=-1;fx<=1;fx++)
                    for(int fy=-1;fy<=1;fy++)
                        if(fx!=0||fy!=0)
                        {
                            int bo=now.a[i][j];
                            for(int f=1;f<=2;f++)
                                if(i+fx*f>=3||j+fy*f>=3||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
                            if(bo)return bo;
                        }
    return 0;
}
int getstep(BOARD now)
{
    int step=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)step+=now.a[i][j];
    if(step==0)step=1;else step=-1;
    return step;
}
int dfs(BOARD now)
{
    tree[now.number]=now;
    if(now.win)
    {
        tree[now.number].score=now.win==-1?10:0;
        return now.win==-1?10:0;
    }
    int step=getstep(now),ping=1,Min=1e9,Max=-1e9;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(!now.a[i][j])
            {ping=0;
                NODE++;BOARD next=now;next.number=NODE;
                son[now.number].push_back(NODE);
                next.a[i][j]=step;
                next.win=check(next);
                if(step==1)Min=min(Min,dfs(next));
                else Max=max(Max,dfs(next));
                
            }
    if(ping==1)
    {
        tree[now.number].score=5;
        return 5;
    }
    tree[now.number].score=(step==1?Min:Max);
    return tree[now.number].score;
}
BOARD empty_board()
{
    BOARD empty;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
    return empty;
}
void print_board(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+100,y+100);
    x+=10;y+=10;
    setcolor(BLACK);
    int t=80/3;
    for(int i=x;i<=x+80;i+=t)line(i,y,i,y+80);
    for(int j=y;j<=y+80;j+=t)line(x,j,x+80,j);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(z.a[i][j]==1)
            {
                setcolor(BLUE);setlinewidth(2);
                circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
            }
    else if(z.a[i][j]==-1)
    {
        setcolor(RED);
        setlinewidth(3);
        line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
        line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
        setlinewidth(1);
    }
}
void change_board(int x,int y,BOARD &z)
{
    x+=10;y+=10;
    int t=80/3;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
            {
                if(Dr)z.a[i][j]=1;PC=1;
            }
}
void print_line()
{
    setcolor(BLACK);
    for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+50,node[LINE[i][1]].x+50,node[LINE[i][1]].y+50);
}
void mousedata()
{
    if(Dr==0)LOCK=0;
    Dl=0;Rc=0;
    while(mousemsg())
    {
        mouse_msg m=getmouse();
        if(m.is_move())mx=m.x,my=m.y;
        if(m.is_down()&&m.is_mid())Dl=1;
        if(m.is_down()&&m.is_left())Dr=1;
        if(m.is_up()&&m.is_left())Dr=0;
        if(m.is_down()&&m.is_right())Rc=1;
    }    
}
int main()
{srand(time(0));
    initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
    BOARD empty=empty_board();
    while(1)
    {
        setcaption("下棋模式（左键下棋，右键确认）");Rc=0;
        while(Rc==0)
        {
            cleardevice();
            print_board(5,250,empty);
            change_board(5,250,empty);
            mousedata();
            delay_ms(50);
        }print_board(5,250,empty);
        for(int i=1;i<=NODE;i++)
        {
            show[i]=0;tree[i].number=0;tree[i].win=0;
            son[i].clear();node[i].SON=0;
        }
        NODE=1;LN=0;empty.number=1;
        dfs(empty);
        setcaption("显示模式（点击右键AI决策，中键展开，左键移动）");
        cout<<"TOTAL:"<<NODE<<endl;
        int t=0;
        node[1].y=250;node[1].x=5;show[1]=1;Rc=0;
        int Min=1e9,Max=-1e9;
        vector<BOARD>CAN;CAN.clear();
        if(son[1].size()==0)exit(0);
        //for(int i=1;i<=10;i++)cout<<son[i].size();
        for(auto i:son[1])
        {//cout<<i<<endl;
            Max=max(Max,tree[i].score);
        }
        Min=Max;
        for(auto i:son[1])if(tree[i].score==Min)CAN.push_back(tree[i]);
        empty=CAN[rand()%CAN.size()];cout<<"[COMPLETE]\n";
        while(Rc==0)
        {
            cleardevice();
            print_line();
            
            for(int i=1;i<=NODE;i++)
                if(show[i])
                {
                    print_board(node[i].x,node[i].y,tree[i]);
                    outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
                    if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
                        node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
                        son[i].pop_back();node[i].SON++;
                    }
                    if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        if(LOCK==i||LOCK==0)
                        {
                            node[i].x=mx-50;node[i].y=my-50;
                            LOCK=i;
                        }
                        
                    }
                }
            mousedata();
            delay_ms(100);
        }
    }
}

     T 
    
   
     e 
    
   
     s 
    
   
     t 
    
   
       
    
   
     3 
    
   
  
    Test \ 3 
   
  
Test 3

#include<bits/stdc++.h>
#include<graphics.h>
using namespace std;
struct BOARD{int a[10][10];int number,win,score,stepx,stepy;};
struct SHOW{int x,y;int SON;}node[402088];
int NODE=1;bool show[402808];
BOARD tree[402880];
vector<int>son[400288];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int cmp(int a,int b)
{
    return tree[a].score<tree[b].score;
}
int check(BOARD now,int x,int y)
{
    for(int i=x;i<=x;i++)
        for(int j=y;j<=y;j++)
            if(now.a[i][j])
                for(int fx=-1;fx<=1;fx++)
                    for(int fy=-1;fy<=1;fy++)
                        if(fx!=0||fy!=0)
                        {
                            int bo=now.a[i][j];
                            for(int f=1;f<=4;f++)
                                if(i+fx*f>=10||j+fy*f>=10||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
                            if(bo)return bo;
                        }
    return 0;
}
int evaluateDirection(const BOARD board, int row, int col, int player) 
{
    int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
    int score = 0;
    for (int i = 0; i < 4; i++) 
    {
        int count = 0,dc=1;
        for (int j = 1; j <= 5; j++) 
        {
            int newRow = row + j * directions[i][0];
            int newCol = col + j * directions[i][1];
            if (newRow < 0 || newRow >= 10 || newCol < 0 || newCol >= 10 ||
                board.a[newRow][newCol] != player)
            {
                if(board.a[newRow][newCol] != 0)dc=2;
                break;
            }
            count++;
        }
        if(board.a[row  -1 * directions[i][0]][col - 1 * directions[i][1]]==-player)dc*=2;
        if (count == 1) {
            score += 1/dc;
        } else if (count == 2) {
            score += 10/dc;
        } else if (count == 3) {
            score += 100/dc;
        } else if (count == 4) {
            score += 900/dc;
        } else if (count == 5) {
            score += 1000/dc;
        }
    }
    
    return score;
}
int evaluateBoard(const BOARD board) 
{
    int score = 0;
    for (int i = 0; i < 10; i++) 
    {
        for (int j = 0; j < 10; j++) 
        {
            if (board.a[i][j] == 1) 
                score += evaluateDirection(board, i, j, 1);
            else if (board.a[i][j] == -1) 
                score -= evaluateDirection(board, i, j, -1);
        }
    }
    return score;
}
int getstep(BOARD now)
{
    int step=0;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)step+=now.a[i][j];
    if(step==0)step=1;else step=-1;
    return step;
}
int dfs(BOARD now,int k,int Nk)
{//if(rand()%10000==0)cout<<now.number;
    son[now.number].clear();
    int nd=NODE;
    tree[now.number]=now;
    if(now.win)
    {
        tree[now.number].score=now.win==-1?1000:0;
        return now.win==-1?1000:0;
    }
    int step=getstep(now),Min=1e9,Max=-1e9;
    if(k>min(Nk,4))
    {
        tree[now.number].score=-evaluateBoard(now);
        return tree[now.number].score;
    }
    map<int,int>ndx,ndy;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(!now.a[i][j])
            {
                NODE++;BOARD next=now;next.number=NODE;
                son[now.number].push_back(NODE);
                next.a[i][j]=step;ndx[NODE]=i;ndy[NODE]=j;
                next.win=check(next,i,j);next.stepx=i;next.stepy=j;
                if(step==1)Min=min(Min,dfs(next,k+1,Nk));
                else Max=max(Max,dfs(next,k+1,Nk));
            }
    sort(son[now.number].begin(),son[now.number].end(),cmp);
    if(getstep(tree[now.number])==1)reverse(son[now.number].begin(),son[now.number].end());
    if(k>2)
    {
        Min=1e9,Max=-1e9;NODE=nd;
        vector<int>SON;
        for(int i=0;i<5;i++)
        {
            NODE++;BOARD next=now;next.number=NODE;
            SON.push_back(NODE);
            next.stepx=ndx[son[now.number][i]];next.stepy=ndy[son[now.number][i]];
            next.a[next.stepx][next.stepy]=step;next.win=check(next,next.stepx,next.stepy);
            if(step==1)Min=min(Min,dfs(next,k+1,k+3));
            else Max=max(Max,dfs(next,k+1,k+3));
        }
        son[now.number]=SON;
    }
    
    tree[now.number].score=(step==1?Min:Max);
    return tree[now.number].score;
}
BOARD empty_board()
{
    BOARD empty;
    for(int i=0;i<10;i++)for(int j=0;j<10;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
    return empty;
}
void print_board_all(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+300,y+300);
    x+=10;y+=10;
    setcolor(BLACK);
    int t=270/10;
    for(int i=x;i<=x+280;i+=t)line(i,y,i,y+280);
    for(int j=y;j<=y+280;j+=t)line(x,j,x+280,j);
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(z.a[i][j]==1)
            {
                setcolor(BLUE);setlinewidth(2);
                circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
            }
    else if(z.a[i][j]==-1)
    {
        setcolor(RED);
        setlinewidth(3);
        line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
        line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
        setlinewidth(1);
    }
}
void print_board_step(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+100,y+40);
    x+=20;y+=10;
    setcolor(BLACK);
    if(z.stepx==0&&z.stepy==0);else
        outtextxy(x,y,("("+to_string(z.stepx+1)+","+to_string(z.stepy+1)+")").c_str());
}
void change_board(int x,int y,BOARD &z)
{
    x+=10;y+=10;
    int t=270/10;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
            {
                if(Dr)z.a[i][j]=getstep(z);
            }
}
void print_line()
{
    setcolor(BLACK);
    for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+20,node[LINE[i][1]].x+50,node[LINE[i][1]].y+20);
}
void mousedata()
{
    if(Dr==0)LOCK=0;
    Dl=0;Rc=0;
    while(mousemsg())
    {
        mouse_msg m=getmouse();
        if(m.is_move())mx=m.x,my=m.y;
        if(m.is_down()&&m.is_mid())Dl=1;
        if(m.is_down()&&m.is_left())Dr=1;
        if(m.is_up()&&m.is_left())Dr=0;
        if(m.is_down()&&m.is_right())Rc=1;
    }    
}

int main()
{
    initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
    BOARD empty=empty_board();
    while(1)
    {
        setcaption("游玩模式（点击右键AI开始计算，左键下棋）");
        Rc=0;
        cleardevice();
        while(Rc==0)
        {
            print_board_all(5,250,empty);
            change_board(5,250,empty);
            mousedata();
            if(Dl)empty=empty_board();
            delay_ms(100);
        }
        for(int i=1;i<=NODE;i++)
        {
            show[i]=0;tree[i].number=0;tree[i].win=0;
            son[i].clear();node[i].SON=0;
        }
        NODE=1;LN=0;
        dfs(empty,1,2);
        setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
        cout<<"TOTAL:"<<NODE<<endl;
        int t=0;
        node[1].y=250;node[1].x=5;show[1]=1;Rc=0;int lc=1;
        empty=tree[son[1].back()];empty.number=1;empty.score=0;
        while(Rc==0)
        {
            cleardevice();
            print_line();print_board_all(0,0,tree[lc==0?1:lc]);
            for(int i=NODE;i>=1;i--)
                if(show[i])
                {
                    
                    print_board_step(node[i].x,node[i].y,tree[i]);
                    outtextxy(node[i].x,node[i].y-20,("["+to_string(son[i].size())+"]"+"Score:"+to_string(tree[i].score)).c_str());
                    if(Dl&&!son[i].empty()&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+100)
                    {
                        show[son[i].back()]=1;node[son[i].back()].x=node[i].x+120;
                        node[son[i].back()].y=node[i].y;LINE[++LN][0]=i;LINE[LN][1]=son[i].back();
                        son[i].pop_back();node[i].SON++;
                    }
                    if(Dr&&mx>node[i].x&&mx<node[i].x+100&&my>node[i].y&&my<node[i].y+40)
                    {
                        if(LOCK==i||LOCK==0)
                        {
                            node[i].x=mx-50;node[i].y=my-20;
                            LOCK=i;lc=i;
                        }
                        
                    }
                }
            mousedata();
            delay_ms(100);
        }
        
    }
}

     五子棋最终 
    
   
     A 
    
   
     I 
    
   
     ( 
    
   
     我无法评价 
    
   
     ) 
    
   
  
    五子棋最终AI(我无法评价) 
   
  
五子棋最终AI(我无法评价)

#include<bits/stdc++.h>
#include<graphics.h>
using namespace std;
struct BOARD{int a[10][10];int number,win,score,stepx,stepy;};
struct SHOW{int x,y;int SON;}node[402088];
int NODE=1;bool show[402808];
BOARD tree[402880];
vector<int>son[400288];
int mx,my,Dl,LINE[400288][5],LN,Dr,LOCK,Rc=1;
int cmp(int a,int b)
{
    return tree[a].score<tree[b].score;
}
int check(BOARD now,int x,int y)
{
    for(int i=x;i<=x;i++)
        for(int j=y;j<=y;j++)
            if(now.a[i][j])
                for(int fx=-1;fx<=1;fx++)
                    for(int fy=-1;fy<=1;fy++)
                        if(fx!=0||fy!=0)
                        {
                            int bo=now.a[i][j];
                            for(int f=1;f<=4;f++)
                                if(i+fx*f>=10||j+fy*f>=10||i+fx*f<0||j+fy*f<0||now.a[i][j]!=now.a[i+fx*f][j+fy*f])bo=0;
                            if(bo)return bo;
                        }
    return 0;
}
int evaluateDirection(const BOARD board, int row, int col, int player) 
{
    int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
    int score = 0;
    for (int i = 0; i < 4; i++) 
    {
        int count = 0,dc=1;
        for (int j = 1; j <= 5; j++) 
        {
            int newRow = row + j * directions[i][0];
            int newCol = col + j * directions[i][1];
            if (newRow < 0 || newRow >= 10 || newCol < 0 || newCol >= 10 ||
                board.a[newRow][newCol] != player)
            {
                if(board.a[newRow][newCol] != 0)dc=2;
                break;
            }
            count++;
        }
        if(board.a[row  -1 * directions[i][0]][col - 1 * directions[i][1]]==-player)dc*=2;
        if (count == 1) {
            score += 1/dc;
        } else if (count == 2) {
            score += 10/dc;
        } else if (count == 3) {
            score += 100/dc;
        } else if (count == 4) {
            score += 900/dc;
        } else if (count == 5) {
            score += 1000/dc;
        }
    }
    
    return score;
}
int evaluateBoard(const BOARD board) 
{
    int score = 0;
    for (int i = 0; i < 10; i++) 
    {
        for (int j = 0; j < 10; j++) 
        {
            if (board.a[i][j] == 1) 
                score += evaluateDirection(board, i, j, 1);
            else if (board.a[i][j] == -1) 
                score -= evaluateDirection(board, i, j, -1);
        }
    }
    return score;
}
int getstep(BOARD now)
{
    int step=0;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)step+=now.a[i][j];
    if(step==0)step=1;else step=-1;
    return step;
}
int dfs(BOARD now,int k,int Nk,int alpha,int beta)
{//if(rand()%10000==0)cout<<now.number;
    son[now.number].clear();
    int nd=NODE;
    tree[now.number]=now;
    if(now.win)
    {
        tree[now.number].score=now.win==-1?1000:0;
        return now.win==-1?1000:0;
    }
    int step=getstep(now),Min=1e9,Max=-1e9;
    if(k>min(Nk,6))
    {
        tree[now.number].score=-evaluateBoard(now);
        return tree[now.number].score;
    }
    map<int,int>ndx,ndy;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(!now.a[i][j])
            {
                NODE++;BOARD next=now;next.number=NODE;
                son[now.number].push_back(NODE);
                next.a[i][j]=step;ndx[NODE]=i;ndy[NODE]=j;
                next.win=check(next,i,j);next.stepx=i;next.stepy=j;
                int t=step==1?dfs(next,k+1,Nk,alpha,Min):dfs(next,k+1,Nk,Max,beta);
                //if(t>beta||t<alpha)return t;
                if(step==1)Min=min(Min,t);
                else Max=max(Max,t);
            }
    sort(son[now.number].begin(),son[now.number].end(),cmp);
    if(getstep(tree[now.number])==1)reverse(son[now.number].begin(),son[now.number].end());
    if(k>2)
    {
        Min=1e9,Max=-1e9;NODE=nd;
        vector<int>SON;
        for(int i=0;i<5;i++)
        {
            NODE++;BOARD next=now;next.number=NODE;
            SON.push_back(NODE);
            next.stepx=ndx[son[now.number][i]];next.stepy=ndy[son[now.number][i]];
            next.a[next.stepx][next.stepy]=step;next.win=check(next,next.stepx,next.stepy);
            int t=step==1?dfs(next,k+1,Nk,alpha,Min):dfs(next,k+1,Nk,Max,beta);
            if(step==1)Min=min(Min,t);
            else Max=max(Max,t);
        }
        son[now.number]=SON;
    }
    
    tree[now.number].score=(step==1?Min:Max);
    return tree[now.number].score;
}
BOARD empty_board()
{
    BOARD empty;
    for(int i=0;i<10;i++)for(int j=0;j<10;j++)empty.a[i][j]=0;empty.number=1;empty.win=0;
    return empty;
}
void print_board_all(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+300,y+300);
    x+=10;y+=10;
    setcolor(BLACK);
    int t=270/10;
    for(int i=x;i<=x+280;i+=t)line(i,y,i,y+280);
    for(int j=y;j<=y+280;j+=t)line(x,j,x+280,j);
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(z.a[i][j]==1)
            {
                setcolor(BLUE);setlinewidth(2);
                circle(x+i*t+t/2,y+j*t+t/2,t/2-1);setlinewidth(1);
            }
    else if(z.a[i][j]==-1)
    {
        setcolor(RED);
        setlinewidth(3);
        line(x+t*i+2,y+t*j+2,x+t*i+t-2,y+t*j+t-2);
        line(x+t*i+2,y+t*j+t-2,x+t*i+t-2,y+t*j+2);
        setlinewidth(1);
    }
}
void print_board_step(int x,int y,BOARD z)
{
    setcolor(getstep(z)==1?RED:BLUE);
    setfillcolor(WHITE);
    fillrect(x,y,x+100,y+40);
    x+=20;y+=10;
    setcolor(BLACK);
    if(z.stepx==0&&z.stepy==0);else
        outtextxy(x,y,("("+to_string(z.stepx+1)+","+to_string(z.stepy+1)+")").c_str());
}
void change_board(int x,int y,BOARD &z)
{
    x+=10;y+=10;
    int t=270/10;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(mx>x+t*i&&mx<x+t*i+t&&my>y+t*j&&my<y+t*j+t)
            {
                if(Dr)z.a[i][j]=getstep(z);
            }
}
void print_line()
{
    setcolor(BLACK);
    for(int i=1;i<=LN;i++)line(node[LINE[i][0]].x+50,node[LINE[i][0]].y+20,node[LINE[i][1]].x+50,node[LINE[i][1]].y+20);
}
void mousedata()
{
    if(Dr==0)LOCK=0;
    Dl=0;Rc=0;
    while(mousemsg())
    {
        mouse_msg m=getmouse();
        if(m.is_move())mx=m.x,my=m.y;
        if(m.is_down()&&m.is_mid())Dl=1;
        if(m.is_down()&&m.is_left())Dr=1;
        if(m.is_up()&&m.is_left())Dr=0;
        if(m.is_down()&&m.is_right())Rc=1;
    }    
}

int main()
{
    initgraph(1000,600);setbkcolor(WHITE);setcolor(BLACK);
    BOARD empty=empty_board();
    while(1)
    {
        setcaption("游玩模式（点击右键AI开始计算，左键下棋）");
        Rc=0;
        cleardevice();
        while(Rc==0)
        {
            print_board_all(0,0,empty);
            change_board(0,0,empty);
            mousedata();
            if(Dl)empty=empty_board();
            delay_ms(100);
        }
        for(int i=1;i<=NODE;i++)
        {
            show[i]=0;tree[i].number=0;tree[i].win=0;
            son[i].clear();node[i].SON=0;
        }
        NODE=1;LN=0;
        dfs(empty,1,3,-10000,10000);
        setcaption("显示模式（点击右键编辑初始棋盘，中键展开，左键移动）");
        cout<<"TOTAL:"<<NODE<<endl;
        int t=0;
        node[1].y=250;node[1].x=5;show[1]=1;Rc=0;int lc=1;
        empty=tree[son[1].back()];empty.number=1;empty.score=0;
    }
}
标签： 人工智能
本文转载自: https://blog.csdn.net/wangyuhan2010/article/details/133558562
版权归原作者 wangyuhan2010 所有， 如有侵权，请联系我们删除。
登录后发布评论

“如何编写一个五子棋AI（附AI源码）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航