文档介绍：中国象棋算法————————————————————————————————作者:————————————————————————————————日期: 解剖大象的眼睛——中国象棋程序设计探索黄晨* 2005年6月(*联系地址:复旦大学化学系表面化学实验室,eMail:morning_yellow@) (一)引言我在今年2月写出了象棋程序ElephantEye的第一个版本(),本来它只是象棋界面ElephantBoard的调试引擎。在设计程序的过程中,我尝试性地加入了很多算法,发现每次改进都能让程序的棋力有大幅度的提高,因此便对象棋程序的算法产生了浓厚的兴趣。到现在我已经陆续对ElephantEye作了几十次加工(),使得它的棋力接近了中等商业软件的水平,在公开源代码的象棋程序中,ElephantEye是最强的一个。我希望能通过公开源代码的方式,推动中国象棋程序水平的整体发展,然而根据很多网友的反馈意见,发现源代码中的很多部分并不是那么容易理解的。因此我才打算以《中国象棋程序设计探索》为题,写几篇详细介绍ElephantEye算法的连载,希望能让的源代码充分发挥它的作用。下面我先简要谈一下我自己对ElephantEye的体会。 ? 在我写本次连载以前,我已经完成了《象棋百科全书》网站上《对弈程序基本技术》专题中所有文章的翻译,ElephantEye的大部分算法都参考了这些文章,这些算法我会在连载中一笔带过,详细的内容希望读者参考这些译文,那里还有我加的很多译注,希望它们能够加深读者对这些算法的体会。当然,仅根据这些文章所提供的算法,是写不出很好的程序的,我参考了王小春的《PC游戏编程——人机博弈》一书,也参考了一些国际象棋的源程序,并通过自己的探索,在ElephantEye中加入了另外的非常重要的算法,尤其是启发算法,我认为它们在程序中发挥了关键性的作用,而且很多细节在绝大多数文字资料中没有详细给出,我会在我的连载中重点介绍。我猜读者最感兴趣的内容是ElephantEye的着法生成器,这应该算是象棋程序的核心部分,同时也是各个程序差异最大的部分。在写ElephantEye以前,我在《象棋百科全书》网站上刊登了大量介绍“位棋盘”的文章,这是个非常有吸引力的思想,但是我试验下来觉得它的速度并不快,在ElephantEye的程序里我只把位棋盘运用在将军判断上。尽管如此,ElephantEye短短10行的将军判断也许是程序的一个亮点吧,那么这部分内容我将尽量介绍得详细一点。此外,一些看似和棋力关系不大的技术,诸如开局库、长将检测、后台思考、时间策略、引擎协议等等,其实也直接影响着象棋程序的稳定性,因此也有必要逐一讲解。总之,每个技术都很重要,我的连载虽然不能面面俱到,但我会尽我所能来作详细阐述的。 ? ElephantEye是“蛮力型”象棋程序,与大多数商业程序的不同之处在于,它没有审局能力,那么它的棋力到底有多强?网友对这个问题众说纷纭,有人认为它无法跟一流的商业软件相比,毕竟ElephantEye是免费程序,其源代码又是公开的,为什么非要去和顶尖程序去比呢?也有人认为它能战胜中等商业软件,但电脑对电脑和电脑对人类根本就不是一回事,这么一个不懂得防守空头炮的程序怎能说它厉害呢?还有人喜欢在同一搜索水平(比如6层、8层或10层)上比较两个不同的程序,这种标准去比较“蛮力型”程序和“知识型”程序,这有意义吗? 要正确认识这个问题,我想说明几点: (1)测试标准要合理,这个标准只能是“时限”,即给两个程序以同样多的时间,可以对每步都限定时间,也可以是比赛所采用的时段制或加时制,而不能以同样的搜索水平作标准。另外,如果两个程序运行在同一台电脑上,那么不能启用后台思考功能。(2)某几盘对局并不能说明问题,我以“浅红象棋”为平台用ElephantEye对阵“梦入神蛋”,ElephantEye遗憾地以2:3败北。我有充分的信心表明ElephantEye的棋力比梦入神蛋强得多,因为两者用了相同的评价函数,但同样时间ElephantEye通常要比梦入神蛋多搜索一层以上,那么2:3的比分又能说明什么问题呢? (3)跟人类比和跟电脑比是两回事,每个电脑程序都有弱点,这些弱点很容易被人类棋手抓住,但其他电脑程序则不会抓住你的弱点。一般认为,知识缺乏的程序弱点也多(例如ElephantEye不懂得防守空头炮),因此对阵人类棋手失败的几率要比对阵其他程序高得多。 ? 要说ElephantEye一点象棋知识都不具备,这种观点我是无法接受的。很多搜索算法确实只能用在象棋上,这一点ElephantEye做得