当前位置:首页>> >>


基于java的中国象棋.rar

收藏

资源目录
    文档预览:
    编号:20180913143532390    类型:共享资源    大小:3.72MB    格式:RAR    上传时间:2018-09-13
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    40
    金币
    关 键 词:
    基于 java 中国象棋
    资源描述:
    太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸i基于 JAVA 的中国象棋摘要近年来,现代化的人工智能以及先进的计算机技术迅猛发展,基于此基础的电脑象棋程序,其下棋水平也得到了进一步的提升。然而,早在二十世纪的六十年代初期,来此美国麻省理工学院的约翰·麦卡锡就提出了修剪算法——“alpha-beta” 。在该算法提出以前,通常计算机下棋程序在决定每一步走步时,所需的棋盘状态空间的搜索量都是指数级别的,而该算法则将这一搜索量的数量级减少为指数的平方根,这极大程度地提高了电脑下棋程序的水平。而随后 IBM 公司推出的超级计算机“Deep Blue”,则是一个不择不扣的神话,这一耗资上千万,耗时 8 年所建造出的世界上最强大的国际象棋“棋手” ,着实为广大棋迷们所神往。本文内容根据以往国内外象棋程序在设计上所取得的一些成功案例及经验,为中国象棋设计其基本的思路和算法。关键词:中国象棋,位棋盘,alpha-beta 搜索,Zobrist 键值,置换表太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸Chinese Chess based on JAVAAbstractIn recent years, modern artificial intelligence as well as the rapid development of advanced computer technology, computer chess program based on this foundation, its level of chess also got further improvement.However, as early as the early 60 s of the 20th century, to the United States at the Massachusetts institute of technology, John McCarthy was proposed pruning algorithm -- “alpha and beta“. Before the algorithm is put forward, the computer chess programs usually every step in deciding when walking, the board of state space search volume index level, while the algorithm reduces the search quantity of an order of magnitude as the index to the square root of the drastically increased the level of computer chess program.And then IBM supercomputer “Deep Blue“, is a myth, not choose the travel this at a cost of tens of millions, spent eight years built by the world's most powerful chess “chess player“, is by the masses of chess enthusiasts. This article content based on previous chess programs at home and abroad in the design of some successful cases and experience, design the basic train of thought for Chinese chess and algorithms.Keywords: Chinese Chess, bit board, alpha-beta search, zobrist keys, transposition table太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸目 录摘要 .......................................................................iAbstract ...................................................................ii目 录 .....................................................................1引 言 ...................................................................11 概述 ....................................................................21.1 棋盘的标记 ...........................................................21.1.1 纵线方式 ..........................................................21.1.2 坐标方式 ..........................................................21.2 棋子的名称 ...........................................................31.3 棋谱的记录方法 .......................................................31.4 历史局面的表示及存储 .................................................41.5 棋谱记录文件的格式 ...................................................41.5.1 标签部分 ..........................................................41.5.2 棋谱记录部分 ......................................................51.5.3 XML 格式 .........................................................52 基本数据结构—— 位棋盘 ..................................................72.1 什么是位棋盘 .........................................................72.2 位棋盘的作用 .........................................................72.3 位棋盘的基本运算 .....................................................92.4 Java 中位棋盘的实现 ...................................................92.4.1 位棋盘类的实现 ....................................................92.4.2 位棋盘的初始化 ...................................................102.4.3 位棋盘的更新 .....................................................103 基本数据结构—— Zobrist 键值 .............................................113.1 比较局面的方法 ......................................................113.2 Zobrist 键值的实现方法 ................................................113.3 Zobrist 键值的工作原理及用途 ..........................................113.3.1 Zobrist 键值的工作原理 .............................................113.3.2 Zobrist 键值的用途 .................................................123.4 Java 中实现 Zobrist 键值 ................................................124 着法生成 ...............................................................144.1 伪合法着法的生成 ....................................................144.1.1 数组及其下标的含义 ...............................................144.1.2 算法示例—— 车炮的伪合法着法生成 .................................16太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸4.2 合法着法的生成 ......................................................185 搜索算法 ...............................................................215.1 最小-最大搜索 .......................................................215.1.1 基于最小-最大的评价函数 ..........................................215.1.2 最小-最大搜索 ....................................................215.1.3 负值最大函数 .....................................................235.2 Alpha-Beta 搜索 .......................................................235.2.1 最小-最大搜索算法的问题 ..........................................235.2.2 Alpha-Beta 修剪 ...................................................245.2.3 Alpha-Beta 修剪算法的实现 .........................................255.2.4 可能的弱点 .......................................................265.3 迭代加深 ............................................................265.4 置换表 ..............................................................275.4.1 置换表的实现 .....................................................275.4.2 替换策略 .........................................................296 局面评价函数 ...........................................................306.1 评价函数的实现方法 ..................................................306.1.1 算法设计思路 .....................................................306.1.2 评价要素的组合 ...................................................316.2 评价函数所需的信息 ..................................................317 程序的设计及实现 .......................................................347.1 搜索引擎的实现(engine 包) ..........................................347.2 信息传输机制(message 包) ...........................................347.3 棋子(pieces 包) ....................................................357.4 主控模块(main 包) .................................................35参考文献 .................................................................36致 谢 ..................................................................37外文文献 .................................................................38太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸0引 言计算机象棋水平的发展,依赖的是计算机软硬件技术的不断提高。国际象棋对弈平台有两个非常好的典范,即 WinBoard 和 ChessBase。前者是作为一个国际象棋对弈平台的同时,又可以直接对象棋的棋谱进行编辑。后者则是国际象棋的一个商业数据库和象棋对弈软件。他们都为国际象棋爱好者以及研究人员大开方便之门。国际象棋软件作为一种新兴产业,它有着自己十分成功的商业运作。与此相对的,中国象棋在计算机上的运用实则刚刚起步,由于缺乏必要的基础工作,尽管国内有相当一部分制作计算机中国象棋的专业网站与专业软件,但是,计算机技术在中国象棋上的应用优势仍然无法清晰明朗地体现出来。在中国象棋的软件设计过程中,国际象棋软件有很多优秀的思想以及成功经验值得我们来借鉴。例如,微软公司的程序设计师 B. Moreland,业余时间用来进行国际象棋引擎软件 Ferret 的研究开发,他写的关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。虽然如此,中国象棋也仍然与国际象棋存在着巨大的差异,因此国际象棋的某些成熟技术,无法直接应用于中国象棋,需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题,总结出一些搜索引擎的设计方法,并给出 java 语言的实现。太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸11 概述中国象棋是由两人下的。一方称为红方(或白方),一方称为黑方。对局时由红方先走,黑方后走,一次一着,双方轮流走棋,直到对局结束为止。棋子的走法及详细规则见《中国象棋竞赛规则》,本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。1.1 棋盘的标记象棋的着法表示,简而言之就是某个棋子从什么位置走到什么位置。通常,表示方法可以分为“纵线方式”和“坐标方式”两种,现在作简要说明。1.1.1 纵线方式这是中国象棋常用的表示方法,即棋子从棋盘的哪条线走到哪条线。中国象棋规定,对于红方来说的纵线从右到左依次用“一”到“九”表示,黑方则是“1”到“9”(如图 1.1(左)所示),这种表示方式体现了古代中国象棋研究者的智慧。 1.1.2 坐标方式这是套用国际象棋中的表示方法,即把每个格子按坐标编号(如图 1.1(右)所示),只要知道起始格子和到达格子,就确定了着法,这种表示方式更方便也更合理,而且还可以移植到其他棋类游戏中。采用这种方法来表示,棋盘的纵线从左到右(红方)依次为 a b c d e f g h i,横线从下到上(红方)依次为 0 1 2 3 4 5 6 7 8 9(如图 1.1(右)所示)。1 2 3 4 5 6 7 8 9九 八 七 六 五 四 三 二 一a B c d e f g h i 9 98 87 76 65 54 43 32 21 10 0a B c d e f g h i (左) (右)图 1.1 中国象棋与国际象棋常用表示方法太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸21.2 棋子的名称 为方便表示,中国象棋的棋子名称除了用汉字以外,还可以用字母,字母可从国际象棋中稍加改动得到,而数字是为了方便着法的输入(以便用在数字小键盘上)(见表1.2):表 1.2 中国象棋中英文名称对照表格红方 黑方 字母 英文单词 数字帅 将 K King 1仕 士 A Advisor 2相 象 B Bishop 3马 马 N Knight 4车 车 R Rook 5炮 炮 C Cannon 6兵 卒 P Pawn 71.3 棋谱的记录方法现以如下局面为例说明各种记谱方法对于右图图 1.3 的局面,记法如下:1.炮二平五 炮8平52.炮五进四 士4进53.马二进三 马8进74.炮八平五 马2进35.前炮退二 车9平8图 1.3 象棋记谱方法示例图太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸3坐标格式包括:棋子的名称、起点和终点的位置(起点和终点用‘-’连接),对上面的走法,记录如表 1.3.1(省略了吃子、将军等信息):表 1.3.1 棋子走步记录法 1、Ch2-e2(炮二平五) Ch7-e7(炮8平5)2、Ce2-e6(炮五进四 ) Ad9-e8(士4进5)3、Nh0-g2(马二进三 ) Nh9-g7(马8进7 )4、Cb2-e2(炮八平五) Nb9-c7(马2进3)5、Ce6-e4(前炮退二 ) Ri9-h9(车9平8)1.4 历史局面的表示及存储中国象棋的一个局面可以用一个“FEN 格式串”来表示。 FEN 格式串是由 4 段ASCII 字符串组成的代码(彼此 3 个空格隔开),这 4 段代码的意义依次是: (1) 棋盘上的棋子,这是 FEN 格式串的主要部分; (2) 当前局面轮到哪一方走子; (3) 最近一次吃子或者进兵后棋局进行的步数(半回合数),用来判断“50 回合自然限着”;(4) 棋局的回合数。现以最初局面为例详细说明如下:rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w 0 1 第一部分(w 前面的字符):表示棋盘布局,小写表示黑方棋子,大写表示红方棋子。例如前九个字母 rnbakabnr 表示棋盘第一行的棋子分别为黑方的 “车马象士将士象马车” , “/”为棋盘行与行之间的分割;数字“ 9(5,1)”表示该行从该位置起连续 9(5, 1)个位置无棋子。 第二部分(w):表示轮到哪一方走棋,如果是 w 表示轮到红方(白方)走,是 b 表示轮到黑方走。 第三部分(w 后的数字 0):表示自然限着。 第四部分(w 后的数字 1):表示当前局面的回合数。1.5 棋谱记录文件的格式存放棋谱的文件分为两个部分:标签部分和棋谱部分,现分述如下:1.5.1 标签部分有如下标签:1、Event :比赛名; 2、Site:比赛地点; 3、Date:比赛日期,格式统一为 “yyyy.mm.dd“; 4、Red:红方棋手; 5、Black:黑方棋手; 6、Result:比赛结果,“红先胜”用“1-0”表示,“黑先胜”用“0-1”表示,和棋用“1/2-1/2”7、FenStr:起始局面。如果空缺,表示起始局面是最初局面。太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸41.5.2 棋谱记录部分棋谱记录部分必须在标签部分的后面,棋谱部分当中不能插入标签; 每一回合都由“回合数”、“红方着法”和“黑方着法”三部分组成,回合数后面要跟“.”(句点),三者之间用两个分隔符隔开(回合数后面的句点也不例外),回合之间也用分隔符隔开。现举一个例子如下:例 1:[Event “第 19 届五羊杯全国象棋冠军邀请赛 “][Date “1998.12.09“][Site “广州“][Red “徐天红“][Black “许银川 “][Result “1/2-1/2“]1. 炮二平五 马8进7 2. 马二进三 车9平83. 车一平二 马2进3 4. 兵七进一 卒7进15. 车二进六 炮8平9 6. 车二平三 炮9退17. 马八进九 车8进5 8. 兵五进一 马3退59. 炮八进四 炮2平5 10. 马九进七 炮9平7例 2:[Event “全国象棋冠军邀请赛“][Date “1999.12.15“][Site “广州“][Red “吕钦“][Black “许银川 “][FEN “3k1ab2/4a4/8b/6NPP/9/4n1P2/6p2/4B4/4A4/2BAK4 w - - 0 46“][Result “1-0“]46. 兵一进一 卒7进147. 兵一平二 卒7进148. 前兵平三 卒7平649. 马三退五 马5退350. 兵二平三 马3进251. 马五退六 1.5.3 XML 格式全国象棋冠军邀请赛 太 原 理 工 大 学 毕 业 设 计 (论 文 )用 纸5广州 1999.12.09 许银川 聂卫平 rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/9/1C5C1/9/RN2K2NR r - - 0 11-0 炮八平五 炮8平5
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:基于java的中国象棋.rar
    链接地址:http://www.gold-doc.com/p-116494.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
    copyright@ 2014-2018 金牌文库网站版权所有
    经营许可证编号:浙ICP备15046084号-3
    收起
    展开