五子棋课程设计报告

程序设计实验报告PAGEPAGE2上海海事大学程序设计课程设计报告课程题目FIVECHESSGAME作者姓名学号联系方式指导教师学科(专业)所在学院提交日期目录1引言 31.1五子棋介绍 31.2选题背景和动机 31.3系统所要解决的问题 32系统框架 52.1棋盘类 62.1.1主要成员变量说明： 62.1.2清空棋盘——Clear 62.1.3绘制棋子——Draw 62.1.4左键消息——OnLButtonUp 72.1.5 载入棋盘 72.1.6对方落子完毕——Over 72.1.7设置游戏模式——SetGameMode 72.1.8胜负的判断——Win 72.2游戏模式类 83关键技术 93.1棋盘对话框的制作 93.1.1对话框机制 93.1.3棋子 103.2人机对弈 103.2.1难度的选择 103.2.2机器的落子判断 114运行结果 154.1开发环境及运行环境 154.1.1开发环境 154.1.2运行环境 154．2运行图示 154.2.1棋盘显示 154.2.2开始的选择对话框 164.2.3主界面中的游戏难度选项 164.2.4电脑的应对 175调试分析 196总结 21参考文献 221引言1.1五子棋介绍五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”（FiveinaRow的缩写），亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。1.2选题背景和动机随着社会的发展，越来越多人接触和使用计算机，网上进行的棋类运动也随之普及。许多人喜欢上了下棋，但有时又苦于没有对手。作为一个计算机专业的学生，我对五子棋有很浓厚的兴趣，平时也一直和同学下棋，有时也和电脑下棋，我对计算机人机对弈智能算法如何与人脑对抗产生了极大的兴趣，当然人机对弈的算法有很多种，许多人也对此有所研究。有些算法的智能程度甚至已经与人脑不相上下。这类程序的开发最重要的莫过于智能算法的实现，然后就是判断胜负的方法。当前网络上流传的五子棋游戏功能并不尽善尽美，其中最主要的问题就是人机对战和网络对战不能够一起实现，所以我决定开发[1]一个既能够人机对战，又能够进行网络对战的五子棋系统。1.3系统所要解决的问题1）棋盘和棋子的绘制。2）计算机对下一步落棋的计算3)棋盘的载入4）难度的模式选择5）棋盘状态的判定2系统框架五子棋系统框架：五子棋人机对弈五子棋人机对弈人人对弈判断输赢结果棋盘考虑到整个的下棋过程（无论对方是电脑或是其他网络玩家）可以分为：己方落子、等待对方落子、对方落子、设置己方棋盘数据这一系列过程，因此一人游戏类、二人游戏类和棋盘类之间的关系是不同的。2.1棋盘类整个架构的核心部分，类名为CTable。封装了棋盘的各种可能用到的功能，如保存棋盘数据、初始化、判断胜负等。用户操作主界面，主界面与CTable进行交互来完成对游戏的操作。2.1.1主要成员变量说明：棋盘等待标志——m_bWait与m_bOldWait由于在玩家落子后需要等待对方落子，m_bWait标志就用来标识棋盘的等待状态。当m_bWait为TRUE时，是不允许玩家落子的。在人人对弈模式下，玩家之间需要互相发送诸如悔棋、和棋这一类的请求消息，在发送请求后等待对方回应时，也是不允许落子的，所以需要将m_bWait标志置为TRUE。在收到对方回应后，需要恢复原有的棋盘等待状态，所以需要另外一个变量在发送请求之前保存棋盘的等待状态做恢复之用，也就是m_bOldWait。等待标志的设置，由成员函数SetWait和RestoreWait完成。2.1.2清空棋盘——Clear在每一局游戏开始的时候都需要调用这个函数将棋盘清空，也就是棋盘的初始化工作。在这个函数中，主要发生了这么几件事情：将m_data中每一个落子位都置为无子状态（-1）。按照传入的参数设置棋盘等待标志m_bWait，以供先、后手的不同情况之用。2.1.3绘制棋子——Draw这无疑是很重要的一个函数，它根据参数给定的坐标和颜色绘制棋子。绘制的详细过程如下：将给定的棋盘坐标换算为绘图的像素坐标。根据坐标绘制棋子位图。在刚绘制完成的棋子四周绘制最后落子指示矩形。2.1.4左键消息——OnLButtonUp作为棋盘唯一响应的左键消息，也需要做不少的工作：如果棋盘等待标志m_bWait为TRUE，则直接发出警告声音并返回，即禁止落子。如果点击时的鼠标坐标在合法坐标(0,0)～(14,14)之外，亦禁止落子。如果走的步数大于1步，方才允许悔棋。进行胜利判断，如胜利则修改UI状态并增加胜利数的统计。如未胜利，则向对方发送已经落子的消息。落子完毕，将m_bWait标志置为TRUE，开始等待对方回应。载入棋盘寻找棋盘位图，通过简单的代码载入位图，直接完成绘制棋盘工作，免去了大量绘制棋盘的多余操作。2.1.6对方落子完毕——Over在对方落子之后，仍然需要做一些判断工作，这些工作与OnLButtonUp中的类似。2.1.7设置游戏模式——SetGameMode这个函数通过传入的游戏模式参数对m_pGame指针进行了初始化，，就可以利用继承和多态特点来使m_pGame指针使用相同的调用来完成不同的工作了，事实上，COneGame::Init和CTwoGame::Init都是不同的。2.1.8胜负的判断——Win这是游戏中一个极其重要的算法，用来判断当前棋盘的形势是哪一方获胜。其详细内容在关键技术一节。2.2游戏模式类用来管理人机对弈人人对弈两种游戏模式，类名为CGame。CGame是一个抽象类，经由它派生出一人游戏类COneGame和网络游戏类CTwoGame，如图2.2：抽象类抽象类CGameCOneGameCTwoGameCOneGameCTwoGame图2.2CGame类派生关系这样，CTable类就可以通过一个CGame类的指针在游戏初始化的时候根据具体游戏模式的要求实例化COneGame或CTwoGame类的对象来区分人机对弈还是人人对弈；然后利用多态性，使用CGame类提供的公有接口就可以完成不同游戏模式下的不同功能了。3关键技术3.1棋盘对话框的制作3.1.1对话框机制显示对话框供人选择下棋模式BOOLCBestDlg::OnInitDialog()//初始化对话框{ CDialog::OnInitDialog(); m_hIcon=AfxGetApp()->LoadIcon(IDR_MAINFRAME); SetIcon(m_hIcon,TRUE); //设置大图标 SetIcon(m_hIcon,FALSE); //设置小图标 Name1Edit().SetWindowText(g_strName1);//载入用户名1 Name2Edit().SetWindowText(g_strName2);//载入用户名2 Name3Edit().SetWindowText(g_strName3);//载入用户名3 charstr[4];//定义4个字符的字符串 wsprintf(str,"%d",g_nTime1);//wsprintf(缓冲区,格式，要格式化的值)； Time1Edit().SetWindowText(str)//设置主窗口中空间(ID)的文字或标题; wsprintf(str,"%d",g_nTime2);//用来格式化字符串 Time2Edit().SetWindowText(str); wsprintf(str,"%d",g_nTime3); Time3Edit().SetWindowText(str); returnTRUE;}3.1.2棋盘用于载入棋盘m_pDibBoard->LoadDib(IDDIB_BOARD);//载入棋盘位图，m_pDibBoard->MakeBitmap(pDC);//绘制棋盘上的坐标，方便下子3.1.3棋子用于画棋子CRectCPenteDlg::GetCurStoneArea(CPointpoint)//获得棋子的坐标{ intnXd=point.x-m_wStoneWidth/2;//棋子横坐标 intnYd=point.y-m_wStoneHeight/2;//棋子纵坐标 returnCRect(nXd,nYd,nXd+m_wStoneWidth,nYd+m_wStoneHeight);//返回棋子的宽度高度}3.2人机对弈3.2.1难度的选择它能让玩家选择适合自己的难度设置电脑难易程度：BOOLCRecordDlg::OnInitDialog()//初始化对话框{ CDialog::OnInitDialog(); m_hIcon=AfxGetApp()->LoadIcon(IDR_MAINFRAME);//载入主框架图标 SetIcon(m_hIcon,TRUE); //设置大图标 SetIcon(m_hIcon,FALSE); //设置小图标 CStringstr;//声明字符串 if(g_nSkill==1)//如果技术为1 { str.LoadString(g_bChineseIDS_BEGINNER_CHINESE:IDS_BEGINNER_ENGLISH);//载入显示初学者难度位图，并用中文或者英文显示说明 SkillEdit().SetWindowText(str);//设置难度窗口 NameEdit().SetWindowText(g_strName1);//设置窗口，用于输入姓名 } elseif(g_nSkill==2)//如果技术为2 { str.LoadString(g_bChineseIDS_INTERMEDIATE_CHINESE:IDS_INTERMEDIATE_ENGLISH);载入中级难度位图，并显示 SkillEdit().SetWindowText(str); NameEdit().SetWindowText(g_strName2); } if(g_nSkill==3)//如果难度为3 { str.LoadString(g_bChineseIDS_EXPERT_CHINESE:IDS_EXPERT_ENGLISH);//载入专家级难度位图，并显示 SkillEdit().SetWindowText(str); NameEdit().SetWindowText(g_strName3); } NameEdit().SetFocus();对之前设置的窗口设置键盘焦点 returnTRUE;FALSE}3.2.2机器的落子判断它使电脑能够根据人的走棋加以应对人与机器对弈，机器是如何判断的呢？此时就需要引入人机对弈智能算法：算法如下：CPointCPenteDlg::UrgentPoint(BYTEbyColor)//声明紧迫度函数{ inti,i0,j,j0; BeginWaitCursor();///是建立等待光标 CPointptUrgent[2025],ptInit(-1,-1);//建立最大紧迫度2025 for(i=0;i<2025;++i)//初始化i ptUrgent[i]=ptInit;初始化i点的紧迫度nGrade1

=

Judge(i,

j,

(char)(byColor+1));//获取对方紧迫度

nGrade2

=

Judge(i,

j,

(char)(!byColor+1));//不同紧迫度，赋予不同度权值

if

(g_nSkill

==

1)

//初学者难度

{

switch

(nGrade1)

//转向等级1，并对它赋权值，用于判断电脑下棋位子

{

case

0

:

nUrgent1

=

0;

break;//在情况0下对紧迫度为1的点赋予权值0case

1

:

nUrgent1

=

2;

break;//在情况1下对紧迫度为1的点赋予权值4case

2

:

nUrgent1

=

4;

break；//以下的以此类推，直到赋予40case

3

:

nUrgent1

=

5;

break;

case

4

:

nUrgent1

=

8;

break;

case

5

:

nUrgent1

=

10;

break;

case

6

:

nUrgent1

=

11;

break;……

case

16

:

nUrgent1

=

32;

break;

case

17

:

nUrgent1

=

34;

break;

case

18

:

nUrgent1

=

36;

break;

case

19

:

nUrgent1

=

38;

break;

case

20

:

nUrgent1

=

40;

break;

default

:

nUrgent1

=

40;

break;

}

switch(nGrade2)//转向等级2{case0:nUrgent2=1;break;//在情况0时对紧迫度未2的点赋予权值1，case1:nUrgent2=3;break;//以下的以此类推直到赋予41为止case2:nUrgent2=6;break; case3:nUrgent2=7;break; case4:nUrgent2=9;break; case5:nUrgent2=21;break;//对紧迫度为2的点赋予在不同的情况下赋予不同的权值case6:nUrgent2=22;break; case7:nUrgent2=23;break; case8:nUrgent2=24;break; case9:nUrgent2=25;break; case10:nUrgent2=26;break; case11:nUrgent2=27;break; case12:nUrgent2=28;break; case13:nUrgent2=29;break; case14:nUrgent2=30;break; case15:nUrgent2=31;break; case16:nUrgent2=33;break; case17:nUrgent2=35;break; case18:nUrgent2=37;break; case19:nUrgent2=39;break; case20:nUrgent2=41;break; default:nUrgent2=41;break; } }nUrgent

=

min(nUrgent1,nUrgent2)*45

+

max(nUrgent1,

nUrgent2);//如上算法既考虑了对手的权值，也考虑了自己紧迫点的权值，通过赋予不同紧迫点不同的权值，综合起来且根据总和最大的来确定自己的下子点，由此而实现了人机的对弈。通过如下计算公式求出了最紧急的下子点：

ptUrgent[nUrgent]

=

ptCurrent;//获取具有最小紧迫度的点

}

}

for

(i=0;

i<2025;

++i)//

初始化i

if

(ptUrgent[i]

!=

ptInit)

//如果紧迫点权值i不等于初始值

break;

EndWaitCursor();//结束等待光标

if

(ptUrgent[i]

==

ptInit)//如果紧迫点权值i等于初始值

{

CString

str1,

str2;

声明2个字符串

str1.LoadString(IDS_DRAW_CHINESE);//载入中文图片

str2.LoadString(IDS_TITLE_CHINESE);//载入中文标题

MessageBox(str1,

str2);//出现显示平局的对话框

}

return

ptUrgent[i];//返回最小的点

}4运行结果4.1开发环境及运行环境4.1.1开发环境Intel®Pentium®42.0GHz，512M内存，80G硬盘Microsoft®Windows™XPMicrosoft®VisualC++6.04.1.2运行环境Intel®Pentium®2及以上处理器，32M以上内存，4G以上硬盘Microsoft®Windows™9X/NT操作系统800*600或以上的屏幕分辨率4．2运行图示4.2.1棋盘显示通过载入棋盘位图达到了如下效果：图4.2.1.五子棋棋盘4.2.2开始的选择对话框开始的选择对话框能让你选择与电脑下棋还是与人下棋，以及谁执黑先手。图4.2.2选择对话框4.2.3主界面中的游戏难度选项通过主界面中的游戏难度选项，能选择适合自己的难度等级，与电脑对弈。图4.2.3游戏难度选择4.2.4电脑的应对电脑抢先冲3先行的黑子电脑抢先冲3先行的黑子图冲3的情况冲3这点的权值最大，电脑选择此点。先行黑子进行防守白子继续冲4进攻先行黑子进行防守白子继续冲4进攻图冲4的情况这时冲4权值经计算最大，故电脑选择此点。黑子率先冲三电脑选择防守黑子率先冲三电脑选择防守图防守的情况5调试分析在调试过程出我的算法出了点问题，特别是对于紧迫点权值的计算，之后同学求助于CSDN上面的帖子，我修改了自己的算法。并理解了算法实现要领：电脑下子实际上是分两个步骤的，第一个步骤是尽可能的收集棋盘格局的信息，并且使这些信息以一定的格式存放再内存中，以便于第二步的处理。第二个步骤就是，对收集到的信息进行分析处理，即要给出一个规则，用穷举搜索的办法遍历所有收集到的信息，搜索的过程实际上是用所定下的规则去衡量每一点的权值，搜索的目的是为了找到一个权值最大的点，这个点就是当前的最优解，也就是应该下的子。举个例子来说：如果在第一步中，先遍历棋盘上的每一个点，即对于每一个点，我们假定这个点放上黑子，这时候就判断这个黑子放上去后，会形成多少个活2、活3、活4和5子连珠，然后把对应的数值记下，然后再假定这个点放白棋，又会形成多少个活2、活3、活4和五，当然你也可以用两个下面就是如何利用所得到的信息去下棋了：这个过程也是遍历分析所得的信息的过程。对上面的信息，我们可以很好的处理。比如，假定四三是必胜的，则我们给他的权值就很大比如100吧，而活二给的权值应该比较小，就给1吧。然后你可以得到一个权值的计算公式，举例说：权值＝活二的个数×1+活三的个数×5+活四的个数×10+四三的个数×100就是类似这样的公式，只要得出权值最大点，并判断己方下个子的权值大于对手的URGENTPOINT的权值的话，这个位置就是你下一步所要下子的点。下棋是就是遍历每一个点的信息，对每一个点计算权值，找到权值最大的就是要下的点了。上面说了用两个数组分别保存黑子和白子的信息也是有必要的，因为可以计算出某一点对黑白双方的重要程度。就是说如果轮到你下白子了，你光看哪一点对白子有利也不行呀，还要看哪些点对黑子有利，并且要比较这种有利的程度。如果你放某一点能成活3，而别人放另一点就是四三了，你就要抢先吧那一点占了。如上算法既考虑了对手的权值，也考虑了自己紧迫点的权值，通过赋予不同紧迫点不同的权值，综合起来且根据总和来确定自己的下子点，由此而实现了人机的对弈。通过如下计算公式求出了最紧急的下子点：当遇到问题时，我求助于论坛，与许多人交流了有关人工智能算法的思想，许多程序员回了帖子，并教了我许多技巧，我很感谢他们。这个五子棋本来是没有声音的，我觉得缺乏趣味，于是便添加了一些声音文件，当出现重复地点下子的ERROR，获胜以及重新开始游戏时，都会有一小段音效，我想这也许也会是一点小小的改变吧。6总结为期1个学期的程序设计课，学到的是我大学中最受益的东西。首先，在知识方面，我了解了许多C++MFC的知识以及相关应用。对系统的完成五子棋这个小游戏有了深刻的认识。这次的课程设计，不仅令我掌握了五子棋的人工智能算法，同时也培养了我的动手和实践创新能力。我学会了如何把理论用于实际应用中去。我深深的感到独立思考，与他们探讨，一起研究一个项目是多么快乐的事情。当我在设计过程中出现困难，并出现疑惑时，我求助于老师，并且通过GOOGLE获取了许多有助于我程序设计课题的相关知识。谷歌为我们中国乃至全世界学生提供了一