当前位置：首页 » 《关于电脑》 » 正文

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

22 人参与  2024年04月09日 16:46  分类 : 《关于电脑》  评论

点击全文阅读


注:此文章的代码推荐在 小熊猫 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);elseouttextxy(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);elseouttextxy(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;}}

点击全文阅读


本文链接：http://zhangshiyu.com/post/92917.html

<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 老书虫看了N遍的结婚当天，他逼我给白月光输血最新章节
  • 和豪门老公联姻后知乎后续免费试读
  • 女总裁的神级赘婿全文目录-秦誉萧菱雪小说无弹窗阅读
  • 快手热推《多年等候，他仍是她期待的终点》小说主角纪云佳宋季铭在线阅读
  • 沈梨陆景川全文小说最新章节阅读沈梨陆景川
  • 快手热推《夫君要和皇妃私奔，我转头让他做铁王八》小说主角江承轩温元在线阅读
  • 主人公温梨周行云在线免费试读《掐指一算，玄学真千金说你要完蛋》最新章节列表
  • 《转生：我以毒蛇之躯，屹立世界之巅》龙度龙宴免费全章节目录阅读
  • 老书虫力荐《全民寿命转盘，只有我能指定奖励》免费无弹窗阅读
  • 陈言张青斯是哪部小说的主角 陈言张青斯全文阅读
  • 熬夜也要看完的大小姐重生后，好孕姨娘慌了小说推荐
  • 抖音爆款小说《绯闻陷落闻檀明濯》免费txt全文阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1