算法课程设计Java版中国象棋.docx

《算法课程设计Java版中国象棋.docx》由会员分享，可在线阅读，更多相关《算法课程设计Java版中国象棋.docx（123页珍藏版）》请在课桌文档上搜索。

1、XX学院课程设计书系别计算机学院专业计算机科学与技术班级2006题目中国象棋教师学生一 .选题背景和研究意义2二 .需求分析32.1.功能需求分析32.2.用户需求分析41 .2.1系统运行环境42 .2.2问题描述5三 .概要设计6四 .详细设计74.1Jz74.2.着法生成84.3.搜索算法103414五 .调试运行结果14六 .源程序（附关键部分代码）17t三jLj彳124八.参考文献125一.选题背景和研究意义计算机博弈是人工智能研究的一个重要分支，被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果，这些成果在人工智能领域产生了重要影响。国际象棋计算机博弈

2、研究已经有了五十多年的历史，IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界公认第一的国际象根大师卡斯帕罗夫，标志其水平已超过国际象棋世界冠军。而中国象棋的历史更为悠久，早在2000多年前的战国时代就已经有了关于象棋的记载。中国象棋计算机博弈的难度绝不会低于国际象棋，图Ll是几种棋类游戏空间复杂度和树复杂度对比，其中中国象棋的空间复杂度是国际象棋的100倍,而树复杂度则达到了10倍。表1.1几种棋类空间复杂度和树复杂度对比棋类空间复杂度树的复杂度国际象棋IO50IO123中国象棋IO52IO150将棋IO71IO226围棋IO16010100中国象棋计算机博弈起步晚，七十年代末才

3、有相关的研究文献，比国际象棋晚了近20年，相对国际象棋计算机博弈技术还不够成熟。但近年来通过许多中国象棋软件编程爱好者和多个象棋开发团队的努力，使中国象棋软件水平有了长足的进步，慢棋已达到业余大师水平，快棋可以和象棋大师对抗。但要设计出打败人类的中国象棋软件，还需要一段发展过程。许多学者认为，对于人工智能研究而言，象棋的重要作用相当于遗传学研究的果蝇。就是说人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心;那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活

4、动中。因此对于中国象棋人机博弈问题的研究意义重大。二.需求分析2.1. 功能需求分析1、走棋和吃子对局时，由执红棋的一方先走，双方轮流各走一着，直至分出胜、负、和，对局即终了。轮到走棋的一方，将某个棋子从一个交叉点走到另一个交叉点，或者吃掉对方的棋子而占领其交叉点，都算走一着。双方各走一着，称为一个回合。2、各种棋子的走法 帅（将）：帅和将是棋中的首脑，是双方竭力争夺的目标。它只能在九宫之内活动，可上可下，可左可右，每次走动只能按竖线或横线走动一格。帅与将不能在同一直线上直接对面，否则走方判负。 仕（士）：仕（士）是帅（将）的贴身保镖，它也只能在九宫内走动。它的行棋路径只能是九宫内的斜线。 相

5、（象）：相（象）的主要作用是防守，保护自己的帅（将）。它的走法是每次循对角线走两格，俗称象走出。相（象）的活动范围限于河界以内的本方阵地，不能过河，且如果它走的田字中央有一个棋子，就不能走，俗称塞象眼。 车：车在象棋中威力最大，无论横线、竖线均可行走，只要无子阻拦，步数不受限制。因此，一车可以控制十七个点，故有一车十子寒之称。 炮：炮在不吃子的时候，走动与车完全相同。炮与被吃子之间必须隔一个棋子，进行跳吃，俗称架炮或炮打隔子。 马：马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称马走日。马一次可走的选择点可以达到四周的八个点，故有八面威风之说。如果在要去的方向有别的棋

6、子挡住，马就无法走过去，俗称蹩马腿。 兵（卒）:兵（卒）在未过河前，只能向前一步步走，过河以后,除不能后退外，允许左右移动，但也只能一次一步。2、吃子：任何棋子走动时，如果目标位置上有对方的棋子，就可以把对方的棋子拿出棋盘，再换上自己的棋子（即吃子）。22.用户需求分析2.2.1系统运行环境（1）硬件环境本系统适用于那种Inter386以上计算机，内存容量至少为128M,应配备，键盘，鼠标（最好两个），显示器等外部设备。（2）软件环境本系统的设计采用java（jdkl.6版本）编写。在WindowsXPSP2环境下测试通过本游戏软件在WindOWS平台下都可以运行。2.2.2问题描述象棋是一种

7、双方对阵的竞技项目。棋子共有三十二个，分为红黑两组，各有十六个，由对弈的双方各执一组。兵种是一样的，分为七种：红方：红方有帅一个，仕、相、车、马、炮各两个，兵五个。黑方：黑方有将一个，土、象、车、马、炮各两个，卒五个。其中帅与将；仕与土；相与象；兵与卒的作用完全相同，仅仅是为了区别红棋和黑棋而已。棋子活动的场所，叫作棋盘。在长方形的平面上，绘有九条平行的竖线和十条平行的横线相交组成，共有九十个交叉点，棋子就摆在交叉点上。中间部分，也就是棋盘的第五，第六两横线之间末画竖线的空白地带称为“河界”。两端的中间，也就是两端第四条到第六条竖线之间的正方形部位，以斜交叉线构成“米”字方格的地方，叫作“九宫

8、”（它恰好有九个交叉点）。任何棋子在走动时,如果乙方棋子可以到达的位置有对方的棋子，就可以把对方棋子拿出棋盘（称为吃子）而换上自己的棋子。只有炮的吃子方式与它的走法不同:它和对方棋子之间必须隔一个子（无论是自己的还是对方的），具备此条件才能吃掉人家。一定要注意，中隔一个棋子，这个棋子俗称“炮架子”。帅和将被吃或不能动弹即输棋。三.概要设计首先将棋盘的每一格坐标化，横坐标从Ol开始到09。纵坐标从01开始到10,初始横坐标01行上摆放红子棋子，01放车、02放马、03放象、04放土、05放帆06、07、08、09对称放士、象、马、车。横坐标03行02、08列放炮，横坐标04行01、03、05、0

9、7、09列放兵。绿子旗子和红子棋子对称放在对面。在这个初始化的坐标上每一个棋子都对应的有一个点，并且对应一个数，红子棋子从车(i=0)开始一直到帅，for(i=0;i4；列号=(potion=X_LEFT&XY_TOP&y=Y_B0TT0M之类的边界判断语句了，取而代之的是CcInBoardsq!=0其次,一维数组的好就是上下左右关系非常简明一一上面一格是sq-16,下面一格是Sq+16,左面一格是sq-1,右面一格是sq+Io马可以跳的点只有8个，终点相对起点的偏移值是固定的：constcharccKnightDelta42=-33,-31,-18,14,-14,18,31,33);而对应的

10、马腿的偏移值是：constcharccKingDelta4=-16,-1,1,16;这个数组之所以命名为CcKingDelta,是因为它也是帅(将)的偏移值。这样，找到一个马的所有走法就容易很多了。首先判断某个方向上的马腿是否有子，然后判断该方向上的两个走法是否能走：（2）界面模块用户着法合法性判断如果让用引擎的着法生成器生成所有着法看是否包含用户的着法则太浪费时间，“出棋制胜”用了一个小技巧，下面看最负责的马象着法合法性判断，（sGX,sGY）是着法起始坐标，（eGX,eGY）是着法结束坐标。（3）判断将军中国象棋的胜负标准就是帅（将）有没有被将死或困毙，我们的做法很简单一一生成所有走法，如

11、果走任意一步都会被将军，那么该局面就是将死或困毙的局面，棋局到此结束。那么如何来判断是否被将军呢？我们有两种做法：A.让对方生成全部走法，看看其中有没有走法可以吃掉自己的帅（将）；B.按照判断走法是否符合规则的思路，采用更简单的做法。第一种做法没有什么不对的,但电脑象棋程序每秒种需要分析上万个局面，对每个局面都去生成全部走法显然太花时间了，所以我们要尝试第二种做法。其实判断帅（将）是否被将军的过程并不复杂：（1）假设帅（将）是车，判断它是否能吃到对方的车和将（帅）（中国象棋中有将帅不能对脸的规则）；（2）假设帅（将）是炮，判断它是否能吃到对方的炮；（3）假设帅（将）是马，判断它是否能吃到对方的

12、马，需要注意的是，帅（将）的马腿用的数组是CCAdViSorDelta,而不是CcKingDelta;（4）假设帅（将）是过河的兵（卒）,判断它是否能吃到对方的卒（兵）。这样，一个复杂的走法生成过程（方案A）就被简化成几个简单的走法判断过程（方案B）。4.3.搜索算法（1）博弈树的基本概念如果参加博弈的不是一个主体，而是对抗性的敌我双方，则搜索的进程不仅仅取决于其中一方的意愿，而是取决于对方应付的策略。由此而产生的搜索树，通常称为博弈树。图2.2就是一颗红方走棋时展开的4层博弈树。红方走棋时展开的4层博弈树博弈树搜索的目标是在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一颗博

13、弈树。这颗博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。像这样从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树，成为完全搜索树。像这样的完全搜索树是非常庞大的，正如表1.1所示，中国象棋的完全搜索树复杂度是10吗IBM公司目前正在制造全球运算速度最快的超级计算机，估计峰值操作突破一千万亿（即10日浮点运算的限制。则计算如此一颗完全搜索树需要的时间是10侬妙，约3*1（年。所以不可能建立到棋局结束的完全搜索树，搜索也不必真地进行到分出胜负的棋局，只需要在一定深度范

14、围内对局面进行评价即可。当搜索进行到一定深度，用局面评价机制来评价棋局，按照极大极小的原则选出最优，向上回溯，给出这一局面的父亲节点的价值评价，然后再继续向上回溯，一直到根节点，最优走步就是这样搜索出来的。（2）极大极小算法极大极小值算法是解决博弈树问题的基本方法。在象棋博弈中，极大极小值算法体现在始终站在博弈一方的立场选择着法。因为一方所追求的利益恰是另一方极力避免的，所以在这一方行棋的时候，选择价值极大的儿子节点着法，另一方行棋则选择价值极小的儿子节点着法。这就是一个极大极小过程。当然，程序不能也没有必要做到搜索整棵博弈树的所有节点，对于一些己经确定为不佳的走步可以将以它为根节点的子树剪掉

15、。在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是真的想要博弈程序棋力提高，还必须有一个好的局面评价机制，即估值算法作后。就是说，用这个估值算法评价的局面价值必须是客观的、正确的，可以确凿的评价局面的优劣以及优劣的程度。如图2.3就是一颗结合估值算法搜索5层的完全极大极小博弈树。红方选揖O黑方选挣max minmaxmin图极大极小搜索在图2.3中，最底层为当前搜索深度(5层)下对各个可能出现的棋面进行估值的结果，按照由底向上推理，先由黑方选择从第5层各个子节点中选择较小的值推出第4层各个父节点，然后红方从第4各个节点中选择教大的值

16、向上推出第3层各个父节点，依次交替类推，推出第一层的节点值，从而选择出博弈路径。(3)负极大值法普通的极大极小值算法有点麻烦，一方试图取极小值，而另一方试图取极大值，也就是说我们总要检查哪一方要取极大值。负极大值法是一种可以避免此类判断的算法，负极大值算的值是各子节点的值的负数的极大值。如要这个算法正确运作。例如象棋，估值函数必须对谁走棋敏感，也就是说对于一正的估值的话,则对于一个该黑方走棋的局面返回负的估值。这样才能保证原来取极大值还是取极大值，原来取极小值则转变成取儿子节点负数的极大值。(4)Alpha-Beta搜索算法Alpha-Beta算法的原理是根据当前的信息确定儿子节点的上下界AI

17、Pha,Beta,然后根据儿子节点的儿子节点返回值进行剪枝操作。其具体过程如图所示：图左半部分是一颗极大极小树的片段，节点下面的数字为该节点的值，搜索开始时，A为MAX局面，要从所有的儿子节点中返回最大值，首先搜索第一个子节点B,假定得到返回值10,那么此时可以确定A的值必定=10。接着搜索C的第一个子节点D,得到值8,因为C为MlN局面，返回所有子节点最小值，此时可以确定C的值必定=8。不论E,F等其他C的子节点可以取道多大的值，C的值都会小于B,不会被A选中，即可剪去对等其他C的子节点的搜索。此为AIPha剪枝（下界剪枝）。图右半部分是是一颗极大极小树的片段，节点下面的数字为该节点的值，搜

18、索开始时，A为MIN局面，要从所有的儿子节点中返回最小值，首先搜索第一个子节点B,假定得到返回值10,那么此时可以确定A的值必定二10。接着搜索C的第一个子节点D,得到值12,因为C为MAX局面，返回所有子节点最大值，此时可以确定C的值必定=12。不论E,F等其他C的子节点可以取道多小的值，C的值都会大于B,不会被A选中，即可剪去对等其他C的子节点的搜索。此为Beta剪枝(上界剪枝)。如果能尽早的找到值较大的子节点，则能在搜索中剪去很多兄弟节点。所以说Alpha-Beta算法的效率很大程度上受子节点顺序的影响。3. 4.置换表几乎所有的棋类计算机博弈程序都使用了置换表技术。“出棋制胜”的置换表

19、非常简单，以局面的ZobristKey%HASHSIZE作为索引值。每个置换表项存储的内容为：.深度，B.标志，C.分值，D.最佳走法，E.ZobristLock校验码。置换表的处理函数PrObeHaSh和ReCOrdHaSh,RecordHash在判断深度后，将节点的值赋值给HaSh表项中的每个值。ProbeHash的过程：(1)检查局面所对应的置换表项，如果ZobristLock校验码匹配，那么我们就认为命中(Hit)了；(2)是否能直接利用置换表中的结果,取决于两个因素:A.深度是否达到要求，B.非PV节点还需要考虑边界。第二种情况是最好的(完全利用)，ProbeHash返回一个非-MA

20、TE_VALUE的值，这样就能不对该节点进行展开了。如果仅仅符合第一种情况，那么该置换表项的信息仍旧是有意义的一一它的最佳走法给了我们一定的启发(部分利用)。五.调试运行结果这个程序在JDK配置环境下运行，运行命令行如下：D:javacChess,java编译程序，生成CLASS文件D:javaChess执行CLASS文件初始化棋盘截图:对弈过程截图:博弈结果截图:撕游戏梅镇打开保存退出六.源程序（附关键部分代码）/* 中国象棋Java版V3.O* 作者* 源文件：CheSs.java* 最后修改时间：2005-8-20* 添加功能:实现了当前棋局的保存* /importjava.awt.*;

21、importjava.awt.event.*;importjavax.swing.*;importjava.util.*;importjava.io.*;主类publicclassChesspublicstaticvoidmain(Stringargs)newCheSSMainFranle(中国象棋Java版)；)主框架类classChessMainFrameextendsJFrameimplementsActionListener,MouseListener,Runnable玩家JLabelplay=newJLabel32;棋盘JLabelimage;窗格Containercon;工具栏JT

22、oolBarjmain;重新开始JButtonanew;悔棋JButtonrepent;打开JButtonshowOpen;保存JButtonshowSave;退出JButtonexit;当前信息JLabeltext;保存当前操作VectorFileVar;VectorVar;规则类对象(使于调用方法)ChessRulerule;/5C5C5C*C5C5C5C5C5C5C5C*C5C5C5C5C5C5C5C*C5C5C5C5C5C5C5C*C5C5C5C5C5C5CAchessManClick=true闪烁棋子并给线程响应*/AchessManClick=false吃棋子停止闪烁并给线程响应*

23、/booleanChessManClick;/*控制玩家走棋*/AchessPlayClick=I黑棋走棋*/AchessPlayClick=2红棋走棋默认红棋*/AchessPlayClick=3双方都不能走棋*/intChessPlayClick=2;控制棋子闪烁的线程Threadtmain;把第一次的单击棋子给线程响应staticintMan,i;ChessMainFrame()ChessMainFrame（StringTitle）获行客格引用con=this.getContentPane（）;con.SetLayout（null）;实例化规则类rule=newChessRuleO;Fi

24、leVar=newVectorO;Var=newVectorO；创建工具栏jmain=newJToolBarO；text=newJLabel（z,热烈欢迎）；text.SetTooITiPTeXt（提示信息”）；anew=newJButton（,z新游戏）；anew.SetTOolTiPTeXt（重新开始新的一局）；exit=newJButton（,z退出）；exit.SetTOOITiPTeXt（退出本程序）；repent=newJButton（z,悔棋”）；repent.SetTOOlTiPTeXt（返回到上次走棋的位置）；showOpen=newJBUttOn（打开）;showOpen.

25、SetTOOiTiPText（打开以前棋局）；showSave=newJBUtton（保存）；showSave.SetToOlTiPTeXt（保存当前棋局）；把组件添加到工具栏jmain.SetLayout（newGridLayout（0,6）;jmain.add（anew）;jmain.add(repent);jmain.add(showOpen);jmain.add(showSave);jmain.add(exit);jmain.add(text);jmain.SetBounds(0,500,450,30);con.add(jmain);添加棋子标签(JrawChessMan();*注册监

26、听者*/注册按扭监听anew.addActionListener(this);repent.addActionListener(this);exit.addActionListener(this);showOpen.addActionListener(this);showSave.addActionListener(this);注册棋子移动监听for(inti=0;iscreenSize.height)frameSize.height=screenSize.height;)if(frameSize.widthscreenSize.width)frameSize.width=screenSize

27、.width;)this.SetLocation(screenSize.width-frameSize.width)/2-200,(screenSize.height-frameSize.height)/2-290);this,seticonimage(newImageIcon(zz相1.gif)getImageO);this.SetResizable(false);this.SetTitle(Title);this.setSize(450,555);this,show();*添加棋子方法*/publicvoiddrawChessMan()流程控制inti,k;图标Iconin;黑色棋子车in

28、二newImageICOn(车1.GIF);for(i=0,k=10;i2;i+,k+=385)playi=newJLabel(in);playi.SetBounds(k,10,40,40);playi.SetName(车1)；马in=newImagelCon(“马LGIF);for(i=4,k=60;i6;i+,k+=285)playi=newJLabel(in);playi.setBounds(k,10,40,40);playi.SetName(马1”);相in=newIinagelCOn(相LGIF);for(i=8,k=105;i10;i+,k+=195)playi=newJLabel

29、(in);playi.SetBounds(k,10,40,40);playi.SetNaIne(相1);)士in=newImagelCon(士1.GIF)；for(i=12,k=155;i14;i+,k+=95)playi=newJLabel(in);playi.SetBounds(k,10,40,40);playi.setName(z*i1)；卒in=newImagelCon(卒LGIF);for(i=16,k=10;i21;i+,k+=96.5)playi=newJLabel(in);playi.setBounds(k,160,40,40);playi.setName(卒1+i);)炮in

30、=newIlnageICOn(炮1.GIF);for(i=26,k=60;i28;i+,k+=289)playi=newJLabel(in);playi.setBounds(k,110,40,40);playisetName(炮1+i);)/将in=newImageiconCLGIF);play30=newJLabel(in);play30.SetBounds(205,10,40,40);play30.SetName(将1”);红色棋子车in=newImagelCOn(车2.GIF);for(i=2,k=10;i4;i+,k+=385)playi=newJLabel(in);playi.set

31、Bounds(k,450,40,40);playi.SetName(车2”);马in=newImageICon(马2.GIF);for(i=6,k=60;i8;i+,k+=285)playi=newJLabel(in);playi.setBounds(k,450,40,40);playi.SetName(马2);)相in二newInIagelCon(相2.GIF);for(i=10,k=105;i12;i+,k+=195)playi=newJLabel(in);playi.setBounds(k,450,40,40);playi.SetName(相2”);)/in-newInIagelCon(

32、士2.GIF);for(i=14,k=155;i16;i+,k+=95)playi=newJLabel(in);playi.SetBounds(k,450,40,40);playi.SetNaIne(2”);兵in=newImagelCOn(兵2.GIF);for(i=21,k=10;i26;i+k+=96.5)playi=newJLabel(in);playi.setBounds(k,300,40,40);playi.setName(兵2+i);炮in二newImageICOn(炮2.GIF);for(i=28,k=60;i15&Man25&Man=O&Man3&Man7&Man11&Man

33、15&Man25&Man=O&Man3&Man7&Man11&Man16)rule.chapRule(Man,playMan,play,me);)移动将、帅elseif(Man=30Man=31)rule,wiIlRule(Man,playMan,play,me);& Ey =是否走棋错误(是否在原地没有动)if(Ex=playMan.getX()playMan.getY()text.setText(黑棋走棋);ChessPlayClick=1;elsetext.setText(红棋走棋)；ChessPlayClick=2;)elseif当前没有操作(停止闪烁)ChessManClick=false;)if单击棋子else第一次单击棋子(闪烁棋子)if(IchessManClick)for(inti=0;i32;i+)被单击的棋子if(me.getSource().equals(playi)告诉线程让该棋子闪烁Man=i;开始闪烁ChessManClick=true;break;)forif第二次单击棋子(吃棋子)elseif(chessManClick)当前没有操作(停止闪烁)chessManClick=false;for(i=0;i15&Man25&Man=O&