毕业设计（论文）基于VisualC++的五子棋设计与实现.doc

太原科技大学毕 业 设 计（论 文）设计(论文)题目：基于Visual C+的五子棋设计与实现姓 名_ _学院（系）_电子信息工程系_专 业_ 通信工程_年 级_ 通信082201H_ 指导教师_ _2012年 6 月 14 日 太原科技大学毕业设计（论文）任务书学院（直属系）：电子信息工程系 时间： 2012年1月14日学 生 姓 名陈磊指 导 教 师司秉楠设计（论文）题目基于Visual C+的五子棋设计与实现主要研究内容学习C+编程语言，在Visual C+6.0环境中实现五子棋的设计。研究方法通过Visual C+6.0编写程序和编译程序，并成功运行五子棋游戏，实现五子棋的相关功能。主要技术指标(或研究目标)1.掌握Visual C+6.0的应用，并进行程序的编译和运行。2.编写五子棋的相关程序，以实现五子棋的走棋、悔棋、判断输赢、英雄榜记录等功能。教研室 意见 教研室主任（专业负责人）签字： 年 月 日说明：一式两份，一份装订入学生毕业设计（论文）内，一份交学院（直属系）目录摘要ABSTRACT第1章 绪论-1- 1.1课题背景-1- 1.2五子棋介绍-1- 1.3目的和意义-2- 1.4系统设计思想-3- 1.5开发工具简介-3-第2章 可行性研究与算法分析-5- 2.1本系统的可行性研究-5- 2.2算法分析-6- 2.2.1博弈树-6- 2.2.2极大极小值算法-7- 2.2.3负极大值算法-8- 2.2.4 ALPHA-BETA搜索-8- 2.2.5 置换表-9- 2.2.6 哈希表-10- 2.2.7 历史启发-11- 2.3 本章小结-12-第3章 总体设计-13- 3.1 总体设计过程-13- 3.2 系统的数据结构设计-13- 3.2.1 系统的数据结构设计-13- 3.2.2 系统的算法设计-14- 3.3 系统模型设计-15- 3.4 本章小结-16-第4章 详细设计-17- 4.1系统运行平台设计-17- 4.2系统的程序流程图-17- 4.3系统主要功能的实现-18- 4.3.1 新局-18- 4.3.2 菜单及提示-20- 4.3.3 游戏结束-23- 4.3.4 英雄榜-24- 4.4本章小结-26-第5章 系统测试-27- 5.1系统软件测试-27-结论-30-致谢-32-参考文献-33-附录-34-摘要 自从计算机作为游戏对战平台以来，各种棋类游戏如雨后春笋般纷纷冒出。使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而五子棋游戏由于其规则简单，变化多端，深受大众喜爱。 五子棋不仅能增强人们的抽象思维能力、逻辑推理能力、空间想象力，提高人们的记忆力、心算能力等，而且深含哲理，有助于修身养性。它既有简单易学的特点，为人民群众所喜闻乐见，又有深奥的技巧。既能组织群众性的比赛、活动，又能举办高水平的国际性比赛。 基于五子棋游戏以上的优点，开发五子棋是一个非常有价值的课题。本系统具有功能齐全、简单易学、既动手又动脑的特点。尤其是游戏的同时，还有声音效果的配合，使游戏更加富有趣味性和消遣性。本系统基于Visual C+6.0软件，主要应用估值函数、负极大值搜索算法、Alpha-Beta剪枝等算法来完成人机对弈功能的实现。本系统的成功开发，能够使人们的日常娱乐生活更加丰富多彩。关键词:五子棋；国际性比赛；人机对弈；Visual C+6.0AbstractSince the computer as a game platform, various board games have mushroomed out. Makes those who love chess, and often do not have the Jimi opponents will be able to keep a full game addiction. Gobang game and its rules are simple, making love by the public. Gobang can not only enhance people's ability to abstract thinking, logical reasoning, spatial imagination and enhancing people's memory, mental arithmetic ability, but also with deep philosophical, self-help and support. It has easy to learn the characteristics of the eye and ear, other esoteric skills. Can organize the masses of competitions, activities, but also organized a high level of international competition. Gobang game based on the merits of the above, the development of Gobang is a very valuable subject. The system is fully functional, easy to learn, hands and both mental and physical characteristics. Especially games at the same time, there are sound effects with them to games more interesting and full of fun. Application of this system is mainly valuation function, the negative Maxima search algorithm, such as Alpha-Beta search algorithm to complete the function of the realization of human chessboard. The successful development of the system will enable people's daily life more colorful entertainment.Key words:Gobang International Competition Human Chessboard Visual C+6.0基于Visual C+的五子棋设计与实现第1章绪论1.1课题背景计算机技术的发展，使得计算机在现代企业、家庭中得以普及，应用计算机成为现代人生活中非常重要的一部分。大到政府办公、教育事业、商业活动，小到生活中的每一个细节。随着社会进步的节奏越来越快，人们的生活压力也越来越大。每天奔波于不同的目的地，忙得没有时间和朋友见面，忙得想找个释放压力的机会都没有。这个时候，你是不是非常希望有个游戏，能够陪你轻松愉快度过周末。自从计算机作为游戏对战平台以来，各种棋类游戏如雨后春笋般纷纷冒出。使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾，而且这类软件大都水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表。五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。同时具有简单易学、既动手又动脑的特点。1.2五子棋介绍五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”(Five In a Row的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。相传早在尧造围棋之前，五子棋游戏在民间已经相当盛行了。据增山海经中记载：“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。”辞海中亦言：“五子棋中棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。”唐时由高丽使者带到高丽，后来辗转反复，流传到日本。起先是在日本皇宫内盛行的游戏，只限于王室成员、贵族阶层之间的对弈，后来据说被出入皇宫的挑夫看见，由此便流行民间。五子棋起源于古代中国，发展于日本，风靡于欧洲。对于它与围棋的关系有两种说法，一种说法是早于围棋，早在“尧造围棋”之前，民间就已有五子棋游戏；另一说法是源于围棋，是围棋发展的一个分支。在中国的文化里，倍受人们的青睐。古代的五子棋的棋具与围棋相同，纵横各十七道。五子棋大约随围棋一起在我国南北朝时先后传入朝鲜、日本等地。据日本史料文献介绍，中国古代的五子棋是经由高丽(朝鲜)，于1688年至1704年的日本元禄时代传到日本的。到日本明治32年(公元1899年)，经过公开征名，“连珠”这一名称才被正式确定下来，取意于“日月如合壁，五星如连珠”。从此，连珠活动经过了不断的改良，主要是规则的变化(即对执黑棋一方的限制)。例如，1899年规定，禁止黑白双方走“双三” ；1903年规定，只禁止黑方走“双三” ；1912年规定，黑方被迫走“双三”亦算输；1916年规定，黑方不许走“长连” ；1918年规定，黑方不许走“四、三、三” ；1931年规定，黑方不许走“双四” ，并规定将19×19的围棋盘改为15×15的连珠专用棋盘。本世纪初五子棋传入欧洲并迅速风靡全欧。通过一系列的变化，使五子棋这一简单的游戏复杂化、规范化，而最终成为今天的职业连珠五子棋，同时也成为一种国际比赛棋。现代五子棋（连珠）的基本下法是：先由执黑棋一方将一枚棋子落在天元点上，为了尊重对方和出于礼貌，持白棋的一方通常将盘面的第二手棋布在天元下方周围。1.3目的和意义五子棋游戏不仅能增强人们的抽象思维能力、逻辑推理能力、空间想象力，提高人们的记忆力、心算能力等，而且深含哲理，有助于修身养性。五子棋既有现代休闲方式所特有的特征“短、平、快” ，又有中国古典哲学所包含的高深学问“阴阳易理” ；它既有简单易学的特点，为人民群众所喜闻乐见，又有深奥的技巧；既能组织举办群众性的比赛、活动，又能组织举办高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观，它是中西方文化的交融点，也是中西方文化交流的一个平台。五子棋的根在中国，在这个国境里，他有着广泛的群众基础。但与世界先进的五子棋技术相比，我们的棋艺水平还要继续提高，所以我们要推广五子棋，宣传五子棋，争取在较短的时间内赶上和超过世界五子棋坛的先进水平。在这种环境下，开发一个易学实用的五子棋游戏软件是很有必要的。中国作为五子棋的发源国，要对五子棋在下个世纪的发展起到世界性的推动作用。五子棋的发展在中国出现方兴未艾、星火燎原之势。同时还有一大批的中生代棋手和充满希望的“明日之星”。相信，中国棋手攀登五子棋巅峰的日子会早日来到。1.4系统设计思想一个优秀的游戏软件，必须有一个正确的设计思想，通过合理地选择数据结构、操作系统以及开发环境，构成一个完善的体系结构，才能充分发挥计算机应用的优势。根据游戏玩家的实际需求，本系统的设计按照下述原则进行。（1）实用性：系统以用户需求为目标，以方便用户为原则，同时融入先进的设计思想。根据用户实际的需求情况，量身制作一个功能齐全、操作简单、实用性强的游戏软件。充分满足游戏玩家的需求，真正成为为玩家提供轻松、娱乐、休闲的工具。（2）先进性：本软件将充分应用现有成熟的计算机技术、软件开发技术，为用户提供高性能的系统，可以方便的实现玩家的需要。（3）高可靠性：一个实用的系统同时必须是可靠的，本系统通过合理而先进的结构设计以及软、硬件的优化选型，可保证系统的可靠性与容错性。（4）可维护性：系统的设计要求方便维护，包括硬件的维护，软件的维护（更改，升级等）。（5）可扩展性及灵活性：系统的设计以方便未来业务的扩展和系统扩充为目标，系统要求能够方便的升级，充分保护系统的投资。玩家可以根据自己的需要，灵活设置自己的游戏。（6）智能性：智能化是这个游戏软件的一大特色。系统在设计时，充分考虑系统运行的智能性，如果有充足的时间改进，计算机就可以实现更高的AI，在游戏中走的每一步就会考虑得更周密。1.5开发工具简介Visual C+6.0是Microsoft公司开发的基于C/C+的面向对象的可视化集成开发工具，它是Visual Studio中功能最为强大、代码效率最高的开发工具。Visual C+6.0与以前的版本相比有了多方面的改进。它的编译器、调试器、连接器、编辑器、资源编辑器都有所加强。在编辑器中还提供了自动语句生成功能，编辑器会像Visual Basic一样自动提示函数的参数、对象的成员。另外，Visual C+ 6.0还提供了很多向导。MFC提供了一些新的类，提供了更强大的数据访问功能。用户可利用Visual C+6.0以两种方式编写Win32应用程序，一种方式是基于Windows API的C编程方式，另一种是基于MFC的C+编程方式。Visual C+ 6.0的主要特点如下：Visual C+ 6.0的最大特色就是提供面向对象技术的支持，它利用类把大部分与用户界面设计有关的Windows API函数封装起来，通过MFC（Microsoft Foundation Class）类库的方式提供给开发人员使用，大大提高了程序代码的重用性。Visual C+ 6.0提供一个功能强大的应用程序生成向导AppWizard，这也是其得意之处。有了AppWizard，用户将不会为创建繁琐的初始化代码而苦恼。AppWizard将帮助MFC类库的用户自动生成一个运行程序框架一个空的不能做任何事情的应用程序，而用户只需要在该框架的适当部分添加扩充代码就可以得到一个满意的应用程序。Visual C+ 6.0的另一个强大工具就是Class Wizard，用户通过它能够方便而有效地使用和管理MFC类库。以前，继承和派生一个类是一件很麻烦的事，而现在简单了，只需在Class Wizard中指定一些必要信息，Visual C+ 6.0将自动为你生成类的框架和代码。Visual C+ 6.0利用“所见即所得”的方式完成程序界面的设计，大大减轻了程序设计人员的劳动强度，提高了开发效率。Visual C+ 6.0的功能强大，用途广泛。不仅可以编写普通的应用程序，还能很好的进行系统及通信软件的开发。第2章可行性研究与算法分析2.1本系统的可行性研究本系统要实现的目标：作为一个悠闲的小游戏软件，首先应该为用户提供一套方便的操作方法，在游戏模式、用户操作、反馈信息方面应该有明确的说明，能够让大多数玩家能快速上手，使该游戏看上去是一款悠闲的精品。本系统的流程图描述如下：玩家在新开局后，可以设置本局游戏，包括对弈模式、游戏级别、中英文菜单、声音效果等进行设置，即初始化棋盘。初始化棋盘完成后，玩家和计算机就可以在分析了当前棋局以后下棋，即对弈阶段。在玩家和计算机每下了一手棋以后，都会进行胜负的判断，如有胜负，则结束此局游戏。如果此局玩家的成绩比英雄榜里的成绩更好，则把玩家的姓名和成绩记录到英雄榜中，覆盖原来的玩家名和成绩。本游戏软件的系统流程图，如图2.1所示。图2.1系统流程图本系统是一款休闲的小游戏，是人们日常生活娱乐的工具。只要针对大众的喜好，使系统功能齐全，操作简单，界面美观大方，就一定会有市场潜力。根据该系统目标来衡量所需的技术是否具备，一般可从软硬件的性能要求、环境条件、操作人员水平和数量等方面去考虑和分析。考虑到系统实施的可行性，在软件方面选择了性能稳定的VC+6.0开发环境、C+语言来进行开发。VC+是非常成熟的开发工具，因此无论在安全性、可用性及可靠性等方面都毫无置疑，因此软件方面是可行的。在硬件方面，则选择空间较大，只要是Pentium III系列及以上的计算机，内存在256M以上，硬盘在1GB，都可以满足系统的开发需要。当然，硬件的配置越高，系统的开发与运行会更流畅。考虑到如今的家用或商用电脑硬件的整体配置水平，系统在硬件方面是可行的。2.2算法分析五子棋游戏的开发在搜索算法方面，可以有多种选择。通过从不同的角度分析各种搜索方法的效率，来考虑本系统的算法应用。开局时计算机每走一步的平均耗时(ms)，如表2.1所示。表2.1各种算法每走一步平均耗时(ms) 通过上表，可以看出使用置换表技术和历史启发技术可以增强搜索效率。综合分析表中几种算法的效率，本系统按照计算机下每一手棋所应用的算法的大致顺序，采用的主要算法有博弈树、负极大值算法、Alpha-Beta剪枝算法、置换表技术、哈希表技术、历史启发等。下面详细地介绍一下这些算法。2.2.1博弈树设想下五子棋的情形，两人对弈，我们将其中一位叫做甲，另一位叫做乙。假定现在该甲下棋，甲可以有225种走法（不论好坏）；而对甲的任一走法，乙也可以有与之相对的若干种下法。然后又轮到甲走棋，对乙的下法甲又有若干种方法应对。如此往复。显然，我们可以依此构建一棵博弈树，将所有的走法罗列出来。在这棵树的根部是棋局的初始局面。根的若干子节点则是由甲的每一种可能走法所生成的局面，而这些节点的子节点则是由与之相对的乙的每一种可能走法所生成的局面。在这棵树的末梢，是结束的棋局，甲胜或者乙胜或者是双方都无法取胜的平局。如果我们令甲胜的局面值为WIN，乙胜的局面值为LOST，而和局的值为DRAW。当轮到甲走时，甲定会选择子节点值为WIN或DRAW（如果没有值为WIN的子节点的话）的下法；而轮到乙时，乙则会选择子节点值为LOST或DRAW（如果没有值为LOST的子节点的话）的下法。对于中间节点的值可以有如下计算方法：如果该节点所对应的局面轮到甲下棋，则该节点的值是其所有子节点中值最佳（对甲而言）的一个的值；如果该节点所对应的局面轮到乙走棋，则该节点的值是其所有子节点中值最差（对甲而言）的一个的值。这样看来从这棵树的叶子节点倒推向根部，就可以得出所有节点的值。双方就可以从其所面临的棋局中选择一步好棋。然后一步步走向胜利。博弈树是从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树，这里称为完全搜索树。Neill Graham形容此过程类似于在一个状态图中寻求从初始状态通向终了状态的过程。只是状态图搜索仅有一个主体参加，仅是单方面做出的路径选择。而博弈树的搜索则有对立的双方参加，一方只能做出一半选择，而这一半选择的目的是使对方远离其竭力靠近的目标。也就是说状态图搜索是纯粹的或树（OR tree），而博弈树搜索是与或树（AND/OR tree）。但是在五子棋游戏中，我们没有建立完全搜索树的可能。一方面是因为很多情形根本就到达不了叶子节点。另一方面，这棵树上的节点数量也已多到了无法处理的程度。所以我们需要其它的算法来减少搜索的数量。2.2.2极大极小值算法（Minimax Algorithm）在上面的博弈树中，如果我们令甲胜的局面值为1，乙胜的局面值为-1，而和局的值为0。当轮到甲下棋时，甲定会选择子节点值最大的下法；而轮到乙时，乙则会选择子节点值最小的下法。所以，对于中间节点的值可以有如下计算方法：如果该节点所对应的局面轮到甲下棋，则该节点的值是其所有子节点中值最大的一个的值。而如果该节点所对应的局面轮到乙下棋，则该节点的值是其所有子节点中值最小的一个的值。对博弈树的这个变化仅仅是形式上的，本质上丝毫未变，但是这个形式更容易推广以运用到一般实际的情形。既然建立整棵的搜索树不可能，那么，为当前所面临的局面找出一步好棋如何？也就是通过少量的搜索，为当前局面选择一步较好的走法。在通常的棋局当中，一个局面的评估往往并不像输、赢、平3种状态这么简单，在分不出输赢的局面中棋局也有优劣之分。也就是说，要用更细致的方法来刻画局面的优劣，而不是仅仅使用1、-1、0三个数字刻画3种终了局面。假定我们有一个函数可以为每一局面的优劣评分。例如甲胜为+；乙胜为-；和局为0；这样我们可以建立一棵固定深度的搜索树，其叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子节点的最小值。这个评分的函数称作静态估值函数（Static Evaluation Function）。用以取代超出固定深度的搜索。显然，我们无法拥有绝对精确的静态估值函数。否则，只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分，在此基础上进行的少量搜索的可靠性，理论上是不如前述的WIN，LOST，DRAW三种状态的博弈树的，但这个方法却是可实现的。利用具体的知识构成评估函数的搜索叫做启发式搜索（Heuristic Search）。估值函数在有些文献中也称为启发函数（Heuristic Function）。在博弈树搜索的文献当中，极大极小方法往往指的是基于静态估值函数的有限深度的极大极小搜索。MinMax算法是对弈的基础思想。2.2.3负极大值算法（Negamax Algorithm）普通的极大极小值算法看起来有一点笨，既然一方试图取极大值而另一方试图取极小值也就是说我们总要检查哪一方要取极大值而哪一方又要取极小值，以执行不同的动作。Knuth和Moore在1975年提出了负极大值（Negamax）方法，消除了两方的差别，而且简洁优雅。使用负极大值方法，博弈双方都取极大值。2.2.4Alpha-Beta搜索在极大极小搜索的过程中，存在着一定程度的数据冗余。举一个最简单的例子：在象棋博弈的过程中，如果某一个节点轮到甲走棋，而甲向下搜索节点时发现第一个子节点就可以将死乙（节点值为最大值），则剩下的节点就无需再搜索了，甲的值就是第一个子节点的值。这个过程，就可以将大量冗余的（不影响结果的）节点抛弃。图2.2A lpha-Beta剪枝示例图将上述这个情形推广一下，设想有如图2.1左半部所示的一棵极大极小树的片断，节点下面数字为该节点的值，节点B的值为18，节点D的值为16，由此我们可以判断节点C的值将小于等于16（取极小值）；而节点A的值为节点Max（B,C），为18，也就是说不再需要估算节点C的其他子节点如E、F的值就可以得出父节点A的值了。这样将节点D的后继兄弟节点减去称为Alpha剪枝（alpha cutoff）。设想有如图2-2右半部所示的一棵极大极小树的片断，节点B的估值为8，节点D的估值为18，由此我们可以判断节点C的值将大于等于18（取极大值）；而节点A的值为节点Min（B,C），为8。也就是说不再需要求节点C的其他子节点如E、F的值就可以得出父节点A的值了。这样将节点D的后继兄弟节点减去称为Beta剪枝（beta cutoff）。2.2.5置换表（Transposition Table）在极大极小搜索的过程中，改进搜索算法的目标在于将不必搜索的（冗余）分枝从搜索的过程中尽量剔除，以达到搜索尽量少的分枝来降低运算量的目的。在先前谈到的几种搜索算法中，我们看到可以通过 Alpha-Beta剪枝来剪除两种类型的冗余分枝/节点，但是已经搜索过的节点不可以免于搜索。从图2-2的极大极小树的片断中，我们可以看出，该片断从节点A开始，有两个分B和C（为简化问题，其他节点从略），B 有子节点D，C有子节点E，再往下D有子节点F，E有子节点G。读者可以看到，在极大极小树的不同分枝上，存在着完全相同的节点。在上图中，节点F和G完全相同。对于节点F，在搜索分枝的时候，就可能已经搜索过了。那么，在搜索节点G的子节点时，我们能不能直接利用已经搜索过的节点F的结果，而不是重新搜索一遍节点G？想法是可行的。如果要利用已经搜索过的节点的结果，我们就要用一张表把搜索过的节点记录下来。然后在后续的搜索中，察看记录在表中的这些结果，如果将要搜索的某个节点已有记录，就直接利用记录下来的结果。这种方法叫做置换表（Transposition Table，简称TT）。如果将Alpha-Beta搜索过程中每一节点的结果都记录下来，则在任意节点向下搜索之前先查看这些纪录，就可避免上述重复的操作。但是这个置换表如何实现的？困难集中在时间和空间复杂度上。1可能的节点可以认为是无穷多，将其存入一张表中要占据多少存储空间呢？2即使有无穷多内存空间，一个节点要从表中找到自己对应的一项，需要花费多少时间？虽然有序表可用二分查找等快速的算法，但要维持表中内容有序，又要进行大量排序操作，会耗费更多时间。如何解决？2.2.6哈希表（Hash Table）置换表的实现在时间和空间复杂度上的疑问。实际上已经明确了要实现置换表必须要满足如下条件：1查找记录中的节点数据时速度要非常快，最好是类似于随机存取。2将节点数据放入记录的速度也要非常快。这就意味着数据项插入的过程不可有数据移动排序等操作。3要能在有限的存储空间内进行。可以利用哈希表，哈希方法的思想为每一个学过数据结构或算法课程的开发人员所熟知。对棋类博弈来说，定义一个巨大的数组，将每一局面记入其中，每一局面在数组中对应惟一的位置。这样，将数据记入和取出就类似于随机读写，不会有耗时的查找和插入过程。但是，以象棋而论，如果为每一局面在数组中对应一个与其他局面不同的位置的话，则组合的结果是全世界所有的计算机内存加起来也不够这样一个数组用。那么让每一局面在数组中对应惟一的位置，但并不保证数组中每一个数据项对应惟一的局面如何呢？比如将所有的局面对应在106单位的数组上。这样，必然有一些局面对应在相同的位置上；但是对一次搜索而言，这种情况发生的概率并不高。一旦某个搜索过的局面在该数组中未找到，我们不过是对它进行Alpha-Beta搜索而已。不同的局面对应在数组中同一存储单元上的情形，叫做冲突。我们将利用哈希方法实现置换表的方法叙述如下。定义哈希数组如下：structHASHITEMint64 checksum；/64位哈希值，用以验证表中数据是否是要找的局面int depth；/该表项求值时的搜索深度enum exact，lower_bound，upper_bound entry_type；/表项值的类型double eval； /所代表的节点的值hashtableHASH_TABLE_SIZE；/定义大小为 HASH_TABLE_SIZE 的哈希数组对要搜索的每一节点，计算出它的一个哈希值（hashIndex，通常是一个32位数对哈希表大小取模）以确定此局面在哈希表中的位置。计算另一个64位的哈希值（Checksum）来校验表中的数据项是否是所要的那一项。在对某一局面搜索之前，先查看哈希表项 hashTablehashIndex，如果 hashTablehashIn-dex.checksum=Checksum并且hashTablehashIndex.depth 大于等于最大搜索深度减去当前层数，就返回hashTablehashIndex.eval作为当前局面的估值。当对一个局面的搜索完成之后，将Checksum、当前层数和估值结果保存到 hashTablehashIndex当中，以备后面的搜索使用。2.2.7历史启发（History Heuristic）在前面的章节我们曾经提到过，Alpha-Beta搜索的剪枝效率，几乎完全取决于节点的排列顺序。在节点排列顺序处于理想状态的情况下，Alpha-Beta搜索需遍历的节点数仅为极大极小算法所需遍历的节点数的平方根的两倍左右。也就是说对一棵极大极小树来说，如果极大极小搜索需遍历106个节点求得结果，那么处于理想状态的 Alpha-Beta搜索仅需遍历约2000个节点就可求得结果。而在节点的排序最不理想的情况下，Alpha-Beta搜索要遍历的结点数同极大极小算法一样多。如何调整待展开的走法排列的顺序，是提高搜索效率的关键。根据部分已经搜索的结果来调整将要进行搜索的节点顺序是一个可行的方向。通常一个局面经搜索得知较好时，在其后继节点当中往往有一些相似的局面，比如仅有一些无关紧要的棋子位置不同等等。这些相似的局面往往也是较好的。可以通过一些较复杂的判断来找出这些相似的局面，率先搜索，从而提高剪枝效率。但这一方法需要具体棋类相关的知识，并且往往判断复杂而效果不彰。J.Schaeffer提出了History Heuristic的方法，在基于Alpha-Beta的搜索当中，一个好的走法可以定义如下：1由其产生的节点引发了剪枝。2未引发剪枝，但是其兄弟走法中的最佳者。在搜索的过程中，每当找到一个好的走法，就将与该走法相对应的历史得分作一个增量，一个多次被搜索并确认为好的走法的历史纪录就会较高，当搜索中间节点时，将走法根据其历史得分排列顺序，以获得较佳的排列顺序。这比采用基于棋类知识而对节点排序的方法要容易得多。由于历史得分表随搜索而改变，对节点顺序的排列也会随之动态改变。2.3本章小结本系统的可行性研究，从市场可行性、技术可行性方面着手进行考虑。市场可行性主要研究五子棋游戏的潜在市场；技术可行性主要研究系统开发软硬件条件。综上考虑，本项目的开发技术成熟、完备，运行环境优良，具有一定的开发前景。算法分析部分主要介绍了五子棋游戏开发用到的算法。按照计算机下每一手棋时，应用算法的大致顺序，本系统使用的主要算法有极大极小值算法、负极大值算法、Alpha-Beta算法、置换表技术、哈希表技术、历史启发等。其中的极大极小值算法是对弈算法的基础。哈希表技术的使用，是置换表技术能够实现的基础。各种算法的综合使用，得以提高算法的效率。第3章总体设计3.1总体设计过程总体设计过程通常由四个主要阶段组成：系统体系结构设计，确定系统的具体体系结构实现方案；系统模块设计，确定系统模块层次；结构算法设计，确定软件结构和典型算法；交互设计，确定系统的交互界面。总体设计的典型过程包括如下七个阶段：（1）选取合理的体系结构方案（2）推荐最佳方案（3）系统模块设计（4）数据结构和算法设计（5）交互设计（6）编写文档（7）审查和复审由于本系统应用到算法的设计，下面详细描述一下第四个阶段。高效率的程序基于良好的数据结构与算法，一般来说，数据结构与算法就是一类数据的表示及其相关的操作。从数据表示的观点来看，存储在数组中的一个有序整数表也是一种数据结构。算法是指对数据结构施加的一些操作。一个算法如果能在所要求的资源限制范围内将问题解决好，则称这个算法是有效率的。一个算法如果比其他已知算法所需要的资源都少，这个算法也称为是有效率的。算法的代价是指消耗的资源量。一般来说，代价是由一个关键资源，例如时间或空间来评估的。3.2系统的数据结构和算法设计3.2.1系统的数据结构设计本系统在开发过程中，为了设计更合理的数据结构，使用了用户自定义数据类型结构体和枚举类型。 1利用哈希表方法实现置换表，哈希表中元素的结构定义如下：typedef struct HASHITEMLONGLONG checksum; /哈希值，用以验证表中数据是否是要找的局面EnterType enterType; / 数据类型short nPly; / 取到此值时的层次short value; / 节点的值 HashItem;2用以表示走法的结构：typedef struct STONEMOVE int x; / 棋子的横坐标 int y; / 棋子的纵坐标 int score; / 此走法的分数StoneMove;3枚举类型的使用enum EnterTypeexam,lower,uper;/搜索的精确值、下边界、上边界enum IDD = IDD_BEST ;enum IDD = IDD_PENTE_DIALOG ;3.2.2系统的算法设计本系统是通过多个算法的结合使用来增强算法的效率。应用的主要算法有博弈树、负极大值算法、Alpha-Beta剪枝算法、置换表、哈希表、历史启发等。其中的博弈树算法是搜索算法的基础，但是它的搜索量太大，在实现的过程中，我们不可能让系统搜索所有的结点，于是使用极大极小值算法对博弈树进行了改进。极大极小值算法是对弈算法的基础。普通的极大极小值算法看起来有一点笨，既然一方试图取极大值而另一方试图取极小值，也就是说我们总要检查哪一方要取极大值而哪一方又要取极小值，以执行不同的动作。而负极大值方法，消除了两方的差别，博弈双方都取极大值。在极大极小搜索的过程中，存在着一定程度的数据冗余。这就需要Alpha-Beta算法的剪枝功能来消除冗余。在搜索过程中，利用置换表技术将 Alpha-Beta搜索过程中每一节点的结果都记录下来，则在任意节点向下搜索之前先查看这些记录，就可避免重复搜索，以提高搜索效率。而置换表的实现则是依赖哈希表。这种算法之间的优化组合，使得本系统能够实现它有效的搜索。3.3系统模块设计五子棋游戏是在系统地分析了游戏玩家的各项需求，以实际为基础进行设计的。本系统可以进行人与计算机的对弈，还可以实现两个人在同一台计算机上对弈。本系统包括三大模块：游戏模块、设置模块、帮助模块。每个模块包括的主要内容如下： 1游戏模块：新局、初级、中级、专家、英雄榜。2设置模块：悔棋、提示、英文菜单、声音效果。3帮助模块：有关本系统的介绍其中：在新局对话框下，可以对本局游戏进行设置：（1）对弈方式选择：人与计算机对弈、人与人对弈（2）先手选择：玩家执黑先下、计算机执黑先下（3）是否选择声音效果本系统的功能模块，如下图3.1所示。图3.1系统功能模块图3.4本章小结本系统按照总体设计典型过程的七个阶段进行，详细介绍了系统的数据结构和算法设计。本系统的数据结构主要采用了用户自定义数据类型结构体和枚举类型。算法设计是利用各种算法的优化组合来提高算法的效率。本系统主要包括三大功能模块游戏模块、选项模块、功能模块。每个功能模块包括若干子功能。本系统以需求分析结论为基础，考虑得比较全面。 第4章详细设计4.1系统运行平台设置1硬件环境：台式计算机（PC）一台，如表4.1所示。表4.1运