五子棋程序设计.doc

高级语言程序设计课程设计五子棋对战算法设计与实现题 目：班 级：* 学生姓名： *学生学号： *指导老师：*提交时间：2007年11月11日成 绩：华南农业大学 信息学院：一、设计题目分析1. （1）设计题目描述在一个15*15的棋盘上，进行五子棋的对战，不同的是这一次要求由程序代替你战斗。（2）系统设计目的根据系统提供的对战信息，通过计算给出合理的下一步落子的位置。（3）输入、输出数据格式输入格式的第一行为一个整数N，表示当前已下的子数，此后N行，每行一个落子的位置（第一个落子为黑子、第二个落子为白子、依次类推），位置由x,y表示（分别为落子的行坐标、列坐标，取值范围为014）输出格式为一坐标x,y，表示经过计算得出的下一落子位置。（注意，不必标明落黑子还是白子，因为落黑子还是白子从当前已下的子数即可判断）例如（输入数据）67,76,66,75,77,55,6右图为输入数据所描述的棋局。例如（输出数据）7,6在（7，6）位置落子后，如右图所示。（4）设计时的注意事项落子必须在棋盘有效范围内，已经落子的位置不能落子。程序对先手黑棋或后手白棋均能计算正确的落子。2.胜负判断根据最后落子情况从水平、垂直、左斜、右斜四个方向检查是否存在五个连续棋子即可。3.个人分析如何将五子棋量化是本题目的关键，这就需要引入打分。而关键在于如何打分，如冲四，活三，眠三等分别要打多少分，再综合起来考虑。求出最高分，再根据其给出下一步落子的位置。而除了打分，如果能引进预测以及存储可使程序的智能性大大提高。（而此次由于时间关系，并未作出这两个函数。）二、总体设计包括：总体设计思想：本次主要采用数组储存主要数组five1515,my1515,table15158,his1515五子棋智能化的关键在于如何打分，如眠三，冲四，死三活三等分别分值为多少，再综合起来考虑。求出最高分，再根据其给出下一步落子的位置。程序模块结构图：主函数void main() 函数Score();打分函数函数void search_space()寻找空格函数比较分数高低，输出最高分所对应的值流程图：将各个空格的分数加以比较，得出最高分，将我方的分数与对方的分数加以比较，如果我方最高分数sc1等于或大于对方分数sc2，则选择我方分数sc1，否则选择对方分数sc2。将四个方向的分数相加，得出该空格的分数whoseijbounds4组合成各种不同情况，而八个方向又可以合成四个方向，再根据这四个方向再打分。（这些下面都有图及文字加以解释）k=0-7代表从左方顺时针的八个方向，用bounds4来记录空格该方向上相邻四个位置的情况，其中black 1，white -1，empty 0，边界为-2，search_space(i,j,k,f,who,table)Y N该格是否为空格当k8当j15当i15i=0,j=0,k=0score(five,table,my,Iam)输入x，y当i 4 3（1） 3（3） 2（2） 2（3） 1 2（1） 5(1) 4 5(1) 3（2） 3（4） 2（3） 3（1）根据优先级再进行打分。以开头的分数都在10分以上，以开头的分数在1-6分。1502（1）432（2）392（3）31 / 63（1）27 / 53（2）43（3）173（4）3411 / 25（1）150而分数的合成为成五： if(temp=50) pkk=1000;成活四： else if(temp=44) pkk=100;成眠四，活三：else if(temp=32) pkk=20;空间不足五子：else if(temp=22) pkk=0;成眠三，活二：else if(temp=14) pkk=4;成眠二，活一：else if(temp=12) pkk=1;其他： else pkk=0;（3）函数设计：函数Score();打分函数void search_space()寻找空格函数比较分数高低，输出最高分所对应的值三、详细设计主要函数：函数Score();打分函数Void search_space()寻找空格函数比较分数高低，输出最高分所对应的值主要程序清单：#include #include#include#include#define black 1#define white -1#define empty 0void search_space(int i,int j,int t,int five1515,int Iam,int table15158)/寻找空白模块int i2=i,j2=j,k2,bounds4=-2,-2,-2,-2,Heis=-Iam;/将边界定义为2，用bounds4来储存空格该方向上四子的情况if(t=0)j2+;for(k2=0;k24&j215;k2+,j2+) boundsk2=fivei2j2;/左方else if(t=1)j2+,i2+;for(k2=0;k24&i215&j215;k2+,j2+,i2+) boundsk2=fivei2j2;/左上方else if(t=2)i2+;for(k2=0;k24&j215;k2+,i2+) boundsk2=fivei2j2;/上方else if(t=3)j2-,i2+;for(k2=0;k2=0;k2+,j2-,i2+) boundsk2=fivei2j2;/右上方else if(t=4)j2-;for(k2=0;k2=0;k2+,j2-) boundsk2=fivei2j2;/右方else if(t=5)j2-,i2-;for(k2=0;k2=0&i2=0;k2+,j2-,i2-) boundsk2=fivei2j2;/右下方else if(t=6)i2-;for(k2=0;k2=0;k2+,i2-) boundsk2=fivei2j2;/下方else if(t=7)j2+,i2-;for(k2=0;k2=0&j215;k2+,j2+,i2-) boundsk2=fivei2j2;/左下方if(bounds0=Heis|bounds0=-2) tableijt=0;else if(bounds0=Iam)if(bounds1=Heis|bounds1=-2) tableijt=11;else if(bounds1=Iam)if(bounds2=Heis|bounds2=-2) tableijt=27;else if(bounds2=Iam)if(bounds3=Heis|bounds3=-2) tableijt=39;else if(bounds3=Iam) tableijt=50;else if(bounds3=empty) tableijt=44;else if(bounds2=empty) tableijt=31;else if(bounds1=empty) tableijt=17;else if(bounds0=empty)if(bounds1=empty|bounds1=Heis|bounds1=-2) tableijt=1;else if(bounds1=Iam)if(bounds2=Heis|bounds2=-2) tableijt=2;if(bounds2=empty) tableijt=3;else if(bounds2=Iam)if(bounds3=Heis|bounds3=-2) tableijt=4;else if(bounds3=Iam) tableijt=6;else if(bounds3=empty) tableijt=5; void score(int f1515,int table15158,int whose1515,int who)int i,j,k,temp,pk4;for(i=0;i15;i+)for(j=0;j15;j+)if(fij=0)for(k=0;k8;k+)search_space(i,j,k,f,who,table); /对八个方向进行初步打分for(k=0;k=50) pkk=1000;else if(temp=45) pkk=100;else if(temp=32) pkk=20;else if(temp=22) pkk=0;else if(temp=14) pkk=4;else if(temp=12) pkk=1;else pkk=0; temp=pk0+pk1+pk2+pk3;/将四个方向的分数相加，即为该空格的分数 whoseij=temp;void main()int n,i,j,i1,j1,i2,j2,i3,j3,i4,j4,x=0,y=0,Iam,Heis,sc1=0,sc2=0,k=0,k1,l=0,l1,t=0;int five1515=0,my1515=0,table15158=0,his1515=0,temp12252=0,temp22252=0;scanf(%d,&n);if(n%2=0)Iam=black;Heis=white;if(n%2=1)Iam=white;Heis=black;if(n=0)printf(7,7n);/如果第一步我下就下7，7elsefor(i=0;in;i+)scanf(%d,%d,&x,&y);if(i%2=0) fivexy=black;else fivexy=white;score(five,table,my,Iam);/我方的打分，即进攻打分，比较出最高分for(i=0;i15;i+)for(j=0;j15;j+)if (sc1=myij)sc1=myij;i1=i;j1=j;score(five,table,his,Heis);/对方的打分，即防守打分，比较出最高分for(i=0;i15;i+)for(j=0;j15;j+)if (sc2=hisij)sc2=hisij;i2=i;j2=j; for(i=0;i15;i+)/用temp12252记录进攻最高分的几个点for(j=0;j15;j+)if (myij=sc1)temp1k0=i;temp1k1=j;+k;k1=k;time_t tt;srand(unsigned) time(&tt);/随机抽取一个最高分的点k=rand()%k1;i1=temp1k0;j3=temp1k1;for(i=0;i15;i+)/用temp22252记录防守最高分的几个点for(j=0;j=sc2)printf(%d,%dn,i1,j1);else printf(%d,%dn,i2,j2);四、总结一开始完全没有头绪，如何将五子棋实际量化，自己根本想不出来。只能依据它的规则思考可能形成的格局。而后来自己在网上找了一些资料参考，才知道打分是关键。而究竟如何打分，就是主要靠个人的判断了。而后自己开始写程序。从一开始用一个1515的函数来记载棋盘信息，到后来自己分出三个模块。分别是记载模块，打分模块，还有对空白的寻找模块。而遇到的问题实在不少：如依据什么搜索，一开始自己试过用子搜索，在某一个子的旁边搜索旁边的情形，而后来发现这样判断比较难，而且效率不高，就改用了用空格搜索，在某一个空格那里寻找周围的情况。而后又考虑是否要在开头的时候，将循环次数减少，但实际操作中时间耗费很小，所以不是很有意义，因此也就删除了这个函数。看别人程序的时候，发现没有注释确实很难懂，明白了注释的重要性，以及程序的结构化的好处，如果乱写一通，最后只能是谁也不懂的程序。而即使是有注释，如果自己不将其运算一遍，也很难懂得其中的道理，通过运算程序来理解程序，这是一个老师的忠告，现在终于懂得这点。不断的改进，在得出最高分数时自己本来做了一个改进，即假如我方的最高分数比对方最高分数高，则在那几个最高分数的点再进行第二次搜索，比较在这几个点（我方分数最高的几个点）对方的最高分数，下在那个位置。