本文共 5583 字，大约阅读时间需要 18 分钟。
不会输，超碉！井字棋这个游戏真是太无聊啦！
算法大概就是，有一个给状况进行估价的函数，深搜每种状况，假设每个人都按对自己最有利的方式走（假设玩家也是不傻），最后让电脑走出最有利的一步。
实验报告：
代码：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std; 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define mf1(array) memset(array, -1, sizeof(array)) 17 #define minf(array) memset(array, 0x3f, sizeof(array)) 18 #define REP(i,n) for(i=0;i<(n);i++) 19 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 20 #define FORD(i,x,y) for(i=(x);i>=(y);i--) 21 #define RD(x) scanf("%d",&x) 22 #define RD2(x,y) scanf("%d%d",&x,&y) 23 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 24 #define WN(x) printf("%d\n",x); 25 #define RE freopen("D.in","r",stdin) 26 #define WE freopen("huzhi.txt","w",stdout) 27 #define mp make_pair 28 #define pb push_back 29 #define pf push_front 30 #define ppf pop_front 31 #define ppb pop_back 32 typedef long long ll; 33 typedef unsigned long long ull; 34 35 const char CHESS[3]= { '-', '@', '#'}; 36 37 struct Board { 38 int a[3][3]; 39 inline void Init() { 40 memset(a,0,sizeof(a)); 41 } 42 inline void operator =(Board b) { 43 int i,j; 44 REP(i,3)REP(j,3)a[i][j]=b.a[i][j]; 45 } 46 }; 47 48 int GetInput(string s, int maxNum) { 49 int t; 50 char c; 51 while(1) { 52 cout< =0 && t =0 && x<=2 && y>=0 && y<=2)) { 85 puts("输入错误！请重新输入！横纵坐标都要是0或者1或者2。"); 86 continue; 87 } 88 if(bod.a[x][y]!=0) { 89 puts("下错了，这个位置有棋！请选择其他位置。"); 90 continue; 91 } 92 break; 93 } 94 bod.a[x][y]=1; 95 //OutBoard(bod); 96 printf("你下到了(%d,%d)位置。\n",x,y); 97 puts(""); 98 // puts("(按回车键继续)"); 99 // getch();100 // system("cls");101 }102 103 inline int Evaluate(const Board &bod) {104 int i,j;105 int cnt[3];106 int re=0;107 REP(i,3) {108 mz(cnt);109 REP(j,3)cnt[bod.a[i][j]]++;110 if(cnt[1]==3)return 1000;111 if(cnt[2]==3)return -1000;112 if(cnt[1]==2&&cnt[0]==1)re+=50;113 else if(cnt[1]==1 && cnt[0]==2)re+=10;114 if(cnt[2]==2&&cnt[0]==1)re-=50;115 else if(cnt[2]==1 && cnt[0]==2)re-=10;116 mz(cnt);117 REP(j,3)cnt[bod.a[j][i]]++;118 if(cnt[1]==3)return 1000;119 if(cnt[2]==3)return -1000;120 if(cnt[1]==2&&cnt[0]==1)re+=50;121 else if(cnt[1]==1 && cnt[0]==2)re+=10;122 if(cnt[2]==2&&cnt[0]==1)re-=50;123 else if(cnt[2]==1 && cnt[0]==2)re-=10;124 }125 mz(cnt);126 REP(i,3) {127 cnt[bod.a[i][i]]++;128 }129 if(cnt[1]==3)return 1000;130 if(cnt[2]==3)return -1000;131 if(cnt[1]==2&&cnt[0]==1)re+=50;132 else if(cnt[1]==1 && cnt[0]==2)re+=10;133 if(cnt[2]==2&&cnt[0]==1)re-=50;134 else if(cnt[2]==1 && cnt[0]==2)re-=10;135 mz(cnt);136 REP(i,3) {137 cnt[bod.a[i][2-i]]++;138 }139 if(cnt[1]==3)return 1000;140 if(cnt[2]==3)return -1000;141 if(cnt[1]==2&&cnt[0]==1)re+=50;142 else if(cnt[1]==1 && cnt[0]==2)re+=10;143 if(cnt[2]==2&&cnt[0]==1)re-=50;144 else if(cnt[2]==1 && cnt[0]==2)re-=10;145 return re;146 }147 148 Board boa;149 150 inline int dfs(const int &depth, const int &nowWho) {151 int i,j,t,ma=-100000,mi=100000,ok=0;152 int eva = Evaluate(boa);153 if(depth==0 || (eva>=1000)|| (eva<=-1000)) {154 return eva;155 }156 157 REP(i,3) {158 REP(j,3) {159 if(boa.a[i][j]!=0)continue;160 ok=1;161 boa.a[i][j]=nowWho+1;162 t=dfs(depth-1 , nowWho^1);163 boa.a[i][j]=0;164 ma=max(t,ma);165 mi=min(t,mi);166 }167 }168 if(!ok)return eva;169 if(nowWho==0)return ma;170 if(nowWho==1)return mi;171 }172 173 void ComputerMove(Board &bod) {174 int x,y,i,j;175 boa=bod;176 puts("电脑：“该我啦！看我思考一下...”");177 vector > > v;178 v.clear();179 REP(i,3)REP(j,3) {180 if(boa.a[i][j]!=0)continue;181 boa.a[i][j]=2;182 v.pb(mp(dfs(9,0),mp(i,j)));183 boa.a[i][j]=0;184 }185 sort(v.begin(),v.end());186 j=1;187 while(j 1)printf("电脑：“想完啦！我有%d种不同的效果差不多的棋可以走，看我随便走一个！”\n",j);190 else printf("电脑：“想完啦！看我要走出这步惊天之棋了！”\n");191 if(v.size()>j && v[j].first==1000)puts("电脑：“要是我走除此之外的棋我就输了，我已经看出来了。”");192 if(v[0].first==-1000)puts("电脑：“现在，高下立判，你输定了！”");193 j=rand()%j;194 x=v[j].second.first;195 y=v[j].second.second;196 bod.a[x][y]=2;197 //OutBoard(bod);198 printf("电脑：“经过我的精确思考，我下到了(%d,%d)位置。”\n",x,y);199 puts("");200 }201 202 int WhoWin(Board bod) {203 int i,j,k=0;204 int t = Evaluate(bod);205 if(t==1000)return 1;206 if(t==-1000)return 2;207 REP(i,3)REP(j,3)if(bod.a[i][j]!=0)k++;208 if(k==9)return 3;209 return 0;210 }211 212 void Game() {213 int playerFirst, nowMove, whoWin, continueGame=1;214 Board now;215 int t;216 int step;217 srand(time(NULL));218 while(continueGame) {219 system("cls");220 puts("欢迎来到 【带鱼人工智能博弈树井字棋游戏】！");221 playerFirst = GetInput("请选择玩家先后手（0先手，1后手）：",2);222 if(playerFirst==0){223 puts("电脑：“就算你选先手，我也不会输，不信走着瞧！”");224 }else puts("电脑：“居然敢选后手，要是你稍有不慎，就输定了！”");225 now.Init();226 printf("（棋盘说明：%c是空位，%c是你的棋子，%c是电脑的棋子，上面是横坐标，左边是纵坐标）\n\n",CHESS[0],CHESS[1],CHESS[2]);227 nowMove=playerFirst;228 whoWin=0;229 step=0;230 while(!whoWin) {231 printf("【第%d手】\n",++step);232 if(nowMove==0) {233 PlayerMove(now);234 } else {235 ComputerMove(now);236 }237 whoWin=WhoWin(now);238 if(whoWin!=0) {239 OutBoard(now);240 if(whoWin==1) {241 printf("电脑：“哇，你居然赢了，真是不敢相信！我输了！”\n");242 }243 if(whoWin==2) {244 printf("电脑：“蛤铪哈！我赢了，你太弱啦！”\n");245 }246 if(whoWin==3) {247 printf("电脑：“平局！你还是有点实力，但是我是绝对不会输的！”\n");248 }249 }250 nowMove^=1;251 }252 continueGame=GetInput("是否继续游戏？（0结束游戏，1重新开始）：",2);253 }254 }255 256 int main() {257 Game();258 return 0;259 }
2017.1.20 update:
187行由
if(v.size()>1)while(v[j].first ==v[0].first)j++;
改为：
while(j
转载于:https://www.cnblogs.com/yuiffy/p/4235128.html
