《毕业答辩-基于QT的中国象棋算法设计与实现》由会员分享，可在线阅读，更多相关《毕业答辩-基于QT的中国象棋算法设计与实现（21页珍藏版）》请在金锄头文库上搜索。
1、中国象棋游戏的设计与实现,答辩人: 指导教师：,研究背景,中国象棋发展至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国象棋的普及程度是其它棋类无法比拟的，大至国际、国内比赛，小至社区街道。如今，仅中国就有2亿人会下中国象棋，且中国象棋的发展趋势日益国际化。本文首先研究了中国象棋在计算机中的表示问题，讨论如何产生着法等一系列相关内容，其次研究了博弈树的搜索技术及在此基础上发展起来的相关剪枝算法。系统使用MFC文档视图体系结构和QT开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。此博弈程序实现了人机博弈，悔棋，电脑难度设置，着法名称生成等功能。,目录,1 绪论 1 1.1 中国
2、象棋游戏设计背景和研究意义 4 1.2 国内外象棋软件发展概况 4 1.3 中国象棋游戏设计研究方法 4 1.4 本文的主要工作 4 2 棋局表示和着法生成 6 2.1 棋盘和棋子的表示 6 2.2 着法生成 9 3 走棋和博弈程序的实现 10 3.1 博弈程序的实现 10 3.1.1 搜索算法 10 3.1.2 着法排序 14 3.1.3 局面评估 18 3.2 悔棋和还原功能的实现 21 3.3 着法名称显示功能的实现 25 3.4 胜败判定 34 4 系统实现 37,中国象棋研究背景,国内外象棋软件发展概况 最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些
3、容量很小的象棋软件如：DOS界面将族、WIN31程序的中国象棋等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS窗口界面的象棋专业高级软件棋隐、象棋世家、象棋参谋、象棋奇兵等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。,主要功能,该象棋人机博弈系统实现的功能主要包括： 1、选手选择（人或电脑）；
4、 2、人机对弈（人与电脑竞技）； 3、悔棋、还原； 4、着法名称显示（象棋走棋规范名称）,主要工作,1.1 本程序的主要工作 第一部分主要介绍了中国象棋游戏开发的背景及意义、国内外象棋软件的发展概况和象棋游戏的设计研究方法； 第二部分介绍了棋局表示方法和着法生成； 第三部分介绍了走棋和博弈程序的实现； 第四部分介绍了系统的实现。,算法设计,采用short board256 表征棋盘,非棋盘位置0.棋盘上无棋子的位置也为0.采用256长度的数组,可以方便的像使用二位数组那样使用一维数组,如想要表征第三行第四列,只需使用board0x34即可.,算法设计,1.1 悔棋和还原功能的实现 悔棋和还原是
5、棋类软件中较为基本的功能。要实现悔棋和还原功能，首先要明确哪些信息应当被保存以供悔棋和还原所使用。 在程序中保存了如下信息： 棋局表示中所定义的棋盘数组； 各棋子的贴图位置； 这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。,算法设计,在悔棋中主要完成了以下任务： 1、下棋回合数减一； 2、将当前局面信息保存至走法队列，
6、以供还原所用； 3、从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从 队列中剔除掉； 4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 列，以供还原所用。然后从列表框中删除它。,算法设计,(三)将军检测 将军检测功能的相关函数在check文件夹中. checkmate.cpp调用check文件夹中的其他函数,检测当前方(检查side)/当前局面(检查地方的攻击性棋子)是否本方被将军.若是返回true,否则返回false. 可以造成将军的棋子有对方的车/对方的马/对方的兵/对方的炮,另外,有不能对将的规定.因而对general/chariot/cannon/hor
7、se/soldier这五类棋子各写了一个检测函数,它们都被checkmate.cpp中的bool checkmate()调用.,算法设计,AI部分采用bottom-up的方法设计,包括局面表示/走法生成/局面评估/将军检测/搜索算法.AI部分代码在kernel文件夹中.kernel文件夹中代码的组织与AI的结构同构.表征局面的数据结构以及其他一些全局变量在global.h中声明,在define_global.cpp中定义.move文件夹中为走法生成的函数.check文件夹中为将军检测函数.eval文件夹中为局面评估函数.search文件夹中为搜索函数.每个文件夹中都有test.cpp及make
8、file,为相应函数的测试代码.用户可到相应文件夹中运行make,然后执行可执行文件查看测试结果(makefile在linux环境下写成),算法设计,局面评估。为某一特定局面进行评分。 当实现了引擎部分的各要素时，可先建立一个Win32控制台项目，之后只要再添加一个.cpp文件负责接受用户的输入、调用搜索函数、显示搜索结果，便可简单的测试引擎了（采用输入着法的起点坐标和终点坐标的方式来传送用户走棋的信息。同样，程序显示计算机走棋的起点坐标和终点坐标来做出回应）。 对局时，由执红棋的一方先走，双方轮流各走一着，直至分出胜、负、和，对局即终了。轮到走棋的一方，将某个棋子从一个交叉点走到另一个交叉点
9、，或者吃掉对方的棋子而占领其交叉点，都算走一着。双方各走一着，称为一个回合。如果有一方的主帅被对方吃了，就算那一方输。 各种棋子的走法： 帅（将）：帅和将是棋中的首脑，是双方竭力争夺的目标。它只能在“九宫”之内活动，可上可下，可左可右，每次走动只能按竖线或横线走动一格。帅与将不能在同一直线上直接对面，否则走方判负。 仕（士）：仕（士）是帅（将）的贴身保镖，它也只能在九宫内走动。它的行棋路径只能是九宫内的斜线。 相（象）：相（象）的主要作用是防守，保护自己的帅（将）。它的走法是每次循对角线走两格，俗称“象走田”。相（象）的活动范围限于“河界”以内的本方阵地，不能过河，且如果它走的“田”字中央有一
10、个棋子，就不能走，俗称“塞象眼”。 车：车在象棋中威力最大，无论横线、竖线均可行走，只要无子阻拦，步数不受限制。因此，一车可以控制十七个点，故有“一车十子寒”之称。 炮：炮在不吃子的时候，走动与车完全相同。 马：马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。马一次可走的选择点可以达到四周的八个点，故有“八面威风”之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩马腿”。 兵（卒）：兵（卒）在未过河前，只能向前一步步走，过河以后，除不能后退外，允许左右移动，但也只能一次一步。 在懂的以上规则之后并可进行游戏，执行该软件后，并可进入游戏界面,总结
11、,2014年2月，我开始了我的毕业论文工作，时至今日，论文基本完成。从最初的茫然，到慢慢的进入状态，再到对思路逐渐的清晰，整个写作过程难以用语言来表达。历经了几个月的奋战，紧张而又充实的毕业设计终于落下了帷幕。回想这段日子的经历和感受，我感慨万千，在这次毕业设计的过程中，我拥有了无数难忘的回忆和收获。 脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益。我想这是一次意志的磨练，是对我实际能力的一次提升，也会对我未来的学习和工作有很大的帮助。 在这次毕业设计中也使我们的同学关系更进一步了，同学之间互相帮助，有什么不懂的大家在一起商量，听听不同的看
12、法对我们更好的理解知识，所以在这里非常感谢帮助我的同学。 在此更要感谢我的导师和专业老师，是你们的细心指导和关怀，使我能够顺利的完成毕业论文。在我的学业和论文的研究工作中无不倾注着老师们辛勤的汗水和心血。老师的严谨治学态度、渊博的知识、无私的奉献精神使我深受启迪。从尊敬的导师身上，我不仅学到了扎实、宽广的专业知识，也学到了做人的道理。在此我要向我的导师致以最衷心的感谢和深深的敬意。,不足之处,本程序对计算机博弈技术进行了研究，在深入研究了机器下中国象棋方法理论基础上，实现了一个具有一定棋力的人机对弈中国象棋程序。然而，由于时间关系，程序也存在着几点不足： 第一：没对计算机下棋引擎部分作更深一步
13、的挖掘和研究。对于诸如位棋盘（BitBoard）、迭代加深（Iterative Deepening）、机器学习（Machine Learning）等当今棋类对弈程序中所采用的先进技术和思想，在程序中并未涉及。这在一定程度上影响了程序中下棋引擎的工作效率。 第二：由于对人工智能算法的不熟悉，在Alpha-Beta搜索算法上花了大量的时间和精力来了解，导致程序进度的缓慢。 尽管，这些问题最终都得以解决，但却影响了程序开发的进程。 第三、程序仍在局面检测和贴图刷新上存在着随机性的出错可能（出错几率很小）。,参考文献,主要参考文献（资料） 1 钱寿宇,葛敏芳. 中国象棋对弈的计算机辅助分析J. 微电子
14、学与计算机. 1987(05) 2 岳金朋,冯速. 博弈树搜索算法在中国象棋中的应用J. 计算机系统应用. 2009(09) 3 徐心和,王骄. 中国象棋计算机博弈关键技术分析J. 小型微型计算机系统. 2006(06) 4 高强,郭琛. 哈希技术在中国象棋机器博弈系统中的应用研究J. 科学技术与工程. 2008(17) 5 谢国. 中国象棋机器博弈数据结构设计与搜索算法研究D. 西安理工大学 2008 6 董红安. 计算机五子棋博奕系统的研究与实现D. 山东师范大学 2005 7 万翼. 计算机国际象棋博弈系统的研究与实现D. 西南交通大学 2006,参考文献,8。YenWu R,Beal
15、D F.Fast,memory-efficient retrograde algorithms. ICGA Journal . 2001 9.S.J.,Chen J.C,Hsu S.C.Chinese Chess Informa-tion ICGA Games Information homepage http:/www.cs.unimaas.nl/icga/games/chinesechess . 2004 10.Hsu T.S,Liu P.Y.Verification of endgame databases. ICGA Journal . 2002,运行截图,运行截图,运行截图,运行截图,非常感谢各位老师 谢谢！,
