山东凯文科技职业学院
20##届毕业论文
基于Visual C++的五子棋游戏设计
——主要算法的设计与实现
学 院： 信息学院
学生姓名： XXX
指导教师： 张老师
专 业： 软件技术
班 级： 08软件1班
完成时间： 20##年6月29日
摘 要
本论文主要阐述以面向对象的程序开发语言VC++为开发工具,设计一个五子棋游戏。本系统是个小型游戏，可以单机使用，也可以网络两个人游戏，也可以和电脑进行游戏。论文首先介绍了开发背景及开发语言的介绍。然后介绍设计该游戏的框架结构，然后介绍了程序的设计过程，以及程序的相关算法。其中算法是我主要负责的，算法（Algorithm）是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
关键词：游戏,系统,图片,算法, Visual C++
Abstract
This paper mainly expounds on object-oriented programming language for development tools, design of vc + + a renju game. This system is a small game, can use single, also can network two game, can also and computer games. It firstly introduces the development background and development of language is introduced. And then introduced the design frame structure of the game, then introduces the design process of the program, and the related algorithm procedures. Among them is I mainly responsible for the Algorithm, the Algorithm (done) is a series of the solution to the problem of clear instructions, the Algorithm represents a systematic approach describe the solving strategy mechanism. That is, to some of the standard input, in limited time get required output. If an algorithm with a defect, or is not suitable for a problem is, carry out the algorithm will not solve the problem. Different algorithm may use different time, space or efficiency to complete the same task.
Keywords: The game, the system, pictures,algorithm, Visual C + +
目 录
1引言... 1
1.1 五子棋介绍... 1
1.2 开发背景... 1
1.3 开发环境及运行环境... 1
1.3.1 开发环境... 1
1.3.2 运行环境... 1
2 C++简介... 2
3 软件架构... 2
3.1 棋盘类... 3
3.2 游戏模式类... 3
4 主要算法... 4
4.1 判断胜负... 4
4.2 人机对弈算法... 6
4.2.1 获胜组合... 6
4.2.2 落子后处理... 7
4.2.3 查找棋盘空位... 7
4.2.4 落子打分... 8
4.2.5 防守策略... 10
4.2.6 选取最佳落子... 11
4.2.7统计数据... 11
5 几点补充说明... 15
6 心得体会... 15
参考文献... 16
致谢... 16
1引言
1.1 五子棋介绍
五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”（Five in a Row的缩写），亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。
五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。
1.2 开发背景
当前网络上流传的五子棋游戏功能并不尽善尽美，其中最主要的问题就是人机对战和网络对战不能够一起实现，所以我决定开发[1]一个既能够人机对战，又能够进行网络对战的五子棋系统。
1.3 开发环境及运行环境
1.3.1 开发环境
l Intel® Pentium® Y450，2G内存，320G硬盘
l Microsoft® Windows? XP Professional
l Microsoft® Visual C++ 6.0
l Microsoft® Developer Network for Visual Studio.NET 2003
l Visual Assist X 10.1.1301.0
1.3.2 运行环境
l Intel® Pentium® 2及以上处理器，32M以上内存，4G以上硬盘
l Microsoft® Windows? 9X/NT操作系统
l 800*600或以上的屏幕分辨率
2 C++简介
语言之所以要起名为“C”，是因为它是主要参考那个时候的一门叫B的语言，它的设计者认为C语言是B语言的进步，所以就起名为C语言；但是B语言并不是因为之前还有个A语言，而是B语言的作者为了纪念他的妻子，他的妻子名字的第一个字母是B； 当C语言发展到顶峰的时刻，出现了一个版本叫C with Class，那就是C++最早的版本，在C语言中增加class关键字和类，那个时候有很多版本的C都希望在C语言中增加类的概念；后来C标准委员会决定为这个版本的C起个新的名字，那个时候征集了很多种名字，最后采纳了其中一个人的意见，以C语言中的++运算符来体现它是C语言的进步，故而叫C++，成立了C++标准委员会。
C++是一种语言，仅仅是它的语法、特性、标准类库就已经是一门非常高深的课程，C++设计成静态类型、和C同样高效且可移植的多用途程序设计语言。设计成直接的和广泛的支援多种程序设计风格（程序化程序设计、资料抽象化、面向对象程序设计、泛型程序设计）。设计成给程序设计者更多的选择，即使可能导致程序设计者选择错误。设计成尽可能与C兼容，籍此提供一个从C到C++的平滑过渡。避免平台限定或没有普遍用途的特性。不使用会带来额外开销的特性。设计成无需复杂的程序设计环境。
C++标准演变了许多年。C++模板是近几年来对此语言的一种扩展，模板是根据类型参数来产生函数和类的机制，有时也称模板为“参数化的类型”。使用模板，可以设计一个对许多类型的数据进行操作的类，而不需要为每个类型的数据建立一个单独的类。标准模板库(Standard Tempalte Library，STL )和微软的活动模板库(Active Tempalte Library，ATL )都基于这个C++语言扩展。
C++标准可分为两部分， C++语言本身和C++标准库。C++标准库对于Visual C++是相当新的，实际上微软只是在发布Visual C++ 5.0时去除了一些“bug”。标准库提供了标准的输入/输出、字符串、容器(如矢量、列表和映射等)、非数值运算(如排序、搜索和合并等)和对数值计算的支持。应该说， C/C++包含了相对少的关键字，而且很多最有用的函数都来源于库，C++标准库实现容器和算法的部分就是STL。
STL是数据结构和算法的一个框架，数据结构包括矢量、列表和映射等，算法包括这些数据结构的查找、拷贝和排序等。1994年7月，ANSI/ISO C++标准委员会投票决定接受STL为C++标准库的一部分，这个建议是根据Alex Stepanov、Meng Lee和David Musser这三人的编程和软件库研究提出的。STL的产生是为了满足通用性的设计目标，而不是为了提高性能。
3 软件架构
软件的总体架构如图3.1：
图3.1 软件架构
考虑到整个的下棋过程（无论对方是电脑抑或其他网络玩家）可以分为：己方落子、等待对方落子、对方落子、设置己方棋盘数据这一系列过程，因此一人游戏类、二人游戏类和棋盘类之间的关系参考了AbstractFactory（抽象工厂）模式，以实现对两个不同模块进行一般化的控制。[2]
3.1 棋盘类
整个架构的核心部分，类名为CTable。封装了棋盘的各种可能用到的功能[3]，如保存棋盘数据、初始化、判断胜负等。用户操作主界面，主界面与CTable进行交互来完成对游戏的操作。
3.2 游戏模式类
用来管理人机对弈/网络对弈两种游戏模式，类名为CGame。CGame是一个抽象类，经由它派生出一人游戏类COneGame和网络游戏类CTwoGame，如图3.2：
图3.2 CGame类派生关系
这样，CTable类就可以通过一个CGame类的指针[4]，在游戏初始化的时候根据具体游戏模式的要求实例化COneGame或CTwoGame类的对象；然后利用多态性[5]，使用CGame类提供的公有接口就可以完成不同游戏模式下的不同功能了。
4 主要算法
五子棋游戏中，有相当的篇幅是算法的部分。无论是人机对弈，还是网络对弈，都需要合理算法的支持，本节中将详细介绍五子棋中使用的算法。[13]
4.1 判断胜负
五子棋的胜负，在于判断棋盘上是否有一个点，从这个点开始的右、下、右下、左下四个方向是否有连续的五个同色棋子出现，如图4.1：
图4.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_data[x][y] &&
color == m_data[x + 1][y] &&
color == m_data[x + 2][y] &&
color == m_data[x + 3][y] &&
color == m_data[x + 4][y] )
{
return TRUE;
}
}
}
// 判断纵向
for ( y = 0; y < 11; y++ )
{
for ( x = 0; x < 15; x++ )
{
if ( color == m_data[x][y] &&
color == m_data[x][y + 1] &&
color == m_data[x][y + 2] &&
color == m_data[x][y + 3] &&
color == m_data[x][y + 4] )
{
return TRUE;
}
}
}
// 判断“\”方向
for ( y = 0; y < 11; y++ )
{
for ( x = 0; x < 11; x++ )
{
if ( color == m_data[x][y] &&
color == m_data[x + 1][y + 1] &&
color == m_data[x + 2][y + 2] &&
color == m_data[x + 3][y + 3] &&
color == m_data[x + 4][y + 4] )
{
return TRUE;
}
}
}
// 判断“/”方向
for ( y = 0; y < 11; y++ )
{
for ( x = 4; x < 15; x++ )
{
if ( color == m_data[x][y] &&
color == m_data[x - 1][y + 1] &&
color == m_data[x - 2][y + 2] &&
color == m_data[x - 3][y + 3] &&
color == m_data[x - 4][y + 4] )
{
return TRUE;
}
}
}
// 不满足胜利条件
return FALSE;
}
需要说明的一点是，由于这个算法所遵循的搜索顺序是从左到右、自上而下，因此在每次循环的时候，都有一些坐标无需纳入考虑范围。例如对于横向判断而言，由于右边界所限，因而所有横坐标大于等于11的点，都构不成达到五子连的条件，所以横坐标的循环上界也就定为11，这样也就提高了搜索的速度。
4.2 人机对弈算法
人机对弈算法完全按照CGame基类定义的接口标准，封装在了COneGame派生类之中。下面将对这个算法进行详细地介绍。[14]
4.2.1 获胜组合
获胜组合是一个三维数组，它记录了所有取胜的情况。也就是说，参考于CTable::Win中的情况，对于每一个落子坐标，获胜的组合一共有
15 * 11 * 2 + 11 * 11 * 2 = 572种。
而对于每个坐标的获胜组合，应该设置一个[15][15][572]大小的三维数组。
在拥有了这些获胜组合之后，就可以参照每个坐标的572种组合给自己的局面和玩家的局面进行打分，也就是根据当前盘面中某一方所拥有的获胜组合多少进行权值的估算，给出最有利于自己的一步落子坐标。
由于是双方对弈，所以游戏的双方都需要一份获胜组合，也就是：
bool m_Computer[15][15][572]; // 电脑获胜组合
bool m_Player[15][15][572]; // 玩家获胜组合
在每次游戏初始化（COneGame::Init）的时候，需要将每个坐标下可能的获胜组合都置为true。
此外，还需要设置计算机和玩家在各个获胜组合中所填入的棋子数：
int m_Win[2][572];
在初始化的时候，将每个棋子数置为0。
4.2.2 落子后处理
每当一方落子后，都需要作如下处理：
l 如果己方此坐标的获胜组合仍为true，且仍有可能在此获胜组合处添加棋子，则将此获胜组合添加棋子数加1；
l 如果对方此坐标的获胜组合仍为true，则将对方此坐标的获胜组合置为false，并将对方此获胜组合添加棋子数置为-1（不可能靠此组合获胜）。
以玩家落子为例，代码为：
for ( i = 0; i < 572; i++ )
{
// 修改状态变化
if ( m_Player[stepPut.x][stepPut.y][i] &&
m_Win[0][i] != -1 )
m_Win[0][i]++;
if ( m_Computer[stepPut.x][stepPut.y][i] )
{
m_Computer[stepPut.x][stepPut.y][i] = false;
m_Win[1][i] = -1;
}
}
4.2.3 查找棋盘空位
在计算机落子之前，需要查找棋盘的空位，所以需要一个SearchBlank成员函数完成此项工作，此函数需要进行不重复的查找，也就是说，对已查找过的空位进行标记，并返回找到空位的坐标，其代码如下：
bool COneGame::SearchBlank( int &i, int &j,
int nowTable[][15] )
{
int x, y;
for ( x = 0; x < 15; x++ )
{
for ( y = 0; y < 15; y++ )
{
if ( nowTable[x][y] == -1 && nowTable[x][y] != 2 )
{
i = x;
j = y;
return true;
}
}
}
return false;
}
4.2.4 落子打分
找到空位后，需要对这个点的落子进行打分，这个分数也就是这个坐标重要性的体现，代码如下：
int COneGame::GiveScore( const STEP& stepPut )
{
int i, nScore = 0;
for ( i = 0; i < 572; i++ )
{
if ( m_pTable->GetColor() == stepPut.color )
{
// 玩家下
if ( m_Player[stepPut.x][stepPut.y][i] )
{
switch ( m_Win[0][i] )
{
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_Computer[stepPut.x][stepPut.y][i] )
{
switch ( m_Win[1][i] )
{
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.2.5 防守策略
落子的考虑不单单要从进攻考虑，还要从防守考虑。这一细节的实现其实就是让计算机从玩家棋盘布局分析战况，然后找出对玩家最有利的落子位置。整个过程如下：
for ( m = 0; m < 572; m++ )
{
// 暂时更改玩家信息
if ( m_Player[i][j][m] )
{
temp1[n] = m;
m_Player[i][j][m] = false;
temp2[n] = m_Win[0][m];
m_Win[0][m] = -1;
n++;
}
}
ptempTable[i][j] = 0;
pi = i;
pj = j;
while ( SearchBlank( i, j, ptempTable ) )
{
ptempTable[i][j] = 2; // 标记已被查找
step.color = m_pTable->GetColor();
step.x = i;
step.y = j;
ptemp = GiveScore( step );
if ( pscore > ptemp ) // 此时为玩家下子，运用极小极大法时应选取最小值
pscore = ptemp;
}
for ( m = 0; m < n; m++ )
{
// 恢复玩家信息
m_Player[pi][pj][temp1[m]] = true;
m_Win[0][temp1[m]] = temp2[m];
}
4.2.6 选取最佳落子
在循环结束的时候，就可以根据攻、守两方面的打分综合地考虑落子位置了。代码如下：
if ( ctemp + pscore > cscore )
{
cscore = ctemp + pscore;
bestx = pi;
besty = pj;
}
在这之后，重新改变一下棋盘的状态（4.2.2）即可。
4.2.7统计数据
在对战结束的时候我们可以查询一下我们的胜率和一些别的战斗情况。
代码如下：
CStatDlg::CStatDlg(CWnd* pParent /*=NULL*/)
: CDialog(CStatDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CStatDlg)
// NOTE: the ClassWizard will add member initialization here
//}}AFX_DATA_INIT
}
void CStatDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CStatDlg)
// NOTE: the ClassWizard will add DDX and DDV calls here
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CStatDlg, CDialog)
//{{AFX_MSG_MAP(CStatDlg)
ON_BN_CLICKED(IDC_BTN_RESET, OnBtnReset)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
// CStatDlg message handlers
BOOL CStatDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// TODO: Add extra initialization here
// 读取姓名
CTable *pTable = (CTable *)GetParent()->GetDlgItem( IDC_TABLE );
SetDlgItemText( IDC_ST_NAME, pTable->m_strMe );
ShowStat();
return TRUE;
// return TRUE unless you set the focus to a control
// EXCEPTION: OCX Property Pages should return FALSE
}
void CStatDlg::OnOK()
{
// TODO: Add extra validation here
CFiveApp *pApp = (CFiveApp *)AfxGetApp();
// 写入战绩统计
TCHAR str[10];
wsprintf( str, _T("%d"), pApp->m_nWin );
::WritePrivateProfileString( _T("Stats"), _T("Win"), str, pApp->m_szIni );
wsprintf( str, _T("%d"), pApp->m_nDraw );
::WritePrivateProfileString( _T("Stats"), _T("Draw"), str, pApp->m_szIni );
wsprintf( str, _T("%d"), pApp->m_nLost );
::WritePrivateProfileString( _T("Stats"), _T("Lost"), str, pApp->m_szIni );
CDialog::OnOK();
}
void CStatDlg::OnBtnReset()
{
// TODO: Add your control notification handler code here
CFiveApp *pApp = (CFiveApp *)AfxGetApp();
pApp->m_nWin = 0;
pApp->m_nDraw = 0;
pApp->m_nLost = 0;
ShowStat();
}
void CStatDlg::ShowStat()
{
CFiveApp *pApp = (CFiveApp *)AfxGetApp();
CString str;
str.Format( _T("%d"), pApp->m_nWin );
SetDlgItemText( IDC_ST_WIN, str );
str.Format( _T("%d"), pApp->m_nDraw );
SetDlgItemText( IDC_ST_DRAW, str );
str.Format( _T("%d"), pApp->m_nLost );
SetDlgItemText( IDC_ST_LOST, str );
// 计算胜率
if ( 0 == pApp->m_nWin )
{
str = _T("胜率：0%");
}
else
{
str.Format( _T("胜率：%d%%"), pApp->m_nWin * 100 / ( pApp->m_nWin + pApp->m_nDraw + pApp->m_nLost ) );
}
SetDlgItemText( IDC_ST_PERCENT, str );
}
代码执行后的效果图如下：
图4.2 效果图
5 几点补充说明
l 考虑到程序的响应速度，人机对弈算法只对玩家的棋子进行了一步的推测。
l 由于计算机在落子时选取的是得分最高的一步落子，所以如果玩家在开局的时候不改变落子步骤，那么将会获得从头至尾相同的棋局。
l 考虑到下棋同时还要聊天，所以并未对落子时间加入任何限制，同样如果玩家离开游戏也不会判负。
l 对于人机对弈的悔棋处理，由于这个算法的开销相当大，每一步落子都会存在不同的棋盘布局，所以实现从头到尾的悔棋不是很现实（将会存在过多的空间保存棋盘布局），因而在人机对弈模式下，只允许玩家悔最近的两步落子。
6 心得体会
经过这段时间的紧张忙碌，这次的毕业设计已制作了一个较完整的五子棋游戏，从各方面来讲，都有比较大的收获，同时也大大提高了实际操作的能力，当然，期间遇到的困难也是层出不穷。由于对游戏的概念比较模糊，在前期的编程设计过程中脑海中仅仅有一个框架，而很多却细节没有考虑到，结果一度走入一边编程，一边改模版的尴尬境地，进度缓慢，思路不清。后来，在艰难进展的过程中渐渐领悟到了一些编程的方法和系统设计的思想，所谓眼过千遍不如手过一遍，在自己实际操作中暴露出来的问题自己的体会最深刻，也就更有想法去克服他。在困境中摸索，总结，转变思路，继续前进，这是对我制作本游戏过程的一个概括。
在不断的学习与改进中我体会到：
1.做毕业设计本身也是一个学习新鲜事物的过程，从设计初的不懂到最后顺利完成设计，我体会到在实践中学习的重要性，我想这对于我以后的工作受益匪浅。
2.设计的过程是漫长而困难重重的，设计过程中需要理论与实际的结合，这就要求有扎实的理论知识，灵活的头脑，我本身所做的设计并不算十分复杂，但由于以前没有独立做过系统所以刚开始时有点乱，好在有老师的帮助，我很快理清了思路，找到了自己的出发点。
3.由于前期工作的不彻底，对系统的需求分析的要求认识不够清楚，使得后续的工作不得不经常返回去修改个别代码。使我体会到在设计中的每一步的重要性，如果上一个步骤不能很好的完成，在后续的设计将会付出几倍的代价。
总之，经过这么长时间的设计，我与我的同学完成了这个一个功能比较完善的五子棋游戏。我深刻体会到要做好一个完整的事情，需要有系统的思维方式和方法，还要有一个团队合作的精神。对待一个新的问题，要耐心、要细心，也要有很好的团结，共同努力的团队协作精神。
参考文献
[1] MSDN for Visual Studio 6.0
[2] 设计模式——可复用面向对象软件的基础，Erich Gamma/Richard Helm/Ralph Johnson/John Vlissides著，李英军/马晓星/蔡敏/刘建中 等译，机械工业出版社
[3] 深入浅出MFC（第2版），侯俊杰著，华中科技大学出版社
[4] Microsoft® Visual C++.NET 技术内幕（第6版），George Shepherd/David Kruglinski著，潘爱民译，清华大学出版社
[5] Visual C++网络通信协议分析与应用实现，汪晓平/钟军 等编著，人民邮电出版社
[6] C++编程思想，Bruce Eckel著，刘宗田/邢大红/孙慧杰 等译，机械工业出版社
[7] 21天学通C++，Jesse Liberty著，康博创作室译，人民邮电出版社
[8] C++标准程序库，Nicolai M.Josuttis著，侯捷/孟岩 译，华中科技大学出版社
[9] Windows程序设计，Charles Petzold著，北京博彦科技发展有限公司译，北京大学出版社
[10] Visual C++.NET网络编程，易君 编著，中国铁道出版社
[11] 五子棋的核心算法，蝈蝈俊.net
http://blog.joycode.com/ghj/articles/12727.aspx
致谢
本设计的完成是在我们的导师张老师的细心指导下进行的。在每次设计遇到问题时老师不辞辛苦的讲解才使得我的设计顺利的进行。从设计的选题到资料的搜集直至最后设计的修改的整个过程中，花费了张老师很多的宝贵时间和精力，在此向导师表示衷心地感谢！导师严谨的治学态度，开拓进取的精神和高度的责任心都将使学生受益终生！