【毕业学位论文】（Word原稿）JSP,JAVA手机中国象棋设计论文范文

中国象棋 对弈软件的设计 中国象棋对弈软件的设计 摘 要 ： 随着人工智能及计算机硬件的发展，计算机象棋 程序 的下棋水平也不断地得到提高。 20 世纪 60 年代初，麦卡锡提出了 剪算法，把为决定 下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根，大大地提高了机器下棋的水平。 超级计算机“ 是一个神话，让棋迷们神往。本文根据国际象棋程序设计的一些成功经验，提出中国象棋程序设计的一些思路和方法。 关 键 词 ：中国象棋， 位 棋盘， 值， 索 ， 置换表，局面评价 of of 0s,20th by of of of (). s is a In my I of of 录 引 言 . 3 第一章 概述 . 4 盘的标记 . 4 子的名称 . 5 谱的记录方法 . 5 史局面的表示及存储 . 7 谱记录文件的格式 . 7 第二章 基本数据结构 位棋盘 . 10 么是位棋盘 . 10 棋盘的作用 . 10 棋盘的基本运算 . 12 位棋盘的实现 . 13 第三章 基本数据结构 值 . 16 较局面的方法 . 16 值的实现方法 . 16 值的工作原理及用途 . 16 实现 值 . 17 第四章 着法生成 . 19 合法着法的生成 . 19 法着法的生成 . 24 第五章 搜索算法 . 28 小 . 28 索 . 31 代加深 . 35 换表 . 35 他策略 . 39 第六章 局面评价函数 . 45 价函数的实现 方法 . 46 价函数所 需的信息 . 46 第七章 程 序的设计及实现 . 49 索引擎的实现（ ） . 49 息传输机制（ ） . 50 子 生成 （ ） . 50 控模块（ ） . 50 附件 1：搜索算法主程序 . 55 附件 2：程序运行界面及功能说明 . 74 引 言 象棋水平的发展是需要靠信息技术来推动的，国际象棋有两个很好的范例，一个是象棋棋谱编辑和对弈程序的公共平台 台，另一个是商业的国际象棋数据库和对弈软件 们为国际象棋爱好者和研究者提供了极大的便利。 国际象棋软件 有着成功的商业运作，已发展成一种产业。 然而，电脑在中国象棋上的运用还刚刚起步，尽管国内涌现出一大批中国象棋的专业网站和专 业软件，但是由于缺乏必要的基础工作，电脑技术在中国象棋上的应 用优势还无法体现出来 。 在设计中国象棋软件过程中，国际象棋软件有很多值得借鉴的成功经验和优秀的思想。 例如 B. 软 (程序设计师，业余从事国际象棋引擎 开发 ， 他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计 人员 借鉴。然而， 中国象棋 与国际象棋存在着 很 大的差异，因此国际象棋的某些成熟技术，无法直接应用于中国象棋 ，需要对其加以改进和创新 。 本文 针对 中国象棋 程序设计 的 一系列问题 ，总结 出 一些 搜索引 擎 的设计方法 ， 并给出 言 的 实现 。 第一章 概述 中国象棋是由两人下的。 一方称为红方（或白方），一方称为黑方。对局时由红方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止。棋子的走法 及详细规则 见 中国象棋竞赛规则 ，本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。 盘的标记 象棋的着法表示，简而言之就是某个棋子从什么位置走到什么位置。通常，表示方法可以分为“纵线方式”和“坐标方式”两种，现在作简要说明： 线方式 这 是中国象棋常用的表示方法，即棋 子从棋盘的哪条线走到哪条线。中国象棋规定，对于红方来说的纵线从右到左依次用“一”到“九”表示，黑方则是“ 1”到“ 9” (如图 1所示 )，这种表示方式体现了古代中国象棋研究者的智慧。 标方式 这 是 套用 国际象棋 中 的表示方法， 即 把每个格子按坐标编号 (如图二所示 )，只要知道起始格子和到达格子，就确定了着法，这种表示方式更方便也更合理，而且还可以移植到其他棋类游戏中。 采用 这种方法来表示， 棋盘的 纵线从左到右 (红方 )依次为 a b c d e f g h i，横线从下到上 (红方 )依次为 0 1 2 3 4 5 6 7 8 9(如图 2所示 )。 九 八 七 六 五 四 三 二 一 a B c d e f g h i 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 a B c d e f g h i （图 1） （图 2） 子的名称 为方便表示，中国象棋的棋子名称除了用汉字以外，还可以用字母，字母可从国际象棋中稍加改动得到，而数字是为了方便着法的输入 (以便用在数字小键盘上 )(见表 1)： 红方 黑方 字母 英文单词 数字 帅 将 K 仕 士 A 相 象 B 马 马 N 车 车 R 炮 炮 C 兵 卒 P （表 1） 谱 的 记录 方法 现以如下局面为例说明各种记谱方法 对于右图的局面，记法如下： 炮平 士进 马进 马进 车平 标记法 坐标格式包括：棋子的名称、起点和终点的位置（起点和终点用 -连接），对上面的走法，记录如下（省略了吃子、将军等信息）： 1、 二平五 ) 平 ) 2、 五进四 ) 进 ) 3、 二进三 ) 进 ) 4、 八平五 ) 进 ) 5、 炮退二 ) 平 ) 文纵线记法 这种格式 是中国象棋棋谱的常规记法，在各类出版物中最为普遍。 但是这里还是要说明两个重要的细节。 1、 仕 (士 )和相 (象 )如果在同一纵线上，不用“前”和“后”区别，因为能退的一定在前，能进的一定在后。 2、 兵 要按情况讨论 ： (1) 三个兵在一条纵线上：用“前”、“中”和“后”来区别； (2) 三个以上兵在一条纵线上：最前面的兵用“一”代替“前”，以后依次是“二”、“三”、“四”和“五”； (3) 在有两条纵线，每条纵线上都有一个以上的兵：按照“先从右到左，再从前到后” (即先看最左边一列，从前到后依次标记为“一”和“二”，可能还有“三”，再看右边一列 )的顺序，把这些兵的位置标依次标记为“一”、“二”、“三”、“四”和“五”，不在这两条纵线上的兵不参与标记。 如右图局面，四个兵分别位于四线和六线，下表列举了几 种走法的坐标格式和纵线格式。 中文纵线格式 符号纵线格式 坐标格式 一兵平五 兵平五 五进一 兵平五 兵平五 外需要注意的是： (1) 如果黑方出现数字，不管数字代表纵线标号还是前进或后退的格数，都用阿拉伯数字表示，在计算机中显示全角的数字。但是代表同一纵线上不同兵的“一二三四五” (它们类似于“前中后”的作用 )例外，例如例局面红黑互换，那么某步着法就应该写成 “一卒平”。 (2) 在传统的象棋记谱中，如果发生以上这种情况，通常用五个字来表示，例如“前兵四平五”等，在计算机处理过程中就比较麻烦，因为 4 个汉字 (一个汉字占16 位 )的着法可以储存在一个 64 位的字当中 (在 C 语言中数据类型为 _ 而增加到 5 个汉字就比较麻烦了。黑方用全角的数字是同一个道理。 号 纵线记法 这种格式仅仅是用字母和数字代替汉字，其中“进”、“退”和“平”分别用符号“ +”、“ -”和“ .”表示，“前”、“中”和“后”也分别用符号“ +”、“ -”和“ .”表示，并且写在棋子的后面 (例如“前炮退二”写成“ C+不是“ +)，多个兵位于一条纵线时，代替“前中后”的“一二三四五”分别用“ 示 (这种情况极少发生 )。 另外，代表棋子名称的第一个字母，还可以用数字 1 到 7 表示，这是为了方便数字小键盘的输入，例如“炮二平五”可以记作“ (6 代表炮 )选用符号“ +”、“ -”和“ .”也是出于这个考虑。 史 局面 的表示及存储 中国 象棋 的一个 局面可以用一个 “ 式串 ” 来表示。 式串是由 4段符串组成的代码 (彼此 3个空格隔开 )，这 4段代码的意义依次是： (1) 棋盘上的棋子，这是 式串的主要部分； (2) 当前局面轮到哪一方走子； (3) 最近一次吃子或者进兵后棋局进行的步数 (半回合数 )，用来判断 “ 50 回合自然限着 ” ； (4) 棋局的回合数。 现以最初局面为例详细说明如下： 第一部分 (w 前 面的字符 )： 表示棋盘布局，小写表示黑方 棋子 ，大写表示红方 棋子 。例如前九个字母 示棋盘第一行的棋子分别为黑方的“车马象士将士象马车”，“ /”为棋盘行与行之间的分割；数字“ 9(5,1)”表示该行从该位置起连续 9(5，1)个位置无棋子 。 第二部分 (w)：表示轮到哪一方走棋，如果是 w 表示轮到红方 (白方 )走，是 b 表示轮到黑方走。 第三部分 (w 后 的数字 0)：表示自然限着。 第四部分 (w 后的数字 1)：表示当前局面的回合数。 谱记录文件的格式 存放棋谱的 文件分为两个部分：标签部分和棋谱部分，现分述如下： 签部分 有如下标签 1、 赛名； 2、 比赛地点； 3、 赛日期，格式统一为 4、 方棋手； 5、 方棋手； 6、 赛结果， “ 红先胜 ” 用 “ 1表示， “ 黑先胜 ” 用 “ 0表示，和棋用 “ 1/2” 7、 起始局面。如果空缺，表示起始局面是最初局面。 谱记录部分 棋谱 记录 部分必须在标签部分的后面，棋谱部分当中不能插入标签 ； 每一回合都由 “ 回合数 ” 、 “ 红方着法 ” 和 “ 黑方着法 ” 三部分组成，回合数后面要跟 “ .” (句点 )，三者 之间用两个分隔符隔开 (回合数后面的句点也不例外 )，回合之间也用分隔符隔开 。 现举一个例子如下： 例 1： 第 19 届五羊杯全国象棋冠军邀请赛 ? 广州 徐天红 许银川 1/2 1. 炮二平五 马 进 2. 马二进三 车 平 3. 车一平二 马进 4. 兵七进一 卒进 5. 车二进六 炮平 6. 车二平三 炮退 7. 马八进九 车进 8. 兵五进一 马退 9. 炮八进四 炮平 10. 马九进七 炮平 例 2： 全国象棋冠军邀请赛 广州 吕钦 许银川 3b/6 1 46. 兵一进一 卒 进 47. 兵一平二 卒 进 48. 前兵平三 卒 平 49. 马三退五 马 退 50. 兵二平三 马进 51. 马五退六 全国象棋冠军邀请赛 广州 许银川 聂卫平 位棋盘 么是位棋盘 在中国象棋中，棋盘有 90 个交叉点。 位棋盘其实就是一个 长度为 90 位的变量， 每个位对应一个交叉点， 用来记录棋盘上的某些布尔值。 在 ，用 3 个 型数据（每个 32位，共 96位多余的 6位不用）表示一个位棋盘。 棋盘 的作用 位棋盘的作用，可从回答下面的问题开始： “ 哪些格子上面有棋子？ ” “ 哪些格子上面有白棋 （ 黑棋） 棋子？ ” “ 哪些格子上面有车 （马，炮等） ？ ” “ 哪些格子受到 上的棋子的攻击？ ” (不用管格子上是否有棋子或是什么颜色的棋子 。 ) “ 如果有马在 上，哪些格子会受到它的攻击？ ” 通过回答上面的问题，可设置如下一些位棋盘 1、 记录所有棋子位置的位棋盘 诉我们棋盘上哪些格子有棋子，哪些没有。当棋子处于最初位置的时候， “ 看上去是这个样子的 (以下描述中，格子的下标从 0 开始，坐标的图示见第一章“棋盘的标记” ): (9,11111111 000000000 101010101 000000000 000000000 101010101 000000000 010000010 000000000 111111111(, 其最高位对应第 89格 ( ,左上角 )，最低位对应第 0 格 ( ，右下角 )。 这样显示位棋盘可能更形象一点： 黑棋 111111111 000000000 010000010 101010101 000000000 000000000 101010101 000000000 010000010 000000000 111111111 红 棋 2、 记录 所有黑 棋棋子初始位置的位棋盘 下 (记录 红 棋棋子初始位置的位棋盘 此类似，在此不再列出 ) 111111111 000000000 010000010 101010101 000000000 000000000 000000000 000000000 000000000 000000000 3、 记录 各兵种如红 棋车的初始位置的位棋盘 “ 如下： 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 100000001 4、 假如我们创建了一个位棋盘数组 0， 用 “ ” 位棋盘记录当马在 0格 (即 时，棋盘上所有受到它攻击的格子 ， 9记录当马在 第 89 格 ( )时，棋盘上所有受到它攻击的格子 ，那么，“ 0” 就 是这个样子的 （为了直观，用“ x”标记出马的位置，实际上该位置是“ 0”） ： 000000000 000000000 000000000 000000000 000000000 000001010 000010001 00000000010001 000001010 5、用另外一个位棋盘数组 0记录蹩马腿位置的位棋盘 。与 0对应的 0如下 (在实际系统中，根据马的行走方向单独设置只有一个蹩腿位的位棋盘， 08)： 000000000 000000000 000000000 000000000 000000000 000000000 000000100 00000100000100 000000000 6、 建立全局数组 “ 0” ， 用来屏蔽或设置位棋盘中的某位。是这样的： 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000001 9 是这样的： 100000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 棋盘的基本 运算 1、 与 (&) 0 1 0 1 1 0 0 1 0 0 0 1 2、 或 (|) 0 1 0 1 1 0 0 1 1 1 0 1 3、 异或 () 0 1 0 1 1 0 0 1 1 1 0 0 4、 取补 () a = 0001， a = 1110。 位棋盘的实现 棋盘类 的实现 棋盘用 3 个 高六位不用。 、或、非、异或、左位移，右位移（注意，位棋盘的右位移是无符号位移）”分别是“ &、 |、 、”。代码摘要（详细代码见附件）及相关说明如下： i/用 3 个 段表示位棋盘，最高位 高 /6 位不用 /构造函数 /位棋盘的“与”操作，保存结果。 hi= /位棋盘的“或”操作，保存结果。 /位棋盘的“异或”操作，保存结果。 ( /位棋盘是否相等（所有 90位对应的位相同即 /为相等） /位棋盘 (（从 0开始计数） （从 0开始计数） “ 0”。当 90位中有非 0位时返回 棋盘的初始化 某些位棋盘从程序开始运行到结束都不会改变。 例如上面所述的 那个位棋盘数组“ 0” 。 (他实际上记录了当马在任意格子上时，它下一步可以走的格 子。 )这个数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例如“ 位棋盘。当 中国 象棋棋盘变化时，它也跟着变化。然而，他们的初始化方式相同。 对于诸如 0这样不变化的位棋盘的初始化，将在“伪着法生成”章节详述。此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。 首先，初始化 “ 0” 数组 ： b = ,0,1); c = 0; c = 0; k (j & (1 = 0; k (j & (1 = 0; k (j & (1 = 0; k (j & (1 ( (0 ? 16 : 32)!=0) = y+ x; = y+ x; ，也就是“ 平 ” y;/行位棋盘数值， 9 位二进制数 x+ y; 以上对炮伪合法着法的合法性判断。 0和 0保存的是格子对应的列和行，这比“ %、 /”（取余和除法）的运算速度快。 和 0分别保存的是位棋盘中 9 列（每列共 10 位）和 10 行（每行共 9 位）的二进制值。 生成伪合法的类，保存有所有伪合法着法的静态数组。 2、合法着法的生成 代码如下： ,0 s,d) s; d; () - a + ) - 0); () - a + ) - 0); 90 | 90) / 着法的数据结构， 别是移动前后的位置（格子） ) ( 据当前局面（作为参数的 成合法着法，并保存在一个数组 ，同时也将每个着法的局面评价值存入数组 ，这样以便对着法进行排序，在搜索算法中提高算法的效率。以上算法调用的子函数再此给出为代码，详细代码见附件。 根据 出当前局面 的伪合法着法； 的伪合法着法 ) 中一个着法 ) ; 子方不是处于被“将”状态 ) ; 第五章 搜索算法 小 在 中国 象棋里，双方棋手都知道每个棋子在哪里，他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方，或者避免被将死，或者有时争取和棋是最好的选择。 中国 象棋程序通过使用 “ 搜索 ” 函数来寻找着法。搜索函数获得棋局信息，然后寻找对于程序一方来说最好的着法。 一个浅显的搜索 函数用 “ 树状搜索 ” (实现。一个 中国 象棋棋局通常可以看作一个很大的 “ 意思是树的每个结点有任意多个分枝通向其他结点 )，棋盘上目前的局面就是 “ 根局面 ” ( “ 根结点 ” (从根局面走一步棋，局面就到达根局面的 “ 分枝 ” (这些局面称为 “ 后续局面 ” ( “ 后续结点 ” (每个后续局面后面还有一系列分枝，每个分枝就是这个局面的一个合理的着法。 中国 象 棋的树非常庞大 (通常每个局面有 45 个分枝 )，又非常深。 每盘棋局都是一棵巨大的 n 叉树，如果能通过树状搜索找到棋局中对双方来说都最好的着法就好了。这个浅显的算法在这里称为 “ 最小 ( 用最小 即完全了解每一种变化 )。井字棋的博弈树既不烦琐也不深，所以整个树可以遍历，棋局的所有变化都可以知道，任何局面都可以保证找到一步最佳着法。 数学上用这种方法处理 中国 象棋也是可以的，但是目前和不久的将来用计算机去实现，却是不可行的。即便如 此，我们仍然可以用基于最小 棋。相比最小 一个给定的局面下搜索前几步则是可能的。由于叶子结点的局面没能搜索出杀棋或和棋，所以要用一个称为 “ 评价 ” (启发函数给这些局面赋值。 最大的评价函数 评价函数的细节 ，在后面再说 。这里我只说明它是怎样确定的，在以后的章节中会详细展开。评价函数首先应该返回局面的准确值，在没办法得到准确值的情况下，如果可能的话启发值也可以。它可以由两种方法来决定： 1、 如果黑方被将死了，那么评价函数返回一个充分大 的正数；如果 红方 被将死了，那么返回一个充分大的负数；如果棋局是和棋，那么返回一个常数，通常是零或接近零。如果不是棋局结束局面，那么它返回一个启发值。 确定启发值， 子力平衡是首先要考虑的 (如果 红方 盘面上多子的话，这个值就大 )，而其他位置上的考虑 (帅、将 的安全性 ， 重要的子力 的位置 等等 )也需要加上。如果 红方 是赢棋或者很有希望赢，那么启发函数通常会返回正数；如果黑方是赢棋或者很有希望赢，那么返回负数；如果棋局是均势或者是和棋，那么返回在零左右的数值。 2、 这个函数的工作原理跟第一个一样，只是如果当前局面要走子的一方 优势，那么它返回正数，反之是负数。 小 最小 者说两个逻辑上重复的函数。纯粹的 (不完美的 )最小 码如下： = / 红 方是 “ 最大 ” 者 ax( / 黑方是 “ 最小 ” 者 in( ax( in( “ 最大 ” 算法 在这个函数里，当走子一方改变时就要对返回值取负值，以反映当前局面评价的更改。就根结点是 红 先走的情况，如果没有剩下的层数，那么 “ 评价 ” 返回的值是就 红 方而言的，如果有剩下的层数，就产生后续局面，函数对这些局面逐一做递归，每个次递归都得到就黑方而言的评价，黑方走得越好值就越大 。当评价值返回时，它们被取负数，变成就白方而言的评价。 该函数在遍历时结点的顺序同 “ 最小 搜索的函数是一样的，产生的返回值也一样。它的代码更短，同时减少了移植代码时出错的可能，代码维护起来也比较方便。 索 小 法的问题 “最小 非常相似，事实上只多了一条额外的语句。 “ 最小 运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。 通常一个 中国 象棋局面 平均 都有 45 个左右的合理着法 （有效分支因子） ，所以用最小 有 45 个局面要检查，如果用这个函数来搜索两层，就有 452 个局面要搜索， 搜索局面的数量一指数级 增长 ， 非常迅速 。 要想通过检查搜索树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜索是很重要的。最小 为有效的分枝因子实在太大了。 是建立在这样一个思想之上： 如果你已经有一个不太坏的选择了 ，那么当你要作别的选择并知道它不会更好时，你没有必要确切地知道它有多坏。有了最好的选择，任何不比它更好的选择就是足够坏的，因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。 搜索树有两种修剪 1、 浅的 修 剪 假设用最小 前面讲到的 )来搜索下面的树 ： 当 搜索到 F，发现子结点的评价分别是 11、 12、 7 和 9，在这层是棋手甲走，我们希望他选择最好的值，即 12。所以， F 的最小 2。 现在开始搜索 G，并且第一个子结点就返回 15。一旦如此，就知道 G 的值至少是15，可能更高 (如果另一个子结点比 G 更好 )。这就意味着我们不指望棋手乙走 G 这步了，因为就棋手乙看来， F 的评价 12 要比 G 的 15(或更高 )好，因此我们知道 G 不在主要变例上。我