人工智能三子棋业游戏报告(共18页)

1、 数 学 与 计 算 机 科 学 学 院三子棋游戏(yux)设计(shj)报告 课程名称： 人工智能(rn n zh nn)原理及其应用 年级专业： 11级计算机科学与技术 任课教师： 杨 炎 设计时间： 2014年4月20 日 小组成员： 姓 名 学 号 韩 磊 136263010068 张 雨 136263010064 孟 帝 136263010073目录(ml) TOC o 1-3 h z u HYPERLINK l _Toc385967096 第一章：三子棋游戏软件描述(mio sh) PAGEREF _Toc385967096 h 3 HYPERLINK l _Toc38596709

2、7 1.1 三子棋游戏(yux)简介 PAGEREF _Toc385967097 h 3 HYPERLINK l _Toc385967098 1.2 软件功能介绍 PAGEREF _Toc385967098 h 3 HYPERLINK l _Toc385967099 1.3 限制条件 PAGEREF _Toc385967099 h 3 HYPERLINK l _Toc385967100 第二章：软件功能描述 PAGEREF _Toc385967100 h 3 HYPERLINK l _Toc385967101 第三章：三子棋游戏的分析 PAGEREF _Toc385967101 h 4 HYP

3、ERLINK l _Toc385967102 3.1 流程图如下： PAGEREF _Toc385967102 h 4 HYPERLINK l _Toc385967103 3.2 程序所用到的算法分析： PAGEREF _Toc385967103 h 5 HYPERLINK l _Toc385967104 第四章：游戏程序 PAGEREF _Toc385967104 h 5 HYPERLINK l _Toc385967105 第五章：程序运行图 PAGEREF _Toc385967105 h 19 HYPERLINK l _Toc385967106 5.1 是否开始游戏进行选择。 PAGERE

4、F _Toc385967106 h 19 HYPERLINK l _Toc385967107 5.2 先下一方下棋 PAGEREF _Toc385967107 h 19 HYPERLINK l _Toc385967108 5.3 判断胜利一方 PAGEREF _Toc385967108 h 19 HYPERLINK l _Toc385967109 5.4 判断和棋 PAGEREF _Toc385967109 h 19第一章：三子棋游戏软件描述(mio sh)1.1 三子棋游戏(yux)简介 三子棋是一种人与机器对弈的小游戏，一方先下，轮流下棋(xi q)，直到一方先将三个棋子连成一条线，就可以

5、取胜。 1.2 软件功能介绍井字棋游戏，也就是三子棋游戏。棋盘大小为33，在方格内下棋，对弈双方轮流下棋。只要有一方有3颗棋子连成一条线(行、列及对角线)，则该方获胜，且游戏结束。如果所有位置都已经下满棋子，且没有哪一方能赢棋，则是和棋。1.3 限制条件该程序必须在C+6.0环境中运行。模式选择时，不管输入何种值，只要不是要求的输入都是无效的。第二章： 软件功能描述用户进入游戏后选择2项其中之一:Y/N用户进入游戏开始界面后，玩游戏的人先下，然后电脑再下。用户(yngh)进入游戏后，根据屏幕的棋图输入第几行第几列，每次输入一个值后，电脑也会对应输入值。当棋盘上出现-1和1填满棋盘时，电脑会判断

6、那方胜利，或者判断是否是和棋，然后游戏(yux)结束。第三章： 三子棋游戏(yux)的分析 游戏界面关闭游戏退出游戏是否进行新游戏判断和棋判断输赢进行对弈人机对战游戏模式开 始3.1 流程图如下：3.2 程序所用到的算法(sun f)分析：1. 计算某个棋局状态中甲方是否已经(y jing)胜出算法：对矩阵(j zhn)的列，行，斜线求和。若和为3，则甲已经胜出，否则返回02.计算中某个棋局状态中甲方或乙方全占满的行，列，斜线数总和把矩阵中和为3的行数，列数，斜线数总和返回3.计算估价函数值算法：对某个棋局状态，首先把该棋局状态的空格塞满甲方的棋子，算出现在甲方棋子占满整行，整列，整斜线的总数

7、。然后在原来的棋局状态的空格塞满乙方的棋子，算出乙方棋子占满整行，整列，整斜线的总数。然后求两者差。4.使用的-剪枝技术的基本思想或算法： 边生成博弈树边计算评估各节点的倒推值，并且根据评估值的倒推值的范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效益。第四章： 游戏程序#includeint num=0; /记录棋盘上棋子的个数int p,q; int tmpQP33; /表示棋盘数据的临时数组，其中的元素0表示该格为空，int cur33; /存储当前棋盘的状态const int depth=3; /搜索树的最大深度void

8、Init() /初始化棋盘(qpn)状态 for(int i=0;i3;i+)for(int j=0;j3;j+)curij=0;void PrintQP() /打印(d yn)棋盘当前状态for(int i=0;i3;i+)for(int j=0;j3;j+)coutcurijt;coutendl; void UserInput()/用户通过(tnggu)此函数来输入落子的位置，比如：用户输入31，则表示用户在第3行第1列落子。int pos,x,y;L1: coutpos;x=pos/10,y=pos%10;if(x0&x0&y4&curx-1y-1=0)curx-1y-1=-1;else

9、coutInput Error!;goto L1;int CheckWin() /检查是否有一方(y fn)赢棋（返回 0：没有任何一方赢；1：计算机赢；-1：人赢） /该方法(fngf)没有判断平局for(int i=0;i3;i+)if(curi0=1&curi1=1&curi2=1)return 1;if(curi0=-1&curi1=-1&curi2=-1)return -1;for(i=0;i3;i+)if(cur0i=1&cur1i=1&cur2i=1)return 1;if(cur0i=-1&cur1i=-1&cur2i=-1)return -1;if(cur00=1&cur11

10、=1&cur22=1)|(cur20=1&cur11=1&cur02=1)return 1;if(cur00=-1&cur11=-1&cur22=-1)|(cur20=-1&cur11=-1&cur02=-1)return -1;return 0;int value()/评估当前棋盘状态的值（同时可以(ky)用p或q判断是否平局）p=0;q=0;for(int i=0;i3;i+) /计算机一方(y fn) /将棋盘中的空格(kn )填满自己的棋子，既将棋盘数组中的0变为1for(int j=0;j3;j+)if(curij=0)tmpQPij=1;elsetmpQPij=curij; for

11、(i=0;i3;i+) /计算共有多少连成3个1的行p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(i=0;i3;i+) /计算共有多少连成3个1的列p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;p+=(tmpQP00+tmpQP11+tmpQP22)/3;/计算共有多少连成3个1的对角线p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(i=0;i3;i+) /人一方 /将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1for(int j=0;j3;j+)if(curij=0)tmpQPij=-1;elsetmpQPij=cur

12、ij;for(i=0;i3;i+) /计算(j sun)共有多少连成3个-1的行q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(i=0;i3;i+) /计算(j sun)共有多少连成3个-1的列q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;q+=(tmpQP00+tmpQP11+tmpQP22)/3;/计算(j sun)共有多少连成3个-1的对角线q+=(tmpQP20+tmpQP11+tmpQP02)/3;return p+q; /返回评估出的棋盘状态的值int cut(int &val,int dep,bool max)/主算法部分，实现a-B剪枝的算

13、法，val为上一层的估计值，dep为搜索深度，max记录上一层是否为极大层 if(dep=depth|dep+num=9) /如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用估计函数 return value(); int i,j,flag,temp; /flag记录本层的极值，temp记录下层求得的估计值 bool out=false; /out记录是否剪枝，初始为false /*if(CheckWin()=1) /如果计算机赢了，就置上一层的估计值为无穷（用很大的值代表无穷） val=10000; return 0; */ if(max) /如果(rgu)上一层是极大

14、层，本层则需要是极小层，记录flag为无穷大；反之，则为记录为负无穷大flag=10000; /flag记录本层节点(ji din)的极值 else flag=-10000; for(i=0;i3 & !out;i+) /双重循环，遍历棋盘(qpn)所有位置 for(j=0;j3 & !out;j+) if(curij=0) /如果该位置上没有棋子 if(max) /并且上一层为极大层，即本层为极小层,轮到用户玩家走了。 curij=-1; /该位置填上用户玩家棋子 if(CheckWin()=-1) /如果用户玩家赢了temp=-10000; /置棋盘估计值为负无穷 else temp=cu

15、t(flag,dep+1,!max); /否则继续调用a-B剪枝函数 if(tempflag) /如果下一步棋盘的估计值小于本层节点的极值，则置本层极值为更小者 flag=temp; if(flagflag) flag=temp; if(flag=val) out=true; curij=0; /把模拟下的一步棋还原，回溯 if(max) /根据上一层是否为极大层，用本层的极值修改上一层的估计值 if(flagval) val=flag; else if(flagval) val=flag; return flag; /函数返回(fnhu)的是本层的极值int main()/主程序int m=

16、-10000,val=-10000,dep=1; /m用来(yn li)存放最大的valint x_pos,y_pos; /记录(jl)最佳走步的坐标Init();coutQipan: endl;PrintQP();char IsFirst;coutIsFirst;while(IsFirst!=y&IsFirst!=n)coutERROR!IsFirst;if(IsFirst=n)/计算机先走L5:for(int x=0;x3;x+)for(int y=0;y3;y+)if(curxy=0)curxy=1;cut(val,dep,1);/计算机试探的走一步棋，棋盘状态(zhungti)改变了，

17、在该状态下计算出深度为dep-1的棋盘状态估计值valif(CheckWin()=1)coutThe computer put the qizi at:x+1y+1endl;PrintQP();coutThe computer WIN! GAME OVER.m) /m要记录通过试探(shtn)求得的棋盘状态的最大估计值m=val;x_pos=x;y_pos=y;val=-10000;curxy=0;curx_posy_pos=1;val=-10000;m=-10000;dep=1;coutThe computer put the qizi at:x_pos+1y_pos+1endl;Print

18、QP();coutendl;num+;value();if(p=0)coutDOWN GAME!endl;return 0;UserInput(); /玩家走一步棋PrintQP(); coutendl;num+;value();if(p=0)coutDOWN GAME!endl;return 0;if(CheckWin()=-1)coutConguatulations! You Win! GAME OVER.endl;return 0;goto L5;else /人先走 L4:UserInput(); PrintQP();coutendl;num+;value();if(q=0)coutDOWN GAME!endl;return 0;if (CheckWin()=-1)c