五子棋___毕业论文.doc

计算机科学与技术学院网络信息处理课程设计姓 名： 学 号： 专 业： 班 级： 设计题目： 网络五子棋 指导教师： 职 称： 摘要本论文主要阐述以面向对象的程序开发语言VC+为开发工具,设计一个五子棋游戏。本系统是个小型游戏，可以单机使用，也可以网络两个人游戏，也可以和电脑进行游戏。论文首先介绍了开发背景及开发语言的介绍。然后介绍设计该游戏的框架结构，然后介绍了程序的设计过程，以及程序的相关算法。)关键词:游戏, 系统 ,图片, VISUAL C+目 录1引 言 -11.1五子棋介绍 11.2开发背景 11.3开发环境及运行环境- 11.3.1开发环境- 11.3.2运行环境- 12软件架构 -22.1棋盘类 -22.2游戏模式类 -33棋盘类CTable -43.1主要成员变量说明 -43.1.1网络连接标志- 43.1.2棋盘等待标志- 43.1.3网络套接字- 43.1.4棋盘数据 -43.1.5游戏模式指针- 53.2主要成员函数说明- 53.2.1套接字的回调处理- 53.2.2清空棋盘- 53.2.3绘制棋子- 53.2.4左键消息- 63.2.5绘制棋盘- 63.2.6对方落子完毕- 63.2.7设置游戏模式- 63.2.8胜负的判断- 74游戏模式类- 84.1主要成员变量说明- 94.1.1棋盘指针- 94.1.2落子步骤- 94.2主要成员函数说明- 94.2.1悔棋操作- 94.2.2初始化操作- 94.2.3接收来自对方的消息 -104.2.4发送落子消息- 104.2.5胜利后的处理 -105消息机制- 115.1消息机制的架构 -115.2各种消息说明 -115.2.1落子消息- 125.2.2悔棋消息 -125.2.3同意悔棋消息 -135.2.4拒绝悔棋消息 -135.2.5和棋消息 -135.2.6同意和棋消息 -135.2.7拒绝和棋消息 -145.2.8认输消息- 145.2.9聊天消息 -145.2.10对方信息消息 -155.2.11再次开局消息- 155.2.12同意再次开局消息-156主要算法 -166.1判断胜负- 166.2人机对弈算法- 186.2.1获胜组合- 196.2.2落子后处理- 196.2.5防守策略 -236.2.6选取最佳落子 -247几点补充说明- 258心得体会 -26参考文献- 27第一章引言1.1五子棋介绍五子棋是起源于中国古代的传统黑白棋种之一。五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。1.2开发背景 为了综合利用我们所学过的相关知识，深化理解理解这三年来所学的知识，提高动手方面的能力，将理论应用于与实践，利用本次网络信息课程设计的大好机会，我们组决定以“网络五子棋”这一实验项目为题，编制双人联机对抗决赛的智力游戏。当前网络上流传的五子棋游戏功能并不尽善尽美，其中最主要的问题就是人机对战和网络对战不能够一起实现，所以我决定开发1一个既能够人机对战，又能够进行网络对战的五子棋系统。1.3开发环境及运行环境1.3.1开发环境l Intel Pentium 4 2.0GHz，512M内存，80G硬盘l Microsoft Windows 2000 Professionall Microsoft Visual C+ 6.0l Microsoft Developer Network for Visual Studio.NET 2003l Visual Assist X 10.1.1301.01.3.2运行环境l Intel Pentium 2及以上处理器，32M以上内存，4G以上硬盘l Microsoft Windows 9X/NT操作系统l 800*600或以上的屏幕分辨率第二章概要设计.软件架构软件的总体架构如图2.1：二人游戏类游戏类指针棋盘类主界面用户图2.1 软件架构考虑到整个的下棋过程（无论对方是电脑抑或其他网络玩家）可以分为：己方落子、等待对方落子、对方落子、设置己方棋盘数据这一系列过程，因此二人游戏类和棋盘类之间的关系参考了AbstractFactory（抽象工厂）模式，以实现对两个不同模块进行一般化的控制。22.棋盘类整个架构的核心部分，类名为CTable。封装了棋盘的各种可能用到的功能3，如保存棋盘数据、初始化、判断胜负等。用户操作主界面，主界面与CTable进行交互来完成对游戏的操作。2.游戏模式类用来管理人机对弈/网络对弈两种游戏模式，类名为CGame。CGame是一个抽象类，经由它派生出一人游戏类COneGame和网络游戏类CTwoGame，如图2.2：抽象类CGameCOneGameCTwoGame 图2.2 CGame类派生关系这样，CTable类就可以通过一个CGame类的指针4，在游戏初始化的时候根据具体游戏模式的要求实例化COneGame或CTwoGame类的对象；然后利用多态性5，使用CGame类提供的公有接口就可以完成不同游戏模式下的不同功能了。第三章详细设计棋盘类CTable3.1主要成员变量说明3.1.1网络连接标志m_bConnected用来表示当前网络连接的情况，在网络对弈游戏模式下客户端连接服务器的时候用来判断是否连接成功；事实上，它也是区分当前游戏模式的唯一标志。3.1.2棋盘等待标志m_bWait与m_bOldWait由于在玩家落子后需要等待对方落子，m_bWait标志就用来标识棋盘的等待状态。当m_bWait为TRUE时，是不允许玩家落子的。在网络对弈模式下，玩家之间需要互相发送诸如悔棋、和棋这一类的请求消息，在发送请求后等待对方回应时，也是不允许落子的，所以需要将m_bWait标志置为TRUE。在收到对方回应后，需要恢复原有的棋盘等待状态，所以需要另外一个变量在发送请求之前保存棋盘的等待状态做恢复之用，也就是m_bOldWait。等待标志的设置，由成员函数SetWait和RestoreWait完成。3.1.3网络套接字m_sock和m_conn在网络对弈游戏模式下，需要用到这两个套接字对象。其中m_sock对象用于做服务器时的监听之用，m_conn用于网络连接的传输。3.1.4棋盘数据m_data这是一个15*15的二位数组，用来保存当前棋盘的落子数据。其中对于每个成员来说，0表示落黑子，1表示落白子，-1表示无子。3.1.5游戏模式指针m_pGame这个CGame类的对象指针是CTable类的核心内容。它所指向的对象实体决定了CTable在执行一件事情时候的不同行为，具体的内容请参见“游戏模式”一节。3.2主要成员函数说明3.2.1套接字的回调处理Accept、Connect、Receive本程序的套接字派生自MFC的CAsyncSocket类6，CTable的这三个成员函数就分别提供了对套接字7回调事件OnAccept、OnConnect、OnReceive的实际处理，其中尤以Receive成员函数重要，它之中包含了对所有网络消息（参见“消息机制”一节）的分发处理。3.2.2清空棋盘Clear在每一局游戏开始的时候都需要调用这个函数将棋盘清空，也就是棋盘的初始化工作。在这个函数中，主要发生了这么几件事情：l 将m_data中每一个落子位都置为无子状态（-1）。l 按照传入的参数设置棋盘等待标志m_bWait，以供先、后手的不同情况之用。l 使用delete将m_pGame指针所指向的原有游戏模式对象从堆上删除。3.2.3绘制棋子Draw这无疑是很重要的一个函数，它根据参数给定的坐标和颜色绘制棋子。绘制的详细过程如下：l 将给定的棋盘坐标换算为绘图的像素坐标。l 根据坐标绘制棋子位图。l 如果先前曾下过棋子，则利用R2_NOTXORPEN将上一个绘制棋子上的最后落子指示矩形擦除。l 在刚绘制完成的棋子四周绘制最后落子指示矩形。3.2.4左键消息OnLButtonUp作为棋盘唯一响应的左键消息，也需要做不少的工作：l 如果棋盘等待标志m_bWait为TRUE，则直接发出警告声音并返回，即禁止落子。l 如果点击时的鼠标坐标在合法坐标(0, 0)(14, 14)之外，亦禁止落子。l 如果走的步数大于1步，方才允许悔棋。l 进行胜利判断，如胜利则修改UI状态并增加胜利数的统计。l 如未胜利，则向对方发送已经落子的消息。l 落子完毕，将m_bWait标志置为TRUE，开始等待对方回应。3.2.5绘制棋盘OnPaint每当WM_PAINT消息触发时，都需要对棋盘进行重绘。OnPaint作为响应绘制消息的消息处理函数使用了双缓冲技术，减少了多次绘图可能导致的图像闪烁问题。这个函数主要完成了以下工作：l 装载棋盘位图并进行绘制。l 根据棋盘数据绘制棋子。l 绘制最后落子指示矩形。.棋盘指针m_pTable由于在游戏中需要对棋盘以及棋盘的父窗口主对话框进行操作及UI状态设置，故为CGame类设置了这个成员。当对主对话框进行操作时，可以使用m_pTable-GetParent()得到它的窗口指针。.落子步骤m_StepList一个好的棋类程序必须要考虑到的功能就是它的悔棋功能，所以需要为游戏类设置一个落子步骤的列表。由于人机对弈和网络对弈中都需要这个功能，故将这个成员直接设置到基类CGame中。另外，考虑到使用的简便性，这个成员使用了C+标准模板库10（Standard Template Library，STL）中的std:list，而不是MFC的CList。3.2.对方落子完毕Over在对方落子之后，仍然需要做一些判断工作，这些工作与OnLButtonUp中的类似，在此不再赘述。这之后，就可以利用OO的继承和多态特点8来使m_pGame指针使用相同的调用来完成不同的工作了，事实上，COneGame:Init和CTwoGame:Init都是不同的。.接收来自对方的消息ReceiveMsg这个成员函数由CTable棋盘类的Receive成员函数调用，用于接收来自对方的消息。对于网络对弈游戏模式来说，这个成员函数则负责从套接字读取对方发过来的数据，然后将这些数据解释为自定义的消息结构，并回到CTable:Receive来进行处理。.发送落子消息SendStep在玩家落子结束后，要向对方发送自己落子的消息。对于网络对弈游戏模式，将把落子消息发送给套接字，并由套接字转发给对方。.胜利后的处理Win这个成员函数主要针对CTwoGame网络对弈模式。在玩家赢得棋局后，这个函数仍然会调用SendStep将玩家所下的制胜落子步骤发送给对方玩家，然后对方的游戏端经由CTable:Win来判定自己失败。第四章消息机制Windows系统拥有自己的消息机制，在不同事件发生的时候，系统也可以提供不同的响应方式11。五子棋程序也模仿Windows系统实现了自己的消息机制，主要为网络对弈服务，以响应多种多样的网络消息。5.1消息机制的架构当继承自CAsyncSocket的套接字类CFiveSocket收到消息时，会触发CFiveSocket:OnReceive事件12，在这个事件中调用CTable:Receive，CTable:Receive开始按照自定义的消息格式接收套接字发送的数据，并对不同的消息类型进行分发处理。CFiveSocket网络数据CTable:Receive分发处理CFiveSocket:OnReceiveCFiveSocket:Receive调用 图5.1 自定义的消息机制如图5.1所示，当CTable获得了来自网络的消息之后，就可以使用一个switch结构来进行消息的分发了。5.2各种消息说明网络间传递的消息，都遵循以下一个结构体的形式：/ 摘自Messages.htypedef struct _tagMsgStruct / 消息ID UINT uMsg; / 落子信息 int x; int y; int color; / 消息内容 TCHAR szMsg128; MSGSTRUCT;随着uMsg表示消息ID，x、y表示落子的坐标，color表示落子的颜色，szMsg随着uMsg的不同而有不同的含义。5.2.1落子消息MSG_PUTSTEP表明对方落下了一个棋子，其中x、y和color成员有效，szMsg成员无效。在人机对弈游戏模式下，亦会模拟发送此消息以达到程序模块一般化的效果。5.2.2悔棋消息MSG_BACK表明对方请求悔棋，除uMsg成员外其余成员皆无效。接到这个消息后，会弹出MessageBox询问是否接受对方的请求（如图5.2所示），并根据玩家的选择回返MSG_AGREEBACK或MSG_REFUSEBACK消息。另外，在发送这个消息之后，主界面上的某些元素将不再响应用户的操作。图5.2 请求悔棋5.2.3同意悔棋消息MSG_AGREEBACK表明对方接受了玩家的悔棋请求，除uMsg成员外其余成员皆无效。接到这个消息后，将进行正常的悔棋操作。5.2.4拒绝悔棋消息MSG_REFUSEBACK表明对方拒绝了玩家的悔棋请求（如图5.3所示），除uMsg成员外其余成员皆无效。接到这个消息后，整个界面将恢复发送悔棋请求前的状态。图5.3 拒绝悔棋5.2.5和棋消息MSG_DRAW表明对方请求和棋，除uMsg成员外其余成员皆无效。接到这个消息后，会弹出MessageBox询问是否接受对方的请求（如图5.4所示），并根据玩家的选择回返MSG_AGREEDRAW或MSG_REFUSEDRAW消息。另外，在发送这个消息之后，主界面上的某些元素将不再响应用户的操作。图5.4 请求和棋5.2.6同意和棋消息MSG_AGREEDRAW表明对方接受了玩家的和棋请求（如图5.5所示），除uMsg成员外其余成员皆无效。接到这个消息后，双方和棋。图5.5 同意和棋5.2.7拒绝和棋消息MSG_REFUSEDRAW表明对方拒绝了玩家的和棋请求（如图5.6所示），除uMsg成员外其余成员皆无效。接到这个消息后，整个界面将恢复发送和棋请求前的状态。图5.6 拒绝和棋5.2.8认输消息MSG_GIVEUP表明对方已经投子认输（如图5.7所示），除uMsg成员外其余成员皆无效。接到这个消息后，整个界面将转换为胜利后的状态。图5.7 认输5.2.9聊天消息MSG_CHAT表明对方发送了一条聊天信息，szMsg表示对方的信息，其余成员无效。接到这个信息后，会将对方聊天的内容显示在主对话框的聊天记录窗口内。5.2.10对方信息消息MSG_INFORMATION用来获取对方玩家的姓名，szMsg表示对方的姓名，其余成员无效。在开始游戏的时候，由客户端向服务端发送这条消息，服务端接到后设置对方的姓名，并将自己的姓名同样用这条消息回发给客户端。5.2.11再次开局消息MSG_PLAYAGAIN表明对方希望开始一局新的棋局，除uMsg成员外其余成员皆无效。接到这个消息后，会弹出MessageBox询问是否接受对方的请求（如图5.8所示），并根据玩家的选择回返MSG_AGREEAGAIN消息或直接断开网络。图5.8 再次开局5.2.12同意再次开局消息MSG_AGREEAGAIN表明对方同意了再次开局的请求，除uMsg成员外其余成员皆无效。接到这个消息后，将开启一局新游戏。6主要算法五子棋游戏中，有相当的篇幅是算法的部分。无论是人机对弈，还是网络对弈，都需要合理算法的支持，本节中将详细介绍五子棋中使用的算法。136.1判断胜负五子棋的胜负，在于判断棋盘上是否有一个点，从这个点开始的右、下、右下、左下四个方向是否有连续的五个同色棋子出现，如图6.1：图6.1 判断胜负方向这个算法也就是CTable的Win成员函数。从设计的思想上，需要它接受一个棋子颜色的参数，然后返回一个布尔值，这个值来指示是否胜利，代码如下：BOOL CTable:Win( int color ) const 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，这样也就提高了搜索的速度。6.2人机对弈算法人机对弈算法完全按照CGame基类定义的接口标准，封装在了COneGame派生类之中。下面将对这个算法进行详细地介绍。146.2.1获胜组合获胜组合是一个三维数组，它记录了所有取胜的情况。也就是说，参考于CTable:Win中的情况，对于每一个落子坐标，获胜的组合一共有15 * 11 * 2 + 11 * 11 * 2 = 572种。而对于每个坐标的获胜组合，应该设置一个1515572大小的三维数组。在拥有了这些获胜组合之后，就可以参照每个坐标的572种组合给自己的局面和玩家的局面进行打分，也就是根据当前盘面中某一方所拥有的获胜组合多少进行权值的估算，给出最有利于自己的一步落子坐标。由于是双方对弈，所以游戏的双方都需要一份获胜组合，也就是：bool m_Computer1515572; / 电脑获胜组合bool m_Player1515572; / 玩家获胜组合在每次游戏初始化（COneGame:Init）的时候，需要将每个坐标下可能的获胜组合都置为true。此外，还需要设置计算机和玩家在各个获胜组合中所填入的棋子数：int m_Win2572;在初始化的时候，将每个棋子数置为0。6.2.2落子后处理每当一方落子后，都需要作如下处理：l 如果己方此坐标的获胜组合仍为true，且仍有可能在此获胜组合处添加棋子，则将此获胜组合添加棋子数加1；l 如果对方此坐标的获胜组合仍为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; 6.2.3查找棋盘空位在计算机落子之前，需要查找棋盘的空位，所以需要一个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;6.2.4落子打分找到空位后，需要对这个点的落子进行打分，这个分数也就是这个坐标重要性的体现，代码如下：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;如代码所示，考虑到攻守两方面的需要，所以将玩家落子给的分数置为负值。6.2.5防守策略落子的考虑不单单要从进攻考虑，还要从防守考虑。这一细节的实现其实就是让计算机从玩家棋盘布局分析战况，然后找出对玩家最有利的落子位置。整个过程如下：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;在这之后，重新改变一下棋盘的状态（6.2.2）即可。7几点补充说明l 考虑到程序的响应速度，人机对弈算法只对玩家的棋子进行了一步的推测。