搜索
中国象棋游戏的设计与实现摘要象棋程序的实现可以被分为人工智能和界面程序辅助两大部分。人工智能部分主要体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选择胜利面最大的一步；而界面及程序辅助部分主要便于用户通过以前的下棋步骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确地把握整个局面。本文首先研究了中国象棋在计算机中的表示问题，接着讨论如何产生着法一系列相关内容。其次研究了博弈树的极小极大搜索技术及在此基础上发展起来的Alpha-Beta剪枝算法，使用MFC文档视图体系结构和VisualC++开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。关键词：中国象棋；人工智能；博弈树；Alpha-Beta搜索TheDesignandImplementationofChineseChessAbstractTheimplementationofachessprogramcanbedecomposedintotwomajorparts:theartificialintelligenceandtheuserinterfaceandprogramassist.Thepartofartificialintelligenceshowsthewayofcomputerthinking,andwhichstepisthebeststepwouldbedecidedbyit.Firstly,thecomputerusessearchalgorithmstosearch,andthenevaluateseveryimpossiblestep,finallychosesthebestone,theotherpartisusedfortheplayertoadjusthisthoughttothecurrentlyphases.Thedisplayofsteplistmakesplayerknowtheprocessofchessdistinctly,andletplayermakeabetterchoice.Thispaperfirstlystudieshowtorepresentachessboardincomputer,thendiscusseshowtogeneratelegalmoves.Secondly,thispaperstudiesthemini-maxsearchingprocedureofGameTree,andtheAlpha-Betapruningalgorithm.AChess-playingsystemisdesignedanddeveloped,whichisbuiltontheintegratedcomputerMFCSDIdocumentviewarchitecturebyusingVisualC++.Keywords:Chinesechess;ArtificialIntelligence;Gametree;Alpha-Betasearching目录论文总页数：22页1引言........................................................................................................................................11.1象棋设计背景和研究意义..............................................................................................11.2象棋设计研究方法..........................................................................................................12人工智能算法设计................................................................................................................22.1棋局表示..........................................................................................................................32.2着法生成..........................................................................................................................42.3搜索算法..........................................................................................................................52.4历史启发及着法排序......................................................................................................92.5局面评估..........................................................................................................................92.6程序组装........................................................................................................................113界面及程序辅助设计..........................................................................................................123.1界面基本框架................................................................................................................123.2多线程...........................................................................................................................133.3着法名称显示................................................................................................................143.4悔棋和还原....................................................................................................................154系统实现..............................................................................................................................16结论........................................................................................................错误!未定义书签。参考文献........................................................................................................错误!未定义书签。致谢........................................................................................................错误!未定义书签。声明........................................................................................................错误!未定义书签。1引言1.1象棋设计背景和研究意义电脑游戏行业经过二十年的发展，已经成为与影视、音乐等并驾齐驱的全球最重要的娱乐产业之一，其年销售额超过好莱坞的全年收入。游戏，作为一种娱乐活动。早期的人类社会由于生产力及科技的制约，只能进行一些户外的游戏。随着生产力的发展和科技进步，一种新的游戏方式——电子游戏也随之诞生。当计算机发明以后，电子游戏又多了一个新的载体。电子游戏在整个计算机产业的带动下不断地创新、发展着。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。而计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想。事实上，个人计算机软件市场的大约80%销售份额是来自游戏软件。棋牌游戏属于休闲类游戏，相对于角色扮演类游戏和即时战略类游戏等其它游戏，具有上手快、游戏时间短的特点，更利于用户进行放松休闲，为人们所喜爱，特别是棋类游戏，方便、快捷、操作简单，在休闲娱乐中占主要位置。作为中华民族悠久文化的代表之一，中国象棋不仅源远流长，而且基础广泛，作为一项智力运动，中国象棋开始走向世界。随着计算机处理速度的飞速提高，人们很早就提出了疑问：计算机是否会超越人类？世界国际象棋大师已被计算机打败，计算机已经超过了人类？而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。1.2象棋设计研究方法对于象棋来说，核心设计主要包括人工智能算法的以及整个游戏中界面及程序辅助部分的实现，主要用VisualC++进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。本文的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。该程序功能包括：*人机对弈；*搜索深度设定；（电脑棋力选择）*悔棋、还原；*着法名称显示；整个程序的实现可分为两大部分：一、人工智能算法设计（计算机下棋引擎）该部分实现了如何让计算机下中国象棋，其中涉及人机对弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。二、界面及程序辅助设计光有下棋引擎尚不能满足人机交互的基本要求，因此还需要一个框架（界面）来作为引擎的载体，同时提供一些诸如悔棋，还原之类的附属功能（程序辅助）。下面分别介绍各部分实现。由于界面及程序辅助部分涉及内容宽泛而又繁琐，因而本文只介绍其中重点部分。2人工智能算法设计程序的基本框架：从程序的结构上讲，大体上可以将引擎部分划分为四大块：棋局表示；着法生成；搜索算法；局面评估。程序的大概的思想是：首先使用一个数据结构来描述棋局信息，对某一特定的棋局信息由着法生成器生成当前下棋方所有合法的着法并依次存入着法队列。然后通过