人工智能井字棋

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

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

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

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

5、面：F值。判断算出的 F值是否比前一次的在，如果是记llo,lieIcome to tliis garnet?*Do pou want to play f iFst?j,Please enter the position cu UAntTnt«p nun Q to exit（2）用户赢时:K； ：0K；OSx;osx ConsfrstLilationi!irou win!（4） 当机器赢时:0：M IXp： ：OSoppy* tyou lose T（5） 当机器先下时，机器先下第五格，用户下第八格后，机器下第一格。这些都与预期 相符。!X；antinue七、实验心得：通过这次我对极大

6、极小算法和a- B剪枝有了更深的理解。在设计井字棋的过程中，发现了设计这个程序必须不能照搬书上的算法，而是应该根据实际情况来计算评价值。最后感谢梁云老师为我提供这一次的实验让我们学会了很多的东西。八、附源代码：#in clude<stdio.h>#in clude<ct yp e.h>#in clude<c oni o.h>/*引入头文件*/#defi ne MAX 1000/*定义最大值为1000 */#define MIN -1000#define NONE 0#define DRAW 1#define C_WIN 2 #define M_WIN 3 #

7、define QUIT 4 #define MAN -1 #define COM 1 #define TRUE 1/* 最小值为 -1000 */ 如果搜索不到结果，结果 NONE 定义平局 DRAW 为 1 */ 电脑赢为 2 人赢为 3/* /*/*/*/* 放弃为 4 人用 -1 表示 电脑用 1 表示/*/*/*/*/*/*/*/* 定义 b10 用来存储棋盘( ，r 表示结果，初始值为NONE ；w 表示可以赢的位置int b10=0,step=9,r=NONE,w=0;/* checkWin 函数用来判断胜负，如果有胜负，返回胜方，否则返回 int checkWin(int t,

8、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=t4 && t4=t7) return(p);if (t2=p && t2=t5 && t5=t8) return(p);if (t3=p && t3=t

9、6 && 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 函数，搜索计算机和人可以羸的机会，用来计算评价值， int search(int t)int f=0,k=0; k=checkWin(t,MAN); if(k=MAN) return MIN;board), step表示可以下的步数/* 先判断人是否可以羸 */ /* 如果可

10、以返回一个最小值 */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 && t4>=0 && t7>=0) f+;if (t2>=0 && t5>=0 && t8>=0) f+;if (

11、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<=0 && t3<=0) f-;if (t4<=0 && t5<=0 && t6<=0) f-;if (t7<=0 &

12、& 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 && t9<=0) f-;if (t1<=0 && t5<=0 && t9<=0) f-;if (t3<=0 && t5<=0

13、&& t7<=0) f-;return f;/* 计算评价值，并返回评价值*/*/NONE */*/并返回成线的位置 */* 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) ti=0; k=i;w+; ti=0;return k;*/*display 函数用来显示棋盘，并显示结果void display(int type) char dis10="" i

14、nt 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,dis6); printf("n");printf("Sorry!you lose!"); printf("Congratulation!you win!"

15、) ; printf("You has just quited the game!");printf("%c|%c|%cn",dis7,dis8,dis9); if(type=NONE) printf("continue!"); if(type=DRAW) printf("the game is draw!"); if(type=C_WIN) if(type=M_WIN) if(type=QUIT)man 函数 */* 人下的时候执行int man()int c;*/* 提示信息printf("nPlea

16、se 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')r=QUIT;return;/* 下在用户输入的位置 ，步数减 1 */ step-;bc-48=MAN;*/* 如果步数为 0，结果设为平局if(step=0) r=DRAW;/* 人赢了，结果为 M_WIN */ if

17、(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;step-;return; /* 如果人可以赢，也下在相应的位置 */ flag=checkWinning(MAN,b);if(flag<10) bflag=COM;step-;return;/* 用 t 暂时存储棋盘 for(i=

18、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=search(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=CO