中国象棋对弈软件的设计java版本.docx

资源描述

中国象棋对弈软件的设计java版本.docx

《中国象棋对弈软件的设计java版本.docx》由会员分享，可在线阅读，更多相关《中国象棋对弈软件的设计java版本.docx（102页珍藏版）》请在冰点文库上搜索。

中国象棋对弈软件的设计java版本.docx

中国象棋对弈软件的设计java版本

中国象棋对弈软件的设计

姓名

学科专业

指导老师

中国象棋对弈软件的设计

摘要：

随着人工智能及计算机硬件的发展，计算机象棋程序的下棋水平也不断地得到提高。

20世纪60年代初，麦卡锡提出了alpha-beta修剪算法，把为决定下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根，大大地提高了机器下棋的水平。

IBM的超级计算机“DeepBlue”更是一个神话，让棋迷们神往。

本文根据国际象棋程序设计的一些成功经验，提出中国象棋程序设计的一些思路和方法。

关键词：

中国象棋，位棋盘，Zobrist键值，alpha-beta搜索，置换表，局面评价

Abstract：

AlongwiththedevelopmentoftheArtificialIntelligenceandcomputerhardware,thecapabilityofcomputerchessprogramhaveadvancedcontinually.Atthebeginningof60s,20thcentury,McCaxibroughtforwordalpha-betapruningalgorismwhichmadethechessprogramadvancedmorebyreducingtheorderofmagnitudeofthenumberofsearchingnodesdecidingnextstep,named“StateSpace”fromO（Xn）toO（Xn/2）.IBM’ssuper-computer“DeepBlue”ismorelikeamythforallcomputerchessfans.Inmyarticle,IwilldescribesomeideasandmethodsofdesigningChineseChessprogramalongwithsomesuccessfulexperiencesandcasesoftheChess.

Keywords:

ChineseChess,bitboard,zobristkeys,alpha-betasearch,transpositiontable,

Evaluation

附件1：

搜索算法主程序SearchMove.java55

引言

象棋水平的发展是需要靠信息技术来推动的，国际象棋有两个很好的范例，一个是象棋棋谱编辑和对弈程序的公共平台——WinBoard平台，另一个是商业的国际象棋数据库和对弈软件——ChessBase，他们为国际象棋爱好者和研究者提供了极大的便利。

国际象棋软件有着成功的商业运作，已发展成一种产业。

然而，电脑在中国象棋上的运用还刚刚起步，尽管国内涌现出一大批中国象棋的专业网站和专业软件，但是由于缺乏必要的基础工作，电脑技术在中国象棋上的应用优势还无法体现出来。

在设计中国象棋软件过程中，国际象棋软件有很多值得借鉴的成功经验和优秀的思想。

例如B.Moreland，微软（Microsoft）的程序设计师，业余从事国际象棋引擎Ferret的开发，他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。

然而，中国象棋与国际象棋存在着很大的差异，因此国际象棋的某些成熟技术，无法直接应用于中国象棋，需要对其加以改进和创新。

本文针对中国象棋程序设计的一系列问题，总结出一些搜索引擎的设计方法，并给出java语言的实现。

第一章概述

中国象棋是由两人下的。

一方称为红方（或白方），一方称为黑方。

对局时由红方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止。

棋子的走法及详细规则见《中国象棋竞赛规则》，本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。

1.1棋盘的标记

象棋的着法表示，简而言之就是某个棋子从什么位置走到什么位置。

通常，表示方法可以分为“纵线方式”和“坐标方式”两种，现在作简要说明：

1.1.1纵线方式

这是中国象棋常用的表示方法，即棋子从棋盘的哪条线走到哪条线。

中国象棋规定，对于红方来说的纵线从右到左依次用“一”到“九”表示，黑方则是“1”到“9”（如图1所示），这种表示方式体现了古代中国象棋研究者的智慧。

1.1.2坐标方式

这是套用国际象棋中的表示方法，即把每个格子按坐标编号（如图二所示），只要知道起始格子和到达格子，就确定了着法，这种表示方式更方便也更合理，而且还可以移植到其他棋类游戏中。

采用这种方法来表示，棋盘的纵线从左到右（红方）依次为abcdefghi，横线从下到上（红方）依次为0123456789（如图2所示）。

１

２

３

４

５

６

７

８

９

九

八

七

六

五

四

三

二

一

（图1）

（图2）

1.2棋子的名称

为方便表示，中国象棋的棋子名称除了用汉字以外，还可以用字母，字母可从国际象棋中稍加改动得到，而数字是为了方便着法的输入（以便用在数字小键盘上）（见表1）：

红方

黑方

字母

英文单词

数字

帅

将

King

仕

士

Advisor

相

象

Bishop

马

Knight

车

Rook

炮

Cannon

兵

卒

Pawn

（表1）

1.3棋谱的记录方法

现以如下局面为例说明各种记谱方法

对于右图的局面，记法如下：

1.炮二平五炮８平５

2.炮五进四士４进５

3.马二进三马８进７

4.炮八平五马２进３

5.前炮退二车９平８

1.3.1坐标记法

坐标格式包括：

棋子的名称、起点和终点的位置（起点和终点用‘-’连接），对上面的走法，记录如下（省略了吃子、将军等信息）：

1、Ch2-e2（炮二平五）

Ch7-e7（炮８平５）

2、Ce2-e6（炮五进四）

Ad9-e8（士４进５）

3、Nh0-g2（马二进三）

Nh9-g7（马８进７）

4、Cb2-e2（炮八平五）

Nb9-c7（马２进３）

5、Ce6-e4（前炮退二）

Ri9-h9（车９平８）

1.3.2中文纵线记法

这种格式是中国象棋棋谱的常规记法，在各类出版物中最为普遍。

但是这里还是要说明两个重要的细节。

1、仕（士）和相（象）如果在同一纵线上，不用“前”和“后”区别，因为能退的一定在前，能进的一定在后。

2、兵要按情况讨论：

（1）三个兵在一条纵线上：

用“前”、“中”和“后”来区别；

（2）三个以上兵在一条纵线上：

最前面的兵用“一”代替“前”，以后依次是“二”、“三”、“四”和“五”；

（3）在有两条纵线，每条纵线上都有一个以上的兵：

按照“先从右到左，再从前到后”（即先看最左边一列，从前到后依次标记为“一”和“二”，可能还有“三”，再看右边一列）的顺序，把这些兵的位置标依次标记为“一”、“二”、“三”、“四”和“五”，不在这两条纵线上的兵不参与标记。

如右图局面，四个兵分别位于四线和六线，下表列举了几种走法的坐标格式和纵线格式。

中文纵线格式

符号纵线格式

坐标格式

一兵平五

Pa.5

Pf8-e8

二兵平五

Pb.5

Pf6-e6

兵五进一

P5+1

Pe7-e8

三兵平五

Pc.5

Pd8-e8

四兵平五

Pd.5

Pd6-e6

另外需要注意的是：

（1）如果黑方出现数字，不管数字代表纵线标号还是前进或后退的格数，都用阿拉伯数字表示，在计算机中显示全角的数字。

但是代表同一纵线上不同兵的“一二三四五”（它们类似于“前中后”的作用）例外，例如例局面红黑互换，那么某步着法就应该写成“一卒平５”。

（2）在传统的象棋记谱中，如果发生以上这种情况，通常用五个字来表示，例如“前兵四平五”等，在计算机处理过程中就比较麻烦，因为4个汉字（一个汉字占16位）的着法可以储存在一个64位的字当中（在C语言中数据类型为__int64或longlong），而增加到5个汉字就比较麻烦了。

黑方用全角的数字是同一个道理。

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/RNBAKABNRw01

Ø第一部分（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：

起始局面。

如果空缺，表示起始局面是最初局面。

1.5.2棋谱记录部分

棋谱记录部分必须在标签部分的后面，棋谱部分当中不能插入标签；每一回合都由“回合数”、“红方着法”和“黑方着法”三部分组成，回合数后面要跟“.”（句点），三者之间用两个分隔符隔开（回合数后面的句点也不例外），回合之间也用分隔符隔开。

现举一个例子如下：

例1：

[Event"第19届五羊杯全国象棋冠军邀请赛"]

[Date"1998.12.?

[Site"广州"]

[Red"徐天红"]

[Black"许银川"]

[Result"1/2-1/2"]

1.炮二平五马８进７2.马二进三车９平８

3.车一平二马２进３4.兵七进一卒７进１

5.车二进六炮８平９6.车二平三炮９退１

7.马八进九车８进５8.兵五进一马３退５

9.炮八进四炮２平５10.马九进七炮９平７

例2：

[Event"全国象棋冠军邀请赛"]

[Date"1999.12.15"]

[Site"广州"]

[Red"吕钦"]

[Black"许银川"]

[FEN"3k1ab2/4a4/8b/6NPP/9/4n1P2/6p2/4B4/4A4/2BAK4w--046"]

[Result"1-0"]

46.兵一进一卒７进１

47.兵一平二卒７进１

48.前兵平三卒７平６

49.马三退五马５退３

50.兵二平三马３进２

51.马五退六

1.5.3XML格式

全国象棋冠军邀请赛

广州

1999.12.09

许银川

聂卫平

rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/9/1C5C1/9/RN2K2NRr--01

1-0

炮八平五

炮８平５

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

2.1什么是位棋盘

在中国象棋中，棋盘有90个交叉点。

位棋盘其实就是一个长度为90位的变量，每个位对应一个交叉点，用来记录棋盘上的某些布尔值。

在Java中，用3个int类型数据（每个32位，共96位多余的6位不用）表示一个位棋盘。

2.2位棋盘的作用

位棋盘的作用，可从回答下面的问题开始：

“哪些格子上面有棋子？

”

“哪些格子上面有白棋（黑棋）棋子？

”

“哪些格子上面有车（马，炮等）？

”

“哪些格子受到a7格上的棋子的攻击？

”（不用管格子上是否有棋子或是什么颜色的棋子。

）

“如果有马在a3格上，哪些格子会受到它的攻击？

”

　……

通过回答上面的问题，可设置如下一些位棋盘

1、记录所有棋子位置的位棋盘AllPieces。

AllPieces告诉我们棋盘上哪些格子有棋子，哪些没有。

当棋子处于最初位置的时候，“AllPieces”看上去是这个样子的（以下描述中，格子的下标从0开始，坐标的图示见第一章“棋盘的标记”）:

（Hi,89,a9）111111111000000000101010101000000000000000000101010101000000000010000010000000000111111111（Low,0,i0）

其最高位对应第89格（a9格,左上角），最低位对应第0格（a8格，右下角）。

这样显示位棋盘可能更形象一点：

黑棋

111111111

000000000

010000010

101010101

000000000

101010101

000000000

010000010

000000000

111111111

红棋

2、记录所有黑棋棋子初始位置的位棋盘BlackPieces如下（记录红棋棋子初始位置的位棋盘RedPieces与此类似，在此不再列出）

111111111

000000000

010000010

101010101

000000000

3、记录各兵种如红棋车的初始位置的位棋盘“redRooks”如下：

000000000

100000001

4、假如我们创建了一个位棋盘数组knight[90]，用“knight[0]”位棋盘记录当马在0格（即i0格）时，棋盘上所有受到它攻击的格子，knight[89]记录当马在第89格（a9格）时，棋盘上所有受到它攻击的格子，那么，“knight[20]”就是这个样子的（为了直观，用“x”标记出马的位置，实际上该位置是“0”）：

000000000

000001010

000010001

000000x00

000010001

000001010

5、用另外一个位棋盘数组HorseLeg[90]记录蹩马腿位置的位棋盘。

与Knight[20]对应的HorseLeg[20]如下（在实际系统中，根据马的行走方向单独设置只有一个蹩腿位的位棋盘，knight数组更改为knight[90][8]）：

000000000

000000100

000001x10

000000100

000000000

6、建立全局数组“BitBoardbitMask[90]”，用来屏蔽或设置位棋盘中的某位。

bitMask[0]是这样的：

000000000

000000001

mask[89]是这样的：

100000000

000000000

2.3位棋盘的基本运算

1、与（&）

0101

1001

————

0001

2、或（|）

0101

1001

————

1101

3、异或（^）

0101

1001

————

1100

4、取补（~）a=0001，~a=1110。

2.4Java中位棋盘的实现

2.4.1位棋盘类的实现

Java中，位棋盘用3个int型的数据表示，最高六位不用。

Java中“与、或、非、异或、左位移，右位移（注意，位棋盘的右位移是无符号位移）”分别是“&、|、^、<<、>>>”。

代码摘要（详细代码见附件）及相关说明如下：

publicclassBitBoard{

privateintLow,Mid,Hi//用3个int字段表示位棋盘，最高位Hi的高//6位不用

publicBitBoard（intArg1,intArg2,intArg3）{//构造函数

Low=Arg1;

Mid=Arg2;

Hi=Arg3;

}

publicstaticBitBoardopAnd（BitBoardarg1,BitBoardarg2）{

//位棋盘的“与”操作，保存结果。

intlow=arg1.Low&arg2.Low;

intmid=arg1.Mid&arg2.Mid;

inthi=arg1.Hi&arg2.Hi;

returnnewBitBoard（low,mid,hi）;

}

publicstaticBitBoardopOr（BitBoardarg1,BitBoardarg2）

//位棋盘的“或”操作，保存结果。

publicstaticBitBoardopXor（BitBoardarg1,BitBoardarg2）

//位棋盘的“异或”操作，保存结果。

publicstaticintcount（BitBoardarg）//计算位棋盘中非零位的个数

publicstaticBitBoardduplicate（intarg）//复制位棋盘

publicstaticbooleanequals（BitBoardarg1,BitBoardarg2）

//位棋盘是否相等（所有90位对应的位相同即//为相等）

publicstaticBitBoardleftShift（BitBoardarg,intnum）

//位棋盘arg左位移num位

publicstaticrightShift（BitBoard,intnum）//位棋盘右位移num位

publicstaticintLSB（BitBoardArg）//位棋盘最低非0位的位置（从0开始计数）

publicstaticintMSB（BitBoardArg）//位棋盘最高非0位的位置（从0开始计数）

publicstaticbooleannotZero（BitBoardArg）//是否非“0”。

当90位中有非0位时返回true。

}

2.4.2位棋盘的初始化

某些位棋盘从程序开始运行到结束都不会改变。

例如上面所述的那个位棋盘数组“knight[90]”。

（他实际上记录了当马在任意格子上时，它下一步可以走的格子。

）这个数组将在程序开始执行的时候被初始化并且不再改变。

其余的位棋盘将不断变化。

例如“AllPieces”位棋盘。

当中国象棋棋盘变化时，它也跟着变化。

然而，他们的初始化方式相同。

对于诸如knight[90]这样不变化的位棋盘的初始化，将在“伪着法生成”章节详述。

此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。

首先，初始化“BitBoardbitMask[90]”数组：

BitBoardb=newBitBoard（0,0,1）;

for（intc=0;c<90;c++）{

mask[c]=BitBoard.leftShift（b,c）;

}

其次，用一个叫ChessPosition类记录棋盘上某一状态的所有有用信息。

它包含了一个整型数组intpiece_in_square[90]，还包含了一些位棋盘。

publicclassChessPosition{

intpiece_in_square[90];

intplayer;//轮到哪方走棋，0：

红方走，1：

黑方走

BitBoardallPieces;

BitBoardredKing;//红帅

BitBoardblackKing;//黑将

BitBoardredRooks;//红车

BitBoardblackRooks;//黑车

BitBoardredKnights;//红马

BitBoardblackKnights;//黑马

BitBoardredCannon;//红炮

BitBoardredCannon;//黑炮

BitBoardredBishops;//红相

BitBoardblackBishops;//黑象

BitBoardredAdvisor;//红仕

BitBoardblackAdvisor;//黑士

BitBoardredPawns;//红兵

BitBoardb

展开阅读全文