中国象棋算法.docx
- 文档编号:13036742
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:67
- 大小:103.47KB
中国象棋算法.docx
《中国象棋算法.docx》由会员分享,可在线阅读,更多相关《中国象棋算法.docx(67页珍藏版)》请在冰点文库上搜索。
中国象棋算法
中国象棋算法
解剖大象的眼睛——中国象棋程序设计探索
黄晨* 2005年6月
(*联系地址:
复旦大学化学系表面化学实验室,eMail:
morning_yellow@elephantbas
)
(一)引言
我在今年2月写出了象棋程序ElephantEye的第一个版本(0.90),本来它只是象棋界
面ElephantBoard的调试引擎。
在设计程序的过程中,我尝试性地加入了很多算法,发现
每次改进都能让程序的棋力有大幅度的提高,因此便对象棋程序的算法产生了浓厚的兴
趣。
到现在我已经陆续对ElephantEye作了几十次加工(目前版本为0.94),使得它的棋力
接近了中等商业软件的水平,在公开源代码的象棋程序中,ElephantEye是最强的一个。
《PC游戏编程——人机博弈》一书,也参考了一些国际象棋的源程序,并通过自己的探
索,在ElephantEye中加入了另外的非常重要的算法,尤其是启发算法,我认为它们在程
序中发挥了关键性的作用,而且很多细节在绝大多数文字资料中没有详细给出,我会在
我的连载中重点介绍。
我猜读者最感兴趣的内容是ElephantEye的着法生成器,这应该算是象棋程序的核心
部分,同时也是各个程序差异最大的部分。
在写ElephantEye以前,我在《象棋百科全书
》网站上刊登了大量介绍“位棋盘”的文章,这是个非常有吸引力的思想,但是我试验
下来觉得它的速度并不快,在ElephantEye的程序里我只把位棋盘运用在将军判断上。
尽
管如此,ElephantEye短短10行的将军判断也许是程序的一个亮点吧,那么这部分内容我
将尽量介绍得详细一点。
此外,一些看似和棋力关系不大的技术,诸如开局库、长将检测、后台思考、时间
策略、引擎协议等等,其实也直接影响着象棋程序的稳定性,因此也有必要逐一讲解。
总之,每个技术都很重要,我的连载虽然不能面面俱到,但我会尽我所能来作详细
阐述的。
1.2如何正确评价ElephantEye目前的棋力?
ElephantEye是“蛮力型”象棋程序,与大多数商业程序的不同之处在于,它没有审
局能力,那么它的棋力到底有多强?
网友对这个问题众说纷纭,有人认为它无法跟一流
的商业软件相比,毕竟ElephantEye是免费程序,其源代码又是公开的,为什么非要去和
顶尖程序去比呢?
也有人认为它能战胜中等商业软件,但电脑对电脑和电脑对人类根本
就不是一回事,这么一个不懂得防守空头炮的程序怎能说它厉害呢?
还有人喜欢在同一
搜索水平(比如6层、8层或10层)上比较两个不同的程序,这种标准去比较“蛮力型”程
序和“知识型”程序,这有意义吗?
要正确认识这个问题,我想说明几点:
(1)测试标准要合理,这个标准只能是“时限”,即给两个程序以同样多的时间,
可以对每步都限定时间,也可以是比赛所采用的时段制或加时制,而不能以同样的搜索
水平作标准。
另外,如果两个程序运行在同一台电脑上,那么不能启用后台思考功能。
(2)某几盘对局并不能说明问题,我以“浅红象棋”为平台用ElephantEye对阵“梦
入神蛋”,ElephantEye遗憾地以2:
3败北。
我有充分的信心表明ElephantEye的棋力比梦
入神蛋强得多,因为两者用了相同的评价函数,但同样时间ElephantEye通常要比梦入神
蛋多搜索一层以上,那么2:
3的比分又能说明什么问题呢?
(3)跟人类比和跟电脑比是两回事,每个电脑程序都有弱点,这些弱点很容易被人
类棋手抓住,但其他电脑程序则不会抓住你的弱点。
一般认为,知识缺乏的程序弱点也
多(例如ElephantEye不懂得防守空头炮),因此对阵人类棋手失败的几率要比对阵其他程
序高得多。
1.3ElephantEye对象棋有哪些认识?
要说ElephantEye一点象棋知识都不具备,这种观点我是无法接受的。
很多搜索算法
确实只能用在象棋上,这一点ElephantEye做得比很多商业程序都好,这些算法体现在以
下几个方面:
(1)杀棋局面在置换表中的特殊处理,这使得ElephantEye识别杀棋的速度快了很多
;
(2)将军扩展,这使得ElephantEye对可能有杀棋的线路特别感兴趣,它会在搜索上
增加对这些路线的投入;
(3)带检验的适应性空着裁剪,这个算法首先由一个以色列学者发表于2002年(不是
“适应性”的),最近我对该算法作了改进,使得它能正确处理残局中的等着杀和连等着
杀,速度也快了很多。
这些算法使得ElephantEye有很强的处理杀局和残局的能力,我相信绝大多数商业软
件都没它做得好。
如果一个程序能在很短的时间内告诉你,几步之后必定有一方会被将
死,或者几步之后优势一方就可以破士或破象,那么这个程序的实用价值还算小吗?
(二)棋盘结构和着法生成器
在阅读本章前,建议读者先阅读《象棋百科全书》网站中《对弈程序基本技术》专题的以下几篇译文:
(1)数据结构——简介(DavidEppstein);
(2)数据结构——位棋盘(JamesSwafford);
(3)数据结构——旋转的位棋盘(JamesSwafford);
(4)数据结构——着法生成器(JamesSwafford);
(5)数据结构——0x88着法产生方法(BruceMoreland);
(6)数据结构——Zobrist键值(BruceMoreland);
(7)其他策略——重复检测(BruceMoreland)。
2.1局面和着法的表示
局面是象棋程序的核心数据结构,除了要包括棋盘、棋子、哪方要走、着法生成的辅助结构、Zobrist键值等,还要包含一些历史着法,来判断重复局面。
ElephantEye的局面结构很庞大(见
structCchessPosition{
……
intMoveNum;
MoveStructMoveList[MaxMoveNum];//MaxMoveNum=256
charLoopHash[LoopHashMask+1];//LoopHashMask+1=1024
……
}
其中MoveStruct这个结构记录了四个信息:
(1)着法的起始格(Src),
(2)着法的目标格(Dst),(3)着法吃掉的棋子(Cpt),(4)着法是否将军(Chk)。
有意思的是,每个部分都只占一个字节,后两个部分(Cpt和Chk)与其说有特殊作用,不如说是为了凑一个32位整数。
在MoveStruct出现的很多地方(置换表、杀手着法表、着法生成表)里,这两项都是没作用的,而只有在CchessPosition结构的记录历史着法的堆栈中才有意义。
Cpt一项主要用在撤消着法上,它可以用来还原被吃的棋子,而Chk一项则可以记录当前局面是否处于将军状态。
ElephantEye是用MovePiece()函数来走棋的,每走完一步棋就做两次将军判断:
第一次判断走完子的一方是否被将军,即Checked(Player),如果被将则立即撤消着法,并返回走子失败的信息;第二次判断要走的一方是否被将军,由于交换了走子方(即执行了Player=1-Player),所以仍旧是Checked(Player),如果被将则Chk置为1,这个着法被压入历史着法堆栈。
因此LastMove().Chk就表示当前局面是否被将军。
2.2循环着法的检测
Cpt和Chk的另一个作用就是判断循环着法:
ElephantEye判断循环着法时,依次从堆栈顶往前读,读到吃过子的着法(Cpt不为零)就结束;而是否有单方面长将的情况,则是通过每个着法的Chk一项来判断的。
在循环着法的检测中,我们感兴趣的不是Cpt和Chk,而是LoopHash结构,这是一个微型的置换表,用来记录历史局面。
ElephantEye在做循环着法的判断这之前,先去探测这个置换表,如果命中置换表,则说明可能存在重复局面(由于置换表可能有冲突,所以只是有这个可能),因而做循环检测;如果没有命中则肯定没有重复局面。
ElephantEye使用“归位检测法”来判断循环着法,即从最后一个着法开始,依次向前撤消着法,并记录每个移动过的棋子所在的格子。
如果所有移动过的棋子同时归位,那么循环着法就出现了。
因此
2.3棋盘-棋子联系数组
众所周知,棋盘的表示有两种方法。
一是做一个棋盘数组(例如Squares[10][9]),每个元素记录棋子的类型(包括空格);二是做一个棋子数组(例如Pieces[32]),每个元素记录棋子的位置(包括被吃的状态)。
如果一个程序同时使用这两个数组,那么着法生成的速度就可以快很多。
这就是“棋盘-棋子联系数组”,它的技术要点是:
(1)同时用棋盘数组和棋子数组表示一个局面,棋盘数组和棋子数组之间可以互相转换。
(2)随时保持这两个数组之间的联系,棋子移动时必须同时更新这两个数组。
根据这两个原则,棋盘-棋子联系数组可以定义为:
structCchessPosition{
intSquares[90];
intPieces[32];
};
棋子数组Pieces[48]是ElephantEye的一个特点,0到16没有作用,16到31代表红方棋子(16代表帅,17和18代表仕,依此类推,直到27到31代表兵),32到47代表黑方棋子(在红方基础上加16)。
这样,棋盘数组Squares[90]中的每个元素的意义就明确了,0代表没有棋子,16到31代表红方棋子,32到47代表黑方棋子。
这样表示的好处就是:
它可以快速判断棋子的颜色,(Piece&16)可以判断是否为红方棋子,(Piece&32)可以判断是否为黑方棋子。
棋子数组Squares[90]存储的是每个棋子所在的格子,用“列x10+行”表示(稍后再来解释为什么不用“行x9+列”,红方最左边的车为0,黑方最左边的车为89。
这个数值整除10得到的商就是列号,余数就是行号,如果是-1,就代表这个子已被吃掉。
在棋盘上删除一个棋子,需要做两个操作(分别修改棋盘数组和棋子数组)。
同样,添加一个棋子时也需要两个操作。
执行一个着法时有三个步骤:
(1)如果目标格上已经有棋子,就要先把它从棋盘上拿走(吃子的过程);
(2)把棋子从起始格上拿走;
(3)把棋子放在目标格上。
因此执行着法简单地说就是两个ClearPiece()操作(其中一个只发生在吃子时)和一个SetPiece()操作,撤消着法的过程正好相反,但也是两个ClearPiece()和一个SetPiece()。
当然,ElephantBoard为了减少代码,把ClearPiece()和SetPiece()合并为一个函数ChangePiece(),它除了修改棋盘数组和棋子数组外,还修改Zobrist键值、位棋盘、位行和位列等信息。
“棋盘-棋子联系数组”最大的优势是:
移动一步只需要有限的运算。
对于着法产生过程,可以逐一查找棋子数组,如果该子没有被吃掉,就产生该子的所有合理着法,由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多,因此联系数组的速度要比单纯的棋盘数组快很多。
可以说,“棋盘-棋子联系数组”是所有着法生成器的基础,位棋盘等其他方法都只是辅助手段。
如今,很少有程序使用Squares[90]和Pieces[32]这样的数组了,浪费一些存储空间以换取速度是流行的做法,例如ElephantEye就用了Pieces[48]。
更多的程序使用Squares[256],这样求得行号和列号就可以用16除,这要比用9或10除快得多。
当然,把棋盘扩展成16行和16列还有更大的好处,它可以防止棋子走出棋盘边界,这点会在后面提到。
2.4扩展棋盘和着法预产生数组
在中国象棋里,短程棋子(短兵器)指的是除车和炮以外的其他棋子,它们的着法都有固定的增量(行的增量,列的增量),因此处理起来非常简单,也是着法生成技术的基础。
例如马有8个着法,增量分别是(1,2)、(-1,2)、(1,-2)、(-1,-2)、(2,1)、(2,-1)、(-2,1)和(-2,-1),红方的过河兵有3个着法,增量分别是(1,0)、(0,1)和(0,-1)。
当棋盘上的格子使用了统一的编号以后,增量也就由两个坐标变成了一个坐标。
以16x16的棋盘为例,马的8个增量就是±0x0e、±0x12、±0x1f和±0x21,兵的3个增量就是±0x01和0x10。
在16x16的扩展棋盘如下图所示,底色是红色的格子都被标上“出界”的标记,目标格在这些格子上就说明着法无效。
这样,马的着法产生就非常简单了:
constintMaxHorseMove=8;
constintHorseMovDelta[MaxHorseMove]={-0x21,-0x1f,-0x12,-0x0e,+0x0e,+0x12,+0x1f,+0x21};
constintHorseLegDelta[MaxHorseMove]={-0x10,-0x10,-0x01,+0x01,-0x01,+0x01,+0x10,+0x10};
for(i=MyFirstHorse;i //在ElephantEye的Pieces[48]中,红方的MyFirstHorse为21,MyLastHorse为22。 SrcSq=Pieces[i]; if(SrcSq! =-1){ for(j=0;j DstSq=SrcSq+HorseMovDelta[j]; LegSq=SrcSq+HorseLegDelta[j]; if(InBoard[DstSq]&&! (Squares[DstSq]&MyPieceMask)&&! Squares[LegSq]){ MoveList[MoveNum].Src=SrcSq; MoveList[MoveNum].Dst=DstSq; MoveNum++; } } } } 上面的代码是着法生成器的典型写法,用了两层循环,第一层循环用来确定要走的棋子,第二层循环用来确定棋子走到的目标格。 如果要加快程序的运行速度,第二个循环可以拆成顺序结构。 这个代码还加入了蹩马腿的判断,马腿的位置增量由HorseLegDelta[j]给出。 另外有个诀窍,如果把所有出界的格子都设置MyPieceMask和OppPieceMask标志(如果用前面所说的Pieces[48]这个数组,那么出界的格子可以用16+32=48表示),那么InBoard[DstSq]的判断也可以省去了。 其它棋子的着法也同样处理,只要注意帅(将)和仕(士)把InBoard[DstSq]改为InCity[DstSq]就可以了。 而对于兵和象等需要考虑是否能过河的棋子,判断是否过河的方法非常简单: 红方是(SrcSq/DstSq&0x80),黑方是! (SrcSq/DstSq&0x80)。 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f ElephantEye用的是Squares[90],着法生成器就没这么简单了。 对于每个短程子力,都给定一个[90][4]到[90][9]不等的数组,它们保存着棋子可以到达的绝对位置,这些数组称为“着法预产生数组”。 ElephantEye的着法预产生数组数组有些奇怪,用了HorseMovs[90][9](在目前的 程序基本上是这样的: for(i=MyFirstHorse;i<=MyLastHorse;i++){ SrcSq=Pieces[i]; if(SrcSq! =-1){ j=0; DstSq=HorseMovs[SrcSq][j]; while(DstSq! =-1){ LegSq=HorseLegs[SrcSq][j]; if(! (Squares[DstSq]&MyPieceMask)&&! Squares[LegSq]){ MoveList[MoveNum].Src=SrcSq; MoveList[MoveNum].Dst=DstSq; MoveNum++; } j++; DstSq=HorseMovs[SrcSq][j]; } } } 和前一个程序一样,这个程序也同样用了两层循环,不同之处在于第二个循环读取的是着法预产生数组,DstSq从HorseMovs[90][9]中读出,LegSq从HorseLegs[90][8]中读出,DstSq中最后一个值总是-1,所以HorseMovs的第二个维度要比HorseLeg多1。 ElephantEye的着法生成器由 2.5位行和位列 车和炮的着法分为吃子和不吃子两种,这两种着法生成器原则上是分开的,因此分为车炮不吃子、车吃子和炮吃子三个部分。 不吃子的着法可以沿着上下左右四条射线逐一生成(即并列做4个循环)。 我们感兴趣的是吃子的着法,因为静态搜索只需要生成这种着法,能否不用循环就能做到? ElephantEye几乎就做到了。 “位行”和“位列”是目前比较流行的着法生成技术,但仅限于车和炮的着法,它是否有速度上的优势还很难说,但是设计程序时可以减少一层循环,这个思想就已经比较领先了。 以“位”的形式记录棋盘上某一行所有的格子的状态(仅仅指是否有子),就称为“位行”(BitRank),与之对应的是“位列”(BitFile),棋盘结构应该包含10个位行和9个位列,即: structCchessPosition{ …… intBitFiles[9]; intBitRanks[10]; …… }; 值得注意的是,它仅仅是棋盘的附加信息,“棋盘-棋子联系数组”仍旧是必不可少的。 它的运作方式有点和“棋盘-棋子联系数组”类似: (1)同时用位行数组和位列数组表示棋盘上的棋子分布信息,位行数组和位列数组之间可以互相转换; (2)随时保持这两个数组之间的联系,棋子移动时必须同时更新这两个数组。 因此,移走或放入一颗棋子时,必须在位行和位列上置位: voidSetPiece(intSquare,intPiece){ …… x=Square/10; y=Square%10; BitFiles[x]=1< BitRanks[y]=1< …… } 车和炮是否能吃子(暂时不管吃到的是我方棋子还是敌方棋子),只取决于它所在的行和列上的每个格子上是否有棋子,而跟棋子的颜色和兵种无关,因此这些信息完全反映在位行和位列中。 预置一个“能吃到的格子”的数组,以位行或位列为指标查找数组,就可以立即知道车或炮能吃哪个子了。 预置数组到底有多大呢? intFileRookCapUp[10][1024];//某列各个位置的车(10)在各种棋子排列下(1024)能吃到的左边的子 intFileRookCapDown[10][1024]; …… intRankCannonCapLeft[9][512]; intRankCannonCapRight[9][512]; 数组中的值记录的是目标格子的偏移值,即相对于该行或列第一个格子的编号。 产生吃子着法很简单,以车吃子位例: for(i=MyFirstRook;i<=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国象棋 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)