基于Android技术的中国象棋人机对弈游戏的设计与实现

绪论1.1研究背景1.1.1中国象棋背景中国象棋发展至今已有两千三、四百年的历史，早在战国时期就有正式的记载，堪称中国的国粹。中国象棋具有悠久的历史，深的人们的喜爱，象棋的爱好者也更是数不胜数，远在战国中国象棋便在贵族阶层广为流传，早期的象棋是象征着当时战斗场面的游戏，后来这种观念慢慢被改变，经过千年的流传不断的完善和改进，成为人们休闲娱乐、锻炼脑力思维不可获取的好方式。中国象棋体现的是一种策略，方寸之间包含天地玄机，人生哲理，使人越是细玩越觉其味悠然深远。由于简单的行棋规则，趣味性强，便捷的载体，使得象棋成为雅俗共赏的竞技项目。因此，也成为流行极为广泛的棋艺活动。是我国正式开展的78个体育项目之一，为促进该项目在世界范围内的普及和推广，在中国古代，象棋被列为士大夫们的修身之艺，现在则被视为怡神益智的一种有益的活动。有着数以亿计的爱好者。它不仅能丰富文化生活，陶冶情操，在棋战中，人们可以从攻与防、虚与实、整体与局部等复杂关系的变化中悟出某种哲理；更有助于开发智力，启迪思维，锻炼辨证分析能力和培养顽强的意志。象棋是中华民族的传统文化，不仅在国内深受群众喜爱，而且流传国外。1.1.2Android系统简介Android系统构架简介：Android是一个基于Linux®V2.6内核的交互性操作环境，同时它也是一个分层系统，Android系统架构显示如下图1.1。图１.１Aｎｄｒｏｉｄ系统构架图应用层由所有的Android应用程序组成。其中包括电子邮件客户端，SMS程序，地图，浏览器，联系人及其他。所有的应用程序都是用Java编程语言编写的。应用框架层定义了Android应用程序框架。所有的Android应用程序都是基于应用框架的。Android应用框架包括：丰富及可扩展性的视图，可以用来建立一个美观的用户界面，包括列表，网格，文本框，按钮，甚至是嵌入到Web浏览器的应用程序。一组内容提供商，使应用程序能够访问其他应用程序的数据（如电话簿），或共享自己的数据。资源管理器提供了访问的非编码资源的途径，如本地化的字符串，图形，布局文件。通知管理器允许所有应用程序显示定制的提示或通知在状态栏里。活动管理器可以管理应用程序的生命周期，并提供一个通用的后台堆栈导航。库层包括了一套被各类Android系统组件使用的C/C++库并对应用程序框架提供支持。Android的运行环境包括一套核心库和Java虚拟机（Dalvik虚拟机），已经由谷歌重新设计和优化来适合Android平台。Linux内核位于Android系统的底层并作为硬件和软件之间的一个抽象层。它提供了核心系统服务，如安全，内存管理，进程管理，网络协议栈和驱动模型。此外，一些底层功能如Dalvik虚拟机线程管理也依赖于Linux内核。Android应用新特点作为一个新的操作系统，一方面，Android可以受益于其他的成熟的操作系统的技术。另一方面，Android也会改善出现在其他操作系统上的缺陷。对于开发商的前瞻性，Android系统具有以下新的特点：允许一个应用程序被明确的定义。Android应用程序中，所有的组件可以通过系统独立启动，不过需要在一个XML文件名为AndroidManifest的文件中被声明。AndroidManifest做许多另外声明应用的组件的东西，包括：定义一些应用所需要的用户权限，如互联网接入。仅定义应用程序需要的权限和应用程序必须执行的操作权限。声明应用程序所需的最低API级别。定义硬件和软件的使用或应用程序所需的功能。声明API函数库的应用需要被对应的链接。资源和代码是分开的。在Android中，所有的非代码资源是在XML文件中定义。对于每一个包括在Android项目中的资源，SDK构建工具定义一个唯一的整数ID，它可以用来参考从应用程序代码的资源或从XML文件中定义其他资源。提供单独的资源可以从源代码中很容易地更新应用程序的不同特性，从而无需修改代码。同时通过提供一套替代资源集，使开发人员能够针对各种设备配置优化中的应用，如不同的语言和屏幕尺寸。Android作为一个完整的，开放的和自由的移动设备平台，凭借其强大的功能和良好的用户体验迅速发展成为最流行的移动操作系统。本文给出了关于Android应用框架和Android应用程序的主要工作的详细介绍。最后，推出了android平台上的音乐播放器作为一个例子来说明了这个机制。1.2本论文研究意义中国象棋是一项智力和策略的游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人机会话综合性很强的一门边缘学科，它的中心任务是研究使计算机如何去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。本次论文的研究，主要是对中国象棋在Android系统中的兼容行性，对游戏界面可观性，游戏中人机会话的研究。对于游戏中的人机会话的要点：a某种在及其上表示棋局的方法，让程序知道会话的状态；b产生合法的走棋法则，使得会话双方公正，并可以判断人类对手是否乱走；c从所有和法定的走法中选择最佳的走法的技术；d一种评估局面优化的方法，同上面技术配合做出智能选择；e一个实现游戏的界面；通过对游戏的设计，来实现游戏中棋牌的表示，着法的生成，对着法的搜索，最后对局面的评估来实现中国象棋的人机会话。2设计相关技术理论2.1游戏系统开发平台及搭建JDK和Eclipse：JDK是Sun公司针对java开发员的产品。自从Java推出以来，JDK已经成为使用最广泛的javaSDK。JDK是整个java的核心。包括运行环境Java工具和Java基础类库。JDK是学好Java的第一步。安装Eclipse的开发环境需要JDK的支持，如果没有JDK，则启动Eclipse时会报告错误。在windows上安装JDK非常简单首先在Sun官网上下载，按照默认路径进行安装。安装完成之后，可以在检查JDK是否安装成功。打开cmd窗口，输入java–version查看JDK的版本信息。出现类似下面的画面表示安装成功了：图2.1JDK测试Eclipse如果你还没有Eclipse的话，从官网上下载EclipseIDEforJavaDevelopers解压之后即可使用。AndroidSDKAndroidSDK提供了在windows平台上的开发安卓应用程序的开发组件，也就是说，不论读者使用什么样的平台都可以开发出安卓平台的应用软件，其中包含了安卓平台上开发移动应用的各种工具集。它不仅包括了安卓模拟器和用于Eclipse的安卓开发工具插件（ADT），而且包括了各种用来调试，打包盒在模拟器上安装应用的工具。安卓主要是以java语言为基础，用户可以使用java语言来开发安卓平台上的软件应用。通过SDK提供的一些工具将其打包成安卓平台使用的apk文件，然后在使用SDK中的模拟器（Emulator)来模拟和测试软件在安卓平台运行情况和效果。安装安卓的SDK，安装好JDK和Eclipse后，打开EclipseIDE。依次单击Menu项中的windows->AndroidSDKManager项，进入AndroidSDKManager界面选择Tool和需要的Android版本项进行更新安装。ADTAndroid为Eclipse定制了一个插件，及ADT（AndroidDevelopmentTools），目的是为用户提供一个强大的综合环境用于开发Android应用程序，ADT扩展了Eclipse的功能，可以让用户快速的建立Android项目，创建应用程序界面，在基于AndroidAPI的基础上添加组件，以及用SDK工具集调试应用程序，甚至导出签名（或未签名）的APKs以便发行应用程序。安装AndroidDevelopmentToolplug-in，打开EclipseIDE。依次单击Menu项中的Help->SoftwareUpdate项2.2可行性研究本次毕业设计的题目是：基于Android技术的中国象棋人机对弈游戏的设计与实现；主要是在基于Android平台开发一个手持设备应用游戏，使得游戏具有兼容性和人机会话；并对整个系统分析，设计过程给出一个论证。中国象棋游戏是棋牌类游戏，体现的是一种策略。对于行棋走棋不同的棋子有不同走棋规则，走棋都必须按照走棋规则要求，双方轮换走棋，吃子，将军。本游戏设计无疑是模拟现实人人博弈，虚拟的替换了真实的棋子棋盘，由人来和电脑直接对弈；在一个人闲暇时也可以体验博弈的乐趣。该应用游戏的设计主要从以下几方面做起：系统流程分析、系统的功能设计、系统的数据结构设计。做好这些工作需要对Android开发平台了解，并搭建平台；深入了解数据结构、Android应用程序以及各种组件(API)库函数。3游戏系统功能分析与设计3.1界面的需求分析通过以往手持设备游戏的体验，和用户对中国象棋游戏需求逻辑，游戏的功能以及操作方法把整个设计划分成单元；先是运行游戏，进入欢迎游戏界面，随后单击欢迎界面的图片进入菜单界面，在菜单中可以点击“打开声音”/“关闭声音”按钮来控制声音开关，单击“帮助”菜单可以进入帮助界面显示游戏操作方法，而在菜单界面单击“开始游戏”菜单将进入游戏主界面开始游戏，在游戏界面玩家可以通过单击自己的棋子按照行棋规则来走棋，同时可以单击声音按钮打开关闭声音，当游戏一方的“将”或者敌方的“帅”被吃掉是，会出现游戏失败或游戏胜利的界面，在游戏过程中玩家可以随时通过单击“退出”按钮返回到游戏主菜单，主菜单中还可以点击“退出游戏”结束关闭游戏。3.2游戏走棋需求设计分析进入游戏界面，游戏提示当前走棋为“帅”或者“将”，双方各走一着，直至分出胜负或者直接点击退出结束游戏，轮到走棋的一方，将某个棋子从一个交叉点走到另一个交叉点，或者吃掉对方的棋子而占领其交叉点，都算走一着，双方各走一着即一个回合，吃子时，任何棋子走动，如果目标位置上有对方的棋子，就可以把对方的棋子拿出棋盘，即屏幕上消失在显示自己的棋子。玩家走完棋后电脑相对应搜索出自己相对应的走法。程序需要让计算机在轮到它走子的时候能够执行一步它认为最有利的着法，而不是乱走；那么它就要有在诸多可供选择的着法，提供所有候选着法的列表就是着法生成器所要完成的。之后用搜索函数来搜索列表，并用局面评估函数逐一打分，最后就可以选择出最佳着法并执行。3.3类框架的设计通过对中国象棋游戏的了解，对基于Android技术的中国象棋人机对弈游戏的需求分析，游戏实现的理解并结合自己对知识点所掌握的程度；对中国象棋游戏总体设计，主要由三个类组成：共有类，辅助界面相关类，游戏界面相关类。共有类是Activity的实现类ChessActivity，该类是通过扩展基类Activity得到的，是整个游戏的控制器，也是整个游戏程序的入口；辅助界面相关类由WelcomeView欢迎界面类（该类为游戏欢迎界面的实现类，主要负责欢迎界面的绘制工作），HelpView帮助界面类（该类为帮助界面的实现类），MenuView菜单界面类（该类为菜单界面的实现类，负责绘制菜单界面以及对菜单界面的屏幕进行监听）三个类实现；游戏界面相关类由GameView游戏界面类（该类为游戏程序中最主要的类，负责绘制游戏过程中所有的信息，如棋盘、棋子、各个按钮以及胜利或失败菜单等），GuiZe象棋规则类（该类是象棋规则的实现类，其中包含所有棋子的走棋规则以及当前棋牌所有可能走法），ChessMove走法类（该类为棋子的走法的封装类，包括棋子的名称，出发点以及目标点）SearchEngine类和NegamaxEngine类对当前棋局进行搜索，搜索出最优的走棋着法；Eveluation类和ConstData类对棋局的评估，通过评估给出当前棋局分数；几个类组成。之间关系如图所示：图3.1游戏类框架图4游戏系统的设计与实现4.1游戏界面的设计4.1.1共有类ChessActivity的实现该类的主要作用是通过接受Handler消息变量，根据各个界面发送的Handler消息的类型判断所需要执行的操作。在适当的时间初始化相应的用户界面，各个界面初始化方法被调用时，并根据其他界面的需求直接将用户界面切换到相应的界面4.1.2辅助界面相关类的实现该游戏的第一个用户界面即欢迎界面，通过WelcomeView类来实现该界面加载了一个欢迎中国象棋图片，并通过监听触击屏幕图片，向Activity发送Handler消息通知控制器切换用户界面；然后切换到菜单界面MenuView。MenuView类中通过监听“开始游戏”切换到游戏界面；通过监听“打开声音”/“关闭声音”进行声音的打开与关闭，与此同时“打开声音”、“关闭声音”按钮进行切换；通过监听“帮助”来切换都帮助界面；通过监听“退出游戏”结束游戏用行退出游戏。帮助界面HelpView，该类中加载图片，图片中显示该游戏“怎么玩”同时监听“返回”按钮，向Activity发送Handler消息通知控制器切换用户界面从而返回到菜单界面。4.1.3游戏界面相关类的实现游戏界面GameView，该类是整个程序中最主要的类，该类首先是绘制屏幕上的内容棋盘和对应的棋子。提示一方先走；当“黑帅”或者“红将”被吃的话，弹出您赢了或者您输了通过监听结束游戏切换到菜单界面。或者点击退出按钮也可结束游戏切换至菜单界面。监听声音按钮来控制声音的开与关并以红色显示声音开，消失即为关。在游戏过程中，电脑走棋通过调动NegamaxEngine类中的Search（）函数调动GuiZe类中的allPossibleMoves()产生所有可能的走棋着法，然后在通过Eveluation类和ConstData类来对当前棋局进行评估得分。给不同的棋子不同的位置给不同的棋子基本值，棋子灵活价值，棋子被威胁价值，棋子被保护价值；按照算法计算出走法的价值，最后对所有的价值进行比较，价值高的也就是最终的要查找最优走棋着法。4.2中国象棋的规则及走法的实现4.2.1行棋规则中国象棋分为红黑双方，以楚河汉界为分界线，双方各执16字，分别为2车2马2相2仕2炮1将5卒，各自走法不同，具体如下：车：只可以走直线，且一步可以走任意距离，且起始点与目标点之间不得存在其他棋子。车吃子的条件是与目标棋子在一条直线上，且两子之间不得存在任何其他的棋子。红黑车规则走法的介绍：图４.１車的走法if(fromY!=toY&&fromX!=toX){//只能走直线 returnfalse; } if(fromY==toY){//走横线 if(fromX<toX){//向右走 for(i=fromX+1;i<toX;i++){//循环 if(qizi[fromY][i]!=0){ returnfalse;//返回false } } } else{//向左走 for(i=toX+1;i<fromX;i++){//循环 if(qizi[fromY][i]!=0){ returnfalse;//返回false } } } } else{//走的是竖线 if(fromY<toY){//向右走 for(j=fromY+1;j<toY;j++){ if(qizi[j][fromX]!=0) returnfalse;//返回false } } else{//向左走 for(j=toY+1;j<fromY;j++){ if(qizi[j][fromX]!=0) returnfalse;//返回false } } }break;马：只可以走“日”字方格，因此一匹马的最理想落子点有8个，但存在绊马腿的情况，即从马的位置到要走到的目标位置，顺着此方向，“日”字方格有两个方向，即两格长度和一个长度，马紧挨的两格长度方向的位置不能有子，否则即被绊住，不能走动。若目标位置为空，即可走过，若为对方的棋子，即可吃掉。图４.２马的走法红黑马规则走法的介绍：if(!((Math.abs(toX-fromX)==1&&Math.abs(toY-fromY)==2) ||(Math.abs(toX-fromX)==2&&Math.abs(toY-fromY)==1))){ returnfalse;//马走的不是日字时}if(toX-fromX==2){//向右走 i=fromX+1;//移动 j=fromY;}elseif(fromX-toX==2){//向左走 i=fromX-1;//移动 j=fromY;}elseif(toY-fromY==2){//向下走 i=fromX;//移动 j=fromY+1;}elseif(fromY-toY==2){ //向上走 i=fromX; //移动 j=fromY-1;}if(qizi[j][i]!=0) returnfalse; //绊马腿break;炮：只可以走直线，且一步可以走任意距离，其起始点与目标点之间不得存在其他棋子。炮吃子的条件是与目标棋子在一条直线上，且两子之间必须有且只有一个棋子作为“跳板”，让炮进行跳跃式攻击。红黑炮规则走法的介绍：图４.３炮的走法if(fromY!=toY&&fromX!=toX){ //炮走直线 returnfalse; //返回false}if(qizi[toY][toX]==0){ //不吃子时 if(fromY==toY){ //横线 if(fromX<toX){ //向右走 for(i=fromX+1;i<toX;i++){ if(qizi[fromY][i]!=0){ returnfalse; //返回false } } } lse{ //向走走 for(i=toX+1;i<fromX;i++){ if(qizi[fromY][i]!=0){ returnfalse; //返回false } } } } else{ //竖线 if(fromY<toY){ //向下走 for(j=fromY+1;j<toY;j++){ if(qizi[j][fromX]!=0){ returnfalse; //返回false } } } else{ //向上走 for(j=toY+1;j<fromY;j++){ if(qizi[j][fromX]!=0){ returnfalse; //返回false } } } }}else{ //吃子时 intcount=0; if(fromY==toY){ //走的是横线 if(fromX<toX){ //向右走 for(i=fromX+1;i<toX;i++){ if(qizi[fromY][i]!=0){ count++; } } if(count!=1){ returnfalse; //返回false } } else{ //向左走 for(i=toX+1;i<fromX;i++){ if(qizi[fromY][i]!=0){ count++; } } if(count!=1){ returnfalse; //返回false } } } else{ //走的是竖线 if(fromY<toY){ //向下走 for(j=fromY+1;j<toY;j++){ if(qizi[j][fromX]!=0){ count++; //返回false } } if(count!=1){ returnfalse; //返回false } } else{//向上走 for(j=toY+1;j<fromY;j++){ if(qizi[j][fromX]!=0){ count++; //返回false } } if(count!=1){ returnfalse; //返回false } } }}break;卒、兵：一步只可以走过一个方格的距离。当兵卒位于己方阵营时，只可以向前走动。当兵卒过河后到达对方阵营，可向前、向左、向右三个方向行走，即兵卒遵循的规律是绝不后退。图４.４卒的走法黑兵规则走法的介绍if(toY<fromY){ //不能回头 returnfalse; //返回false}if(fromY<5&&fromY==toY){ //过河前只能直走 returnfalse; //返回false}if(toY-fromY+Math.abs(toX-fromX)>1){ //只能走一步并且是直线 returnfalse; //返回false}break;//////////////////////////////////////////////////////红卒规则走法的介绍if(toY>fromY){ //不能回头 returnfalse; //返回false}if(fromY>4&&fromY==toY){ //过河前只能直走 returnfalse; //返回false}if(toY-fromY+Math.abs(toX-fromX)>1){ //只能走一步并且是直线 returnfalse; //返回false}break;象、相：只可以在己方阵营走动，且仅限于7个点，即己方“田”字格上的7个点，走的是斜线，走动时，起始点与目标点构成一条斜线，若该斜线的中点位置存在其他棋子，则被绊住无法走动。图４.５象的走法黑象规则走法的介绍if(toY>4){ //不能过河 returnfalse; //返回false}if(Math.abs(fromX-toX)!=2||Math.abs(fromY-toY)!=2){//象走“田”字 returnfalse; //返回false}if(qizi[(fromY+toY)/2][(fromX+toX)/2]!=0){ //象眼处有棋子 returnfalse; //返回false}break;///////////////////////////////////////////////////////红相规则走法的介绍if(toY<5){ //不能过河 returnfalse; //返回false}if(Math.abs(fromX-toX)!=2||Math.abs(fromY-toY)!=2){//象走“田”字 returnfalse; //返回false}if(qizi[(fromY+toY)/2][(fromX+toX)/2]!=0){ //象眼处有棋子 returnfalse; //返回false}break;士、仕：只可以在己方阵营走动，且仅限于5个点，即己方棋盘上所绘的两条斜线的四个顶点和交叉点。一步只可以走动一个方格的斜线距离。可进可退。图４.６士的走法黑士规则走法的介绍：if(toY>2||toX<3||toX>5){//出了九宫格 returnfalse; //返回false}if(Math.abs(fromY-toY)!=1||Math.abs(toX-fromX)!=1){//走斜线 returnfalse; //返回false}break;/////////////////////////////////////////////////////////////////////红仕规则走法的介绍：if(toY<7||toX<3||toX>5){//出了九宫格 returnfalse; //返回false}if(Math.abs(fromY-toY)!=1||Math.abs(toX-fromX)!=1){//走斜线 returnfalse; //返回false}break;将、帅：只可以在己方阵营走动，且仅限于9个点，即己方底三行中三列形成的9个交叉点，也就是俗称的“九宫”，一步只可以走动一个方格的直线距离作为本方的主将，镇守大本营，双方的主将是不能够处于同一条直线而主将之间不存在其他的棋子进行隔挡。图４.７将帅的走法黑帅规则走法的介绍：if(toY>2||toX<3||toX>5){//出了九宫格 returnfalse; //返回false}if((Math.abs(fromY-toY)+Math.abs(toX-from))>1){//只能走一步 returnfalse;//返回false}break;/////////////////////////////////////////////////////////////////////////////////红将规则走法的介绍：if(toY<7||toX<3||toX>5){//出了九宫格 returnfalse; //返回false}if((Math.abs(fromY-toY)+Math.abs(toX-from))>1){//只能走一步 returnfalse;//返回false}break;4.2.2棋盘的表示针对棋盘的设计，每一种棋子对应一个固定的值用以识别该棋子的类型，那么设计就根据红黑双方的棋子以及每个类型的棋子，设计规则类（GuiZe类，调用其中的canMove方法用以判断某一步走棋的是否可行。规则类的设计则采用了常规的办法，因为棋子的种类只有7种，且红黑双方处于棋盘的两端，某些棋子走动时的方向不一样，设计时就要进行分类讨论设计，供存在14中不同的判别方法来对所以的棋子走法进行判别是否可行，每一个判别方法都对应于其独有的判断算法。棋盘上各种棋子以及棋盘的初始布局的设计采用10*9的数组来进行标识，如下图4.8所示：图4.8棋盘初始布局各个数字的对应关系如下：0-无棋子；1-黑方的帅；2-黑方的车；3-黑方的马；4-黑方的炮；5-黑方的士；6-黑方的象；7-黑方的卒；8-红方的将；9-红方的车；10-红方的马；11-红方的炮；12-红方的士；13-红方的相；14-红方的兵。坐标(0,0)到坐标(8,4)之间的坐标代表楚河汉界的一方，坐标(0,5)到坐标(8,9)之间的坐标代表楚河汉界的另一方，即红黑双方各自的领土。电脑走棋时通过构造一个走法类ChessMove，创建一个对象调用NegamaxEngine类中的Search（）函数根据当前局势查询一个最好的走法记录棋子的原有位置坐标、目标位置坐标、棋子类型并对该对象进行初始化。然后根据该对象记录的原有位置坐标和目标位置坐标进行数据改变达到行棋目的。玩家走棋是通过对屏幕进行监听，从而记录棋子类型，原有位置坐标和目标位置坐标，通过调用规则类GuiZe中的CanMove判断该棋子走法是否可行符合棋子走棋规则，可行就改变原有位置和目标位置数据，达到行棋的目的轮到走棋的一方，游戏界面当前位置显示走棋一方的“黑帅”或者“红将”，将某个棋子从一个交叉点走到另一个交叉点，或者吃掉对方的棋子而占领其交叉点，这样一方走棋结束当前位置显示改变轮到另一方走棋。任何棋子走动，如果目标位置上有对方的棋子，就可以把对方的棋子拿出棋盘，即在10*9数组中相应位置的数字变为自己棋子所对应的数字，自己棋子原来所在的位置对应数组的数字变为0，刷帧线程不断的刷新界面改变屏幕显示，这样对方的棋子就被吃掉，在屏幕上消失在对应显示自己的棋子；如果目标位置上没有对方棋子，10*9数组对应目标位置数字改变，原有位置数字变为0，刷帧线程更新界面改变显示。4.3游戏人机会话的实现4.3.1着法的生成在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。这里的合法着法是通过象棋的行棋规则来确定；产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。因此可以将着法队列定义为二维数组MoveList[10][100]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。关于搜索层数，设定为4，实际使用的是1到3（在界面中将其限定为1—3）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。在配置为1.5G，512M内存的计算机上最多只能搜索3层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为100，应当可以保证十分的安全。4.3.2搜索算法中国象棋博弈为二人零和，全信息，非偶然博弈，他的特征如下：

(1)对弈的MAX、MIN双方轮流采取思考走棋，对弈的结果有三种情况：和局；MAX方胜，MIN方败；MIN方胜，MAX方败。

(2)在对弈过程中，任何一方都了解当前的格局和过去的行棋历史。

(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的走法，不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。最终也就组成了一颗博弈树(如图4.9)所示。图4.9博弈树示意图在这棵博弈树中，根节点是初始局面，一个节点下的每个分支代表一个着法，分支相连的子节点是走了这个着法后会出现的局面。由于双方交替出着在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案，使自己利益最大化。让始终从红方的角度来考虑。轮到红方走棋时，红方总是选择对自己最有利的着法，从而在生成的一系列子节点中寻找分值最高的局面（即MAX层），据此返回最佳着法；然后轮到黑方走棋，黑方也选对自己最有利的着法，但在红方看来，这个着法对自己最不利，所以从红方的角度来看，黑方就选择了分值最低的局面（即MIN层），从而返回黑方的最佳着法。可以用一个简化的博弈树模型来表示（如图4.10）所示：在这棵树中，矩形代表红方，圆代表黑方，分别取子节点的极大/极小值。根据上面的描述，我们选择了第二个着法。而加粗的这条路径就是极大极小算法思考的过程。图4.10博弈树搜索过程示意下图4.11为负极大值的伪代码的实现图4.11负极大值算法4.3.3局面评估局面评估是一个通过既有的棋类知识来评估一个局面的优劣的过程。这一过程对具体的棋类知识的依赖程度很深，但是仍有一般性的规律可循。

（1）棋子的价值评估，简单的说就是评估双方都有哪些棋子在棋盘上。根据我们的经验，可以让一个车的价值为500，一个马的价值为300，一个兵的价值为100等等。将的价值为无限大。一方的棋子总值就是棋盘上存活的该方棋子乘以棋子的价值的和。用一个式子表示：chessValue=sum(Number*baseValude)其中Number是某种棋子的数量，baseValue是该中棋子的价值，sum是对各种棋子的总价值求和。如果红色棋子的价值总和大于黑色的棋子价值总和，通常意味着红方的局势优于黑方。而红黑双方的chessValue之差越大，红方的优势就越大。

（2）棋子的灵活性与棋盘控制

棋子的灵活性是指棋子的活动范围，通常越大越好。一匹不能动的马很难在棋局中发挥重要的作用；同样，一个蹲在角落里的车也是价值不高。评估棋子的灵活性较为简单，将一个棋子的所有合法的走法罗列出来，称上该种棋子每一可移动的价值就行了。可用下面的公式：mobility＝sum(moveNumber*flexValue)其中，moveNumber是某种棋子的合法走法数量，flexValue是该种棋子每一走法的价值，sum是对所有棋子灵活性价值求和。mobility就是所有棋子的灵活性分数。与灵活性评估类似，还可以评估博弈双方对棋盘上位置的控制能力。在象棋中，如果一位置落在某方棋子的合法走不上，就可以认为被该方控制。如果某一位置同时落在双方的合法的步上，我们可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方应该在这项得分上更多。（3）棋子之间的关系棋子之间的关系也是估值重要的内容之一，我们可以将某个棋子被对方棋子威胁看成是一个步利因素。类如红车的位置在黑马的合法走法当中，此时我们可以把红车的价值减去一个值如200来刻画这种情形。而如果红马在黑车的合法走步之中，而红马同时也在红卒的合法走步之中，我们可以认为红马置于红卒的保护之下，没有受到威胁，价值不变。棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应该认为红马受到的威胁较轻。而如果此时轮到黑方走棋，就应该认为受到的危险很大，应减去一个相对较大的值了。如果将被威胁，且轮到对方走棋，那么无论有何种可以走到将位都没有意义，将等于失去了。此时应该结束估值返回失败的估值。棋子间关系的评估可以在很大程度上提高估值的精度，通常是博弈估值的必备内容。5游戏系统模块的设计实现5.1欢迎界面运行该游戏，首先进入的将是欢迎界面，效果如图5.1所示。图5.1游戏欢迎界面5.2菜单界面（1）进入欢迎界面后，然后点击屏幕将进入菜单界面如图5.2所示。图5.2菜单界面点击“关闭声音”按钮来关闭声音，显示如图5.3所示。原来的“关闭声音”按钮变成“打开声音”按钮。图5.3关闭声音5.3帮助界面点击菜单界面中的“帮助”按钮，界面切换至帮助界面如图5.4所示。图5.4帮助界面点击帮助界面中的“返回”按钮，界面返回至菜单界面。5.4游戏界面（1）点击“开始游戏”按钮，界面切换至游戏界面如（图5）所示。当前由“红将”即红棋先走，声音状态为关闭状态。图5.5游戏界面（2）玩家先走棋，玩家走一步棋；当前位置显示为黑帅，轮到电脑走棋如图5.6所示：图5.6轮到电脑走棋（3）电脑走完棋后当前位置显示红将，轮到玩家走棋；如图5.7所示：图5.7电脑走完棋转换玩家（4）对局结束红方将输了（电脑赢了)如图5.8所示：图5.8红方玩家输了（电脑胜利）(5)对局结束红方将赢了（电脑输了）如图5.9所示：图5.9红方玩家赢了（电脑输了）（5）点击“您输了”小框体或者点击“退出”按钮退出游戏界面切换到菜单界面，如图5.9所示：图5.9从游戏界面返回菜单界面6运行测试系统测试是软件开发投入使用之前必不可少的一个步骤，同时也必须严格要求进行测试，对程序的功能，性能、可用性、客户端兼容性和美观等测试。测试完成后要上交测试报告，我们可以根据测试报告及时发现问题并提出解决方案，便于系统的维护与升级。经过最初的测试，系统能正常运行，能够很好地实现模块界面间的切换，音乐声音的开关，象棋能够按照规则来行走等功能都能正常运行；同时电脑也可以进行走棋，实现人和电脑下棋。不足是在游戏过程中，人和电脑对弈电脑着法比较粗糙，只是初步的实现人工智能。通过对大量资料的了解学习，最终初步设计实现了负极大值搜索引擎的搜索和局面的评估代码。对于负极大值搜索，由于对于每层每个节点都要扫描评估，如果层次增加，那样的数据量也就相当的大，以至于搜索的效率也会变差。造成象棋对弈过程中电脑走棋思索时间太长，将使得玩家受不了。对于搜索算法和局面评估还有待于继续实现和完善。7结束语本论文详细论述了基于Android技术中国象棋人机对弈的设计与实现，采用了JDK，EclipseforIDE，AndroidSDK，ADT等工具。使得应用程序基本实现了系统功能需求分析中的基本功能。对Android手机的兼容，欢迎界面、菜单界面、帮助界面、游戏界面之间的切换，背景音乐的开与关，安全的退出游戏，棋子按规则行走等基本功能都得到实现；而且粗略的完成了象棋的人机对弈。进入游戏界面便可以开始和电脑对弈。由于技术和时间的问题，本系统对弈时电脑走棋相对比较粗糙，系统中还存在着许多不足的地方需要改正和完善，如人机对战时电脑走棋人工智能还欠缺。由于对博弈树的算法没能够完全掌握，只是初步设计实现了负极大值搜索引擎。对于人机博弈搜索算法只是用了负极大值搜索，负极大值搜索由于搜索太多效率较差由此设想可以通过对几种不同的算法如历史表法、迭代加深、极小窗口、渴望搜索、alpha-beta等的同时实现然后选择有效的搜索，来提高电脑人工智能的效率。对于这些算法在后面工作中有待于实现。致谢经过这段时间的忙碌和工作，本次毕业设计已经接近尾声，作为一个本科生的毕业设计，由于经验的匮乏，难免有许多考虑不周全的地方，如果没有导师的督促指导，以及一起工作的同学们的支持，想要完成这个设计是难以想象的。在此更要感谢我的导师林椹尠老师和专业老师，是你们的细心指导和关怀，使我能够顺利的完成毕业论文。我的设计较为复杂烦琐，而且涉及到的一些技术算法很是生僻，但是林老师仍然细心地纠正我程序设计中的错误，并且为我提供阅读资料和开发文档供我参考。在我的学业和论文的研究工作中无不倾注着老师们辛勤的汗水和心血。老师的严谨治学态度、渊博的知识、无私的奉献精神使我深受启迪。从尊敬的导师身上，我不仅学到了扎实、宽广的专业知识，也学到了做人的道理。在此我要向我的导师致以最衷心的感谢和深深的敬意。然后还要感谢大学四年来所有的老师，为我们打下一定的技术知识的基础；同时还要感谢所有的同学们，正是因为有了你们的支持和鼓励。此次毕业设计才会顺利完成。

最后感谢西安邮电大学和理学院这四年来对我的教导，使我能够成长为现在这样一个拥有技术，即将踏入社会的学子。参考文献[1]徐心和,王骄.中国象棋计算机博弈关键技术分析.小型微型计算机系统,2006,27(6):961–965。[2]黄晨等.象棋百科全书.。[3]马占欣,李亚,陆玉昌.用遗传算法解决博弈问题.河南科学,2007,25(2):273-277。[4]王骄,王涛,罗艳红,等.中国象棋计算机博弈系统评估函数的自适应遗传算法实现.东北大学学报,2005,126(10):949-952.。[5]付强,陈焕文.中国象棋人机对弈的自学习方法研究.计算机技术与发展,2007,17(12):76-79。[6]王赠凯,吕维先.机器博弈搜索技术分析.软件导刊,2007,2:26-27。[7]张从明、马京成.网络教学设计.第四军医大学出版社，2004。[8]周玮,王水涛,孙旸.中国象棋计算机博弈中的一种数据结构方法.计算机工程与应用,2006.35:219。附录：ChessActivity.javapackagecom.example.chessgame;importandroid.app.Activity;//引入相关的包importandroid.media.MediaPlayer;importandroid.os.Bundle;importandroid.os.Handler;importandroid.os.Message;importandroid.view.Window;importandroid.view.WindowManager;publicclassChessActivityextendsActivity{ booleanisSound=true;//是否播放声音 MediaPlayerstartSound;//开始和菜单时的音乐 MediaPlayergamemusic;//游戏声音 HandlermyHandler=newHandler(){//用来更新UI线程中的控件publicvoidhandleMessage(Messagemsg){ if(msg.what==1){ //WelcomeView或HelpView或GameView传来的消息，切换到MenuView initMenuView();//初始化并切换到菜单界面 } elseif(msg.what==2){//MenuView传来的消息，切换到GameView initGameView();//初始化并切换到游戏界面 } elseif(msg.what==3){//MenuView传来的消息，切换到HelpView initHelpView();//初始化并切换到帮助界面 }} }; publicvoidonCreate(BundlesavedInstanceState){//重写的onCreatesuper.onCreate(savedInstanceState); //全屏 requestWindowFeature(Window.FEATURE_NO_TITLE); getWindow().setFlags(WindowManager.LayoutParams.FLAG_FULLSCREEN, WindowManager.LayoutParams.FLAG_FULLSCREEN); startSound=MediaPlayer.create(this,R.raw.startsound);//加载欢迎声音 startSound.setLooping(true);//设置游戏声音循环播放 gamemusic=MediaPlayer.create(this,R.raw.gamemusic);//游戏过程的背景声音 gamemusic.setLooping(true);//设置游戏声音循环播放this.initWelcomeView();//初始化欢迎界面}publicvoidinitWelcomeView(){//初始化欢迎界面 this.setContentView(newWelcomeView(this,this));//切换到欢迎界面 if(isSound){//需要播放声音时 startSound.start();//播放声音 }}publicvoidinitGameView(){//初始化游戏界面 this.setContentView(newGameView(this,this));//切换到游戏界面}publicvoidinitMenuView(){//初始化菜单界面 if(startSound!=null){//停止 startSound.stop();//停止播放声音 startSound=null; } if(this.isSound){//是否播放声音 gamemusic.start();//播放声音 } this.setContentView(newMenuView(this,this));//切换View}publicvoidinitHelpView(){//初始化帮助界面 this.setContentView(newHelpView(this,this));//切换到帮助界面}}ChessMove.javapackagecom.example.chessgame;/***该类为棋子的一个走法*包含是什么棋子*起始点的位置*目标点的位置*以及估值时所用到的score*/publicclassChessMove{ intChessID;//表明是什么棋子 intfromX;//起始的坐标 intfromY; inttoX;//目的地的坐标 inttoY; intscore;//值,估值时会用到 publicChessMove(intChessID,intfromX,intfromY,inttoX,inttoY,intscore){//构造器 this.ChessID=ChessID;//棋子的类型 this.fromX=fromX;//棋子的起始坐标 this.fromY=fromY; this.toX=toX;//棋子的目标点x坐标 this.toY=toY;//棋子的目标点y坐标 this.score=score; }}SearchEngine.javapackagecom.example.chessgame;publicclassSearchEngine{ //表示棋盘棋的分布publicstaticintm_curPosition[][]=newint[10][9];//记录最佳走棋publicstaticChessMovebestMove=newChessMove();//走法产生七器publicstaticGuiZemoveGen=newGuiZe();//估值产生器publicstaticEveluationm_eve=newEveluation();//搜索深度publicstaticintm_searchDepth;//当前搜索深度publicstaticintm_maxDepth;//移动棋子publicstaticvoidsearchAgoodMove(intposition[][]){}publicstaticintmakeMove(ChessMovedata){intchessID; chessID=m_curPosition[data.toY][data.toX];m_curPosition[data.toY][data.toX]=m_curPosition[data.fromY][data.fromX];m_curPosition[data.fromY][data.fromX]=ConstData.NOCHESS;returnchessID;}//判断游戏时候结束publicstaticintisGameOver(intposition[][],intdepth){inti,j;booleanredLive=false,blackLive=false;for(i=0;i<3;++i)for(j=3;j<6;++j){if(position[i][j]==1)blackLive=true;}for(i=7;i<10;++i)for(j=3;j<6;++j){if(position[i][j]==8)redLive=true;}i=(m_maxDepth-depth+1)%2;//取当前奇偶标志if(!redLive)//红将不在了{if(i!=0)return19990+depth;elsereturn-19990-depth;}if(!blackLive)if(0!=i)return-19990-depth;elsereturn19990+depth;return0;//两将都在，返回0}//取消移动publicstaticvoidunMakeMove(ChessMovemove,intchessID){m_curPosition[move.fromY][move.fromX]=m_curPosition[move.toY][move.toX];m_curPosition[move.toY][move.toX]=chessID;}}NegamaxEngine.javapackagecom.example.chessgame;publicclassNegamaxEngineextendsSearchEngine{ publicNegamaxEngine(){ } publicstaticChessMoveSearch(int[][]position){ searchAgoodMove(position); returnbestMove; } publicstaticvoidsearchAgoodMove(int[][]position){m_maxDepth=m_searchDepth;inti,j;for(i=0;i<10;++i)for(j=0;j<9;++j)m_curPosition[i][j]=position[i][j];negaMax(m_maxDepth);//调用负极大值搜索引擎try{ Thread.sleep(4000); }catch(InterruptedExceptione){ //TODOAuto-generatedcatchblock e.printStackTrace(); }makeMove(bestMove);}//负极大值搜索引擎publicstaticintnegaMax(intdepth){intcurrent=-20000;intscore=0;intcount=0,i;inttype;i=isGameOver(m_curPosition,depth);if(i!=0)//不等于0表示某方的王不存在了，直接返回{returni;}booleanside;if((m_maxDepth-depth)%2==1)side=true;elseside=false;if(depth<=0){//搜索到叶子节点，返回估值信息 returnm_eve.eveluation(m_curPosition,side);}//生产所有可能的走法，count=moveGen.allPossibleMoves(m_curPosition,depth,side);for(i=0;i<count;++i){//尝试每种走法type=makeMove(moveGen.MoveList[depth][i]);//返回此种走法的估值分数score=-negaMax(depth-1);//取消上次走法unMakeMove(moveGen.MoveList[depth][i],type);//若当前走法更优，则记录下来if(score>current){current=score;//如果到了根节点Sif(depth==m_maxDepth){//记录最优的走棋，把它保存到m_bestMove中bestMove=moveGen.MoveList[depth][i];}}}returncurrent;}}ConstDate.javapackagecom.example.chessgame;publicclassConstData{ publicfinalstaticintNOCHESS=0;//无子//黑方publicfinalstaticintB_KING=1;//黑帅publicfinalstaticintB_CAR=2;//黑车publicfinalstaticintB_HORSE=3;//黑马publicfinalstaticintB_CANON=4;//黑炮publicfinalstaticintB_BISHOP=5;//黑士publicfinalstaticintB_ELEPHANT=6;//黑象publicfinalstaticintB_PAWN=7;//黑兵publicfinalstaticintB_BEGIN=1;publicfinalstaticintB_END=7;//红方publicfinalstaticintR_KING=8;//红将publicfinalstaticintR_CAR=9;//红车publicfinalstaticintR_HORSE=10;//红马publicfinalstaticintR_CANON=11;//红炮publicfinalstaticintR_BISHOP=12;//红仕publicfinalstaticintR_ELEPHANT=13;//红相publicfinalstaticintR_PAWN=14;//红卒publicfinalstaticintR_BEGIN=8;publicfinalstaticintR_END=14;//定义每种棋的价值//兵100，士250，象250，马350，炮350车500publicfinalstaticintBASEVALUE_PAWN=100;publicfinalstaticintBASEVALUE_BISHOP=250;publicfinalstaticintBASEVALUE_ELEPHANT=250;publicfinalstaticintBASEVALUE_HORSE=350;publicfinalstaticintBASEVALUE_CANON=350;publicfinalstaticintBASEVALUE_CAR=500;publicfinalstaticintBASEVALUE_KING=10000;//定义各种棋子的灵活性//也就是每多一个可走位置应加上的值//兵15，士1，象1，车6，马12，炮6，王0publicfinalstaticintFLEXIBLE_PAWN=15;publicfinalstaticintFLEXIBLE_BISHOP=1;publicfinalstaticintFLEXIBLE_ELEPHANT=1;publicfinalstaticintFLEXIBLE_HORSE=12;publicfinalstaticintFLEXIBLE_CANON=6;publicfinalstaticintFLEXIBLE_CAR=6;publicfinalstaticintFLEXIBLE_KING=0;//初始棋盘publicfinalstaticintINITCHESSBOARD[][]={{2,3,6,5,1,5,6,3,2},{0,0,0,0,0,0,0,0,0},{0,4,0,0,0,0,0,4,0},{7,0,7,0,7,0,7,0,7},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{14,0,14,0,14,0,14,0,14},{0,11,0,0,0,0,0,11,0},{0,0,0,0,0,0,0,0,0},