热门标签
热门文章
- 1idea类存在找不到解决办法_idea找不到已存在的工具类
- 2AI示范代码_ai代码
- 3Docker概念|容器|镜像|命令详细（创建，删除，修改，添加）_docker创建容器
- 4Java学习总结之坦克大战项目（完结版）
- 5苹果个人开发者自动发包(超级签)教程(1)-UDID获取_描述文件自动注册uuid到服务器
- 6Mac os镜像下载地址记录
- 7MacOS下使用如何开启并使用MySQL_mac 启动mysql
- 8[STM32] Keil 创建 HAL 库的工程模板
- 9如何让pycharm的shell环境代码编写同python文件中一样丝滑_pycharm美化shell脚本
- 10SAP BASIS ADM100 中文版 Unit 8（1）_sap 假脱机清单 abap清单
当前位置: article > 正文
用C++实现五子棋人机对战小游戏_c++五子棋人机算法
作者：我家自动化 | 2024-04-02 20:16:50
赞
踩
c++五子棋人机算法
如何用C++实现五子棋小游戏呢？
五子棋可谓是家喻户晓了，在科技如此发达的今天，我们能不能用电脑实现五子棋人机对弈呢？
答案当然是可以的
首先，思考一下我们需要完成哪些步骤
1、打印棋盘（使用二维数组即可）
2、判断胜负（可以考虑深搜，但是暴力似乎能让代码更简洁）
3、思考下一部棋该怎么走
- 1
- 2
- 3
先从最简单的一部开始：打印棋盘
void out(){
for(int i=0;i<=24;i++){
for(int j=0;j<=24;j++){
if(a[i][j]!=0){ //a数组即为这个棋盘，用来存储棋子位置
if(a[i][j]==1&&i!=0&&j!=0) printf(" O");
else if(a[i][j]==2&&i!=0&&j!=0) printf(" X");
else cout<<setw(2)<<a[i][j];
}
else printf(" -");
}
printf("\n");
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
构建的棋盘大概是这个样子：
（O是对手，X是电脑）
- 1 2 3 4 5 6 7 8 9101112131415161718192021222324 1 - - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - 3 - - - - - - - - - - - - - - - - - - - - - - - - 4 - - - - - - - - - - - - - - - - - - - - - - - - 5 - - - - - - - - - - - - - - - - - - - - - - - - 6 - - - - - - - - - - - - - - - - - - - - - - - - 7 - - - - - - - - - - - - - - - - - - - - - - - - 8 - - - - - - - - - - - - - - - - - - - - - - - - 9 - - - - - - - - - - - - - - - - - - - - - - - - 10 - - - - - - - - - - - - - - - - - - - - - - - - 11 - - - - - - - - - - - - - - - - - - - - - - - - 12 - - - - - - - - - - - - - - - - - - - - - - - - 13 - - - - - - - - - - - - - - - - - - - - - - - - 14 - - - - - - - - - - - - - - - - - - - - - - - - 15 - - - - - - - - - - - - - - - - - - - - - - - - 16 - - - - - - - - - - - - - - - - - - - - - - - - 17 - - - - - - - - - - - - - - - - - - - - - - - - 18 - - - - - - - - - - - - - - - - - - - - - - - - 19 - - - - - - - - - - - - - - - - - - - - - - - - 20 - - - - - - - - - - - - - - - - - - - - - - - - 21 - - - - - - - - - - - - - - - - - - - - - - - - 22 - - - - - - - - - - - - - - - - - - - - - - - - 23 - - - - - - - - - - - - - - - - - - - - - - - - 24 - - - - - - - - - - - - - - - - - - - - - - - -
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
这一步很简单，自己思考一下吧
第二部，判断输赢
这一步我比较推荐用暴力搜索，反正又不是NOIP，不差这点时间复杂度 /doge
思路就是搜索每一个位置，看这个位置下、右、斜是否有连续的五个子，搜就完了
int judgewin(){ for(int i=1;i<=25;i++){ for(int j=1;j<=25;j++){ if(a[i][j]==0) continue; int numwin=0; for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; for(numwin=1;numwin<=4;numwin++){ if(a[i][j+numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j+numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; if(j>5){ for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j-numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} } } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
这部也还不算困难，自己看看吧
最关键的一步
现在，终于到了这篇算法的精髓
在写代码之前，先把程序的计算原理理解一下：
1、构建一个能和a数组对应的数组dp（虽然不是dp，但是类似dp）
2、dp里面存储着这个位置下子是否合理的数字，数字越大，越应该下在这里
3、枚举每一个点，将dp数组填满
但是说来简单，究竟怎么填这个数字呢？
1、发现四周有敌人的半活4就+1000
2、发现四周有敌人的活3就+500
3、发现四周有敌人的双活2就+400
（这些算致命的，是防守，同理，自己的子也是如此，但数值要再+100，因为下一步就是我们进攻了）
…
（后面就极为复杂了，是经过半个月研究才弄清楚的，详见代码）
void checksit(int n,int m){ for(int i=0;i<8;i++){ int num=0; for(int j=1;j<5;j++){ if(a[n+j*dx[i]][m+j*dy[i]]==1) num++; if(a[n+j*dx[i]][m+j*dy[i]]==2) break; } for(int j=1;j<5;j++){ if(a[n-j*dx[i]][m-j*dy[i]]==1) num++; if(a[n-j*dx[i]][m-j*dy[i]]==2) break; } if(num==4) {dp[n][m]+=1000; flag[n][m]==3;} if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==2) dp[n][m]+=10; if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==0) {dp[n][m]+=500; flag[n][m]==1;} if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==2) dp[n][m]+=1; if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==0) dp[n][m]+=3; } for(int i=0;i<8;i++){ int num=0; for(int j=1;j<5;j++){ if(a[n+j*dx[i]][m+j*dy[i]]==2) num++; else break; } for(int j=1;j<5;j++){ if(a[n-j*dx[i]][m-j*dy[i]]==2) num++; else break; } if(num==4) {dp[n][m]+=1000; flag[n][m]==2;} if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==1) dp[n][m]+=20; if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==0) {dp[n][m]+=500; flag[n][m]==2;} if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==1) dp[n][m]+=2; if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==0) dp[n][m]+=10; } for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(j==i) continue; int num=0; for(int k=1;k<3;k++){ if(a[n+k*dx[j]][m+k*dy[j]]==1) num++; if(a[n+k*dx[i]][m+k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[j]][m-k*dy[j]]==1) num++; if(a[n-k*dx[i]][m-k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n+k*dx[i]][m+k*dy[i]]==1) num++; if(a[n+k*dx[i]][m+k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[i]][m-k*dy[i]]==1) num++; if(a[n-k*dx[i]][m-k*dy[i]]==2) {num-=2;break;} } if(num>=4) dp[n][m]+=80; else if(num==3) dp[n][m]+=20; } } for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(j==i) continue; int num=0; for(int k=1;k<3;k++){ if(a[n+k*dx[j]][m+k*dy[j]]==2) num++; if(a[n+k*dx[i]][m+k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[j]][m-k*dy[j]]==2) num++; if(a[n-k*dx[i]][m-k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n+k*dx[i]][m+k*dy[i]]==2) num++; if(a[n+k*dx[i]][m+k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[i]][m-k*dy[i]]==2) num++; if(a[n-k*dx[i]][m-k*dy[i]]==1) {num-=2;break;} } if(num>=4) dp[n][m]+=50; else if(num==3) dp[n][m]+=10; } } for(int i=0;i<8;i++){ int seti=0,setj=0; for(int j=1;j<5;j++) if(a[n+j*dx[i]][m+j*dy[i]]==1) seti=j; for(int j=1;j<5;j++) if(a[n-j*dx[i]][m-j*dy[i]]==1) setj=j; if(abs(seti-setj)<=4) dp[n][m]-=30; } int num=0; for(int k=0;k<8;k++){ if(a[n+dx[k]][m+dy[k]]==2){ dp[n][m]+=10; num++; } if(a[n+dx[k]][m+dy[k]]==1) dp[n][m]+=2; } if(num==0) for(int i=0;i<8;i++){ if(a[n+rx[i]][m+rx[i]]==2) dp[n][m]-=20; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
整合起来，大概长这样：
#include <bits/stdc++.h> //可替换成<iostream>和<algorithm> using namespace std; int a[30][30],dp[30][30]; int flag[30][30]; int dx[9]={-1,-1,-1,0,0,1,1,1}; int dy[9]={-1,0,1,-1,1,-1,0,1}; int rx[9]={-2,-2,-1,1,2,2,1,-1}; int ry[9]={-1,1,2,2,1,-1,-2,-2}; int step,check; void checksit(int n,int m){ for(int i=0;i<8;i++){ int num=0; for(int j=1;j<5;j++){ if(a[n+j*dx[i]][m+j*dy[i]]==1) num++; if(a[n+j*dx[i]][m+j*dy[i]]==2) break; } for(int j=1;j<5;j++){ if(a[n-j*dx[i]][m-j*dy[i]]==1) num++; if(a[n-j*dx[i]][m-j*dy[i]]==2) break; } if(num==4) {dp[n][m]+=1000; flag[n][m]==3;} if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==2) dp[n][m]+=10; if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==0) {dp[n][m]+=500; flag[n][m]==1;} if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==2) dp[n][m]+=1; if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==0) dp[n][m]+=3; } for(int i=0;i<8;i++){ int num=0; for(int j=1;j<5;j++){ if(a[n+j*dx[i]][m+j*dy[i]]==2) num++; else break; } for(int j=1;j<5;j++){ if(a[n-j*dx[i]][m-j*dy[i]]==2) num++; else break; } if(num==4) {dp[n][m]+=1000; flag[n][m]==2;} if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==1) dp[n][m]+=20; if(num==3&&a[n+4*dx[i]][m+4*dy[i]]==0) {dp[n][m]+=500; flag[n][m]==2;} if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==1) dp[n][m]+=2; if(num==2&&a[n+3*dx[i]][m+3*dy[i]]==0) dp[n][m]+=10; } for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(j==i) continue; int num=0; for(int k=1;k<3;k++){ if(a[n+k*dx[j]][m+k*dy[j]]==1) num++; if(a[n+k*dx[i]][m+k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[j]][m-k*dy[j]]==1) num++; if(a[n-k*dx[i]][m-k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n+k*dx[i]][m+k*dy[i]]==1) num++; if(a[n+k*dx[i]][m+k*dy[i]]==2) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[i]][m-k*dy[i]]==1) num++; if(a[n-k*dx[i]][m-k*dy[i]]==2) {num-=2;break;} } if(num>=4) dp[n][m]+=80; else if(num==3) dp[n][m]+=20; } } for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ if(j==i) continue; int num=0; for(int k=1;k<3;k++){ if(a[n+k*dx[j]][m+k*dy[j]]==2) num++; if(a[n+k*dx[i]][m+k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[j]][m-k*dy[j]]==2) num++; if(a[n-k*dx[i]][m-k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n+k*dx[i]][m+k*dy[i]]==2) num++; if(a[n+k*dx[i]][m+k*dy[i]]==1) {num-=2;break;} } for(int k=1;k<3;k++){ if(a[n-k*dx[i]][m-k*dy[i]]==2) num++; if(a[n-k*dx[i]][m-k*dy[i]]==1) {num-=2;break;} } if(num>=4) dp[n][m]+=50; else if(num==3) dp[n][m]+=10; } } for(int i=0;i<8;i++){ int seti=0,setj=0; for(int j=1;j<5;j++) if(a[n+j*dx[i]][m+j*dy[i]]==1) seti=j; for(int j=1;j<5;j++) if(a[n-j*dx[i]][m-j*dy[i]]==1) setj=j; if(abs(seti-setj)<=4) dp[n][m]-=30; } int num=0; for(int k=0;k<8;k++){ if(a[n+dx[k]][m+dy[k]]==2){ dp[n][m]+=10; num++; } if(a[n+dx[k]][m+dy[k]]==1) dp[n][m]+=2; } if(num==0) for(int i=0;i<8;i++){ if(a[n+rx[i]][m+rx[i]]==2) dp[n][m]-=20; } } int judgewin(){ for(int i=1;i<=25;i++){ for(int j=1;j<=25;j++){ if(a[i][j]==0) continue; int numwin=0; for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; for(numwin=1;numwin<=4;numwin++){ if(a[i][j+numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j+numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} numwin==0; if(j>5){ for(numwin=1;numwin<=4;numwin++){ if(a[i+numwin][j-numwin]!=a[i][j]) break; } if(numwin==5) {return a[i][j];} } } } return 0; } void out(){ for(int i=0;i<=24;i++){ for(int j=0;j<=24;j++){ if(a[i][j]!=0){ if(a[i][j]==1&&i!=0&&j!=0) printf(" O"); else if(a[i][j]==2&&i!=0&&j!=0) printf(" X"); else cout<<setw(2)<<a[i][j]; } else printf(" -"); } printf("\n"); } } int main(){ int tempi,tempj; for(int i=3;i<=24;i++) a[0][i]=i; for(int i=3;i<=24;i++) a[i][0]=i; out(); while(1){ step++; memset(dp,0,sizeof(dp)); memset(flag,0,sizeof(flag)); int n,m; scanf("%d%d",&n,&m); if(a[n][m]!=0||n>24||m>24){ printf("Useless place!Try again!"); scanf("%d%d",&n,&m); } a[n][m]=1; dp[n][m]=0; out(); int ans=judgewin(); if(ans==2) {printf("Computer win!\n"); break;} if(ans==1) {printf("Player win!\n"); break;} if(step>=100) {printf("Good game!\n");break;} if(step==1){ dp[n+1][m+2]=100; tempi=n+1;tempj=m+2; } else if(step==2){ if(a[tempi+1][tempj-1]==0) dp[tempi+1][tempj-1]=100; else dp[tempi-1][tempj-1]=100; } else for(int i=1;i<=25;i++){ for(int j=1;j<=25;j++){ if(a[i][j]!=0) continue; checksit(i,j); } } int max=0,maxn=0,maxm=0; for(int i=1;i<=25;i++){ for(int j=1;j<=25;j++){ if(max<dp[i][j]){ max=dp[i][j]; maxn=i;maxm=j; } } } int mfl=0,mfln=0,mflm=0; for(int i=1;i<=25;i++){ for(int j=1;j<=25;j++){ if(mfl<flag[i][j]){ mfl=flag[i][j]; mfln=i;mflm=j; } if(mfl==flag[i][j]&&mfl!=0){ if(dp[mfln][mflm]<dp[i][j]){ mfln=i;mfln=j; } } } } if(mfl==0) printf("%d %d\n",maxn,maxm); else printf("%d %d\n",mfln,mflm); a[maxn][maxm]=2; out(); ans=judgewin(); if(ans==2) {printf("Computer win!\n"); break;} if(ans==1) {printf("Player win!\n"); break;} if(step>=100) {printf("Good game!\n");break;} } system("pause"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
（代码如有任何错误与不理解，欢迎评论！）
码字辛苦，给个赞吧！
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/353664
推荐阅读
相关标签
