中国象棋人机博弈系统的设计与实现

班级031221学号03122014本科毕业设计论文题目中国象棋人机博弈系统的设计与实现学院计算机学院专业网络工程学生姓名李盼舒摘要摘要中国象棋发展至今已经有了几千年的历史，是中华民族灿烂的文化瑰宝，它具有浓厚的趣味性，规则简单明了，在中国已经成为了一项普遍的棋类运动，是其他棋类远远无法比拟的，并且目前，中国象棋正在往国外发展。为了使中国象棋更加具有趣味性，我们在象棋博弈中加入了人机交互,实现了一个中国象棋人机博弈系统，这个系统是将计算机和人工智能结合起来的一种电脑游戏。本文研究了中国象棋在电脑上的局面表示，走棋过程中走法生成和局面评估、博弈树搜索等一系列的问题。通过visualC++开发平台和MFC文档视图体系结构实现了一个包括人人对战、人机对战、残局保存、读取残局、悔棋、还原等功能模块的中国象棋人机博弈系统。本系统为象棋爱好者提供了一个平台，满足了玩家对中国象棋的基本需求。关键词：中国象棋人工智能博弈树搜索算法估值函数ABSTRACTABSTRACTChinesechessisagorgeousculturaltreasureofChinesenationwiththousandsofyearshistory.Ithasakeeninterestandsimpleruleswhichhasbeenapopularchessgameinchinathatcan’tbematchedbyanyotherkindsofchess.What’smore,nowadays,Chinesechessisrapiddevelopmentinforeigncountries.InordertoadvancingtheinterestofChinesechess,weaddhuman-computerinteractionintochess-playingsystem,makingahuman-computerinteractiongamethatisakindofcomputergamewhichhasacombinationofcomputerandartificialintelligence.ThispaperstudiestheproblemofboardpositionofChinesechess,movegenerationandsituationassessment.ItreachesaChinesechessgamesystemwithavarietyoffunctionalmoduleswhichinvolves“man-manbattle”,“man-machinebattle”,thekeepingandreadingoftheend-game,undoingandrestoringthroughVisualC++platformandMFC.ThissystemprovidesaplatformfortheChinesechessenthusiasts.ItcanmeetthebasicneedsofplayerstowardsChinesechess.Keywords:Chinesechessartificialintelligencegameplayingtreealgoritjmevaluatefunction目录i目录第一章绪论..........................................................11.1选题的背景和意义..............................................11.2国内外棋类博弈的发展现状.....................................11.3论文的主要工作...............................................2第二章中国象棋简介..................................................32.1简介.........................................................32.2棋盘和棋子...................................................32.3走棋规则.....................................................4第三章系统分析......................................................53.1MFC简介......................................................53.2棋局表示.....................................................63.3走法生成.....................................................63.4局面评估.....................................................73.4.1估值函数................................................83.4.2估值函数和博弈性能......................................83.4.3估值函数的改进..........................................93.5搜索算法.....................................................93.5.1极大极小值搜索算法.....................................103.5.2Alpha-Beta剪枝搜索....................................103.5.3启发式搜索及走法排序...................................12第四章系统设计与实现...............................................154.1系统的整体规划..............................................154.2象棋界面的实现..............................................154.3对弈功能的实现..............................................164.4悔棋和还原功能..............................................174.5文件保存和读取功能..........................................184.6着法显示功能................................................18ii目录4.7程序说明.....................................................184.8系统测试及实验结果..................................................................................................19第五章总结与展望...................................................23致谢...............................................................25参考文献............................................................27第一章绪论1第一章绪论1.1选题的背景和意义近几十年来，随着计算机硬件和软件技术的飞速发展，电脑游戏产业展现出了蓬勃发展的势头，已经变成与音乐、影视等并驾齐驱的娱乐产业。人们也开始对计算机是否可以战胜人脑产生了兴趣。从二十世纪八十年代起，电脑人工智能开始向人类智能提出了挑战，到1997年，IBM研究的超级电脑击败了当时的国际象棋冠军，成为人类人工智能发展史上的重要标志。人类对于人工智能的探索是从棋类开始的，研究人工智能的学者们曾经表示：如果我们要想深入的了解人类智能的核心技术，我们就必须掌握棋类的本质。中国象棋从古代流传至今有了几千年的历史，是一种古老的文化，集人类科学、文化、艺术为一体，有助于开发人的智力，培养人的思维，锻炼人的毅力，使人更具有竞争意识。并且相比较于国际象棋，中国象棋更为复杂，因此对中国象棋人机博弈问题进行研究更有意义。如何让机器变得智能，可以和人类智力进行竞技，是本文研究的一个重要的问题，通过本文的研究，掌握人工智能的搜索、知识表示、计算，在人工智能领域进行一个深度的探索。1.2国内外棋类博弈的发展现状人类对于机器棋类博弈的研究最早是开始于国际象棋，美国数学家香农通过几十年的研究，找到了编写国际象棋程序的方法，他提出了通过一个函数评估局面的优劣，函数主要考虑一般棋手会考虑到的一些问题，例如：棋子的棋力、棋子在棋盘上的位置、棋子间的相互制约和棋子的机动性等等。香农是国际象棋博弈理论的先驱。当国际象棋博弈已经发展到一个比较成熟的阶段，对中国象棋博弈的研究才刚刚开始。直到1981年，张耀腾发表了第一篇研究中国象棋人机博弈的文章《人造智慧在电脑象棋上的应用》。他在他的文章中以残局做实验，提出了局面评估函2中国象棋人机博弈系统的设计与实现数是静态子力值、棋子机动性、棋子的位置、威胁和保护等之和，但是缺乏对全局的把握。1982廖嘉成发表的《利用计算机象棋的实验》，其中包括对开局、中局和残局的研究。1983年周玉龙、黄少龙一起开发的《象棋排局系列软盘》系统，实现了电脑与人的对弈。这些研究成果为象棋软件的发展奠定了基础。到了九十年代，中国象棋软件开始发展起来了，出现了一些比较著名的象棋软件，如《中国象棋》、《将族Ⅲ》、《象棋水浒战》、《象棋巫师》等，但是当时的象棋软件没有布局库，水平上比较弱。进入21世纪以后，中国象棋人机博弈的研究受到越来越多的关注，并且随着计算机硬件和软件水平的不断提高，象棋软件得到了很大水平上的提升。目前象棋软件比较厉害的是《新天机》、《台风引擎》、《象棋名手》、《新小虫》等，这些象棋软件基本上都有计算能力强，审局比较深入等优点，这也是现在中国象棋计算机博弈的正在进行进一步研究的地方。1.3论文的主要工作本文的主要工作是将人工智能和中国象棋结合在一起，通过MFC文档视图体系结构和VisualC++开发工具，设计并实现一个中国象棋人机博弈系统。主要的部分是象棋的界面实现部分和博弈引擎部分。界面拥有友好人机交互，主要包括棋盘、菜单、功能按钮，提供一些悔棋、还原或者走法显示之类的功能。引擎部分主要是数据结构、走法生成、局面评估和搜索算法，是程序的核心部分。第二章中国象棋简介3第二章中国象棋简介2.1简介中国象棋历史悠久，起源于山西沁县。战国时期，已经有了关于象棋的正式记载，如：《说苑》载：“雍门子周以琴见孟尝君，说：足下千乘之君也，……燕则斗象棋而舞郑女。”。《楚辞·招魂》中有“蓖蔽象棋，有六簿些；分曹并进，遒相迫些；成枭而牟,北周象戏，呼五白些。”。因此在战国时期，象棋就开始在贵族中流传。中国象棋发展到唐朝的时候，发生了巨大的变化，由原先的战国时期盛行的文博象棋发展到了有4个兵种，分别是“将、马、车、卒”，刚开始，和国际象棋一样的，中国象棋的棋盘也是由黑白相间的64个方格组成。后又变成和围棋一样的90个网格点。经过不断的传承和演变至宋代，中国象棋才完全定型。增加了“炮”“象”、“士”这三个兵种。记载于宋代的《事林广记》的象棋棋谱