中国象棋对弈程序文档.doc

发布时间：2022-06-10 发布人：admin 分类：说明书资料大小：0.61M 资料格式：doc 举报版权申诉

greatcai8-2286026-16359647608945397011.doc.pdf-第1页.png

第1页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第2页.png

第2页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第3页.png

第3页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第4页.png

第4页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第5页.png

第5页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第6页.png

第6页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第7页.png

第7页 / 共75页

greatcai8-2286026-16359647608945397011.doc.pdf-第8页.png

第8页 / 共75页

中国象棋对弈软件的设计

Abstract：Along with the development of the Artific

引言

第一章概述

1.1 棋盘的标记

1.1.1 纵线方式

1.1.2 坐标方式

1.2棋子的名称

1.3棋谱的记录方法

1.3.1 坐标记法

1.3.2 中文纵线记法

1.3.3 符号纵线记法

1.4 历史局面的表示及存储

1.5 棋谱记录文件的格式

1.5.1 标签部分

1.5.2 棋谱记录部分

1.5.3 XML格式

第二章基本数据结构——位棋盘

2.1 什么是位棋盘

2.2 位棋盘的作用

2.3 位棋盘的基本运算

2.4 Java中位棋盘的实现

2.4.1 位棋盘类的实现

2.4.2 位棋盘的初始化

2.4.3 位棋盘的更新

第三章基本数据结构——Zobrist键值

3.1 比较局面的方法

3.2 Zobrist键值的实现方法

3.3 Zobrist键值的工作原理及用途

3.3.1 Zobrist键值的工作原理

3.3.2 Zobrist键值的用途

3.4 Java中实现Zobrist键值

第四章着法生成

4.1伪合法着法的生成

4.1.1 数组及其下标的含义

4.1.2 算法示例——车炮的伪合法着法生成

4.2 合法着法的生成

第五章搜索算法

5.1 最小-最大搜索

5.1.1基于最小-最大的评价函数

5.1.2 最小-最大搜索

5.1.3、负值最大函数

5.2 Alpha-Beta搜索

5.2.1 最小-最大搜索算法的问题

5.2.2 Alpha-Beta修剪

5.2.3 Alpha-Beta修剪算法的实现

5.2.4 可能的弱点

5.3迭代加深

5.4 置换表

5.4.1 置换表的实现

5.4.2 替换策略

5.5 其他策略

5.5.1 静态搜索

5.5.2 空着裁剪

5.5.3 主要变例搜索

第六章局面评价函数

6.1 评价函数的实现方法

6.1.1 算法设计思路

6.1.2评价要素的组合

6.2评价函数所需的信息

第七章程序的设计及实现

7.1 搜索引擎的实现（engine包）

7.2 信息传输机制（message包）

7.3 棋子（pieces包）

7.4 主控模块（main包）

致谢

附件1：搜索算法主程序SearchMove.java

附件2：程序运行界面及功能说明

合肥工业大学毕业论文（计算机及其应用专业）中国象棋对弈软件的设计姓名葛标学科专业计算机及其应用专业指导老师李琳二零零五年九月 - 1 -

中国象棋对弈软件的设计摘要：随着人工智能及计算机硬件的发展，计算机象棋程序的下棋水平也不断地得到提高。20 世纪 60 年代初，麦卡锡提出了 alpha-beta 修剪算法，把为决定下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根，大大地提高了机器下棋的水平。IBM 的超级计算机“Deep Blue”更是一个神话，让棋迷们神往。本文根据国际象棋程序设计的一些成功经验，提出中国象棋程序设计的一些思路和方法。关键词：中国象棋，位棋盘，Zobrist 键值，alpha-beta 搜索，置换表，局面评价 Abstract：Along with the development of the Artificial Intelligence and computer hardware, the capability of computer chess program have advanced continually.At the beginning of 60s,20th century, McCaxi brought forword alpha-beta pruning algorism which made the chess program advanced more by reducing the order of magnitude of the number of searching nodes deciding next step,named “State Space” from O(Xn) to O(Xn/2). IBM’s super-computer “Deep Blue” is more like a myth for all computer chess fans. In my article, I will describe some ideas and methods of designing Chinese Chess program along with some successful experiences and cases of the Chess. Keywords: Chinese Chess, bit board, zobrist keys, alpha-beta search, transposition table, Evaluation - 2 -

目录引言...................................................................................................... 4 第一章概述.......................................................................................................................5 1.1 棋盘的标记..............................................................................................................5 1.2 棋子的名称..............................................................................................................6 1.3 棋谱的记录方法......................................................................................................6 1.4 历史局面的表示及存储..........................................................................................8 1.5 棋谱记录文件的格式..............................................................................................8 第二章基本数据结构——位棋盘.................................................................................11 2.1 什么是位棋盘........................................................................................................ 11 2.2 位棋盘的作用........................................................................................................ 11 2.3 位棋盘的基本运算................................................................................................13 2.4 Java 中位棋盘的实现.............................................................................................14 第三章基本数据结构——Zobrist 键值....................................................................... 17 3.1 比较局面的方法....................................................................................................17 3.2 Zobrist 键值的实现方法........................................................................................ 17 3.3 Zobrist 键值的工作原理及用途............................................................................ 17 3.4 Java 中实现 Zobrist 键值....................................................................................... 18 第四章着法生成.............................................................................................................20 4.1 伪合法着法的生成.................................................................................................20 4.2 合法着法的生成....................................................................................................25 第五章搜索算法.............................................................................................................29 5.1 最小-最大搜索.......................................................................................................29 5.2 Alpha-Beta 搜索......................................................................................................32 5.3 迭代加深................................................................................................................36 5.4 置换表....................................................................................................................36 5.5 其他策略................................................................................................................40 第六章局面评价函数.....................................................................................................46 6.1 评价函数的实现方法............................................................................................47 6.2 评价函数所需的信息............................................................................................47 第七章程序的设计及实现.............................................................................................50 7.1 搜索引擎的实现（engine 包）............................................................................ 50 7.2 信息传输机制（message 包）............................................................................. 51 7.3 棋子生成（pieces 包）.........................................................................................51 7.4 主控模块（main 包）...........................................................................................51 附件 1：搜索算法主程序 SearchMove.java................................................................. 55 附件 2：程序运行界面及功能说明 ................................................................................74 - 3 -

引言象棋水平的发展是需要靠信息技术来推动的，国际象棋有两个很好的范例，一个是象棋棋谱编辑和对弈程序的公共平台——WinBoard 平台，另一个是商业的国际象棋数据库和对弈软件——ChessBase，他们为国际象棋爱好者和研究者提供了极大的便利。国际象棋软件有着成功的商业运作，已发展成一种产业。然而，电脑在中国象棋上的运用还刚刚起步，尽管国内涌现出一大批中国象棋的专业网站和专业软件，但是由于缺乏必要的基础工作，电脑技术在中国象棋上的应用优势还无法体现出来。在设计中国象棋软件过程中，国际象棋软件有很多值得借鉴的成功经验和优秀的思想。例如 B. Moreland，微软(Microsoft)的程序设计师，业余从事国际象棋引擎 Ferret 的开发，他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。然而，中国象棋与国际象棋存在着很大的差异，因此国际象棋的某些成熟技术，无法直接应用于中国象棋，需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题，总结出一些搜索引擎的设计方法，并给出 java 语言的实现。 - 4 -

第一章概述中国象棋是由两人下的。一方称为红方（或白方），一方称为黑方。对局时由红方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止。棋子的走法及详细规则见《中国象棋竞赛规则》，本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。 1.1 棋盘的标记象棋的着法表示，简而言之就是某个棋子从什么位置走到什么位置。通常，表示方法可以分为“纵线方式”和“坐标方式”两种，现在作简要说明： 1.1.1 纵线方式这是中国象棋常用的表示方法，即棋子从棋盘的哪条线走到哪条线。中国象棋规定，对于红方来说的纵线从右到左依次用“一”到“九”表示，黑方则是“1”到“9”(如图 1 所示)，这种表示方式体现了古代中国象棋研究者的智慧。 1.1.2 坐标方式这是套用国际象棋中的表示方法，即把每个格子按坐标编号(如图二所示)，只要知道起始格子和到达格子，就确定了着法，这种表示方式更方便也更合理，而且还可以移植到其他棋类游戏中。采用这种方法来表示，棋盘的纵线从左到右(红方)依次为 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 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 九八七六五四三二一 a B c d e f g h i （图 1）（图 2） - 5 -

1.2 棋子的名称为方便表示，中国象棋的棋子名称除了用汉字以外，还可以用字母，字母可从国际象棋中稍加改动得到，而数字是为了方便着法的输入(以便用在数字小键盘上)(见表 1)：红方黑方帅仕相马车炮兵（表 1）将士象马车炮卒字母 K A B N R C P 英文单词 King Advisor Bishop Knight Rook Cannon Pawn 数字 1 2 3 4 5 6 7 1.3 棋谱的记录方法现以如下局面为例说明各种记谱方法对于右图的局面，记法如下： 1.炮二平五炮８平５ 2.炮五进四士４进５ 3.马二进三马８进７ 4.炮八平五马２进３ 5.前炮退二车９平８ 1.3.1 坐标记法坐标格式包括：棋子的名称、起点和终点的位置（起点和终点用‘-’连接），对上面的走法，记录如下（省略了吃子、将军等信息）： 1、Ch2-e2(炮二平五) 2、Ce2-e6(炮五进四) 3、Nh0-g2(马二进三) Ch7-e7(炮８平５) Ad9-e8(士４进５) Nh9-g7(马８进７) - 6 -

4、Cb2-e2(炮八平五) 5、Ce6-e4(前炮退二) Nb9-c7(马２进３) Ri9-h9(车９平８) 1.3.2 中文纵线记法这种格式是中国象棋棋谱的常规记法，在各类出版物中最为普遍。但是这里还是要说明两个重要的细节。 1、仕(士)和相(象)如果在同一纵线上，不用“前”和“后”区别，因为能退的一定在前，能进的一定在后。 2、兵要按情况讨论： (1) 三个兵在一条纵线上：用“前”、“中”和“后”来区别； (2) 三个以上兵在一条纵线上：最前面的兵用“一”代替“前”，以后依次是“二”、 “三”、“四”和“五”； (3) 在有两条纵线，每条纵线上都有一个以上的兵：按照“先从右到左，再从前到后”(即先看最左边一列，从前到后依次标记为“一”和“二”，可能还有“三”，再看右边一列)的顺序，把这些兵的位置标依次标记为“一”、“二”、“三”、“四” 和“五”，不在这两条纵线上的兵不参与标记。如右图局面，四个兵分别位于四线和六线，下一兵平五二兵平五中文纵线格式符号纵线格式坐标格式 Pf8-e8 Pf6-e6 Pe7-e8 Pd8-e8 Pd6-e6 表列举了几种走法的坐标格式和纵线格式。 Pa.5 Pb.5 P5+1 Pc.5 Pd.5 兵五进一三兵平五四兵平五另外需要注意的是： (1) 如果黑方出现数字，不管数字代表纵线标号还是前进或后退的格数，都用阿拉伯数字表示，在计算机中显示全角的数字。但是代表同一纵线上不同兵的“一二三四五”(它们类似于“前中后”的作用)例外，例如例局面红黑互换，那么某步着法就应该写成“一卒平５”。 (2) 在传统的象棋记谱中，如果发生以上这种情况，通常用五个字来表示，例如 “前兵四平五”等，在计算机处理过程中就比较麻烦，因为 4 个汉字(一个汉字占 16 位)的着法可以储存在一个 64 位的字当中(在 C 语言中数据类型为__int64 或 long long)，而增加到 5 个汉字就比较麻烦了。黑方用全角的数字是同一个道理。 - 7 -

1.3.3 符号纵线记法这种格式仅仅是用字母和数字代替汉字，其中“进”、“退”和“平”分别用符号 “+”、“-”和“.”表示，“前”、“中”和“后”也分别用符号“+”、“-”和 “.”表示，并且写在棋子的后面(例如“前炮退二”写成“C+-2”而不是“+C-2”)，多个兵位于一条纵线时，代替“前中后”的“一二三四五”分别用“abcde”表示(这种情况极少发生)。另外，代表棋子名称的第一个字母，还可以用数字 1 到 7 表示，这是为了方便数字小键盘的输入，例如“炮二平五”可以记作“62.5“(6 代表炮)选用符号“+”、“-”和“.”也是出于这个考虑。 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：起始局面。如果空缺，表示起始局面是最初局面。 - 8 -

分享到：

赞收藏

资料库

中国象棋对弈程序文档.doc

相关推荐

课程资源

热门标签

最新资料