论文总字数：14822字

摘 要

自从计算机作为游戏对战平台以来，各种棋类游戏如雨后春笋般纷纷冒出。使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而黑白棋游戏由于其规则简单，变化多端，深受大众喜爱。

基于黑白棋游戏以上的优点，开发黑白棋是一个非常有价值的课题。本系统采用vs2010平台开发，主要功能包括人机对战，困难选择以及数据存储。具有功能齐全、简单易学、既动手又动脑的特点。尤其是游戏的同时，还有声音效果的配合，使游戏更加富有趣味性和消遣性。本系统主要应用哈希表，Alpha-Beta剪枝等算法来完成人机对弈功能的实现。

关键词：黑白棋；C#；人机对弈

Abstract：Since 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. ful entertainment.

Key words：Gobang C#: Human Chessboard

第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-1生活中的黑白棋

1.3　目的和意义

黑白棋游戏不仅能增强人们的抽象思维能力、逻辑推理能力、空间想象力，提高人们的记忆力、心算能力等，而且深含哲理，有助于修身养性。黑白棋既有现代休闲方式所特有的特征“短、平、快” ，又有中国古典哲学所包含的高深学问“阴阳易理” ；它既有简单易学的特点，为人民群众所喜闻乐见，又有深奥的技巧；既能组织举办群众性的比赛、活动，又能组织举办高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观，它是中西方文化的交融点，也是中西方文化交流的一个平台。

黑白棋的根在中国，在这个国境里，他有着广泛的群众基础。但与世界先进的黑白棋技术相比，我们的棋艺水平还要继续提高，所以我们要推广黑白棋，宣传黑白棋，争取在较短的时间内赶上和超过世界黑白棋坛的先进水平。在这种环境下，开发一个易学实用的黑白棋游戏软件是很有必要的。

中国作为黑白棋的发源国，要对黑白棋在下个世纪的发展起到世界性的推动作用。黑白棋的发展在中国出现方兴未艾、星火燎原之势。同时还有一大批的中生代棋手和充满希望的“明日之星”。相信，中国棋手攀登黑白棋巅峰的日子会早日来到。

1.4　系统设计思想

一个优秀的游戏软件，必须有一个正确的设计思想，通过合理地选择数据结构、操作系统以及开发环境，构成一个完善的体系结构，才能充分发挥计算机应用的优势。根据游戏玩家的实际需求，本系统的设计按照下述原则进行。

（1）实用性：系统以用户需求为目标，以方便用户为原则，同时融入先进的设计思想。根据用户实际的需求情况，量身制作一个功能齐全、操作简单、实用性强的游戏软件。充分满足游戏玩家的需求，真正成为为玩家提供轻松、娱乐、休闲的工具。

（2）先进性：本软件将充分应用现有成熟的计算机技术、软件开发技术，为用户提供高性能的系统，可以方便的实现玩家的需要。

（3）高可靠性：一个实用的系统同时必须是可靠的，本系统通过合理而先进的结构设计以及软、硬件的优化选型，可保证系统的可靠性与容错性。

（4）可维护性：系统的设计要求方便维护，包括硬件的维护，软件的维护（更

第2章　人机对弈算法研究

黑白棋游戏的开发在搜索算法方面，可以有多种选择。通过从不同的角度分析各种搜索方法的效率，来考虑本系统的算法应用。可以看出几种算法的效率，本系统按照计算机下每一手棋所应用的算法的大致顺序，采用的主要算法Alpha-Beta剪枝算法、置换表技术、哈希表技术等。下面详细地介绍一下这些算法。

首先是Alpha-Beta剪枝算法

2.1　Alpha-Beta搜索

Alpha-Beta算法其实是一种高效率的极大极小搜索算法，在黑白棋的设计过程中，考虑到在电脑需要搜索步骤时，会有一个难易程度和冗余的问题，因此选择Alpha-Beta算法，在搜索的过程中，极大的避免了许多不需要的步骤，能够尽快的找到最好最优的落子点，如下图2-1所示的博弈树图，搜索每深入一层，树的大小呈指数上涨，减少了冗余，极大的提高了系统在运行过程中，对每一步旗子落点的搜索。

图2-1　Ａlpha-Ｂeta剪枝示例图

在搜索的过程中，存在着一定程度的数据冗余。举一个最简单的例子：在象棋博弈的过程中，如果某一个节点轮到甲走棋，而甲向下搜索节点时发现第一个子节点就可以将死乙（节点值为最大值），则剩下的节点就无需再搜索了，甲的值就是第一个子节点的值。这个过程，就可以将大量冗余的（不影响结果的）节点抛弃。

2.2　置换表（Transposition Table）

在搜索的过程中，改进搜索算法的目标在于将不必搜索的（冗余）分枝从搜索的过程中尽量剔除，以达到搜索尽量少的分枝来降低运算量的目的。

在先前谈到的几种搜索算法中，我们看到可以通过 Alpha-Beta剪枝来剪除两种类型的冗余分枝/节点，但是已经搜索过的节点不可以免于搜索。

从图2-1的极大极小树的片断中，我们可以看出，该片断从节点A开始，有两个分B和C（为简化问题，其他节点从略），B 有子节点D，C有子节点E，再往下D有子节点F，E有子节点G。读者可以看到，在极大极小树的不同分枝上，存在着完全相同的节点。在上图中，节点F和G完全相同。对于节点F，在搜索分枝的时候，就可能已经搜索过了。那么，在搜索节点G的子节点时，我们能不能直接利用已经搜索过的节点F的结果，而不是重新搜索一遍节点G？

想法是可行的。如果要利用已经搜索过的节点的结果，我们就要用一张表把搜索过的节点记录下来。然后在后续的搜索中，察看记录在表中的这些结果，如果将要搜索的某个节点已有记录，就直接利用记录下来的结果。这种方法叫做置换表（Transposition Table，简称TT）。

如果将Alpha-Beta搜索过程中每一节点的结果都记录下来，则在任意节点向下搜索之前先查看这些纪录，就可避免上述重复的操作。

2.3　哈希表（Hash Table）

置换表的实现在时间和空间复杂度上的疑问。实际上已经明确了要实现置换表必须要满足如下条件：

1．查找记录中的节点数据时速度要非常快，最好是类似于随机存取。

2．将节点数据放入记录的速度也要非常快。这就意味着数据项插入的过程不可有数据移动排序等操作。

3．要能在有限的存储空间内进行。

答案是哈希表，哈希方法的思想为每一个学过数据结构或算法课程的开发人员所熟知。对棋类博弈来说，定义一个巨大的数组，将每一局面记入其中，每一局面在数组中对应惟一的位置。这样，将数据记入和取出就类似于随机读写，不会有耗时的查找和插入过程。但是，以象棋而论，如果为每一局面在数组中对应一个与其他局面不同的位置的话，则组合的结果是全世界所有的计算机内存加起来也不够这样一个数组用。

那么让每一局面在数组中对应惟一的位置，但并不保证数组中每一个数据项对应惟一的局面如何呢？比如将所有的局面对应在106单位的数组上。这样，必然有一些局面对应在相同的位置上；但是对一次搜索而言，这种情况发生的概率并不高。一旦某个搜索过的局面在该数组中未找到，我们不过是对它进行Alpha-Beta搜索而已。不同的局面对应在数组中同一存储单元上的情形，叫做冲突。

对要搜索的每一节点，计算出它的一个哈希值（hashIndex，通常是一个32位数对哈希表大小取模）以确定此局面在哈希表中的位置。计算另一个64位的哈希值（Checksum）来校验表中的数据项是否是所要的那一项。

在对某一局面搜索之前，先查看哈希表项 hashTable［hashIndex］，如果 hashTable［hashIn-dex］.checksum==Checksum并且hashTable［hashIndex］.depth 大于等于最大搜索深度减去当前层数，就返回hashTable［hashIndex］.eval作为当前局面的估值。

当对一个局面的搜索完成之后，将Checksum、当前层数和估值结果保存到 hashTable［hashIndex］当中，以备后面的搜索使用。

第3章　黑白棋游戏功能设计

3.1　总体设计过程

总体设计过程通常由四个主要阶段组成：

1. 首先是棋盘的设计。黑白棋的棋盘是一个8*8的正方形棋盘，里面含有64个小格，玩家开始游戏时，正是在这些小格进行操作。主要运用的是绘图软件制作。
2. 第二部是游戏的难度的设计。我的游戏一共分为四个难易程度，从开始的简单到最困难，分别对应的是猴子的厉害程度，比较简单易懂，这里主要是运用了搜索。前面也提到过，主要是在玩家选择不同的难易程度之后，系统会相应的进行不同深度的搜素，形成难易程度的区别。
3. 第三部是游戏的一些选项设置。比如游戏的声音是默认就有的，这里并没有添加取消音乐的设置。另外还有像帮助信息，退出游戏，还有一个就是棋盘上方会有一只猴子，每当玩家走棋时，这只猴子都会进行点评，但是猴子所说的话都是事先写好的，不多，就那几句话。
4. 最后的一个步骤就是这个黑白棋的关键所在。黑白棋在走棋时都会触发周围旗子颜色的变化，因此需要知道怎样实现。首先我的棋盘，是有64个格子组成，每个格子下面都有两张图片一张白子，一张是黑子。在游戏的过程中，每当玩家点击棋盘有效区域时，都会出发事件，这其实就是递归，当这个子落下时，系统会判断是否与周围棋子颜色一样，如果不同，则会继续变化，直到周围棋子颜色一致，递归就会停止。

3.2　数据结构定义和算法设计

3.2.1　数据结构定义

本系统在开发过程中，为了设计更合理的数据结构，使用了用户自定义数据类型和枚举类型。

1. 利用棋盘结构类实现对棋盘信息，当前棋子信息等的封装，棋盘结构类结构定义如下。首先这是一个棋盘结构类。这个类中定义了int型常量rowsNum即棋盘行数，表示棋子的数组Stones以及表示棋子数目的int型的数组( StonesNum[0]黑子数目，StonesNum[1]白子数目 )。

public class BoardStruct{ private const int rowsNum = Constants.RowsNum;

public Listlt;Seatgt; MobSeat //通过public Listlt;Seatgt; MobSeat 获取当前可行位置。

{

get { return mobSeat; }

set { mobSeat = value; }

}

public int[] StonesNum;

public Stacklt;Stepgt; StepStack;

public StoneColor CurrentColor//获取当前下棋方的棋子颜色

{

get { return currentColor; }

set { currentColor = value; }

}

public StoneNode this[Seat seat]

{ get

剩余内容已隐藏，请支付后下载全文，论文总字数：14822字