智能中国象棋系统的设计与实现毕业论文.docx
- 文档编号:9182310
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:79
- 大小:532.81KB
智能中国象棋系统的设计与实现毕业论文.docx
《智能中国象棋系统的设计与实现毕业论文.docx》由会员分享,可在线阅读,更多相关《智能中国象棋系统的设计与实现毕业论文.docx(79页珍藏版)》请在冰点文库上搜索。
智能中国象棋系统的设计与实现毕业论文
毕业论文声明
本人郑重声明:
1.此毕业论文是本人在指导教师指导下独立进行研究取得的成果。
除了特别加以标注地方外,本文不包含他人或其它机构已经发表或撰写过的研究成果。
对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。
本人完全意识到本声明的法律结果由本人承担。
2.本人完全了解学校、学院有关保留、使用学位论文的规定,同意学校与学院保留并向国家有关部门或机构送交此论文的复印件和电子版,允许此文被查阅和借阅。
本人授权大学学院可以将此文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本文。
3.若在大学学院毕业论文审查小组复审中,发现本文有抄袭,一切后果均由本人承担,与毕业论文指导老师无关。
4.本人所呈交的毕业论文,是在指导老师的指导下独立进行研究所取得的成果。
论文中凡引用他人已经发布或未发表的成果、数据、观点等,均已明确注明出处。
论文中已经注明引用的内容外,不包含任何其他个人或集体已经发表或撰写过的研究成果。
对本文的研究成果做出重要贡献的个人和集体,均已在论文中已明确的方式标明。
学位论文作者(签名):
年月
关于毕业论文使用授权的声明
本人在指导老师的指导下所完成的论文及相关的资料(包括图纸、实验记录、原始数据、实物照片、图片、录音带、设计手稿等),知识产权归属华北电力大学。
本人完全了解大学有关保存,使用毕业论文的规定。
同意学校保存或向国家有关部门或机构送交论文的纸质版或电子版,允许论文被查阅或借阅。
本人授权大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索,可以采用任何复制手段保存或编汇本毕业论文。
如果发表相关成果,一定征得指导教师同意,且第一署名单位为大学。
本人毕业后使用毕业论文或与该论文直接相关的学术论文或成果时,第一署名单位仍然为大学。
本人完全了解大学关于收集、保存、使用学位论文的规定,同意如下各项内容:
按照学校要求提交学位论文的印刷本和电子版本;学校有权保存学位论文的印刷本和电子版,并采用影印、缩印、扫描、数字化或其它手段保存或汇编本学位论文;学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务;学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版,允许论文被查阅和借阅。
本人授权大学可以将本学位论文的全部或部分内容编入学校有关数据库和收录到《中国学位论文全文数据库》进行信息服务。
在不以赢利为目的的前提下,学校可以适当复制论文的部分或全部内容用于学术活动。
论文作者签名:
日期:
指导教师签名:
日期:
毕业设计论文
智能中国象棋系统的设计与实现
毕业设计(论文)原创性声明和使用授权说明
原创性声明
本人郑重承诺:
所呈交的毕业设计(论文),是我个人在指导教师的指导下进行的研究工作及取得的成果。
尽我所知,除文中特别加以标注和致谢的地方外,不包含其他人或组织已经发表或公布过的研究成果,也不包含我为获得及其它教育机构的学位或学历而使用过的材料。
对本研究提供过帮助和做出过贡献的个人或集体,均已在文中作了明确的说明并表示了谢意。
作者签名:
日 期:
指导教师签名:
日 期:
使用授权说明
本人完全了解大学关于收集、保存、使用毕业设计(论文)的规定,即:
按照学校要求提交毕业设计(论文)的印刷本和电子版本;学校有权保存毕业设计(论文)的印刷本和电子版,并提供目录检索与阅览服务;学校可以采用影印、缩印、数字化或其它复制手段保存论文;在不以赢利为目的前提下,学校可以公布论文的部分或全部内容。
作者签名:
日 期:
智能中国象棋系统的设计与实现
摘要
人工智能(AI)中国象棋系统是将计算机知识和中国象棋知识结合起来的一种新型的游戏方式。
智能中国象棋系统在此基础上实现人与机器的对弈,突破了以往传统象棋游戏只能人与人对战的限制,使中国象棋这一古老的游戏形式焕发出蓬勃朝气。
本文结合在中国象棋机器博弈方面的实践经验,在分析了中国象棋游戏需求基础上,设计并实现了智能中国象棋系统。
该系统包括人人对战、人机对战、制作棋谱、播放棋谱以及挑战英雄榜等功能模块。
人人对战规则明确,包含了中国象棋所有的着法;人机对战中电脑棋力分为简单、中等、困难三个等级,方便了不同水平人群的选择;制作和播放棋谱模块容易操作,方便学习;挑战英雄榜则为象棋游戏增加了乐趣。
本系统的实现满足了人们对中国象棋的基本需求,解决了传统象棋游戏学习性差、棋谱不易保存、不易演示等问题。
关键词:
计算机博弈,中国象棋,人机对战,制作棋谱,搜索算法
IntelligentChineseChessSystemDesignandImplementation
Author:
WangGuiweiTutor:
FangMiao
Abstract
ArtificialIntelligence(AI)ChineseChessSystemisanewgames’waywhichcombineswithcomputerknowledgeandChineseChessknowledge.IntelligentChineseChessSystemonthebasisofitwhichcompletesthegamebetweenhumanandcomputer,breakingthetraditionalchessgame’srestrictionthatonlycanplayagainstpeople.SothattheancientgameofChinesechessbecomeprosperity.
WiththepracticalexperienceinChinesechesscomputergame,adetailedanalysisandresearchhasbeendone.Basedonthose,IdesignedandimplementedtheIntelligentChineseChessSystem.Thissystemincludesthegameagainsthuman,thegmebetweencomputerandhuman,makechessmanual,playchessmanualandherolistfunctions.ThegameagainsthumanfunctionhasalltheChineseChessrulesandtheyareveryclear.Inthegamebetweencomputerandhumanfunction,computerthinkingdepthisdividedintosimple,mediumanddifficulty.Itfacilitatethechoiceofdifferentlevels.Makingandplayingchessmanualfuctionsareeasytooperatingandlearning.Herolistfuctionaddsmuchfuntochessgame.
ThissystemsatisfiedthebasicdemandofpeopletoChinesechessandsolvedthestudyinghardandthetheoreticalisnoteasytomakingandplayingofthetraditionalchessgame.
KeyWords:
ComputerGame,ChineseChess,GamebetweenHumanandComputer,
MakeChessManual,SearchTecniques
1绪论
1.1选题的背景和意义
在人类文明发展的初期,人们便开始进行棋类博弈的游戏了。
近几十年来,随着计算机硬件和软件技术的不断发展,人们开始对计算机能否战胜人脑这个话题产生了浓厚的兴趣。
从1980开始,电脑博弈便开始逐渐大规模地向人类智能发起了挑战,到了1997年,IBM超级电脑DeeperBlue击败了当时的国际象棋冠军卡斯帕罗夫,成为了人工智能挑战人类智能发展的一个重要里程碑。
许多学者认为,对于人工智能研究而言,象棋的重要作用不亚于遗传学研究中的果蝇。
人类对机器博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生了重要影响。
人工智能的先驱们曾认真的表明:
如果能掌握下棋的本质,也许就掌握了人类智能行为的核心;那些能够存在于下棋活动中的重大原则,或许就存在于其它任何需要人类智能的活动中。
因此对于中国象棋人机博弈问题的研究意义重大。
而当今对中国象棋的研究也正如专家们所期望的那样在蓬勃地发展着。
中国象棋不仅是中国传统智慧的体现,同时也具有着比国际象棋更高的复杂度,如何让机器具有智能,与人进行对弈成了本课题研究的一个重要问题。
通过本课题的研究,掌握智能知识的表示与计算、搜索,不仅是对所学知识的锻炼,更是在人工智能领域的有意义的探索
1.2发展动态及研究现状
和国际象棋博弈系统相比,中国象棋博弈系统的研究起步比较晚,是八十年代开始的。
在这个时候计算机国际象棋取得重大突破,1983年美国贝尔公司的电脑参加美国人类比赛,取得了不错的成绩,被授予大师称号。
于是有专家学者想如何将国际象棋电脑技术移植到中国象棋上来,以带动中国象棋电脑较快的发展;同时中国象棋从技术研究进入理论研究,有关开局、中局、残局理论以及象棋对策相继建立起来,为中国象棋计算机博弈提供了理论基础。
1981年张耀腾发表的《人造智慧在电脑象棋上的应用》,他提出审局函数为静态子力值,棋子位置值,棋子灵活度值,威胁与保护等四项之和。
但该文主要以残局做实验,缺乏完整对局的考虑。
1982年廖嘉成发表的《利用计算机象棋的实验》就进了一步,包括开局、中局、残局。
1983年黄少龙、周玉龙合作制成《象棋排局系列软盘》专家系统与人对弈。
到了90年代,中国象棋计算机博弈的应用开始发展起来,人们研究出了各种博弈软件。
比较著名的软件有台湾的吴身润的《中国象棋》、光谱公司出品的《将族Ⅲ》、晟业编制的《象棋水浒战》、《象棋武林帖》。
而且涉足这个领域比较早的是台湾的一些专家学者。
近几年,在内地也涌现出一批对中国象棋人机博弈问题感兴趣的高校、单位及个人,而且进入21世纪以后,中国象棋计算机博弈的研究受到越来越多的学者的关注,比较著名的博弈软件如表1所示。
表1-1著名中国象棋计算机博弈程序
程序作者地区
纵马奔流涂志坚广州中山大学
谢谢象棋大师法国电脑公司法国
ELP郑武尧、陈志吕台湾
SHIGA(象棋世家)郑明政、颜士净台湾
SHCC(神乎棋技)SAIteam美国
Cyclone(象棋旋风)陈朝阳北京
CONTEMPLATION千虑陈志昌、许舜钦台湾
棋天大圣王骄东北大学
象棋奇兵赵明阳中国
每年也会有中国象棋计算机博弈的国际奥林匹克大赛,这其中有2003年的世界冠军“纵马奔流”,2004年的世界冠军“谢谢象棋大师”,2005年的世界冠军“象棋奇兵”,2006、2007年的世界冠军“棋天大圣”,2008年的世界冠军“倚天”。
这些都体现了中国象棋的人机博弈的研究的受关注程度;虽然如此,但中国象棋的人机博弈的研究比国际象棋还是晚了几十年,并且在搜索算法等方面的研究还与国际象棋相距甚远。
1.3系统概述
1、棋盘表示(BoardRepresentations)
棋盘表示就是使用一种数据结构来描述棋盘及棋盘上的棋子,以方便计算机处理。
中国象棋的棋盘表示还没有形成统一的或者公认的哪种为最佳的数据格式。
最直观也是最典型的方式是使用10x9的二维棋盘数组表示,也有使用棋子数组,扩展棋盘—棋子数组等,棋盘的数据表示直接影响到程序的时间及空间复杂度。
2、着法生成(MoveGeneration)
着法生成就是找到某个局面所有合法的走法。
它与棋盘表示的数据结构密切相关,一般需要大量繁琐的判断,伴随着搜索进行,并且调用频繁,是相当复杂而且耗费运算时间。
在一定程度上形成了程序的性能瓶颈。
当前为了提高着法生成的效率通常采用以空间换时间的方法:
与先求出棋子的在某位置的所有走法。
3、评估函数(EvaluationFunction)
评估函数就是对博弈过程中实际局面的好坏做出判断或打分,它影响着博弈局发展的趋势。
目前象棋程序的静态评价函数主要有子力价值,子力灵活性,子力对棋盘的控制,和一些对棋局影响比较大的重要特征计算几部分组成。
它与着法生成一样十分耗费运算时间,如何加速评估函数的速度十分关键。
4、搜索技术(SearchTechniques)
搜索技术与算法是象棋博弈系统程序的核心,是决定搜索效率的关键所在。
再好的硬件也无法实现“象棋不败算法”。
如何在成指数递增的状态空间中寻求最优解,是象棋博弈系统的一个重要的方向。
“蛮力搜索”肯定是不可取的。
如何有选择地搜索,既瞄准最有希望的方向局部加深,又不遗漏其它存在最优解的可能。
目前主要是使用α-β剪枝算法加上迭代深化、置换表、历史启发等策略的综合应用。
5、开局库(OpeningBook)
把开局几步的走法建成数据库供程序直接取用。
实践表明无论搜索引擎如何出色,在开局搜索过若干层后,得到的可能只是一些很笨拙的开局。
直接从开局库中取就可以大大加快开局时的运行速度和提高开局的质量。
开局库一般是采用zobrist哈希技术加以实现。
6、机器自学习(MachineLearning)
机器自学习之一是针对评估函数。
对弈过程机器自动调整评估函数参数的权值进行优化,发现一些棋子之间潜在的联系:
之二是采用模式识别,学习的过程是通过对博弈过程的识别统计,自行丰富模式库中的内容,以提高程序的博弈性能。
1.4本文的主要工作
本文的主要工作是将博弈策略应用到中国象棋程序的设计与实现上,建立一个完整的中国象棋计算机博弈系统,研究工作主要集中在以下几个方面:
1、棋盘表示与走法生成
从操作速度(性能)以及使用方便与否考虑,本象棋博弈系统从带位行位列信息的扩展棋盘——棋子联系数组着手进行研究。
然后根据棋盘表示获得所有棋子的走法预生成数组。
在产生走法时直接从中取出数据,进行少量判断以得到该棋子的合法走步。
2、估值函数
如何快速有效的对一个局面进行评估需要从速度和知识的两个角度进行考虑:
一般知识越多估值越准确,但速度也慢下来。
本系统采用通用的静态估值方式,同时在估值时结合走法预生成数组,使估值的速度有很大提升。
3、搜索技术
博弈树搜索技术它很大程度上独立于具体的计算机博弈程序。
本文讨论了α-β剪枝搜索算法及其各种增强手段:
包括窗口原则、置换表(内存增强);历史启发表(节点顺序调整);迭代深化(时间控制)等。
如何把各种增强手段有机组合起来达到最优,文章对基于迭代加深、置换表、历史启发的Negascout算法进行改进。
1.5论文结构
第一章阐述了选题背景,课题的国内外研究现状及课题的主要工作和文章的章节安排。
第二章第一部分首先介绍中国象棋程序的一些基本数据结构,着重研究了扩展的棋盘——棋子联系数组棋盘;在此基础上实现所有棋子的走法预生成数组,以提高搜索过程中走法产生的效率。
第二部分研究本系统的着法生成,包括预置表法和模板匹配法,进一步提高了搜索效率。
第三部分描述本系统的评价函数架构,着重描述了静态估值方法,分析了其不足,并提出了解决之道。
包括子力分数、子力灵活度评价、棋盘控制等并与走法预生成数组结合以提高估值速度。
第四部分实现了博弈树的α-β剪枝算法并简要介绍各种搜索策略。
第五部分阐述了开局库的设计原理。
第三章给出实验环境和程序实现。
第四章是全文的总结及展望。
2系统的分析和设计
2.1数据结构(Datastructure)
数据结构是一个程序的骨架,选择一种好的数据结构可以使程序的运行效率大大提高。
2.1.1棋盘的基本表示法(BoardRepresentions)
棋盘表示就是使用一种数据结构来描述棋盘上的信息,以便程序知道博弈的状态。
棋盘的数据表示直接影响到程序的时间及空间复杂度。
为了追求更高效率,研究人员针对中国象棋提出了多种不同的表示方法。
中国象棋的棋盘表示中最典型的是用一个10×9的二维字节(byte)数组,数组中每个元素代表棋盘上的一个交点,其值表明这个交点上放置的是一个什么棋子或是没有棋子
从棋子的角度考虑,如果把棋盘看成是一个平面坐标系,可以知道每一个棋子的位置信息:
小于10的横坐标和小于11的纵坐标;又在棋盘上最多32个棋子,故可以用一个32个字节的一维数组表示所有32个棋子的位置,其中每个字节的高4位表示该棋子的横坐标,低4位表示棋子的纵坐标。
而己被吃掉的棋子用坐标范围以外的数表示。
这样棋盘信息就被装入这32个字节中。
当然也可以把棋盘看作一维的,每个元素保存直接的位置信息。
两种棋盘表示方法:
一是做一个棋盘数组;二是做一个棋子数组。
棋盘数组中由棋子的位置获得棋子的类型可以在常数时间内完成,但由棋子的类型获得棋子的位置需要遍历;在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成,但由棋子的位置获得棋子的类型操作繁琐。
如果一个程序同时使用这两个数组,那么获得棋子的类型和棋子的位置都可以在常数时间内完成。
这就是“棋盘·棋子联系数组”,它的技术要点是:
(l)同时用棋盘数组和棋子数组表示一个局面,棋盘数组和棋子数组之间可以互相转换。
(2)随时保持这两个数组之间的联系,棋子移动时必须同时更新这两个数组。
在棋盘上删除一个棋子,需要做两个操作(分别修改棋盘数组和棋子数组)。
同样,添加一个棋子时也需要两个操作。
“棋盘·棋子联系数组“最大的优势是:
对于着法产生过程,可以逐一查找棋子数组,如果该子没有被吃掉,就产生该子的所有合理着法,由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多,因此联系数组的速度要比单纯的棋盘数组快很多。
同时“棋盘——棋子联系数组”是很多改进的棋盘的基础。
·2.1.2改进型棋盘结构
在计算机上面,位运算比一般的加减乘除及取余运算快得多。
如果能在寻找棋子
和定位棋子上使用位运算代替加减乘除和取余,这将很大程度上提高运算速度。
所以,人们把“棋盘——棋子联系数组“进行扩展:
把棋盘做成16×16的大小,这样得到行号可以用16除,得到列号可以对16取余(和15进行运算),这比除以10和对9取余操作要快得多。
如图2.1(红色格子都被标上“出界”的标志,目标格在这些格子上就说明着法无效):
图2.1扩展的棋盘
这种棋盘的更大的好处是:
(1)它可以防止棋子走出棋盘边界。
由bool型棋盘数组(属于棋盘的位置为true,否则为false),判断棋子是否走出棋盘边界只要返回该数组对应的值即可,速度快。
(2)对于是否在城池内可以用bool型城池数组判断,因为是否在城池内的判断会非常频繁,直接用该数组会很高效。
(3)判断是否过河的方法非常简单:
只要设定特定的表达式,当表达式为假表示已过河,否则没过河。
(4)还可以非常方便的判断棋子是否在己方。
2.2着法生成(MoveGeneration)
着法生成就是要产生所有有效的着法,让电脑棋手在这些着法中选择最好的着法,并判断人类棋手是否符合走棋规则。
着法生成是博弈程序中一个相当复杂而且耗费运算时间的方面,要生成所有着法只能用穷举。
中国象棋大约每一步可以有45个着法。
通过良好的数据结构和走法预生成,可以显著地提高生成的速度。
2.2.1模板匹配法
当动子确定以后,其“落址”和“提址”的相对关系便确定下来了,这样可以为某些动子设计其着法生成的“模板”,只要匹配到提址,便可以迅速找到落址。
图2.3给出了马的匹配模板。
图2.2马的匹配模板
将马对准提址,“O”表示符合“马走日”规则的落址,“x”表示“蹩马腿”的制约条件,通过查找模板匹配数组,实现“本方子则止,对方子则吃”,完成“提——动——落——吃”内容的确定。
对马的着法生成使用模板匹配法时,只要写出符合马行棋规则的模板匹配数组和马腿的模板匹配数组,在生成着法时通过查找这两个数组就可以实现。
显然,这比扫描整个棋盘,通过计算得到合法落址要快速的多。
同样的,可以对象、将、士、卒使用模板匹配生成着法。
2.2.2预置表法
它是把所有可能的着法预先存储起来,在生成着法时,用查表取代计算。
中国象棋每种棋子的行棋规则不同,生成每种棋子的着法和整个棋盘棋子的分布密切相关,如果建立每种棋子最大可能着法的小型数据库,用查询取代复杂的判断,那么也可以在很大程度上加快着法生成的速度。
预置表看起来似乎很大,但是只需在程序开始运行时初始化一次就可以了,这些耗费对整个程序的影响不大,但是对着法生成的作用却是非常明显的。
图2.3即是以路向行向比特向量为索引的一个车的预置着法表的生成范例。
图中显示,该车位于某行第4列,棋子分布的布尔向量形式为[010100100],可以看出,此时车可能的吃子着法落址为[010000100],非吃子着法的落址为[f0010110001]。
把车的列号和该行棋子的布尔分布作为输入,把吃子落址和非吃子落址作为输出,将输入和输出的关系写入一个预置表中,在使用时通过查表,就可以快速构成可行着法,而且可以区分开吃子着法和非吃子着法。
如图2.3所示:
图2.3车的着法预置表范例
2.3局面评估
局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。
从象棋的棋力上考虑,在搜索之外,局面估值是最重要的部分,因为对实际局面的评价的好坏,影响着今后局势发展的趋势。
这一过程对具体的棋类知识依赖程度很深,但是仍有一般性的规律可循。
目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。
同时由于随着搜索层数的加深,叶子节点的数目迅速上升,估值函数被数以百万次的调用,花费大量的运算时间,如何提高估值函数的速度,也成了博弈性能改进的重要话题。
下面分别从这两个方面及其关系介绍局面评估。
2.3.1估值函数(EvaluationFunction)
本系统的估值函数包括:
棋子固定价值,棋子位置附加值,棋子灵活性,棋子对棋盘的控制,棋子间的关系几部分。
棋子固定价值指的是对棋盘中的每一个棋子,根据它的重要性和走法的丰富程度赋予其一个特定的值。
在棋盘上,棋子多者占优,棋子少者为劣。
根据经验,可以让一个车价值为500,一个马价值为300,一个兵价值为100等等。
在中国象棋的对弈中,由于一般以将死对方的将(帅)作为结束,因此,通常赋值的规则是为将(帅)赋予一个远大于其他棋子的子力之和的值。
可以用下面的表达式求某一方的棋子固定值SideValue=sum(PieceNum*PieceValue);其中PieceNum是某种棋子的数量,PieceValue是该种棋子的价值,sum是对各种棋子的总价值求和。
如果红色的棋子价值总和大于黑色的棋子价值总和,通常这意味着红方的局势优于黑方。
而红黑双方的SideValue之差越大,红方的优势也就越大。
同样的棋子在不同位置上起的作用是不同的,最明显的是兵(卒)过河之前与之后它的作用和攻击力以及对对方的威胁显然是不一样的,而当兵卒一旦到了底线附近,它
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 智能 中国象棋 系统 设计 实现 毕业论文