中国象棋“深蓝”含苞待放

【 文 野生的鱼】

 从我成功开发的{dy}个软件起，我就有一个梦想，自己设计出一个{dj0}的中国象棋或围棋人机对弈系统，达到甚至打败特级大师、专业九段的水平。那时由于无知者无畏，不知深浅。现如今已在此道潜心修行了二十多载，蓦然回首，梦想未果，怅然若失。今放眼环视，悲喜交加，个中情愫纠葛，现一并道来，以慰平生，以飨棋朋博友。

 你可能会问我，早过不惑之年了，此种情结为何经久不散呢？我想主要有一下三个原因吧。一则它确实能满足我作为超级棋迷的实际需要；二来想发挥自己软件工程专业所长找些成就感；再者也是为我国棋类事业尽微薄之力吧。   

 当前三大棋国际象棋，中国象棋，围棋人机对弈水平中以国际象棋最强，中国象棋次之，围棋最弱。造成此格局的主要原因很多，如普及程度，科技水平及科研经费，复杂度不同等。以复杂度为例，具体如下表：

几种棋类的空间复杂度及树的复杂度对比  （表中的数字为搜索的复杂度的自然对数值）

       棋类         棋盘大小        空间复杂度         树的复杂度

       国际象棋      8 ×8           50                123

       中国象棋      10 ×9          52                150

       围棋         19 ×19         172                400

可以看出，中国象棋的状态空间复杂度和博弈复杂度都比国际象棋要高，围棋就更高，显然这是对中国学者提出的严峻挑战。

 所幸的是，经过半个世纪的发展，及计算机界大师积极的参与，国际象棋的人机对弈已经得相当成熟。早在上世纪， 及时代的奠基人美国的香农(Claude Elwood Shannon,1950)与被称为计算机科学之父、人工智能之父的图灵(Alan Mathison Turing,1953)提出了对象棋博弈编程的方案，成为机器博弈的创始人。系统的博弈论的研究是从国际象棋开始的，被称为“计算机之父”和“之父”的冯﹒诺依曼通过对两人零和一类博弈游戏的分析，提出了极大极小值定理，这也是博弈论产生的{dy}个里程碑。 

国际象棋是影响{zd0}研究时间最长投入研究精力最多的博弈项目，成为计算机博弈发展的主线。具体的国际象棋的编程可以通过优秀的评估函数和修剪搜索树解决，国际象棋软件的协议UCI(Universal Chess Interface即通用象棋接口)就一直在发展和完善，并已逐步成为国际象棋程序设计的标准，在此基础上的国际象棋程序自动对弈比赛也在大规模地开展，1997年IBM 公司的超级计算机深蓝战胜了国际象棋世界{gj}卡斯帕罗夫 ，成为人工智能领域的一个里程碑。我想，对于我们中国象棋，两者的相似度又很高，我们xx可以借鉴其经验，通过适当的改造甚至发展，早就我们自己的中国象棋“深蓝”。近年来，我们欣喜的看到，我们的中国象棋人机博弈的发展非常迅速，如赵明阳博士设计的象棋奇兵，在家用普通PC上达到了中国象棋业余高手水平，在高性能计算机上达到了中国象棋特级大师水平。软件特征：棋盘表示基于Bitboard；规则判断；后台思考；置换表；迭代深化；开局库；历史表；空着裁剪；学习文件；PVS搜索算法；LBR裁剪算法。荣获第十届奥林匹克中国象棋电脑软件大赛{gj}，2006年8月“浪潮杯”首届中国象棋人机大赛中一胜一和中国象棋特级大师卜风波。另外由“深蓝之父”许峰雄博士担任名誉顾问的东北大学一个研发小组开发的棋天大圣，荣获2006年和2007年的世界{gj}，其研发小组深入研究了中国象棋计算机博弈的特点，研究了中国象棋计算机博弈状态空间表示、搜索算法、数据结构、审局函数、开局库、残局库等关键技术，建立了数字化的象棋博弈模型，运用了UCCI通用引擎协议把一个棋类软件分成了“界面程序”和“引擎程序”两个部分，实现了模块间的松耦合，符合了软件工程的原则，开发出了可以达到人类特级大师水平的中国象棋博弈软件“棋天大圣”。有力开展了计算机博弈的普及活动，实实在在地推动了中国计算机博弈的发展进程等。

尽管中国象棋计算机博弈已经取得了很好的成绩，但是毕竟离战胜世界{gj}还有一定的差距，同国际象棋相比也逊色不少，中国象棋有它自己独特的特点，如大的棋盘，不同的子力和走法规则等，要做的工作还有很多，我认为主要应在以下方面做好研究：

棋盘的表示不象国际象棋刚好用6位位图表示，还没有统一高效的方法；局面采用64位HASH函数表示，高效{wy}；开局库的高效检索优化及引入评估函数；尤其是核心搜索算法博弈树的α-β剪枝优化，引进{zx1}的遗传变异算法，并行计算，BP神经网络技术，自适应学习方法等，尤其是后者；评价函数需要快速科学精准；残局库的完备性等。另外，可借鉴互联网成功的TCP/IP协议分层的经验，简化和标准化复杂问题。同时，采用符合软件工程的规范，技术和流程来开发系统，如做好质量与过程管理，原型化、瀑布型等多种开发方法，做到高内聚低耦合等。计算机博弈的水平很大程度取决于计算机搜索的广度与深度，也就是计算机的计算能力与存储能力。60年代中期机器的计算能力仅能达到每秒200步，它的搜索深度最多也就6层。到了1997年的“超级深蓝”则可达到每秒2亿步。这时的搜索深度可以达到14层，局部高达40层。合理精巧的数据结构和先进有效的搜索算法仍然是最为关键的研究内容，因为它们直接关系到搜索的广度与深度。可以说，在这方面的研究也是永无止境的。

令人欣慰的是，以上方面国内有许多业内人士已在开展了研究，其中也有不少硕士博士加盟。如大连交通大学的鹿荣，在其硕士论文中提出了一种新的混合博弈树的搜索算法，其基本搜索算法如：PVS 搜索、静寂搜索等；高级搜索算法为1) 历史启发；2）杀手启发；3) 迭代深化；4))迭代深化，它能够根据搜索所需要的时间选择搜索深度；5) 改进的置换表等。同时也设计了一种新的评估函数在中国象棋开局库中的应用，结合了利用共轭梯度求解二次{zy}的方法，尽可能的保证系统在开局阶段便处于优势，并使开局库具有一定的自学习能力，提高了博弈水平。哈尔滨工程大学的硕士王一非的《具有自学习功能的计算机象棋博弈系统的研究与实现》硕士学位论文，其中主要运用神经网络结合时间差分算法的方法来代替传统的线性估值函数 ,利用强化学习的方法，使象棋程序具有自学习的功能 ,使计算机在对弈的过程中不断地学习。这是一种非常有意义的尝试 。我认为这也是以后人工智能研究的方向，也是攻克围棋博弈算法的利器。

可以预见，在不远的未来，在国内外专家学者棋迷的共同努力下，随着计算机软硬件技术的不断进步，古老灿烂的中国国粹文化之一---中国象棋的人机博弈水平很快会登峰造顶，迎来属于我们自己的中国象棋的“深蓝”。当然，围棋的“深蓝”之路才刚刚开始,还很幼稚，其设计难度曾令软件天才、IT枭雄比尔.盖茨望而却步，令“深蓝之父”许峰雄博士感叹。但放眼天下，许多IT志士已开始了其艰难的探索之旅，如中国科学院计算机技术研究所的梁永全，史忠植，张玉志博士，清华大学硕士谷蓉等。路慢慢其修远兮，我们将上下而求索！为了梦想，为了抱负，为了博弈人生，为了缺失的信仰，也为了使国粹进一步走向世界，让我们携起手来，继往开来吧！

草写于 2010-04-26