人工智能课程设计报告-五子棋.doc

目 录1. 五子棋简介 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 32. 需求分析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 33. 主要名词说明 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 34. 主要算法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 45. 程序运行界面展示 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 76. 不足说明 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 87. 心得体会 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 81、五子棋简介 选择五子棋游戏作为本设计的课题，是因为该游戏的规则简单，所涉及的方向比较少。这样才能将问题的重点放在人工智能解决上，而非规则的解决，有更多的精力放在高效算法的优化。希望能通过本次系统的设计，整合所学的知识，实现从理论到实践上的升华。 五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”(Five in a Row的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。它不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。 五子棋的规则如下： 棋盘：采用1515的棋盘。下法：两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点落子。 输赢判断：黑、白双方有一方的5个棋子在横、竖或斜方向上连接成一线即为该方赢。2、需求分析 作为五子棋的设计需要考虑到的最基本的需求莫过于人机对战功能的实现，当然还有下棋过程中的悔棋功能以及判断游戏的胜负等方面的要求。当然最好是要考虑到界面的友好性，作为一个娱乐软件，还应该考虑到玩家在游戏时的舒适性，比如可以考虑加入一些背景音乐和音效。3、主要名词说明3.1 棋盘数据m_data这是一个15*15的二位数组，用来保存当前棋盘的落子数据。其中对于每个成员来说，0表示落黑子，1表示落白子，-1表示无子。3.2 清空棋盘Clear在每一局游戏开始的时候都需要调用这个函数将棋盘清空，也就是棋盘的初始化工作。这个函数主要将m_data中每一个落子位都置为无子状态（-1）。3.3 初始化操作Init 对于人机对弈而言，初始化操作包括以下几个步骤：（1）初始化所有的获胜组合。（2）如果是计算机先走，则占据天元（棋盘正中央）的位置。3.4 绘制棋子Draw 这是很重要的一个函数，它根据参数给定的坐标和颜色绘制棋子。绘制的详细过程如下：（1）将给定的棋盘坐标换算为绘图的像素坐标。（2）根据坐标绘制棋子位图。（3）如果先前曾下过棋子，则利用R2_NOTXORPEN将上一个绘制棋子上的最后落子指示矩形擦除。（4）在刚绘制完成的棋子四周绘制最后落子指示矩形。3.5 左键消息OnLButtonUp 作为棋盘唯一响应的左键消息，也需要做不少的工作：（1）如果点击时的鼠标坐标在合法坐标(0, 0)(14, 14)之外，亦禁止落子。（2）如果走的步数大于1步，则允许悔棋。3.6 绘制棋盘OnPaint 每当WM_PAINT消息触发时，都需要对棋盘进行重绘。OnPaint作为响应绘制消息的消息处理函数使用了双缓冲技术，减少了多次绘图可能导致的图像闪烁问题。这个函数主要完成了以下工作：（1）装载棋盘位图并进行绘制。（2）根据棋盘数据绘制棋子。（3）绘制最后落子指示矩形。3.7 胜负的判断Win这是游戏中一个极其重要的算法，用来判断当前棋盘的形势是哪一方获胜。其详细内容请参见“主要算法”一节。3.8 悔棋操作Back因为是人机对弈，所以计算机是完全允许玩家悔棋的，但是出于对程序负荷的考虑，只允许玩家悔当前的两步棋（计算机一步，玩家一步）。4、主要算法4.1 判断胜负 五子棋的胜负，在于判断棋盘上是否有一个点，从这个点开始的横竖斜四个方向是否有连续的五个同色棋子出现，如图1： 图1 这个算法就是Win函数。从设计的思想上，需要它接受一个棋子的参数，然后返回一个值，这个值来指示是否胜利，代码如下：int x, y; for ( y = 0; y 15; y+ ) / 判断横向 for ( x = 0; x 11; x+ ) if ( color = m_dataxy &color = m_datax + 1y &color = m_datax + 2y &color = m_datax + 3y &color = m_datax + 4y ) return TRUE; for ( y = 0; y 11; y+ ) / 判断纵向 for ( x = 0; x 15; x+ ) if ( color = m_dataxy &color = m_dataxy + 1 &color = m_dataxy + 2 &color = m_dataxy + 3 &color = m_dataxy + 4 ) return TRUE; for ( y = 0; y 11; y+ ) / 判断“”方向 for ( x = 0; x 11; x+ ) if ( color = m_dataxy &color = m_datax + 1y + 1 &color = m_datax + 2y + 2 &color = m_datax + 3y + 3 &color = m_datax + 4y + 4 ) return TRUE; for ( y = 0; y 11; y+ ) / 判断“/”方向 for ( x = 4; x 15; x+ ) if ( color = m_dataxy &color = m_datax - 1y + 1 &color = m_datax - 2y + 2 &color = m_datax - 3y + 3 &color = m_datax - 4y + 4 ) return TRUE;return FALSE; / 不满足胜利条件需要说明的一点是，由于搜索顺序是从左到右、自上而下，因此在每次循环的时候，都有一些坐标无需纳入考虑范围。例如对于横向判断而言，由于右边界所限，因而所有横坐标大于等于11的点，都构不成达到五子连的条件，所以横坐标的循环上界也就定为11，这样就提高了搜索的速度。4.2 获胜组合 获胜组合是一个三维数组，它记录了所有获胜的情况。也就是说，参考于Win中的情况，对于每一个落子坐标，获胜的情况一共有15 * 11 * 2 + 11 * 11 * 2 = 572种，而对于每个坐标的获胜组合，应该设置一个1515572大小的三维数组。 在拥有了这些获胜组合之后，就可以参照每个坐标的572种组合给自己的局面和玩家的局面进行打分，也就是根据当前盘面中某一方所拥有的获胜组合多少进行权值的估算，给出最有利于自己的一步落子坐标。在每次游戏初始化（Init）的时候，需要将每个坐标下可能的获胜组合都置为true。 由于是双方对弈，所以游戏的双方都需要一份获胜组合，也就是：bool m_Computer1515572; / 电脑获胜组合bool m_Player1515572; / 玩家获胜组合4.3 落子后处理 每当一方落子后，都需要作如下处理： 如果己方此坐标的获胜组合仍为true，且仍有可能在此获胜组合处添加棋子，则将此获胜组合添加棋子数加1；如果对方此坐标的获胜组合仍为true，则将对方此坐标的获胜组合置为false，并将对方此获胜组合添加棋子数置为-1。 以玩家落子为例，代码为：for ( i = 0; i 572; i+ )if ( m_PlayerstepPut.xstepPut.yi &m_Win0i != -1 ) / 修改状态变化 m_Win0i+; if ( m_ComputerstepPut.xstepPut.yi ) m_ComputerstepPut.xstepPut.yi = false; m_Win1i = -1;4.4 查找棋盘空位 在计算机落子之前，需要查找棋盘的空位，所以需要一个SearchBlank成员函数完成此项工作，此函数需要进行不重复的查找，也就是说，对已查找过的空位进行标记，并返回找到空位的坐标，其代码如下：bool COneGame:SearchBlank( int &i, int &j, int nowTable15 )int x, y; for ( x = 0; x 15; x+ ) for ( y = 0; y 15; y+ ) if ( nowTablexy = -1 & nowTablexy != 2 ) i = x; j = y; return true;return false;4.5 落子打分 找到空位后，需要对这个点的落子进行打分，这个分数也就是这个坐标重要性的体现，代码如下：int COneGame:GiveScore( const STEP& stepPut )int i, nScore = 0; for ( i = 0; i GetColor() = stepPut.color ) if ( m_PlayerstepPut.xstepPut.yi ) / 玩家下 switch ( m_Win0i ) case 1: nScore -= 5; break; case 2: nScore -= 50; break; case 3: nScore -= 500; break; case 4: nScore -= 5000; break; default: break; else if ( m_ComputerstepPut.xstepPut.yi ) / 计算机下 switch ( m_Win1i ) case 1: nScore += 5; break; case 2: nScore += 50; break; case 3: nScore += 100; break; case 4: nScore += 10000; break; default: break; return nScore;如代码所示，考虑到攻守两方面的需要，所以将玩家落子给的分数置为负值。4.6 防守策略 落子的考虑不单单要从进攻考虑，还要从防守考虑。这一细节的实现其实就是让计算机从玩家棋盘布局分析战况，然后找出对玩家最有利的落子位置。整个过程如下：for ( m = 0; m GetColor(); step.x = i; step.y = j; ptemp = GiveScore( step ); if ( pscore ptemp ) / 此时为玩家下子，运用极 pscore = ptemp; 小极大法时应选取最小值for ( m = 0; m cscore )cscore = ctemp + pscore; bestx = pi; besty = pj;在这之后，重新改变一下棋盘的状态（4.3）即可。5、 程序运行界面展示 6、不足说明:（1）由于计算机在落子时选取的是得分最高的一步落子，所以如果玩家在开局的时候不改变落子步骤，那么将会获得从头至尾相同的棋局。考虑可以在某些步骤上加入随机因素，使对弈过程更具趣味性。（2）可能的话增加一些背景音乐功能；可以增加保存棋局，以便于调用观看。（3）人机算法部分中的评估函数，也需要调整使得其更加的智能。算法有个缺点就是当棋盘上的棋子相当的时候，比如双方都存在活三，它会调用评估函数向前预测，算出双方的值相当。于是就不选择自己连四。可以说这是很大的败笔，不过可以写个函数进行修补。（4）总体感觉系统可维护性很差，应该尽可能的使用常量代替具体数据。这样更利于后期的维护，避免牵一发而动全身。7、 心得体会 在刚开始编写这个程序的时候，我幼稚地认为其中最重要的是博弈算法。但是头几天编写程序的时候却发现程序越写越不容易维护，可