C++实现黑白棋.doc

黑白棋规则介绍黑白棋是由黑方和白方两人进行的益智游戏。棋盘为NN方格，黑白棋总共使用N2个棋子，每个棋子分正反两面，分别是黑色和白色。轮到一方下棋时，必须把棋下在与对方棋子相邻的空位上，要求所下的棋子和原有的已方棋子夹住对方的至少一个棋子(横竖斜夹均可)，然后把被夹住的子变成己方的颜色(也叫吃子)。下棋过程中，任何棋子既不会从棋盘上拿走，也不会从一个格子移到另一个格子,吃子时，不会发生连锁反应，吃进的棋子不能再夹吃其他的子。当双方都无棋可下，或者方格全部占满后，棋局结束，子多的一方为胜方。黑白棋人工智能的实现我们这里取棋盘大小为1010个方格，用数组int state1010来表示棋盘的状态，其中0表示方格为空，1表示用黑方的棋，1表示白方的棋。在1010的棋盘上，除了那些已经有子的地方不能走子外，那些不能吃子的点也不能走。如何判断某个点（x, y）能不能走子呢？通过分析黑白棋的规则我们知道，在这一个方格上的八个方向的任何一个方向上只要满足：在这个方向与之相邻的有连续若干个对方的棋子，接着有一个己方的子，我们就可以肯定这一点能够走子。所以我定义了一个数组int dirstate8（数组从右逆时针开始，如dirstate0表示右，dirstate1表示右上，以此类推）来表示个方向的状态,值1表示在这个方向上可以吃掉对方的子，值0则表示不能，同时定义一个函数movedir(int x,int y,int mover)来判断各方向的状态，函数movedir的具体实现见源代码，这里以右方向为例说明，其他各个方向类似，右方向的判断可以用以下语句实现：int tx=x+1,ty=y,step=0;/tx,ty分别用来表示右方向各点在数组中的索引dirstate0=0;/初始化为不能吃子while(1)if(tx9) break;/处于边界，退出循环，该方向不能吃子if(statetytx=0) break; /空子，退出循环，该方向不能吃子if(statetytx!=mover) step+;/（tx,ty）所在的方格上的棋不一样，step加1，有连/续step个对方的棋子与（x，y）上的棋相邻else if(step0) dirstate0=1;break;/ （tx,ty）所在的方格上的棋一样，同时在(tx,ty) /和(x,y)之间如果有连续step个对方的棋子，则、/表示该方向上可以吃子，修改dirstate0状态。tx+;我们需要让计算机自己决定下一步走哪儿，必须让它知道走哪儿对它自己最有利，解决这个问题的基本思想就是对这个有利进行量化，我们有一个非常简单的方法就可以实现这个量化，那就是下该子能吃掉对方子的数目为该步的有利值，为了让计算机算出该值，我定义了一个int movetotal(int x,int y,int mover)函数，该函数返回该步能吃掉对方的子数，他的主要实现跟movedir类似，也是对各个方向进行统计，因此也可以用此函数来判断该位置能不能放子：int total=0;/total用来统计总的能够吃掉对方的子数，函数最后返回此值int tx=x+1,ty=y,step=0;while(1)if(tx9) break;if(statetytx=0) break;if(statetytx!=mover) step+;else if(step0) total+=step;break;/与movedir不同的地方，这里将step加到/total这个统计整数里面tx+;有了这些函数，电脑就可以用这个有利值选择一个位置下棋，因此接下来我们就要考虑黑白棋的下棋后棋盘状态的变化了。我们知道，当我们在（x，y）这个位置上下一个棋后，就会引起这个位置的八个方向上的符合条件（棋子和原有的已方棋子夹住对方的至少一个棋子）的方格上棋子状态的改变。为此我们定义了函数move (int x,int y,int mover)实现这个功能，其中x，y为下棋的位置， mover为-1表示己方用黑棋，1表示己方用白棋，函数move的主要实现如下（以右方向为例，详细请看源代码）：movedir(x,y,mover);/调用movedir函数，得到dirstate数组表示各个方向的状态stateyx=mover;/在该位置上下棋，改变棋盘在该位置的状态，将空状态改为moverint tx=x,ty=y;if(dirstate0=1)/为1则表示该方向可以吃掉对方的棋子，将已方棋子夹住对方棋子改/为己方while(statety+tx=mover*(-1)/循环直到遇到己方的棋子statetytx=mover;/将对方的棋子改为己方的棋子至此，一个非常简单的黑白棋就已经完成了，看到这里聪明的你当然会说，这样的电脑不是太容易赢了，没错，如果只看到当前能够吃掉对方子的个数最大数就下认为该步是最优的话，那明显是不对的，因为下一步对方有可能吃掉你更多的子，这样就得不偿失，所以我们必须增加一些算法，使计算机得到的位置接近最优，我们就必须判断该步后的几步，预测对方可能下的位置，计算机的高速运算能力和高存储能力为我们提供了实现的条件，这里我们采用了深度优先的方法，生成一棵解树，找出比较接近最优的解，预测的步数就是深度优先方法的深度，也就是解树的深度，这就要看具体计算机的速度内存的大小，深度越深，得到的也就越接近最优解，这里不可能递推太深，不然计算机每下一步会慢的你无法忍受，同时内存的限制了你递推的深度。递推函数的实现如下：1. int getbenefit (int x,int y,int mover,int n)2. 3. int benefit=0;4. benefit=movetotal(x,y,mover);5. if(benefit=0)return 0;6. if(n=1)7. 8. return benefit;9. 10. else11. 12. int tempstate1010;13. int good1010;14. int i=0,j=0;15. for(i=0;i10;i+)16. 17. for(j=0;j10;j+)18. 19. tempstateij=stateij;20. goodij=0;21. 22. 23. move(x,y,mover);24. mover=mover*(-1);25. n-=1;26. for(i=0;i10;i+)27. 28. for(j=0;j0)32. 33. if(i=0&j=0|i=9&j=0|i=0&j=9|i=9&j=9)34. 35. if(mover=computermover)36. benefit+=n+5;37. if(mover!=computermover)38. benefit-=n-5;39. 40. goodij=getbenefit(j,i,mover,n);41. 42. 43. 44. benefit=findmax(good,10,10)*mover+benefit;45. for(i=0;i10;i+)46. 47. for(j=0;j10;j+)48. 49. stateij=tempstateij;50. 51. 52. return benefit;53. 54. 函数说明：1：函数的参数中（x，y）表示当前要下的位置，mover为-1表示己方用黑棋，1表示己方用白棋，n为递推的深度。45：计算下（x，y）能够吃掉对方棋子的数放到benefit里，并判断（x，y）能不能放子，benefit大于0表示可以，否则退出递推函数，返回0表示不能放子。611：判断是否达到所要求的递推深度，当n等于1是表示完成递推，返回该位置能吃掉对方的棋子数benefit，否则继续进行递推。1222：数组int tempstate1010对当前棋盘的状态进行备份，使递推函数退出时可以恢复原来的棋盘状态，数组int good1010用来存储下该子后对方在棋盘各个位置上下棋分别能吃掉己方的棋子数，初始化为0。23：在（x，y）位置上下棋，调用move函数实现，改变棋盘的状态，以前进行递推运算对方下一步的吃掉己方的子数，当然这种改变是暂时的，在最后还要用数组tempstate备份的棋盘状态进行恢复。2425：改变下棋方，同时递推深度减一2643：对棋盘可以下棋位置进行递推调用getbenefit函数，这是本函数的主要部分，将各个位置的调用getbenefit函数的返回值保存到good数组上，以便找到对方能够吃掉己方最多子的位置。3339：这是对本智能函数的一个优化部分，考虑到占领四个角对整盘棋起着至关重要的作用，所以只要可以占领四个角，便对该位置增加或减少（看当前递推是处于递推己方还是对方）一个权值，在这里我将这个权值设为n5，与递推的深度有关，越深表示最后下到那里的机会越小，所以权值就越小。44：用findmax求出good数组中最大的值，乘以mover的作用就是要根据当前递推是处于递推黑方还是白方来判断good数组中表示的是黑方还是白方的加权值，用mover可以巧妙的分辨出当前递推是处于递推黑方还是白方，这里mover已经在24行那里改变了，所以good得到的是与前面用movetotal函数得到benefit值相反。4551：恢复棋盘到进入递推函数前的状态。至此，该程序的核心部分已经完成，整合上面的函数，我们可以得到一个电脑选择位置下棋子的函数computerAI ()，他的实现如下： 1. int i=0,j=0,mx=0,my=0,max; 2. int benefit1010; 3. for(i=0;i10;i+) 4. 5. for(j=0;j10;j+) 6. 7. benefitij=-1000; 8. 9. 10. for(i=0;i10;i+) 11. 12. for(j=0;j0) 18. 19. move(j,i,computermover); 20. return; 21. 22. 23. if(movetotal(j,i,computermover)0) 24. benefitij=getbenefit(j,i,computermover,AI); 25. if(i=1|i=8|j=1|j=8)benefitij+=1; 26. 27. 28. max=benefit00; 29. for(i=0;i10;i+) 30. 31. for(j=0;jmax) 34. 35. max=benefitij; 36. mx=j; 37. my=i; 38. 39. 40. 41. if(movetotal(mx,my,computermover)0) 42. move(mx,my,computermover);函数说明：29：数组benefit1010用来存放各点所能得到的权值，类似于getbenefit的good数组，初始化为一个比较大的负值，这里取1000，因为权值不会大于1000。1027：循环尝试各个位置，分别调用getbenefit函数进行递推，将各个位置上得到的值存放到benefit数组。14：当前点已经有棋，不用考虑，进行下一循环。1522：如果当前可以下四个对角点，则下对角点，不用调用递推函数。2324：当前位置可以下，则调用getbenefit递推函数进行递推，所得结果送到数组benefit相应的位置上。 2840：查找数组benefit上的最大值，并将最大值的位置放在mx和my上。4142：下棋，调用move函数实现得到computerAI ()函数，本程序基本完成了，对于黑白棋的界面则可以根据state数组画出棋盘。当然这样的AI还是不够的，一些比较简单的陷阱就可以让电脑毫不犹豫的跳进去，同时通过预测未来几步，计算机可以相应的求出最佳解。但是由于“预测步数”不可能无限制扩大，我们得到的解永远是近似的。为了补偿这种缺憾，我们可以把我们人类思考而得来的一些规律性的东西告诉电脑，使它在理性思考的同时把经验考虑进去，让它更聪明一些、更接近人类思维一些，在我的源代码里面就有一些这样的经验函数，通过与写好的黑白棋程序进行对弈，你就可以发现他的不足，然后分析这些不足的地方，将他们写成经验函数，每当遇到这些情况，就对他增加或减少一个权值，这样，这个程序也会随着你的经验函数的增加AI越来越厉害。更深的考虑，你可以为此建立一个数据库，将一些棋局存进去，这样你的程序会随着下的次数越多，AI也就越厉害，但实现起来已经出了本文要讨论的了，有兴趣的可以看看人工智能关于专家系统方面的介绍。黑白棋程序源代码的组成主要由两个类加一个主程序实现，分别是Chess类和Show类。Chess类实现有关棋盘状态，人工智能函数，经验函数的封装，主要组成如下：class CHESSpublic:CHESS(int x,int y);/构造函数，x表示电脑用黑子还是白纸，y是所使用的人工/智能函数选择CHESS();/析构函数void move(int x,int y,int mover);/下棋，作用具体见上面void humanmove(int x,int y);/游戏者下棋，将游戏者所要下的位置传到此函数int movetotal(int x,int y,int mover);/吃子总数，具体见上int getbenefit(int x,int y,int mover,int n);/递推函数，具体见上void movedir(int x,int y,int mover);/判断各个方向的状态到dirstate数组，具体/见上int dirstate8;/ 各个方向的状态int computermover;/计算机下黑子还是白子，1黑子，1白子int AI; /所要使用的AI的等级int state1010;/棋盘的状态private:int findmax(int data10,int xsize,int ysize);/查找data数组的最大值void computerAI(char a);/根据a的值，选择下面四个AI函数之一void computerAI1();/第一级AI函数void computerAI2();/第二级AI函数void computerAI3();/第三级AI函数void computerAI4();/第四级AI函数int addAI6