1、人工智能三子棋业游戏报告解读数 学 与 计 算 机 科 学 学 院三子棋游戏设计报告 课程名称： 人工智能原理及其应用 年级专业： 11级计算机科学与技术* 杨 炎 设计时间： 2014年4月20 日 小组成员： 姓 名 学 号 韩 磊 136*8 张 雨 136*4 孟 帝 136*3第一章：三子棋游戏软件描述1.1 三子棋游戏简介 三子棋是一种人与机器对弈的小游戏，一方先下，轮流下棋，直到一方先将三个棋子连成一条线，就可以取胜。 1.2 软件功能介绍1井字棋游戏，也就是三子棋游戏。2棋盘大小为33，在方格内下棋，对弈双方轮流下棋。3只要有一方有3颗棋子连成一条线(行、列及对角线)，则该方获
2、胜，且游戏结束。4如果所有位置都已经下满棋子，且没有哪一方能赢棋，则是和棋。1.3 限制条件该程序必须在C+6.0环境中运行。模式选择时，不管输入何种值，只要不是要求的输入都是无效的。第二章： 软件功能描述1.用户进入游戏后选择2项其中之一:Y/N2.用户进入游戏开始界面后，玩游戏的人先下，然后电脑再下。3.用户进入游戏后，根据屏幕的棋图输入第几行第几列，每次输入一个值后，电脑也会对应输入值。4.当棋盘上出现-1和1填满棋盘时，电脑会判断那方胜利，或者判断是否是和棋，然后游戏结束。第三章： 三子棋游戏的分析 3.1 流程图如下：3.2 程序所用到的算法分析：1. 计算某个棋局状态中甲方是否已经
3、胜出算法：对矩阵的列，行，斜线求和。若和为3，则甲已经胜出，否则返回02.计算中某个棋局状态中甲方或乙方全占满的行，列，斜线数总和把矩阵中和为3的行数，列数，斜线数总和返回3.计算估价函数值算法：对某个棋局状态，首先把该棋局状态的空格塞满甲方的棋子，算出现在甲方棋子占满整行，整列，整斜线的总数。然后在原来的棋局状态的空格塞满乙方的棋子，算出乙方棋子占满整行，整列，整斜线的总数。然后求两者差。4.使用的-剪枝技术的基本思想或算法： 边生成博弈树边计算评估各节点的倒推值，并且根据评估值的倒推值的范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高
4、了搜索效益。第四章： 游戏程序#includeint num=0; /记录棋盘上棋子的个数int p,q; int tmpQP33; /表示棋盘数据的临时数组，其中的元素0表示该格为空，int cur33; /存储当前棋盘的状态const int depth=3; /搜索树的最大深度void Init() /初始化棋盘状态 for(int i=0;i3;i+) for(int j=0;j3;j+) curij=0; void PrintQP() /打印棋盘当前状态 for(int i=0;i3;i+) for(int j=0;j3;j+) coutcurijt; coutendl; void
5、UserInput()/用户通过此函数来输入落子的位置，比如：用户输入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 coutInput Error!; goto L1; int CheckWin() /检查是否有一方赢棋（返回 0：没有任何一方赢；1：计算机赢；-1：人赢） /该方法没有判断平局 for(int i=0;i3;i+) if(curi0=1&curi1=1&curi2=1) return 1; if(curi0=-
6、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=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()/评估当前棋盘状态的值（同时可以用p
7、或q判断是否平局） p=0; q=0; for(int i=0;i3;i+) /计算机一方 /将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1 for(int j=0;j3;j+) if(curij=0) tmpQPij=1; else tmpQPij=curij; for(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;/计算共有多少连
8、成3个1的对角线 p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(i=0;i3;i+) /人一方 /将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1 for(int j=0;j3;j+) if(curij=0) tmpQPij=-1; else tmpQPij=curij; for(i=0;i3;i+) /计算共有多少连成3个-1的行 q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(i=0;i3;i+) /计算共有多少连成3个-1的列 q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; q+=(tmpQP00+tmpQP11+
9、tmpQP22)/3;/计算共有多少连成3个-1的对角线 q+=(tmpQP20+tmpQP11+tmpQP02)/3; return p+q; /返回评估出的棋盘状态的值int cut(int &val,int dep,bool max)/主算法部分，实现a-B剪枝的算法，val为上一层的估计值，dep为搜索深度，max记录上一层是否为极大层 if(dep=depth|dep+num=9) /如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用估计函数 return value(); int i,j,flag,temp; /flag记录本层的极值，temp记录下层求得的估计
10、值 bool out=false; /out记录是否剪枝，初始为false /*if(CheckWin()=1) /如果计算机赢了，就置上一层的估计值为无穷（用很大的值代表无穷） val=10000; return 0; */ if(max) /如果上一层是极大层，本层则需要是极小层，记录flag为无穷大；反之，则为记录为负无穷大 flag=10000; /flag记录本层节点的极值 else flag=-10000; for(i=0;i3 & !out;i+) /双重循环，遍历棋盘所有位置 for(j=0;j3 & !out;j+) if(curij=0) /如果该位置上没有棋子 if(ma
11、x) /并且上一层为极大层，即本层为极小层,轮到用户玩家走了。 curij=-1; /该位置填上用户玩家棋子 if(CheckWin()=-1) /如果用户玩家赢了 temp=-10000; /置棋盘估计值为负无穷 else temp=cut(flag,dep+1,!max); /否则继续调用a-B剪枝函数 if(tempflag) /如果下一步棋盘的估计值小于本层节点的极值，则置本层极值为更小者 flag=temp; if(flagflag) flag=temp; if(flag=val) out=true; curij=0; /把模拟下的一步棋还原，回溯 if(max) /根据上一层是否为
12、极大层，用本层的极值修改上一层的估计值 if(flagval) val=flag; else if(flagval) val=flag; return flag; /函数返回的是本层的极值int main()/主程序 int m=-10000,val=-10000,dep=1; /m用来存放最大的val int x_pos,y_pos; /记录最佳走步的坐标 Init(); coutQipan: endl; PrintQP(); char IsFirst; coutIsFirst; while(IsFirst!=y&IsFirst!=n) coutERROR!IsFirst; if(IsFir
13、st=n)/-计算机先走- L5: for(int x=0;x3;x+) for(int y=0;y3;y+) if(curxy=0) curxy=1; cut(val,dep,1);/计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为dep-1的棋盘状态估计值val if(CheckWin()=1) coutThe computer put the qizi at:x+1y+1endl; PrintQP(); coutThe computer WIN! GAME OVER.m) /m要记录通过试探求得的棋盘状态的最大估计值 m=val; x_pos=x;y_pos=y; val=-
14、10000; curxy=0; curx_posy_pos=1; val=-10000; m=-10000; dep=1; coutThe computer put the qizi at:x_pos+1y_pos+1endl; PrintQP(); 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
15、) 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) coutYou Win! GAME OVER.endl; return 0; for(int x=0;x3;x+) for(int y=0;y3;y+) if(curxy=0) curxy=1; cut(val,dep,1
16、); if(CheckWin()=1) coutThe computer put the qizi at:x+1y+1endl; PrintQP(); coutThe computer WIN! GAME OVER.m) 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; PrintQP(); coutendl; num+; value(); if(q=0) c
17、outDOWN GAME!endl; return 0; goto L4; return 0;第五章：程序运行图5.1 是否开始游戏进行选择。5.2 先下一方下棋5.3 判断胜利一方5.4 判断和棋 读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟。3、读书破万卷，下笔如有神。4、我所学到的任何有价值的知识都是由自学中得来的。达尔文5、少壮不努力，老大徒悲伤。6、黑发不知勤学早，白首方悔读书迟。颜真卿7、宝剑锋从磨砺出，梅花香自苦寒来。8、读书要三到：心到、眼到、口到9、玉不琢、不成器，人不学、不知义。10、一日无书，百事荒废。陈寿11、书是人类进步的阶梯。12、一日不读口生，一日不写手生。13、我扑在书上，就像饥饿的人扑在面包上。高尔基14、书到用时方恨少、事非经过不知难。陆游15、读一本好书，就如同和一个高尚的人在交谈歌德16、读一切好书，就是和许多高尚的人谈话。笛卡儿17、学习永远不晚。高尔基18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。刘向19、学而不思则惘，思而不学则殆。孔子20、读书给人以快乐、给人以光彩、给人以才干。培根
