人工智能井字棋

1、实验报告课程名称：人工智能实验名称：井字棋学院:专业班级：学生姓名： 学号： 一、实验目的：（1） 了解极大极小算法的原理和使用方法，并学会用-剪枝来提高算法的效率。（2） 使用C语言平台，编写一个智能井字棋游戏。（3） 结合极大极小算法的使用方法和-剪枝，让机器与人对弈时不但有智能的特征，而且计算的效率也比较高。二、设计思想：井字棋是一个流传已久的传统游戏。游戏由两个人轮流来下，分别用“X”和“O”来代替自身的棋子。棋盘分9个格，双方可以在轮到自己下的时候，可以用棋子占领其中一个空的格子。如果双方中有一方的棋子可以连成一条直线，则这一方判胜，对方判负。当所有的格子都被占领，但双方都无法使棋子

2、连成一条直线的话，则判和棋。这是一个智能型的井字棋游戏，机器可以模拟人与用户对弈。当轮到机器来下的时候，机器会根据当前棋局的形势，利用极大极小算法算出一个评价值，判断如何下才对自身最有利，同时也是对方来说对不利的，然后下在评价值最高的地方。另外利用-剪枝，使机器在搜索评价值的时候不用扩展不必要的结点，从而提高机器计算的效率。在用户界面方法，用一个3×3的井字格来显示用户与机器下的结果。当要求用户输入数据的时候会有提示信息。用户在下的过程中可以中途按下“0”退出。当用户与计算机分出了胜负后，机器会显示出比赛的结果，并按任意键退出。如果用户在下棋的过程中，输入的是非法字符，机器不会做出反

3、应。三、程序主要流程四、程序中的主要伪代码：（1）主函数部分：（一）打印出欢迎信息，提示用户输入是否先下，如果用户选择先下，跳到第二步，否则，跳到第三步。（二）调用man()。（三）调用com()，判断棋局是否分出胜负。判断是否分出了胜负，是的话跳到第五步。（四）调用man()，判断棋局是否分出胜负。判断是否分出胜负，是的话跳到第五步。否则跳到第三步。（五）打印棋盘和比赛结果，退出程序。（2）Man()函数部分（一）、让用户选择要下的位置，判断用户下完是否已经取胜。否是则跳到第三步。（二）、结果置为用户赢（三）、可以下的步数减1，退出函数。（3）com()函数部分（一）、判断机器是否可以赢了，

4、如果是将棋子下在可以赢的位置，rs=C_WIN,并退出程序。判断用户是否可以赢了，如果是将棋子下在用户可以赢的位置，并退出函数。（二）、I=1（三）、检查I是否小于10.（四）、检查第I格是否为空，否则I+，重复第三步。（五）、试下第I格，先检查下完第I格后，用户是否再一步可能赢，如果是只算出用户将会赢的那一步的评价值f，（因为如果没有阻止用户赢的话，F值都是MAX，所以不用计算）。否则，算出所有用户可能下的格局的F值。判断算出的F值是否比前一次的在，如果是记录这一次的位置和F值。I+,step-,回到第三步。（六）、根据最大的F值和相应的I值，决定要下的位置。（七）、退出程序。六、调试结果：

5、（1）欢迎界面：（2）用户赢时：（4） 当机器赢时：（5） 当机器先下时，机器先下第五格，用户下第八格后，机器下第一格。这些都与预期相符。七、实验心得：通过这次我对极大极小算法和-剪枝有了更深的理解。在设计井字棋的过程中，发现了设计这个程序必须不能照搬书上的算法，而是应该根据实际情况来计算评价值。 最后感谢梁云老师为我提供这一次的实验让我们学会了很多的东西。八、附源代码：#include<stdio.h> /* 引入头文件 */#include<ctype.h> #include<conio.h> #define MAX 1000 /* 定义最大值为1000

6、 */#define MIN -1000 /* 最小值为-1000 */#define NONE 0 /* 如果搜索不到结果，结果NONE */#define DRAW 1 /* 定义平局DRAW为1 */#define C_WIN 2 /* 电脑赢为2 */#define M_WIN 3 /* 人赢为3 */#define QUIT 4 /* 放弃为4 */#define MAN -1 /* 人用-1表示 */#define COM 1 /* 电脑用1表示 */#define TRUE 1 /* 定义b10用来存储棋盘（board） , step表示可以下的步数 ，r表示结果，初始值为NON

7、E；w表示可以赢的位置 */int b10=0,step=9,r=NONE,w=0; /* checkWin函数用来判断胜负，如果有胜负，返回胜方，否则返回NONE */ int checkWin(int t, int p) if (t1=p && t1=t2 && t2=t3) return(p); if (t4=p && t4=t5 && t5=t6) return(p); if (t7=p && t7=t8 && t8=t9) return(p); if (t1=p && t1

8、=t4 && t4=t7) return(p); if (t2=p && t2=t5 && t5=t8) return(p); if (t3=p && t3=t6 && t6=t9) return(p); if (t1=p && t1=t5 && t5=t9) return(p); if (t3=p && t3=t5 && t5=t7) return(p); return(NONE);/* search函数，搜索计算机和人可以羸的机会，用来计算评价值，

9、*/int search(int t) int f=0,k=0; k=checkWin(t,MAN); /* 先判断人是否可以羸 */ if(k=MAN) return MIN; /* 如果可以返回一个最小值 */ if (t1>=0 && t2>=0 && t3>=0) f+; if (t4>=0 && t5>=0 && t6>=0) f+; if (t7>=0 && t8>=0 && t9>=0) f+; if (t1>=0 &

10、& t4>=0 && t7>=0) f+; if (t2>=0 && t5>=0 && t8>=0) f+; if (t3>=0 && t6>=0 && t9>=0) f+; if (t1>=0 && t5>=0 && t9>=0) f+; if (t3>=0 && t5>=0 && t7>=0) f+; if (t1<=0 && t2&l

11、t;=0 && t3<=0) f-; if (t4<=0 && t5<=0 && t6<=0) f-; if (t7<=0 && t8<=0 && t9<=0) f-; if (t1<=0 && t4<=0 && t7<=0) f-; if (t2<=0 && t5<=0 && t8<=0) f-; if (t3<=0 && t6<=0 &

12、& t9<=0) f-; if (t1<=0 && t5<=0 && t9<=0) f-; if (t3<=0 && t5<=0 && t7<=0) f-; return f; /* 计算评价值，并返回评价值 */* checkWinning函数用来搜索是否已经有两子成线， 并返回成线的位置*/int checkWinning(int p,int t) int i,k=10; for(i=1;i<10;i+) if(ti=0) ti=p; if(checkWin(t,p)=p

13、) ti=0; k=i; w+; ti=0; return k;/*display函数用来显示棋盘，并显示结果*/void display(int type) char dis10="" int i; for(i=1;i<10;i+) if(bi<0) disi='X' if(bi>0) disi='O' printf("n%c|%c|%cn",dis1,dis2,dis3); printf("-n"); printf("%c|%c|%cn",dis4,dis5,d

14、is6); printf("-n"); printf("%c|%c|%cn",dis7,dis8,dis9); if(type=NONE) printf("continue!"); if(type=DRAW) printf("the game is draw!"); if(type=C_WIN) printf("Sorry!you lose!"); if(type=M_WIN) printf("Congratulation!you win!") ; if(type=QUIT)

15、 printf("You has just quited the game!");/* 人下的时候执行man函数 */int man() int c; /* 提示信息 */ printf("nPlease enter the position you want!enter num 0 to exitn"); for (c=getche(); ; printf("n"), c=getche() ) if (isdigit(c) && bc-48=0) /* 如果用户输入的是“0”就结束程序 */if(c='0&#

16、39;)r=QUIT;return;/* 下在用户输入的位置 ，步数减1 */step-;bc-48=MAN;/* 如果步数为0，结果设为平局 */if(step=0) r=DRAW;/* 人赢了，结果为M_WIN */if(checkWin(b,MAN)=MAN)r=M_WIN;return; int com() int i,j,t10; int temp,max=MIN-1,f=0,best=1,k,flag; clrscr(); /* 如果电脑可以赢下在该位置 */ flag=checkWinning(COM,b); if(flag<10) bflag=COM;r=C_WIN;st

17、ep-;return; /* 如果人可以赢，也下在相应的位置 */ flag=checkWinning(MAN,b); if(flag<10) bflag=COM;step-;return; /* 用t暂时存储棋盘 */ for(i=1;i<10;i+) ti=bi; for(i=1;i<10;i+) if(ti=0) ti=COM; f=MAX; k=checkWinning(COM,t); /*如果搜索到下了第i格后人可以赢*/ /*就对算法进行剪支，只返回k位置的评价值 */ for(j=1;j<10;j+) if(k<10) tk=MAN; f=searc

18、h(t); tk=0; break; /* 否则算出每个生成的结点的评价值 */ if(tj=0) tj=MAN; temp=search(t); if(temp<f) /* 每次都返回最小评价值给最大层 */ f=temp; tj=0; if(f=MIN) break; ti=0; if(f>max) /* 在最大层中选择最大的评价值 */ best=i; max=f; bbest=COM; /* 并下在最大层中评价值最大的位置*/ step-; if(step=0) r=DRAW;main() char c; int i; clrscr(); for(i=0;i<30;i+) printf("*"); printf("n*hello,welcome to this game!*n"); for(i=0;i<30;i+) printf("*"); printf("nDo you want to play first?"); for (c=getche(); c!='Y'&&c!='y'&&c!='